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:8;
A4: for n being Element of NAT holds
( t ^ <*n*> in Z1 with-replacement p,Z2 iff t2 ^ <*n*> in Z2 )

proof

let n be Element of 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:31;
A6: t ^ <*n*> = p ^ (t2 ^ <*n*>) by A2, FINSEQ_1:45;
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 t ^ <*n*> in Z1 with-replacement p,Z2 ; :: thesis: t2 ^ <*n*> in Z2
then ex w being FinSequence of NAT st
( w in Z2 & t ^ <*n*> = p ^ w ) by A1, A5, TREES_1:def 12;
hence t2 ^ <*n*> in Z2 by A6, FINSEQ_1:46; :: 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 12; :: thesis: verum

end;

defpred S₁[ set , set ] means for n being Element of NAT st $1 = t ^ <*n*> holds
$2 = t2 ^ <*n*>;
A10: for x being set st x in succ t holds
ex y being set st S₁[x,y]

proof

let x be set ; :: thesis: ( x in succ t implies ex y being set st S₁[x,y] )
assume x in succ t ; :: thesis: ex y being set st S₁[x,y]
then consider n being Element of NAT such that
A11: ( x = t ^ <*n*> & t ^ <*n*> in Z1 with-replacement p,Z2 ) ;
take t2 ^ <*n*> ; :: thesis: S₁[x,t2 ^ <*n*>]
let m be Element of 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 A11, FINSEQ_1:46; :: thesis: verum

end;

consider f being Function such that
A12: ( dom f = succ t & ( for x being set st x in succ t holds
S₁[x,f . x] ) ) from CLASSES1:sch 1(A10);
A13: rng f = succ t2

proof

now

let x be set ; :: 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 set such that
A14: ( y in dom f & x = f . y ) by FUNCT_1:def 5;
consider n being Element of NAT such that
A15: ( y = t ^ <*n*> & t ^ <*n*> in Z1 with-replacement p,Z2 ) by A12, A14;
A16: x = t2 ^ <*n*> by A12, A14, A15;
t2 ^ <*n*> in Z2 by A4, A15;
hence x in succ t2 by A16; :: thesis: verum

end;

assume x in succ t2 ; :: thesis: x in rng f
then consider n being Element of NAT such that
A17: ( x = t2 ^ <*n*> & t2 ^ <*n*> in Z2 ) ;
t ^ <*n*> in Z1 with-replacement p,Z2 by A4, A17;
then A18: t ^ <*n*> in dom f by A12;
then f . (t ^ <*n*>) = x by A12, A17;
hence x in rng f by A18, FUNCT_1:def 5; :: thesis: verum

end;

hence rng f = succ t2 by TARSKI:2; :: thesis: verum

end;

f is one-to-one

proof

let x1 be set ; :: according to FUNCT_1:def 8 :: thesis: for b₁ being set holds
( not x1 in dom f or not b₁ in dom f or not f . x1 = f . b₁ or x1 = b₁ )
let x2 be set ; :: thesis: ( not x1 in dom f or not x2 in dom f or not f . x1 = f . x2 or x1 = x2 )
assume A19: ( x1 in dom f & x2 in dom f & f . x1 = f . x2 ) ; :: thesis: x1 = x2
then consider m being Element of NAT such that
A20: ( x1 = t ^ <*m*> & t ^ <*m*> in Z1 with-replacement p,Z2 ) by A12;
consider k being Element of NAT such that
A21: ( x2 = t ^ <*k*> & t ^ <*k*> in Z1 with-replacement p,Z2 ) by A12, A19;
t2 ^ <*m*> = f . x1 by A12, A19, A20
.= t2 ^ <*k*> by A12, A19, A21 ;
hence x1 = x2 by A20, A21, FINSEQ_1:46; :: thesis: verum

end;

hence succ t, succ t2 are_equipotent by A12, A13, WELLORD2:def 4; :: thesis: verum