I just pulled that title out of thin air because it sounded dramatic. Also, it’s a lot less geeky than How I stopped worrying and learned to love that we cannot prove mathematics is not self-contradictory but instead rests on a set of axioms that we insist ought to be true.
Perhaps you ended up here after an AI or web search. Or maybe you saw a link somewhere and just got curious. If you fall into this category and have no background in logic or math, then allow me to summarize this post. In the late nineteenth century, the German logician Gottlob Frege pretty much invented modern logic. He had a wild idea. He believed that mathematics could be reduced to pure logic. At the dawn of the twentieth century, British mathematician Bertrand Russell discovered a lethal contradiction in Frege’s logic. This contradiction is called Russell’s Paradox. Frege never recovered. Russell built a theory of types that he believed firewalled his own system from contradiction. This too proved to be short-lived. In 1931, Austrian mathematician Kurt Gödel was able to generate unprovable formulas in Russell’s system. The logicist program was already straining under the load of controversial ad hoc axioms. Gödel’s proof was the straw that broke the camel’s back. He showed that despite our best efforts we can never provide a secure foundation for mathematics.
That’s the summary of this post. You can now be forgiven if you move on with your life. Otherwise, if you’re up for a deeper dive read on!
Russell’s Paradox
It was Frege’s Axiom V that famously led to Russell’s Paradox. Flash Sheridan presents it in the standard expression of first-order logic:
For an arbitrary predicate ϕ with y not free in ϕ, ∃y ∀x. x ∈ y ⇔ ϕ(x)
Scott Soames has the same expression of the axiom with the letter F instead of the Greek phi:
∃y ∀x (Fx ⇔ x ∈ y)
This states formally “there exists a set y such that for all x, x satisfies the property F if and only if x is a member of y” (p. 140). To “satisfy” property F is to say that the predicate F is true. For example, if F is the property of “being a widget,” the axiom states there exists a set (y) that contains all widgets. An object (x) is a member of the set (x ∈ y) if and only if the object is a widget (Fx).
The problem with Axiom V is if every property necessarily leads to a defined set, then what happens if I define a set S as the set of all sets that do not contain themselves? Does S contain itself? If so, then S is a member of S (S ∈ S). But our definition says that S only contains sets that do not contain themselves, so S cannot be a member of S (S ∉ S). Both can’t be true. This is Russell’s Paradox.
Both Soames and Sheridan offer similar formal proofs to illustrate it. Here is Sheridan’s version:
(1) Replace Fx with x ∉ x
(2) We obtain ∃y ∀x (x ∈ y ⇔ x ∉ x)
(3) Since the scope is for all x (∀x), we can test where x is the set y itself. Instantiating y and substituting y for x we obtain y ∈ y ⇔ y ∉ y
Step 3 says “y is a member of itself if and only if y is not a member of itself.” This contradiction cannot be true so something is wrong with Frege’s underlying system. The paradox is possible because Fx can take any formula over the range of everything (∀x). It is too permissible.
Notice how the free variable x in Step 2 is substituted. This same maneuver will come up again in Gödel’s proof where he substitutes a free variable with an encoded integer, leading once again to self-reference. But for now, Russell believes he can guard against self-reference in his system with the theory of types.
Theory of Types
Bertrand Russell and Alfred North Whitehead considered the Principia Mathematica (PM) to be complete. Because they believed mathematics could be reduced to logic, their system could prove every mathematical truth using logical expressions. Russell believed his own paradox had been mitigated by the addition of his Theory of Logical Types (PM *12).
The theory creates a strict hierarchy to prevent self reference:
Level 0: Base objects (variables and numbers like x, y, z … 0, 1, 2, …)
Level 1: Statements about base objects (e.g., 2 + 2 = 4)
Level 2: Statements about Level 1 statements (e.g., “the formula 2 + 2 = 4 is a theorem”)
A level 1 statement can never talk about another level 1 statement. It can only talk about level 0 base objects. Consider the expression ∀x ϕx which says “all values of ϕx are true.” We saw above what happens if x takes on anything that might be self-referential. So the theory of types introduces a “range of significance” that says function ϕ can take only certain values of x if it is to be meaningful.
In this case, the free variable x is a level 0 base object while ϕ is a level 1 statement about x. I can denote this hierarchy visually with subscripts:
∀x0 ϕ1 (x0)
Now the syntax shows the hierarchy. The level 1 function ϕ1 is only allowed to accept a level 0 variable x0. Anything else is meaningless. Russell’s types were the basis for modern strongly-typed programming languages like Java or C#. Today, I might write a function like this:
bool IsOdd(int x)
{
return x % 2 != 0;
}
That would return the following outputs:
IsOdd(3); // True IsOdd(4); // False
If I try to pass in an invalid type the compiler will fail and report an error:
IsOdd(“widget”); // nope! wrong type
The string of characters “widget” is outside the range of significance for the function. Of course, there were no compilers or programming languages in 1910 when the PM was published. Russell’s theory states that a type violation is logically meaningless, which means it cannot take on a value of true or false. Alfred Tarski noted, the “theory of types was thought of chiefly as a kind of prophylactic to guard the deductive sciences against possible antinomies” (p. 215). With his theory of types, Russell believed he had prevented self-referential statements that generated paradoxes. This belief would prove to be short lived.
Gödel’s Proof
Kurt Gödel demonstrates that the theory of types fails to prevent self-reference. He accomplishes this with a mathematical Trojan Horse. Smuggled inside the belly of a valid logical statement, Gödel places an ordinary looking integer that is actually an encoded value of the statement’s own identifier. This integer sneaks past Russell’s guard and shows that there exists in PM a true statement that cannot be proved within the system itself. This makes the system incomplete. I’ll walk through this one step at a time following chapters 6 and 7 of the book Gödel’s Proof by Nagel and Newman.
First, it helps to understand what a demonstration is in mathematics. A demonstration (or “dem”) is a formal presentation of a proof. For example, Euclid’s Theorem states that prime numbers are infinite. He demonstrated this theorem with these steps:
Step 1: Let a, b, and c be a set of consecutive prime numbers.
Step 2: Multiply a, b, and c together and add 1. Let’s call this new number n.
Step 3: Every positive number must be divisible by at least one prime number; however, n cannot be divided by any prime number without leaving a remainder of 1.
Therefore, either n itself is a new prime number, or it is divisible by a prime number not on the list. Either way, a new prime number is found and we can add it to the list.
To see this, let’s plug in concrete values for the free variables a, b, and c. Take the first three primes: 2, 3, and 5. Multiply them and add 1: (2 * 3 * 5) + 1 = 31. If we test, 31 cannot be divided by 2, 3, or 5 without leaving a remainder of 1. In this case 31 is a new prime number. We can add it to our list and repeat the exercise over and over and there will always be new prime numbers. Therefore, prime numbers are infinite.
Euclid’s proof can be put in the form Dem (x, z) where x represents the three steps of the proof, and z the conclusion. Similarly, Gödel puts his proof in the form Dem (x, z). Only he wants to deny that x proves z. So using the logical symbols of PM we can say that:
~(∃x) Dem (x, z)
This logical statement says “there does not exist a demonstration that x proves z.” For the purposes of Gödel’s proof, this says “there does not exist a sequence of steps (x) that demonstrates the conclusion (z).” In plain English, Gödel is saying that formula z is unprovable within PM.
Before we get to unprovability, I need to talk about Gödel numbering. I mentioned at the outset that Gödel is going to smuggle an ordinary-looking encoded integer into the logical statement. He will do it by substituting variable z with this integer. So let’s look at how he calculates this value.
Gödel Numbering
Gödel first creates a map that is keyed to various logical constants and variables in PM. Here is a similar one that Nagel and Newman created in Chapter 7:
| Logical Constant |
Gödel Number |
Description |
|---|---|---|
| ~ | 1 | negation (not) |
| ∨ | 2 | or |
| ⊃ | 3 | implies (if… then…) |
| ∃ | 4 | existential quantifier (there is) |
| = | 5 | equals |
| 0 | 6 | zero |
| s | 7 | immediate successor of |
| ( | 8 | open parentheses |
| ) | 9 | closed parentheses |
| , | 10 | comma |
| + | 11 | addition |
| * | 12 | multiplication |
| x | 13 | numerical variable |
| y | 17 | numerical variable |
| z | 19 | numerical variable |
We can use this map to create any Gödel number for a single symbol like “x”, a whole formula like ~(∃x) Dem (x, z) or even a sequence of formulas that make up the steps of a proof. Per Nagel and Newman:
“Gödel first showed that it is possible to assign a unique number to each elementary sign, each formula (or sequence of signs), and each proof (or finite sequence of formulas). This number, which serves as a distinctive tag or label, is called the ‘Gödel number’ of the sign, formula, or proof” (p. 69).
Encoding
Take a simple example. Let’s say we want to express the identity statement “zero is zero” or 0 = 0. We first map the symbols to the Gödel number from the table above:
| Symbol | 0 | = | 0 |
| Gödel Number | 6 | 5 | 6 |
Then starting with the first prime number (2) we successively raise each prime number to the power of its corresponding Gödel number and then multiply them all together. Recall that prime numbers begin with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and so on. Here I’ve added another row to show successive primes, beginning with 2, that will go into the calculation:
| Symbol | 0 | = | 0 |
| Gödel Number | 6 | 5 | 6 |
| Prime Number | 2 | 3 | 5 |
We now have what we need for our calculation:
n = 2⁶ * 3⁵ * 5⁶ = 64 * 243 * 15,625 = 243,000,000
The integer 243,000,000 is now an encoded statement of 0 = 0. It can be decoded back into the original form. The fundamental theorem of arithmetic states that every integer greater than 1 is either a prime number or can be written as the product of prime numbers. That means the three Gödel numbers can be recovered or decoded from n:
(1) 243 * 1,000,000 = 243 * 10⁶
(2) 10⁶ = (2 * 5)⁶ = 2⁶ * 5⁶
(3) 243 is not divisible by the first prime 2. It does divide sequentially by 3 five times:
243 / 3 = 81
81 / 3 = 27
27 / 3 = 9
9 / 3 = 3
3 / 3 = 1
(4) So 243 = 3⁵
Grouping all prime factors in order we get 2⁶ * 3⁵ * 5⁶ which maps the Gödel numbers back into the logical symbols again:
| Gödel Number | 6 | 5 | 6 |
| Symbol | 0 | = | 0 |
We’re now ready to look at Gödel’s proof. We start with Dem (x, z) which says x is a proof of z. And then deny it with ~(∃x) Dem (x, z) which says there is not an x which can prove z.
Now we get to the tricky part. Gödel introduces a function called Sub which does the same thing as a word processor’s search and replace tool. Suppose I have the word “Napoleon” and I replace the letter “p” with the entire word itself. It will look like this: NaNapoleonoleon. You can see that the word “Napoleon” has replaced the letter “p” to produce a longer mashup string. For Gödel the Sub function takes three variables:
Sub (a, b, c)
Where a is the target Gödel number of the formula to be edited, b is the Gödel number of the variable inside of a to be found and replaced, and c is the Gödel number you want to paste over b in order to replace it. Nagel and Newman use an example formula m = (∃x) (x = sy) which means “there is an x such that x is an immediate successor of y” (p. 75). In other words, if y = 2 then there must be an x = 3. And if y = 3 there must be an x = 4. And so on. The substitution Sub (m, 17, m) means, just like with the Napoleon example, a search and replace is done in the formula where y is replaced by m:
m = (∃x) (x = sy)
(∃x) (x = sm)
This says there is an x such that x is the immediate successor of m. Notice that m has substituted y with a copy of the formula itself so that the formula now points to itself.
Suppose for simplicity that m is the integer 1,001,001. The formula would read (∃x) (x = s1001001) which is saying that there is an x that is the immediate successor of the number 1,001,001. That is of course 1,001,002. What is the point? Why do this? The point is to illustrate that there is a way for a formula to talk about itself. By substituting y with m we’re saying that the formula itself can become a value that feeds back into itself. It shows that despite our best efforts at preventing it, mathematics (like logic) can be recursive and self-referential.
Now let’s leave that example behind and turn to Gödel’s proof that a metamathematical statement can be unprovable. This begins with the formula ~(∃x) Dem (x, z) which then includes the Sub formula so that:
~(∃x) Dem (x, Sub(y, 17, y))
Notice what is going on here. We’ve replaced the free variable z from ~(∃x) Dem (x, z) with the Sub function. Why the number 17? Recall from the table above that 17 is the Gödel number for the variable y. So like my Napoleon example where I replaced the letter p with the word itself, here we’re going to replace the encoded number for y (17) with yet another calculated Gödel number.
That substitution for y (17) will be the encoded Gödel number of the entire formula. I’m not going to do the math because the value of this number is not only astronomical but unimportant for our purposes. Let’s call this value n. We then substitute the encoded variable y with the definite value n. This gives us:
~(∃x) Dem (x, Sub(n, 17, n))
This is Formula G. It says there is not an x that can prove the formula for Sub(n, 17, n). But notice that Sub(n, 17, n) is the mathematical operation that calculates the Gödel number of Formula G. What the formula really says in plain English:
There is no proof for the formula with the Gödel number that belongs to this formula.
The “Gödel number that belongs to this formula” is Sub(n, 17, n). Formula G now sits inside Formula G and declares that it itself is unprovable. We’re right back to a twist on Russell’s Paradox. Only instead of saying “this statement is false,” Gödel is showing that “this statement is unprovable.” But how did it sneak past Russell’s type theory? It did it by taking a Level 1 formula and encoded it into a harmless looking Level 0 integer. The formula hid in the belly of the Trojan Horse until it got to the other side of the gate.
Formula G claims that it is unprovable. Why is this significant? Well, if the claim is false, then it is provable. A mathematically sound system cannot prove a false statement. Therefore, Formula G cannot be false and must be true. But we just walked through a demonstration showing that we cannot generate a proof for Formula G. In the end, we are faced with a true statement that cannot be proved. This is what makes the system incomplete.
Notes
Nagel, Ernest and Newman, James R. Gödel’s Proof, Revised Edition (Douglas R. Hofstadter, Ed.), New York University Press (2001).
Soames, Scott. Philosophical Analysis in the Twentieth Century (The Dawn of Analysis, Volume 1), Princeton University Press, 2003.
Tarski, Alfred. Logic, Semantics, Metamathematics (Papers From 1923 to 1938), 2nd Edition, “Concept of Truth in Formalized Languages” J. H. Woodger, Trans., John Corcoran, Ed., Hackett Publishing Company, 1983.
Whitehead, Alfred North and Russell, Bertrand. Principia Mathematica to *56, Cambridge University Press, 1910 (Reprint 1978).
I used Google’s Gemini to help brainstorm structural transitions, act as an editorial assistant, proofreader, and format the HTML tables for this post.