:: G{\"o}del's Completeness Theorem
:: by Patrick Braselmann and Peter Koepke
::
:: Received September 25, 2004
:: Copyright (c) 2004-2016 Association of Mizar Users
:: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland).
:: This code can be distributed under the GNU General Public Licence
:: version 3.0 or later, or the Creative Commons Attribution-ShareAlike
:: License version 3.0 or later, subject to the binding interpretation
:: detailed in file COPYING.interpretation.
:: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these
:: licenses, or see http://www.gnu.org/licenses/gpl.html and
:: http://creativecommons.org/licenses/by-sa/3.0/.
environ
vocabularies NUMBERS, SUBSET_1, CQC_LANG, QC_LANG1, XBOOLE_0, VALUAT_1,
FINSEQ_1, HENMODEL, CQC_THE1, XBOOLEAN, BVFUNC_2, FUNCT_1, ORDINAL4,
CALCUL_1, ARYTM_3, RELAT_1, CARD_1, XXREAL_0, TARSKI, ZF_MODEL, CQC_SIM1,
REALSET1, SUBSTUT1, SUBSTUT2, ZF_LANG, ARYTM_1, CARD_3, ZFMISC_1,
FINSET_1, MCART_1, GOEDELCP, NAT_1;
notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, XCMPLX_0, XXREAL_0, ORDINAL1,
CARD_1, CARD_3, FINSEQ_1, FUNCT_1, NAT_1, QC_LANG1, QC_LANG2, QC_LANG3,
NUMBERS, CQC_LANG, RELAT_1, FINSET_1, VALUAT_1, RELSET_1, FUNCT_2,
CQC_SIM1, DOMAIN_1, XTUPLE_0, XFAMILY, MCART_1, SUBSTUT1, SUBLEMMA,
SUBSTUT2, CALCUL_1, HENMODEL;
constructors SETFAM_1, DOMAIN_1, XXREAL_0, NAT_1, NAT_D, FINSEQ_2, QC_LANG3,
CQC_SIM1, SUBSTUT2, CALCUL_1, HENMODEL, CARD_3, RELSET_1, XTUPLE_0,
XFAMILY;
registrations SUBSET_1, RELAT_1, ORDINAL1, XXREAL_0, XREAL_0, CQC_LANG,
HENMODEL, FINSEQ_1, FINSET_1, CARD_3, RELSET_1, XTUPLE_0;
requirements REAL, NUMERALS, SUBSET, BOOLE, ARITHM;
begin :: Henkin`s Theorem
registration
cluster countable for QC-alphabet;
end;
reserve Al for QC-alphabet;
reserve b,c,d for set,
X,Y for Subset of CQC-WFF(Al),
i,j,k,m,n for Nat,
p,p1,q,r,s,s1 for Element of CQC-WFF(Al),
x,x1,x2,y,y1 for bound_QC-variable of Al,
A for non empty set,
J for interpretation of Al, A,
v for Element of Valuations_in(Al,A),
f1,f2 for FinSequence of CQC-WFF(Al),
CX,CY,CZ for Consistent Subset of CQC-WFF(Al),
JH for Henkin_interpretation of CX,
a for Element of A,
t,u for QC-symbol of Al;
definition
let Al,X;
attr X is negation_faithful means
:: GOEDELCP:def 1
X |- p or X |- 'not' p;
end;
definition
let Al,X;
attr X is with_examples means
:: GOEDELCP:def 2
for x,p holds ex y st X |- ('not' Ex(x,p)) 'or' (p.(x,y));
end;
theorem :: GOEDELCP:1
CX is negation_faithful implies (CX |- p iff not CX |- 'not' p);
theorem :: GOEDELCP:2
for f being FinSequence of CQC-WFF(Al) holds
|- f^<*'not' p 'or' q*> & |- f^<*p*> implies |- f^<*q*>;
theorem :: GOEDELCP:3
X is with_examples implies (X |- Ex(x,p) iff ex y st X |- p.(x,y));
theorem :: GOEDELCP:4
(CX is negation_faithful & CX is with_examples implies
(JH,valH(Al) |= p iff CX |- p)) implies
(CX is negation_faithful & CX is with_examples implies
(JH,valH(Al) |= 'not' p iff CX |- 'not' p));
theorem :: GOEDELCP:5
|- f1^<*p*> & |- f1^<*q*> implies |- f1^<*p '&' q*>;
theorem :: GOEDELCP:6
X |- p & X |- q iff X |- p '&' q;
theorem :: GOEDELCP:7
(CX is negation_faithful & CX is with_examples implies
(JH,valH(Al) |= p iff CX |- p)) &
(CX is negation_faithful & CX is with_examples implies
(JH,valH(Al) |= q iff CX |- q)) implies
(CX is negation_faithful & CX is with_examples
implies (JH,valH(Al) |= p '&' q iff CX |- p '&' q));
theorem :: GOEDELCP:8
for p st QuantNbr(p) <= 0 holds
CX is negation_faithful & CX is with_examples implies
(JH,valH(Al) |= p iff CX |- p);
theorem :: GOEDELCP:9
J,v |= Ex(x,p) iff ex a st J,v.(x|a) |= p;
theorem :: GOEDELCP:10
JH,valH(Al) |= Ex(x,p) iff ex y st JH,valH(Al) |= p.(x,y);
theorem :: GOEDELCP:11
J,v |= 'not' Ex(x,'not' p) iff J,v |= All(x,p);
theorem :: GOEDELCP:12
X |- 'not' Ex(x,'not' p) iff X |- All(x,p);
theorem :: GOEDELCP:13
QuantNbr(Ex(x,p)) = QuantNbr(p)+1;
theorem :: GOEDELCP:14
QuantNbr(p) = QuantNbr(p.(x,y));
reserve L for PATH of q,p,
F1,F3 for QC-formula of Al,
a for set;
theorem :: GOEDELCP:15
for p st QuantNbr(p) = 1 holds (CX is negation_faithful & CX is with_examples
implies (JH,valH(Al) |= p iff CX |- p));
theorem :: GOEDELCP:16
for n st for p st QuantNbr(p) <= n holds
(CX is negation_faithful & CX is with_examples
implies (JH,valH(Al) |= p iff CX |- p)) holds
for p st QuantNbr(p) <= n+1 holds
(CX is negation_faithful & CX is with_examples
implies (JH,valH(Al) |= p iff CX |- p));
:: Ebb et al, Chapter V, Henkin's Theorem 1.10
theorem :: GOEDELCP:17
for p holds (CX is negation_faithful & CX is with_examples
implies (JH,valH(Al) |= p iff CX |- p));
begin :: Satisfiability of Consistent Sets of Formulas with Finitely Many Free
:: Variables
theorem :: GOEDELCP:18
Al is countable implies
QC-WFF(Al) is countable;
definition
let Al;
func ExCl(Al) -> Subset of CQC-WFF(Al) means
:: GOEDELCP:def 3
a in it iff ex x,p st a = Ex(x,p);
end;
theorem :: GOEDELCP:19
Al is countable implies
CQC-WFF(Al) is countable;
theorem :: GOEDELCP:20
Al is countable implies
ExCl(Al) is non empty & ExCl(Al) is countable;
definition
let Al;
let p be Element of QC-WFF(Al) such that
p is existential;
func Ex-bound_in p -> bound_QC-variable of Al means
:: GOEDELCP:def 4
ex q being Element of QC-WFF(Al) st p = Ex(it,q);
end;
definition
let Al;
let p be Element of CQC-WFF(Al) such that
p is existential;
func Ex-the_scope_of p -> Element of CQC-WFF(Al) means
:: GOEDELCP:def 5
ex x st p = Ex(x,it);
end;
definition
let Al;
let F be sequence of CQC-WFF(Al),a be Nat;
func bound_in(F,a) -> bound_QC-variable of Al means
:: GOEDELCP:def 6
p = F.a implies it = Ex-bound_in p;
end;
definition
let Al;
let F be sequence of CQC-WFF(Al),a be Nat;
func the_scope_of(F,a) -> Element of CQC-WFF(Al) means
:: GOEDELCP:def 7
p = F.a implies it = Ex-the_scope_of p;
end;
definition
let Al,X;
func still_not-bound_in X -> Subset of bound_QC-variables(Al) equals
:: GOEDELCP:def 8
union {still_not-bound_in p : p in X};
end;
theorem :: GOEDELCP:21
p in X implies X |- p;
theorem :: GOEDELCP:22
Ex-bound_in Ex(x,p) = x & Ex-the_scope_of Ex(x,p) = p;
theorem :: GOEDELCP:23
X |- VERUM(Al);
theorem :: GOEDELCP:24
X |- 'not' VERUM(Al) iff X is Inconsistent;
reserve C,D for Element of [:CQC-WFF(Al),bool bound_QC-variables(Al):];
reserve K,L for Subset of bound_QC-variables(Al);
theorem :: GOEDELCP:25
for f,g being FinSequence of CQC-WFF(Al) st 0 < len f & |- f^<*p*> holds
|- Ant(f)^g^<*Suc(f)*>^<*p*>;
theorem :: GOEDELCP:26
still_not-bound_in {p} = still_not-bound_in p;
theorem :: GOEDELCP:27
still_not-bound_in (X \/ Y) = still_not-bound_in X \/ still_not-bound_in Y;
theorem :: GOEDELCP:28
for A being Subset of bound_QC-variables(Al) st A is finite holds
ex x st not x in A;
theorem :: GOEDELCP:29
X c= Y implies still_not-bound_in X c= still_not-bound_in Y;
theorem :: GOEDELCP:30
for f being FinSequence of CQC-WFF(Al) holds
still_not-bound_in rng f = still_not-bound_in f;
:: Ebb et al, Chapter V, Lemma 2.1
theorem :: GOEDELCP:31
( Al is countable &
still_not-bound_in CX is finite ) implies
ex CY st CX c= CY & CY is with_examples;
theorem :: GOEDELCP:32
X |- p & X c= Y implies Y |- p;
reserve C,D for Subset of CQC-WFF(Al);
:: Ebb et al, Chapter V, Lemma 2.2
theorem :: GOEDELCP:33
( Al is countable &
CX is with_examples ) implies ( ex CY st CX c= CY &
CY is negation_faithful & CY is with_examples );
reserve JH1 for Henkin_interpretation of CZ,
J for interpretation of Al, A,
v for Element of Valuations_in(Al,A);
theorem :: GOEDELCP:34
(Al is countable & still_not-bound_in CX is finite)
implies ex CZ,JH1 st JH1,valH(Al) |= CX;
begin :: Goedel's Completeness Theorem,
:: Ebb et al, Chapter V, Completeness Theorem 4.1
theorem :: GOEDELCP:35
J,v |= X & Y c= X implies J,v |= Y;
theorem :: GOEDELCP:36
still_not-bound_in X is finite implies
still_not-bound_in (X \/ {p}) is finite;
theorem :: GOEDELCP:37
X |= p implies not J,v |= X \/ {'not' p};
::$N Goedel Completeness Theorem
theorem :: GOEDELCP:38
( Al is countable &
still_not-bound_in X is finite & X |= p ) implies X |- p;