set IT = elementary_tree n;
elementary_tree n, Seg (n + 1) are_equipotent
proof
defpred S1[ set , set ] means ( ( n = {} & c2 = 1 ) or ex n being Element of NAT st
( n = <*n*> & c2 = n + 2 ) );
A12: for x, y, z being set st x in elementary_tree n & S1[x,y] & S1[x,z] holds
y = z
proof
let x, y, z be set ; :: thesis: ( x in elementary_tree n & S1[x,y] & S1[x,z] implies y = z )
assume that
x in elementary_tree n and
A13: ( ( ( x = {} & y = 1 ) or ex n being Element of NAT st
( x = <*n*> & y = n + 2 ) ) & ( ( x = {} & z = 1 ) or ex n being Element of NAT st
( x = <*n*> & z = n + 2 ) ) ) ; :: thesis: y = z
now
given n1 being Element of NAT such that A14: ( x = <*n1*> & y = n1 + 2 ) ; :: thesis: ( ex n2 being Element of NAT st
( x = <*n2*> & z = n2 + 2 ) implies y = z )
given n2 being Element of NAT such that A15: ( x = <*n2*> & z = n2 + 2 ) ; :: thesis: y = z
<*n1*> . 1 = n1 by FINSEQ_1:def 8;
hence y = z by A14, A15, FINSEQ_1:def 8; :: thesis: verum
end;
hence y = z by A13; :: thesis: verum
end;
A16: for x being set st x in elementary_tree n holds
ex y being set st S1[x,y]
proof
let x be set ; :: thesis: ( x in elementary_tree n implies ex y being set st S1[x,y] )
assume A17: x in elementary_tree n ; :: thesis: ex y being set st S1[x,y]
A18: now
assume x in { <*k*> where k is Element of NAT : k < n } ; :: thesis: ex y being set st S1[x,y]
then consider k being Element of NAT such that
A19: x = <*k*> and
k < n ;
reconsider y = k + 2 as set ;
take y = y; :: thesis: S1[x,y]
thus S1[x,y] by A19; :: thesis: verum
end;
now
assume A20: x in {{}} ; :: thesis: ex y being set st S1[x,y]
reconsider y = 1 as set ;
take y = y; :: thesis: S1[x,y]
thus S1[x,y] by A20, TARSKI:def 1; :: thesis: verum
end;
hence ex y being set st S1[x,y] by A17, A18, XBOOLE_0:def 3; :: thesis: verum
end;
consider f being Function such that
A21: ( dom f = elementary_tree n & ( for x being set st x in elementary_tree n holds
S1[x,f . x] ) ) from CLASSES1:sch 1(A16);
 take f ; :: according to WELLORD2:def 4 :: thesis: ( f is one-to-one & proj1 f = elementary_tree n & proj2 f = Seg (n + 1) )
thus f is one-to-one :: thesis: ( proj1 f = elementary_tree n & proj2 f = Seg (n + 1) )
proof
let x be set ; :: according to FUNCT_1:def 4 :: thesis: for b1 being set holds
( not x in proj1 f or not b1 in proj1 f or not f . x = f . b1 or x = b1 )
let y be set ; :: thesis: ( not x in proj1 f or not y in proj1 f or not f . x = f . y or x = y )
assume that
A22: x in dom f and
A23: y in dom f and
A24: f . x = f . y ; :: thesis: x = y
A25: ( ( x = {} & f . x = 1 ) or ex n being Element of NAT st
( x = <*n*> & f . x = n + 2 ) ) by A21, A22;
A26: ( ( y = {} & f . y = 1 ) or ex n being Element of NAT st
( y = <*n*> & f . y = n + 2 ) ) by A21, A23;
A27: now
assume that
x = {} and
A28: f . x = 1 ; :: thesis: for n being Element of NAT holds
( not y = <*n*> or not f . y = n + 2 )
given n being Element of NAT such that y = <*n*> and
A29: f . y = n + 2 ; :: thesis: contradiction
0 + 1 = (n + 1) + 1 by A24, A28, A29;
hence contradiction ; :: thesis: verum
end;
now
assume that
y = {} and
A30: f . y = 1 ; :: thesis: for n being Element of NAT holds
( not x = <*n*> or not f . x = n + 2 )
given n being Element of NAT such that x = <*n*> and
A31: f . x = n + 2 ; :: thesis: contradiction
0 + 1 = (n + 1) + 1 by A24, A30, A31;
hence contradiction ; :: thesis: verum
end;
hence x = y by A24, A25, A26, A27; :: thesis: verum
end;
thus dom f = elementary_tree n by A21; :: thesis: proj2 f = Seg (n + 1)
thus rng f c= Seg (n + 1) :: according to XBOOLE_0:def 10 :: thesis: Seg (n + 1) is_a_prefix_of proj2 f
proof
let x be set ; :: according to TARSKI:def 3 :: thesis: ( not x in rng f or x in Seg (n + 1) )
assume x in rng f ; :: thesis: x in Seg (n + 1)
then consider y being set such that
A32: y in dom f and
A33: x = f . y by FUNCT_1:def 3;
1 <= 1 + n by NAT_1:11;
then A34: 1 in Seg (n + 1) by FINSEQ_1:1;
now
given k being Element of NAT such that A35: y = <*k*> and
A36: x = k + 2 ; :: thesis: x in Seg (n + 1)
( y in { <*j*> where j is Element of NAT : j < n } or y in {{}} ) by A21, A32, XBOOLE_0:def 3;
then consider l being Element of NAT such that
A37: ( y = <*l*> & l < n ) by A35, TARSKI:def 1;
( <*k*> . 1 = k & <*l*> . 1 = l ) by FINSEQ_1:def 8;
then k + 1 <= n by A35, A37, NAT_1:13;
then ( 1 + 0 <= (k + 1) + 1 & (k + 1) + 1 <= n + 1 ) by XREAL_1:7;
hence x in Seg (n + 1) by A36, FINSEQ_1:1; :: thesis: verum
end;
hence x in Seg (n + 1) by A21, A32, A33, A34; :: thesis: verum
end;
let x be set ; :: according to TARSKI:def 3 :: thesis: ( not x in Seg (n + 1) or x in proj2 f )
assume A38: x in Seg (n + 1) ; :: thesis: x in proj2 f
then reconsider k = x as Element of NAT ;
A39: 1 <= k by A38, FINSEQ_1:1;
A40: k <= n + 1 by A38, FINSEQ_1:1;
{} in {{}} by TARSKI:def 1;
then A41: {} in elementary_tree n by XBOOLE_0:def 3;
then S1[ {} ,f . {}] by A21;
then A42: 1 in rng f by A21, A41, FUNCT_1:def 3;
now
assume 1 < k ; :: thesis: k in rng f
then 1 + 1 <= k by NAT_1:13;
then consider m being Nat such that
A43: k = 2 + m by NAT_1:10;
reconsider m = m as Element of NAT by ORDINAL1:def 12;
(1 + 1) + m = 1 + (1 + m) ;
then 1 + m <= n by A40, A43, XREAL_1:6;
then m < n by NAT_1:13;
then <*m*> in { <*j*> where j is Element of NAT : j < n } ;
then A44: <*m*> in elementary_tree n by XBOOLE_0:def 3;
then S1[<*m*>,f . <*m*>] by A21;
then k = f . <*m*> by A12, A43, A44;
hence k in rng f by A21, A44, FUNCT_1:def 3; :: thesis: verum
end;
hence x in proj2 f by A39, A42, XXREAL_0:1; :: thesis: verum
end;
hence elementary_tree n is finite by CARD_1:38; :: thesis: verum