:: Reduction Relations
:: by Grzegorz Bancerek
::
:: Received November 14, 1995
:: Copyright (c) 1995-2021 Association of Mizar Users

definition
let p, q be FinSequence;
func p $^ q -> FinSequence means :Def1: :: REWRITE1:def 1 it = p ^ q if ( p = {} or q = {} ) otherwise ex i being Nat ex r being FinSequence st ( len p = i + 1 & r = p | (Seg i) & it = r ^ q ); existence ( ( ( p = {} or q = {} ) implies ex b1 being FinSequence st b1 = p ^ q ) & ( p = {} or q = {} or ex b1 being FinSequence ex i being Nat ex r being FinSequence st ( len p = i + 1 & r = p | (Seg i) & b1 = r ^ q ) ) ) proof end; uniqueness for b1, b2 being FinSequence holds ( ( ( p = {} or q = {} ) & b1 = p ^ q & b2 = p ^ q implies b1 = b2 ) & ( p = {} or q = {} or for i being Nat for r being FinSequence holds ( not len p = i + 1 or not r = p | (Seg i) or not b1 = r ^ q ) or for i being Nat for r being FinSequence holds ( not len p = i + 1 or not r = p | (Seg i) or not b2 = r ^ q ) or b1 = b2 ) ) ; consistency for b1 being FinSequence holds verum ; end; :: deftheorem Def1 defines$^ REWRITE1:def 1 :
for p, q, b3 being FinSequence holds
( ( ( p = {} or q = {} ) implies ( b3 = p $^ q iff b3 = p ^ q ) ) & ( p = {} or q = {} or ( b3 = p$^ q iff ex i being Nat ex r being FinSequence st
( len p = i + 1 & r = p | (Seg i) & b3 = r ^ q ) ) ) );

Lm1: now :: thesis: for p being FinSequence
for x being Nat st x in dom p holds
( x <= len p & x >= 0 + 1 & x > 0 )
let p be FinSequence; :: thesis: for x being Nat st x in dom p holds
( x <= len p & x >= 0 + 1 & x > 0 )

let x be Nat; :: thesis: ( x in dom p implies ( x <= len p & x >= 0 + 1 & x > 0 ) )
assume x in dom p ; :: thesis: ( x <= len p & x >= 0 + 1 & x > 0 )
then A1: x in Seg (len p) by FINSEQ_1:def 3;
hence ( x <= len p & x >= 0 + 1 ) by FINSEQ_1:1; :: thesis: x > 0
thus x > 0 by ; :: thesis: verum
end;

Lm2: now :: thesis: for p being FinSequence
for x being Nat st x + 1 in dom p holds
x < len p
let p be FinSequence; :: thesis: for x being Nat st x + 1 in dom p holds
x < len p

let x be Nat; :: thesis: ( x + 1 in dom p implies x < len p )
assume x + 1 in dom p ; :: thesis: x < len p
then x + 1 <= len p by Lm1;
hence x < len p by NAT_1:13; :: thesis: verum
end;

Lm3: now :: thesis: for p being FinSequence
for x being Nat st ( x <= len p or x < len p ) & ( x >= 1 or x > 0 ) holds
x in dom p
let p be FinSequence; :: thesis: for x being Nat st ( x <= len p or x < len p ) & ( x >= 1 or x > 0 ) holds
x in dom p

let x be Nat; :: thesis: ( ( x <= len p or x < len p ) & ( x >= 1 or x > 0 ) implies x in dom p )
assume that
A1: ( x <= len p or x < len p ) and
A2: ( x >= 1 or x > 0 ) ; :: thesis: x in dom p
x >= 0 + 1 by ;
then x in Seg (len p) by ;
hence x in dom p by FINSEQ_1:def 3; :: thesis: verum
end;

Lm4: now :: thesis: for p being FinSequence
for x being Nat st x < len p holds
x + 1 in dom p
let p be FinSequence; :: thesis: for x being Nat st x < len p holds
x + 1 in dom p

let x be Nat; :: thesis: ( x < len p implies x + 1 in dom p )
assume x < len p ; :: thesis: x + 1 in dom p
then x + 1 <= len p by NAT_1:13;
hence x + 1 in dom p by Lm3; :: thesis: verum
end;

theorem :: REWRITE1:1
for p being FinSequence holds
( {} $^ p = p & p$^ {} = p )
proof end;

theorem Th2: :: REWRITE1:2
for p, q being FinSequence
for x being object st q <> {} holds
(p ^ <*x*>) $^ q = p ^ q proof end; theorem :: REWRITE1:3 for p, q being FinSequence for x, y being object holds (p ^ <*x*>)$^ (<*y*> ^ q) = (p ^ <*y*>) ^ q
proof end;

theorem :: REWRITE1:4
for q being FinSequence
for x being object st q <> {} holds
<*x*> $^ q = q proof end; theorem :: REWRITE1:5 for p being FinSequence st p <> {} holds ex x being object ex q being FinSequence st ( p = <*x*> ^ q & len p = (len q) + 1 ) proof end; scheme :: REWRITE1:sch 1 PathCatenation{ P1[ set , set ], F1() -> FinSequence, F2() -> FinSequence } : for i being Nat st i in dom (F1()$^ F2()) & i + 1 in dom (F1() $^ F2()) holds for x, y being set st x = (F1()$^ F2()) . i & y = (F1() $^ F2()) . (i + 1) holds P1[x,y] provided A1: for i being Nat st i in dom F1() & i + 1 in dom F1() holds P1[F1() . i,F1() . (i + 1)] and A2: for i being Nat st i in dom F2() & i + 1 in dom F2() holds P1[F2() . i,F2() . (i + 1)] and A3: ( len F1() > 0 & len F2() > 0 & F1() . (len F1()) = F2() . 1 ) proof end; definition let R be Relation; mode RedSequence of R -> FinSequence means :Def2: :: REWRITE1:def 2 ( len it > 0 & ( for i being Nat st i in dom it & i + 1 in dom it holds [(it . i),(it . (i + 1))] in R ) ); existence ex b1 being FinSequence st ( len b1 > 0 & ( for i being Nat st i in dom b1 & i + 1 in dom b1 holds [(b1 . i),(b1 . (i + 1))] in R ) ) proof end; end; :: deftheorem Def2 defines RedSequence REWRITE1:def 2 : for R being Relation for b2 being FinSequence holds ( b2 is RedSequence of R iff ( len b2 > 0 & ( for i being Nat st i in dom b2 & i + 1 in dom b2 holds [(b2 . i),(b2 . (i + 1))] in R ) ) ); registration let R be Relation; cluster -> non empty for RedSequence of R; coherence for b1 being RedSequence of R holds not b1 is empty by ; end; theorem Th6: :: REWRITE1:6 for R being Relation for a being object holds <*a*> is RedSequence of R proof end; theorem Th7: :: REWRITE1:7 for R being Relation for a, b being object st [a,b] in R holds <*a,b*> is RedSequence of R proof end; theorem Th8: :: REWRITE1:8 for R being Relation for p, q being RedSequence of R st p . (len p) = q . 1 holds p$^ q is RedSequence of R
proof end;

theorem Th9: :: REWRITE1:9
for R being Relation
for p being RedSequence of R holds Rev p is RedSequence of R ~
proof end;

theorem Th10: :: REWRITE1:10
for R, Q being Relation st R c= Q holds
for p being RedSequence of R holds p is RedSequence of Q
proof end;

definition
let R be Relation;
let a, b be object ;
pred R reduces a,b means :: REWRITE1:def 3
ex p being RedSequence of R st
( p . 1 = a & p . (len p) = b );
end;

:: deftheorem defines reduces REWRITE1:def 3 :
for R being Relation
for a, b being object holds
( R reduces a,b iff ex p being RedSequence of R st
( p . 1 = a & p . (len p) = b ) );

definition
let R be Relation;
let a, b be object ;
pred a,b are_convertible_wrt R means :: REWRITE1:def 4
R \/ (R ~) reduces a,b;
end;

:: deftheorem defines are_convertible_wrt REWRITE1:def 4 :
for R being Relation
for a, b being object holds
( a,b are_convertible_wrt R iff R \/ (R ~) reduces a,b );

theorem Th11: :: REWRITE1:11
for R being Relation
for a, b being object holds
( R reduces a,b iff ex p being FinSequence st
( len p > 0 & p . 1 = a & p . (len p) = b & ( for i being Nat st i in dom p & i + 1 in dom p holds
[(p . i),(p . (i + 1))] in R ) ) )
proof end;

theorem Th12: :: REWRITE1:12
for R being Relation
for a being object holds R reduces a,a
proof end;

theorem Th13: :: REWRITE1:13
for a, b being object st {} reduces a,b holds
a = b
proof end;

theorem Th14: :: REWRITE1:14
for R being Relation
for a, b being object st R reduces a,b & not a in field R holds
a = b
proof end;

theorem Th15: :: REWRITE1:15
for R being Relation
for a, b being object st [a,b] in R holds
R reduces a,b
proof end;

theorem Th16: :: REWRITE1:16
for R being Relation
for a, b, c being object st R reduces a,b & R reduces b,c holds
R reduces a,c
proof end;

theorem Th17: :: REWRITE1:17
for R being Relation
for p being RedSequence of R
for i, j being Nat st i in dom p & j in dom p & i <= j holds
R reduces p . i,p . j
proof end;

theorem Th18: :: REWRITE1:18
for R being Relation
for a, b being object st R reduces a,b & a <> b holds
( a in field R & b in field R )
proof end;

theorem :: REWRITE1:19
for R being Relation
for a, b being object st R reduces a,b holds
( a in field R iff b in field R ) by Th18;

theorem Th20: :: REWRITE1:20
for R being Relation
for a, b being object holds
( R reduces a,b iff ( a = b or [a,b] in R [*] ) )
proof end;

theorem Th21: :: REWRITE1:21
for R being Relation
for a, b being object holds
( R reduces a,b iff R [*] reduces a,b )
proof end;

theorem Th22: :: REWRITE1:22
for R, Q being Relation st R c= Q holds
for a, b being object st R reduces a,b holds
Q reduces a,b
proof end;

theorem :: REWRITE1:23
for R being Relation
for X being set
for a, b being object holds
( R reduces a,b iff R \/ (id X) reduces a,b )
proof end;

theorem Th24: :: REWRITE1:24
for R being Relation
for a, b being object st R reduces a,b holds
R ~ reduces b,a
proof end;

Lm5: for R being Relation
for a, b being object st a,b are_convertible_wrt R holds
b,a are_convertible_wrt R

proof end;

theorem Th25: :: REWRITE1:25
for R being Relation
for a, b being object st R reduces a,b holds
( a,b are_convertible_wrt R & b,a are_convertible_wrt R )
proof end;

theorem Th26: :: REWRITE1:26
for R being Relation
for a being object holds a,a are_convertible_wrt R by Th12;

theorem Th27: :: REWRITE1:27
for a, b being object st a,b are_convertible_wrt {} holds
a = b by Th13;

theorem :: REWRITE1:28
for R being Relation
for a, b being object st a,b are_convertible_wrt R & not a in field R holds
a = b
proof end;

theorem Th29: :: REWRITE1:29
for R being Relation
for a, b being object st [a,b] in R holds
a,b are_convertible_wrt R
proof end;

theorem Th30: :: REWRITE1:30
for R being Relation
for a, b, c being object st a,b are_convertible_wrt R & b,c are_convertible_wrt R holds
a,c are_convertible_wrt R by Th16;

theorem :: REWRITE1:31
for R being Relation
for a, b being object st a,b are_convertible_wrt R holds
b,a are_convertible_wrt R by Lm5;

theorem Th32: :: REWRITE1:32
for R being Relation
for a, b being object st a,b are_convertible_wrt R & a <> b holds
( a in field R & b in field R )
proof end;

definition
let R be Relation;
let a be object ;
pred a is_a_normal_form_wrt R means :: REWRITE1:def 5
for b being object holds not [a,b] in R;
end;

:: deftheorem defines is_a_normal_form_wrt REWRITE1:def 5 :
for R being Relation
for a being object holds
( a is_a_normal_form_wrt R iff for b being object holds not [a,b] in R );

theorem Th33: :: REWRITE1:33
for R being Relation
for a, b being object st a is_a_normal_form_wrt R & R reduces a,b holds
a = b
proof end;

theorem Th34: :: REWRITE1:34
for R being Relation
for a being object st not a in field R holds
a is_a_normal_form_wrt R by RELAT_1:15;

definition
let R be Relation;
let a, b be object ;
pred b is_a_normal_form_of a,R means :: REWRITE1:def 6
( b is_a_normal_form_wrt R & R reduces a,b );
pred a,b are_convergent_wrt R means :Def7: :: REWRITE1:def 7
ex c being object st
( R reduces a,c & R reduces b,c );
pred a,b are_divergent_wrt R means :: REWRITE1:def 8
ex c being object st
( R reduces c,a & R reduces c,b );
pred a,b are_convergent<=1_wrt R means :: REWRITE1:def 9
ex c being object st
( ( [a,c] in R or a = c ) & ( [b,c] in R or b = c ) );
pred a,b are_divergent<=1_wrt R means :: REWRITE1:def 10
ex c being object st
( ( [c,a] in R or a = c ) & ( [c,b] in R or b = c ) );
end;

:: deftheorem defines is_a_normal_form_of REWRITE1:def 6 :
for R being Relation
for a, b being object holds
( b is_a_normal_form_of a,R iff ( b is_a_normal_form_wrt R & R reduces a,b ) );

:: deftheorem Def7 defines are_convergent_wrt REWRITE1:def 7 :
for R being Relation
for a, b being object holds
( a,b are_convergent_wrt R iff ex c being object st
( R reduces a,c & R reduces b,c ) );

:: deftheorem defines are_divergent_wrt REWRITE1:def 8 :
for R being Relation
for a, b being object holds
( a,b are_divergent_wrt R iff ex c being object st
( R reduces c,a & R reduces c,b ) );

:: deftheorem defines are_convergent<=1_wrt REWRITE1:def 9 :
for R being Relation
for a, b being object holds
( a,b are_convergent<=1_wrt R iff ex c being object st
( ( [a,c] in R or a = c ) & ( [b,c] in R or b = c ) ) );

:: deftheorem defines are_divergent<=1_wrt REWRITE1:def 10 :
for R being Relation
for a, b being object holds
( a,b are_divergent<=1_wrt R iff ex c being object st
( ( [c,a] in R or a = c ) & ( [c,b] in R or b = c ) ) );

theorem Th35: :: REWRITE1:35
for R being Relation
for a being object st not a in field R holds
a is_a_normal_form_of a,R by ;

theorem Th36: :: REWRITE1:36
for R being Relation
for a, b being object st R reduces a,b holds
( a,b are_convergent_wrt R & a,b are_divergent_wrt R & b,a are_convergent_wrt R & b,a are_divergent_wrt R )
proof end;

theorem Th37: :: REWRITE1:37
for R being Relation
for a, b being object st ( a,b are_convergent_wrt R or a,b are_divergent_wrt R ) holds
a,b are_convertible_wrt R
proof end;

theorem Th38: :: REWRITE1:38
for R being Relation
for a being object holds
( a,a are_convergent_wrt R & a,a are_divergent_wrt R ) by Th12;

theorem Th39: :: REWRITE1:39
for a, b being object st ( a,b are_convergent_wrt {} or a,b are_divergent_wrt {} ) holds
a = b
proof end;

theorem :: REWRITE1:40
for R being Relation
for a, b being object st a,b are_convergent_wrt R holds
b,a are_convergent_wrt R ;

theorem :: REWRITE1:41
for R being Relation
for a, b being object st a,b are_divergent_wrt R holds
b,a are_divergent_wrt R ;

theorem Th42: :: REWRITE1:42
for R being Relation
for a, b, c being object st ( ( R reduces a,b & b,c are_convergent_wrt R ) or ( a,b are_convergent_wrt R & R reduces c,b ) ) holds
a,c are_convergent_wrt R
proof end;

theorem :: REWRITE1:43
for R being Relation
for a, b, c being object st ( ( R reduces b,a & b,c are_divergent_wrt R ) or ( a,b are_divergent_wrt R & R reduces b,c ) ) holds
a,c are_divergent_wrt R
proof end;

theorem Th44: :: REWRITE1:44
for R being Relation
for a, b being object st a,b are_convergent<=1_wrt R holds
a,b are_convergent_wrt R
proof end;

theorem Th45: :: REWRITE1:45
for R being Relation
for a, b being object st a,b are_divergent<=1_wrt R holds
a,b are_divergent_wrt R
proof end;

definition
let R be Relation;
let a be object ;
pred a has_a_normal_form_wrt R means :: REWRITE1:def 11
ex b being object st b is_a_normal_form_of a,R;
end;

:: deftheorem defines has_a_normal_form_wrt REWRITE1:def 11 :
for R being Relation
for a being object holds
( a has_a_normal_form_wrt R iff ex b being object st b is_a_normal_form_of a,R );

theorem Th46: :: REWRITE1:46
for R being Relation
for a being object st not a in field R holds
a has_a_normal_form_wrt R by Th35;

definition
let R be Relation;
let a be object ;
assume that
A1: a has_a_normal_form_wrt R and
A2: for b, c being object st b is_a_normal_form_of a,R & c is_a_normal_form_of a,R holds
b = c ;
func nf (a,R) -> set means :Def12: :: REWRITE1:def 12
it is_a_normal_form_of a,R;
existence
ex b1 being set st b1 is_a_normal_form_of a,R
proof end;
uniqueness
for b1, b2 being set st b1 is_a_normal_form_of a,R & b2 is_a_normal_form_of a,R holds
b1 = b2
by A2;
end;

:: deftheorem Def12 defines nf REWRITE1:def 12 :
for R being Relation
for a being object st a has_a_normal_form_wrt R & ( for b, c being object st b is_a_normal_form_of a,R & c is_a_normal_form_of a,R holds
b = c ) holds
for b3 being set holds
( b3 = nf (a,R) iff b3 is_a_normal_form_of a,R );

definition
let R be Relation;
attr R is weakly-normalizing means :Def14: :: REWRITE1:def 14
for a being object st a in field R holds
a has_a_normal_form_wrt R;
attr R is strongly-normalizing means :: REWRITE1:def 15
for f being ManySortedSet of NAT holds
not for i being Nat holds [(f . i),(f . (i + 1))] in R;
end;

:: deftheorem defines co-well_founded REWRITE1:def 13 :
for R being Relation holds
( R is co-well_founded iff R ~ is well_founded );

:: deftheorem Def14 defines weakly-normalizing REWRITE1:def 14 :
for R being Relation holds
( R is weakly-normalizing iff for a being object st a in field R holds
a has_a_normal_form_wrt R );

:: deftheorem defines strongly-normalizing REWRITE1:def 15 :
for R being Relation holds
( R is strongly-normalizing iff for f being ManySortedSet of NAT holds
not for i being Nat holds [(f . i),(f . (i + 1))] in R );

definition
let R be Relation;
redefine attr R is co-well_founded means :Def16: :: REWRITE1:def 16
for Y being set st Y c= field R & Y <> {} holds
ex a being object st
( a in Y & ( for b being object st b in Y & a <> b holds
not [a,b] in R ) );
compatibility
( R is co-well_founded iff for Y being set st Y c= field R & Y <> {} holds
ex a being object st
( a in Y & ( for b being object st b in Y & a <> b holds
not [a,b] in R ) ) )
proof end;
end;

:: deftheorem Def16 defines co-well_founded REWRITE1:def 16 :
for R being Relation holds
( R is co-well_founded iff for Y being set st Y c= field R & Y <> {} holds
ex a being object st
( a in Y & ( for b being object st b in Y & a <> b holds
not [a,b] in R ) ) );

scheme :: REWRITE1:sch 2
coNoetherianInduction{ F1() -> Relation, P1[ object ] } :
for a being object st a in field F1() holds
P1[a]
provided
A1: F1() is co-well_founded and
A2: for a being object st ( for b being object st [a,b] in F1() & a <> b holds
P1[b] ) holds
P1[a]
proof end;

registration
coherence
for b1 being Relation st b1 is strongly-normalizing holds
( b1 is irreflexive & b1 is co-well_founded )
proof end;
coherence
for b1 being Relation st b1 is co-well_founded & b1 is irreflexive holds
b1 is strongly-normalizing
proof end;
end;

registration
coherence
for b1 being Relation st b1 is empty holds
( b1 is weakly-normalizing & b1 is strongly-normalizing )
by RELAT_1:40;
end;

theorem :: REWRITE1:47
for Q being co-well_founded Relation
for R being Relation st R c= Q holds
R is co-well_founded
proof end;

registration
coherence
for b1 being Relation st b1 is strongly-normalizing holds
b1 is weakly-normalizing
proof end;
end;

definition
let R, Q be Relation;
pred R commutes-weakly_with Q means :: REWRITE1:def 17
for a, b, c being object st [a,b] in R & [a,c] in Q holds
ex d being object st
( Q reduces b,d & R reduces c,d );
symmetry
for R, Q being Relation st ( for a, b, c being object st [a,b] in R & [a,c] in Q holds
ex d being object st
( Q reduces b,d & R reduces c,d ) ) holds
for a, b, c being object st [a,b] in Q & [a,c] in R holds
ex d being object st
( R reduces b,d & Q reduces c,d )
proof end;
pred R commutes_with Q means :Def18: :: REWRITE1:def 18
for a, b, c being object st R reduces a,b & Q reduces a,c holds
ex d being object st
( Q reduces b,d & R reduces c,d );
symmetry
for R, Q being Relation st ( for a, b, c being object st R reduces a,b & Q reduces a,c holds
ex d being object st
( Q reduces b,d & R reduces c,d ) ) holds
for a, b, c being object st Q reduces a,b & R reduces a,c holds
ex d being object st
( R reduces b,d & Q reduces c,d )
proof end;
end;

:: deftheorem defines commutes-weakly_with REWRITE1:def 17 :
for R, Q being Relation holds
( R commutes-weakly_with Q iff for a, b, c being object st [a,b] in R & [a,c] in Q holds
ex d being object st
( Q reduces b,d & R reduces c,d ) );

:: deftheorem Def18 defines commutes_with REWRITE1:def 18 :
for R, Q being Relation holds
( R commutes_with Q iff for a, b, c being object st R reduces a,b & Q reduces a,c holds
ex d being object st
( Q reduces b,d & R reduces c,d ) );

theorem :: REWRITE1:48
for R, Q being Relation st R commutes_with Q holds
R commutes-weakly_with Q
proof end;

definition
let R be Relation;
attr R is with_UN_property means :Def19: :: REWRITE1:def 19
for a, b being object st a is_a_normal_form_wrt R & b is_a_normal_form_wrt R & a,b are_convertible_wrt R holds
a = b;
attr R is with_NF_property means :: REWRITE1:def 20
for a, b being object st a is_a_normal_form_wrt R & a,b are_convertible_wrt R holds
R reduces b,a;
attr R is subcommutative means :: REWRITE1:def 21
for a, b, c being object st [a,b] in R & [a,c] in R holds
b,c are_convergent<=1_wrt R;
attr R is confluent means :Def22: :: REWRITE1:def 22
for a, b being object st a,b are_divergent_wrt R holds
a,b are_convergent_wrt R;
attr R is with_Church-Rosser_property means :Def23: :: REWRITE1:def 23
for a, b being object st a,b are_convertible_wrt R holds
a,b are_convergent_wrt R;
attr R is locally-confluent means :: REWRITE1:def 24
for a, b, c being object st [a,b] in R & [a,c] in R holds
b,c are_convergent_wrt R;
end;

:: deftheorem Def19 defines with_UN_property REWRITE1:def 19 :
for R being Relation holds
( R is with_UN_property iff for a, b being object st a is_a_normal_form_wrt R & b is_a_normal_form_wrt R & a,b are_convertible_wrt R holds
a = b );

:: deftheorem defines with_NF_property REWRITE1:def 20 :
for R being Relation holds
( R is with_NF_property iff for a, b being object st a is_a_normal_form_wrt R & a,b are_convertible_wrt R holds
R reduces b,a );

:: deftheorem defines subcommutative REWRITE1:def 21 :
for R being Relation holds
( R is subcommutative iff for a, b, c being object st [a,b] in R & [a,c] in R holds
b,c are_convergent<=1_wrt R );

:: deftheorem Def22 defines confluent REWRITE1:def 22 :
for R being Relation holds
( R is confluent iff for a, b being object st a,b are_divergent_wrt R holds
a,b are_convergent_wrt R );

:: deftheorem Def23 defines with_Church-Rosser_property REWRITE1:def 23 :
for R being Relation holds
( R is with_Church-Rosser_property iff for a, b being object st a,b are_convertible_wrt R holds
a,b are_convergent_wrt R );

:: deftheorem defines locally-confluent REWRITE1:def 24 :
for R being Relation holds
( R is locally-confluent iff for a, b, c being object st [a,b] in R & [a,c] in R holds
b,c are_convergent_wrt R );

theorem Th49: :: REWRITE1:49
for R being Relation st R is subcommutative holds
for a, b, c being object st R reduces a,b & [a,c] in R holds
b,c are_convergent_wrt R
proof end;

theorem :: REWRITE1:50
for R being Relation holds
( R is confluent iff R commutes_with R )
proof end;

theorem Th51: :: REWRITE1:51
for R being Relation holds
( R is confluent iff for a, b, c being object st R reduces a,b & [a,c] in R holds
b,c are_convergent_wrt R )
proof end;

theorem :: REWRITE1:52
for R being Relation holds
( R is locally-confluent iff R commutes-weakly_with R )
proof end;

registration
coherence
for b1 being Relation st b1 is with_Church-Rosser_property holds
b1 is confluent
proof end;
coherence
for b1 being Relation st b1 is confluent holds
( b1 is locally-confluent & b1 is with_Church-Rosser_property )
proof end;
coherence
for b1 being Relation st b1 is subcommutative holds
b1 is confluent
proof end;
coherence
for b1 being Relation st b1 is with_Church-Rosser_property holds
b1 is with_NF_property
proof end;
coherence
for b1 being Relation st b1 is with_NF_property holds
b1 is with_UN_property
by Th33;
coherence
for b1 being Relation st b1 is with_UN_property & b1 is weakly-normalizing holds
b1 is with_Church-Rosser_property
proof end;
end;

registration
coherence
for b1 being Relation st b1 is empty holds
b1 is subcommutative
;
end;

theorem Th53: :: REWRITE1:53
for R being with_UN_property Relation
for a, b, c being object st b is_a_normal_form_of a,R & c is_a_normal_form_of a,R holds
b = c
proof end;

theorem Th54: :: REWRITE1:54
for R being weakly-normalizing with_UN_property Relation
for a being object holds nf (a,R) is_a_normal_form_of a,R
proof end;

theorem Th55: :: REWRITE1:55
for R being weakly-normalizing with_UN_property Relation
for a, b being object st a,b are_convertible_wrt R holds
nf (a,R) = nf (b,R)
proof end;

registration
coherence
for b1 being Relation st b1 is strongly-normalizing & b1 is locally-confluent holds
b1 is confluent
proof end;
end;

definition
let R be Relation;
attr R is complete means :: REWRITE1:def 25
( R is confluent & R is strongly-normalizing );
end;

:: deftheorem defines complete REWRITE1:def 25 :
for R being Relation holds
( R is complete iff ( R is confluent & R is strongly-normalizing ) );

registration
coherence
for b1 being Relation st b1 is complete holds
( b1 is confluent & b1 is strongly-normalizing )
;
coherence
for b1 being Relation st b1 is confluent & b1 is strongly-normalizing holds
b1 is complete
;
end;

registration
existence
ex b1 being non empty Relation st b1 is complete
proof end;
end;

theorem :: REWRITE1:56
for R, Q being with_Church-Rosser_property Relation st R commutes_with Q holds
R \/ Q is with_Church-Rosser_property
proof end;

theorem :: REWRITE1:57
for R being Relation holds
( R is confluent iff R [*] is locally-confluent )
proof end;

theorem :: REWRITE1:58
for R being Relation holds
( R is confluent iff R [*] is subcommutative )
proof end;

definition
let R, Q be Relation;
pred R,Q are_equivalent means :: REWRITE1:def 26
for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convertible_wrt Q );
symmetry
for R, Q being Relation st ( for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convertible_wrt Q ) ) holds
for a, b being object holds
( a,b are_convertible_wrt Q iff a,b are_convertible_wrt R )
;
end;

:: deftheorem defines are_equivalent REWRITE1:def 26 :
for R, Q being Relation holds
( R,Q are_equivalent iff for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convertible_wrt Q ) );

definition
let R be Relation;
let a, b be object ;
pred a,b are_critical_wrt R means :: REWRITE1:def 27
( a,b are_divergent<=1_wrt R & not a,b are_convergent_wrt R );
end;

:: deftheorem defines are_critical_wrt REWRITE1:def 27 :
for R being Relation
for a, b being object holds
( a,b are_critical_wrt R iff ( a,b are_divergent<=1_wrt R & not a,b are_convergent_wrt R ) );

theorem Th59: :: REWRITE1:59
for R being Relation
for a, b being object st a,b are_critical_wrt R holds
a,b are_convertible_wrt R by ;

theorem :: REWRITE1:60
for R being Relation st ( for a, b being object holds not a,b are_critical_wrt R ) holds
R is locally-confluent
proof end;

theorem :: REWRITE1:61
for R, Q being Relation st ( for a, b being object st [a,b] in Q holds
a,b are_critical_wrt R ) holds
R,R \/ Q are_equivalent
proof end;

theorem Th62: :: REWRITE1:62
for R being Relation ex Q being complete Relation st
( field Q c= field R & ( for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convergent_wrt Q ) ) )
proof end;

definition
let R be Relation;
mode Completion of R -> complete Relation means :Def28: :: REWRITE1:def 28
for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convergent_wrt it );
existence
ex b1 being complete Relation st
for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convergent_wrt b1 )
proof end;
end;

:: deftheorem Def28 defines Completion REWRITE1:def 28 :
for R being Relation
for b2 being complete Relation holds
( b2 is Completion of R iff for a, b being object holds
( a,b are_convertible_wrt R iff a,b are_convergent_wrt b2 ) );

theorem :: REWRITE1:63
for R being Relation
for C being Completion of R holds R,C are_equivalent
proof end;

theorem :: REWRITE1:64
for R being Relation
for Q being complete Relation st R,Q are_equivalent holds
Q is Completion of R
proof end;

theorem :: REWRITE1:65
for R being Relation
for C being Completion of R
for a, b being object holds
( a,b are_convertible_wrt R iff nf (a,C) = nf (b,C) )
proof end;