defpred S1[ set , set , set ] means verum;
set S0 = 1GateCircStr (<*>,((0 -tuples_on BOOLEAN) --> TRUE));
set Sn = n -BitGFA1Str (x,y);
set o0 = [<*>,((0 -tuples_on BOOLEAN) --> TRUE)];
deffunc H1( non empty ManySortedSign , set , Nat) -> ManySortedSign = $1 +* (BitGFA1Str ((x . ($3 + 1)),(y . ($3 + 1)),$2));
deffunc H2( set , Nat) -> Element of InnerVertices (GFA1CarryStr ((x . ($2 + 1)),(y . ($2 + 1)),$1)) = GFA1CarryOutput ((x . ($2 + 1)),(y . ($2 + 1)),$1);
consider f, g being ManySortedSet of NAT such that
A13: n -BitGFA1Str (x,y) = f . n and
A14: f . 0 = 1GateCircStr (<*>,((0 -tuples_on BOOLEAN) --> TRUE)) and
A15: g . 0 = [<*>,((0 -tuples_on BOOLEAN) --> TRUE)] and
A16: for n being Nat
for S being non empty ManySortedSign
for z being set st S = f . n & z = g . n holds
( f . (n + 1) = H1(S,z,n) & g . (n + 1) = H2(z,n) ) by Def5;
defpred S2[ Nat] means ex S being non empty ManySortedSign st
( S = f . $1 & g . $1 in InnerVertices S );
InnerVertices (1GateCircStr (<*>,((0 -tuples_on BOOLEAN) --> TRUE))) = {[<*>,((0 -tuples_on BOOLEAN) --> TRUE)]} by CIRCCOMB:42;
then [<*>,((0 -tuples_on BOOLEAN) --> TRUE)] in InnerVertices (1GateCircStr (<*>,((0 -tuples_on BOOLEAN) --> TRUE))) by TARSKI:def 1;
then A17: S2[ 0 ] by A14, A15;
A18: for i being Nat st S2[i] holds
S2[i + 1]
proof
let i be Nat; :: thesis: ( S2[i] implies S2[i + 1] )
assume that
A19: ex S being non empty ManySortedSign st
( S = f . i & g . i in InnerVertices S ) and
A20: for S being non empty ManySortedSign st S = f . (i + 1) holds
not g . (i + 1) in InnerVertices S ; :: thesis: contradiction
consider S being non empty ManySortedSign such that
A21: S = f . i and
g . i in InnerVertices S by A19;
GFA1CarryOutput ((x . (i + 1)),(y . (i + 1)),(g . i)) in InnerVertices (BitGFA1Str ((x . (i + 1)),(y . (i + 1)),(g . i))) by GFACIRC1:69;
then A22: GFA1CarryOutput ((x . (i + 1)),(y . (i + 1)),(g . i)) in InnerVertices (S +* (BitGFA1Str ((x . (i + 1)),(y . (i + 1)),(g . i)))) by FACIRC_1:22;
A23: f . (i + 1) = S +* (BitGFA1Str ((x . (i + 1)),(y . (i + 1)),(g . i))) by A16, A21;
g . (i + 1) = GFA1CarryOutput ((x . (i + 1)),(y . (i + 1)),(g . i)) by A16, A21;
hence contradiction by A20, A22, A23; :: thesis: verum
end;
for i being Nat holds S2[i] from NAT_1:sch 2(A17, A18);
 then ex S being non empty ManySortedSign st
( S = f . n & g . n in InnerVertices S ) ;
then reconsider o = g . n as Element of InnerVertices (n -BitGFA1Str (x,y)) by A13;
take o ; :: thesis: ex h being ManySortedSet of NAT st
( o = h . n & h . 0 = [<*>,((0 -tuples_on BOOLEAN) --> TRUE)] & ( for n being Nat holds h . (n + 1) = GFA1CarryOutput ((x . (n + 1)),(y . (n + 1)),(h . n)) ) )
take g ; :: thesis: ( o = g . n & g . 0 = [<*>,((0 -tuples_on BOOLEAN) --> TRUE)] & ( for n being Nat holds g . (n + 1) = GFA1CarryOutput ((x . (n + 1)),(y . (n + 1)),(g . n)) ) )
thus ( o = g . n & g . 0 = [<*>,((0 -tuples_on BOOLEAN) --> TRUE)] ) by A15; :: thesis: for n being Nat holds g . (n + 1) = GFA1CarryOutput ((x . (n + 1)),(y . (n + 1)),(g . n))
let i be Nat; :: thesis: g . (i + 1) = GFA1CarryOutput ((x . (i + 1)),(y . (i + 1)),(g . i))
A24: ex S being non empty ManySortedSign ex x being set st
( S = f . 0 & x = g . 0 & S1[S,x, 0 ] ) by A14;
A25: for n being Nat
for S being non empty ManySortedSign
for x being set st S = f . n & x = g . n & S1[S,x,n] holds
S1[H1(S,x,n),H2(x,n),n + 1] ;
for n being Nat ex S being non empty ManySortedSign st
( S = f . n & S1[S,g . n,n] ) from CIRCCMB2:sch 2(A24, A16, A25);
 then ex S being non empty ManySortedSign st S = f . i ;
hence g . (i + 1) = GFA1CarryOutput ((x . (i + 1)),(y . (i + 1)),(g . i)) by A16; :: thesis: verum