:: Transitive Closure of Fuzzy Relations
:: by Takashi Mitsuishi and Grzegorz Bancerek
::
:: Received November 23, 2003
:: Copyright (c) 2003-2021 Association of Mizar Users

registration

let X be non empty set ;

cluster [.0,1.] -valued Function-like quasi_total -> real-valued for Element of bool [:X,REAL:];

coherence
for b₁ being Membership_Func of X holds b₁ is real-valued ;

end;

definition

let X, Y be non empty set ;
let f, g be RMembership_Func of X,Y;

:: original: is_less_than
redefine pred f is_less_than g means :: LFUZZY_1:def 1
for x being Element of X
for y being Element of Y holds f . (x,y) <= g . (x,y);

compatibility
( f is_less_than g iff for x being Element of X
for y being Element of Y holds f . (x,y) <= g . (x,y) )

proof end;

end;

:: deftheorem defines is_less_than LFUZZY_1:def 1 :
for X, Y being non empty set
for f, g being RMembership_Func of X,Y holds
( f is_less_than g iff for x being Element of X
for y being Element of Y holds f . (x,y) <= g . (x,y) );

theorem Th1: :: LFUZZY_1:1

for X being non empty set
for R, S being Membership_Func of X st ( for x being Element of X holds R . x = S . x ) holds
R = S

proof end;

theorem Th2: :: LFUZZY_1:2

for X, Y being non empty set
for R, S being RMembership_Func of X,Y st ( for x being Element of X
for y being Element of Y holds R . (x,y) = S . (x,y) ) holds
R = S

proof end;

theorem Th3: :: LFUZZY_1:3

for X being non empty set
for R, S being Membership_Func of X holds
( R = S iff ( S c= & R c= ) )

proof end;

theorem :: LFUZZY_1:4

for X being non empty set
for R being Membership_Func of X holds R c= ;

theorem Th5: :: LFUZZY_1:5

for X being non empty set
for R, S, T being Membership_Func of X st S c= & T c= holds
T c=

proof end;

theorem Th6: :: LFUZZY_1:6

for X, Y, Z being non empty set
for R, S being RMembership_Func of X,Y
for T, U being RMembership_Func of Y,Z st S c= & U c= holds
S (#) U c=

proof end;

definition

let X be non empty set ;
let f, g be Membership_Func of X;
:: original: min
redefine func min (f,g) -> Element of bool [:X,REAL:];
commutativity
for f, g being Membership_Func of X holds min (f,g) = min (g,f) ;
:: original: max
redefine func max (f,g) -> Element of bool [:X,REAL:];
commutativity
for f, g being Membership_Func of X holds max (f,g) = max (g,f) ;

end;

theorem :: LFUZZY_1:7

for X being non empty set
for f, g being Membership_Func of X holds f c=

proof end;

theorem :: LFUZZY_1:8

for X being non empty set
for f, g being Membership_Func of X holds max (f,g) c=

proof end;

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

attr R is reflexive means :: LFUZZY_1:def 2
R c= ;

end;

:: deftheorem defines reflexive LFUZZY_1:def 2 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is reflexive iff R c= );

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

redefine attr R is reflexive means :: LFUZZY_1:def 3
for x being Element of X holds R . (x,x) = 1;

compatibility
( R is reflexive iff for x being Element of X holds R . (x,x) = 1 )

proof end;

end;

:: deftheorem defines reflexive LFUZZY_1:def 3 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is reflexive iff for x being Element of X holds R . (x,x) = 1 );

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

attr R is symmetric means :: LFUZZY_1:def 4
converse R = R;

end;

:: deftheorem defines symmetric LFUZZY_1:def 4 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is symmetric iff converse R = R );

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

redefine attr R is symmetric means :: LFUZZY_1:def 5
for x, y being Element of X holds R . (x,y) = R . (y,x);

compatibility
( R is symmetric iff for x, y being Element of X holds R . (x,y) = R . (y,x) )

proof end;

end;

:: deftheorem defines symmetric LFUZZY_1:def 5 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is symmetric iff for x, y being Element of X holds R . (x,y) = R . (y,x) );

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

attr R is transitive means :: LFUZZY_1:def 6
R c= ;

end;

:: deftheorem defines transitive LFUZZY_1:def 6 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is transitive iff R c= );

Lm1: for X, Y, Z being non empty set
for R being RMembership_Func of X,Y
for S being RMembership_Func of Y,Z
for x being Element of X
for z being Element of Z holds
( rng (min (R,S,x,z)) = { ((R . [x,y]) "/\" (S . [y,z])) where y is Element of Y : verum } & rng (min (R,S,x,z)) <> {} )

proof end;

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

redefine attr R is transitive means :: LFUZZY_1:def 7
for x, y, z being Element of X holds (R . [x,y]) "/\" (R . [y,z]) <<= R . [x,z];

compatibility
( R is transitive iff for x, y, z being Element of X holds (R . [x,y]) "/\" (R . [y,z]) <<= R . [x,z] )

proof end;

end;

:: deftheorem defines transitive LFUZZY_1:def 7 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is transitive iff for x, y, z being Element of X holds (R . [x,y]) "/\" (R . [y,z]) <<= R . [x,z] );

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

attr R is antisymmetric means :: LFUZZY_1:def 8
for x, y being Element of X st R . (x,y) <> 0 & R . (y,x) <> 0 holds
x = y;

end;

:: deftheorem defines antisymmetric LFUZZY_1:def 8 :
for X being non empty set
for R being RMembership_Func of X,X holds
( R is antisymmetric iff for x, y being Element of X st R . (x,y) <> 0 & R . (y,x) <> 0 holds
x = y );

registration

let X be non empty set ;

cluster Imf (X,X) -> reflexive symmetric transitive antisymmetric ;

coherence
( Imf (X,X) is symmetric & Imf (X,X) is transitive & Imf (X,X) is reflexive & Imf (X,X) is antisymmetric )

proof end;

end;

registration

let X be non empty set ;

cluster non empty Relation-like [:X,X:] -defined REAL -valued [.0,1.] -valued Function-like total quasi_total complex-valued ext-real-valued real-valued reflexive symmetric transitive antisymmetric for Element of bool [:[:X,X:],REAL:];

existence
ex b₁ being RMembership_Func of X,X st
( b₁ is reflexive & b₁ is transitive & b₁ is symmetric & b₁ is antisymmetric )

proof end;

end;

theorem Th9: :: LFUZZY_1:9

for X being non empty set
for R, S being RMembership_Func of X,X st R is symmetric & S is symmetric holds
converse (min (R,S)) = min (R,S) by FUZZY_4:8;

theorem Th10: :: LFUZZY_1:10

for X being non empty set
for R, S being RMembership_Func of X,X st R is symmetric & S is symmetric holds
converse (max (R,S)) = max (R,S) by FUZZY_4:7;

registration

let X be non empty set ;
let R, S be symmetric RMembership_Func of X,X;

cluster min (R,S) -> symmetric ;

coherence
min (R,S) is symmetric by Th9;

cluster max (R,S) -> symmetric ;

coherence
max (R,S) is symmetric by Th10;

end;

theorem Th11: :: LFUZZY_1:11

for X being non empty set
for R, S being RMembership_Func of X,X st R is transitive & S is transitive holds
min (R,S) c=

proof end;

registration

let X be non empty set ;
let R, S be transitive RMembership_Func of X,X;

cluster min (R,S) -> transitive ;

coherence
min (R,S) is transitive by Th11;

end;

definition

let A be set ;
let X be non empty set ;
:: original: chi
redefine func chi (A,X) -> Membership_Func of X;
coherence
chi (A,X) is Membership_Func of X

proof end;

end;

theorem :: LFUZZY_1:12

for X being non empty set
for r being Relation of X st r is_reflexive_in X holds
chi (r,[:X,X:]) is reflexive

proof end;

theorem :: LFUZZY_1:13

for X being non empty set
for r being Relation of X st r is antisymmetric holds
chi (r,[:X,X:]) is antisymmetric

proof end;

theorem :: LFUZZY_1:14

for X being non empty set
for r being Relation of X st r is symmetric holds
chi (r,[:X,X:]) is symmetric

proof end;

theorem :: LFUZZY_1:15

for X being non empty set
for r being Relation of X st r is transitive holds
chi (r,[:X,X:]) is transitive

proof end;

theorem :: LFUZZY_1:16

for X being non empty set holds
( Zmf (X,X) is symmetric & Zmf (X,X) is antisymmetric & Zmf (X,X) is transitive )

proof end;

theorem :: LFUZZY_1:17

for X being non empty set holds
( Umf (X,X) is symmetric & Umf (X,X) is transitive & Umf (X,X) is reflexive )

proof end;

theorem :: LFUZZY_1:18

for X being non empty set
for R being RMembership_Func of X,X holds max (R,(converse R)) is symmetric

proof end;

theorem :: LFUZZY_1:19

for X being non empty set
for R being RMembership_Func of X,X holds min (R,(converse R)) is symmetric

proof end;

theorem :: LFUZZY_1:20

for X being non empty set
for R, R9 being RMembership_Func of X,X st R9 is symmetric & R9 c= holds
R9 c=

proof end;

theorem :: LFUZZY_1:21

for X being non empty set
for R, R9 being RMembership_Func of X,X st R9 is symmetric & R c= holds
min (R,(converse R)) c=

proof end;

definition

let X be non empty set ;
let R be RMembership_Func of X,X;
let n be Nat;

func n iter R -> RMembership_Func of X,X means :Def9: :: LFUZZY_1:def 9
ex F being sequence of (Funcs ([:X,X:],[.0,1.])) st
( it = F . n & F . 0 = Imf (X,X) & ( for k being Nat ex Q being RMembership_Func of X,X st
( F . k = Q & F . (k + 1) = Q (#) R ) ) );

existence
ex b₁ being RMembership_Func of X,X ex F being sequence of (Funcs ([:X,X:],[.0,1.])) st
( b₁ = F . n & F . 0 = Imf (X,X) & ( for k being Nat ex Q being RMembership_Func of X,X st
( F . k = Q & F . (k + 1) = Q (#) R ) ) )

proof end;

uniqueness
for b₁, b₂ being RMembership_Func of X,X st ex F being sequence of (Funcs ([:X,X:],[.0,1.])) st
( b₁ = F . n & F . 0 = Imf (X,X) & ( for k being Nat ex Q being RMembership_Func of X,X st
( F . k = Q & F . (k + 1) = Q (#) R ) ) ) & ex F being sequence of (Funcs ([:X,X:],[.0,1.])) st
( b₂ = F . n & F . 0 = Imf (X,X) & ( for k being Nat ex Q being RMembership_Func of X,X st
( F . k = Q & F . (k + 1) = Q (#) R ) ) ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def9 defines iter LFUZZY_1:def 9 :
for X being non empty set
for R being RMembership_Func of X,X
for n being Nat
for b₄ being RMembership_Func of X,X holds
( b₄ = n iter R iff ex F being sequence of (Funcs ([:X,X:],[.0,1.])) st
( b₄ = F . n & F . 0 = Imf (X,X) & ( for k being Nat ex Q being RMembership_Func of X,X st
( F . k = Q & F . (k + 1) = Q (#) R ) ) ) );

theorem Th22: :: LFUZZY_1:22

for X being non empty set
for R being RMembership_Func of X,X holds (Imf (X,X)) (#) R = R

proof end;

theorem Th23: :: LFUZZY_1:23

for X being non empty set
for R being RMembership_Func of X,X holds R (#) (Imf (X,X)) = R

proof end;

theorem Th24: :: LFUZZY_1:24

for X being non empty set
for R being RMembership_Func of X,X holds 0 iter R = Imf (X,X)

proof end;

theorem Th25: :: LFUZZY_1:25

for X being non empty set
for R being RMembership_Func of X,X holds 1 iter R = R

proof end;

theorem Th26: :: LFUZZY_1:26

for X being non empty set
for R being RMembership_Func of X,X
for n being Nat holds (n + 1) iter R = (n iter R) (#) R

proof end;

theorem Th27: :: LFUZZY_1:27

for X being non empty set
for R being RMembership_Func of X,X
for m, n being Nat holds (m + n) iter R = (m iter R) (#) (n iter R)

proof end;

theorem :: LFUZZY_1:28

for X being non empty set
for R being RMembership_Func of X,X
for m, n being Nat holds (m * n) iter R = m iter (n iter R)

proof end;

definition

let X be non empty set ;
let R be RMembership_Func of X,X;

func TrCl R -> RMembership_Func of X,X equals :: LFUZZY_1:def 10
"\/" ( { (n iter R) where n is Element of NAT : n > 0 } ,(FuzzyLattice [:X,X:]));

coherence
"\/" ( { (n iter R) where n is Element of NAT : n > 0 } ,(FuzzyLattice [:X,X:])) is RMembership_Func of X,X

proof end;

end;

:: deftheorem defines TrCl LFUZZY_1:def 10 :
for X being non empty set
for R being RMembership_Func of X,X holds TrCl R = "\/" ( { (n iter R) where n is Element of NAT : n > 0 } ,(FuzzyLattice [:X,X:]));

theorem Th29: :: LFUZZY_1:29

for X being non empty set
for R being RMembership_Func of X,X
for x, y being Element of X holds (TrCl R) . [x,y] = "\/" ((pi ( { (n iter R) where n is Element of NAT : n > 0 } ,[x,y])),(RealPoset [.0,1.]))

proof end;

theorem Th30: :: LFUZZY_1:30

for X being non empty set
for R being RMembership_Func of X,X holds TrCl R c=

proof end;

theorem Th31: :: LFUZZY_1:31

for X being non empty set
for R being RMembership_Func of X,X
for n being Nat st n > 0 holds
TrCl R c=

proof end;

theorem Th32: :: LFUZZY_1:32

for X being non empty set
for Q being Subset of (FuzzyLattice X)
for x being Element of X holds ("\/" (Q,(FuzzyLattice X))) . x = "\/" ((pi (Q,x)),(RealPoset [.0,1.]))

proof end;

Lm2: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ((R . (x,y)) "/\" ((@ ("\/" (Q,(FuzzyLattice [:X,X:])))) . (y,z))) where y is Element of X : verum } = { ((R . [x,y]) "/\" ("\/" ((pi (Q,[y,z])),(RealPoset [.0,1.])))) where y is Element of X : verum }

proof end;

theorem Th33: :: LFUZZY_1:33

for R being complete Heyting LATTICE
for X being Subset of R
for y being Element of R holds y "/\" ("\/" (X,R)) = "\/" ( { (y "/\" x) where x is Element of R : x in X } ,R)

proof end;

Lm3: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ((R . [x,y]) "/\" ("\/" ((pi (Q,[y,z])),(RealPoset [.0,1.])))) where y is Element of X : verum } = { ("\/" ( { ((R . [x,y9]) "/\" b) where b is Element of (RealPoset [.0,1.]) : b in pi (Q,[y9,z]) } ,(RealPoset [.0,1.]))) where y9 is Element of X : verum }

proof end;

Lm4: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ("\/" ( { ((R . [x,y]) "/\" b) where b is Element of (RealPoset [.0,1.]) : b in pi (Q,[y,z]) } ,(RealPoset [.0,1.]))) where y is Element of X : verum } = { ("\/" ( { ((R . [x,y9]) "/\" (r . [y9,z])) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } ,(RealPoset [.0,1.]))) where y9 is Element of X : verum }

proof end;

Lm5: for X, Y, Z being non empty set
for R being RMembership_Func of X,Y
for S being RMembership_Func of Y,Z
for x being Element of X
for z being Element of Z holds
( rng (min (R,S,x,z)) = { ((R . [x,y]) "/\" (S . [y,z])) where y is Element of Y : verum } & rng (min (R,S,x,z)) <> {} )

proof end;

Lm6: for X, Y, Z being non empty set
for R being RMembership_Func of X,Y
for S being RMembership_Func of Y,Z
for x being Element of X
for z being Element of Z holds (R (#) S) . [x,z] = "\/" ( { ((R . [x,y]) "/\" (S . [y,z])) where y is Element of Y : verum } ,(RealPoset [.0,1.]))

proof end;

Lm7: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ("\/" ( { ((R . [x,y]) "/\" (r . [y,z])) where y is Element of X : verum } ,(RealPoset [.0,1.]))) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } = { ("\/" ( { ((R . [x,y]) "/\" ((@ r9) . [y,z])) where y is Element of X : verum } ,(RealPoset [.0,1.]))) where r9 is Element of (FuzzyLattice [:X,X:]) : r9 in Q }

proof end;

Lm8: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ("\/" ( { ((R . [x,y]) "/\" ((@ r) . [y,z])) where y is Element of X : verum } ,(RealPoset [.0,1.]))) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } = { ((R (#) (@ r)) . [x,z]) where r is Element of (FuzzyLattice [:X,X:]) : r in Q }

proof end;

Lm9: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds { ((R (#) (@ r)) . [x,z]) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } = pi ( { (R (#) (@ r)) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } ,[x,z])

proof end;

Lm10: for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:])
for x, z being Element of X holds "\/" ( { ("\/" ( { ((R . [x,y]) "/\" (r . [y,z])) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } ,(RealPoset [.0,1.]))) where y is Element of X : verum } ,(RealPoset [.0,1.])) = "\/" ( { ("\/" ( { ((R . [x,y]) "/\" (r9 . [y,z])) where y is Element of X : verum } ,(RealPoset [.0,1.]))) where r9 is Element of (FuzzyLattice [:X,X:]) : r9 in Q } ,(RealPoset [.0,1.]))

proof end;

theorem Th34: :: LFUZZY_1:34

for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:]) holds R (#) (@ ("\/" (Q,(FuzzyLattice [:X,X:])))) = "\/" ( { (R (#) (@ r)) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } ,(FuzzyLattice [:X,X:]))

proof end;

theorem Th35: :: LFUZZY_1:35

for X being non empty set
for R being RMembership_Func of X,X
for Q being Subset of (FuzzyLattice [:X,X:]) holds (@ ("\/" (Q,(FuzzyLattice [:X,X:])))) (#) R = "\/" ( { ((@ r) (#) R) where r is Element of (FuzzyLattice [:X,X:]) : r in Q } ,(FuzzyLattice [:X,X:]))

proof end;

theorem Th36: :: LFUZZY_1:36

for X being non empty set
for R being RMembership_Func of X,X holds (TrCl R) (#) (TrCl R) = "\/" ( { ((i iter R) (#) (j iter R)) where i, j is Element of NAT : ( i > 0 & j > 0 ) } ,(FuzzyLattice [:X,X:]))

proof end;

registration

let X be non empty set ;
let R be RMembership_Func of X,X;

cluster TrCl R -> transitive ;

coherence
TrCl R is transitive

proof end;

end;

theorem Th37: :: LFUZZY_1:37

for X being non empty set
for R being RMembership_Func of X,X
for n being Nat st R is transitive & n > 0 holds
R c=

proof end;

theorem Th38: :: LFUZZY_1:38

for X being non empty set
for R being RMembership_Func of X,X st R is transitive holds
R = TrCl R

proof end;

theorem Th39: :: LFUZZY_1:39

for X being non empty set
for R, S being RMembership_Func of X,X
for n being Nat st S c= holds
n iter S c=

proof end;

theorem :: LFUZZY_1:40

for X being non empty set
for R, S being RMembership_Func of X,X st S is transitive & S c= holds
S c=

proof end;