:: Relations and Their Basic Properties
:: by Edmund Woronowicz
::
:: Received March 15, 1989
:: Copyright (c) 1990-2012 Association of Mizar Users


begin

definition
let IT be set ;
attrIT is Relation-like  means :Def1: :: RELAT_1:def 1
 for x being set st x in IT holds
ex y, z being set st x = [y,z];
end;

:: deftheorem Def1 defines Relation-like RELAT_1:def_1_:_
 for IT being set holds
( IT is Relation-like iff for x being set st x in IT holds
ex y, z being set st x = [y,z] );

registration
cluster empty  ->  Relation-like for set ;
coherence
 for b1 being set st b1 is empty holds
b1 is Relation-like
proofend;
end;

definition
mode Relation is Relation-like set ;
end;

registration
let R be Relation;
cluster  ->  Relation-like for Element of bool R;
coherence
 for b1 being Subset of R holds b1 is Relation-like
proofend;
end;

scheme :: RELAT_1:sch 1
RelExistence{ F1() ->  set , F2() ->  set , P1[ set , set ] } :
 ex R being Relation st
for x, y being set holds
( [x,y] in R iff ( x in F1() & y in F2() & P1[x,y] ) )
proofend;

definition
let P, R be Relation;
redefine pred P = R means :: RELAT_1:def 2
 for a, b being set holds
( [a,b] in P iff [a,b] in R );
compatibility
 ( P = R iff for a, b being set holds
( [a,b] in P iff [a,b] in R ) )
proofend;
end;

:: deftheorem  defines = RELAT_1:def_2_:_
 for P, R being Relation holds
( P = R iff for a, b being set holds
( [a,b] in P iff [a,b] in R ) );

registration
let P be Relation;
let X be set ;
clusterP /\ X ->  Relation-like ;
coherence
 P /\ X is Relation-like
proofend;
clusterP \ X ->  Relation-like ;
coherence
 P \ X is Relation-like ;
end;

registration
let P, R be Relation;
clusterP \/ R ->  Relation-like ;
coherence
 P \/ R is Relation-like
proofend;
end;

registration
let R, S be Relation;
clusterR \+\ S ->  Relation-like ;
coherence
 R \+\ S is Relation-like ;
end;

registration
let a, b be set ;
cluster{[a,b]} ->  Relation-like ;
coherence
 {[a,b]} is Relation-like
proofend;
cluster[:a,b:] ->  Relation-like ;
coherence
 [:a,b:] is Relation-like
proofend;
end;

registration
let a, b, c, d be set ;
cluster{[a,b],[c,d]} ->  Relation-like ;
coherence
 {[a,b],[c,d]} is Relation-like
proofend;
end;

definition
let P be Relation;
let A be set ;
redefine pred P c= A means :: RELAT_1:def 3
 for a, b being set st [a,b] in P holds
[a,b] in A;
compatibility
 ( P c= A iff for a, b being set st [a,b] in P holds
[a,b] in A )
proofend;
end;

:: deftheorem  defines c= RELAT_1:def_3_:_
 for P being Relation
for A being set holds
( P c= A iff for a, b being set st [a,b] in P holds
[a,b] in A );

notation
let R be Relation;
synonym  dom R for  proj1 R;
end;

theorem Th1: :: RELAT_1:1
for P, R being Relation holds dom (P \/ R) = (dom P) \/ (dom R) by XTUPLE_0:23;

theorem Th2: :: RELAT_1:2
for P, R being Relation holds dom (P /\ R) c= (dom P) /\ (dom R) by XTUPLE_0:24;

theorem :: RELAT_1:3
for P, R being Relation holds (dom P) \ (dom R) c= dom (P \ R) by XTUPLE_0:25;

notation
let R be Relation;
synonym  rng R for  proj2 R;
end;

theorem :: RELAT_1:4
canceled;

theorem :: RELAT_1:5
canceled;

theorem :: RELAT_1:6
canceled;

theorem Th7: :: RELAT_1:7
for R being Relation holds R c= [:(dom R),(rng R):]
proofend;

theorem :: RELAT_1:8
for R being Relation holds R /\ [:(dom R),(rng R):] = R by Th7, XBOOLE_1:28;

theorem Th9: :: RELAT_1:9
for x, y being set
for R being Relation st R = {[x,y]} holds
( dom R = {x} & rng R = {y} )
proofend;

theorem :: RELAT_1:10
for a, b, x, y being set
for R being Relation st R = {[a,b],[x,y]} holds
( dom R = {a,x} & rng R = {b,y} )
proofend;

theorem Th11: :: RELAT_1:11
for P, R being Relation st P c= R holds
( dom P c= dom R & rng P c= rng R ) by XTUPLE_0:8, XTUPLE_0:9;

theorem Th12: :: RELAT_1:12
for P, R being Relation holds rng (P \/ R) = (rng P) \/ (rng R) by XTUPLE_0:27;

theorem Th13: :: RELAT_1:13
for P, R being Relation holds rng (P /\ R) c= (rng P) /\ (rng R) by XTUPLE_0:28;

theorem :: RELAT_1:14
for P, R being Relation holds (rng P) \ (rng R) c= rng (P \ R) by XTUPLE_0:29;

:: FIELD OF RELATION
definition
canceled;
canceled;
let R be Relation;
func field R ->  set  equals :: RELAT_1:def 6
(dom R) \/ (rng R);
coherence
 (dom R) \/ (rng R) is set ;
end;

:: deftheorem  RELAT_1:def_4_:_
canceled;

:: deftheorem  RELAT_1:def_5_:_
canceled;

:: deftheorem  defines field RELAT_1:def_6_:_
 for R being Relation holds field R = (dom R) \/ (rng R);

theorem :: RELAT_1:15
for a, b being set
for R being Relation st [a,b] in R holds
( a in field R & b in field R )
proofend;

theorem :: RELAT_1:16
for P, R being Relation st P c= R holds
field P c= field R
proofend;

theorem Th17: :: RELAT_1:17
for x, y being set holds field {[x,y]} = {x,y}
proofend;

theorem :: RELAT_1:18
for P, R being Relation holds field (P \/ R) = (field P) \/ (field R)
proofend;

theorem :: RELAT_1:19
for P, R being Relation holds field (P /\ R) c= (field P) /\ (field R)
proofend;

:: CONVERSE RELATION
definition
let R be Relation;
funcR ~  ->  Relation means :Def7: :: RELAT_1:def 7
 for x, y being set holds
( [x,y] in it iff [y,x] in R );
existence
 ex b1 being Relation st
for x, y being set holds
( [x,y] in b1 iff [y,x] in R )
proofend;
uniqueness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff [y,x] in R ) ) & ( for x, y being set holds
( [x,y] in b2 iff [y,x] in R ) ) holds
b1 = b2
proofend;
involutiveness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff [y,x] in b2 ) ) holds
for x, y being set holds
( [x,y] in b2 iff [y,x] in b1 ) ;
end;

:: deftheorem Def7 defines ~ RELAT_1:def_7_:_
 for R, b2 being Relation holds
( b2 = R ~ iff for x, y being set holds
( [x,y] in b2 iff [y,x] in R ) );

theorem Th20: :: RELAT_1:20
for R being Relation holds
( rng R = dom (R ~) & dom R = rng (R ~) )
proofend;

theorem :: RELAT_1:21
for R being Relation holds field R = field (R ~)
proofend;

theorem :: RELAT_1:22
for P, R being Relation holds (P /\ R) ~ = (P ~) /\ (R ~)
proofend;

theorem :: RELAT_1:23
for P, R being Relation holds (P \/ R) ~ = (P ~) \/ (R ~)
proofend;

theorem :: RELAT_1:24
for P, R being Relation holds (P \ R) ~ = (P ~) \ (R ~)
proofend;

:: COMPOSITION OF RELATIONS
definition
let P, R be set ;
funcP (#) R ->  Relation means :Def8: :: RELAT_1:def 8
 for x, y being set holds
( [x,y] in it iff ex z being set st
( [x,z] in P & [z,y] in R ) );
existence
 ex b1 being Relation st
for x, y being set holds
( [x,y] in b1 iff ex z being set st
( [x,z] in P & [z,y] in R ) )
proofend;
uniqueness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff ex z being set st
( [x,z] in P & [z,y] in R ) ) ) & ( for x, y being set holds
( [x,y] in b2 iff ex z being set st
( [x,z] in P & [z,y] in R ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def8 defines (#) RELAT_1:def_8_:_
 for P, R being set
for b3 being Relation holds
( b3 = P (#) R iff for x, y being set holds
( [x,y] in b3 iff ex z being set st
( [x,z] in P & [z,y] in R ) ) );

notation
let P, R be Relation;
synonym P * R for P (#) R;
end;

theorem Th25: :: RELAT_1:25
for P, R being Relation holds dom (P * R) c= dom P
proofend;

theorem Th26: :: RELAT_1:26
for P, R being Relation holds rng (P * R) c= rng R
proofend;

theorem :: RELAT_1:27
for R, P being Relation st rng R c= dom P holds
dom (R * P) = dom R
proofend;

theorem :: RELAT_1:28
for P, R being Relation st dom P c= rng R holds
rng (R * P) = rng P
proofend;

theorem Th29: :: RELAT_1:29
for P, R, Q being Relation st P c= R holds
Q * P c= Q * R
proofend;

theorem Th30: :: RELAT_1:30
for P, Q, R being Relation st P c= Q holds
P * R c= Q * R
proofend;

theorem :: RELAT_1:31
for P, R, Q, S being Relation st P c= R & Q c= S holds
P * Q c= R * S
proofend;

theorem :: RELAT_1:32
for P, R, Q being Relation holds P * (R \/ Q) = (P * R) \/ (P * Q)
proofend;

theorem :: RELAT_1:33
for P, R, Q being Relation holds P * (R /\ Q) c= (P * R) /\ (P * Q)
proofend;

theorem :: RELAT_1:34
for P, R, Q being Relation holds (P * R) \ (P * Q) c= P * (R \ Q)
proofend;

theorem :: RELAT_1:35
for P, R being Relation holds (P * R) ~ = (R ~) * (P ~)
proofend;

theorem Th36: :: RELAT_1:36
for P, R, Q being Relation holds (P * R) * Q = P * (R * Q)
proofend;

:: EMPTY RELATION
registration
cluster non empty Relation-like for set ;
existence
 not for b1 being Relation holds b1 is empty
proofend;
end;

registration
let f be non empty Relation;
cluster dom f ->  non empty ;
coherence
 not dom f is empty
proofend;
cluster rng f ->  non empty ;
coherence
 not rng f is empty
proofend;
end;

theorem Th37: :: RELAT_1:37
for R being Relation st ( for x, y being set holds not [x,y] in R ) holds
R = {}
proofend;

theorem Th38: :: RELAT_1:38
( dom {} = {} & rng {} = {} )
proofend;

theorem Th39: :: RELAT_1:39
for R being Relation holds
( {} * R = {} & R * {} = {} )
proofend;

registration
let X be empty set ;
cluster dom X ->  empty ;
coherence
 dom X is empty ;
cluster rng X ->  empty ;
coherence
 rng X is empty ;
let R be Relation;
clusterX (#) R ->  empty ;
coherence
 X * R is empty by Th39;
clusterR (#) X ->  empty ;
coherence
 R * X is empty by Th39;
end;

theorem :: RELAT_1:40
field {} = {} ;

theorem Th41: :: RELAT_1:41
for R being Relation st ( dom R = {} or rng R = {} ) holds
R = {} ;

theorem :: RELAT_1:42
for R being Relation holds
( dom R = {} iff rng R = {} ) by Th38, Th41;

registration
let X be empty set ;
clusterX ~  ->  empty ;
coherence
 X ~ is empty
proofend;
end;

theorem :: RELAT_1:43
{} ~ = {} ;

theorem :: RELAT_1:44
for R, P being Relation st rng R misses dom P holds
R * P = {}
proofend;

definition
let R be Relation;
attrR is non-empty  means :Def9: :: RELAT_1:def 9
 not {} in rng R;
end;

:: deftheorem Def9 defines non-empty RELAT_1:def_9_:_
 for R being Relation holds
( R is non-empty iff not {} in rng R );

registration
cluster Relation-like non-empty for set ;
existence
 ex b1 being Relation st b1 is non-empty
proofend;
end;

registration
let R be Relation;
let S be non-empty Relation;
clusterR (#) S ->  non-empty ;
coherence
 R * S is non-empty
proofend;
end;

:: IDENTITY RELATION
definition
let X be set ;
func id X ->  Relation means :Def10: :: RELAT_1:def 10
 for x, y being set holds
( [x,y] in it iff ( x in X & x = y ) );
existence
 ex b1 being Relation st
for x, y being set holds
( [x,y] in b1 iff ( x in X & x = y ) )
proofend;
uniqueness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff ( x in X & x = y ) ) ) & ( for x, y being set holds
( [x,y] in b2 iff ( x in X & x = y ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def10 defines id RELAT_1:def_10_:_
 for X being set
for b2 being Relation holds
( b2 = id X iff for x, y being set holds
( [x,y] in b2 iff ( x in X & x = y ) ) );

registration
let X be set ;
reduce dom (id X) to X;
reducibility
 dom (id X) = X
proofend;
reduce rng (id X) to X;
reducibility
 rng (id X) = X
proofend;
end;

theorem :: RELAT_1:45
for X being set holds
( dom (id X) = X & rng (id X) = X ) ;

registration
let X be set ;
reduce(id X) ~  to  id X;
reducibility
 (id X) ~ = id X
proofend;
end;

theorem :: RELAT_1:46
for X being set holds (id X) ~ = id X ;

theorem :: RELAT_1:47
for X being set
for R being Relation st ( for x being set st x in X holds
[x,x] in R ) holds
id X c= R
proofend;

theorem Th48: :: RELAT_1:48
for x, y, X being set
for R being Relation holds
( [x,y] in (id X) * R iff ( x in X & [x,y] in R ) )
proofend;

theorem Th49: :: RELAT_1:49
for x, y, Y being set
for R being Relation holds
( [x,y] in R * (id Y) iff ( y in Y & [x,y] in R ) )
proofend;

theorem Th50: :: RELAT_1:50
for X being set
for R being Relation holds
( R * (id X) c= R & (id X) * R c= R )
proofend;

theorem Th51: :: RELAT_1:51
for X being set
for R being Relation st dom R c= X holds
(id X) * R = R
proofend;

theorem :: RELAT_1:52
for R being Relation holds (id (dom R)) * R = R by Th51;

theorem Th53: :: RELAT_1:53
for Y being set
for R being Relation st rng R c= Y holds
R * (id Y) = R
proofend;

theorem :: RELAT_1:54
for R being Relation holds R * (id (rng R)) = R by Th53;

theorem :: RELAT_1:55
id {} = {}
proofend;

theorem :: RELAT_1:56
for X being set
for P2, R, P1 being Relation st rng P2 c= X & P2 * R = id (dom P1) & R * P1 = id X holds
P1 = P2
proofend;

definition
let R be Relation;
let X be set ;
funcR | X ->  Relation means :Def11: :: RELAT_1:def 11
 for x, y being set holds
( [x,y] in it iff ( x in X & [x,y] in R ) );
existence
 ex b1 being Relation st
for x, y being set holds
( [x,y] in b1 iff ( x in X & [x,y] in R ) )
proofend;
uniqueness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff ( x in X & [x,y] in R ) ) ) & ( for x, y being set holds
( [x,y] in b2 iff ( x in X & [x,y] in R ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def11 defines | RELAT_1:def_11_:_
 for R being Relation
for X being set
for b3 being Relation holds
( b3 = R | X iff for x, y being set holds
( [x,y] in b3 iff ( x in X & [x,y] in R ) ) );

registration
let R be Relation;
let X be empty set ;
clusterR | X ->  empty ;
coherence
 R | X is empty
proofend;
end;

theorem Th57: :: RELAT_1:57
for x, X being set
for R being Relation holds
( x in dom (R | X) iff ( x in X & x in dom R ) )
proofend;

theorem Th58: :: RELAT_1:58
for X being set
for R being Relation holds dom (R | X) c= X
proofend;

theorem Th59: :: RELAT_1:59
for X being set
for R being Relation holds R | X c= R
proofend;

theorem Th60: :: RELAT_1:60
for X being set
for R being Relation holds dom (R | X) c= dom R
proofend;

theorem Th61: :: RELAT_1:61
for X being set
for R being Relation holds dom (R | X) = (dom R) /\ X
proofend;

theorem :: RELAT_1:62
for X being set
for R being Relation st X c= dom R holds
dom (R | X) = X
proofend;

theorem :: RELAT_1:63
for X being set
for R, P being Relation holds (R | X) * P c= R * P by Th30, Th59;

theorem :: RELAT_1:64
for X being set
for P, R being Relation holds P * (R | X) c= P * R by Th29, Th59;

theorem :: RELAT_1:65
for X being set
for R being Relation holds R | X = (id X) * R
proofend;

theorem :: RELAT_1:66
for X being set
for R being Relation holds
( R | X = {} iff dom R misses X )
proofend;

theorem Th67: :: RELAT_1:67
for X being set
for R being Relation holds R | X = R /\ [:X,(rng R):]
proofend;

theorem Th68: :: RELAT_1:68
for X being set
for R being Relation st dom R c= X holds
R | X = R
proofend;

registration
let R be Relation;
reduceR | (dom R) to R;
reducibility
 R | (dom R) = R by Th68;
end;

theorem :: RELAT_1:69
for R being Relation holds R | (dom R) = R ;

theorem Th70: :: RELAT_1:70
for X being set
for R being Relation holds rng (R | X) c= rng R
proofend;

theorem Th71: :: RELAT_1:71
for X, Y being set
for R being Relation holds (R | X) | Y = R | (X /\ Y)
proofend;

registration
let R be Relation;
let X be set ;
reduce(R | X) | X to R | X;
reducibility
 (R | X) | X = R | X
proofend;
end;

theorem :: RELAT_1:72
for X being set
for R being Relation holds (R | X) | X = R | X ;

theorem :: RELAT_1:73
for X, Y being set
for R being Relation st X c= Y holds
(R | X) | Y = R | X
proofend;

theorem :: RELAT_1:74
for Y, X being set
for R being Relation st Y c= X holds
(R | X) | Y = R | Y
proofend;

theorem Th75: :: RELAT_1:75
for X, Y being set
for R being Relation st X c= Y holds
R | X c= R | Y
proofend;

theorem Th76: :: RELAT_1:76
for X being set
for P, R being Relation st P c= R holds
P | X c= R | X
proofend;

theorem Th77: :: RELAT_1:77
for X, Y being set
for P, R being Relation st P c= R & X c= Y holds
P | X c= R | Y
proofend;

theorem Th78: :: RELAT_1:78
for X, Y being set
for R being Relation holds R | (X \/ Y) = (R | X) \/ (R | Y)
proofend;

theorem :: RELAT_1:79
for X, Y being set
for R being Relation holds R | (X /\ Y) = (R | X) /\ (R | Y)
proofend;

theorem Th80: :: RELAT_1:80
for X, Y being set
for R being Relation holds R | (X \ Y) = (R | X) \ (R | Y)
proofend;

registration
let R be empty Relation;
let X be set ;
clusterR | X ->  empty ;
coherence
 R | X is empty
proofend;
end;

theorem :: RELAT_1:81
for R being Relation holds R | {} = {} ;

theorem :: RELAT_1:82
for X being set holds {} | X = {} ;

theorem :: RELAT_1:83
for X being set
for P, R being Relation holds (P * R) | X = (P | X) * R
proofend;

definition
let Y be set ;
let R be Relation;
funcY |` R ->  Relation means :Def12: :: RELAT_1:def 12
 for x, y being set holds
( [x,y] in it iff ( y in Y & [x,y] in R ) );
existence
 ex b1 being Relation st
for x, y being set holds
( [x,y] in b1 iff ( y in Y & [x,y] in R ) )
proofend;
uniqueness
 for b1, b2 being Relation st ( for x, y being set holds
( [x,y] in b1 iff ( y in Y & [x,y] in R ) ) ) & ( for x, y being set holds
( [x,y] in b2 iff ( y in Y & [x,y] in R ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def12 defines |` RELAT_1:def_12_:_
 for Y being set
for R, b3 being Relation holds
( b3 = Y |` R iff for x, y being set holds
( [x,y] in b3 iff ( y in Y & [x,y] in R ) ) );

registration
let R be Relation;
let X be empty set ;
clusterX |` R ->  empty ;
coherence
 X |` R is empty
proofend;
end;

theorem Th84: :: RELAT_1:84
for y, Y being set
for R being Relation holds
( y in rng (Y |` R) iff ( y in Y & y in rng R ) )
proofend;

theorem Th85: :: RELAT_1:85
for Y being set
for R being Relation holds rng (Y |` R) c= Y
proofend;

theorem Th86: :: RELAT_1:86
for Y being set
for R being Relation holds Y |` R c= R
proofend;

theorem Th87: :: RELAT_1:87
for Y being set
for R being Relation holds rng (Y |` R) c= rng R
proofend;

theorem Th88: :: RELAT_1:88
for Y being set
for R being Relation holds rng (Y |` R) = (rng R) /\ Y
proofend;

theorem :: RELAT_1:89
for Y being set
for R being Relation st Y c= rng R holds
rng (Y |` R) = Y
proofend;

theorem :: RELAT_1:90
for Y being set
for R, P being Relation holds (Y |` R) * P c= R * P by Th30, Th86;

theorem :: RELAT_1:91
for Y being set
for P, R being Relation holds P * (Y |` R) c= P * R by Th29, Th86;

theorem :: RELAT_1:92
for Y being set
for R being Relation holds Y |` R = R * (id Y)
proofend;

theorem Th93: :: RELAT_1:93
for Y being set
for R being Relation holds Y |` R = R /\ [:(dom R),Y:]
proofend;

theorem Th94: :: RELAT_1:94
for Y being set
for R being Relation st rng R c= Y holds
Y |` R = R
proofend;

registration
let R be Relation;
reduce(rng R) |` R to R;
reducibility
 (rng R) |` R = R by Th94;
end;

theorem :: RELAT_1:95
for R being Relation holds (rng R) |` R = R ;

theorem Th96: :: RELAT_1:96
for Y, X being set
for R being Relation holds Y |` (X |` R) = (Y /\ X) |` R
proofend;

registration
let Y be set ;
let R be Relation;
reduceY |` (Y |` R) to Y |` R;
reducibility
 Y |` (Y |` R) = Y |` R
proofend;
end;

theorem :: RELAT_1:97
for Y being set
for R being Relation holds Y |` (Y |` R) = Y |` R ;

theorem :: RELAT_1:98
for X, Y being set
for R being Relation st X c= Y holds
Y |` (X |` R) = X |` R
proofend;

theorem :: RELAT_1:99
for Y, X being set
for R being Relation st Y c= X holds
Y |` (X |` R) = Y |` R
proofend;

theorem Th100: :: RELAT_1:100
for X, Y being set
for R being Relation st X c= Y holds
X |` R c= Y |` R
proofend;

theorem Th101: :: RELAT_1:101
for Y being set
for P1, P2 being Relation st P1 c= P2 holds
Y |` P1 c= Y |` P2
proofend;

theorem :: RELAT_1:102
for Y1, Y2 being set
for P1, P2 being Relation st P1 c= P2 & Y1 c= Y2 holds
Y1 |` P1 c= Y2 |` P2
proofend;

theorem :: RELAT_1:103
for X, Y being set
for R being Relation holds (X \/ Y) |` R = (X |` R) \/ (Y |` R)
proofend;

theorem :: RELAT_1:104
for X, Y being set
for R being Relation holds (X /\ Y) |` R = (X |` R) /\ (Y |` R)
proofend;

theorem :: RELAT_1:105
for X, Y being set
for R being Relation holds (X \ Y) |` R = (X |` R) \ (Y |` R)
proofend;

theorem :: RELAT_1:106
for R being Relation holds {} |` R = {} ;

theorem :: RELAT_1:107
for Y being set holds Y |` {} = {}
proofend;

theorem :: RELAT_1:108
for Y being set
for P, R being Relation holds Y |` (P * R) = P * (Y |` R)
proofend;

theorem :: RELAT_1:109
for Y, X being set
for R being Relation holds (Y |` R) | X = Y |` (R | X)
proofend;

:: IMAGE OF SET IN RELATION
definition
let R be Relation;
let X be set ;
funcR .: X ->  set  means :Def13: :: RELAT_1:def 13
 for y being set holds
( y in it iff ex x being set st
( [x,y] in R & x in X ) );
existence
 ex b1 being set st
for y being set holds
( y in b1 iff ex x being set st
( [x,y] in R & x in X ) )
proofend;
uniqueness
 for b1, b2 being set st ( for y being set holds
( y in b1 iff ex x being set st
( [x,y] in R & x in X ) ) ) & ( for y being set holds
( y in b2 iff ex x being set st
( [x,y] in R & x in X ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def13 defines .: RELAT_1:def_13_:_
 for R being Relation
for X, b3 being set holds
( b3 = R .: X iff for y being set holds
( y in b3 iff ex x being set st
( [x,y] in R & x in X ) ) );

theorem Th110: :: RELAT_1:110
for y, X being set
for R being Relation holds
( y in R .: X iff ex x being set st
( x in dom R & [x,y] in R & x in X ) )
proofend;

theorem Th111: :: RELAT_1:111
for X being set
for R being Relation holds R .: X c= rng R
proofend;

theorem :: RELAT_1:112
for X being set
for R being Relation holds R .: X = R .: ((dom R) /\ X)
proofend;

theorem Th113: :: RELAT_1:113
for R being Relation holds R .: (dom R) = rng R
proofend;

theorem :: RELAT_1:114
for X being set
for R being Relation holds R .: X c= R .: (dom R)
proofend;

theorem :: RELAT_1:115
for X being set
for R being Relation holds rng (R | X) = R .: X
proofend;

registration
let R be Relation;
let X be empty set ;
clusterR .: X ->  empty ;
coherence
 R .: X is empty
proofend;
end;

registration
let R be empty Relation;
let X be set ;
clusterR .: X ->  empty ;
coherence
 R .: X is empty
proofend;
end;

theorem :: RELAT_1:116
canceled;

theorem :: RELAT_1:117
canceled;

theorem :: RELAT_1:118
for X being set
for R being Relation holds
( R .: X = {} iff dom R misses X )
proofend;

theorem :: RELAT_1:119
for X being set
for R being Relation st X <> {} &amp; X c= dom R holds
R .: X <> {}
proofend;

theorem :: RELAT_1:120
for X, Y being set
for R being Relation holds R .: (X \/ Y) = (R .: X) \/ (R .: Y)
proofend;

theorem :: RELAT_1:121
for X, Y being set
for R being Relation holds R .: (X /\ Y) c= (R .: X) /\ (R .: Y)
proofend;

theorem :: RELAT_1:122
for X, Y being set
for R being Relation holds (R .: X) \ (R .: Y) c= R .: (X \ Y)
proofend;

theorem Th123: :: RELAT_1:123
for X, Y being set
for R being Relation st X c= Y holds
R .: X c= R .: Y
proofend;

theorem Th124: :: RELAT_1:124
for X being set
for P, R being Relation st P c= R holds
P .: X c= R .: X
proofend;

theorem :: RELAT_1:125
for X, Y being set
for P, R being Relation st P c= R &amp; X c= Y holds
P .: X c= R .: Y
proofend;

theorem :: RELAT_1:126
for X being set
for P, R being Relation holds (P * R) .: X = R .: (P .: X)
proofend;

theorem Th127: :: RELAT_1:127
for P, R being Relation holds rng (P * R) = R .: (rng P)
proofend;

theorem :: RELAT_1:128
for X, Y being set
for R being Relation holds (R | X) .: Y c= R .: Y by Th59, Th124;

theorem Th129: :: RELAT_1:129
for R being Relation
for X, Y being set st X c= Y holds
(R | Y) .: X = R .: X
proofend;

theorem :: RELAT_1:130
for X being set
for R being Relation holds (dom R) /\ X c= (R ~) .: (R .: X)
proofend;

:: INVERSE IMAGE OF SET IN RELATION
definition
let R be Relation;
let Y be set ;
funcR " Y ->  set  means :Def14: :: RELAT_1:def 14
 for x being set holds
( x in it iff ex y being set st
( [x,y] in R &amp; y in Y ) );
existence
 ex b1 being set st
for x being set holds
( x in b1 iff ex y being set st
( [x,y] in R &amp; y in Y ) )
proofend;
uniqueness
 for b1, b2 being set st ( for x being set holds
( x in b1 iff ex y being set st
( [x,y] in R &amp; y in Y ) ) ) &amp; ( for x being set holds
( x in b2 iff ex y being set st
( [x,y] in R &amp; y in Y ) ) ) holds
b1 = b2
proofend;
end;

:: deftheorem Def14 defines " RELAT_1:def_14_:_
 for R being Relation
for Y, b3 being set holds
( b3 = R " Y iff for x being set holds
( x in b3 iff ex y being set st
( [x,y] in R &amp; y in Y ) ) );

theorem Th131: :: RELAT_1:131
for x, Y being set
for R being Relation holds
( x in R " Y iff ex y being set st
( y in rng R &amp; [x,y] in R &amp; y in Y ) )
proofend;

theorem Th132: :: RELAT_1:132
for Y being set
for R being Relation holds R " Y c= dom R
proofend;

theorem :: RELAT_1:133
for Y being set
for R being Relation holds R " Y = R " ((rng R) /\ Y)
proofend;

theorem Th134: :: RELAT_1:134
for R being Relation holds R " (rng R) = dom R
proofend;

theorem :: RELAT_1:135
for Y being set
for R being Relation holds R " Y c= R " (rng R)
proofend;

registration
let R be Relation;
let Y be empty set ;
clusterR " Y ->  empty ;
coherence
 R " Y is empty
proofend;
end;

registration
let R be empty Relation;
let Y be set ;
clusterR " Y ->  empty ;
coherence
 R " Y is empty
proofend;
end;

theorem :: RELAT_1:136
canceled;

theorem :: RELAT_1:137
canceled;

theorem :: RELAT_1:138
for Y being set
for R being Relation holds
( R " Y = {} iff rng R misses Y )
proofend;

theorem :: RELAT_1:139
for Y being set
for R being Relation st Y <> {} &amp; Y c= rng R holds
R " Y <> {}
proofend;

theorem :: RELAT_1:140
for X, Y being set
for R being Relation holds R " (X \/ Y) = (R " X) \/ (R " Y)
proofend;

theorem :: RELAT_1:141
for X, Y being set
for R being Relation holds R " (X /\ Y) c= (R " X) /\ (R " Y)
proofend;

theorem :: RELAT_1:142
for X, Y being set
for R being Relation holds (R " X) \ (R " Y) c= R " (X \ Y)
proofend;

theorem Th143: :: RELAT_1:143
for X, Y being set
for R being Relation st X c= Y holds
R " X c= R " Y
proofend;

theorem Th144: :: RELAT_1:144
for Y being set
for P, R being Relation st P c= R holds
P " Y c= R " Y
proofend;

theorem :: RELAT_1:145
for X, Y being set
for P, R being Relation st P c= R &amp; X c= Y holds
P " X c= R " Y
proofend;

theorem :: RELAT_1:146
for Y being set
for P, R being Relation holds (P * R) " Y = P " (R " Y)
proofend;

theorem Th147: :: RELAT_1:147
for P, R being Relation holds dom (P * R) = P " (dom R)
proofend;

theorem :: RELAT_1:148
for Y being set
for R being Relation holds (rng R) /\ Y c= (R ~) " (R " Y)
proofend;

begin

definition
let R be Relation;
attrR is empty-yielding  means :Def15: :: RELAT_1:def 15
 rng R c= {{}};
end;

:: deftheorem Def15 defines empty-yielding RELAT_1:def_15_:_
 for R being Relation holds
( R is empty-yielding iff rng R c= {{}} );

theorem :: RELAT_1:149
for R being Relation holds
( R is empty-yielding iff for X being set st X in rng R holds
X = {} )
proofend;

:: from AMI_3
theorem :: RELAT_1:150
for f, g being Relation
for A, B being set st f | A = g | A &amp; f | B = g | B holds
f | (A \/ B) = g | (A \/ B)
proofend;

theorem :: RELAT_1:151
for X being set
for f, g being Relation st dom g c= X &amp; g c= f holds
g c= f | X
proofend;

theorem :: RELAT_1:152
for f being Relation
for X being set st X misses dom f holds
f | X = {}
proofend;

:: from AMI_5
theorem :: RELAT_1:153
for f, g being Relation
for A, B being set st A c= B &amp; f | B = g | B holds
f | A = g | A
proofend;

:: missing, 2005.07.11, A.T.
theorem :: RELAT_1:154
for R, S being Relation holds R | (dom S) = R | (dom (S | (dom R)))
proofend;

:: missing, 2005.11.13, A.T.
registration
cluster empty Relation-like  ->  empty-yielding for set ;
coherence
 for b1 being Relation st b1 is empty holds
b1 is empty-yielding
proofend;
end;

registration
let R be empty-yielding Relation;
let X be set ;
clusterR | X ->  empty-yielding ;
coherence
 R | X is empty-yielding
proofend;
end;

theorem :: RELAT_1:155
for X being set
for R being Relation st not R | X is empty-yielding holds
not R is empty-yielding ;

:: from EQREL_1 (Class), 2007.02.06
definition
let R be Relation;
let x be set ;
func Im (R,x) ->  set  equals :: RELAT_1:def 16
R .: {x};
correctness
coherence
R .: {x} is set ;
;
end;

:: deftheorem  defines Im RELAT_1:def_16_:_
 for R being Relation
for x being set holds Im (R,x) = R .: {x};

scheme :: RELAT_1:sch 2
ExtensionalityR{ F1() ->  Relation, F2() ->  Relation, P1[ set , set ] } :
 F1() = F2()
provided
A1: for a, b being set holds
( [a,b] in F1() iff P1[a,b] ) and
A2: for a, b being set holds
( [a,b] in F2() iff P1[a,b] )
proofend;

:: from SCMFSA6A, 2007.07.23, A.T.
theorem :: RELAT_1:156
for X being set
for R being Relation holds dom (R | ((dom R) \ X)) = (dom R) \ X
proofend;

theorem :: RELAT_1:157
for X being set
for R being Relation holds R | X = R | ((dom R) /\ X)
proofend;

:: missing, 2007.11.07, A.T.
theorem :: RELAT_1:158
for X, Y being set holds dom [:X,Y:] c= X
proofend;

theorem :: RELAT_1:159
for X, Y being set holds rng [:X,Y:] c= Y
proofend;

:: from FUNCOP_1, 2008.02.19, A.T.
theorem :: RELAT_1:160
for X, Y being set st X <> {} &amp; Y <> {} holds
( dom [:X,Y:] = X &amp; rng [:X,Y:] = Y )
proofend;

theorem :: RELAT_1:161
for R, Q being Relation st dom R = {} &amp; dom Q = {} holds
R = Q
proofend;

theorem :: RELAT_1:162
for R, Q being Relation st rng R = {} &amp; rng Q = {} holds
R = Q
proofend;

theorem :: RELAT_1:163
for R, Q, S being Relation st dom R = dom Q holds
dom (S * R) = dom (S * Q)
proofend;

theorem :: RELAT_1:164
for R, Q, S being Relation st rng R = rng Q holds
rng (R * S) = rng (Q * S)
proofend;

:: from RELSET_2 (R"x, generalized), 2008.07.16, A.T.
definition
let R be Relation;
let x be set ;
func Coim (R,x) ->  set  equals :: RELAT_1:def 17
R " {x};
coherence
 R " {x} is set ;
end;

:: deftheorem  defines Coim RELAT_1:def_17_:_
 for R being Relation
for x being set holds Coim (R,x) = R " {x};

:: from NECKLACE, 2008.07.25, A.T.
registration
let R be trivial Relation;
cluster dom R ->  trivial ;
coherence
 dom R is trivial
proofend;
end;

registration
let R be trivial Relation;
cluster rng R ->  trivial ;
coherence
 rng R is trivial
proofend;
end;

:: comp. RFUNCT_2:34, CFCONT_1:31, 2008.08.07, A.T.
theorem :: RELAT_1:165
for X being set
for R, S being Relation st rng R c= dom (S | X) holds
R * (S | X) = R * S
proofend;

:: from LATTICE2, 2008.09.14, A.T.
theorem :: RELAT_1:166
for A being set
for Q, R being Relation st Q | A = R | A holds
Q .: A = R .: A
proofend;

:: new, 2009.01.21, A.T
definition
let X be set ;
let R be Relation;
attrR is X -defined  means :Def18: :: RELAT_1:def 18
 dom R c= X;
attrR is X -valued  means :Def19: :: RELAT_1:def 19
 rng R c= X;
end;

:: deftheorem Def18 defines -defined RELAT_1:def_18_:_
 for X being set
for R being Relation holds
( R is X -defined iff dom R c= X );

:: deftheorem Def19 defines -valued RELAT_1:def_19_:_
 for X being set
for R being Relation holds
( R is X -valued iff rng R c= X );

Lm1:  for X, Y being set holds
( {} is X -defined &amp; {} is Y -valued )
proofend;

registration
let X, Y be set ;
cluster Relation-like X -defined Y -valued for set ;
existence
 ex b1 being Relation st
( b1 is X -defined &amp; b1 is Y -valued )
proofend;
end;

:: from QC_LANG4, 2009.01.23, A.T
theorem :: RELAT_1:167
for D being set
for R being b1 -valued Relation
for y being set st y in rng R holds
y in D
proofend;

:: new, 2009.02.07, A.T.
registration
let X, A be set ;
let R be A -valued Relation;
clusterR | X -> A -valued ;
coherence
 R | X is A -valued
proofend;
end;

registration
let X, A be set ;
let R be A -defined Relation;
clusterR | X -> X -defined A -defined ;
coherence
 ( R | X is A -defined &amp; R | X is X -defined )
proofend;
end;

registration
let X be set ;
cluster id X -> X -defined X -valued ;
coherence
 ( id X is X -defined &amp; id X is X -valued )
proofend;
end;

:: 2009.02.16, A.T.
registration
let A be set ;
let R be A -valued Relation;
let S be Relation;
clusterS (#) R -> A -valued ;
coherence
 S * R is A -valued
proofend;
end;

registration
let A be set ;
let R be A -defined Relation;
let S be Relation;
clusterR (#) S -> A -defined ;
coherence
 R * S is A -defined
proofend;
end;

:: 2009.02.16, A.T.
theorem :: RELAT_1:168
for x, X, Y being set st x in X holds
Im ([:X,Y:],x) = Y
proofend;

theorem Th169: :: RELAT_1:169
for x, y being set
for R being Relation holds
( [x,y] in R iff y in Im (R,x) )
proofend;

theorem :: RELAT_1:170
for x being set
for R being Relation holds
( x in dom R iff Im (R,x) <> {} )
proofend;

theorem :: RELAT_1:171
for X, Y being set holds
( {} is X -defined &amp; {} is Y -valued ) by Lm1;

:: 2009.10.02, A.T.
registration
cluster empty Relation-like  ->  non-empty for set ;
coherence
 for b1 being Relation st b1 is empty holds
b1 is non-empty
proofend;
end;

registration
let X be set ;
let R be X -defined Relation;
cluster  -> X -defined for Element of bool R;
coherence
 for b1 being Subset of R holds b1 is X -defined
proofend;
end;

registration
let X be set ;
let R be X -valued Relation;
cluster  -> X -valued for Element of bool R;
coherence
 for b1 being Subset of R holds b1 is X -valued
proofend;
end;

:: missing, 2010.01.02, A.T
theorem :: RELAT_1:172
for X, Y being set
for R being Relation st X misses Y holds
(R | X) | Y = {}
proofend;

:: from AMISTD_3, 2010.01.10, A.T.
theorem :: RELAT_1:173
for x being set holds field {[x,x]} = {x}
proofend;

registration
let X be set ;
let R be X -defined Relation;
reduceR | X to R;
reducibility
 R | X = R
proofend;
end;

registration
let Y be set ;
let R be Y -valued Relation;
reduceY |` R to R;
reducibility
 Y |` R = R
proofend;
end;

theorem :: RELAT_1:174
for X being set
for R being b1 -defined Relation holds R = R | X ;

theorem :: RELAT_1:175
for X being set
for S being Relation
for R being b1 -defined Relation st R c= S holds
R c= S | X
proofend;

:: missing, 2010.04.07, A.T.
theorem Th176: :: RELAT_1:176
for X, A being set
for R being Relation st dom R c= X holds
R \ (R | A) = R | (X \ A)
proofend;

theorem Th177: :: RELAT_1:177
for A being set
for R being Relation holds dom (R \ (R | A)) = (dom R) \ A
proofend;

theorem :: RELAT_1:178
for A being set
for R being Relation holds (dom R) \ (dom (R | A)) = dom (R \ (R | A))
proofend;

theorem :: RELAT_1:179
for R, S being Relation st dom R misses dom S holds
R misses S
proofend;

theorem :: RELAT_1:180
for R, S being Relation st rng R misses rng S holds
R misses S
proofend;

theorem :: RELAT_1:181
for X, Y being set
for R being Relation st X c= Y holds
(R \ (R | Y)) | X = {}
proofend;

theorem :: RELAT_1:182
for X, Y being set st X c= Y holds
for R being b1 -defined Relation holds R is Y -defined
proofend;

theorem :: RELAT_1:183
for X, Y being set st X c= Y holds
for R being b1 -valued Relation holds R is Y -valued
proofend;

theorem :: RELAT_1:184
for R, S being Relation holds
( R c= S iff R c= S | (dom R) )
proofend;

theorem :: RELAT_1:185
for X, Y being set
for R being b1 -defined b2 -valued Relation holds R c= [:X,Y:]
proofend;

:: new, 20011.06.11, A.T.
theorem Th186: :: RELAT_1:186
for X being set
for R being Relation holds dom (X |` R) c= dom R
proofend;

registration
let A, X be set ;
let R be A -defined Relation;
clusterX |` R -> A -defined ;
coherence
 X |` R is A -defined
proofend;
end;

registration
let X, A be set ;
let R be A -valued Relation;
clusterX |` R -> X -valued A -valued ;
coherence
 ( X |` R is A -valued &amp; X |` R is X -valued )
proofend;
end;

registration
let X be empty set ;
cluster Relation-like X -defined  ->  empty X -defined for set ;
coherence
 for b1 being X -defined Relation holds b1 is empty
proofend;
cluster Relation-like X -valued  ->  empty X -valued for set ;
coherence
 for b1 being X -valued Relation holds b1 is empty
proofend;
end;