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

I-count. The reason is that if 3 divides 2n, then-because 3 does not dig 2-it must divide n (a simple fact from the theory of numbers). Neither rule II nor rule III can create a multiple of 3 from scratch.

But this is the key to the MU-puzzle! Here is what we know:

(1) The I-count begins at 1 (not a multiple of 3);

(2) Two of the rules do not affect the I-count at all; (3)

(3) The two remaining rules which do affect the I-count do so in such a way as never to create a multiple of 3 unless given one initially.

The conclusion-and a typically hereditary one it is, too-is that I-count can never become any multiple of 3. In particular, 0 is a forbid value of the I-count. Hence, MU is not a theorem of the MIU-system.

Notice that, even as a puzzle about I-counts, this problem was plagued by the crossfire of lengthening and shortening rules. Zero became the goal; I-counts could increase (rule II), could decrease (rule III). 1 we analyzed the situation, we might have thought that, with enough switching back and forth between the rules, we might eventually hit 0. IS thanks to a simple number-theoretical argument, we know that the impossible.

Gödel-Numbering the MIU-System

Not all problems of the the type which the MU-puzzle symbolizes at easy to solve as this one. But we have seen that at least one such pr could be embedded within, and solved within, number theory. We are going to see that there is a way to embed all problems about any for system, in number theory. This can happen thanks to the discovery Gödel, of a special kind of isomorphism. To illustrate it, I will use MIU-system.

We begin by considering the notation of the MIU-system. We map each symbol onto a new symbol:

M <= => 3

I <= => 1

U <= => 0

The correspondence was chosen arbitrarily; the only rhyme or reason is that each symbol looks a little like the one it is mapped onto. I number is called the Gödel number of the corresponding letter. Now I sure you can guess what the Gödel number of a multiletter string will be:

MU <= => 30

MIIU <= => 3110

Etc.

It is easy. Clearly this mapping between notations is an information preserving transformation; it is like playing the same melody on two different instruments.

Let us now take a look at a typical derivation in the MIU-system, written simultaneously in both notations:

(1)

MI

axiom 31

(2)

MII

rule 2 311

(3)

MIIII

rule 2 31111

(4)

MUI

rule 3 301

(5)

MUIU

rule 1 3010

(6)

MUIUUIU

rule 2 3010010

(7)

MUIIU

rule 4 30110

The left-hand column is obtained by applying our four familiar typographical rules. The right-hand column, too, could be thought of as having been generated by a similar set of typographical rules. Yet the right-hand column has a dual nature. Let me explain what this means.

Seeing Things Both Typographically and Arithmetically

We could say of the fifth string ('3010') that it was made from the fourth, by appending à0' on the right; on the other hand we could equally well view the transition as caused by an arithmetical operation-multiplication by 10, to be exact. When natural numbers are written in the decimal system, multiplication by 10 and putting à0' on the right are indistinguishable operations. We can take advantage of this to write an arithmetical rule which corresponds to typographical rule I:

ARITHMETICAL RULE la: A number whose decimal expansion ends on the right in `1'

can be multiplied by 10.

We can eliminate the reference to the symbols in the decimal expansion by arithmetically describing the rightmost digit:

ARITHMETICAL RULE Ib: A number whose remainder when divided by 10 is 1, can be multiplied by 10.

Now we could have stuck with a purely typographical rule, such as the following one: TYPOGRAPHICAL RULE I: From any theorem whose rightmost symbol is ' 1' a new theorem can be made, by appending `0' to the right of that 1'.

They would have the same effect. This is why the right-hand column has a "dual nature": it can be viewed either as a series of typographical operations changing one pattern of symbols into another, or as a series arithmetical operations changing one magnitude into another. But the are powerful reasons for being more interested in the arithmetical version Stepping out of one purely typographical system into another isomorphic typographical system is not a very exciting thing to do; whereas stepping clear out of the typographical domain into an isomorphic part of number theory has some kind of unexplored potential. It is as if somebody h known musical scores all his life, but purely visually-and then, all o: sudden, someone introduced him to the mapping between sounds a musical scores. What a rich, new world! Then again, it is as if somebody h been familiar with string figures all his life, but purely as string figur devoid of meaning-and then, all of a sudden, someone introduced him the mapping between stories and strings. What a revelation! The discovery of Gödel-numbering has been likened to the discovery, by Descartes, of t isomorphism between curves in a plane and equations in two variables; incredibly simple, once you see it-and opening onto a vast new world

Before we jump to conclusions, though, perhaps you would like to a more complete rendering of this higher level of the isomorphism. It i very good exercise. The idea is to give an arithmetical rule whose action is indistinguishable from that of each typographical rule of the MIU-system:

A solution is given below. In the rules, m and k are arbitrary natural numbers, and n is any natural number which is less than 10m

RULE 1: If we have made 10m + 1, then we can make 10 x (10m + 1)

Example: Going from line 4 to line 5. Here, m = 30.

RULE 2: If we have made 3 x 10" + n, then we can make 10' X X (3 x 10"'+n)+n.

Example: Going from line 1 to line 2, where both m and n equal 1.

RULE 3: If we have made k x 10 "`+ 111 x 10'+n, then we can make k x 10"+` + n.

Example: Going from line 3 to line 4. Here, m and n are 1, and k is 3.

RULE 4: If we have made k x 10rn+z + n, k x 10" +n. then we can make k x 10m + n Example: Going from line 6 to line 7. Here, m = 2, n = 10, and k = 301.

Let us not forget our axiom! Without it we can go nowhere. Therefore, let us postulate that:

We can make 31.

Now the right-hand column can be seen as a full-fledged arithmetic process, in a new arithmetical system which we might call the 310-system

I

(1)

31

given

(2)

311

rule 2 (m=1, n=1)

(3)

31111

rule 2 (m=2, n=11)

(4)

301

rule 3 (m=1, n=1, k=3)

(5)

3010

rule 1 (m=30)

(6)

3010010

rule 2 (m=3, n=10)

(7)

30110

rule 4 (m=2, n=10, k=301)

Notice once again that the lengthening and shortening rules are ever with us in this "310-system"; they have merely been transposed into the domain of numbers, so that the Godel numbers go up and down. If you look carefully at what is going on, you will discover that the rules are based on nothing more profound than the idea that shifting digits to left and right in decimal representations of integers is related to multiplications and divisions by powers of 10. This simple observation finds its generalization in the following CENTRAL PROPOSITION: If there is a typographical rule which tells how certain digits are to be shifted, changed, dropped, or inserted in any number represented decimally, then this rule can be represented equally well by an arithmetical counterpart which involves arithmetical operations with powers of 10

as well as additions, subtractions, and so forth.

More briefly:

Typographical rules for manipulating numerals are actually arithmetical rules for operating on numbers.

This simple observation is at the heart of Gödel’s method, and it will have an absolutely shattering effect. It tells us that once we have a Gödel numbering for any formal system, we can straightaway form a set of arithmetical rules which complete the Gödel isomorphism. The upshot is that we can transfer the study of any formal system-in fact the study of all formal systems-into number theory.

MIU-Producible Numbers

Just as any set of typographical rules generates a set of theorems, a corresponding set of natural numbers will be generated by repeated applications of arithmetical rules. These
producible numbers
play the same role inside number theory as theorems do inside any formal system. Of course, different numbers will be producible, depending on which rules are adopted. "Producible numbers" are only producible
relative to a system
of arithmetical rules. For example, such numbers as 31, 3010010, 3111, and so forth could be called
MIU
-
producible
numbers-an ungainly name, which might be shortened to
MIU
-
numbers
, symbolizing the fact that those numbers are the ones that result when you transcribe the
MIU
-system into number theory, via Gödel-numbering. If we were to Gödel-number the pq-system

and then "arithmetize" its rules, we could call the producible numbers "pq-numbers"-and so on.

Note that the producible numbers (in any given system) are defined by a recursive method: given numbers which are known to be producible, we have rules telling how to make more producible numbers. Thus, the class of numbers known to be producible is constantly extending itself, in much the same way that the list of Fibonacci numbers, or Q-numbers, does. The set of producible numbers of any system is a
recursively
enumerable set
. What about its complement-the set of nonproducible numbers? Is that set always recursively enumerable? Do numbers which are nonproducible share some common arithmetical feature?

This is the sort of issue which arises when you transpose the study of formal systems into number theory. For each system which is arithmetized, one can ask, "Can we characterize producible numbers in a simple way?" "Can we characterize
non
producible numbers in a recursively enumerable way?" These are difficult questions of number theory. Depending on the system which has been arithmetized, such questions might prove too hard for us to resolve. But if there is any hope for solving such problems, it would have to reside in the usual kind of step-by-step reasoning as it applies to natural numbers. And that, of course, was put in its quintessential form in the previous Chapter.

TNT seemed, to all appearances, to have captured all valid mathematical thinking processes in one single, compact system.

Answering Questions about Producible Numbers

by Consulting TNT

Could it be, therefore, that the means with which to answer any question about any formal system lies within just a single formal system-
TNT
? It seems plausible. Take, for instance, this question:

Is
MU
a theorem of the
MIU
-system?

Finding the answer is equivalent to determining whether 30 is a
MIU
number or not.

Because it is a statement of number theory, we should expect that, with some hard work, we could figure out how to translate the sentence "30 is a
MIU
-number" into
TNT
-

notation, in somewhat the same way as we figured out how to translate other numbertheoretical sentences into
TNT
-notation. I should immediately caution the reader that such a translation, though it does exist, is immensely complex. If you recall, I pointed out in Chapter VIII that even such a simple arithmetical predicate as "b is a power of 10" is very tricky to code into
TNT
-notation-and the predicate "b is a
MIU
-number" is a lot more complicated than that! Still, it can be found; and the numeral
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSO
can be substituted for every b. This will result in a
MON
strous string of
TNT
, a string of
TNT
which speaks about the
MU
-

puzzle. Let us therefore call that string "
MUMON
". Through
MUMON
and strings like it,
TNT
is now capable of speaking "in code" about the
MIU
-system.

The Dual Nature of
MUMON

In order to gain some benefit from this peculiar transformation of the original question, we would have to seek the answer to a new question:

Is
MUMON
a theorem of
TNT
?

All we have done is replace one relatively short string (
MU
) by another (the monstrous
MUMON
), and a simple formal system (the MIU-system) by a complicated one (
TNT
).

It isn't likely that the answer will be any more forthcoming even though the question has been reshaped. In fact,
TNT
has a full complement of both lengthening and shortening rules, and the reformulation of the question is likely to be far harder than the original.

One might even say that looking at
MU
via
MUMON
is an intentionally idiotic way of doing things. However,
MUMON
can be looked at on more than one level.

In fact, this is an intriguing point:
MUMON
has two different passive meanings.