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

"true". Here is the nub of the matter: mathematical logicians must choose which version of number theory to put their faith in. In particular, they cannot remain neutral on the question of the existence or nonexistence of supernatural numbers, for the two different theories may give different answers to questions in metamathematics.

For instance, take this question: "Is -
G
finitely derivable in
TNT
?" No one actually knows the answer. Nevertheless, most mathematical logicians would answer no without hesitation. The intuition which motivates that answer is based on the fact that if -

G
were a theorem,
TNT
would be w-inconsistent, and this would force supernaturals down your throat if you wanted to interpret
TNT
meaningfully-a most unpalatable thought for most people. After all, we didn't intend or expect supernaturals to be part of
TNT
when we invented it. That is, we-or most of us-believe that it is possible to make a formalization of number theory which does not force you into believing that supernatural numbers are every bit as real as naturals. It is that intuition about reality which determines which “fork” of number theory mathematicians will put their faith in, when the chips are

down. But this faith may be wrong. Perhaps every consistent formalization of number theory which humans invent will imply the existence of supernaturals, by being co-inconsistent. This is a queer thought, but it is conceivable.

If this were the case-which I doubt, but there is no disproof available-then G

would not have to be undecidable. In fact, there might be no undecidable formulas of
TNT
at all. There could simply be one unbifurcated theory of numbers-which necessarily includes supernaturals. This is not the kind of thing mathematical logicians expect, but it is something which ought not to be rejected outright. Generally, mathematical logicians believe that
TNT
-and systems similar to it-are ω-consistent, and that the Gödel string which can be constructed in any such system is undecidable within that system. That means that they can choose to add either it or its negation as an axiom.

Hilbert's Tenth Problem and the Tortoise

I would like to conclude this Chapter by mentioning one extension of Gödel’s Theorem. (This material is more fully covered in the article "Hilbert's Tenth Problem" by Davis and Hersh, for which see the Bibliography.) For this, I must define what a Diophantine equation is. This is an equation in which a polynomial with fixed integral coefficients and exponents is set to 0. For instance,

a
=0

and

5
x
+13
y
-1=0

And

5
p
5 + 17
q
17 - 177 = 0

and

a123,666,111,666 + b123,.666,111,666 - c123,666, 111,666 = 0

are Diophantine equations. It is in general a difficult matter to know whether a given Diophantine equation has any integer solutions or not. In fact, in a famous lecture at the beginning of the century, Hilbert asked mathematicians to look for a general algorithm by which one could determine in a finite number of steps if a given Diophantine equation has integer solutions or not. Little did he suspect that no such algorithm exists!

Now for the simplification of
G
. It has been shown that whenever you have a sufficiently powerful formal number theory and a Gödel-numbering for it, there is a Diophantine equation which is equivalent to
G.
The equivalence lies in the fact that this equation, when interpreted on a metamathematical level, asserts of itself that it has no solutions.

Turn it around: if you found a solution to it, you could construct from it the Gödel number of a proof in the system that the equation has no solutions! This is what the Tortoise did in the
Prelude
, using Fermat's equation as his Diophantine equation. It is nice to know that when you do this, you can retrieve the sound of Old Bach from the molecules in the air!

Birthday Cantatatata . .

One (tine May day, the Tortoise and Achilles meet, wandering in the woods.

The latter, all decked out handsomely, is doing a jiggish sort of thing to a
tune which he himself is humming. On his vest he is wearing a great big
button with the words "Today is my Birthday!"

Tortoise: Hello there, .Achilles. What makes you so joyful today? Is it your birthday, by any chance?

Achilles: Yes, yes! Yes it is, today is my birthday!

Tortoise: That is what I had suspected, on account of that button which you are wearing, and also because unless I am mistaken, you are singing a tune from a Birthday Cantata by Bach, one written in 1727 for the fifty-seventh birthday of Augustus, King of Saxony.

Achilles: You're right. And Augustus' birthday coincides with mine, so THIS Birthday Cantata has double meaning. However, I shan't tell you my age.

Tortoise: Oh, that's perfectly all right. However, I would like to know one other thing.

From what you have told me so far, would it be correct to conclude that today is your birthday?

Achilles: Yes, yes, it would be. Today is my birthday.

Tortoise: Excellent. That's just as I suspected. So now, I WILL conclude it is your birthday, unless

Achilles: Yes-unless what?

Tortoise: Unless that would be a premature or hasty conclusion to draw, you know.

Tortoises don't like to jump to conclusions, after all. (We don't like to jump at all, but especially not to conclusions.) So let me just ask you, knowing full well of your fondness for logical thought, whether it would be reasonable to deduce logically from the foregoing sentences, that today is in fact your birthday.

Achilles: I do believe I detect a pattern to your questions, Mr. T. But rather than jump to conclusions myself, I shall take your question at face value, and answer it straightforwardly. The answer is: YES.

Tortoise: Fine! Fine! Then there is only one more thing I need to know, to be quite certain that today is

Achilles: Yes, yes, yes, yes ... I can already see the line of your questioning, Mr. T. I'll have you know that I am not so gullible as I was when we discussed Euclid's proof, a while back.

Tortoise: Why, who would ever have thought you to be gullible? Quite to the contrary, I regard you as an expert in the forms of logical thought, an authority in the science of valid deductions. a fount of knowledge about certain correct methods of reasoning. . .

To tell the truth, Achilles, you are, in my opinion, a veritable titan in the art of rational cogitation.

And it is only for that reason that I would ask you, "Do the foregoing sentences present enough evidence that I should conclude without further puzzlement that today is your birthday

Achilles: You flatten me with your weighty praise,
Mr. T-FLATTER
, I mean. But I am struck by the repetitive nature of your questioning and in my estimation, you, just as well as I, could have answered `yes' each time.

Tortoise: Of course I could have, Achilles. But you see, to do so would have been to make a Wild Guess-and Tortoises abhor Wild Guesses. Tortoises formulate only Educated Guesses. Ah, yes-the power of the Educated Guess. You have no idea how many people fail to take into account all the Relevant Factors when they're guessing.

Achilles: It seems to me that there was only one relevant factor in this rigmarole, and that was my first statement.

Tortoise: Oh, to be sure, it's at least
ONE
of the factors to take into account, I'd say-but would you have me neglect Logic, that venerated science of the ancients? Logic is always a Relevant Factor in making Educated Guesses, and since I have with me a renowned expert in Logic, I thought it only Logical to take advantage of that fact, and confirm my hunches, by directly asking him whether my intuitions were correct. So let me finally come out and ask you point blank: "Do the preceding sentences allow me to conclude, with no room for doubt, that Today is your Birthday?"

Achilles: For one more time, YES. But frankly speaking, I have the distinct impression that you could have supplied that answer-as well as all the previous ones-yourself.

Tortoise: How your words sting! Would I were so wise as your insinuation suggests! But as merely a mortal Tortoise, profoundly ignorant and longing to take into account all the Relevant Factors, I needed to know the answers to all those questions.

Achilles: Well then, let me clear the matter up for once and for all. The answer to all the previous questions, and to all the succeeding ones which you will ask along the same line, is just this:
YES
.

Tortoise: Wonderful! In one fell swoop, you have circumvented the whole mess, in your characteristically inventive manner. I hope you won't mind if I call this ingenious trick an
ANSWER SCHEMA
. It rolls up yes-answers numbers 1, 2, 3, etc., into one single ball. In fact, coming as it does at the end of the line, it deserves the title

"Answer Schema Omega", `w' being the last letter of the Greek alphabet-as if YOU

needed to be told
THAT
!

Achilles: I don't care what you call it. I am just very relieved that you finally agree that it is my birthday, and we can go on to some other topic-such as what you are going to give me as a present.

Tortoise: Hold on—not so fast. I WILL agree it is your birthday, provided on thing Achilles: What? That I Ask for no present?

Tortoise: Not at all. In fact, Achilles, I am looking forward to treating you to a fine birthday dinner, provided merely that I am convinced that knowledge of all those yes-answers at once (as supplied by Answer Schema w) allows me to proceed directly and without any further detours to the conclusion that today is your birthday. That's the case, isn't it?

Achilles: Yes, of course it is.

Tortoise: Good. And now I have yes-answer ω + 1. Armed with it, I can proceed to accept the hypothesis that today is your birthday, if it is valid to do so. Would you be so kind as to counsel me on that matter, Achilles?

Achilles: What is this? I thought I had seen through your infinite plot. Now doesn't yes-answer ω + 1 satisfy you? All right. I'll give you not only yes-answer ω + 2, but also yes-answers ω + 3, ω + 4, and so on.

Tortoise: How generous of you, Achilles. And here it is your birthday, when I should be giving YOU presents instead of the reverse. Or rather, I SUSPECT it is your birthday.

I guess I can conclude that it IS your birthday, now, armed with the new Answer Schema, which I will call "Answer Schema 2ω ". But tell me, Achilles: Does Answer Schema 2ω REALLY allow me to make that enormous leap, or am I missing something?

Achilles: You won't trick me any more, Mr. T. I've seen the way to end this silly game. I hereby shall present you with an Answer Schema to end all Answer Schemas! That is, I present you simultaneously with Answer Schemas ω, 2 ω, 3 ω, 4 ω, 5 ω, etc. With this Meta-Answer-Schema, I have JUMPED OUT of the whole system, kit and caboodle, transcended this silly game you thought you had me trapped in-and now we are DONE!

Tortoise: Good grief! I feel honored, Achilles, to be the recipient of such a powerful Answer Schema. I feel that seldom has anything so gigantic been devised by the mind of man, and I am awestruck by its power. Would you mind if I give a name to your gift?

Achilles: Not at all.

Tortoise: Then I shall call it "Answer Schema ω2". And we can shortly proceed to other matters-as soon as you tell me whether the possession of Answer Schema ω2 allows me to deduce that today is your birthday.

Achilles: Oh, woe is me! Can't I ever reach the end of this tantalizing trail? What comes next?

Tortoise: Well, after Answer Schema ω2 there's answer ω2 + 1. And then answer ω2 + 2.

And so forth. But you can wrap those all together into a packet, being Answer Schema ω2 + ω. And then there are quite a few other answer-packets, such as ω2 + 2ω, and ω2 + 3ω…. Eventually you come to Answer Schema 2ω2, and after a while, Answer Schemas 3ω2 and 4ω2. Beyond them there

are yet further Answer Schemas, such as ω3;, ω4, ω5, and so on. It goes on quite a ways, you know.

Achilles: I can imagine, I suppose it comes to Answer Schema are yet further Answer Schemas, such as w;, w4, w5, and so on. It goes on quite a ways, you know.

Achilles: I can imagine, I suppose it comes to Answer Schema ωω after a while.

Tortoise: Of course.

Achilles: And then ωωω, and ωωωω',

Tortoise: You're catching on mighty fast, Achilles. I have a suggestion for you, if you don't mind. Why don't you throw all of those together into a single Answer Schema?

Achilles: All right, though I'm beginning to doubt whether it will do any good.

Tortoise: It seems to me that within our naming conventions as so far set up, there is no obvious name for this one. So perhaps we should just arbitrarily name it Answer Schema Œo.

Achilles: Confound it all! Every time you give one of my answers a NAME, it seems to signal the imminent shattering of my hopes that that answer will satisfy you. Why don't we just leave this Answer Schema nameless?

Tortoise: We can hardly do that, Achilles. We wouldn't have any way to refer to it without a name. And besides, there is something inevitable and rather beautiful about this particular Answer Schema. It would be quite ungraceful to leave it nameless! And you wouldn't want to do something lacking in grace on your birthday, would you? Or is it your birthday? Say, speaking of birthdays, today is MY' birthday!