Gödel's incompleteness theorem famously tells us that there are true statements about the integers which cannot be proven. This description rather invites the question of how one can know that a statement is true if it cannot be proven. I will try to give a description of Gödel's theorem which, although incomplete, at least tells no significant lies, and tries to make it fairly clear just what the theorem says.

First, I will describe the standard integers, then give a brief description of what we mean by "provable" in this context. Once the scene is set, we are in a position to see what Gödel's incompleteness theorem actually says. Finally, armed with a reasonably accurate statement of Gödel's theorem, we can see some of its consequences; and also understand better what is not a consequence! As a reward to the patient reader (or the clever skimmer) there is also a description of an interesting statement which is true, but not provable.

What are the integers?

In this context, I mean only the non-negative ones, and we all know what they are. They are the objects \(0, 1, 2, \ldots\) and we can add them together and multiply them. There are various rules for how the numbers behave, and a precise description was given by Giuseppe Peano:
We have a set, \(\mathbb{ N}\), a function \(s:\mathbb{N} \rightarrow \mathbb{N}\), a special element \(0 \in \mathbb{N}\), and two operations, \(+\) and \(\times\) (addition and multiplication). These all fit together in the following way, where we use the mathematical symbol \(\Rightarrow\) as a shorthand for "implies".

Given any \(m,n \in \mathbb{N}\),

\(s(n) = s(m) \Rightarrow n = m\)
\(0 \neq s(n)\)
\(n+0 = n\)
\(s(n+m) = n+s(m)\)
\(n \times 0 = 0\)
\(n \times s (m ) = n + n \times m\)
If \(K\) is any subset of \(\mathbb{N}\) such that (i) \(0 \in K\), and (ii) \(n \in K \Rightarrow s(n) \in K\), then \(K\) is in fact all of \(\mathbb{N}\).

The function \(s\) takes each number to the next, its successor (so \(s(n) = n+1\)); and then the first property says that no two different numbers have the same successor, the next says that 0 is not the successor of any number, the following pairs give recursive definitions of addition and multiplication. These just make sure that addiction and multiplication behave as usual. The the last is called the inductive property, and is what makes proof by induction work.

So, these axioms seem to capture what we mean by the integers: but it would be nice also to know that there is such a collection of objects and operations, in other words, to know that the properties we associate with the integers are in fact consistent! Luckily for us, John von Neumann gave a specific example of a set and a successor operation that satisfies all these properties: \(\emptyset\) is the empty set, the successor of any integer is the set of all integers up to and including that one, and the integers comprise all sets made up in this way.

So, \(0 = \emptyset\), \(1 = s(0) = \{0\}\), \(2 = s(1) = \{0,1\}\) and so on. Then it can be shown that the above requirements are categoric, which means that any other set with a successor function satisfying all 7 properties is just the same as the von Neumann one, except that we may have chosen different symbols for the numbers and functions. The integers so specified are what are called the standard integers. The mathematical term for a relationship between two structures which is really just a relabelling is an isomorphism; we say that any two sets with successor functions satisfying the above properties as isomorphic.

What is truth?

Then we can say that a property of numbers is true if it is true for the von Neuman model of the integers. It may be hard to tell, for any given property, whether or not it is true, but I hope we can all agree that the truth or falsity of any statement about these objects is well defined, and our ignorance is just our problem.

Then what about provability? A statement about the integers is provable if there is an argument from an agreed on set of axioms describing them using an agreed set of rules of inference that leads us to the statement. Together with the above properties, we also require a well defined set of rules of how we are allowed to argue about them: this set of rules is called first order predicate calculus. We need not concern ourselves with the exact nature of this set of rules here---it is enough for our purposes to note that such a set of rules exists. Those properties which matter to us will be introduced as necessary.

To rephrase slightly, truth is to some extent an accidental property; you look at the numbers in question and see whether the property holds. Truth is a property of the meaning of the statement, and so is what we call a semantic property. Provability, on the other hand, is structural; it follows explicitly from the grammatical form of the sentence, without reference to the particular objects we are supposed to be arguing about. Since the construction of grammatically acceptable sentences is called syntax in linguistics, we extend the use of this word slightly, and say that provability is a syntactic property.

All this can be encapsulated in the slogan that truth is a semantic issue, while provability is a syntactic one. There is a snag, though. When we consider formal proof, the tool consists of first order predicate calculus; this allows us to quantify over elements of the universe of discourse, and not over sets of elements. Note that property \(7\) requires a property of all subsets of \(\mathbb{N}\); first order predicate calculus, which is basically all that standard logic has, cannot express this. We have to replace that property by another one. One way of doing this is to use \(7'\) below:

\(7'\) If \(P(n)\) is any statement about the integer \(n\) such that (i) \(P(0)\) is true, and (ii) \(P(n) \Rightarrow P(n+1)\) for all \(n \in \mathbb{N}\), then \(P(n)\) is true for all \(n \in \mathbb{N}\).

This replaces the notion of a subset of \(\mathbb{N}\) by a sentence making a statement about an unspecified integer. Now, such a sentence is a statement which can be finitely expressed using the notions of successor, addition, multiplication and logical operations. So, we replace a single axiom referring to all subsets with what is called an axiom scheme, which represents infinitely many axioms, one for each sentence \(P\). But it turns out that \(7'\) is much less powerful than \(7\); there are far more subsets of \(\mathbb{N}\) than there are sentences which can be constructed as described above.

It is then perhaps not surprising that the set of axioms obtained by replacing \(7\) by \(7'\) cannot be used to prove all the true statements about \(\mathbb{N}\). The surprising thing is that we cannot even prove all the true statements that can be expressed using the more restricted language.

We now say that a statement about \(\mathbb{N}\) is a theorem if it is the last in a sequence of statements, each of which is either one of the axioms \(1 \ldots 6\), or an instance of (7'), or an axiom of the predicate calculus, or follows from previous statements in the sequence using the rule of inference modus ponens (which simply states that if we know \(A\) and we know that \(A \Rightarrow B\) , we can deduce \(B\)). The precise nature of the axioms of predicate calculus is irrelevant; you can chase up this detail in any standard logic text if you wish. The theory obtained by using \(1..6, 7'\) with all the apparatus of first order predicate calculus is called first order Peano arithmetic, or PA for short.

The point is that for those who are reluctant to consider semantic arguments, we have syntactic ones which depend only on the structure of the theory, not on the actual objects we are considering. This is regarded as more reliable by logicians. Many of us may find this somewhat perverse, but then, logicians are paid to be perverse.

Gödel's Insight

On with the story. We can think about relations between pairs of integers (such as \(n \gt m\), or \(m=2\times n\)). Any relation will be true for some pairs, and false for others. A relation can be encoded as a subset of the set of all pairs; the relation is true if the pair is in the subset, false otherwise. Again, there are many such relations, and a smaller (though still infinite) family which can be expressed in finite terms using the notions of addition, multiplication, successor, and the basic notions of predicate calculus. These are called expressible relations, or number theoretic relations.

What Gödel did was to cook up a particularly wonderful expressible relation. To see why it is wonderful requires a very brief digression, to explain what a Gödel numbering is.

Any string involving the symbols used in PA can be associated with a unique integer, in an effective way-which means that given any string the integer can be computed in finite time by a mechanical means, and that given any integer it is possible to decode it back to the original string (or to say that it does not correspond to one) again in finite time by a mechanical process. In particular, any proof in PA corresponds to a number, as does any single statement. What Gödel found was a number theoretic relation (so it is just some complicated statement involving successor, addition, multiplication etc, that can be checked by pure arithmetic) with an almost magical property.

He found a function, \(G(m,n)\) which is zero precisely when \(n\) is the Gödel number of a proof of the statement with Gödel number \(m\). Note that this is not the definition of \(G(m,n)\). \(G(m,n)\) is defined purely in terms of arithmetic properties of \(m\) and \(n\). This means that there is some purely arithmetic combination of \(m\) and \(n\) which is zero exactly when the statement encoded by \(n\) is a proof of the statement encoded by \(m\). This combination doesn't know anything about the statements that are encoded via the Gödel numbering---it just works out some combination of sums, products and so on if the two numbers it is fed. But we, knowing about Gödel numbering, can interpret it via this Gödel numbering as saying something about strings in PA.

Next step: consider the new sentence, \(S(m)\), which says that "no matter what \(n\) you consider, \(G(m,n)\) is never zero"; we write this \(\forall n, G(m,n) \neq 0\). (The mathematical symbol \(\forall\) is pronounced "for all".) Again, this can be given a Gödel number, since it can be expressed in terms of PA. Call this Gödel number \(i\), and consider \(S(i)\). Is this statement provable? Well, suppose it had a proof. That proof would have some Gödel number, say \(j\). Then \(G(i,j)=0\), contradicting \(S(i)\). So \(S(i)\) cannot have a proof. But we can see that in the interpretation via Gödel numbers, that's just what \(S(i)\) says, and so it is in fact true, i.e. it is a true statement about standard integers. But it cannot be proven within PA.

Actually, that's not quite true. What's actually true is that if PA is consistent, then it cannot be proven within PA. If PA is not consistent, then there's no problem with having a proof of a statement and a proof of its negation too. Of course, we believe that PA is consistent, because we have the von Neumann integers as an example that satisfies the axioms of PA.

So now we know that there are true statements about the standard integers which can be expressed in the language of PA, but not proven in PA.

What are the implications?

First, we note that we managed to argue that as long as PA was consistent, we could deduce that \(S(i)\) had no proof in PA. It turns out (again, not trivially) that the statement that PA is consistent can be made within PA; we call this statement \(\mbox{Consis}\). But there is a standard logical result called the deduction theorem that enables us to convert "assuming \(A\) we can deduce \(B\)" into a proof of "\(A \Rightarrow B\)". So what? Well, suppose we had a proof within PA that PA was consistent. Then we could chain this proof of \(\mbox{Consis}\) together with a proof of \(\mbox{Consis} \Rightarrow S(i)\) to get a proof of \(S(i)\), which we know to be impossible. Thus although the statement that PA is consistent can be made within PA, it cannot be proven within PA.

Second, you can't fix this just by adding in the Gödel statement as a new axiom. Exactly the same process will enable the construction of a new Gödel sentence which is true but not provable within PA.

It also tells us that we can't prove that axiomatic set theory is consistent, using only the language of axiomatic set theory; this is because PA lives naturally inside set theory, and so the incompleteness theorem still applies.

It also tells us that PA has nonstandard models, i.e. that one can find a set, \(M\), and a successor function, \(t\), which satisfy all of \(1 \ldots 6,7'\), but where \(M\) is not isomorphic to \(\mathbb{N}\); and also that there are statements true of this model but not of the standard integers. This is also not obvious, but it does follow from standard results in model theory, which is all about attaching semantics to syntactic structures.

There are also quite a few things it doesn't tell us.

First, and most importantly it doesn't tell us that we can never be sure of a proof; all it tells us is that first order reasoning can't justify itself completely.
It doesn't tell us any interesting statements that are true of the standard integers but not provable in PA, and
It doesn't even tell us if there are any.

The proof of the pudding

In fact, there are some. Here, as a reward for sticking with this (or for your acuity in jumping straight to here) is Goodstein's theorem, which is one (really quite astonishing) example.

Let \(n\) be any number, and construct a sequence beginning at \(n\) as follows. First, write \(n\) as a sum of powers of \(2\); write each of the exponents in this sum as a sum of powers of \(2\); keep on going as long as you can. (Don't forget that any positive integer to the power of \(0\) is \(1\).)So, for example, with \(n = 37\), we get \[ 37 = 2^{2^2+1} + 2^2 + 1 \] Now repeat the following pair of operations:

increase the base for this sum of powers expression by \(1\)
subtract \(1\) from the result

The first operation gives \[ 3^{3^3+1} + 3^3 + 1 \] and the second gives \[ 3^{3^3+1} + 3^3 \] Next, we get \[ 4^{4^4+1} + 4^4 - 1 = 4^{4^4+1}+3 \times 4^3 + 3 \times 4^2 + 3 \times 4 + 3 \] Proceeding with this for three more iterations, we reduce the \(3\) to \(0\), at the expense of all the \(4\)'s rising to \(7\). At the next iteration, the \(3 \times 7 \) becomes \(2 \times 8 + 7\) and we gradually kill off the trailing \(7\) which is now no longer affected by the growth of the base.

It seems obvious that the increase of the base makes the number much bigger, and all the second operation does is to subtract \(1\), so the number will just keep getting bigger and bigger. Trying it out starting with \(n=4\) will probably confirm this opinion.

Astonishing though it may seem, this process eventually reaches \(0\), no matter what \(n\) you start with. Roughly speaking, the "subtract \(1\)" operation eventually kills off each tower of exponentials, no matter how tall it is, knocking it down to something which is not affected by the next increase of base. It isn't quick, though.

But this fact cannot be proven in PA. It is true of the standard integers, and can be shown to be true by arguments which are more powerful than those available to PA. The proof is non-trivial, and requires a technique called transfinite induction.

And finally ...

This has already been too long; but I hope I've managed to get across some of the subtlety of Gödel's work, and just how mathematical notions of truth and provability are related.

For those who want more

R Smullyan (1988) Forever Undecided: a puzzle guide to Gödel
T Franzen (2005) Gödel's Theorem: an incomplete guide to it use and abuse
Wikipedia page on Gödel's theorems
Wikipedia page on Goodstein's theorem

Shiny Pebbles and other stuff

Pages

Friday, 28 April 2017

What Goedel told us (and what he didn't).