The famous mathematician Kurt Gödel proved two “incompleteness” theorems. This is their story.

By the 1930s logicians, especially Tarski, had figured out the semantics of predicate logic. Tarski described what exactly was an ‘interpretation’ and what it meant for a formula to be true in an interpretation. Briefly, an interpretation is a nonempty set (the “universe of discourse”) together with, for each n-ary relation symbol, an n-ary relation over the universe, and for each n-ary operation symbol, an n-ary operation over the universe.

Before this, logic had been strictly syntactical and proof theoretic. With the emergence of semantics the question arose about the relation between syntax and semantics. In particular, logicians asked if every tautology (formula true in all interpretations) is provable.

The young Kurt Godel, in his PhD thesis, answered this affirmatively: he showed that every tautology has a proof. This is his “completeness” theorem. We won’t get into it here.

True arithmetic

Truth in all interpretations is important but for practical purposes we are also interested in what is true in individual interpretations. In particular, we’d like to know what is true in arithmetic – in the interpretation where the universe of discourse is the integers and we have equality, the less than relation and the operations successor, addition and multiplication.

Gödel’s colleagues were searching for what, in modern terminology, we’d call a decision procedure for the set of true first order formulas of arithmetic. In other words, a mechanical procedure to decide whether or not a first order formula in the language of arithmetic is true in the standard interpretation. Remember that the twin primes conjecture, for example, is one such formula.

Gödel at first tried to find such a procedure but eventually came to suspect that there wasn’t one, and he set out to prove it. Suppose the set of true arithmetic formulas (this set is now called True Arithmetic) has a mechanical test for membership. We can start listing all formulas and rejecting the false ones. Those left over, the true ones, we can take as axioms for True Arithmetic. These axioms are complete: every formula is either one of these, or its complement is.

Gödel’s strategy was to show that True Arithmetic has no complete axiomatization. Given a proposed set 𝒜 of axioms, he constructs a statement U_𝒜 that is true but unprovable from 𝒜. He used the same trick as the liar paradox: U_𝒜 says it itself is not provable from 𝒜. It follow easily that U_𝒜 is true (it’s not provable) but – not provable.

Recursive and recursively enumerable

An important concept that arises is that of (recursive) enumerability. A set is recursively enumerable (re) if there is a machine which, running possibly indefinitely, eventually outputs any particular element of the set, and only elements of the set. A very simple example of an re set is the natural numbers, They are enumerated by a counter that starts at 0. Every finite set is re.

A set is recursive iff there is a mechanical decision procedure for testing membership. In other words, Gödel’s colleagues were trying to show that the set of all true first-order formulas of arithmetic is recursive.

It’s not hard to show that every recursive set is re – to enumerate its elements you feed the natural numbers through a filter that eliminates non elements. On the other hand, if both a set S and its complement -S are re, S must be recursive. To decide if a number n is in S, you simultaneously enumerate S and its complement -S until n shows up in one of these. If it shows up in the enumeration of S, n is in S, otherwise n is in -S.

Gödel coding

We need to establish that various sets of formulas are re or recursive, but strictly speaking we can’t because only sets of natural numbers have these properties. The solution Gödel came up with was to devise a coding scheme for formulas so that every formula has a unique code and vice versa.

There are various ways to do this and the details don’t matter. For example we can factor a number into a product of powers of exponentials. Then we can consider the number as the code for the sequence of powers.

Once we can code arbitrarily long sequences we can code nested sequences and arbitrary hierarchical structures. This gives us logical formulas, proof trees, sets of formulas and the like. It’s not hard to show that the sets of formulas and proof trees (in particular) are recursive and thus re.

Enumerability of consequences

Then from the enumeration of the proof trees we can filter out those that have no assumptions and extract their conclusions. This shows that the set of (codes for) tautologies is re.

The tautologies are the consequences of the empty set of axioms. We can easily use a similar argument to show that the set of consequences of any finite set of axioms is re.

With a little more effort we can establish the same for any enumerable set of axioms. We take our enumeration of the axioms and produce an enumeration of the initial segments, and for each enumerate the consequences. We merge these enumerations for the desired result. (The principal here is that an re union of re sets is re).

Decision procedure

What this means is that if we have a set of axioms for arithmetic that is complete, we have our decision procedure

A set of axioms is complete iff it settles the status of every formula ψ: either ψ or ¬ψ is a consequence. If we had a complete (re) set of axioms for arithmetic then to decide if ψ is true in arithmetic, we enumerate the consequences of the axioms and wait for either ψ or ¬ψ to show up. If ψ shows up it’s true, otherwise false. Since the axioms are complete one of ψ and ¬ψ will eventually show up, and we won’t wait forever.

On the other hand, if there is decision procedure, we can easily find an enumerable complete set of axioms. We run the set of formulas through our decision procedure and filter out the false ones, leaving the set of true formulas of arithmetic. This set is clearly re (given our assumption of a decision procedure) and so clearly constitutes a complete axiomatization of arithmetic truth.

To summarize, arithmetic truth is recursive iff it has a complete (re) axiomatization.

Axioms for arithmetic

The question then is, which axioms? There is really only one candidate, namely Peano arithmetic. There are different presentations. The simplest are the recurrence equations for + and * plus an axiom schema for proving formulas true by induction. It is now known that Peano arithmetic is strong enough (using coding) for almost all of finite mathematics (it doesn’t handle real arithmetic) but of course is incomplete.

We know it’s incomplete because of Gödel’s result but obviously he didn’t have this information. I haven’t been able to find out if Peano arithmetic was known already to be incomplete.

If Peano arithmetic is incomplete, what do you add? You can already prove, e.g. the distributive law by induction.

Gödel initially believed arithmetic was axiomatizable, but at some point he began to have second thoughts and started working on a proof that it was not. His strategy was to come up with a sentence whose provability would produce a contradiction. The sentence should therefore assert the unprovability of something that is nevertheless true.

The Liar Sentence

The answer is to produce a sentence that asserts its own unprovability. If you can prove it, it’s false and you have your contradiction. But if you can’t prove it, it’s true, and you have incompleteness.

With the coding you can talk about provability but the trick is to get the sentence to refer to itself.

Let 𝒫_𝒜 be provability in 𝒜. Enumerate the one-place formulas so that φ_n is the nth such formula.

Now consider the one-place formula ¬𝒫_𝒜(φ_i(i))), call it δ(i). It must have an index d in the above enumeration, so that δ(d) ⟷ ¬𝒫_𝒜(φ_d(d)). But δ‘s index is d, so δ(d) is φ_d(d), Putting our equivalences together, we get φ_d(d) ⟷ ¬𝒫_𝒜(φ_d(d)) which is φ_d(d) asserting its own unprovability.

So now we reason carefully. If φ_d(d) were provable, we’d get a contradiction, impossible if 𝒜 is consistent. So con(𝒜) implies φ_d(d) not provable, i.e. con(𝒜) –> φ_d(d) . But suppose we were able to prove the consistency of 𝒜; then we could prove φ_d(d), impossible (if 𝒜 is actually consistent).

The end result is that if 𝒜 is consistent, we can’t prove it’s consistent. This is the second incompleteness theorem.

So given a powerful consistent system 𝒜, not only is it incomplete but in particular its own consistency is unprovable. This put paid to the dream of a complete, final axiomatization of arithmetic, of a decision procedure for true arithmetic, and a provably consistent set of axioms.

In fact true arithmetic is a very complicated set – a new level of complexity for every number of quantifier alterations.

Very far from the decidable set the researchers before Gödel hoped it would be.

Relying on Experience

We can’t prove Peano arithmetic consistent so where does that leave us? (We can prove consistency using stronger systems whose own consistency is questionable.)

It leaves us with more than a century of experience with the Peano axioms. In all that time no contradiction has been uncovered. This is strong experimental evidence for the consistency of Peano arithmetic.

Also, in all that time the Peano system has proved perfectly adequate for ‘practical’ mathematics. This is strong experimental evidence for completeness in a practical sense: everything true that we’re interested in is provable.

In fact it wasn’t till 1977 that Paris and Harrington discovered a ‘natural’ example of incompleteness. They found a powerful form of Ramsey’s theorem that implies the consistency of Peano arithmetic and therefore can’t be proved.

So consistency and completeness have proved to be not a problem in any practical sense. The situation is grim only if we restrict ourselves to formal reasoning. If we allow experimental evidence, like any other science, we’re in good shape. This is the real meaning of the incompleteness theorems.