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

(0+0)=0

(O+SO)=S0

(O+SSO)=SSO

(O+SSSO)=SSSO

(O+SSSSO)=SSSSO

etc.

As a matter of fact, each of the theorems in this family can be derived the one directly above it, in only a couple of lines. Thus it is a so "cascade" of theorems, each one triggering the next. (These theorem very reminiscent of the pq-theorems, where the middle and right-] groups of hyphens grew simultaneously.)

Now there is one string which we can easily write down, and v summarizes the passive meaning of them all, taken together. That un sally quantified
summarizing string
is this:

Va:(O+a)=a

Yet with the rules so far given, this string eludes production. Ti produce it yourself if you don't believe me.

You may think that we should immediately remedy the situation the following (PROPOSED) RULE OF ALL: If all the strings in a pyramidal family are theorems, then so is the universally quantified string which summarizes them.

The problem with this rule is that it cannot be used in the M
-
mode. people who are thinking
about
the system can ever know that an infinite set of strings are all theorems.

Thus this is not a rule that can be stuck i any formal system.

ω
-Incomplete Systems and Undecidable Strings

So we find ourselves in a strange situation, in which we can typographically produce theorems about the addition of any
specific
numbers, but even a simple string as the one above, which expresses a property of addition
in general
, is not a theorem. You might think that is not all that strange, we were in precisely that situation with the pq-system.

However, the pq-system had no pretensions about what it ought to be able to do; and ii fact

there was no way to
express
general statements about addition in its symbolism, let alone prove them. The equipment simply was not there, and it did not even occur to us to think that the system was defective. Here, however, the expressive capability is far stronger, and we have correspondingly higher expectations of TNT than of the pq-system. If the string above is not a theorem, then we will have good reason to consider TNT to be defective. As a matter of fact, there is a name for systems with this kind of defect-they are called ω-
incomplete
. (The prefix 'ω'-'omega'- comes from the fact that the totality of natural numbers is sometimes denoted by `ω'.) Here is the exact definition: A system is ω-incomplete if all the strings in a pyramidal family are theorems, but the universally quantified summarizing string is not a theorem.

Incidentally, the negation of the above summarizing string

~Va:(O+a)=a

-is also a nontheorem of TNT. This means that the original string is
undecidable within
the system
. If one or the other were a theorem, then we would say that it was decidable.

Although it may sound like a mystical term, there is nothing mystical about undecidability within a given system. It is only a sign that the system could be extended.

For example, within absolute geometry, Euclid's fifth postulate is undecidable. It has to be added as an extra postulate of geometry, to yield Euclidean geometry; or conversely, its negation can be added, to yield non-Euclidean geometry. If you think back to geometry, you will remember why this curious thing happens. It is because the four postulates of absolute geometry simply do not pin down the meanings of the terms

"point" and "line", and there is room for
different extensions
of the notions. The points and lines of Euclidean geometry provide one kind of extension of the notions of "point"

and "line"; the POINTS and LINES of non-Euclidean geometry, another. However, using the pre-flavored words "point" and "line" tended, for two millennia, to make people believe that those words were necessarily univalent, capable of only one meaning.

Non-Euclidean TNT

We are now faced with a similar situation, involving
TNT
. We have adopted a notation which prejudices us in certain ways. For instance, usage of the symbol `+'tends to make us think that every theorem with a plus sign in it ought to say something known and familiar and "sensible" about the known and familiar operation we call "addition".

Therefore it would run against the grain to propose adding the following "sixth axiom":

~Va:(0+a)=a

It doesn't jibe with what we believe about addition. But it is one possible extension of
TNT
, as we have so far formulated TNT. The system which uses this as its sixth axiom is a
consistent
system, in the sense of not has, two theorems of the form x and - x. However, when you juxtapose this "sixth axiom" with the pyramidal family of theorems shown above, you will probably be bothered by a seeming inconsistency between the family and the new axiom. But this kind of inconsistency is riot so damaging as the other kind (where x and x are both theorems). In fact, it is not a true inconsistency, because there is a way of interpreting the symbols so that everything comes out all right.

ω
-Inconsistency Is Not the Same as Inconsistency

This kind of inconsistency, created by the opposition of (1) a pyramidal family of theorems which collectively assert that
all
natural numbers have some property, and (2) a single theorem which seems to assert that
not all
numbers have it, is given the name of w-inconsistency. An w-inconsistent system is more like the at-the-outset-distasteful-but-in-the-end-accept non-Euclidean geometry. In order to form a mental model of what is going on, you have to imagine that there are some "extra", unsuspected numbers--let us not call them "natural", but
supernatural
numbers-which have no numerals. Therefore, facts about them cannot be represented in the pyramidal family. (This is a little bit like Achilles' conception
GOD
-as a sort of "superdjinn", a being greater than any of the djinn This was scoffed at by the Genie, but it is a reasonable image, and may I you to imagine supernatural numbers.)

What this tells us is that the axioms and rules of TNT, as so presented, do not fully pin down the interpretations for the symbol TNT. There is still room for variation in one's mental model of the notions they stand for. Each of the various possible extensions would pin d, some of the notions further; but in different ways. Which symbols we begin to take on "distasteful" passive meanings, if we added the "s axiom" given above? Would
all
of the symbols become tainted, or we some of them still mean what we want them to mean? I will let you tt about that. We will encounter a similar question in Chapter XIV, discuss the matter then. In any case, we will not follow this extension r but instead go on to try to repair the w-incompleteness of
TNT
.

The Last Rule

The problem with the "Rule of All" was that it required knowing that all lines of an infinite pyramidal family are theorems -- too much for a finite being. But suppose that each line of the pyramid can be derived from its predecessor in a
patterned
way. Then there would be a
finite
reason
accounting for the fact that all the strings in the pyramid are theorems. The trick then, is to find the
pattern
that causes the cascade, and show that pattern is a theorem in itself. That is like proving that each djinn passes a message to its meta, as in the children's game of "Telephone". The other thing left to show is that Genie starts the cascading message-that is, to establish that the first line of the pyramid is a theorem. Then you know that
GOD
will get the message!

In the particular pyramid we were looking at, there is a pattern, captured by lines 4-9 of the derivation below.

(1)
Va:Vb:(a+Sb)=S(a+b)

axiom 3

(2)
Vb:(O+Sb)=S(O+b)

specification

(3)
(O+Sb)=S(O+b)

specification

(4)
[

push

(5)
(O+b)=b

premise

(6)
S(O+b)=Sb

add S

(7)
(O+Sb)=S(O+b)

carry over line 3

(8)
(O+Sb)=Sb

transitivity

(9)
]

pop

The premise is
(O+b)=b
; the outcome is
(O+Sb)=Sb.

The first line of the pyramid is also a theorem; it follows directly from Axiom 2.

All we need now is a rule which lets us deduce that the string which summarizes the entire pyramid is itself a theorem. Such a rule will he a formalized statement of the fifth Peano postulate.

To express that rule, we need a little notation. Let us abbreviate a well-formed formula in which the variable a is free by the following notation:
X{a}

(There may be other free variables, too, but that is irrelevant.) Then the notation
X{Sa/a}

will stand for that string but with every occurrence of a replaced by
Sa
. Likewise,
X{0/a}

would stand for the same string, with each appearance of a replaced by
0
.

A specific example would be to let
X{a}
stand for the string in question: (O+a)=a.

Then
X{Sa/a}
would represent the string
(O+Sa)=Sa
, and
X{0/a}
would represent
(0+0)=0.
(Warning: This notation is not part of
TNT
; it is for our convenience in talking about
TNT
.)

With this new notation, we can state the last rule of
TNT
quite precisely: RULE OF INDUCTION: Suppose
u
is a variable, and
X{u
} is a well-formed formula in which u occurs free. If both
Vu:< X{u}
⊃
X{Su/u}>
and
X{0/u}
are theorems, then
Vu: X{u}
is also a theorem.

This is about as close as we can come to putting Peano's fifth postulate into
TNT
. Now let us use it to show that Va:(O+a)=a is indeed a theorem in
TNT
. Emerging from the fantasy in our derivation above, we can apply the fantasy rule, to give us (10)

<(O+b)=b
⊃
(O+Sb)=Sb>

fantasy rule

(11)

Vb:<(O+b)=b
⊃
(O+Sb)=Sb>

generalization

This is the first of the two input theorems required by the induction The other requirement is the first line of the pyramid, which we have. Therefore, we can apply the rule of induction, to deduce what we wanted.

`Vb:(O+b)=b

Specification and generalization will allow us to change the variable from b to a; thus
Va:(O+a)=
a is no longer an undecidable string of
TNT
..

A Long Derivation

Now I wish to present one longer derivation in TNT, so that you ca what one is like, and also because it proves a significant, if simple, fact of number theory.

(1)
Va: Vb:(a+Sb)=S(a+b)

axiom 3

(2)
Vb:(d+Sb)=S(d+b)

specification

(3)
(d+SSc)=S(d+Sc)

specificatic

(4)
b:(Sd+Sb)=S(Sd+b)

specification (line 1)

(5)
(Sd+Sc)-S(Sd+c)

specification

6)
S(Sd+c)=(Sd+Sc)

symmetry

(7)
[

push

(8)

Vd:(d+Sc)=(Sd+c)

premise

(9)

(d+Sc)=(Sd+c)

specification

(10
)

S(d+Sc)=S(Sd+c)

add S

(11
)

(d+SSc)=S(d+Sc)

carry over 3

(12
)

(d+SSc)=S(Sd+c)

transitivity

(13
)

S(Sd+c)=(Sd+Sc)

carry over 6

(14
)

(d+SSc)=(Sd+Sc)

transitivity

(15
)

Vd:(d+SSc)=(Sd+Sc)

generalization

(16
) ]

pop

(17
) ⊃
Vd:(d+SSc)=(Sd+Sc)>

fantasy rule

(18
) Vc:< Vd:(d+Sc)=(Sd+c)
⊃
Vd:(d+SSc)=(Sd+Sc)>

generalization

* * * * *

specification (line 2)

(20)
Va:(a+0)=a

axiom 1

(21)
(d+0)=d

specification

(22)
S(d+0)=Sd

add S

(23)
(d+SO)=Sd

transitivity (lines 19,2)

(24)
(Sd+O)=Sd

specification (line 20)

(25)
Sd=(Sd+O)

symmetry

(26) (
d+SO)=(Sd+o)

transitivity (lines 23,25)

(27)
Vd:(d+5O)=(Sd+O)

generalization

* * * * *

(28)
Vc: Vd:(d+Sc)=(Sd+c)

induction (lines 18,27)

[
S
can be slipped back and forth in an addition]

* * * * *

(29)
Vb:(c+Sb)=S(c+b)

specification (line 1)

(30)
(c+Sd)=S(c+d)

specification

(31)
Vb:(d+Sb)=S(d+b)

specification (line 1)

(32)
(d+Sc)=S(d+c)

specification

(33)
S(d+c)=(d+Sc)

symmetry

(34)
bed:(d+Sc)=(Sd+c)

specification (line 28)

(35)
(d+Sc)=(Sd+c)

specification

(36)
[

push

(37)