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

Let us proceed to sentence 3: "1729 is a sum of two cubes." This one will involve two existential quantifiers, one after the other, as follows:

ℑ
b:
ℑ
c:SSSSSS…………SSSSSO=(((b • b) • b)+((c • c) • c))

1729 of them

There are alternatives galore. Reverse the order of the quantifiers; switch the sides of the equation; change the variables to d and
e
; reverse the addition; write the multiplications differently; etc., etc. However, I prefer the following two translations of the sentence: ℑ
b:
ℑ
c:(((SSSSSSSSSSO.SSSSSSSSSSO).SSSSSSSSSSO)+

((SSSSSSSSSO • SSSSSSSSSO) • SSSSSSSSSO))=(((b • b) • b)+((c • c) • c))
and

ℑ
b:
ℑ
c:(((SSSSSSSSSSSSO.SSSSSSSSSSSSO). SSSSSSSSSSSSO)+

((SO •SO) • SO))=(((b •b) •b)+((c • c) •c))

Do you see why?

Tricks of the Trade

Now let us tackle the related sentence 4: "No sum of two positive cubes is itself a cube".

Suppose that we wished merely to state that 7 is not a sum of two positive cubes. The easiest way to do this is by
negating
the formula

which asserts that 7 is a sum of two positive cubes. This will be just like the preceding sentence involving 1729, except that we have to add in the proviso of the cubes being positive. We can do this with a trick: prefix variables with the symbol
S
, as follows: ℑ
b:
ℑ
c:SSSSSSSO=(((Sb • Sb) • Sb)+((Sc • Sc) -Sc))

You see, we are cubing not
b
and
c
, but their successors, which must be positive, since the smallest value which either
b
or
c
can take on is zero. Hence the right-hand side represents a sum of two positive cubes. In( tally, notice that the phrase "there exist numbers
b
and
c
such that…..”) when translated, does not involve the symbol `
n'
which stands for ‘and’. That symbol is used for connecting entire well-formed strings, not for joining two quantifiers.

Now that we have translated "7 is a sum of two positive cubes", we wish to negate it. That simply involves prefixing the whole thing by a single (Note: you should
not
negate each quantifier, even though the desired phrase runs "There do not exist numbers
b
and
c
such that ...".) Thus we get:

-
ℑ
b:
ℑ
c:SSSSSSSO=(((Sb • Sb) • Sb)+((Sc -Sc) -Sc))
Now our original goal was to assert this property not of the number of all cubes.

Therefore, let us replace the numeral
SSSSSSSO
by the ((a-a)-
a
), which is the translation of "
a
cubed":

ℑ
b:
ℑ
c:((a •a) •a)=(((Sb •Sb) • Sb)+((Sc -Sc) -Sc))

-

At this stage, we are in possession of an
open
formula, since
a
is still free. This formula expresses a property which a number a might or might not have-and it is our purpose to assert that all numbers do have that property. That is simple -- just prefix the whole thing with a universal quantifier

Va:-
ℑ
b:
ℑ
c:((a -a) • a)=(((Sb • Sb) • Sb) +((Sc -Sc) -Sc))
An equally good translation would be this:

--
ℑ
a:
ℑ
b:
ℑ
c:((a-a) a)=(((Sb•Sb)•Sb)+((Sc•Sc)•Sc))
In austere
TNT
, we could use
a'
instead of
b
, and
a"
instead of
c,
and the formula would become:

--
ℑ
a:
ℑ
a':
ℑ
a":((a • a) • a) =(((Sa' • Sa') • Sa') +((Sa" • Sa") • Sa"))
What about sentence 1: "5 is prime"? We had reworded it in this way "There do not exist numbers
a
and
b
, both greater than 1, such equals
a
times
b
". We can slightly modify it, as follows: "There do not exist numbers
a
and
b
such that 5 equals
a
plus 2, times
b
plus 2". This is another trick-since
a
and
b
are restricted to natural number values, this is an adequate way to say the same thing. Now "
b
plus 2" could be translated into (
b+SSO
), but there is a shorter way to write it -- namely,
SSb
. Likewise, "
c
plus 2" can be written
SSc
. Now, our translation is extremely concise: ℑ
b:
ℑ
c:SSSSSO=(SSb • SSc)

Without the initial tilde, it would be an assertion that two natural numbers
do
exist, which, when augmented by 2, have a product equal to 5. With the tilde in front, that whole statement is denied, resulting in an assertion that 5 is prime.

If we wanted to assert that
d
plus
e
plus 1, rather than 5, is prime, the most economical way would be to replace the numeral for 5 by the string (
d+Se
): ℑ
b:
ℑ
c:(d+Se)=(SSb SSc)

Once again, an open formula, one whose interpretation is neither a true nor a false sentence, but just an assertion about two unspecified numbers,
d
and
e
. Notice that the number represented by the string (
d+Se
) is necessarily greater than
d
, since one has added to
d
an unspecified but definitely positive amount. Therefore, if we existentially quantify over the variable
e
, we will have a formula which asserts that: There exists a number which is greater than
d
and which is prime.

ℑ
e:-
ℑ
b:3c:(d+Se)=(SSb • SSc)

Well, all we have left to do now is to assert that this property actually obtains, no matter what
d
is. The way to do that is to universally quantify over the variable
d
:
Vd:3e:-3b:3c:(d+Se)=(SSb •SSc)

That's the translation of sentence 5!

Translation Puzzles for You

This completes the exercise of translating all six typical number-theoretical sentences.

However, it does not necessarily make you an expert in the notation of
TNT
. There are still some tricky issues to be mastered. The following six well-formed formulas will test your understanding of
TNT
notation. What do they mean? Which ones are true (under interpretation, of course), and which ones are false? (Hint: the way to tackle this exercise is to move leftwards. First, translate the atom; next, figure out what adding a single quantifier or a tilde does; then move leftwards, adding another quantifier or tilde; then move leftwards again, and do the same.)

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

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

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

~
ℑ
b:Vc:(SSO • b)=c

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

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

(Second hint: Either four of them are true and two false, or four false and two true.)
How to Distinguish True from False?

At this juncture, it is worthwhile pausing for breath and contempt what it would mean to have a formal system that could sift out the true from the false ones. This system would treat all these strings-which look like statements-as designs having form, but no content.

An( system would be like a sieve through which could pass only designs v special style-the "style of truth". If you yourself have gone through ti formulas above, and have separated the true from the false by this about meaning, you will appreciate the subtlety that any system would to have, that could do the same thing-but typographically! The bout separating the set of true statements from the set of false statements written in the
TNT
-notation) is anything but straight; it is a boundary with many treacherous curves (recall Fig. 18), a boundary of which mathematicians have delineated stretches, here and there, working over hundreds years. Just think what a coup it would be to have a typographical m( which was guaranteed to place any formula on the proper side o border!

The Rules of Well-Formedness

It is useful to have a table of Rules of Formation for well-formed formulas This is provided below. There are some preliminary stages, defining
numerals, variables
, and
terms
. Those three classes of strings are ingredients of well-formed formulas, but are not in themselves well-formed. The smallest well-formed formulas are the
atoms
; then there are ways of compounding atoms. Many of these rules are recursive lengthening rules, in that they take as input an item of a given class and produce a longer item of the class. In this table, I usèx' and 'y' to stand for well-formed formulas, and `
s
',
`t'
, and `
u'
to stand for other kinds of
TNT
-strings. Needless to say, none of these five symbols is itself a symbol of
TNT
.

NUMERALS.

0
is a numeral.

A numeral preceded by
S
is also a numeral.

Examples
: 0 SO S50 SSSO SSSSO SSSSSO

VARIABLES.

a
is a variable. If we're not being austere, so are
b, c, d
and
e
. A variable followed by a prime is also a variable.

Examples
:
a b' c" d"' a""

TERMS.

All numerals and variables are terms.

A term preceded by
S
is also a term.

If
s
and
t
are terms, then so
are (s+ t) and (s • t).

Examples
:
0 b SSa' (SO • (SSO+c)) S(Sa • (Sb • Sc))

TERMS may be divided into two categories:

(1) DEFINITE terms. These contain no variables.

Examples
: 0 (SO+SO) SS((SSO.SSO)+(SO.SO))

(2) INDEFINITE terms. These contain variables.

Examples
:
b Sa (b+SO) (((SO+SO)+SO)+e)

The above rules tell how to make
parts
of well-formed formulas; the remaining rules tell how to make
complete
well-formed formulas.

ATOMS.

If
s
and
t
are terms, then
s = t
is an atom.

Examples
:
SO=0 (SS0+SS0)=5SSS0 5(b+c)=((c•d).e)

If an atom contains a variable
u
, then u is
free
in it. Thus there are four free variables in the last example.

NEGATIONS.

A well-formed formula preceded by a tilde is well-formed.

Examples
: ~
S0=0 ~
ℑ
b:(b+b)=SO -⊃
S0=O> ~b=SO

The quan
tification status
of a variable (which says whether the variable is free or quantified) does not change under negation.

COMPOUNDS.

If x and y are well-formed formulas, and provided that no variable which is free in one is quantified in the other, then the following are all well-formed formulas:

< x∧ y>, < x∨ y>, < x⊃ y>.

Examples
: <
O=O
∧
~-0=0> ∨
~
ℑ
c:c=b>

⊃
Vc:~
ℑ
b:(b+b)=c>

The quantification status of a variable doesn't change here.

QUANTI FI CATIONS.

If
u
is a variable, and x is a well-formed formula in which
u
is free then the following strings are well-formed formulas:

ℑ
u: x and Vu: x.

Examples
:
Vb:∨
~
ℑ
c:c=b>
∨
c:~
ℑ
b:(b+b)=c ~
ℑ
c:Sc=d
OPEN FORMULAS contain at least one free variable.

Examples
:
--c=c b=b

CLOSED FORMULAS (SENTENCES) contain no free variables.

Examples
:
50=0 ~Vd:d=0
ℑ
c:∧
~c=c>
This completes the table of Rules of Formation for the well-formed formulas of
TNT
.

A Few More Translation Exercises

And now, a few practice exercises for you, to test your understanding of the notation of
TNT
. Try to translate the first four of the following
N
-sentences into
TNT
-sentences, and the last one into an open formed formula.

All natural numbers are equal to 4.

There is no natural number which equals its own square.

Different natural numbers have different successors.

If 1 equals 0, then every number is odd.

b
is a power of 2.

The last one you may find a little tricky. But it is nothing, compared to this one:
b
is a power of 10.

Strangely, this one takes great cleverness to render in our notation. I would caution you to try it only if you are willing to spend hours and hours on it -- and if you know quite a bit of number theory!

A Non typographical System

This concludes the exposition of the notation of
TNT
; however, we still left with the problem of making
TNT
into the ambitious system which we have described. Success would justify the interpretations which we given to the various symbols. Until we have done that, however, particular interpretations are no more justified than the "horse-apple happy" interpretations were for the pq-system's symbols.

Someone might suggest the following way of constructing
TNT
: (1|) Do not have any rules of inference; they are unnecessary, because (2) We take as axioms all true statements of number theory (as written in
TNT
-notation). What a simple prescription!