4.7. The Incompleteness Theorem
In this section, "arithmetic" will mean the first-order
theory of full arithmetic.
The famous incompleteness theorem by Kurt Gödel, comes from finding a way to write
a formula saying "This formula is unprovable", then analyzing its status. The
resulting paradox affects arithmetic
(and thus any theory containing it), as he showed by a very hard work of developing proof theory from it.
Let us focus on the most interesting aspects of this result and its proof, by directly
assuming the framework of proof theory in which they are naturally expressed.
The liar paradox, "This formula is false", uses two a priori dubious elements :
Let us show that self-quotation is actually legitimate, as it can anyway be constructed, without
assuming it, in any theory able to describe expressions (such as a set theory) : in any
expression with a free variable ranging over the notion of expression (as objects), we can
replace this variable by a quotation of this expression, this quotation included.
- the possibility for a formula to quote itself as an object;
- the truth predicate over ground formulas
taken as objects.
To avoid having multiple copies of "the same expression" among objects, let us assume a
formalization generalizing the concept of term algebra,
to the use of all needed symbols (with connectives and quantifiers). (Another method would be
to work with equivalence classes of expressions, maybe implicitly by only using operations
compatible with this equivalence)
Theorem. Let T a theory able to describe
itself, in the sense that we can define there (thus find in every
model M it may have) a system T ' representing an image of the first 2 levels of T (types, structure symbols,
and the notion of expression made of them) in this sense:
Then, for every expression F of T with a distinguished variable x
(ranging over expressions of T ' with "the same"
list of free variables as F but without x), there is a ground term
X so that T⊢ X = [F(X)].
- For any expression F in T, there is a ground
term [F] in T, which is the quotation of F:
in any model, [F] designates the copy of
F in T ′.
- T can describe this quotation process in T ',
by a unary term J,
taking argument in some class of expressions of T ',
and values in the class of ground terms of T '
: for any expression F in T we have T⊢
J[F] = [[F]]
- It can define formal substitutions (compositions) in T ' :
between variables A (ranging over expressions of T '
with a distinguished free variable and a given list of others) and u (ranging over
ground terms of T '), the operation (A : u)
gives the expression in T ' obtained by replacing the
variable of A by u. So, for any unary formula F and
ground term K of T we have T⊢ [F]
: [K] = [F(K)].
Let H(y) be the expression F(y
: J(y)) with variable y ranging over the
class of expressions of T ' with the same type
(in T ') as F (in T) except for the intended
type of their distinguished variable (which will range over expressions with one more
variable, but such a difference on the intended type
of a variable does not affect the formal processes over expressions using it);
and actually the same type as H.
This is itself a theorem of finitistic mathematics, i.e. refers to a specific method (algorithm), which,
given as input the data of some finite systems (expressions, proofs) provides related systems as
output after finitely many operations (not unreasonably more than the size of input). Therefore
it is valid in the framework of any theory able to describe expressions (such as arithmetic, through
Godel's constructions), which may differ (be weaker than) the theory T it may
describe (such as a set theory). Next theorems will also be of this kind.
Then let X be the term ([H] : J[H]).
Thus F(X), that is F([H] :
J[H]), can also be abbreviated as
Thus T⊢ X = ([H] : [[H]])
= [F(X)] ∎
T has non-standard models, that is where the quotation function is not surjective
to T '. Non-standard expressions in T '
(those not reached by quotation) are those which either use a non-standard symbol (which may
exist if T has an infinity of symbols), or have a non-standard
size (which may be defined
as the number of occurrences of symbols, with counting defined by T). In this case
T ' is not actually a theory, but still looks like one as seen by T.
Truth Undefinability theorem
Now that self-quotation is known to be a legitimate mathematical tool, while logic naturally
interprets any contradiction as refuting whatever assumption we started with,
the actual lesson from the
liar paradox is the Truth Undefinability theorem, by Tarski (see wikipedia
article): the impossibility for any formula of T with only 1 free variable,
to correctly express the
predicate of "truth in the current model" over the class of all ground formulas.
Theorem. Under the above assumptions on theory T,
for any invariant unary predicate
v with domain the class of
ground formulas of T', there is a ground formula G of T on which v
necessarily gives the wrong value : T⊢
Proof : by the self-quotation theorem, defining F as ¬v,
and defining G as F(X). ∎
Among unary predicates v over all ground formulas, the logically
consistent ones, which we can call interpretations, represent classes of models for the relation
of elementary equivalence
(bijectively if we consider all unary relations disregarding their definability).
The truth undefinability theorem implies that any invariant interpretation
can only describe a class of models not containing the current one.
Somehow, any "construction" of a model depends on the framework of a preexisting
universe (with its model of arithmetic), whose standardness cannot be defined
in the absolute.
In particular, arithmetic cannot express the interpretation of all its own ground
formulas in the standard model (the current interpretation, trivially interpreting
the object symbols by those of the framework). Namely, while it can interpret
by recursion all algebraic terms by a single formula, this cannot be extended
to ground formulas with an unlimited number of quantifiers.
Still, it can do things the other way round:
Whatever the method, if we can express the truth
predicate of all ground formulas of a theory T in a model M, by a formula also
expressible in T, then the interpretation of this formula by T in M is
necessarily incorrect (defining a different elementary equivalence class of models when tested
on a standard formula), as it differs from the supposedly correct first interpretation.
Arithmetic can define interpretations of (an image of) its own ground formulas but
always different from the standard interpretation, so that the
corresponding models of arithmetic are necessarily non-standard.
- define a formal interpretation of all ground formulas of a given consistent
theory (assuming its consistency but not adding this assumption as an axiom
in this object-theory so assumed to be consistent), and adding one by one to
axioms each ground formula consistent with previous
ones (like in the proof of the completeness theorem);
- then define a model which fits with this interpretation.
This affects the provability in arithmetic, that is a particular use of
which does not admit any complete rules of proof similar to what the
completeness theorem gives to first-order logic. The use of strong axiomatic
systems contributes to reduce the margin of undecidabilities, by
the ability of bigger universes to process the definition of some
subsets of given sets that could have been ignored by smaller
universes, thus forcing them to be present in the considered universe.
We can actually build countable models of set theory whose set of
integers remain standard: in a set theoretical framework with the
axiom of choice, we can take a standard sub-universe U
then construct a countable sub-universe of U with an elementary
embedding into U, by using the axiom of choice to interpret in
U the operator symbols from all existence formulas true in U.
This keeps the "true" (standard) ℕ but gives a different
First Incompleteness Theorem
As particular cases of arithmetical definitions, algorithms (such as the logical
deduction from a consistent list of axioms produced by an algorithm) cannot
process the standard interpretation either. Now Gödel's First Incompleteness
Theorem says that algorithms can do even less than arithmetic definability:
Theorem. No algorithm can produce
any consistent interpretation of all ground formulas of arithmetic.
Here is a proof a bit different (simpler ?) than Gödel's:
An algorithm that stops to decide a formula as true or false (in standard time), will
keep its result when interpreted in a non-standard model (the finiteness of
its operations keeps it unaffected by non-standard numbers). The contradiction with the
truth undefinability theorem refutes the existence of a deciding algorithm. ∎
Thus, the above described kind of arithmetic definition of an interpretation, cannot
be reduced to an algorithm, for the following reason. Each step of its "construction" involves a
search of a proof (a refutation of a formula from previous axioms); among these searches,
will necessarily be endless ones, whose result is differently interpreted
between models : an algorithm (here a search for proof) which does not
stop in standard time, may be reinterpreted in a non-standard model as stopping (after a
non-standard number of operations, finding a proof with non-standard size).
Second Incompleteness Theorem
Continuing with the assumptions of the Truth Undefinability Theorem,
let us present Gödel's second incompleteness theorem, according to which
whenever T is consistent (which we admitted in this study,
since a model of T is used and thus exists) and
T ′ is supposed to have the
same format (having the image of each axiom of T among its own
axioms or at least theorems), then the consistency of
T ′ is not provable inside the
formalism of T. To make things simple let us express it and
sketch its proof in the context of proof theory (assuming the concept
of "proof" to be already available):
Theorem. If T ′ is
built like T which can express the provability p
in T ′, and F is a
1) (T⊢ F) ⇒ (T⊢ p[F])
2) (T⊢ ¬p) ⇔ (T⊢
0) (Gödel's second incompleteness theorem : no consistent theory
can prove its own consistency)
3) (T⊢ p[F] ⇒ F) ⇔ (T⊢
F) (Löb's theorem, from which «This claim is provable» is
No converse for 1): as argued above, the provability of a formula F may be itself
undecidable but then actually false. In this case, (T⊢ p[F])
may hold (such as if p[F] was taken as an axiom of T),
in which case T has only non-standard models where all «proofs of F in
T ′» are non-standard (with non-standard size)
and thus not real proofs.
This case cannot be formally distinguished from the case when proofs of F exist
but are too big to be found in practice. Models where F is false exist in standard
universes but are absent from some non-standard universes.
Wherever models of T can be found, some of them cannot find any one of them anymore.
1) The proof of F in T can be copied into T ′, or converted to a proof of existence of a
Contrapositive viewpoint if T can describe models:
every model of some T ′ is a model
2) Let T⊢ (G ⇎ p[G]). The proof (T⊢
G) ⇔ (T⊢ G∧p[G]) ⇔ (T⊢
0) formalized in T gives T⊢(p[G]⇔p).
Thus (T⊢ ¬p) ⇔ (T⊢ ¬p[G]) ⇔
(T⊢ G) ⇔ (T⊢ 0).
3) from 2) applied to the theory (T+¬F). Finally
take F=«F is provable», ie T⊢ (F ⇔ p[F]).
So, while the rules of provability are formally well-defined (as they have been effectively
expressed by Gödel in the language of arithmetic), the interpretation of these rules and
thus the very question of the provability of some formulas from some specified theory, will
remain sometimes undecidable (relative to a universe with its interpretation of standardness).
This page may be reworked later
Topics of concern :
A version of self-quotation can be expressed for the case of algorithms.
is it worth generalizing the self-quotation theorem by taking a T' with explicitly
richer language than T, and where F only exists in T', named by a ground formula
of T which may not be the quote of a formula of T ? Should we then re-write the
proof for this case (and how) or can it just be deduced by re-applying the self-quotation
theorem already formulated, at the next level of the hierarchy ? Might this provide a way
to simplify the proof of the second incompleteness theorem ? While it is already rather
short, we might still wonder if it can still be simplified further by doing each thing at its
right level of the hierarchy, in case it wouldn't be so yet...
In this second incompleteness
we might distinguish 2 external frameworks: the most external being totally finitist while the
more internal one would be arithmetic with its concept of provability involving a quantifier
(existence of a proof); and the third, most internal level being any theory (containing arithmetic)
We may also introduce other theorems: the speed-up theorem and
Chaitin's theorem are particularly interesting.
Set theory and foundations
1. First foundations of
2. Set theory (continued)
3. Algebra 1
4.1. Finiteness and countability
4.2. The Completeness Theorem
models of Arithmetic
4.4. Infinity and the axiom of choice
4.5. How theories develop
4.6. Second-order logic
4.7. The Incompleteness Theorem