Gödel’s Incompleteness Theorems

GÖDEL’S PARADOX

All of these paradoxes are related to, and historically lead up to, Gödel’s incompleteness theorems. Kurt Gödel was a logician who lived from 1906 to 1978. In 1931 he proved a theorem about the limitations of mathematics which proved quite shocking to mathematicians of the time. The theorem basically says that any consistent logical system is doomed to have statements that can neither be proved nor disproved, unless the logical system is rather small and boring. “Consistent” and “logical” have formal meanings here: logical means it has been built up from axioms in a precise way, and consistent means that it does not contain any contradictions, so that if something is true it can’t also be false.

Of course, “small” and “boring” are very informal words, and sound like subjective descriptions. But, for example, any logical system that is merely large and interesting enough to express the arithmetic of the whole numbers is already doomed to have this property of incompleteness. First-order logic, without quantifiers, doesn’t fall into this category. In fact, first-order logic can be proved to be complete, in that everything is provably true or false. Second-order logic cannot.

The shock of Gödel’s theorem was heightened because it destroyed the ambitious program of David Hilbert. Hilbert, the leading formalist, sought to provide a secure foundation for all of mathematics using finitary consistency proofs—ones that did not rely on the existence of infinite sets. His goal was to banish paradoxes and doubt by showing that mathematics could be completely derived from a consistent set of axioms. Gödel’s incompleteness theorem, however, showed not only that any sufficiently strong system must contain unprovable statements, but also (via his second incompleteness theorem) that no consistent formal system of arithmetic can prove its own consistency. This effectively killed Hilbert’s program.

A bit like Russell’s paradox, it comes down to questions of self-reference. As soon as a statement is allowed to reference itself, strange loops can be caused. Sometimes these loops produce beautiful structures like fractals or infinite loops in computer programs. But logical loops can cause us problems, as referenced in Douglas Hofstadter’s book title I Am a Strange Loop.

Gödel’s incompleteness theorem is discussed extensively in Hofstadter’s exquisite earlier book Gödel, Escher, Bach. In it Hofstadter elucidates not only the incompleteness theorem but all sorts of fascinating links between logical structures and abstract structures in the music of Bach and the prints of Escher, both of whose works are deeply mathematical while also being immensely artistically satisfying.

The proof of the incompleteness theorem involves constructing a statement that creates a paradox through self-reference. The ingenuity and shock of it comes from being able to do this entirely formally in a mathematical system, essentially using numbers. It is easy enough to utter a sentence in normal English that is unprovable, such as “I am happy”, but that is just because “happy” is not a logical enough concept to prove or disprove using logic.

Gödel formally encoded the sentence: This statement is unprovable.

First of all we can determine that this statement is true: if it were false then this would mean it is provable, but that would make it true and would give a contradiction. However, the fact that it is true means that it is unprovable, because that is what the sentence says. (If you’re anything like me, you might get dizzy thinking about that.)

Gödel showed that it is possible to make this statement using the language of arithmetic, thus proving that any mathematical system that includes arithmetic must be incomplete. There certainly are smaller mathematical systems than that which are complete, but they don’t include arithmetic so can hardly claim to be all of mathematics.

Gödel’s paradox is a veridical paradox – there is nothing wrong with the logic, although some mathematicians were so outraged by its conclusion that they refused to believe it. This is an example of the fact that even in the logical world of mathematics if a conclusion feels wrong there are mathematicians who refuse to believe it although they can’t find anything logically wrong with the proof. What the paradox warns us is that we should limit our expectations of what mathematics can do. Mathematicians have by and large recovered from that shock now. However, Hilbert’s formalist spirit survives in the way mathematicians operate: they often rely on intuition and Platonist thinking during exploratory work, but when certainty is required they retreat to formal proofs. As Philip Davis and Reuben Hersh famously put it, “The typical working mathematician is a Platonist on weekdays and a formalist on Sundays.”

Even today, a small number of dissenters question the consistency of mathematics. For instance, Edward Nelson attempted to prove the inconsistency of arithmetic in 2011 (his argument was quickly shown flawed by Terence Tao), and Vladimir Voevodsky has advocated for new foundations based on homotopy theory. Yet for most mathematicians, the lesson of Gödel’s paradox has been absorbed: mathematics is not a closed, perfect system, but an ever-evolving field with inherent limitations.

In fact, even before this shock there was an earlier threat to the very foundations of mathematics, coming from Bertrand Russell.