5.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.

Self-quotation theorem

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.
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)].

Proof.
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.
Then let X be the term ([H] : J[H]). Thus F(X), that is F([H] : J[H]), can also be abbreviated as H[H].
Thus T⊢ X = ([H] : [[H]]) = [F(X)] ∎
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.

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⊢ G⇎v[G].

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:
  1. 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);
  2. then define a model which fits with this interpretation.
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.
This affects the provability in arithmetic, that is a particular use of second-order logic, 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 (countable) ℘(ℕ).

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 ground formula,
1) (T⊢ F) ⇒ (T⊢ p[F])
2) (T⊢ ¬p[0]) ⇔ (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 deduced)

Proofs:
1) The proof of F in T can be copied into T ′, or converted to a proof of existence of a proof.
Contrapositive viewpoint if T can describe models: every model of some T ′ is a model of T.
2) Let T⊢ (G ⇎ p[G]). The proof (T⊢ G) ⇔ (T⊢ G∧p[G]) ⇔ (T⊢ 0) formalized in T gives T⊢(p[G]⇔p[0]). Thus (T⊢ ¬p[0]) ⇔ (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]). ∎

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.

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 of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
5.1. Second-order structures and invariants
5.2. Second-order logic
5.3. Well-foundedness
5.4. Ordinals and cardinals
5.5. Undecidability of the axiom of choice
5.6. Second-order arithmetic
5.7. The Incompleteness Theorem
More philosophical notes :
Gödelian arguments against mechanism : what was wrong and how to do instead
Philosophical proof of consistency of the Zermelo-Fraenkel axiomatic system