FOMODEL4: Sequent calculus, derivability, provability. Goedel's completeness theorem.

:: Sequent calculus, derivability, provability. Goedel's completeness theorem.
:: by Marco B. Caminati
::
:: Received December 29, 2010
:: Copyright (c) 2010-2012 Association of Mizar Users

begin

Lm1: for X, A, B being set st X is Subset of (Funcs (A,B)) holds
X is Subset-Family of [:A,B:]

proof end;

Lm2: for S being Language
for t1, t2 being termal string of S holds (<*(TheEqSymbOf S)*> ^ t1) ^ t2 is 0wff string of S

proof end;

::#####################################################################
::#Definitions and auxiliary lemmas

definition

let S be Language;

func S -sequents -> set equals :: FOMODEL4:def 1
{ [premises,conclusion] where premises is Subset of (AllFormulasOf S), conclusion is wff string of S : premises is finite } ;

coherence ;

end;

:: deftheorem defines -sequents FOMODEL4:def 1 :

registration

let S be Language;

cluster S -sequents -> non empty ;

coherence

proof end;

end;

registration

let S be Language;

cluster S -sequents -> Relation-like ;

coherence

proof end;

end;

definition

let S be Language;
let x be set ;

attr x is S -sequent-like means :Def2: :: FOMODEL4:def 2
x in S -sequents ;

end;

:: deftheorem Def2 defines -sequent-like FOMODEL4:def 2 :

definition

let S be Language;
let X be set ;

attr X is S -sequents-like means :Def3: :: FOMODEL4:def 3
X c= S -sequents ;

end;

:: deftheorem Def3 defines -sequents-like FOMODEL4:def 3 :

registration

let S be Language;

cluster -> S -sequents-like for Element of bool (S -sequents);

coherence by Def3;

cluster -> S -sequent-like for Element of S -sequents ;

coherence by Def2;

end;

registration

let S be Language;

cluster S -sequent-like for Element of S -sequents ;

existence

proof end;

cluster Relation-like S -sequents-like for Element of bool (S -sequents);

existence

proof end;

end;

registration

let S be Language;

cluster S -sequent-like for set ;

existence

proof end;

cluster S -sequents-like for set ;

existence

proof end;

end;

definition

let S be Language;
mode Rule of S is Element of Funcs ((bool (S -sequents)),(bool (S -sequents)));

end;

definition

let S be Language;
mode RuleSet of S is Subset of (Funcs ((bool (S -sequents)),(bool (S -sequents))));

end;

registration

let A, B be set ;
let X be Subset of (Funcs (A,B));

cluster union X -> Relation-like ;

coherence ;

end;

registration

let S be Language;
let D be RuleSet of S;

cluster union D -> Relation-like ;

coherence ;

end;

definition

let S be Language;
let D be RuleSet of S;

func OneStep D -> Rule of S means :Def4: :: FOMODEL4:def 4
for Seqs being Element of bool (S -sequents) holds it . Seqs = union ((union D) .: {Seqs});

existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def4 defines OneStep FOMODEL4:def 4 :

Lm3: for m being Nat
for S being Language
for D being RuleSet of S
for R being Rule of S
for Seqts being Subset of (S -sequents)
for SQ being b₂ -sequents-like set holds
( dom (OneStep D) = bool (S -sequents) & rng (OneStep D) c= dom (OneStep D) & iter ((OneStep D),m) is Function of (bool (S -sequents)),(bool (S -sequents)) & dom (iter ((OneStep D),m)) = bool (S -sequents) & (dom (OneStep D)) \/ (rng (OneStep D)) = bool (S -sequents) & Seqts in dom R & SQ in dom (iter (R,m)) )

proof end;

definition

let S be Language;
let D be RuleSet of S;
let m be Nat;

func (m,D) -derivables -> Rule of S equals :: FOMODEL4:def 5
iter ((OneStep D),m);

coherence

proof end;

end;

:: deftheorem defines -derivables FOMODEL4:def 5 :

definition

let S be Language;
let D be RuleSet of S;
let Seqs1, Seqs2 be set ;

attr Seqs2 is Seqs1,D -derivable means :Def6: :: FOMODEL4:def 6
Seqs2 c= union (((OneStep D) [*]) .: {Seqs1});

end;

:: deftheorem Def6 defines -derivable FOMODEL4:def 6 :

definition

let m be Nat;
let S be Language;
let D be RuleSet of S;
let Seqts, seqt be set ;

attr seqt is m,Seqts,D -derivable means :Def7: :: FOMODEL4:def 7
seqt in ((m,D) -derivables) . Seqts;

end;

:: deftheorem Def7 defines -derivable FOMODEL4:def 7 :

definition

let S be Language;
let D be RuleSet of S;

func D -iterators -> Subset-Family of [:(bool (S -sequents)),(bool (S -sequents)):] equals :: FOMODEL4:def 8
{ (iter ((OneStep D),mm)) where mm is Element of NAT : verum } ;

coherence

proof end;

end;

:: deftheorem defines -iterators FOMODEL4:def 8 :

definition

let S be Language;
let R be Rule of S;

attr R is isotone means :Def9: :: FOMODEL4:def 9
for Seqts1, Seqts2 being Subset of (S -sequents) st Seqts1 c= Seqts2 holds
R . Seqts1 c= R . Seqts2;

end;

:: deftheorem Def9 defines isotone FOMODEL4:def 9 :

Lm4: for S being Language
for R being Rule of S holds
( id (bool (S -sequents)) is Rule of S & ( R = id (bool (S -sequents)) implies R is isotone ) )

proof end;

registration

let S be Language;

cluster Relation-like bool (S -sequents) -defined bool (S -sequents) -valued Function-like total quasi_total isotone for Element of Funcs ((bool (S -sequents)),(bool (S -sequents)));

existence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;

attr D is isotone means :Def10: :: FOMODEL4:def 10
for Seqts1, Seqts2 being Subset of (S -sequents)
for f being Function st Seqts1 c= Seqts2 & f in D holds
ex g being Function st
( g in D & f . Seqts1 c= g . Seqts2 );

end;

:: deftheorem Def10 defines isotone FOMODEL4:def 10 :

registration

let S be Language;
let M be isotone Rule of S;

cluster {M} -> isotone for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster functional isotone for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;
let Seqts be set ;

attr Seqts is D -derivable means :Def11: :: FOMODEL4:def 11
Seqts is {} ,D -derivable ;

end;

:: deftheorem Def11 defines -derivable FOMODEL4:def 11 :

registration

let S be Language;
let D be RuleSet of S;

cluster D -derivable -> {} ,D -derivable for set ;

coherence by Def11;

cluster {} ,D -derivable -> D -derivable for set ;

coherence by Def11;

end;

registration

let S be Language;
let D be RuleSet of S;
let Seqts be empty set ;

cluster Seqts,D -derivable -> D -derivable for set ;

coherence ;

end;

definition

let S be Language;
let D be RuleSet of S;
let X, phi be set ;

attr phi is X,D -provable means :Def12: :: FOMODEL4:def 12
( {[X,phi]} is D -derivable or ex seqt being set st
( seqt `1 c= X & seqt `2 = phi & {seqt} is D -derivable ) );

end;

:: deftheorem Def12 defines -provable FOMODEL4:def 12 :

definition

let S be Language;
let D be RuleSet of S;
let X, x be set ;

redefine attr x is X,D -provable means :Def13: :: FOMODEL4:def 13
ex seqt being set st
( seqt `1 c= X & seqt `2 = x & {seqt} is D -derivable );

compatibility

proof end;

end;

:: deftheorem Def13 defines -provable FOMODEL4:def 13 :

definition

let S be Language;
let D be RuleSet of S;
let R be Rule of S;

attr R is D -macro means :: FOMODEL4:def 14
for Seqs being Subset of (S -sequents) holds R . Seqs is Seqs,D -derivable ;

end;

:: deftheorem defines -macro FOMODEL4:def 14 :

definition

let S be Language;
let D be RuleSet of S;
let Phi be set ;

func (Phi,D) -termEq -> set equals :: FOMODEL4:def 15
{ [t1,t2] where t1, t2 is termal string of S : (<*(TheEqSymbOf S)*> ^ t1) ^ t2 is Phi,D -provable } ;

coherence ;

end;

:: deftheorem defines -termEq FOMODEL4:def 15 :

definition

let S be Language;
let D be RuleSet of S;
let Phi be set ;

attr Phi is D -expanded means :Def16: :: FOMODEL4:def 16
for x being set st x is Phi,D -provable holds
{x} c= Phi;

end;

:: deftheorem Def16 defines -expanded FOMODEL4:def 16 :

definition

let S be Language;
let x be set ;

attr x is S -null means :Def17: :: FOMODEL4:def 17
verum;

end;

:: deftheorem Def17 defines -null FOMODEL4:def 17 :

Lm5: for X, Y, x being set
for S being Language
for D being RuleSet of S st X c= Y & x is X,D -provable holds
x is Y,D -provable

proof end;

::#####################################################################
::#####################################################################
::#####################################################################
::#Type Tuning

definition

let S be Language;
let D be RuleSet of S;
let Phi be set ;
:: original: -termEq
redefine func (Phi,D) -termEq -> Relation of (AllTermsOf S);
coherence

proof end;

end;

registration

let S be Language;
let phi be wff string of S;
let Phi1, Phi2 be finite Subset of (AllFormulasOf S);

cluster [(Phi1 \/ Phi2),phi] -> S -sequent-like ;

coherence

proof end;

end;

definition

let S be Language;
let x be empty set ;
let phi be wff string of S;
:: original: [
redefine func [x,phi] -> Element of S -sequents ;
coherence

proof end;

end;

registration

let S be Language;

cluster {} /\ S -> S -sequents-like for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster S -null for set ;

existence by Def17;

end;

registration

let S be Language;

cluster S -sequent-like -> S -null for set ;

coherence by Def17;

end;

registration

let S be Language;

cluster -> S -null for Element of S -sequents ;

coherence ;

end;

registration

let m be Nat;
let S be Language;
let D be RuleSet of S;
let X be set ;

cluster ((m,D) -derivables) . X -> S -sequents-like ;

coherence

proof end;

end;

registration

let S be Language;
let Y be set ;
let X be S -sequents-like set ;

cluster X /\ Y -> S -sequents-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let D be RuleSet of S;
let m be Nat;
let X be set ;

cluster m,X,D -derivable -> S -sequent-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let D be RuleSet of S;
let Phi1, Phi2 be set ;

cluster Phi1 \ Phi2,D -provable -> Phi1,D -provable for set ;

coherence by Lm5;

end;

registration

let S be Language;
let D be RuleSet of S;
let Phi1, Phi2 be set ;

cluster Phi1 \ Phi2,D -provable -> Phi1 \/ Phi2,D -provable for set ;

coherence by Lm5, XBOOLE_1:7;

end;

registration

let S be Language;
let D be RuleSet of S;
let Phi1, Phi2 be set ;

cluster Phi1 /\ Phi2,D -provable -> Phi1,D -provable for set ;

coherence by Lm5;

end;

registration

let S be Language;
let D be RuleSet of S;
let X be set ;
let x be Subset of X;

cluster x,D -provable -> X,D -provable for set ;

coherence

proof end;

end;

registration

let S be Language;
let premises be finite Subset of (AllFormulasOf S);
let phi be wff string of S;

cluster [premises,phi] -> S -sequent-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;

cluster [{phi1},phi2] -> S -sequent-like for set ;

coherence

proof end;

let phi3 be wff string of S;

cluster [{phi1,phi2},phi3] -> S -sequent-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;
let Phi be finite Subset of (AllFormulasOf S);

cluster [(Phi \/ {phi1}),phi2] -> S -sequent-like for set ;

coherence

proof end;

end;

Lm6: for X being set
for S being Language
for D being RuleSet of S st X c= S -sequents holds
(OneStep D) . X = union (union { (R .: {X}) where R is Subset of [:(bool (S -sequents)),(bool (S -sequents)):] : R in D } )

proof end;

Lm7: for S being Language
for R being Rule of S holds R = OneStep {R}

proof end;

Lm8: for y being set
for S being Language
for D being RuleSet of S
for Seqts being Subset of (S -sequents) st {y} is Seqts,D -derivable holds
ex mm being Element of NAT st y is mm,Seqts,D -derivable

proof end;

Lm9: for m being Nat
for X being set
for S being Language
for D being RuleSet of S st X c= S -sequents holds
((m,D) -derivables) . X c= union (((OneStep D) [*]) .: {X})

proof end;

Lm10: for X being set
for S being Language
for D being RuleSet of S holds union (((OneStep D) [*]) .: {X}) = union { (((mm,D) -derivables) . X) where mm is Element of NAT : verum }

proof end;

Lm11: for m being Nat
for X being set
for S being Language
for D being RuleSet of S holds ((m,D) -derivables) . X c= union (((OneStep D) [*]) .: {X})

proof end;

Lm12: for m being Nat
for x, X being set
for S being Language
for D being RuleSet of S st x is m,X,D -derivable holds
{x} is X,D -derivable

proof end;

Lm13: for S being Language
for D1, D2 being RuleSet of S
for Seqts1, Seqts2 being Subset of (S -sequents) st Seqts1 c= Seqts2 & D1 c= D2 & ( D2 is isotone or D1 is isotone ) holds
(OneStep D1) . Seqts1 c= (OneStep D2) . Seqts2

proof end;

Lm14: for m being Nat
for S being Language
for D1, D2 being RuleSet of S
for Seqts1, Seqts2 being Subset of (S -sequents) st Seqts1 c= Seqts2 & D1 c= D2 & ( D2 is isotone or D1 is isotone ) holds
((m,D1) -derivables) . Seqts1 c= ((m,D2) -derivables) . Seqts2

proof end;

Lm15: for m being Nat
for S being Language
for D1, D2 being RuleSet of S
for SQ1, SQ2 being b₂ -sequents-like set st SQ1 c= SQ2 & D1 c= D2 & ( D2 is isotone or D1 is isotone ) holds
((m,D1) -derivables) . SQ1 c= ((m,D2) -derivables) . SQ2

proof end;

Lm16: for m being Nat
for X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D2 is isotone or D1 is isotone ) holds
((m,D1) -derivables) . X c= ((m,D2) -derivables) . X

proof end;

Lm17: for X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D2 is isotone or D1 is isotone ) holds
union (((OneStep D1) [*]) .: {X}) c= union (((OneStep D2) [*]) .: {X})

proof end;

Lm18: for Y, X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D2 is isotone or D1 is isotone ) & Y is X,D1 -derivable holds
Y is X,D2 -derivable

proof end;

Lm19: for Y being set
for S being Language
for R being Rule of S
for Seqts being Subset of (S -sequents) st Y c= R . Seqts holds
Y is Seqts,{R} -derivable

proof end;

Lm20: for m, n being Nat
for Z being set
for S being Language
for D1, D2 being RuleSet of S
for SQ2, SQ1 being b₄ -sequents-like set st D1 is isotone & D1 \/ D2 is isotone & SQ2 c= (iter ((OneStep D1),m)) . SQ1 & Z c= (iter ((OneStep D2),n)) . SQ2 holds
Z c= (iter ((OneStep (D1 \/ D2)),(m + n))) . SQ1

proof end;

Lm21: for m, n being Nat
for y, X, z being set
for S being Language
for D1, D2 being RuleSet of S st D1 is isotone & D1 \/ D2 is isotone & y is m,X,D1 -derivable & z is n,{y},D2 -derivable holds
z is m + n,X,D1 \/ D2 -derivable

proof end;

Lm22: for X being set
for S being Language
for t1, t2 being termal string of S
for D being RuleSet of S holds
( [t1,t2] in (X,D) -termEq iff (<*(TheEqSymbOf S)*> ^ t1) ^ t2 is X,D -provable )

proof end;

Lm23: for S being Language
for Sq being b₁ -sequent-like set holds Sq `2 is wff string of S

proof end;

Lm24: for x, X being set
for S being Language
for D being RuleSet of S st x is X,D -provable holds
x is wff string of S

proof end;

Lm25: for S being Language
for D being RuleSet of S holds AllFormulasOf S is D -expanded

proof end;

registration

let S be Language;
let D be RuleSet of S;

cluster functional V36() FinSequence-membered with_non-empty_elements D -expanded for Element of bool (AllFormulasOf S);

existence

proof end;

end;

registration

let S be Language;
let D be RuleSet of S;

cluster D -expanded for set ;

existence

proof end;

end;

::############################################################################
::# Encoding of modified Gentzen rules

definition

let Seqts be set ;
let S be Language;
let seqt be S -null set ;

pred seqt Rule0 Seqts means :Def18: :: FOMODEL4:def 18
seqt `2 in seqt `1 ;

pred seqt Rule1 Seqts means :Def19: :: FOMODEL4:def 19
ex y being set st
( y in Seqts & y `1 c= seqt `1 & seqt `2 = y `2 );

pred seqt Rule2 Seqts means :Def20: :: FOMODEL4:def 20
( seqt `1 is empty & ex t being termal string of S st seqt `2 = (<*(TheEqSymbOf S)*> ^ t) ^ t );

pred seqt Rule3a Seqts means :Def21: :: FOMODEL4:def 21
ex t, t1, t2 being termal string of S ex x being set st
( x in Seqts & seqt `1 = (x `1) \/ {((<*(TheEqSymbOf S)*> ^ t1) ^ t2)} & x `2 = (<*(TheEqSymbOf S)*> ^ t) ^ t1 & seqt `2 = (<*(TheEqSymbOf S)*> ^ t) ^ t2 );

pred seqt Rule3b Seqts means :Def22: :: FOMODEL4:def 22
ex t1, t2 being termal string of S st
( seqt `1 = {((<*(TheEqSymbOf S)*> ^ t1) ^ t2)} & seqt `2 = (<*(TheEqSymbOf S)*> ^ t2) ^ t1 );

pred seqt Rule3d Seqts means :Def23: :: FOMODEL4:def 23
ex s being low-compounding Element of S ex T, U being abs (ar b₁) -element Element of (AllTermsOf S) * st
( s is operational & seqt `1 = { ((<*(TheEqSymbOf S)*> ^ (TT . j)) ^ (UU . j)) where j is Element of Seg (abs (ar s)), TT, UU is Function of (Seg (abs (ar s))),(((AllSymbolsOf S) *) \ {{}}) : ( TT = T & UU = U ) } & seqt `2 = (<*(TheEqSymbOf S)*> ^ (s -compound T)) ^ (s -compound U) );

pred seqt Rule3e Seqts means :Def24: :: FOMODEL4:def 24
ex s being relational Element of S ex T, U being abs (ar b₁) -element Element of (AllTermsOf S) * st
( seqt `1 = {(s -compound T)} \/ { ((<*(TheEqSymbOf S)*> ^ (TT . j)) ^ (UU . j)) where j is Element of Seg (abs (ar s)), TT, UU is Function of (Seg (abs (ar s))),(((AllSymbolsOf S) *) \ {{}}) : ( TT = T & UU = U ) } & seqt `2 = s -compound U );

pred seqt Rule4 Seqts means :Def25: :: FOMODEL4:def 25
ex l being literal Element of S ex phi being wff string of S ex t being termal string of S st
( seqt `1 = {((l,t) SubstIn phi)} & seqt `2 = <*l*> ^ phi );

pred seqt Rule5 Seqts means :Def26: :: FOMODEL4:def 26
ex v1, v2 being literal Element of S ex x being set ex p being FinSequence st
( seqt `1 = x \/ {(<*v1*> ^ p)} & v2 is (x \/ {p}) \/ {(seqt `2)} -absent & [(x \/ {((v1 SubstWith v2) . p)}),(seqt `2)] in Seqts );

pred seqt Rule6 Seqts means :Def27: :: FOMODEL4:def 27
ex y1, y2 being set ex phi1, phi2 being wff string of S st
( y1 in Seqts & y2 in Seqts & y1 `1 = y2 `1 & y2 `1 = seqt `1 & y1 `2 = (<*(TheNorSymbOf S)*> ^ phi1) ^ phi1 & y2 `2 = (<*(TheNorSymbOf S)*> ^ phi2) ^ phi2 & seqt `2 = (<*(TheNorSymbOf S)*> ^ phi1) ^ phi2 );

pred seqt Rule7 Seqts means :Def28: :: FOMODEL4:def 28
ex y being set ex phi1, phi2 being wff string of S st
( y in Seqts & y `1 = seqt `1 & y `2 = (<*(TheNorSymbOf S)*> ^ phi1) ^ phi2 & seqt `2 = (<*(TheNorSymbOf S)*> ^ phi2) ^ phi1 );

pred seqt Rule8 Seqts means :Def29: :: FOMODEL4:def 29
ex y1, y2 being set ex phi, phi1, phi2 being wff string of S st
( y1 in Seqts & y2 in Seqts & y1 `1 = y2 `1 & y1 `2 = phi1 & y2 `2 = (<*(TheNorSymbOf S)*> ^ phi1) ^ phi2 & {phi} \/ (seqt `1) = y1 `1 & seqt `2 = (<*(TheNorSymbOf S)*> ^ phi) ^ phi );

pred seqt Rule9 Seqts means :Def30: :: FOMODEL4:def 30
ex y being set ex phi being wff string of S st
( y in Seqts & seqt `2 = phi & y `1 = seqt `1 & y `2 = xnot (xnot phi) );

end;

:: deftheorem Def18 defines Rule0 FOMODEL4:def 18 :

:: deftheorem Def19 defines Rule1 FOMODEL4:def 19 :

:: deftheorem Def20 defines Rule2 FOMODEL4:def 20 :

:: deftheorem Def21 defines Rule3a FOMODEL4:def 21 :

:: deftheorem Def22 defines Rule3b FOMODEL4:def 22 :

:: deftheorem Def23 defines Rule3d FOMODEL4:def 23 :

:: deftheorem Def24 defines Rule3e FOMODEL4:def 24 :

:: deftheorem Def25 defines Rule4 FOMODEL4:def 25 :

:: deftheorem Def26 defines Rule5 FOMODEL4:def 26 :

:: deftheorem Def27 defines Rule6 FOMODEL4:def 27 :

:: deftheorem Def28 defines Rule7 FOMODEL4:def 28 :

:: deftheorem Def29 defines Rule8 FOMODEL4:def 29 :

:: deftheorem Def30 defines Rule9 FOMODEL4:def 30 :

definition

let S be Language;

func P#0 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def31: :: FOMODEL4:def 31
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule0 Seqts );

existence

proof end;

uniqueness

proof end;

func P#1 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def32: :: FOMODEL4:def 32
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule1 Seqts );

existence

proof end;

uniqueness

proof end;

func P#2 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def33: :: FOMODEL4:def 33
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule2 Seqts );

existence

proof end;

uniqueness

proof end;

func P#3a S -> Relation of (bool (S -sequents)),(S -sequents) means :Def34: :: FOMODEL4:def 34
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule3a Seqts );

existence

proof end;

uniqueness

proof end;

func P#3b S -> Relation of (bool (S -sequents)),(S -sequents) means :Def35: :: FOMODEL4:def 35
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule3b Seqts );

existence

proof end;

uniqueness

proof end;

func P#3d S -> Relation of (bool (S -sequents)),(S -sequents) means :Def36: :: FOMODEL4:def 36
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule3d Seqts );

existence

proof end;

uniqueness

proof end;

func P#3e S -> Relation of (bool (S -sequents)),(S -sequents) means :Def37: :: FOMODEL4:def 37
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule3e Seqts );

existence

proof end;

uniqueness

proof end;

func P#4 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def38: :: FOMODEL4:def 38
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule4 Seqts );

existence

proof end;

uniqueness

proof end;

func P#5 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def39: :: FOMODEL4:def 39
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule5 Seqts );

existence

proof end;

uniqueness

proof end;

func P#6 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def40: :: FOMODEL4:def 40
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule6 Seqts );

existence

proof end;

uniqueness

proof end;

func P#7 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def41: :: FOMODEL4:def 41
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule7 Seqts );

existence

proof end;

uniqueness

proof end;

func P#8 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def42: :: FOMODEL4:def 42
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule8 Seqts );

existence

proof end;

uniqueness

proof end;

func P#9 S -> Relation of (bool (S -sequents)),(S -sequents) means :Def43: :: FOMODEL4:def 43
for Seqts being Element of bool (S -sequents)
for seqt being Element of S -sequents holds
( [Seqts,seqt] in it iff seqt Rule9 Seqts );

existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def31 defines P#0 FOMODEL4:def 31 :

:: deftheorem Def32 defines P#1 FOMODEL4:def 32 :

:: deftheorem Def33 defines P#2 FOMODEL4:def 33 :

:: deftheorem Def34 defines P#3a FOMODEL4:def 34 :

:: deftheorem Def35 defines P#3b FOMODEL4:def 35 :

:: deftheorem Def36 defines P#3d FOMODEL4:def 36 :

:: deftheorem Def37 defines P#3e FOMODEL4:def 37 :

:: deftheorem Def38 defines P#4 FOMODEL4:def 38 :

:: deftheorem Def39 defines P#5 FOMODEL4:def 39 :

:: deftheorem Def40 defines P#6 FOMODEL4:def 40 :

:: deftheorem Def41 defines P#7 FOMODEL4:def 41 :

:: deftheorem Def42 defines P#8 FOMODEL4:def 42 :

:: deftheorem Def43 defines P#9 FOMODEL4:def 43 :

definition

let S be Language;
let R be Relation of (bool (S -sequents)),(S -sequents);

func FuncRule R -> Rule of S means :Def44: :: FOMODEL4:def 44
for inseqs being set st inseqs in bool (S -sequents) holds
it . inseqs = { x where x is Element of S -sequents : [inseqs,x] in R } ;

existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def44 defines FuncRule FOMODEL4:def 44 :

Lm26: for S being Language
for Seqts being Subset of (S -sequents)
for seqt being Element of S -sequents
for R being Relation of (bool (S -sequents)),(S -sequents) st [Seqts,seqt] in R holds
seqt in (FuncRule R) . Seqts

proof end;

Lm27: for S being Language
for SQ being b₁ -sequents-like set
for Sq being b₁ -sequent-like set
for R being Relation of (bool (S -sequents)),(S -sequents) st [SQ,Sq] in R holds
Sq is 1,SQ,{(FuncRule R)} -derivable

proof end;

Lm28: for y being set
for S being Language
for SQ being b₂ -sequents-like set
for R being Relation of (bool (S -sequents)),(S -sequents) holds
( y in (FuncRule R) . SQ iff ( y in S -sequents & [SQ,y] in R ) )

proof end;

Lm29: for y, X being set
for S being Language
for R being Relation of (bool (S -sequents)),(S -sequents) holds
( y in (FuncRule R) . X iff ( y in S -sequents & [X,y] in R ) )

proof end;

definition

let S be Language;

func R#0 S -> Rule of S equals :: FOMODEL4:def 45
FuncRule (P#0 S);

coherence ;

func R#1 S -> Rule of S equals :: FOMODEL4:def 46
FuncRule (P#1 S);

coherence ;

func R#2 S -> Rule of S equals :: FOMODEL4:def 47
FuncRule (P#2 S);

coherence ;

func R#3a S -> Rule of S equals :: FOMODEL4:def 48
FuncRule (P#3a S);

coherence ;

func R#3b S -> Rule of S equals :: FOMODEL4:def 49
FuncRule (P#3b S);

coherence ;

func R#3d S -> Rule of S equals :: FOMODEL4:def 50
FuncRule (P#3d S);

coherence ;

func R#3e S -> Rule of S equals :: FOMODEL4:def 51
FuncRule (P#3e S);

coherence ;

func R#4 S -> Rule of S equals :: FOMODEL4:def 52
FuncRule (P#4 S);

coherence ;

func R#5 S -> Rule of S equals :: FOMODEL4:def 53
FuncRule (P#5 S);

coherence ;

func R#6 S -> Rule of S equals :: FOMODEL4:def 54
FuncRule (P#6 S);

coherence ;

func R#7 S -> Rule of S equals :: FOMODEL4:def 55
FuncRule (P#7 S);

coherence ;

func R#8 S -> Rule of S equals :: FOMODEL4:def 56
FuncRule (P#8 S);

coherence ;

func R#9 S -> Rule of S equals :: FOMODEL4:def 57
FuncRule (P#9 S);

coherence ;

end;

:: deftheorem defines R#0 FOMODEL4:def 45 :

:: deftheorem defines R#1 FOMODEL4:def 46 :

:: deftheorem defines R#2 FOMODEL4:def 47 :

:: deftheorem defines R#3a FOMODEL4:def 48 :

:: deftheorem defines R#3b FOMODEL4:def 49 :

:: deftheorem defines R#3d FOMODEL4:def 50 :

:: deftheorem defines R#3e FOMODEL4:def 51 :

:: deftheorem defines R#4 FOMODEL4:def 52 :

:: deftheorem defines R#5 FOMODEL4:def 53 :

:: deftheorem defines R#6 FOMODEL4:def 54 :

:: deftheorem defines R#7 FOMODEL4:def 55 :

:: deftheorem defines R#8 FOMODEL4:def 56 :

:: deftheorem defines R#9 FOMODEL4:def 57 :

registration

let S be Language;
let t be termal string of S;

cluster {[{},((<*(TheEqSymbOf S)*> ^ t) ^ t)]} -> {(R#2 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster R#2 S -> isotone for Rule of S;

coherence

proof end;

end;

Lm30: for X being set
for S being Language
for D being RuleSet of S st {(R#2 S)} c= D holds
(X,D) -termEq is total

proof end;

registration

let S be Language;

cluster R#3b S -> isotone for Rule of S;

coherence

proof end;

end;

Lm31: for X being set
for S being Language
for D being RuleSet of S st {(R#3b S)} c= D & X is D -expanded holds
(X,D) -termEq is symmetric

proof end;

registration

let S be Language;
let t, t1, t2 be termal string of S;
let premises be finite Subset of (AllFormulasOf S);

cluster [(premises \/ {((<*(TheEqSymbOf S)*> ^ t1) ^ t2)}),((<*(TheEqSymbOf S)*> ^ t) ^ t2)] -> 1,{[premises,((<*(TheEqSymbOf S)*> ^ t) ^ t1)]},{(R#3a S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let t, t1, t2 be termal string of S;
let phi be wff string of S;

cluster [{phi,((<*(TheEqSymbOf S)*> ^ t1) ^ t2)},((<*(TheEqSymbOf S)*> ^ t) ^ t2)] -> 1,{[{phi},((<*(TheEqSymbOf S)*> ^ t) ^ t1)]},{(R#3a S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi be wff string of S;
let Phi be finite Subset of (AllFormulasOf S);

cluster [(Phi \/ {phi}),phi] -> 1, {} ,{(R#0 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;

cluster [{phi1,phi2},phi1] -> 1, {} ,{(R#0 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi be wff string of S;

cluster [{phi},phi] -> 1, {} ,{(R#0 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi be wff string of S;

cluster {[{phi},phi]} -> {} ,{(R#0 S)} -derivable for set ;

coherence by Lm12;

end;

registration

let S be Language;

cluster R#0 S -> isotone for Rule of S;

coherence

proof end;

cluster R#3a S -> isotone for Rule of S;

coherence

proof end;

cluster R#3d S -> isotone for Rule of S;

coherence

proof end;

cluster R#3e S -> isotone for Rule of S;

coherence

proof end;

let K1, K2 be isotone RuleSet of S;

cluster K1 \/ K2 -> isotone for RuleSet of S;

coherence

proof end;

end;

Lm32: for X being set
for S being Language
for D being RuleSet of S st {(R#0 S)} \/ {(R#3a S)} c= D & X is D -expanded holds
(X,D) -termEq is transitive

proof end;

Lm33: for X being set
for S being Language
for D being RuleSet of S st {(R#0 S),(R#3a S)} c= D & {(R#2 S),(R#3b S)} c= D & X is D -expanded holds
(X,D) -termEq is Equivalence_Relation of (AllTermsOf S)

proof end;

registration

let S be Language;
let t1, t2 be termal string of S;

cluster (<*(TheEqSymbOf S)*> ^ t1) ^ t2 -> 0 -wff for string of S;

coherence by Lm2;

end;

definition

let S be Language;
let m be non zero Nat;
let T, U be m -element Element of (AllTermsOf S) * ;

func PairWiseEq (T,U) -> set equals :: FOMODEL4:def 58
{ ((<*(TheEqSymbOf S)*> ^ (TT . j)) ^ (UU . j)) where j is Element of Seg m, TT, UU is Function of (Seg m),(((AllSymbolsOf S) *) \ {{}}) : ( TT = T & UU = U ) } ;

coherence ;

end;

:: deftheorem defines PairWiseEq FOMODEL4:def 58 :

definition

let S be Language;
let m be non zero Nat;
let T1, T2 be m -element Element of (AllTermsOf S) * ;
:: original: PairWiseEq
redefine func PairWiseEq (T1,T2) -> Subset of (AllFormulasOf S);
coherence

proof end;

end;

registration

let S be Language;
let m be non zero Nat;
let T, U be m -element Element of (AllTermsOf S) * ;

cluster PairWiseEq (T,U) -> finite ;

coherence

proof end;

end;

Lm34: for S being Language
for s being low-compounding Element of S
for T, U being abs (ar b₂) -element Element of (AllTermsOf S) * st s is termal holds
{[(PairWiseEq (T,U)),((<*(TheEqSymbOf S)*> ^ (s -compound T)) ^ (s -compound U))]} is {} ,{(R#3d S)} -derivable

proof end;

Lm35: for S being Language
for s being relational Element of S
for T1, T2 being abs (ar b₂) -element Element of (AllTermsOf S) * holds {[((PairWiseEq (T1,T2)) \/ {(s -compound T1)}),(s -compound T2)]} is {} ,{(R#3e S)} -derivable

proof end;

registration

let S be Language;
let s be relational Element of S;
let T1, T2 be abs (ar s) -element Element of (AllTermsOf S) * ;

cluster {[((PairWiseEq (T1,T2)) \/ {(s -compound T1)}),(s -compound T2)]} -> {} ,{(R#3e S)} -derivable ;

coherence by Lm35;

end;

Lm36: for X, x1, x2 being set
for S being Language
for D being RuleSet of S
for s being low-compounding Element of S st X is D -expanded & [x1,x2] in (abs (ar s)) -placesOf ((X,D) -termEq) holds
ex T, U being abs (ar b₆) -element Element of (AllTermsOf S) * st
( T = x1 & U = x2 & PairWiseEq (T,U) c= X )

proof end;

Lm37: for X being set
for S being Language
for D being RuleSet of S
for s being low-compounding Element of S st {(R#3d S)} c= D & X is D -expanded & s is termal holds
X -freeInterpreter s is (X,D) -termEq -respecting

proof end;

Lm38: for X, x1, x2 being set
for S being Language
for r being relational Element of S
for D being RuleSet of S st {(R#3e S)} c= D & X is D -expanded & [x1,x2] in (abs (ar r)) -placesOf ((X,D) -termEq) & (r -compound) . x1 in X holds
(r -compound) . x2 in X

proof end;

Lm39: for X, x1, x2 being set
for S being Language
for r being relational Element of S
for D being RuleSet of S st {(R#2 S)} /\ D = {(R#2 S)} & {(R#3b S)} /\ D = {(R#3b S)} & D /\ {(R#3e S)} = {(R#3e S)} & X is D -expanded & [x1,x2] in (abs (ar r)) -placesOf ((X,D) -termEq) holds
( (r -compound) . x1 in X iff (r -compound) . x2 in X )

proof end;

Lm40: for U being non empty set
for Y being set
for x, y being Element of U holds
not ( ( x in Y implies y in Y ) & ( y in Y implies x in Y ) & not [((chi (Y,U)) . x),((chi (Y,U)) . y)] in id BOOLEAN )

proof end;

Lm41: for X being set
for S being Language
for r being relational Element of S
for D being RuleSet of S st {(R#2 S)} /\ D = {(R#2 S)} & {(R#3b S)} /\ D = {(R#3b S)} & D /\ {(R#3e S)} = {(R#3e S)} & X is D -expanded holds
X -freeInterpreter r is (X,D) -termEq -respecting

proof end;

Lm42: for U being non empty set
for X, x being set
for R being total reflexive Relation of U
for f being Function of X,U st x in X holds
f is {[x,x]},R -respecting

proof end;

Lm43: for U being non empty set
for S being Language
for l being literal Element of S
for E being total reflexive Relation of U
for f being Interpreter of l,U holds f is E -respecting

proof end;

Lm44: for X being set
for S being Language
for l being literal Element of S
for D being RuleSet of S st {(R#0 S),(R#3a S)} c= D & {(R#2 S),(R#3b S)} c= D & X is D -expanded holds
X -freeInterpreter l is (X,D) -termEq -respecting

proof end;

Lm45: for X being set
for S being Language
for a being ofAtomicFormula Element of S
for D being RuleSet of S st {(R#0 S),(R#3a S)} c= D & D /\ {(R#3d S)} = {(R#3d S)} & {(R#2 S)} /\ D = {(R#2 S)} & {(R#3b S)} /\ D = {(R#3b S)} & D /\ {(R#3e S)} = {(R#3e S)} & X is D -expanded holds
X -freeInterpreter a is (X,D) -termEq -respecting

proof end;

definition

let m be Nat;
let S be Language;
let D be RuleSet of S;

attr D is m -ranked means :Def59: :: FOMODEL4:def 59
( R#0 S in D & R#2 S in D & R#3a S in D & R#3b S in D ) if m = 0
( R#0 S in D & R#2 S in D & R#3a S in D & R#3b S in D & R#3d S in D & R#3e S in D ) if m = 1
( R#0 S in D & R#1 S in D & R#2 S in D & R#3a S in D & R#3b S in D & R#3d S in D & R#3e S in D & R#4 S in D & R#5 S in D & R#6 S in D & R#7 S in D & R#8 S in D ) if m = 2
otherwise D = {} ;

consistency ;

end;

:: deftheorem Def59 defines -ranked FOMODEL4:def 59 :

registration

let S be Language;

cluster 1 -ranked -> 0 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

coherence

proof end;

cluster 2 -ranked -> 1 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

coherence

proof end;

end;

definition

let S be Language;

func S -rules -> RuleSet of S equals :: FOMODEL4:def 60
{(R#0 S),(R#1 S),(R#2 S),(R#3a S),(R#3b S),(R#3d S),(R#3e S),(R#4 S)} \/ {(R#5 S),(R#6 S),(R#7 S),(R#8 S)};

coherence ;

end;

:: deftheorem defines -rules FOMODEL4:def 60 :

registration

let S be Language;

cluster S -rules -> 2 -ranked for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster functional 2 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

registration

let S be Language;

cluster functional 1 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

registration

let S be Language;

cluster functional 0 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

Lm46: for X being set
for S being Language
for a being ofAtomicFormula Element of S
for D being RuleSet of S st D is 1 -ranked & X is D -expanded holds
X -freeInterpreter a is (X,D) -termEq -respecting

proof end;

registration

let S be Language;
let D be 1 -ranked RuleSet of S;
let X be D -expanded set ;
let a be ofAtomicFormula Element of S;

cluster X -freeInterpreter a -> (X,D) -termEq -respecting for Interpreter of a, AllTermsOf S;

coherence by Lm46;

end;

Lm47: for X being set
for S being Language
for D being RuleSet of S st D is 0 -ranked & X is D -expanded holds
(X,D) -termEq is Equivalence_Relation of (AllTermsOf S)

proof end;

registration

let S be Language;
let D be 0 -ranked RuleSet of S;
let X be D -expanded set ;

cluster (X,D) -termEq -> total symmetric transitive for Relation of (AllTermsOf S);

coherence by Lm47;

end;

registration

let S be Language;

cluster functional 0 -ranked 1 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

theorem :: FOMODEL4:1

for Y, X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D2 is isotone or D1 is isotone ) & Y is X,D1 -derivable holds
Y is X,D2 -derivable by Lm18;

registration

let S be Language;
let Sq be S -sequent-like set ;

cluster {Sq} -> S -sequents-like ;

coherence

proof end;

end;

registration

let S be Language;
let SQ1, SQ2 be S -sequents-like set ;

cluster SQ1 \/ SQ2 -> S -sequents-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let x, y be S -sequent-like set ;

cluster {x,y} -> S -sequents-like for set ;

coherence

proof end;

end;

Lm48: for m, n being Nat
for x, y, z being set
for S being Language
for D1, D2, D3 being RuleSet of S
for SQ1, SQ2 being b₆ -sequents-like set st D1 \/ D2 is isotone & (D1 \/ D2) \/ D3 is isotone & x is m,SQ1,D1 -derivable & y is m,SQ2,D2 -derivable & z is n,{x,y},D3 -derivable holds
z is m + n,SQ1 \/ SQ2,(D1 \/ D2) \/ D3 -derivable

proof end;

Lm49: for x, X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D1 is isotone or D2 is isotone ) & x is X,D1 -provable holds
x is X,D2 -provable

proof end;

Lm50: for x, X being set
for S being Language
for R being Rule of S st x in R . X holds
x is 1,X,{R} -derivable

proof end;

registration

let S be Language;
let phi1, phi2 be wff string of S;

cluster [{(xnot phi1),(xnot phi2)},((<*(TheNorSymbOf S)*> ^ phi1) ^ phi2)] -> 1,{[{(xnot phi1),(xnot phi2)},(xnot phi1)],[{(xnot phi1),(xnot phi2)},(xnot phi2)]},{(R#6 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;

cluster [{phi1,phi2},phi2] -> 1, {} ,{(R#0 S)} -derivable for set ;

coherence

proof end;

end;

theorem Th2: :: FOMODEL4:2

for S being Language
for SQ being b₁ -sequents-like set
for Sq being b₁ -sequent-like set
for R being Relation of (bool (S -sequents)),(S -sequents) st [SQ,Sq] in R holds
Sq in (FuncRule R) . SQ

proof end;

theorem :: FOMODEL4:3

for x, X being set
for S being Language
for R being Rule of S st x in R . X holds
x is 1,X,{R} -derivable by Lm50;

definition

let S be Language;
let D be RuleSet of S;
let X be set ;

redefine attr X is D -expanded means :Def61: :: FOMODEL4:def 61
for x being set st x is X,D -provable holds
x in X;

compatibility

proof end;

end;

:: deftheorem Def61 defines -expanded FOMODEL4:def 61 :

theorem Th4: :: FOMODEL4:4

for X being set
for S being Language
for phi being wff string of S st phi in X holds
phi is X,{(R#0 S)} -provable

proof end;

theorem :: FOMODEL4:5

for m, n being Nat
for x, y, z being set
for S being Language
for D1, D2, D3 being RuleSet of S
for SQ1, SQ2 being b₆ -sequents-like set st D1 \/ D2 is isotone & (D1 \/ D2) \/ D3 is isotone & x is m,SQ1,D1 -derivable & y is m,SQ2,D2 -derivable & z is n,{x,y},D3 -derivable holds
z is m + n,SQ1 \/ SQ2,(D1 \/ D2) \/ D3 -derivable by Lm48;

theorem :: FOMODEL4:6

for m, n being Nat
for y, X, z being set
for S being Language
for D1, D2 being RuleSet of S st D1 is isotone & D1 \/ D2 is isotone & y is m,X,D1 -derivable & z is n,{y},D2 -derivable holds
z is m + n,X,D1 \/ D2 -derivable by Lm21;

theorem :: FOMODEL4:7

for m being Nat
for x, X being set
for S being Language
for D being RuleSet of S st x is m,X,D -derivable holds
{x} is X,D -derivable by Lm12;

registration

let S be Language;

cluster R#6 S -> isotone for Rule of S;

coherence

proof end;

end;

theorem :: FOMODEL4:8

for x, X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D1 is isotone or D2 is isotone ) & x is X,D1 -provable holds
x is X,D2 -provable by Lm49;

theorem :: FOMODEL4:9

for X, Y, x being set
for S being Language
for D being RuleSet of S st X c= Y & x is X,D -provable holds
x is Y,D -provable ;

registration

let S be Language;

cluster R#8 S -> isotone for Rule of S;

coherence

proof end;

end;

registration

let S be Language;

cluster R#1 S -> isotone for Rule of S;

coherence

proof end;

end;

theorem :: FOMODEL4:10

for y being set
for S being Language
for D being RuleSet of S
for SQ being b₂ -sequents-like set st {y} is SQ,D -derivable holds
ex mm being Element of NAT st y is mm,SQ,D -derivable

proof end;

registration

let S be Language;
let D be RuleSet of S;
let X be set ;

cluster X,D -derivable -> S -sequents-like for set ;

coherence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;
let X, x be set ;

redefine attr x is X,D -provable means :Def62: :: FOMODEL4:def 62
ex H being set ex m being Nat st
( H c= X & [H,x] is m, {} ,D -derivable );

compatibility

proof end;

end;

:: deftheorem Def62 defines -provable FOMODEL4:def 62 :

theorem Th11: :: FOMODEL4:11

for m being Nat
for x, X being set
for S being Language
for D1, D2 being RuleSet of S st D1 c= D2 & ( D2 is isotone or D1 is isotone ) & x is m,X,D1 -derivable holds
x is m,X,D2 -derivable

proof end;

registration

let S be Language;

cluster R#7 S -> isotone for Rule of S;

coherence

proof end;

end;

theorem :: FOMODEL4:12

for x, X being set
for S being Language
for D being RuleSet of S st x is X,D -provable holds
x is wff string of S by Lm24;

registration

let S be Language;
let D1 be 0 -ranked 1 -ranked RuleSet of S;
let X be D1 -expanded set ;

cluster (S,X) -freeInterpreter -> S, AllTermsOf S -interpreter-like (X,D1) -termEq -respecting for S, AllTermsOf S -interpreter-like Function;

coherence

proof end;

end;

definition

let S be Language;
let D be 0 -ranked RuleSet of S;
let X be D -expanded set ;

func D Henkin X -> Function equals :: FOMODEL4:def 63
((S,X) -freeInterpreter) quotient ((X,D) -termEq);

coherence ;

end;

:: deftheorem defines Henkin FOMODEL4:def 63 :

registration

let S be Language;
let D be 0 -ranked RuleSet of S;
let X be D -expanded set ;

cluster D Henkin X -> OwnSymbolsOf S -defined ;

coherence ;

end;

registration

let S be Language;
let D1 be 0 -ranked 1 -ranked RuleSet of S;
let X be D1 -expanded set ;

cluster D1 Henkin X -> S, Class ((X,D1) -termEq) -interpreter-like for Function;

coherence ;

end;

definition

let S be Language;
let D1 be 0 -ranked 1 -ranked RuleSet of S;
let X be D1 -expanded set ;
:: original: Henkin
redefine func D1 Henkin X -> Element of (Class ((X,D1) -termEq)) -InterpretersOf S;
coherence

proof end;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;

cluster (<*(TheNorSymbOf S)*> ^ phi1) ^ phi2 -> {(xnot phi1),(xnot phi2)},{(R#0 S)} \/ {(R#6 S)} -provable for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster 0 -ranked -> non empty 0 -ranked for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

coherence by Def59;

end;

definition

let S be Language;
let x be set ;

attr x is S -premises-like means :Def64: :: FOMODEL4:def 64
( x c= AllFormulasOf S & x is finite );

end;

:: deftheorem Def64 defines -premises-like FOMODEL4:def 64 :

registration

let S be Language;

cluster S -premises-like -> finite for set ;

coherence by Def64;

end;

registration

let S be Language;
let phi be wff string of S;

cluster {phi} -> S -premises-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let e be empty set ;

cluster e null S -> S -premises-like for set ;

coherence

proof end;

end;

registration

let X be set ;
let S be Language;

cluster S -premises-like for Element of bool X;

existence

proof end;

end;

registration

let S be Language;

cluster S -premises-like for set ;

existence

proof end;

end;

registration

let S be Language;
let X be S -premises-like set ;

cluster -> S -premises-like for Element of bool X;

coherence

proof end;

end;

definition

let S be Language;
let H2, H1 be S -premises-like set ;
:: original: null
redefine func H1 null H2 -> Subset of (AllFormulasOf S);
coherence by Def64;

end;

registration

let S be Language;
let H be S -premises-like set ;
let x be set ;

cluster H null x -> S -premises-like ;

coherence ;

end;

registration

let S be Language;
let H1, H2 be S -premises-like set ;

cluster H1 \/ H2 -> S -premises-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi be wff string of S;

cluster [H,phi] -> S -sequent-like ;

coherence

proof end;

end;

registration

let S be Language;
let H1, H2 be S -premises-like set ;
let phi be wff string of S;

cluster [(H1 \/ H2),phi] -> 1,{[H1,phi]},{(R#1 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi, phi1, phi2 be wff string of S;

cluster [(H null (phi1 ^ phi2)),(xnot phi)] -> 1,{[(H \/ {phi}),phi1],[(H \/ {phi}),((<*(TheNorSymbOf S)*> ^ phi1) ^ phi2)]},{(R#8 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster {} null S -> S -sequents-like for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi be wff string of S;

cluster [(H \/ {phi}),phi] -> 1, {} ,{(R#0 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi1, phi2 be wff string of S;

cluster [(H null phi2),(xnot phi1)] -> 2,{[H,((<*(TheNorSymbOf S)*> ^ phi1) ^ phi2)]},({(R#0 S)} \/ {(R#1 S)}) \/ {(R#8 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi1, phi2 be wff string of S;

cluster [H,((<*(TheNorSymbOf S)*> ^ phi2) ^ phi1)] -> 1,{[H,((<*(TheNorSymbOf S)*> ^ phi1) ^ phi2)]},{(R#7 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi1, phi2 be wff string of S;

cluster [(H null phi1),(xnot phi2)] -> 3,{[H,((<*(TheNorSymbOf S)*> ^ phi1) ^ phi2)]},(({(R#0 S)} \/ {(R#1 S)}) \/ {(R#8 S)}) \/ {(R#7 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;
let Sq be S -sequent-like set ;

cluster Sq `1 -> S -premises-like for set ;

coherence

proof end;

end;

definition

let S be Language;
let X be set ;
let D be RuleSet of S;
:: original: null
redefine func D null X -> RuleSet of S;
coherence ;

end;

registration

let S be Language;
let phi1, phi2 be wff string of S;
let l1 be literal Element of S;
let H be S -premises-like set ;
let l2 be literal (H \/ {phi1}) \/ {phi2} -absent Element of S;

cluster [((H \/ {(<*l1*> ^ phi1)}) null l2),phi2] -> 1,{[(H \/ {((l1,l2) -SymbolSubstIn phi1)}),phi2]},{(R#5 S)} -derivable for set ;

coherence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;
let X be set ;

attr X is D -inconsistent means :Def65: :: FOMODEL4:def 65
ex phi1, phi2 being wff string of S st
( phi1 is X,D -provable & (<*(TheNorSymbOf S)*> ^ phi1) ^ phi2 is X,D -provable );

end;

:: deftheorem Def65 defines -inconsistent FOMODEL4:def 65 :

registration

let m1 be non zero Nat;
let S be Language;
let H1, H2 be S -premises-like set ;
let phi be wff string of S;

cluster [((H1 \/ H2) null m1),phi] -> m1,{[H1,phi]},{(R#1 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster non empty functional isotone for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

theorem Th13: :: FOMODEL4:13

for X being set
for S being Language
for phi being wff string of S
for D being RuleSet of S st X is D -inconsistent & D is isotone & R#1 S in D & R#8 S in D holds
xnot phi is X,D -provable

proof end;

registration

let S be Language;

cluster R#5 S -> isotone for Rule of S;

coherence

proof end;

end;

registration

let S be Language;
let l be literal Element of S;
let t be termal string of S;
let phi be wff string of S;

cluster [{((l,t) SubstIn phi)},(<*l*> ^ phi)] -> 1, {} ,{(R#4 S)} -derivable for set ;

coherence

proof end;

end;

registration

let S be Language;

cluster R#4 S -> isotone for Rule of S;

coherence

proof end;

end;

Lm51: for S being Language
for D1 being 0 -ranked 1 -ranked RuleSet of S
for X being b₂ -expanded set
for phi being 0wff string of S holds
( (D1 Henkin X) -AtomicEval phi = 1 iff phi in X )

proof end;

definition

let S be Language;
let X be set ;

attr X is S -witnessed means :Def66: :: FOMODEL4:def 66
for l1 being literal Element of S
for phi1 being wff string of S st <*l1*> ^ phi1 in X holds
ex l2 being literal Element of S st
( (l1,l2) -SymbolSubstIn phi1 in X & not l2 in rng phi1 );

end;

:: deftheorem Def66 defines -witnessed FOMODEL4:def 66 :

theorem Th14: :: FOMODEL4:14

for S being Language
for psi being wff string of S
for D1 being 0 -ranked 1 -ranked RuleSet of S
for X being b₃ -expanded set st R#1 S in D1 & R#4 S in D1 & R#6 S in D1 & R#7 S in D1 & R#8 S in D1 & X is S -mincover & X is S -witnessed holds
( (D1 Henkin X) -TruthEval psi = 1 iff psi in X )

proof end;

notation

let S be Language;
let D be RuleSet of S;
let X be set ;
antonym D -consistent X for D -inconsistent ;

end;

theorem Th15: :: FOMODEL4:15

for Y being set
for S being Language
for D being RuleSet of S
for X being Subset of Y st X is D -inconsistent holds
Y is D -inconsistent

proof end;

definition

let S be Language;
let D be RuleSet of S;
let X be functional set ;
let phi be Element of ExFormulasOf S;

func (D,phi) AddAsWitnessTo X -> set equals :Def67: :: FOMODEL4:def 67
X \/ {((((S -firstChar) . phi), the Element of (LettersOf S) \ (SymbolsOf ((((AllSymbolsOf S) *) \ {{}}) /\ (X \/ {(head phi)})))) -SymbolSubstIn (head phi))} if ( X \/ {phi} is D -consistent & (LettersOf S) \ (SymbolsOf ((((AllSymbolsOf S) *) \ {{}}) /\ (X \/ {(head phi)}))) <> {} )
otherwise X;

consistency ;
coherence ;

end;

:: deftheorem Def67 defines AddAsWitnessTo FOMODEL4:def 67 :

registration

let S be Language;
let D be RuleSet of S;
let X be functional set ;
let phi be Element of ExFormulasOf S;

cluster X \ ((D,phi) AddAsWitnessTo X) -> empty for set ;

coherence

proof end;

end;

registration

let S be Language;
let D be RuleSet of S;
let X be functional set ;
let phi be Element of ExFormulasOf S;

cluster ((D,phi) AddAsWitnessTo X) \ X -> trivial for set ;

coherence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;
let X be functional set ;
let phi be Element of ExFormulasOf S;
:: original: AddAsWitnessTo
redefine func (D,phi) AddAsWitnessTo X -> Subset of (X \/ (AllFormulasOf S));
coherence

proof end;

end;

definition

let S be Language;
let D be RuleSet of S;

attr D is Correct means :Def68: :: FOMODEL4:def 68
for phi being wff string of S
for X being set st phi is X,D -provable holds
for U being non empty set
for I being Element of U -InterpretersOf S st X is I -satisfied holds
I -TruthEval phi = 1;

end;

:: deftheorem Def68 defines Correct FOMODEL4:def 68 :

Lm52: for X being set
for S being Language
for phi being wff string of S
for D being RuleSet of S st D is isotone & R#1 S in D & R#8 S in D & X \/ {phi} is D -inconsistent holds
xnot phi is X,D -provable

proof end;

Lm53: for X being set
for S being Language
for D being RuleSet of S holds
( X is D -consistent iff for Y being finite Subset of X holds Y is D -consistent )

proof end;

Lm54: for X being set
for S being Language
for D being RuleSet of S st R#0 S in D & X is S -covering & X is D -consistent holds
( X is S -mincover & X is D -expanded )

proof end;

Lm55: for X being set
for S being Language
for phi being wff string of S
for D being RuleSet of S st D is isotone & R#1 S in D & R#8 S in D & phi is X,D -provable & X is D -consistent holds
X \/ {phi} is D -consistent

proof end;

Lm56: for U being non empty set
for X being set
for S being Language
for D being RuleSet of S
for I being Element of U -InterpretersOf S st D is Correct & X is I -satisfied holds
X is D -consistent

proof end;

registration

let S be Language;
let t1, t2 be termal string of S;

cluster (SubTerms ((<*(TheEqSymbOf S)*> ^ t1) ^ t2)) \+\ <*t1,t2*> -> empty for set ;

coherence

proof end;

end;

Lm57: for U being non empty set
for S being Language
for t1, t2 being termal string of S
for I being b₂,b₁ -interpreter-like Function holds
( I -AtomicEval ((<*(TheEqSymbOf S)*> ^ t1) ^ t2) = 1 iff (I -TermEval) . t1 = (I -TermEval) . t2 )

proof end;

definition

let S be Language;
let R be Rule of S;

attr R is Correct means :Def69: :: FOMODEL4:def 69
for X being set st X is S -correct holds
R . X is S -correct ;

end;

:: deftheorem Def69 defines Correct FOMODEL4:def 69 :

registration

let S be Language;

cluster S -sequent-like -> S -null for set ;

coherence ;

end;

Lm58: for S being Language holds R#0 S is Correct

proof end;

registration

let S be Language;

cluster R#0 S -> Correct for Rule of S;

coherence by Lm58;

end;

registration

let S be Language;

cluster Relation-like bool (S -sequents) -defined bool (S -sequents) -valued Function-like total quasi_total Correct for Element of Funcs ((bool (S -sequents)),(bool (S -sequents)));

existence

proof end;

end;

Lm59: for S being Language holds R#1 S is Correct

proof end;

registration

let S be Language;

cluster R#1 S -> Correct for Rule of S;

coherence by Lm59;

end;

Lm60: for S being Language holds R#2 S is Correct

proof end;

registration

let S be Language;

cluster R#2 S -> Correct for Rule of S;

coherence by Lm60;

end;

Lm61: for S being Language holds R#3a S is Correct

proof end;

registration

let S be Language;

cluster R#3a S -> Correct for Rule of S;

coherence by Lm61;

end;

Lm62: for S being Language holds R#3b S is Correct

proof end;

registration

let S be Language;

cluster R#3b S -> Correct for Rule of S;

coherence by Lm62;

end;

Lm63: for S being Language holds R#3d S is Correct

proof end;

registration

let S be Language;

cluster R#3d S -> Correct for Rule of S;

coherence by Lm63;

end;

Lm64: for S being Language holds R#3e S is Correct

proof end;

registration

let S be Language;

cluster R#3e S -> Correct for Rule of S;

coherence by Lm64;

end;

Lm65: for S being Language holds R#4 S is Correct

proof end;

registration

let S be Language;

cluster R#4 S -> Correct for Rule of S;

coherence by Lm65;

end;

Lm66: for S being Language holds R#5 S is Correct

proof end;

registration

let S be Language;

cluster R#5 S -> Correct for Rule of S;

coherence by Lm66;

end;

Lm67: for S being Language holds R#6 S is Correct

proof end;

registration

let S be Language;

cluster R#6 S -> Correct for Rule of S;

coherence by Lm67;

end;

Lm68: for S being Language holds R#7 S is Correct

proof end;

registration

let S be Language;

cluster R#7 S -> Correct for Rule of S;

coherence by Lm68;

end;

Lm69: for S being Language holds R#8 S is Correct

proof end;

registration

let S be Language;

cluster R#8 S -> Correct for Rule of S;

coherence by Lm69;

end;

theorem Th16: :: FOMODEL4:16

for S being Language
for D being RuleSet of S st ( for R being Rule of S st R in D holds
R is Correct ) holds
D is Correct

proof end;

registration

let S be Language;
let R be Correct Rule of S;

cluster {R} -> Correct for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster S -rules -> Correct for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster R#9 S -> isotone for Rule of S;

coherence

proof end;

end;

registration

let S be Language;
let H be S -premises-like set ;
let phi be wff string of S;

cluster [H,phi] null 1 -> 1,{[H,(xnot (xnot phi))]},{(R#9 S)} -derivable for set ;

coherence

proof end;

end;

registration

let X be set ;
let S be Language;

cluster non empty Relation-like NAT -defined AtomicFormulaSymbolsOf S -valued Function-like finite FinSequence-like FinSubsequence-like countable V209() 0wff 0 -wff wff X -implied for Element of ((AllSymbolsOf S) *) \ {{}};

existence

proof end;

end;

registration

let X be set ;
let S be Language;

cluster non empty Relation-like NAT -defined Function-like finite FinSequence-like FinSubsequence-like countable V209() wff X -implied for Element of ((AllSymbolsOf S) *) \ {{}};

existence

proof end;

end;

registration

let S be Language;
let X be set ;
let phi be wff X -implied string of S;

cluster xnot (xnot phi) -> wff X -implied for wff string of S;

coherence

proof end;

end;

definition

let X be set ;
let S be Language;
let phi be wff string of S;

attr phi is X -provable means :Def70: :: FOMODEL4:def 70
phi is X,{(R#9 S)} \/ (S -rules) -provable ;

end;

:: deftheorem Def70 defines -provable FOMODEL4:def 70 :

begin

::# constructions for countable languages
::# witness adjoining

definition

let X be functional set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(ExFormulasOf S);
set SS = AllSymbolsOf S;
set EF = ExFormulasOf S;
set FF = AllFormulasOf S;
set Y = X \/ (AllFormulasOf S);
set DD = bool (X \/ (AllFormulasOf S));

func (D,num) AddWitnessesTo X -> Function of NAT,(bool (X \/ (AllFormulasOf S))) means :Def71: :: FOMODEL4:def 71
( it . 0 = X & ( for mm being Element of NAT holds it . (mm + 1) = (D,(num . mm)) AddAsWitnessTo (it . mm) ) );

existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def71 defines AddWitnessesTo FOMODEL4:def 71 :

notation

let X be functional set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(ExFormulasOf S);
synonym (D,num) addw X for (D,num) AddWitnessesTo X;

end;

Lm70: for X being set
for S being Language
for phi being wff string of S
for l1, l2 being literal Element of S
for D being RuleSet of S st D is isotone & R#1 S in D & R#8 S in D & R#2 S in D & R#5 S in D & X \/ {((l1,l2) -SymbolSubstIn phi)} is D -inconsistent & l2 is X \/ {phi} -absent holds
X \/ {(<*l1*> ^ phi)} is D -inconsistent

proof end;

theorem Th17: :: FOMODEL4:17

for k, m being Nat
for S being Language
for D being RuleSet of S
for X being functional set
for num being Function of NAT,(ExFormulasOf S) st D is isotone & R#1 S in D & R#8 S in D & R#2 S in D & R#5 S in D & (LettersOf S) \ (SymbolsOf (X /\ (((AllSymbolsOf S) *) \ {{}}))) is infinite & X is D -consistent holds
( ((D,num) addw X) . k c= ((D,num) addw X) . (k + m) & (LettersOf S) \ (SymbolsOf ((((D,num) addw X) . m) /\ (((AllSymbolsOf S) *) \ {{}}))) is infinite & ((D,num) addw X) . m is D -consistent )

proof end;

definition

let X be functional set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(ExFormulasOf S);

func X WithWitnessesFrom (D,num) -> Subset of (X \/ (AllFormulasOf S)) equals :: FOMODEL4:def 72
union (rng ((D,num) AddWitnessesTo X));

coherence

proof end;

end;

:: deftheorem defines WithWitnessesFrom FOMODEL4:def 72 :

notation

let X be functional set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(ExFormulasOf S);
synonym X addw (D,num) for X WithWitnessesFrom (D,num);

end;

Lm71: for S being Language
for D being RuleSet of S
for X being functional set
for num being Function of NAT,(ExFormulasOf S) st D is isotone & R#1 S in D & R#2 S in D & R#5 S in D & R#8 S in D & (LettersOf S) \ (SymbolsOf (X /\ (((AllSymbolsOf S) *) \ {{}}))) is infinite & X is D -consistent holds
X addw (D,num) is D -consistent

proof end;

registration

let X be functional set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(ExFormulasOf S);

cluster X \ (X addw (D,num)) -> empty for set ;

coherence

proof end;

end;

theorem Th18: :: FOMODEL4:18

for Z being set
for S being Language
for D being RuleSet of S
for X being functional set
for num being Function of NAT,(ExFormulasOf S) st D is isotone & R#1 S in D & R#8 S in D & R#2 S in D & R#5 S in D & (LettersOf S) \ (SymbolsOf (X /\ (((AllSymbolsOf S) *) \ {{}}))) is infinite & X addw (D,num) c= Z & Z is D -consistent & rng num = ExFormulasOf S holds
Z is S -witnessed

proof end;

begin

::# constructions for countable languages
::# Consistently maximizing a set of formulas of a countable language

definition

let X be set ;
let S be Language;
let D be RuleSet of S;
let phi be Element of AllFormulasOf S;

func (D,phi) AddFormulaTo X -> set equals :Def73: :: FOMODEL4:def 73
X \/ {phi} if not xnot phi is X,D -provable
otherwise X \/ {(xnot phi)};

consistency ;
coherence ;

end;

:: deftheorem Def73 defines AddFormulaTo FOMODEL4:def 73 :

definition

let X be set ;
let S be Language;
let D be RuleSet of S;
let phi be Element of AllFormulasOf S;
:: original: AddFormulaTo
redefine func (D,phi) AddFormulaTo X -> Subset of (X \/ (AllFormulasOf S));
coherence

proof end;

end;

registration

let X be set ;
let S be Language;
let D be RuleSet of S;
let phi be Element of AllFormulasOf S;

cluster X \ ((D,phi) AddFormulaTo X) -> empty ;

coherence

proof end;

end;

definition

let X be set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(AllFormulasOf S);
set SS = AllSymbolsOf S;
set FF = AllFormulasOf S;
set Y = X \/ (AllFormulasOf S);
set DD = bool (X \/ (AllFormulasOf S));

func (D,num) AddFormulasTo X -> Function of NAT,(bool (X \/ (AllFormulasOf S))) means :Def74: :: FOMODEL4:def 74
( it . 0 = X & ( for m being Nat holds it . (m + 1) = (D,(num . m)) AddFormulaTo (it . m) ) );

existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def74 defines AddFormulasTo FOMODEL4:def 74 :

Lm72: for k, m being Nat
for X being set
for S being Language
for D being RuleSet of S
for num being Function of NAT,(AllFormulasOf S) st D is isotone & R#1 S in D & R#8 S in D & X is D -consistent holds
( ((D,num) AddFormulasTo X) . k c= ((D,num) AddFormulasTo X) . (k + m) & ((D,num) AddFormulasTo X) . m is D -consistent )

proof end;

definition

let X be set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(AllFormulasOf S);

func (D,num) CompletionOf X -> Subset of (X \/ (AllFormulasOf S)) equals :: FOMODEL4:def 75
union (rng ((D,num) AddFormulasTo X));

coherence

proof end;

end;

:: deftheorem defines CompletionOf FOMODEL4:def 75 :

registration

let X be set ;
let S be Language;
let D be RuleSet of S;
let num be Function of NAT,(AllFormulasOf S);

cluster X \ ((D,num) CompletionOf X) -> empty for set ;

coherence

proof end;

end;

Lm73: for X being set
for S being Language
for D being RuleSet of S
for num being Function of NAT,(AllFormulasOf S) st rng num = AllFormulasOf S holds
(D,num) CompletionOf X is S -covering

proof end;

Lm74: for X being set
for S being Language
for D being RuleSet of S
for num being Function of NAT,(AllFormulasOf S) st D is isotone & R#1 S in D & R#8 S in D & X is D -consistent holds
(D,num) CompletionOf X is D -consistent

proof end;

theorem :: FOMODEL4:19

for y, X being set
for S being Language
for R being Relation of (bool (S -sequents)),(S -sequents) holds
( y in (FuncRule R) . X iff ( y in S -sequents & [X,y] in R ) ) by Lm29;

Lm75: for S being Language
for D2 being 2 -ranked RuleSet of S
for X being functional set st AllFormulasOf S is countable & (LettersOf S) \ (SymbolsOf (X /\ (((AllSymbolsOf S) *) \ {{}}))) is infinite & X is D2 -consistent & D2 is isotone holds
ex U being non empty set ex I being Element of U -InterpretersOf S st X is I -satisfied

proof end;

Lm76: for S being Language
for D2 being 2 -ranked RuleSet of S
for X being functional set st X is finite & AllFormulasOf S is countable & X is D2 -consistent & D2 is isotone holds
ex U being non empty set ex I being Element of U -InterpretersOf S st X is I -satisfied

proof end;

Lm77: for U being non empty set
for X being set
for S1, S2 being Language
for I1 being Element of U -InterpretersOf S1
for I2 being Element of U -InterpretersOf S2 st S2 is S1 -extending & X c= AllFormulasOf S1 & I1 | (OwnSymbolsOf S1) = I2 | (OwnSymbolsOf S1) holds
( X is I1 -satisfied iff X is I2 -satisfied )

proof end;

registration

let S be Language;
let r1, r2 be isotone Rule of S;

cluster {r1,r2} -> isotone for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;
let r1, r2, r3, r4 be isotone Rule of S;

cluster K336(r1,r2,r3,r4) -> isotone for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster S -rules -> isotone for RuleSet of S;

coherence

proof end;

end;

registration

let S be Language;

cluster functional isotone Correct for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

registration

let S be Language;

cluster functional isotone 2 -ranked Correct for Element of bool (Funcs ((bool (S -sequents)),(bool (S -sequents))));

existence

proof end;

end;

registration

let S be countable Language;

cluster AllFormulasOf S -> countable ;

coherence ;

end;

theorem Th20: :: FOMODEL4:20

for Z being set
for S being countable Language
for D being RuleSet of S st D is 2 -ranked & D is isotone & D is Correct & Z is D -consistent & Z c= AllFormulasOf S holds
ex U being non empty set ex I being Element of U -InterpretersOf S st Z is I -satisfied

proof end;

Lm78: for Z being set
for S being countable Language
for phi being wff string of S st Z c= AllFormulasOf S & xnot phi is Z -implied holds
xnot phi is Z,S -rules -provable

proof end;

theorem :: FOMODEL4:21

for X being set
for C being countable Language
for phi being wff string of C st X c= AllFormulasOf C & phi is X -implied holds
phi is X -provable

proof end;