let R be non empty reflexive RelStr ; :: thesis: for f being sequence of R st R is connected holds
for X being Subset of R st rng f c= X & X is well_founded holds
ex s being subsequence of f st s is non-descending

let f be sequence of R; :: thesis: ( R is connected implies for X being Subset of R st rng f c= X & X is well_founded holds
ex s being subsequence of f st s is non-descending )

assume A1: R is connected ; :: thesis: for X being Subset of R st rng f c= X & X is well_founded holds
ex s being subsequence of f st s is non-descending

let X be Subset of R; :: thesis: ( rng f c= X & X is well_founded implies ex s being subsequence of f st s is non-descending )
assume A2: ( rng f c= X & X is well_founded ) ; :: thesis: ex s being subsequence of f st s is non-descending
set I = the InternalRel of R;
consider m being object such that
A3: ( m in rng f & the InternalRel of R -Seg m misses rng f ) by A2, WELLFND1:def 3, WELLORD1:def 3;
reconsider m = m as Element of R by A3;
consider a being object such that
A4: ( a in dom f & f . a = m ) by A3, FUNCT_1:def 3;
A5: dom f = NAT by FUNCT_2:def 1;
reconsider a = a as Nat by A4;
defpred S1[ Nat, set , set ] means for i being Nat st i = $2 holds
( $3 is Nat & ( for j being Nat st j = $3 holds
( i < j & f . j in rng (f ^\ (i + 1)) & the InternalRel of R -Seg (f . j) misses rng (f ^\ (i + 1)) ) ) );
A6: for n being Nat
for x being set ex y being set st S1[n,x,y]
proof
let n be Nat; :: thesis: for x being set ex y being set st S1[n,x,y]
let x be set ; :: thesis: ex y being set st S1[n,x,y]
per cases ( not x is Nat or x is Nat ) ;
suppose A7: x is not Nat ; :: thesis: ex y being set st S1[n,x,y]
take a ; :: thesis: S1[n,x,a]
thus S1[n,x,a] by A7; :: thesis: verum
end;
suppose x is Nat ; :: thesis: ex y being set st S1[n,x,y]
then reconsider i = x as Nat ;
set i1 = i + 1;
rng (f ^\ (i + 1)) c= rng f by NAT_1:55;
then rng (f ^\ (i + 1)) c= X by A2;
then consider a being object such that
A8: ( a in rng (f ^\ (i + 1)) & the InternalRel of R -Seg a misses rng (f ^\ (i + 1)) ) by A2, WELLFND1:def 3, WELLORD1:def 3;
consider j being object such that
A9: ( j in dom (f ^\ (i + 1)) & (f ^\ (i + 1)) . j = a ) by A8, FUNCT_1:def 3;
reconsider j = j as Nat by A9;
take J = j + (i + 1); :: thesis: S1[n,x,J]
let X be Nat; :: thesis: ( X = x implies ( J is Nat & ( for j being Nat st j = J holds
( X < j & f . j in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j) misses rng (f ^\ (X + 1)) ) ) ) )

assume A10: X = x ; :: thesis: ( J is Nat & ( for j being Nat st j = J holds
( X < j & f . j in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j) misses rng (f ^\ (X + 1)) ) ) )

thus J is Nat ; :: thesis: for j being Nat st j = J holds
( X < j & f . j in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j) misses rng (f ^\ (X + 1)) )

let j1 be Nat; :: thesis: ( j1 = J implies ( X < j1 & f . j1 in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j1) misses rng (f ^\ (X + 1)) ) )
assume A11: j1 = J ; :: thesis: ( X < j1 & f . j1 in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j1) misses rng (f ^\ (X + 1)) )
i + 1 <= J by NAT_1:11;
hence ( X < j1 & f . j1 in rng (f ^\ (X + 1)) & the InternalRel of R -Seg (f . j1) misses rng (f ^\ (X + 1)) ) by A8, A10, A11, A9, NAT_1:13, NAT_1:def 3; :: thesis: verum
end;
end;
end;
consider N being Function such that
A12: ( dom N = NAT & N . 0 = a ) and
A13: for n being Nat holds S1[n,N . n,N . (n + 1)] from RECDEF_1:sch 1(A6);
defpred S2[ Nat] means N . $1 is Nat;
A14: S2[ 0 ] by A12;
A15: for j being Nat st S2[j] holds
S2[j + 1] by A13;
A16: for j being Nat holds S2[j] from NAT_1:sch 2(A14, A15);
rng N c= NAT
proof
let b be object ; :: according to TARSKI:def 3 :: thesis: ( not b in rng N or b in NAT )
assume A17: b in rng N ; :: thesis: b in NAT
consider a being object such that
A18: ( a in dom N & N . a = b ) by A17, FUNCT_1:def 3;
reconsider a = a as Nat by A12, A18;
N . a is Nat by A16;
hence b in NAT by A18, ORDINAL1:def 12; :: thesis: verum
end;
then reconsider N = N as sequence of NAT by A12, FUNCT_2:2;
for n being Nat holds N . n < N . (n + 1) by A13;
then reconsider N = N as increasing sequence of NAT by VALUED_1:def 13;
reconsider fN = f * N as subsequence of f ;
take fN ; :: thesis: fN is non-descending
defpred S3[ Nat] means ( [(fN . $1),(fN . ($1 + 1))] in the InternalRel of R & the InternalRel of R -Seg (fN . ($1 + 1)) misses rng (f ^\ ((N . $1) + 1)) );
A20: S3[ 0 ]
proof
A21: ( fN . 0 = m & fN . 1 = f . (N . 1) ) by A4, A12, FUNCT_2:15;
A22: f . (N . 1) in rng f by A5, FUNCT_1:def 3;
reconsider fN1 = fN . 1 as Element of R ;
not fN1 in the InternalRel of R -Seg m by A21, A22, A3, XBOOLE_0:3;
per cases then ( m = fN1 or not [fN1,m] in the InternalRel of R ) by WELLORD1:1;
end;
end;
A23: for n being Nat st S3[n] holds
S3[n + 1]
proof
let n be Nat; :: thesis: ( S3[n] implies S3[n + 1] )
assume A24: S3[n] ; :: thesis: S3[n + 1]
set n1 = n + 1;
set n2 = (n + 1) + 1;
A25: ( fN . (n + 1) = f . (N . (n + 1)) & fN . ((n + 1) + 1) = f . (N . ((n + 1) + 1)) ) by FUNCT_2:15;
reconsider fN1 = fN . (n + 1), fN2 = fN . ((n + 1) + 1) as Element of R ;
N . n < N . (n + 1) by A13;
then reconsider K = (N . (n + 1)) - (N . n) as Nat by NAT_1:21;
(N . (n + 1)) + 1 = ((N . n) + 1) + K ;
then f ^\ ((N . (n + 1)) + 1) = (f ^\ ((N . n) + 1)) ^\ K by NAT_1:48;
then A26: rng (f ^\ ((N . (n + 1)) + 1)) c= rng (f ^\ ((N . n) + 1)) by NAT_1:55;
A27: fN2 in rng (f ^\ ((N . (n + 1)) + 1)) by A25, A13;
not fN2 in the InternalRel of R -Seg fN1 by A24, A26, A27, XBOOLE_0:3;
per cases then ( fN1 = fN2 or not [fN2,fN1] in the InternalRel of R ) by WELLORD1:1;
end;
end;
for n being Nat holds S3[n] from NAT_1:sch 2(A20, A23);
hence fN is non-descending ; :: thesis: verum