reconsider IT = { <*k*> where k is Element of NAT : k < n } \/ {{} } as non empty set ;
IT is Tree-like
proof
thus IT c= NAT * :: according to TREES_1:def 5 :: thesis: ( ( for p being FinSequence of NAT st p in IT holds
ProperPrefixes p c= IT ) & ( for p being FinSequence of NAT
for k, n being Element of NAT st p ^ <*k*> in IT & n <= k holds
p ^ <*n*> in IT ) )
proof
let x be set ; :: according to TARSKI:def 3 :: thesis: ( not x in IT or x in NAT * )
assume x in IT ; :: thesis: x in NAT *
then A3: ( x in { <*k*> where k is Element of NAT : k < n } or x in {{} } ) by XBOOLE_0:def 3;
A4: {} in NAT * by FINSEQ_1:66;
now
assume x in { <*k*> where k is Element of NAT : k < n } ; :: thesis: x in NAT *
then ex k being Element of NAT st
( x = <*k*> & k < n ) ;
hence x in NAT * by FINSEQ_1:def 11; :: thesis: verum
end;
hence x in NAT * by A3, A4, TARSKI:def 1; :: thesis: verum
end;
thus for p being FinSequence of NAT st p in IT holds
ProperPrefixes p c= IT :: thesis: for p being FinSequence of NAT
for k, n being Element of NAT st p ^ <*k*> in IT & n <= k holds
p ^ <*n*> in IT
proof
let p be FinSequence of NAT ; :: thesis: ( p in IT implies ProperPrefixes p c= IT )
assume p in IT ; :: thesis: ProperPrefixes p c= IT
then A9: ( p in { <*k*> where k is Element of NAT : k < n } or p in {{} } ) by XBOOLE_0:def 3;
A10: {} c= IT by XBOOLE_1:2;
now
assume p in { <*k*> where k is Element of NAT : k < n } ; :: thesis: ProperPrefixes p c= IT
then ex k being Element of NAT st
( p = <*k*> & k < n ) ;
then ProperPrefixes p = {{} } by Th40;
hence ProperPrefixes p c= IT by XBOOLE_1:7; :: thesis: verum
end;
hence ProperPrefixes p c= IT by A9, A10, Th39, TARSKI:def 1; :: thesis: verum
end;
let p be FinSequence of NAT ; :: thesis: for k, n being Element of NAT st p ^ <*k*> in IT & n <= k holds
p ^ <*n*> in IT
let k, m be Element of NAT ; :: thesis: ( p ^ <*k*> in IT & m <= k implies p ^ <*m*> in IT )
assume p ^ <*k*> in IT ; :: thesis: ( not m <= k or p ^ <*m*> in IT )
then ( p ^ <*k*> in { <*j*> where j is Element of NAT : j < n } or p ^ <*k*> in {{} } ) by XBOOLE_0:def 3;
then consider l being Element of NAT such that
A17: p ^ <*k*> = <*l*> and
A18: l < n by TARSKI:def 1;
(len p) + (len <*k*>) = len <*l*> by A17, FINSEQ_1:35
.= 1 by FINSEQ_1:56 ;
then (len p) + 1 = 0 + 1 by FINSEQ_1:56;
then A21: p = {} ;
then A22: <*k*> = <*l*> by A17, FINSEQ_1:47;
<*k*> . 1 = k by FINSEQ_1:def 8;
then A24: k = l by A22, FINSEQ_1:def 8;
assume A25: m <= k ; :: thesis: p ^ <*m*> in IT
A26: p ^ <*m*> = <*m*> by A21, FINSEQ_1:47;
m < n by A18, A24, A25, XXREAL_0:2;
then p ^ <*m*> in { <*j*> where j is Element of NAT : j < n } by A26;
hence p ^ <*m*> in IT by XBOOLE_0:def 3; :: thesis: verum
end;
then reconsider IT = IT as Tree ;
IT, Seg (n + 1) are_equipotent
proof
defpred S1[ set , set ] means ( ( $1 = {} & $2 = 1 ) or ex n being Element of NAT st
( $1 = <*n*> & $2 = n + 2 ) );
A30: for x, y, z being set st x in IT & S1[x,y] & S1[x,z] holds
y = z
proof
let x, y, z be set ; :: thesis: ( x in IT & S1[x,y] & S1[x,z] implies y = z )
assume that
x in IT and
A31: ( ( ( 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 A33: ( 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 A34: ( x = <*n2*> & z = n2 + 2 ) ; :: thesis: y = z
<*n1*> . 1 = n1 by FINSEQ_1:def 8;
hence y = z by A33, A34, FINSEQ_1:def 8; :: thesis: verum
end;
hence y = z by A31; :: thesis: verum
end;
A36: for x being set st x in IT holds
ex y being set st S1[x,y]
proof
let x be set ; :: thesis: ( x in IT implies ex y being set st S1[x,y] )
assume A37: x in IT ; :: thesis: ex y being set st S1[x,y]
A38: 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
A40: x = <*k*> and
k < n ;
reconsider y = k + 2 as set ;
take y = y; :: thesis: S1[x,y]
thus S1[x,y] by A40; :: thesis: verum
end;
now
assume A42: 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 A42, TARSKI:def 1; :: thesis: verum
end;
hence ex y being set st S1[x,y] by A37, A38, XBOOLE_0:def 3; :: thesis: verum
end;
consider f being Function such that
A43: ( dom f = IT & ( for x being set st x in IT holds
S1[x,f . x] ) ) from CLASSES1:sch 1(A36);
 take f ; :: according to WELLORD2:def 4 :: thesis: ( f is one-to-one & proj1 f = IT & proj2 f = Seg (n + 1) )
thus f is one-to-one :: thesis: ( proj1 f = IT & proj2 f = Seg (n + 1) )
proof
let x be set ; :: according to FUNCT_1:def 8 :: 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
A44: x in dom f and
A45: y in dom f and
A46: f . x = f . y ; :: thesis: x = y
A47: ( ( x = {} & f . x = 1 ) or ex n being Element of NAT st
( x = <*n*> & f . x = n + 2 ) ) by A43, A44;
A48: ( ( y = {} & f . y = 1 ) or ex n being Element of NAT st
( y = <*n*> & f . y = n + 2 ) ) by A43, A45;
A49: now
assume that
x = {} and
A50: 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
A51: f . y = n + 2 ; :: thesis: contradiction
0 + 1 = (n + 1) + 1 by A46, A50, A51;
hence contradiction ; :: thesis: verum
end;
now
assume that
y = {} and
A54: 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
A55: f . x = n + 2 ; :: thesis: contradiction
0 + 1 = (n + 1) + 1 by A46, A54, A55;
hence contradiction ; :: thesis: verum
end;
hence x = y by A46, A47, A48, A49; :: thesis: verum
end;
thus dom f = IT by A43; :: 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
A58: y in dom f and
A59: x = f . y by FUNCT_1:def 5;
1 <= 1 + n by NAT_1:11;
then A61: 1 in Seg (n + 1) by FINSEQ_1:3;
now
given k being Element of NAT such that A63: y = <*k*> and
A64: x = k + 2 ; :: thesis: x in Seg (n + 1)
( y in { <*j*> where j is Element of NAT : j < n } or y in {{} } ) by A43, A58, XBOOLE_0:def 3;
then consider l being Element of NAT such that
A66: ( y = <*l*> & l < n ) by A63, TARSKI:def 1;
( <*k*> . 1 = k & <*l*> . 1 = l ) by FINSEQ_1:def 8;
then k + 1 <= n by A63, A66, NAT_1:13;
then ( 1 + 0 <= (k + 1) + 1 & (k + 1) + 1 <= n + 1 ) by XREAL_1:9;
hence x in Seg (n + 1) by A64, FINSEQ_1:3; :: thesis: verum
end;
hence x in Seg (n + 1) by A43, A58, A59, A61; :: 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 A70: x in Seg (n + 1) ; :: thesis: x in proj2 f
then reconsider k = x as Element of NAT ;
A71: 1 <= k by A70, FINSEQ_1:3;
A72: k <= n + 1 by A70, FINSEQ_1:3;
{} in {{} } by TARSKI:def 1;
then A74: {} in IT by XBOOLE_0:def 3;
then S1[ {} ,f . {} ] by A43;
then A76: 1 in rng f by A43, A74, FUNCT_1:def 5;
now
assume 1 < k ; :: thesis: k in rng f
then 1 + 1 <= k by NAT_1:13;
then consider m being Nat such that
A80: k = 2 + m by NAT_1:10;
reconsider m = m as Element of NAT by ORDINAL1:def 13;
(1 + 1) + m = 1 + (1 + m) ;
then 1 + m <= n by A72, A80, XREAL_1:8;
then m < n by NAT_1:13;
then <*m*> in { <*j*> where j is Element of NAT : j < n } ;
then A85: <*m*> in IT by XBOOLE_0:def 3;
then S1[<*m*>,f . <*m*>] by A43;
then k = f . <*m*> by A30, A80, A85;
hence k in rng f by A43, A85, FUNCT_1:def 5; :: thesis: verum
end;
hence x in proj2 f by A71, A76, XXREAL_0:1; :: thesis: verum
end;
hence { <*k*> where k is Element of NAT : k < n } \/ {{} } is finite Tree by CARD_1:68; :: thesis: verum