We therefore seek a bird A such that for all n and m:
1. A =
2. An. = σ(A), or what is the same thing, for any positive m, A = σ(A(P)).
Thus A must satisfy the condition that for any n and any m, whether 0 or positive, A = Z(σ(A(P))). Such a bird A exists by the fixed point principle, and so we take to be any such bird A.
6 · We note that multiplication is the one and only operation satisfying the following two conditions:
1. For any number n, n · 0 = 0.
2. For any numbers n and m, n · m+ = (n · m) + n.
We therefore want a bird A such that for every n and m, A = (Z)(()(A((P)))). Again, such a bird A can be found by the fixed point principle and we take to be such a bird.
7 · The exponential operation obeys the following well-known laws:
1. n0 = 1
2. nm+ = nm x n
We therefore seek a bird such that for all n, = , and for any positive number m, = (). Equivalently we want a bird such that for all n and m, = Z()). Again, such a bird can be found by the fixed point principle.
8 · The property of being an even number is the one and only property satisfying the following two conditions:
1. 0 is even.
2. For any positive number n, n is even if and only if its predecessor is not even.
We therefore seek a bird A such that:
1. A = t
2. For any positive n, A = N(A(P)), where N is the negation bird.
We thus want a bird A such that for every n, whether positive or 0, A = Zt(N(A(P))). Again such a bird A exists by the fixed point principle.
9 · By virtue of the conditions given, we seek a bird g such that for any numbers a and b:
1. If Z = t, then g = f.
2. If Z = f, then:
a. If Z = t, then g = t.
b. If Z = f, then g = g(P)(P).
Equivalently, we want a bird g such that for all numbers a and b, the following holds:
g = Zf(Zt(g(P)(P)))
Again such a bird g exists by the fixed point principle.
10 · Suppose A is a regular relational bird. By the fixed point principle there is a bird A1 such that for all birds x and y, A1xy = (Axy)y(A1x(σy)). Then for any numbers n and m, A1 = A()(A1.). Thus Condition 1 and Condition 2 hold, because the value of (A)(A1.) is , if A = t, and is A1., if A = f.
Following Griffin’s suggestion, we assume A’ = CA1. Then for every n, A’ = A1 (because A’ = CA1 = A1). Now, given an n, let k be the smallest number such that A = t. For example, suppose k = 3. Then A = f; A = f; A = f; but A = t. We must show that A’ = —in other words, that A1 = . Well, since A = f, then A1 = A1, by Condition 1. Since A = f, then A1n = A1, again by Condition 1. Since A = f, then A1 = A1, again by Condition 1. But now A = t, hence A1 = , by Condition 2. And so A1 = A1 = A1 = A1 = , therefore A1 = , and so A’ = .
We illustrated the proof for k = 3, but the reader can readily see that the same type of proof would work if k were any other number.
11 · A single example should convince the reader of the correctness of Craig’s assertions:
Suppose n = 647. The length of 647 is 3, and 103 = 1000, which is greater than 647. But 102 = 100, which is less than 647. Perhaps we should also consider the case when n itself is a power of 10—suppose n, say, is 100. Then 103 > 100, but 102, though not less than 100, is not greater than 100; it is equal to 100. So 3 is the smallest number such that 103 > 100.
Now to find the bird l: We let A1 be the bird Bg(), where B is the bluebird. Then for any numbers n and m, Bg() = g() = g , which is t if 10n > m, and is f otherwise. And so A1 is a relational bird such that A1 = t if and only if 10n > m. We then let A be the bird CA1, where C is the cardinal. Then A = A1, and so A = t if 10m > n; otherwise A = f. Finally, we take l to be a minimizer of A, and so l is the smallest m such that 10m > n—in other words, = , where k is the length of n.
12 · We first illustrate the general idea with an example. Suppose a = 572 and b = 39. Then 572*39 = 57239 = 57200 + 39 = 572.102 + 39, and 2 is the length of 39.
In general, a*b = a · 10k + b, where k is the length of b. We accordingly take to be a bird such that for all x and y, xy = (x( (ly)))y. As the reader can easily verify, for any numbers a and b, = , where k is the length of b.
25
Is There an Ideal Bird?
“Tomorrow I unfortunately must leave,” said Craig, “but before I do, I want to tell you of a problem I have been unable to solve. Perhaps you may know the answer.
“Any expression X, built from the symbols S and K, and parenthesized correctly, is the name of some bird. Now, two different expressions might happen to name the same bird—for example, the expressions ((SK)K)K and KK(KK) are both names of the kestrel K, though the expressions themselves are different. Now, what I want to know is this: Given two expressions X1 and X2, is there any systematic way of determining whether or not they name the same bird?”
“A beautiful question!” replied Griffin. “And it’s an amazing coincidence that you ask it today. This was just the topic I was planning to talk to you about. This question has been on the minds of some of the world’s ablest logicians and has come to be known as the Grand Question.
“To begin with, any question as to whether two expressions name the same bird can be translated into a question of whether a certain number belongs to a certain set of numbers.”
“How is that?” asked Craig.
“This is done using a clever device attributable to Kurt Gödel—the device known as Gödel numbering, which I will shortly explain.
“All the birds here are derivable from S and K, and their behavior—the way a bird x responds to a bird y—is strictly determined by the rules of combinatory logic. Combinatory logic is a theory that can be completely formalized. The theory uses just five symbols:
“Under each symbol I have written the number called its Gödel number, but I’ll tell you more about Gödel numbering a bit later.
“Any expression built from the two letters S and K and parenthesized correctly is called a term. To be more precise, a term is any expression in the first four symbols that is constructed by the following two rules:
1. The letters S and K standing alone are terms.
2. Given any terms X and Y already constructed, we may form the new term (XY).
“In application to this bird forest, the terms are those expressions that are names of birds. The letter S is the name of one particular starling—which one doesn’t really matter—and the letter K is the name of one particular kestrel.
“By a sentence is meant an expression of the form X = Y, when X and Y are terms. The sentence X = Y is called true if X and Y are names of the same bird and false otherwise. In order for a sentence X = Y to be true, the term X doesn’t have to be the same as the term Y; it merely suffices that these terms name the same bird.
“Of course, for any terms X, Y, and Z, the sentence SXYZ = XZ(YZ) is true, by definition of the starling, and KXY = X is true, by definition of the kestrel. All such sentences are taken as axioms of combinatory logic. We also take as axioms all sentences of the form X = X; these sentences are trivially true. These are the only axioms we shall take. We then prove various sentences to be true by starting with the axioms and using the usual logical rules for equality, which are:
1. If we can prove X = Y, then we can conclude that Y = X.
2. If we can prove X = Y and Y = Z, then we can conclude that X = Z.
3. If we can prove X = Y, then for any term Z we can conclude that XZ = YZ and that ZX = YX.
“Now, when I said that the behavior of the birds of this forest is completely determined by the laws of combinatory logic, what I meant is that a sentence X = Y is true, in the sense that the terms X and Y name the same bird, if and only if the sentence X = Y is provable from the above axioms by the rules I have just mentioned. There are no ‘accidental’ relations between our birds; X = Y only if the fact is provable.
“This system of combinatory logic is known
to be consistent, in the sense that not every sentence is provable—in particular, the sentence KI = K is not provable. If this one sentence were provable, then every sentence would be provable by essentially the same argument we used to show that if KI = K, then there could be only one bird in the forest. We will use f to abbreviate KI, and we will also use t synonymously with K, and so the sentence f = t is an important example of a sentence that is not provable in the system.
“And now for Gödel numbering: I have already told you that the Gödel numbers of the five symbols S, K, (,), and = are respectively 1, 2, 3, 4, and 5. The Gödel number of any compound expression is obtained by simply replacing each symbol with the digit representing its Gödel number and then reading off the resulting string of digits to the base 10. For example, the expression (SK) consists of the third symbol, followed by the first symbol, followed by the second symbol, followed by the fourth symbol, and so its Gödel number is 3124—three thousand one hundred twenty-four.
“Now, let be the set of Gödel numbers of the true sentences. Given any terms X and Y, they name the same bird if and only if the sentence X = Y is true, and the sentence is true if and only if its Gödel number lies in the set . That’s what I meant when I said that any question of whether or not two terms X and Y name the same bird can be translated into a question of whether a certain number—namely, the Gödel number of the sentence X = Y—lies in a certain set of numbers—namely, the set .
“Now, the question you are asking boils down to this: Is the set a computable set? Is there some purely deterministic device that can compute which numbers are in and which ones are not? As I have told you, anything a computer can do can be done by one of our birds, and so your question is equivalent to this: Is there here some ‘ideal’ bird A that can evaluate the truth of all sentences of combinatory logic? Is there a bird A such that whenever you call out the Gödel number of a true sentence, the bird will call back “t,” and whenever you call out any other number, the bird will call back “f”? In other words, is there a bird A such that for every n in , A = t and for every n not in , A = f? That is the question you are asking. Such a bird could settle all formal mathematical questions, because all such questions can be reduced to questions of which sentences are provable in combinatory logic and which sentences are not. Combinatory logic is a universal system for all of formal mathematics, and so any ideal bird might be said to be mathematically omniscient. That is why so many people have come to this forest in search of this bird.”
“That is staggering to the imagination!” said Craig. “Is it yet known whether or not there is this ‘ideal’ bird?”
“The question, in one form or another, has been on the minds of many mathematicians and philosophers from Leibniz on—and possibly earlier. It can be equivalently formulated: Can there be a universal computer that can settle all mathematical questions? Thanks to the work of Gödel, Church, Turing, Post, and others, the answer to this question is now known once and for all. I won’t spoil it for you by telling you the answer yet, but before this day is over, you will know the answer.
“We did a good deal of the preliminary work yesterday when we derived the concatenation bird , but there are still a few preliminaries left before we can answer the Grand Question.
“You realize, of course, that for any expressions X and Y, if a is the Gödel number of X and b is the Gödel number of Y, then the Gödel number of XY is a*b. For example, suppose X is the expression S and Y is the expression K. The Gödel number of X is 31 and the Gödel number of Y is 24. The expression XY is (SK) and its Gödel number is 3124, which is 31*24. Now you can see the significance of the numerical operation of concatenation to the base 10.”
1 • Numerals
“By a numeral is meant any of the terms , , ,…, ,… We call the numeral for the number n. The term , like any other term, has a Gödel number; we let n# be the Gödel number of the numeral .
“For example, is I, which in terms of S and K is the expression ((SK)K); this expression has Gödel number 3312424. And so 0# = 3312424.
“As for 1#, this is already quite a large number: is the expression σ, where σ is the expression (Vf), which in terms of S and K can be seen to be the expression (S(K(S(S((SK)K)(K(K((SK)K))))))K)—a horrible expression whose Gödel number is 313231313312424323233124244444424. To avoid having to write this number again, I will henceforth represent it by the letter s. Thus s is the Gödel number of σ. Then, since is the expression (σ), the number 1# is 3*s*0#*4. Then 2# = 3*s*1#*4; 3# = 3*s*2#*4, and so forth. For each number n, (n + 1)# = 3*s*n#*4.
“What we now need is a bird such that when any number n is called to the bird, the bird will call back the number n#. That is, we want a bird ∆ such that for every number n, ∆ = . Can you see how to find such a bird ∆?”
2 • Normalization
“For any expression X,” said Griffin, “by is meant the numeral designating the Gödel number of X. Thus is , where n is the Gödel number of X. We call the Gödel numeral of X.
“By the norm of X is meant the expression X—that is, X followed by its own Gödel numeral. If n is the Gödel number of X, then n# is the Gödel number of and so n*n# is the Gödel number of X—the norm of X. And so if X has Gödel number n, then the norm of X has Gödel number n*n#.
“We now need a bird ∆ called a normalizer such that for every number n, ∆n = . This bird is easy to find, now that we have the birds and δ. Can you see how?”
3 • The Second Fixed Point Principle
“One can do some amazing things with the normalizer,” said Griffin. “I will give you an example.
“We shall say that a term X designates a number n if the sentence X = is true. Obviously, one term that designates n is the numeral , but there are infinitely many others. For example, I, I(I), I(I(I)),… are all terms that designate n. Also, taking 8 for n, the numeral 8 designates 8; so does the term ; so does the term ; so does the term . You get the idea!
“We call a term a numerical term if it designates some number n. Every numeral is a numerical term, but not every numerical term is a numeral—for example, the expression is a numerical term, but it is not a numeral. For any number n, there is only one numeral designating it—the numeral —but there are infinitely many numerical terms designating it.
“Now, it is impossible that any numeral can designate its own Gödel number, because for any number n, the Gödel number of the numeral is much larger than n. All I am saying is that for every n, n# > n. However, there does exist a numerical term X that designates its own Gödel number.”
“That’s surprising!” said Craig. “I have no idea why this should be.”
“One can also construct a term that designates twice its Gödel number,” said Griffin, “or one that designates three times its Gödel number, or one that designates five times its Gödel number plus seven. All these odd facts are special cases of a very important principle known as the second fixed point principle, which is this: For any term A, there is a term X such that the sentence A = X is true. Stated otherwise, for any term A there is a term X such that X names the same bird as A followed by the Gödel numeral of X.
“Can you see how to prove this? Also, can you see how the oddities I just mentioned are special cases of the second fixed point principle?”
4 • A Gödelian Principle
“The second fixed point principle yields as a corollary an important principle attributable to Gödel, which I will tell you in a moment,” said Griffin.
“For any set of numbers, a sentence X is called a Gödel sentence for if either X is true and its Gödel number is in , or X is false and its Gödel number is not in . Such a sentence can be thought of as expressing the proposition that its own Gödel number is in , because the sentence is true if and only if its Gödel number is in .
“Now, Gödel’s principle is this: For any computable set , there is a Gödel sentence for . For example, since the set of even numbers is computable, then there must be a sentence such that either it is true and
its Gödel number is even, or it is false and its Gödel number is odd. Again, since the set of odd numbers is computable, then there must be a sentence such that either it is true and its Gödel number is odd, or it is false and its Gödel number is even. The remarkable thing is that for any computable set, there is a Gödel sentence for that set. This follows fairly easily from the second fixed point principle. Do you see how?
“I’ll give you a hint,” added Griffin. “For any set , let * be the set of all numbers n such that n*52 is in . First prove as a lemma—a preliminary fact—that if is computable, so is *.”
“What is the significance of the number n*52?” asked Craig.
“If n is the Gödel number of an expression X,” replied Griffin, “then n*52 is the Gödel number of the expression X = t.”
How is Gödel’s principle proved?
5 • The Negation Bird Pops Up
“One last detail before we answer the Grand Question,” said Griffin. “For any set of numbers, by ’ we mean the set of all numbers not in . For example, if is the set of all even numbers, ’ is the set of all odd numbers. The set ’ is called the complement of .
“Prove that if is computable, so is ’.”
• 6 •
“Now we have all the pieces of the puzzle,” said Griffin. “We are letting be the set of Gödel numbers of all the true sentences First ask yourself whether there could possibly be any Gödel sentence for the complement ’ of . Then, using the last two results, show that the set is not computable.”
“This is amazing indeed!” said Craig, after he realized the solution. “It seems to shatter any hope of a purely mechanical device that can decide all mathematical questions.”
“It certainly does!” said Griffin. “Any such mechanism could determine which numbers are in and which ones are not, hence would be a computable set, which we have just seen is not the case. Since is not computable, then there is no mechanism that can compute it. In short, no mechanism can be mathematically omniscient.
To Mock a Mocking Bird Page 19