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

Some typical sentences of
N
-number theory-are:

(1)

5 is prime.

(2)

2 is not a square.

(3)

1729 is a sum of two cubes.

(4)

No sum of two positive cubes is itself a cube.

(5)

There are infinitely many prime numbers.

(6)

6 is even.

Now it may seem that we will need a symbol for each notion such as "prime” or "cube"

or "positive" -- but those notions are really not primitive. Primeness, for instance, has to do with the factors which a number has, which in turn has to do with multiplication.

Cubeness as well is defined in terms multiplication. Let us rephrase the sentences, then, in terms of what seem to be more elementary notions.

(1) There do not exist numbers
a
and
b
, both greater than
1
. such that 5 equals
a
times
b
.

(2) There does not exist a number
b
, such that
b
times
b
equals 2.

(3) There exist numbers
b
and
c
such that
b
times
b
times
b
, plus
c
times
c
times
c
, equals 1729.

(4') For all numbers
b
and
c
, greater than 0, there is no number
a
such that
a
times
a
times
a
equals
b
times
b
times
b
plus
c
times
c
times
c
.

(5) For each number
a
, there exists a number
b
, greater than
a
, with the property that there do not exist numbers
c
and
d
, both greater than 1, such that
b
equals
c
times
d
.

(6') There exists a number
e
such that 2 times
e
equals 6.

This analysis has gotten us a long ways towards the basic elements of language of number theory. It is clear that a few phrases reappear over a over: for all numbers
b

there exists a number
b
, such that

greater than

equals

times

plus

0, 1, 2, . .

Most of these will be granted individual symbols. An exception is "greater than", which can be further reduced. In fact, the sentence "
a
is greater than
b
" becomes there exists a number
c
, not equal to 0, such that
a
equals
b
plus
c
.

Numerals

We will not have a distinct symbol for each natural number. Instead, we have a very simple, uniform way of giving a compound symbol to e natural number -- very much as we did in the pq-system. Here is notation for natural numbers:

zero:

0

one:

SO

two:

SSO

three:

SSSO

etc.

The symbol
S
has an interpretation-"the successor of". Hence, the interpretation of
SSO

is literally "the successor of the successor of zero". Strings of this form are called
numerals.

Variables and Terms

Clearly, we need a way of referring to unspecified, or variable, numbers. For that, we will use the letters a, b, c, d, e. But five will not be enough. We need an unlimited supply of them, just as we had of atoms in the Propositional Calculus. We will use a similar method for making more variables: tacking on any number of primes. (Note: Of course the symbol "'-read "prime"-is not to be confused with prime numbers!) For instance: e

d'

c"

b´´´...

a´´´´

are all
variables
.

In a way it is a luxury to use the first five letters of the alphabet when we could get away with just
a
and the prime. Later on, I will actually drop
b, c, d
, and
e
, which will result in a sort of "austere" version of
TNT
-austere in the sense that it is a little harder to decipher complex formulas. But for now we'll be luxurious.

Now what about addition and multiplication? Very simple: we will use the ordinary symbols `+' and `•'. However, we will also introduce a parenthesizing requirement (we are now slowly slipping into the rules which define well-formed strings of
TNT
). To write "
b
plus
c
" and "
b
times
c
", for instance, we use the strings (b+c)

(b • c)

There is no laxness about such parentheses; to violate the convention is to produce a non-well-formed formula. ("Formula"? I use the term instead of "string" because it is conventional to do so. A
formula
is no more and no less than a string of
TNT
.) Incidentally, addition and multiplication are always to be thought of as
binary
operations-that is, they unite precisely two numbers, never three or more. Hence, if you wish to translate "1 plus 2 plus 3", you have to decide which of the following two expressions you want:

(SO+(SSO+SSSO))

((SO+SSO)+SSSO)

The next notion we'll symbolize is
equals
. That is very simple: we use ´=´.The advantage of taking over the standard symbol used N -- nonformal number theory -- iis obvious: easy legibility. The disadvantage is very much like the disadvantage of using the words

"point" a "line" in a formal treatment of geometry: unless one is very conscious a careful, one may blur the distinction between the familiar meaning and strictly rule-governed behavior of the formal symbol. In discuss geometry, I distinguished between the everyday word and the formal to by capitalizing the formal term: thus, in elliptical geometry, a POINT was 1 union of two ordinary points. Here, there is no such distinction; hen mental effort is needed not to confuse a symbol with all of the association is laden with. As I said earlier, with reference to the pq-system: the string --- is not the number 3, but it acts isomorphically to 3, at least in the context of additions. Similar remarks go for the string
SSSO
.

Atoms and Propositional Symbols

All the symbols of the Propositional Calculus except the letters used making atoms (
P, Q
, and
R
) will be used in
TNT
, and they retain their interpretations. The role of
atoms
will be played by strings which, when interpreted, are statements of equality, such as
SO=SSO
or (
SO • SO
) Now, we have the equipment to do a fair amount of translation of simple sentences into the notation of
TNT
:

2 plus 3 equals 4:

(SSO+SSSO)=SSSSO

2 plus 2 is not equal to 3:

~(SSO+SSO)=SSSO

If 1 equals 0, then 0 equals 1:

The first of these strings is an atom; the rest are compound formulas (Warning: The ànd'

in the phrase "I and 1 make 2" is just another word for `plus', and must be represented by

`+' (and the requisite parentheses).)

Free Variables and Quantifiers

All the well-formed formulas above have the property that their interpretations are sentences which are either true or false. There are, however, well-formed formulas which do-not have that property, such as this one

(b+SO)=SSO

Its interpretation is "
b
plus 1 equals 2". Since
b
is unspecified, there is way to assign a truth value to the statement. It is like an out-of-context statement with a pronoun, such as

"she is clumsy". It is neither true nor false; it is waiting for you to put it into a context.

Because it is neither true nor false, such a formula is called
open
, and the variable
b
is called a
free variable
.

One way of changing an open formula into a
closed
formula, or
sentence
, is by prefixing it with a
quantifier
-either the phrase "there exists a number b such that , or the phrase "for all numbers b". In the first instance, you get the sentence There exists a number
b
such that
b
plus 1 equals 2.

Clearly this is true. In the second instance, you get the sentence For all numbers
b, b
plus 1 equals 2.

Clearly this is false. We now introduce symbols for both of these
quantifiers
. These sentences are translated into TNT-notation as follows:

ℑ
b:(b+SO)=SSO

('ℑ' stands for èxists'.)

Vb:(b+SO)=SSO

('
V
' stands for àll'.)

It is very important to note that these statements are no longer about unspecified numbers; the first one is an assertion of existence, and the second one is a
universal
assertion
. They would mean the same thing, even if written with c instead of b:

ℑ
c:(c+SO)=SSÒ

Vc:(c+SO)=SSO

A variable which is under the dominion of a quantifier is called a
quantified variable
. The following two formulas illustrate the difference between free variables and quantified variables:

(b.b)=SSO

(open)

---
ℑ
b:(b•b)=SSO

(closed; a
sentence
of TNT)

The first one expresses a
property
which might be possessed by some natural number. Of course, no natural number has that property. And that is precisely what is expressed by the second one. It is very crucial to understand this difference between a string with a
free
variable,
which expresses a
property
, and a string where the variable is
quantified
, which expresses a
truth
or
falsity
. The English translation of a formula with at least one free variable-an open formula-is called a
predicate
. It is a sentence without a subject (or a sentence whose subject is an out-of-context pronoun). For instance,

"is a sentence without a subject"

"would be an anomaly"

"runs backwards and forwards simultaneously"

"improvised a six-part fugue on demand"

are nonarithmetical predicates. They express
properties
which specific entities might or might not possess. One could as well stick on a "dummy

subject", such as "so-and-so". A string with free variables is like a predicate with "so-and-so" as its subject. For instance,

(SO+SO)=b

is like saying "1 plus 1 equals so-and-so". This is a predicate in the variable
b
. It expresses a property which the number
b
might have. If one wet substitute various numerals for
b
, one would get a succession of forms most of which would express falsehoods. Here is another example of difference between open formulas and
sentences
:

`Vb:`Vc:(b+c)=(c+b)

The above formula is a sentence representing, of course, the commutativity of addition.

On the other hand,

`Vc:(b+c)=(c+b)

is an open formula, since b is free. It expresses a property which unspecified number
b
might or might not have -- namely of commuting with all numbers
c
.

Translating Our Sample Sentences

This completes the vocabulary with which we will express all num theoretical statements!

It takes considerable practice to get the hang of expressing complicated statements of
N

in this notation, and converse] figuring out the meaning of well-formed formulas. For this reason return to the six sample sentences given at the beginning, and work their translations into
TNT
. By the way, don't think that the translations given below are unique-far from it. There are many -- infinitely many -- ways to express each one.

Let us begin with the last one: "6 is even". This we rephrased in to of more primitive notions as "There exists a number
e
such that 2 times
e
equals 6". This one is easy

:

ℑ
e:(SSO. e)=SSSSSSO

Note the necessity of the quantifier; it simply would not do to write
(SSO . e)=SSSSSSO

alone. This string's interpretation is of course neither true nor false; it expresses a property which the number
e
might have.

It is curious that, since we know multiplication is commutative might easily have written

ℑ
e:(e - SSO)=SSSSSSO

instead. Or, knowing that equality is a symmetrical relation, we might 1 chosen to write the sides of the equation in the opposite order:

ℑ
e:SSSSSSO=(SSO • e)

Now these three translations of "6 is even" are quite different strings, and it is by no means obvious that theoremhood of any one of them is tied to theoremhood of any of the others. (Similarly, the fact that
--p-q---
was a theorem had very little to do with the fact that its "equivalent" string
-p--q---
was a theorem. The equivalence lies in our minds, since, as humans, we almost automatically think about interpretations, not structural properties of formulas.)

We can dispense with sentence 2: "2 is not a square", almost immediately:

-
ℑ
b:(b • b)=SSO

However, once again, we find an ambiguity. What if we had chosen to write it this way?

Vb: -(b • b) =SSO

The first way says, "It is not the case that there exists a number
b
with the property that
b
's square is 2", while the second way says, "For all numbers
b
, it is not the case that
b
's square is 2." Once again,
to us
, they are conceptually equivalent-but to
TNT
, they are distinct strings.