defpred S1[ set , set , set ] means ( ( $2 is MCS:Labeling of G & $1 is Nat & ex nn being Nat ex Gn, Gn1 being MCS:Labeling of G st
( $1 = nn & $2 = Gn & $3 = Gn1 & Gn1 = MCS:Step Gn ) ) or ( ( not $2 is MCS:Labeling of G or not $1 is Nat ) & $2 = $3 ) );
now for n, x being set ex y being set st S1[n,x,y]let n,
x be
set ;
ex y being set st S1[n,x,y]now ex y being set st S1[n,x,y]end; hence
ex
y being
set st
S1[
n,
x,
y]
;
verum end;
then A2:
for n being Nat
for x being set ex y being set st S1[n,x,y]
;
consider IT being Function such that
A3:
( dom IT = NAT & IT . 0 = MCS:Init G & ( for n being Nat holds S1[n,IT . n,IT . (n + 1)] ) )
from RECDEF_1:sch 1(A2);
reconsider IT = IT as ManySortedSet of NAT by A3, PARTFUN1:def 2, RELAT_1:def 18;
defpred S2[ Nat] means IT . $1 is MCS:Labeling of G;
A4:
now for n being Nat st S2[n] holds
S2[n + 1]let n be
Nat;
( S2[n] implies S2[n + 1] )assume A5:
S2[
n]
;
S2[n + 1]
ex
nn being
Nat ex
Gn,
Gn1 being
MCS:Labeling of
G st
(
n = nn &
IT . n = Gn &
IT . (n + 1) = Gn1 &
Gn1 = MCS:Step Gn )
by A3, A5;
hence
S2[
n + 1]
;
verum end;
A6:
S2[ 0 ]
by A3;
for n being Nat holds S2[n]
from NAT_1:sch 2(A6, A4);
then reconsider IT = IT as MCS:LabelingSeq of G by Def23;
take
IT
; ( IT . 0 = MCS:Init G & ( for n being Nat holds IT . (n + 1) = MCS:Step (IT . n) ) )
thus
IT . 0 = MCS:Init G
by A3; for n being Nat holds IT . (n + 1) = MCS:Step (IT . n)
let n be Nat; IT . (n + 1) = MCS:Step (IT . n)
ex nn being Nat ex Gn, Gn1 being MCS:Labeling of G st
( n = nn & IT . n = Gn & IT . (n + 1) = Gn1 & Gn1 = MCS:Step Gn )
by A3;
hence
IT . (n + 1) = MCS:Step (IT . n)
; verum