let Z1, Z2 be Tree; :: thesis: for p being FinSequence of NAT st p in Z1 holds
for v being Element of Z1 with-replacement (p,Z2)
for w being Element of Z2 st v = p ^ w holds
succ v, succ w are_equipotent
let p be FinSequence of NAT ; :: thesis: ( p in Z1 implies for v being Element of Z1 with-replacement (p,Z2)
for w being Element of Z2 st v = p ^ w holds
succ v, succ w are_equipotent )
assume A1: p in Z1 ; :: thesis: for v being Element of Z1 with-replacement (p,Z2)
for w being Element of Z2 st v = p ^ w holds
succ v, succ w are_equipotent
set T = Z1 with-replacement (p,Z2);
let t be Element of Z1 with-replacement (p,Z2); :: thesis: for w being Element of Z2 st t = p ^ w holds
succ t, succ w are_equipotent
let t2 be Element of Z2; :: thesis: ( t = p ^ t2 implies succ t, succ t2 are_equipotent )
assume A2: t = p ^ t2 ; :: thesis: succ t, succ t2 are_equipotent
then A3: p is_a_prefix_of t by TREES_1:1;
A4: for n being Nat holds
( t ^ <*n*> in Z1 with-replacement (p,Z2) iff t2 ^ <*n*> in Z2 )
proof
let n be Nat; :: thesis: ( t ^ <*n*> in Z1 with-replacement (p,Z2) iff t2 ^ <*n*> in Z2 )
A5: p is_a_proper_prefix_of t ^ <*n*> by A3, TREES_1:8;
reconsider nn = n as Element of NAT by ORDINAL1:def 12;
A6: t ^ <*nn*> = p ^ (t2 ^ <*nn*>) by A2, FINSEQ_1:32;
thus ( t ^ <*n*> in Z1 with-replacement (p,Z2) implies t2 ^ <*n*> in Z2 ) :: thesis: ( t2 ^ <*n*> in Z2 implies t ^ <*n*> in Z1 with-replacement (p,Z2) )
proof
assume A7: t ^ <*n*> in Z1 with-replacement (p,Z2) ; :: thesis: t2 ^ <*n*> in Z2
reconsider n = n as Element of NAT by ORDINAL1:def 12;
ex w being FinSequence of NAT st
( w in Z2 & t ^ <*n*> = p ^ w ) by A1, A5, TREES_1:def 9, A7;
hence t2 ^ <*n*> in Z2 by A6, FINSEQ_1:33; :: thesis: verum
end;
assume t2 ^ <*n*> in Z2 ; :: thesis: t ^ <*n*> in Z1 with-replacement (p,Z2)
hence t ^ <*n*> in Z1 with-replacement (p,Z2) by A1, A6, TREES_1:def 9; :: thesis: verum
end;
defpred S1[ object , object ] means for n being Nat st $1 = t ^ <*n*> holds
$2 = t2 ^ <*n*>;
A8: for x being object st x in succ t holds
ex y being object st S1[x,y]
proof
let x be object ; :: thesis: ( x in succ t implies ex y being object st S1[x,y] )
assume x in succ t ; :: thesis: ex y being object st S1[x,y]
then consider n being Nat such that
A9: x = t ^ <*n*> and
t ^ <*n*> in Z1 with-replacement (p,Z2) ;
take t2 ^ <*n*> ; :: thesis: S1[x,t2 ^ <*n*>]
let m be Nat; :: thesis: ( x = t ^ <*m*> implies t2 ^ <*n*> = t2 ^ <*m*> )
assume x = t ^ <*m*> ; :: thesis: t2 ^ <*n*> = t2 ^ <*m*>
hence t2 ^ <*n*> = t2 ^ <*m*> by A9, FINSEQ_1:33; :: thesis: verum
end;
consider f being Function such that
A10: ( dom f = succ t & ( for x being object st x in succ t holds
S1[x,f . x] ) ) from CLASSES1:sch 1(A8);
now :: thesis: for x being object holds
( ( x in rng f implies x in succ t2 ) & ( x in succ t2 implies x in rng f ) )
let x be object ; :: thesis: ( ( x in rng f implies x in succ t2 ) & ( x in succ t2 implies x in rng f ) )
thus ( x in rng f implies x in succ t2 ) :: thesis: ( x in succ t2 implies x in rng f )
proof
assume x in rng f ; :: thesis: x in succ t2
then consider y being object such that
A11: y in dom f and
A12: x = f . y by FUNCT_1:def 3;
consider n being Nat such that
A13: y = t ^ <*n*> and
A14: t ^ <*n*> in Z1 with-replacement (p,Z2) by A10, A11;
A15: x = t2 ^ <*n*> by A10, A11, A12, A13;
t2 ^ <*n*> in Z2 by A4, A14;
hence x in succ t2 by A15; :: thesis: verum
end;
assume x in succ t2 ; :: thesis: x in rng f
then consider n being Nat such that
A16: x = t2 ^ <*n*> and
A17: t2 ^ <*n*> in Z2 ;
t ^ <*n*> in Z1 with-replacement (p,Z2) by A4, A17;
then A18: t ^ <*n*> in dom f by A10;
then f . (t ^ <*n*>) = x by A10, A16;
hence x in rng f by A18, FUNCT_1:def 3; :: thesis: verum
end;
then A19: rng f = succ t2 by TARSKI:2;
f is one-to-one
proof
let x1, x2 be object ; :: according to FUNCT_1:def 4 :: thesis: ( not x1 in dom f or not x2 in dom f or not f . x1 = f . x2 or x1 = x2 )
assume that
A20: x1 in dom f and
A21: x2 in dom f and
A22: f . x1 = f . x2 ; :: thesis: x1 = x2
consider m being Nat such that
A23: x1 = t ^ <*m*> and
t ^ <*m*> in Z1 with-replacement (p,Z2) by A10, A20;
consider k being Nat such that
A24: x2 = t ^ <*k*> and
t ^ <*k*> in Z1 with-replacement (p,Z2) by A10, A21;
t2 ^ <*m*> = f . x1 by A10, A20, A23
.= t2 ^ <*k*> by A10, A21, A22, A24 ;
hence x1 = x2 by A23, A24, FINSEQ_1:33; :: thesis: verum
end;
hence succ t, succ t2 are_equipotent by A10, A19, WELLORD2:def 4; :: thesis: verum