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

Step 3: Apply every applicable rule to the theorems produced in step 2. This yields five new theorems:
MIIIIU, MIIUIIU, MIUIUIUIU, MIIIIIIII, MUI.

This method produces every single theorem sooner or later, because the rules are applied in every conceivable order. (See Fig. 11.) All of the lengthening-shortening alternations which we mentioned above eventually get carried out. However, it is not clear how long to wait for a given string

FIGURE 11. A systematically constructed "tree" of all the theorems of the
MIU
-system.

The
N
th level down contains those theorems whose derivations contain exactly
N
steps.

The encircled numbers tell which rule was employed. Is
MU
anywhere in this tree?

to appear on this list, since theorems are listed according to the shortness of their derivations. This is not a very useful order, if you are interested in a specific string (such as
MU
), and you don't even know if it has any derivation, much less how long that derivation might be.

Now we state the proposed "theoremhood-test":

Wait until the string in question is produced; when that happens, you know it is a theorem-and if it never happens, you know that it is not a theorem.

This seems ridiculous, because it presupposes that we don't mind waiting around literally an infinite length of time for our answer. This gets to the crux of the matter of what should count as a "test". Of prime importance is a guarantee that we will get our answer in a finite length of time. If there is a test for theoremhood, a test which does always terminate in a finite

amount of time, then that test is called a
decision procedure
for the given formal system.

When you have a decision procedure, then you have a very concrete characterization of the nature of all theorems in the system. Offhand, it might seem that the rules and axioms of the formal system provide no less complete a characterization of the theorems of the system than a decision procedure would. The tricky word here is

"characterization". Certainly the rules of inference and the axioms of the
MIU
-system do characterize, implicitly, those strings that are theorems. Even
more
implicitly, they characterize those strings that are not theorems. But implicit characterization is not enough, for many purposes. If someone claims to have a characterization of all theorems, but it takes him infinitely long to deduce that some particular string is not a theorem, you would probably tend to say that there is something lacking in that characterization-it is not quite concrete enough. And that is why discovering that a decision procedure exists is a very important step. What the discovery means, in effect, is that you can perform a test for theoremhood of a string, and that, even if the test is complicated, it is
guaranteed to
terminate
. In principle, the test is just as easy, just as mechanical, just as finite, just as full of certitude, as checking whether the first letter of the string is
M.
A decision procedure is a "litmus test" for theoremhood!

Incidentally, one requirement on formal systems is that the set of
axioms
must be characterized by a decision procedure-there must be a litmus test for axiomhood. This ensures that there is no problem in getting off the ground at the beginning, at least. That is the difference between the set of axioms and the set of theorems: the former always has a decision procedure, but the latter may not.

I am sure you will agree that when you looked at the MIU-system for the first time, you had to face this problem exactly. The lone axiom was known, the rules of inference were simple, so the theorems had been implicitly characterized-and yet it was still quite unclear what the consequences of that characterization were. In particular, it was still totally unclear whether
MU
is, or is not, a theorem.

FIGURE 12. Sky Castle, by M. C.: Escher (woodcut, 1928).

Two-Part Invention

or,

What the Tortoise Said to Achilles

by Lewis Carroll'

Achilles had overtaken the Tortoise, and had seated himself comfortably on its back.

"So you've got to the end of our race-course?" said the Tortoise. "Even though it DOES consist of an infinite series of distances? I thought some wiseacre or other had proved that the thing couldn't be done?"

"It CAN be done," said Achilles. "It HAS been done!
Solvitur ambulando
. You see the distances were constantly DIMINISHING; and so-"

"But if they had been constantly INCREASING?" the Tortoise interrupted. "How then?"

"Then I shouldn't be here," Achilles modestly replied; "and You would have got several times round the world, by this time!"

"You flatter me-FLATTEN, I mean," said the Tortoise; "for you ARE a heavy weight, and NO mistake! Well now, would you like to hear of a race-course, that most people fancy they can get to the end of in two or three steps, while it REALLY consists of an infinite number of distances, each one longer than the previous one?"

"Very much indeed!" said the Grecian warrior, as he drew from his helmet (few Grecian warriors possessed POCKETS in those days) an enormous note-book and pencil.

"Proceed! And speak SLOWLY, please! SHORTHAND isn't invented yet!"

"That beautiful First Proposition by Euclid!" the Tortoise murmured dreamily. "You admire Euclid?"

"Passionately! So far, at least, as one CAN admire a treatise that won't be published for some centuries to come!"

"Well, now, let's take a little bit of the argument in that First Proposition just TWO

steps, and the conclusion drawn from them. Kindly enter them in your note-book. And in order to refer to them conveniently, let's call them A, B, and Z: (A) Things that are equal to the same are equal to each other.

(B) The two sides of this Triangle are things that are equal to the same.

(Z) The two sides of this Triangle are equal to each other.

Readers of Euclid will grant, I suppose, that Z follows logically from A and B, so that any one who accepts A and B as true, MUST accept Z as true?"

"Undoubtedly! The youngest child in a High School-as soon as High Schools are invented, which will not be till some two thousand years later-will grant THAT."

"And if some reader had NOT yet accepted A and B as true, he might still accept the SEQUENCE as a VALID one, I suppose?"

"No doubt such a reader might exist. He might say, Ì accept as true the Hypothetical Proposition that, IF A and B be true, Z must be true; but I DON'T accept A and B as true.'

Such a reader would do wisely in abandoning Euclid, and taking to football."

"And might there not ALSO be some reader who would say Ì accept A and B as true, but I DON'T accept the Hypothetical'?"

"Certainly there might. HE, also, had better take to football."

"And NEITHER of these readers," the Tortoise continued, "is AS YET under any logical necessity to accept Z as true?"

"Quite so," Achilles assented.

"Well, now, I want you to consider ME as a reader of the SECOND kind, and to force me, logically, to accept Z as true."

"A tortoise playing football would be-" Achilles was beginning.

`-an anomaly, of course," the Tortoise hastily interrupted. "Don't wander from the point. Let's have Z first, and football afterwards!"

"I'm to force you to accept Z, am I?" Achilles said musingly. "And your present position is that you accept A and B, but you DON'T accept the Hypothetical-"

"Let's call it C," said the Tortoise.

"-but you DON'T accept

(C) If A and B are true, Z must be true."

"That is my present position," said the Tortoise.

"Then I must ask you to accept C."

"I'll do so," said the Tortoise, "as soon as you've entered it in that notebook of yours.

What else have you got in it?"

"Only a few memoranda," said Achilles, nervously fluttering the leaves: "a few memoranda of-of the battles in which I have distinguished myself!"

"Plenty of blank leaves, I see!" the Tortoise cheerily remarked. "We shall need them ALL!" (Achilles shuddered.) "Now write as I dictate:

(A) Things that are equal to the same are equal to each other.

(B) The two sides of this Triangle are things that are equal to the same.

(C) If A and B are true, Z must be true.

(Z) The two sides of this Triangle are equal to each other."

"You should call it D, not Z," said Achilles. "It comes NEXT to the other three. If you accept A and B and C, you MUST accept Z.

“And why must I?”

"Because it follows LOGICALLY from them. If A and B and C are true, Z MUST be true. You can't dispute THAT, I imagine?"

"If A and B and C are true, Z MUST be true," the Tortoise thoughtfully repeated.

"That's ANOTHER Hypothetical, isn't it? And, if I failed to see its truth, I might accept A and B and C, and STILL not accept Z, mightn't I?"

"You might," the candid hero admitted; "though such obtuseness would certainly be phenomenal. Still, the event is POSSIBLE. So I must ask you to grant ONE more Hypothetical."

"Very good, I'm quite willing to grant it, as soon as you've written it down. We will call it

(D) If A and B and C are true, Z must be true.

Have you entered that in your note-book?"

"I HAVE!" Achilles joyfully exclaimed, as he ran the pencil into its sheath. "And at last we've got to the end of this ideal race-course! Now that you accept A and B and C

and D, OF COURSE you accept Z."

"Do I?" said the Tortoise innocently. "Let's make that quite clear. I accept A and B and C and D. Suppose I STILL refused to accept Z?"

"Then Logic would take you by the throat, and FORCE you to do it!" Achilles triumphantly replied. "Logic would tell you, `You can't help yourself. Now that you've accepted A and B and C and D, you MUST accept Z!' So you've no choice, you see.",

"Whatever LOGIC is good enough to tell me is worth WRITING DOWN," said the Tortoise. "So enter it in your book, please. We will call it (E) If A and B and C and D are true, Z must be true.

Until I've granted THAT, of course I needn't grant Z. So it's quite a NECESSARY

step, you see?"

"I see," said Achilles; and there was a touch of sadness in his tone.

Here the narrator, having pressing business at the Bank, was obliged to leave the happy pair, and did not again pass the spot until some months afterwards. When he did so, Achilles was still seated on the back of the much-enduring Tortoise, and was writing in his notebook, which appeared to be nearly full. The Tortoise was saying, "Have you got that last step written down? Unless I've lost count, that makes a thousand and one.

There are several millions more to come. And WOULD you mind, as a personal favour, considering what a lot of instruction this colloquy of ours will provide for the Logicians of the Nineteenth Century-WOULD you mind adopting a pun that my cousin the Mock-Turtle will then make, and allowing yourself to be renamed TAUGHT-US?"

"As you please," replied the weary warrior, in the hollow tones of despair, as he buried his face in his hands. "Provided that YOU, for YOUR part, will adopt a pun the Mock-Turtle never made, and allow yourself to be re-named A KILL-EASE!"

in Mathematics.

THIS
Two-Part Invention
was the inspiration for my two characters. Just as Lewis Carroll took liberties with Zeno's Tortoise and Achilles, so have I taken liberties with Lewis Carroll's Tortoise and Achilles. In Carroll's dialogue, the same events take place over and over again, only each time on a higher and higher level; it is a wonderful analogue to Bach's Ever-Rising Canon. The Carrollian Dialogue, with its wit subtracted out, still leaves a deep philosophical problem: Do w
ords and thoughts follow formal
rules, or do they not
? That problem is the problem of this book.

In this Chapter and the next, we will look at several new formal systems. This will give us a much wider perspective on the concept of formal system. By the end of these two Chapters, you should have quite a good idea of the power of formal systems, and why they are of interest to mathematicians and logicians.

The pq-System

The formal system of this Chapter is called the
pq-system
. It is not important to mathematicians or logicians-in fact, it is just a simple invention of mine. Its importance lies only in the fact that it provides an excellent example of many ideas that play a large role in this book. There are three distinct symbols of the pq-system:
p