In the previous post we looked at the system of Gödel numbering that allowed Gödel to map any natural number to a unique mathematical expression. In this post we will look at how Gödel succeeded in using this system of numbering to make mathematical statements refer to themselves.
First remember that Gödel used the following mapping as the foundation of his numbering system:
Let us build Gödel’s proof slowly and one step at a time. Consider the mathematical statement ~(s0=s0). Recall that s0 means the successor of 0, namely the number 1. Hence, this statement in English would be “1 is not equal to 1”. Using the mapping above, the initial Gödel numbers are 1, 8, 7, 6, 5, 7, 6, 9. Since there are eight numbers here, the corresponding Gödel number for the statement will be 21×38×57×76×115×137×176×199. This is obviously a very large number and we will not both ourselves with calculating it. Let us just label it as N. Note that the statement ~(s0=s0) is a false statement. Despite this, it has a Gödel number, namely N.
Now consider the statement “The second symbol in the statement ~(s0=s0) is a left parentheses.” This is obviously a true statement. This is a metamathematical statement about the statement ~(s0=s0), namely that its Gödel number (N) has a partial prime factorization of 38 since 3 is the second prime (corresponding to the second symbol) and 8 is the Gödel mapping for ‘(‘ as seen in the table above.
In effect what we are saying is that 38 is a factor of N but 39 is not. We can convert this sentence into precise English to obtain the sentence “There exists some integer x such that x multiplied by 38 is equal to 21×38×57×76×115×137×176×199, and there does not exist any integer x such that x multiplied by 39 is equal to 21×38×57×76×115×137×176×199.” If we convert this to mathematical symbols we will get
where ss … ss0 contains as many repetitions of s to get us to 38, ss … ss0 contains as many repetitions of s to get us to 39, and ss … ss0 contains as many repetitions of s to get us to 21×38×57×76×115×137×176×199.
Of course, since the above statement contains only the symbols used in the Gödel mapping system, it has a Gödel number.
But note what we have done. We have managed to convert a metamathematical statement about the original statement ~(s0=s0) into a pure number using the system of Gödel numbering.
Now, any mathematical proof is nothing but a sequence of mathematical statements. Each of the statements can be mapped onto its own Gödel number. But also every sequence of statements can also be similarly mapped. Potentially, we could consider a statement like “There exists some sequence of statements with Gödel number M that proves the statement with Gödel number K.” In common English this would translate to “The statement with Gödel number K can be proved.”
What Gödel did now was substitute a statement’s own Gödel number into the statement itself. Let us see how this is done.
Consider the statement (∃x)(x = sy). What this says is “There exists a number denoted by the variable x such that x is the successor of the number denoted by the variable y.” In short “y has a successor.” Quite obviously, this statement has a Gödel number, which we will designate as p. Now let us substitute p in place of y to get (∃x)(x = sp), or “p has a successor.” This statement too has its own Gödel number. But it is not any arbitrary number. Rather, it is related to y and p. We began with a statement with a Gödel number p. Then we replaced the variable y with the number p. And the variable y maps onto the number 17. Hence, we can denote the new Gödel number as replace(p, p, 17), which reads “In the statement with Gödel number p replace with p the symbol which maps to the number 17.”
Now consider the statement “The statement with Gödel number replace(y, y, 17) cannot be proved.” Now, the statement with Gödel number replace(y, y, 17) is taking the statement with Gödel number y (at present just an unknown variable), and replacing with the variable y any occurrence of the symbol y (which maps to 17).
Take a breather here because we have obtained a metamathematical statement in which the letter y is being used in three different ways! Grab a coffee and croissant and come back when you have mulled this over sufficiently!
So we have the metamathematical statement “The statement with Gödel number replace(y, y, 17) cannot be proved,” for which we can calculate a Gödel number, say q.
Now Gödel forms a new statement by substituting the number q wherever y occurs in the earlier statement. The new statement is “The formula with Gödel number replace(q, q, 17) cannot be proved.” Let us denote this statement with G. Quite obviously G also has a Gödel number. What is it?
By definition replace(q, q, 17) is the Gödel number of the statement that results from taking the statement with Gödel number q and replacing with q wherever there’s a symbol with Gödel number 17. But this is exactly how we obtained G! Because of the uniqueness of prime factorization, we now see that the statement G is referring to is none other than G itself.
What G asserts is that it cannot be proved! Quite obviously we have obtained a statement whose truth value cannot be determined. If it could be determined then we would be able to prove that the statement “This statement cannot be proved” can be proved, which yields a logical contradiction.
Hence, even though we know in out guts that G cannot be proved, we will be unable within the system of mathematical logic to prove it. Hence, the truth value of G from within the system of mathematical logic is undecidable.
What we have obtained is a true statement that cannot be proved, yielding to the conclusion that the system of mathematical logic is incomplete.
We have explained (hopefully!) Gödel’s first theorem that any consistent mathematical system is incomplete. His second theorem states that no mathematical system can prove its own consistency.
Suppose that a mathematical system can prove its own consistency. Then there would exist a sequence of mathematical statements that could be distilled into the English statement “This set of mathematical axioms is consistent.”
However, by the first theorem we know that the set of axioms is incomplete. Consider the statement “this set of axioms is incomplete.” This is equivalent to saying “There are true statements that cannot be proved.” But this last statement is logically equivalent to G!
What we have here is a contradiction. If the mathematical system could prove its consistency, it could prove G. But G cannot be proved. Hence, no set of axioms can prove its own consistency.
The repercussions of Gödel’s theorems cannot be exaggerated. Prior to that mathematicians like Georg Cantor, David Hilbert, and Bertrand Russell were hoping to develop a self-contained system of mathematics that was both complete and consistent. Gödel’s theorems put paid to those efforts. What he showed was that any mathematical system that can perform basic arithmetic can be made to refer to itself. And once that happens all sorts of self-referential statements can be framed, which can be paradoxical or contradictory, resulting in incompleteness and inability to prove consistency.
But in a very real sense, it forced mathematicians to focus elsewhere rather than on developing a more mechanistic kind of mathematics. For example, despite framing the famous Russell’s paradox within set theory, Russell nevertheless partnered with Alfred North Whitehead to write the Principia Mathematica (PM), choosing the weaker Zermelo-Fraenkel (ZF) set theory specifically to prohibit paradoxes. Gödel’s theorems show that, since ZF is powerful enough to perform basic arithmetic, it is necessarily incomplete and cannot prove its own consistency, thereby rendering one of the main goals of PM unrealizable. And the world is richer for it!
Leave a comment