let R be non empty reflexive RelStr ; 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; ( 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
; 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; ( 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 )
; 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;
for x being set ex y being set st S1[n,x,y]let x be
set ;
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
;
ex y being set st S1[n,x,y]take
a
;
S1[n,x,a]thus
S1[
n,
x,
a]
by A7;
verum end; suppose
x is
Nat
;
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);
S1[n,x,J]let X be
Nat;
( 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
;
( 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
;
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;
( 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
;
( 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;
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
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
; 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 ]
A23:
for n being Nat st S3[n] holds
S3[n + 1]
for n being Nat holds S3[n]
from NAT_1:sch 2(A20, A23);
hence
fN is non-descending
; verum