What Gödel Wrought

The Enlightenment was a three-century European movement to tame the world under the reign of Reason. It began with René Descartes and Isaac Newton in the 17th century, expanding the domain of science; in the 18th century, Emmanuel Kant sought to rationalize faith itself, with his monograph, Religion within the Limits of Reason Alone. In the 19th century, the Enlightenment really caught fire, and John Stuart Mill created (what he claimed as) an ethics of pure reason. It became fashionable to imagine that science would conquer all, and the world would be understood as a vast machine. 

Some say that the Enlightenment faced a crisis with Nietzsche, and some say that the Enlightenment has yet to come to grips with quantum mechanics. I would argue that the Enlightenment ended in 1931, when a young Austrian mathematician named Kurt Gödel wrote his epitaph on the tomb of All-Powerful Reason.

---

Whitehead and Russell

The story’s prelude was in the 1910s, when a young Bertrand Russell teamed up with the foremost philosopher of his time, Alfred North Whitehead to write an encyclopedic, three-volume exposition of mathematical logic. The conquest of the world by Reason would begin with the conquest of mathematics. Every mathematical statement is either true or false. The way we can know this is that for every true statement there is a mathematical proof, derivable from a small number of postulates = self-evident statements about arithmetic. Examples of postulates are “Zero is a number”; “Every number has a successor, which is also a number.” Can’t argue with that.

Just as there are rules for arithmetic, there are rules for logic, and the latter can be used to rationalize the former. Whitehead and Russell set out to prove the bolded statement above — that every true statement could be proven. In practice, this is something that mathematicians had assumed since the time of Euclid. If a statement seemed true, it was reasonable to search for a proof without fear that the search for proof of a true statement would be doomed from the start. The very idea that Russell and Whitehead could question such a thing would have seemed like nitpicking to mathematicians just a few years earlier.

But three volumes later, W & R expressed frustration. Several times, they had felt themselves to be on the cusp of a proof, but there was an elusive gap that they could never quite close. They put the project aside in 1913, as Russell became an outspoken voice for peace during the Great War.

“Russell’s activism against British participation in World War I led to fines, a loss of freedom of travel within Britain, and the non-renewal of his fellowship at Trinity College, Cambridge, and he was eventually sentenced to prison in 1918 on the tenuous grounds that he had interfered in British foreign policy.” [Wikipedia]

Gödel’s Bombshell

Before Gödel, it was intuitively clear to everyone that any meaningful mathematical statement must be either true or false, “the law of the excluded middle”. True statements can be proved, and false statements can be disproved.

Not so, said Gödel. There are an infinity of statements about which we may never know whether they are true or false.

• For example, “There is only one way to express any number as the product of prime numbers.” This is a classical truth, proved in antiquity.
• For example, “There is an infinite number of Pythagorean Triples = sets of three integers {A, B, C} such that A² + B² = C² ” True and proven. It’s true even if you don’t count multiples of smaller Pythagorean Triples as distinct.
• For example, “No set of four numbers {A, B, C, N} exists such that A^N + B^N = C^N except if N=2.” This was called “Fermat’s last theorem” and no one knew whether it was true or false until 1994. It’s true.
• For example, “For every even number E, you can find two prime numbers that add up to E.” This seems to be true, but no one knows for sure.

How can simple integers defy our logical assault? How is it possible to know what can and cannot be known?

I didn’t understand what Gödel’s theorem was about until I read a book by Nagel and Newman. I think it doesn’t take a book to understand Gödel’s proof, and if you have a little acquaintance with math and a nerdy disposition, it’s fun.

Gödel’s Proof — a Cook’s Tour

1. Countable infinities

I’ll start with something much simpler, but counter-intuitive in its own right. The simplest infinity, the “smallest” infinity, is called by mathematicians the “natural numbers”, {0, 1, 2, 3, …}. This is a “countable infinity”.

The next larger infinity you might imagine is the “rational numbers”, which are numbers that can be expressed as a fraction like ½ or 7936/55. Intuitively, there are a whole lot more rational numbers than natural numbers. But, no! The infinity of rational numbers is the same as the infinity of counting numbers. The proof is that you can “count” them, meaning you can set them in an order such that you’re sure you’ll mention each one at least once. Here’s how.

0/1, 1/1, 1/2, 2/1, 1/3, 2/3, 3/3, 3/1, 3/2, 3/3, …

The trick is to make all the fractions you can just with 0 and 1; then with 0, 1, and 2; then with 0, 1, 2, and 3; then keep expanding outward, using one more integer each time and listing all the possibilities.

But suppose you add irrational numbers — all the square roots and cube roots and numbers you might not even be able to write down that way, like the number that satisfies the equation 4x⁴ + 7x³ – 6x² + 19x = 5. This set is called the “algebraic numbers”, and again we would think there is a greater infinity of algebraic numbers than counting numbers, but again our intuition fails. The infinity of algebraic numbers is the same as the infinity of counting numbers. The proof is an extension of what we just did.

Suppose you add in the numbers that don’t solve any algebraic equation, numbers like π and e. They are infinite, non-repeating decimals, but unlike √2, they are not solutions to any equation involving integers. These are called “transcendental numbers,” and indeed they cannot be “counted”. There is no ordering that you can make that would include all transcendental numbers. The number of all non-repeating decimals is an “uncountable infinity”, the next larger infinity after the counting numbers.

2. Countable statements, countable proofs

Any statement you can make about arithmetic can be coded using a small set of symbols. In addition to the digits, you have +, -, * and ÷.  With these you can make statements like “23 + 45 = 68”. Add a few symbols like ( and ). You can use ⊃ for “implies” and ∃…∋ for “there exists a number… such that” and ∀, meaning “true for all numbers” and ~ for “not”. Now you can code all the statements in the above list, and every other statement about integers.

The next step was to combine these symbols into statements about mathematics. Using the same trick we used for rational numbers, he made an (infinite) list of all possible mathematical statements. This is List B.

Note: The list is infinite, but a “countable” infinity. The point is that he could assign a unique integer to every possible logical/arithmetic statement.

Another note: Mathematicians use letters for variables, but there are only 26 of them, and Gödel needed an infinite supply. So he just used x with limitless subscripts — x₁, x₂, x₃, …

Yet Another note: The vast majority of statements in this list are nonsense. For example, “∃ x ∋ x+3=5” means “There exists a number such that when you add it to 3 the result is 5.” But  “∃⊃∀∀∀47” is just a meaningless string of symbols. These meaningless statements are a “waste” or inefficiency of our counting system, but what the heck — we have an infinite number of numbers, and we can afford to waste most of them, so long as we are sure we have covered all the meaningful statements.

Next step: Once you have a list of statements, you can construct a list of lists of statements. This is list C. Every possible proof is in our list. Every possible proof has a number assigned to it. Of course, most of the numbers don’t correspond to legitimate proofs. In fact, most of them don’t make any sense at all, but again, that doesn’t matter. Just so long as we are sure that every proof is assigned to a number, we don’t care that most of the numbers don’t correspond to a legit proof.

We’re almost done with the groundwork. One more list: This one is easier for us than for Gödel because we are familiar with computers and the concept of an algorithm is an everyday idea. A “function” is a set of procedures, taking an input number (or several input numbers) and doing something to them, adding or dividing, possibly doing something else with the result. We’ll need to add symbols for “if” and “then”, “and” and “or”. But then we can imagine listing every possible computer program that takes a list of integers as an input and yields an answer as an output. This is list D. D for “done with the groundwork”.

What can you do with all these lists?

This is where the magic begins. R & W were looking to prove that every true statement about integers has an associated proof. For Gödel to sink their boat, all he had to do was to come up with a single true statement about numbers for which no proof exists. Of course, it’s relatively easy to find statements about numbers that seem to be true because we can’t think of any counter-examples, but no proof has yet been discovered. But maybe there is such a proof, and no one has yet been clever enough to find it. How would you show that no proof is possible? That seems daunting.

Pick a number, any number. If it’s even, divide by 2. If it’s odd, multiply by 3 and add 1. Repeat. If you try this, you’ll find that whatever number you start with, you will always come back to 1. No one has found a number for which you don’t come back to 1 eventually. Why not? If you get to 1, then you cycle around 1, 4, 2, 1, 4, 2, 1, … forever. Certainly there must be other cycles in which you can get caught like this, going around endlessly without ever escaping back to a lower or higher number. No one has found such a cycle, and no one has explained the reason why.

Gödel’s strategy started with the numbering process we illustrated above. Every statement about numbers was assigned a number (list A). Every proof was assigned a number (list B). Every function was assigned a number (list C). (A functions is a sequence of operations and conditional directions that take some input numbers and yield an output, equivalent to an algorithm, or computer program.)

(In this article, I’ve given a general idea how to construct these three lists, but Gödel did so very explicitly, detailing the exact rules, so that given any statement, he could tell you what number it was on the list, and given a number on the list, he could tell you what statement (if any) corresponded to that number. For example, the rule for telling whether a given proof number corresponds to a given statement number was something Gödel could write out explicitly.)

Every statement about arithmetic has an associated number within arithmetic. So every proof of a statement about arithmetic corresponds to a proof about numbers, and that proof itself has an associated number.

The relationship between a statement and its proof is a relationship between two numbers — the number of the statement from list A and the number of the proof from list B. And all possible relationships between numbers are listed in list C, so somewhere in list C is the procedure for determining whether a proof is legit.

So now we have a glimmer of how we might prove that “no proof exists”. It’s equivalent to saying that we can find a number a (corresponding to a statement from list A) for which there is no corresponding number b (corresponding to a proof of that statement from list B).

Gödel could write a function (number c) that tells you (yes or no, 1 or 0) whether a list of statements (number  b) is a legitimate proof of statement number a. Using this, he could write a sentence  made of math symbols that says, for all numbers b, each and every one is not a proof of a given statement, number a. And that sentence is a statement, and so it has a statement number from list A.

Now, suppose that statement number happened to be a itself. Then the content of statement a would be that no proof of a exists. If statement a is true, we’re in just the kind of trouble that W & R hoped to avoid — it would be a true statement about numbers for which there was no proof. But suppose statement a is false. Then we are in much more trouble. All of math is in trouble, in fact, because it would mean that there does exist a proof of a even though a is false. A single inconsistency is fatal to any system of logic.

What is the number that corresponds to the statement, “there is no proof of this statement”?

The crux of Gödel’s idea was to create a mapping from statements about arithmetic to logical statements. Every logical statement had a counterpart in a statement about arithmetic (though not vice versa) so that he could come up with a statement about numbers that we know to be true because the corresponding logical statement is true, even though the statement can never be proved within the system of logic he started with.

I described how he went about this, but in the above description, I have swindled you in the crucial last step in this proof. We have a statement that has the symbol a in it, a generic number, and we want to substitute for the symbol a a specific number, a position within the list of all statements corresponding to the statement itself. We can calculate the number corresponding to the statement we have (with the symbol a), and put that number into the statement where the symbol a was. But as soon as we substitute that number for the symbol, we have changed the statement, so it has a different number. The number a corresponds to the statement that has the variable in it, but to make the statement really apply to itself, it has to have its own list number instead of the variable.

Gödel was able to close the gap in this proof because he knew the numbering system, and so he knew how changing from one symbol to another symbol would affect the number. He calculated this explicitly, and then was able to calculate the number of the statement that had its own proper statement number embedded. It’s analogous to what we do when we have an equation with x on both the left and right of the equation, but with a little algebraic manipulation we can “solve for x”.

So, the system of arithmetic contains just one true statement that can’t be proved?

We might protest: Fine. This is just one statement. Why not add it to the list of postulates, and now the system no longer contains statements that are “true but not provable from the postulates”. Gödel is ahead of us. Already in his first published paper, he shows that if we do this, then we can recreate his same proof, starting over with the expanded set of postulates, and come up with a different Gödel statement that is true but not provable. And so forth, if we added this new statement to our postulates. So we can’t have a complete body of provable theorems unless we’re willing to start with an infinite set of postulates.

This infinity of unprovable statements with expanded postulates are certainly not provable with the original set of postulates. So this logic shows there is not one but an infinity of true, unprovable statements about the integers.

Gödel’s incompleteness theorem

Gödel’s theorem is sometimes called the “incompleteness theorem” because it says our postulates are incomplete or, if you like, our knowledge of the integers must always be incomplete. It’s never called the “inconsistency theorem” because no mathematician wants to doubt that he can trust proofs. No one thinks it possible that the Gödel statement is actually false, but provable.

Impact — Sure, the transcendental poets and the romantic composers and the pointillist painters were already chipping away at the central claims of the Enlightenment in the 19th century. And the stunning appearance of quantum mechanics in 1926 confronted the objectivists with the reality that physics itself could never separate the observer from the observed.

But it was left to Gödel to show that mathematics — the core of the scientific worldview — was itself incomplete, and must forever remain so. The completion of Gödel’s revolution will be to integrate reason and the scientific approach with other human faculties such as intuition, faith, and clairvoyance. We are not yet there.