First, we’ll arbitrarily assign a natural number to each symbol of the alphabet of the formal system. We can do all we need to do in setting out a formal system of arithmetic if we restrict ourselves to just nine symbols, to each of which we’ll assign a Gödel number:
Basic sign Gödel Number Meaning
˜ 1 not
→ 2 if . . . then . . .
x 3 variable
= 4 equals
0 5 zero
s 6 the successor of
( 7 punctuation mark
) 8 punctuation mark
′ 9 prime
The quantificational notion of “all” is represented by using parentheses and variables. So, for example, (x)F(x) means: all x’s are F. The prime allows us to generate additional variables: x, x′, x′′, x′′′, etc. Since we have a symbol for 0, and a way of indicating successors, we have a way of indicating all the natural numbers.
We now specify a rule for assigning Gödel numbers to wffs, which of course are just sequences of the symbols of the alphabet. We adopt the easiest rule possible, reminiscent of the encoding my friends and I used in elementary school. We simply plug in the Gödel number for each symbol in the wff and that will be the Gödel number for the wff.
So consider this wff:
(p1) (x) (x′)((s(x) = s(x′)) → (x = x′))
Assuming our universe of discourse (the objects to which the variables are interpreted to be referring) is the natural numbers, what p1 says is that if two numbers have the same successor, then they’re the same number. Or, in other words, that one number can’t be the successor of two different numbers. More literally: for all x and for all x′, if the successor of x is identical to the successor of x′, then x is identical to x′.
Now we’re going to turn this wff into a number by just consecutively going along and replacing each symbol in the wff by its Gödel number. Every symbol in the formula p1 has been assigned a number: the open parenthesis a 7, the x a 3, the close parenthesis an 8, the tilda a 1. Replacing each element of the formula with the corresponding Gödel number yields a large number, which is the Gödel number for the wff. Abbreviating “the Gödel number of the proposition p1” by GN(p), we obtain:
GN(p1) = 738739877673846739882734398
In this way Gödel numbers are assigned to wffs, which are sequences of symbols, and hence to propositions, which are just special wffs. In the same way, Gödel numbers can be assigned to sequences of propositions, and in particular to potential proofs, which are, after all, just sequences of propositions, using the Gödel numbers already assigned to propositions. Bookkeeping! In our simplified version, the Gödel number of a sequence of propositions (a potential proof) is obtained basically by putting the Gödel numbers of the sequenced propositions together; however, since it is important to be able to unambiguously extract from the number obtained the original sequence of propositions, we’ll need some sort of signal that will indicate where one proposition ends and the next one begins—sort of like a carriage return on a typewriter. We’ll let 0 function as our carriage return, indicating that we now go to a new line in the proof.
So, let us say that in a particular sequence of propositions, p1 is followed by p2, where p2 is defined as:
(p2) s(0) = s(0)
The Gödel number that will correspond to the sequence of p1 followed by p2 is
GN(p1, p2) = 7387398776738467398827343980675846758
Through Gödel’s inspired contrivances, all of the logical relations that hold between propositions in the formal system become arithmetic relations expressible in the arithmet-ical language of the system itself. This is the essence of the heart-stopping beauty of the whole thing. So if, for example, wff1 logically entails wff2, then GN(wff1) will bear some purely arithmetical relation to GN(wff2). Suppose, say, that it can be shown that if wff1 logically entails wff2, then GN(wff2) is a factor of GN(wff1). We would then have two ways of showing that wff1 logically entails wff2: we could use the rules of the formal system to deduce wff2 from wff1; or we could show that GN(wff1) can be obtained from GN(wff2) by multiplying by an integer. Suppose that GN(wff1) = 195589 and GN(wff2) = 317. 317 is a factor of 195589, since 317 multiplied by 617 = 195589. So that wff1 logically entails wff2 could be demonstrated either by using the formal rules of proof to arrive at wff2 from wff1, or, alternatively, by using the rules of arithmetic to arrive at GN(wff1) = 195589 by multiplying 617 by 317 = GN(wff2). The metasyntactic and the arithmetic collapse into one another.
Once one has this sort of collapse between logical implication and arithmetical relationship, we can go on and demonstrate that certain sequences of wffs—precisely those that constitute proofs—have an arithmetical property expressible in the system. Proofs, of course, are built up out of logical entailments. So deriving this arithmetical property (of the Gödel numbers of all and only the proofs in the system) is going to be a consequence of the sort of collapse discussed in the previous paragraph. The Gödel number of those strings of wffs that are valid proofs within the system will have some sort of arithmetical property, say, they’ll all be even or they’ll all be odd or they’ll be prime numbers or the squares of primes or, more likely, a property a good deal more complicated. In other words, the metasyntactic relationship of provability will become an arithmetical relationship; that a string of wffs is a proof will be some property of numbers. From this it becomes possible to show that all and only the provable wffs in the system, the theorems, have a certain arithmetical property. You can see where we’re heading: toward arithmetical propositions expressible in the system that also speak to the issue of their own provability within the system. The Gödel numbering allows some propositions to engage in an interesting sort of double-speak, saying something arithmetical and also commenting on their own situation within the formal system, saying whether they’re provable.
The double-speak of these propositions could be compared to the sort of thing that sometimes happens within a dramatic play, in particular when the play presents actors as characters, with their own “real-life” relationships, and then presents these characters as actors in a play within the play. Through careful contrivance, the lines that the actors speak, in the play within the play, can also be interpreted as having a real-life meaning in their relationships outside the play within the play (in the play proper). Gödel’s strategy asks us to grasp something analogous to what the country audience in Leoncavallo’s opera I Pagliacci grasp when they understand the actors to be delivering lines that, as well as making sense within the play, have a meaning in their offstage lives (in the opera). In Gödel’s inspired stage production, lines speak both to the formal relationships within the system, the play within the play, and also reveal real-life arithmetical relationships. The proposition that Gödel’s proof constructs, the one that will simultaneously announce both its own (provable) unprovability and a true (unprovable) arithmetical relationship, has the same sort of double-entendre as Pagliacci’s final tragic cry, “La commedia è finita!”—the comedy is over.
Step Three: Create a Proposition That’s True Because It Says That It’s Unprovable
Having established his ingenious layers of meaning, Gödel now conjures a rather amazing arithmetical property, which we’ll designate as “Pr,” for “provable.” Because, although Pr is a purely arithmetical property, it’s also that very property toward which all the contrivances have been heading. It’s an arithmetical property that is true of all and only the Gödel numbers of the provable propositions of the system. I choose the verb “conjures” deliberately because even though the collapse of the metasyntactic and arithmetical was heading toward “Pr,” there is still a sense of magic about the entrance of Pr.
Before getting to the property, one little technical point about the way in which properties are specified: by propositional functions of one variable. These can be thought of as of the form F(x). These are expressions in the formal system involving a single variable—the x which is a dummy standing for a whole range of possible valu
es (the domain of individuals) that can be plugged in; if you plug in a value for the variable, you end up with a wff that is either true or false, in other words a proposition. F(x), just as it is, is neither true nor false. So say F(x) were to mean: x is the successor of 1. This is neither true nor false; it isn’t a proposition, a definite statement, since what it says depends upon what x actually represents. Plugging in 2 for the variable x yields a true proposition, and plugging in anything else yields false propositions. That’s how properties are designated in the system, by propositional functions of one variable.
Now onward to Pr(x), which is a somewhat complicated property of numbers. Remember, first of all, that each of the wffs in the formal system have been assigned numbers through the wonders of Gödel numbering. So for every wff p, we have some GN(p), some natural number or other. The theorems are a special subset of the wffs of the system, the provable propositions. Given any natural number n, then, it may or may not be the case that it corresponds to some theorem in the formal system, that is, it may or may not be the case that n = GN(p) for some proposition p which is a theorem of the formal system.
Now we are in position to define Pr(x). The possible values for this propositional function, the things we plug in for the dummy x, are (the expressions for) the natural numbers. For any natural number n, if n = GN(p) for a theorem p of the system then we say that n satisfies the property Pr(x), that is, that Pr(n) is true. Gödel showed that this property is one that can in fact be expressed in the formal system, that is, that it’s an example of an F(x). Pr(x) is a formally expressible arithmetical property, albeit one that is extremely complicated, not anything that we can explicitly give here. But by means of this property Gödel is able to take metasentences about the system, stating which propositions are theorems of the system, and transform them into arithmetical sentences within the system: “p is a theorem” is transformed into “Pr(GN(p)).” To say of some particular n that it has the property Pr(x) is to say that this number corresponds to a theorem in the formal system.
Now perhaps you’re thinking something like this: That a particular number n has the property Pr(x) isn’t a real property of n. The number n, for example, may be even or it may be odd; if it’s divisible by 2 then it’s even. Let’s say it is. Then its evenness is a real arithmetical property; n couldn’t be the number it is if it weren’t even. In contrast, looking at this property Pr(x) metasystematically, it doesn’t seem at all a proper sort of numerical property. A number n has this property only arbitrarily, since the proposition with which n is associated is arbitrary, a consequence merely of the way in which the Gödel numbering was set up, the inspired contrivances.6 True enough, but, arbitrary though it may be, Pr(x) is nonetheless a real arithmetical property, and a number n either will or won’t have it. And n wouldn’t be the number that it is unless it either did or didn’t have it. Just because Pr(x) has a metameaning doesn’t detract from its arithmetical character. This property Pr(x) is, in fact, stupendous, and it allows us to take the plunge into the heart of the proof.
What we use next is something called the diagonal lemma. It’s a general statement, a particular case of which is what we need to prove Gödel’s theorem. (Gödel didn’t actually use it, but rather derived the particular case.) Making use of this general lemma (which, of course, we’re not going to prove) will simplify matters enormously.
The diagonal lemma states that the Gödel numbering is such that for any propositional function F(x) of one variable, there exists a number n such that the Gödel number of F(n), the proposition we get when we plug n into the function F(x), turns out to be n itself. (That there must exist such a number for each F(x) may suggest what superhuman efforts went into the Gödel numbering.) In other words, the diagonal lemma asserts that for any F(x) there is an n such that
n = GN(F(n)) (0)
The number you get out is the same number you started with, and so the special n associated with a given F corresponds precisely to where the graph of y = GN(F(x)) intersects the diagonal, the graph of y = x, namely where x = n. Hence the name, the “diagonal lemma.”
(N.B. The statement n = GN(F(n)) is in the metalanguage. It’s a “normal statement” (i.e., not a formal statement) and n on the left denotes a (normal) natural number. However, the n on the right represents the expression in the formal system that represents the number n, namely s(s(s( . . . s(s(0))))), with n occurrences of s.)
Notice that the number n that the diagonal lemma associates with the propositional function F(x) is such that the proposition with Gödel number n (namely F(n)) says that n itself has the property F. It is, roughly speaking, of the form: this very sentence is F. Soft whispers of self-referentiality are hovering in the hushed air.
Now let’s go back to that stupendous property that Gödel produced, Pr, which is true of all and only the Gödel numbers of the theorems, the provable wffs, of the system. A number will have the arithmetical property Pr if and only if it corresponds to a provable proposition under the Gödel numbering. In other words:
Pr(GN(p)) if and only if p is provable
We have the metasyntactic sense of what Pr(x) means (though not what its arithmetical meaning is; you just have my assurance that it has an arithmetical meaning). Now let’s look at the property:
∼ Pr(x)
This second property will be true of all and only the Gödel numbers of nontheorems; that is, it is true of the Gödel numbers of objects that are not propositions provable in the system. In other words:
∼ Pr (GN(p)) if and only if p is not provable (1)
What kind of sentence is (1)? It is a metamathematical sentence. It’s not itself a sentence of the formal system, nor an arithmetical sentence. But by means of (1) we can transform some metamathematical sentences into arithmetical sentences.
Now the diagonal lemma concerns any propositional function F(x), so let’s apply it to F(x) = ∼Pr(x). The diagonal lemma, remember, states that for any propositional function F(x) of one variable, there exists a number n that is the Gödel number of the very proposition we get when we plug n itself into the function. We’re now considering the propositional function ∼Pr. According to the diagonal lemma there is some number, let’s call it g, such that:
g = GN(∼Pr(g)) (2)
We arrived at (2) by replacing F by ∼Pr and n by g in (0). Equation (2) says that g is the Gödel number of the proposition that states that the number g lacks the arithmetical property Pr (which belongs to all and only those numbers which are Gödel numbers of provable propositions).
Now we’re ready to frame our proposition G. Let
G = ∼ Pr(g) (3)
The proposition G states that the number g lacks the property Pr. Moreover, by (2) and (3), we have that:
GN(G) = g
Now we go back to (1) and make some substitutions. Here’s (1) again:
∼ Pr (GN(p)) if and only if p is not provable
Letting p = G in (1), and using the fact that GN(G) = g, we obtain:
∼Pr(g) if and only if G is not provable (4)
That is, using again (3), G if and only if G is not provable. What (4) is saying is that G is true if and only if G is not provable!
G is, of course, a purely arithmetical statement, but it’s also simultaneously talking about itself, and what it’s saying is that it’s not provable. Is what it’s saying true? Well, it could hardly be false since then it would have to be provable and hence true anyway. That is, unless, of course, the formal system of arithmetic is inconsistent, so that all its propositions would be provable, even contradictions. This is the point in the proof where that presumption of the consistency of the formal system is being called upon to stand up and deliver. And it does. G is both unprovable and, given that that’s what it says, it’s also true. We haven’t shown that it’s true by finding a proof for it within the formal system, using the purely mechanical rules of that system, that is, by deducing it. Rather, we’ve shown it’s true by, ironically, going outside the system and showing that no proof for
it can be produced within the formal system. We’ve shown that G is true by showing that it can’t be proved, just as it says.
Moreover, Gödel in fact showed how to construct a true but unprovable proposition, not just for the formal system of arithmetic we have been discussing but for any formal system whatsoever containing arithmetic. So if we should try to weasel our way out of Gödel’s first incompleteness theorem by constructing a new formal system that has G appended as an axiom, a new problematic proposition can be constructed for that system. And so on, ad infinitum. There are provably unprovable but nonetheless true propositions in any formal system that contains elementary arithmetic, assuming that system to be consistent.
And that is Gödel’s first incompleteness theorem.
The Second Incompleteness Theorem
The second incompleteness theorem states that the consistency of a formal system that contains arithmetic can’t be formally proved within that system. It would seem to follow, pretty straightforwardly, from the first. Remember that the first incompleteness result has the form of a conditional statement: if the formal system of arithmetic is consistent, then G is unprovable. Let C stand for the proposition: “The formal system of arithmetic is consistent.” So the first incompleteness theorem tells us: if C, then G is unprovable. The arithmetization of the proposition “G is unprovable” is, of course, G. So what the first incompleteness says is: C → G, and this conclusion was proved within the formal system of arithmetic. So if we can go on and prove C within the formal system of arithmetic, we would ipso facto be proving G within the formal system of arithmetic, since we’ve proved C → G. And since G has been proved unprovable within the formal system of arithmetic, we know that C, too, is unprovable in the formal system of arithmetic.
And that is Gödel’s second incompleteness theorem.
Incompleteness Page 15
