Gödel, Escher, Bach: An Eternal Golden Braid (80 page)

Falsehood

<==>

nontheoremhood

quotation of a phrase

<==>

preceding a predicate

<==>

definite term) into an open formula

by a subject

preceding a predicate

<==>

substituting the Gödel number of a

by a quoted phrase

string into an open formula

preceding a predicate

<==>

substituting the Gödel number of an

by itself, in quotes

open formula into the formula itself

("quining")

("arithmoquining")

yields falsehood when quined

<==>

"uncle" of
G
”

(a predicate without a subject)

the(an open formula of
TNT

"yields falsehood when quined"

<==>

the number a (the Gödel number

(the above predicate. quoted)

of the above open formula)

"yields falsehood when quined"

<==>

G itself

yields falsehood when quined

(sentence of TNT formed

(complete sentence formed by

by substituting a into the uncle, i.e.,

quining the above predicate)

arithmoquining the uncle)

Gödel’s Second Theorem

Since
G
's interpretation is true, the interpretation of its negation --
G
is false. And we know that no false statements are derivable in
TNT
. Thus neither
G
nor its negation -
G

can be a theorem of T
N
T. We have found a "hole" in our system-an undecidable proposition. This has a number of ramifications. Here is one curious fact which follows from
G
's undecidability: although neither
G
nor -
G
is a theorem, the formula <
GV -G
> is a theorem, since the rules of the Propositional Calculus ensure that all well-formed formulas of the form
> are theorems.

This is one simple example where an assertion inside the system and an assertion about the system seem at odds with each other. It makes one wonder if the system really reflects itself accurately. Does the "reflected metamathematics" which exists inside
TNT

correspond well to the metamathematics which we do? This was one of the questions which intrigued Gödel when he wrote his paper. In particular, he was interested in whether it was possible, in the “reflected metamathematics”, to prove TNT’s consistency.

Recall that this was a great philosophical dilemma of

the day: how to prove a system consistent. Gödel found a simple way to express the statement "
TNT
is consistent" in a
TNT
formula; and then he showed that this formula (and all others which express the same idea) are only theorems of
TNT
under one condition: that
TNT
is inconsistent. This perverse result was a severe blow to optimists who expected that one could find a rigorous proof that mathematics is contradiction-free.

How do you express the statement "
TNT
is consistent" inside
TNT
It hinges on this simple fact: that inconsistency means that two formulas, x and x, one the negation of the other, are both theorems. But if both x and -- x are theorems, then according to the Propositional Calculus, all well-formed formulas are theorems. Thus, to show
TNT's
consistency, it would suffice to exhibit one single sentence of
TNT
which can be proven to be a nontheorem. Therefore, one way to express "
TNT
is consistent" is to say "The formula -0=0 is not a theorem of
TNT
". This was already proposed as an exercise a few pages back. The translation is:

---3a:TNT-PROOF- PAIR{a,SSSSS

SSSSSOIa'}

223,666,111,666 S's

It can be shown, by lengthy but fairly straightforward reasoning, that-as long as
TNT
is consistent-this oath-of-consistency by
TNT
is not a theorem of
TNT
. So
TNT's
powers of introspection are great when it comes to expressing things, but fairly weak when it comes to proving them. This is quite a provocative result, if one applies it metaphorically to the human problem of self-knowledge.

TNT Is ω-Incomplete

Now what variety of incompleteness does
TNT
"enjoy? We shall see that
TNT'
s incompleteness is of the "omega" variety-defined in Chapter VIII. This means that there is some infinite pyramidal family of strings all of which are theorems, but whose associated "summarizing string" is a nontheorem. It is easy to exhibit the summarizing string which is a nontheorem:

u
S's

Va: 3a': To understand why this string is a nontheorem, notice that it is extremely similar to
G

itself-in fact,
G
can be made from it in one step (viz., according to
TNT
's Rule of Interchange). Therefore, if it were a theorem, so would
G
be. But since
G
isn't a theorem, neither can this be.

Now we want to show that all of the strings in the related pyramidal family
are
theorems. We can write them own easily enough:

u
S's

--3a':

-3a':

-3a':

-3a': What does each one assert? Their translations, one by one, are:

"0 and the arithmoquinification of u do not form a TNT-proof-pair."

"1 and the arithmoquinification of u do not form a TNT-proof-pair."

"2 and the arithmoquinification of u do not form a TNT-proof-pail."

"3 and the arithmoquinification of u do not form a TNT-proof-pair."

Now each of these assertions is about whether two specific integers form a proof-pair or not. (By contrast,
G
itself is about whether one specific integer is a theorem-number or not.) Now because
G
is a nontheorem, no integer forms a proof-pair with
G
's Gödel number. Therefore, each of the statements of the family is true. Now the crux of the matter is that the property of being a proof-pair is primitive recursive, hence represented, so that each of the statements in the list above, being true, must translate into a theorem of TNT-which means that everything in our infinite pyramidal family is a theorem. And that shows why
TNT
is w-incomplete.

Two Different Ways to Plug Up the Hole

Since G's interpretation is true, the interpretation of its negation
-G
is false. And, using the assumption that
TNT
is consistent, we know that no false statements are derivable in
TNT
. Thus neither
G
nor its negation -
G
is a theorem of
TNT
. We have found a hole in our system-an undecidable proposition. Now this need be no source of alarm, if we are philosophically detached enough to recognize what this is a symptom of. It signifies that
TNT
can be extended, just as absolute geometry could be. In fact,
TNT
can be extended in two distinct directions, just as absolute geometry could be. It can be extended in a standard direction-which corresponds to extending absolute geometry in the Euclidean direction; or, it can be extended in a nonstandard direction-which corresponds, of course, to extending absolute geometry in the non-Euclidean direction. Now the standard type of extension would involve

Adding
G
as a new axiom.

This suggestion seems rather innocuous and perhaps even desirable, since, after all,
G

asserts something true about the natural number system. But what about the nonstandard type of extensions If it is at all parallel to the case of the parallel postulate, it must involve

adding the negation of
G
as a new axiom.

But how can we even contemplate doing such a repugnant, hideous thing? After all, to paraphrase the memorable words of Girolamo Saccheri, isn't what --
G
says "repugnant to the nature of the natural numbers'?

Supernatural Numbers

I hope the irony of this quotation strikes you. The exact problem with Saccheri's approach to geometry was that he began with a fixed notion of what was true and what was not true, and he set out only to prove what he'd assessed as true to start with. Despite the cleverness of his approach-which involved denying the fifth postulate, and then proving many "repugnant" propositions of the ensuing geometry-Saccheri never entertained the possibility of other ways of thinking about points and lines. Now we should be wary of repeating this famous mistake. We must consider impartially, to the extent that we can, what it would mean to add -G as an axiom to
TNT
. Just think what mathematics would be like today if people had never considered adding new axioms of the following sorts:
3a:(a+a)=S0

3a:Sa=O

3a:(a•a)=SSO

3a:S(a•a) =0

While each of them is "repugnant to the nature of previously known number systems", each of them also provides a deep and wonderful extension of the notion of whole numbers: rational numbers, negative numbers, irrational numbers, imaginary numbers.

Such a possibility is what -G is trying to get us to open our eyes to. Now in the past, each new extension of the notion of number was greeted with hoots and catcalls. You can hear this particularly loudly in the names attached to the unwelcome arrivals, such as

"irrational numbers", "imaginary numbers". True to this tradition, we shall name the numbers which -'-
G
is announcing to us the supernatural numbers, showing how we feel they violate all reasonable and commonsensical notions.

If we are going to throw -
G
in as the sixth axiom of
TNT
, we had better understand how in the world it could coexist, in one system, with the infinite pyramidal family we just finished discussing. To put it bluntly, -
G
says:

“There exists some number which forms a
TNT
-proof-pair with the arithmoquinification of u”

-but the various members of the pyramidal family successively assert:

"0 is not that number"

"1 is not that number"

"2 is not that number"

This is rather confusing, because it seems to be a complete contradiction (which is why it is called "ω-inconsistency"). At the root of our confusion-much as in the case of the splitting of geometry-is our stubborn resistance to adopt a modified interpretation for the symbols, despite the fact that we are quite aware that the system is a modified system.

We want to get away without reinterpreting any symbols-and of course that will prove impossible.

The reconciliation comes when we reinterpret 3 as "There exists a
generalized
natural number", rather than as "There exists a natural number". As we do this, we shall also reinterpret V in the corresponding way. This means that we are opening the door to some extra numbers besides the natural numbers. These are the
supernatural
numbers
.

The naturals and supernaturals together make up the totality of
generalized naturals
.

The apparent contradiction vanishes into thin air, now, for the pyramidal family still says what it said before: "No
natural
number forms a
TNT
-proof-pair with the arithmoquinification of
u
." The family doesn't say anything about supernatural numbers, because there are no numerals for them. But now, -
G
says, "There exists a
generalized
natural number which forms a
TNT
-proof-pair with the arithmoquinification of u." It is clear that taken together, the family and -G tell us something: that there is a
supernatural
number which forms a
TNT
-proof-pair with the arithmoquinification of u. That is all-there is no contradiction any more.
TNT
+-
G
is a consistent system, under an interpretation which includes supernatural numbers.

Since we have now agreed to extend the interpretations of the two quantifiers, this means that any theorem which involves either of them has an extended meaning. For example, the commutativity theorem

Va:da':(a+a')=(a'+a)

now tells us that addition is commutative for all generalized natural numbers-in other words, not only for natural numbers, but also for supernatural numbers. Likewise, the
TNT
-theorem which says "2 is not the square of a natural number"--

-3a:(a • a)=SSO

--now tells us that 2 is not the square of a supernatural number, either. In fact, supernatural numbers share all the properties of natural numbers, as long as those properties are given to us in theorems of
TNT
. In other words, everything that can be
formally proven
about natural numbers is thereby established also for supernatural numbers. This means, in particular, that supernatural numbers are not anything already familiar to you, such as fractions, or negative numbers, or complex numbers, or whatever. The supernatural numbers are, instead, best visualized as integers which are greater than all natural numbers-as
infinitely large
integers. Here is the point: although theorems of
TNT
can rule out negative numbers, fractions, irrational numbers, and complex numbers, still there is no way to rule out infinitely large integers. The problem is, there is no way even to express the statement "There are no infinite quantities".