To Mock a Mocking Bird

by Raymond M. Smullyan

  “Finally,” asked Craig, “do you know the name of this special bird ?”

  “Of course; its name is simply the letter .”

  “Good!” said Craig. “Then I believe I can lead you to a singing bird that is not a nightingale, but from what you’ve said, it may take several hours.”

  “In that case,” said Baritoni eagerly, “let’s start right now. We’ll stop at the lab and I’ll pack us a picnic lunch.”

  The two spent a good part of the day on their hunt, but they were amply rewarded. Toward twilight, they found themselves in a remote, lonely, and almost unknown region of the forest, and sure enough, perched on a low branch was a bird singing away ever so beautifully, and was definitely not a nightingale. In fact, the bird belonged to a species that neither Craig nor Baritoni had ever seen or heard before.

  • 1 •

  How did Craig know there was such a bird, and how did the two go about finding it?

  Note: The bird has subsequently come to be known as a Gödelian bird because Craig’s method of finding it paralleled Gödel’s method of finding a true sentence not provable in a certain axiom system. The reader interested in seeing this parallel should compare the problems of this chapter with those of chapters 14 and 15 of The Lady or the Tiger? The clue to the parallel is that singing birds correspond to true sentences and nightingales correspond to provable sentences. Thus a singing bird that is not a nightingale corresponds to a true sentence that is not provable in the axiom system under consideration.

  2 • A Follow-up

  The next morning Craig and Baritoni met again.

  “You know,” said Craig, “last night I thought of another way of finding a bird that sings but is not a nightingale. If you care to find it, we can do so, although I cannot guarantee that when we do, it might not turn out to be the same bird we found yesterday. But it may be worth a try.”

  Baritoni was delighted with the idea. So they spent the day in the forest and succeeded in finding a bird 1 that sang but was not a nightingale. As luck would have it, 1 turned out to be a different bird than , though this could not have been predicted. Can the reader explain this?

  3 • The Bird Societies

  Craig was enchanted with this forest and stayed for quite a while. He found out that the birds had organized several societies. A bird A is said to represent a set of birds if for every bird x in the set , the bird Ax is a singing bird and for every bird x outside the set , the bird Ax is a nonsing bird—in other words, for every bird x, the bird Ax sings if and only if x is a member of . A set of birds is called a society if it is represented by some bird. For example, the set of nightingales constitutes a society, because this set is represented by the bird .

  Craig was interested in the following problem: Does the set of singing birds constitute a society? This can be answered on the basis of just Condition 2 and Condition 3 stated by Baritoni. What is the answer? Also, from just Condition 3, it can be proved that every society must either contain at least one bird that sings or lack at least one bird that doesn’t sing. How is this proved, and what bearing does it have on the problem of whether the singing birds constitute a society?

  SOLUTIONS

  1 · They found the bird in the following manner:

  Baritoni already knew the name of the bird , hence by consulting his first list, he knew the name of ’—the mate of . Then, by consulting his second list, Baritoni found the name of the bird ’*. To reduce clutter, let us refer to the bird ’* as A. The two men next found the bird A, went up to it, and called out its own name. A responded by naming the bird AA. The two were then able to find AA. Now we prove that AA must be a bird that sings but is not a nightingale.

  We let be the bird AA—in other words, is the bird ’*’*—and we will show that sings but is not a nightingale.

  The bird A has the property that for any bird x, the bird Ax sings if and only if xx is not a nightingale. The reason is: ’*x sings if and only if ’(xx) sings, by Condition 3, and ’(xx) sings if and only if (xx) doesn’t sing, which is true if and only if xx is not a nightingale, because Nxx does sing if and only if xx is a nightingale, by Condition 4. Putting these three facts together, we see that ’*x sings if and only if xx is not a nightingale, and since ’* is the bird A, Ax sings if and only if xx is not a nightingale.

  Since it is true that for every bird x, the bird Ax sings if and only if xx is not a nightingale, then this is true if x is the bird A, and so AA sings if and only if AA is not a nightingale. This means that either AA sings and is not a nightingale, or AA doesn’t sing and is a nightingale. However, all nightingales sing, as given in Condition 1, and so the second alternative is ruled out. Therefore AA does sing, but is not a nightingale.

  The credit for this clever argument is ultimately due to Kurt Gödel.

  2 · Let A1 be the bird *’, rather than ’*. Then A1 is not necessarily the bird A, but it also has the property that for any bird x, the bird A1x sings if and only if A1x is not a nightingale. We leave the verification of this to the reader.

  Then it follows by the same argument that the bird A1A1—call this bird 1—sings but is not a nightingale.

  In summary, the bird ’*’* and the bird *’*’ are both birds that sing and neither is a nightingale.

  3 · We will first prove on the basis of just Condition 3 that any society must either contain a singer or lack some non-singer.

  Take any society . Then is represented by some bird A. Now consider the bird A*. For any bird x, the bird A*x sings if and only if A(xx) sings, according to Condition 3. Also, A(xx) sings if and only if xx is a member of , because A represents . Therefore, A*x sings if and only if xx is a member of . Since this is true for every bird x, then in particular, A*A* sings if and only if A*A* is a member of . And so if A*A* does sing, then it is a member of , and hence contains the singing bird A*A*. On the other hand, if A*A* doesn’t sing, then A*A* is not in , hence lacks at least one nonsinging bird—namely A*A*. This proves that every society must either contain at least one singing bird or fail to contain at least one nonsinging bird.

  Now, suppose the set of all singing birds formed a society; we would get the following contradiction: The set of all singing birds would be represented by some bird A. Then by Condition 2, the bird A’, the mate of A, would represent the set of all birds that don’t sing—can you see why? This means that the set of nonsinging birds forms a society, but this is impossible, since this set neither contains a singing bird nor lacks a nonsinging bird. Therefore the set of singing birds is not represented by any bird—it is not a society.

  Incidentally, the solution of this problem, together with Condition 1 and Condition 4, yields an alternative proof that there is a singing bird that is not a nightingale. Since the set of singing birds doesn’t constitute a society but the set of nightingales does, by Condition 4, then the two sets are not the same. But all nightingales sing, by Condition 1, hence some singing bird is not a nightingale.

  PART FIVE

  THE MASTER

  FOREST

  18

  The Master Forest

  There is only one road leading into the great Master Forest. When Craig reached the entrance, he saw an enormous sign hanging over the gate:

  “Oh, heavens!” thought Craig. “I have no idea if they will let me in. I’ve never thought of myself as elite; in fact, I’m not quite sure I know what the word really means!”

  At this point, an enormous sentinel blocked his way.

  “Only the elite are allowed to enter!” he said in a terrible voice. “Are you one of the elite?”

  “That depends on the definition of ‘elite’,” replied Craig. “How do you define an elite?”

  “It’s not how I define it that counts; it’s how Griffin defines it.”

  “And who is Griffin?” asked Craig.

  “Professor Charles Griffin—he is the resident bird sociologist of this forest, and he’s boss around here. It’s his definition that counts!”

  “Then what is
his definition?”

  “Well,” replied the sentinel in a softer tone, “his definition is a very liberal one. He defines an elite as anyone who wishes to enter. Do you wish to enter?”

  “Of course!” said Craig.

  “Then by definition, you’re an elite and are free to enter. I’m sure Professor Griffin will be delighted to meet you. His house is a mile and a half down the road. You can’t miss it; it’s in the shape of an enormous bird.”

  “That’s a relief!” thought Craig as he wended his way to the house. “I wonder why Professor Griffin instituted such a strange rule, which in fact doesn’t exclude anybody. What sort of a chap is this Griffin, anyway?”

  Well, Craig was pleasantly surprised to find Professor Griffin a most kind and hospitable fellow. He was a gentleman in his mid-sixties with long flowing white hair and a long flowing white beard. He looked somewhat like the popular image of Moses, or of God the Father.

  “Welcome!” said Griffin. “I hope you will find this forest of interest.”

  “I have come a long way,” said Craig, “and I am very curious to know what birds you have here.”

  “A starling and a kestrel,” replied Griffin.

  “That’s all?” asked Craig.

  “And all birds derivable from them,” replied Griffin.

  “Oh, that’s different! Are many birds derivable from just the starling and the kestrel?”

  “Very many indeed!” replied Griffin, with a subtle and rather mysterious smile. “Are you familiar with the bluebird, the dove, the blackbird, the eagle, the bunting, the dickcissel, the becard, the dovekie, the bald eagle, the warbler, the cardinal, the identity bird, the thrush, the robin, the finch, the vireo, the queer bird, the quixotic bird, the quizzical bird, the quirky bird, the quacky bird, the mockingbird, the lark, the sage bird, the Turing bird, and the owl?”

  “I know them all,” replied Craig, “and you mean to tell me that all of them are derivable from just the two birds S and K?”

  “Indeed they are!”

  Craig sank back in thought.

  “Perhaps that’s not too surprising,” Craig said at last. “I already know that all the birds you have just mentioned are derivable from the four birds B, T, M, and I, but I didn’t know that those four birds were derivable from only two combinatorial birds. Those four birds are derivable from S and K?”

  “Indeed they are,” replied Griffin, “and many more birds you haven’t ever heard of.”

  “Such as?”

  “Now this should surprise you,” replied Griffin. “From just S and K you can derive any combinatorial bird whatsoever! And there are infinitely many combinatorial birds!”

  “Fantastic!” exclaimed Craig. “Only one thing puzzles me. How can this finite forest contain infinitely many birds?”

  “Oh, they are not necessarily all here at the same time,” replied Griffin. “This is an evolving forest, and there is an ancient legend explaining this.—Let’s see, where did I put the book?”

  Professor Griffin then rummaged around in his library-study and finally brought out one of the most worn books Craig had ever seen, although it showed signs of having originally had a most beautiful, if overly ornate, binding. The book was full of remarkable ancient paintings and drawings of birds—many of which were unfamiliar. It was written in an ancient script that Craig could not identify.

  “Let me translate the legend as best I can,” said Griffin. “I have some knowledge of the language, but not too much. As I understand it, it goes something like this:

  “In the beginning, the forest gods started the forest with just two birds—the starling S and the kestrel K. There were already humans in the forest. New birds constantly came into existence in the following manner. A human would call out the name of some already existing bird y to some existing bird x; x would then respond by calling out the name of either some existing bird or of some nonexistent bird, but the marvelous thing is that if x named a nonexisting bird, the bird would then come into being! Thus new birds were constantly generated. The forest gods were wise in starting out with the starling and the kestrel, since from these two birds all combinatorial birds can be generated.”

  “That is the legend,” continued Griffin. “Of course, it is only a legend, but it gives one food for thought. Some ornitheological historians have likened it to the story of Adam and Eve, though which of the birds S or K is Adam and which is Eve has been a matter of bitter controversy. Male historians like to think of S as Adam, but many female historians regard this as male chauvinism. More research is needed to settle the matter definitely. Ancient Chinese historians think of S as the yang, K as the yin, and their union as the all-embracing Tao. I could say much more about the legend’s literary and historical aspects, but I’d like to get back to the purely scientific side of the story.”

  “The legend obviously has some foundation in truth,” Griffin went on, “since it is really a fact that all combinatorial birds are derivable from just the two birds S and K.”

  “How is this known?” asked Craig.

  “I will reveal the secret shortly,” replied Griffin, “but first I would like you to try some concrete problems.”

  • 1 •

  “Before we can get to first base,” continued Griffin, “we must derive an identity bird I from S and K. Can you see how to do it?”

  Inspector Craig fiddled around with this a bit, using pencil and paper, and got the solution. (The solution to this and the next three problems is incorporated into the text of “The Secret,” later in this chapter.)

  • 2 •

  “Good!” said Griffin. “Now that we have the identity bird I, we are free to use it in future derivations, since it is derivable in terms of S and K. Most of our future derivations will be in terms of S, K, and I.

  “Next, see if you can derive a mockingbird from S, K, and I—in fact, I’ll give you a hint: A mockingbird can be derived from just S and I. Can you see how?”

  Craig did not have too much difficulty with this one.

  • 3 •

  “Now let’s take another familiar bird—the thrush,” said Professor Griffin. “See if you can derive a thrush from S, K, and I.”

  Inspector Craig worked for quite a while on this one, but could not solve it.

  “I’ll give you some hints,” said Griffin. “First find an expression X1 satisfying the following two conditions:

  1. X1 is composed of just the letters S, K, I, and the variable x; the variable y should not be part of X1.

  2. The relation X1y = yx must hold, on the basis of the given conditions for S and K and also I.”

  Craig worked on this for a bit and found such an expression X1.

  “Now that I have it, what do I do with it?” asked Craig.

  “The next step,” replied Griffin, “is to find an expression X2 having no variables at all—an expression built from just the letters S, K, and I—such that the relation X2x = X1 must hold. Then X2xy = X1y, and X1y = yx must hold, hence, the relation X2xy = yx must hold, so X2 will be an expression for a thrush.”

  “Ah!” said Craig. “I begin to see light!”

  • 4 •

  “Now let’s try a more complex one,” suggested Griffin. “Try finding a bluebird in terms of S, K, and I. There are now three variables involved—x, y, and z. First find an expression X1 in which z doesn’t occur such that the relation X1z = x(yz) must hold. Then find an expression X2 in which neither y nor z occurs—that is, x is to be the only variable—such that the relation X2y = X1 holds. Finally, find an expression X3 in which no variable occurs such that the relation X3x = X2 must hold. Then X3 will be an expression for a bluebird.”

  THE SECRET

  Before telling the reader the general method of deriving any combinatorial bird from S and K, we will first solve the four problems given by Griffin.

  First we derive an identity bird from S and K (Problem 1). Well, SKK is such a bird, because for any bird x, SKKx = Kx(Kx) = x.

  We might remark
that for any bird A, the bird SKA is an identity bird (why?), so, for example, SKS is also an identity bird. But for definiteness, we will take I to be the bird SKK, which is the usual convention.

  Now let’s derive a mockingbird from S, K, and I (Problem 2). As Professor Griffin remarked, we can get a mockingbird from just S and I. Well, since Ix = x, it follows that SIIx = Ix(Ix) = x(Ix) = xx, and so SII is a mockingbird.

  Next for the thrush. This is trickier, since there are now two variables involved—x and y. As Professor Griffin suggested, let’s first find an expression X1 whose only variable is x such that the relation X1y = yx must hold. Well, I is an expression such that Iy = y, and Kx is an expression such that Kxy = x, hence SI(Kx) is an expression such that SI(Kx)y = yx, because SI(Kx)y = Iy(Kxy) = Iyx = yx. So SI(Kx) is an expression in which y doesn’t occur and which is such that SI(Kx)y = yx. We have thus found the desired expression X1—namely, SI(Kx).

  Now we follow Professor Griffin’s second suggestion and look for an expression X2 with no variables at all such that the relation X2x = SI(Kx) holds. Well, K(SI) is an expression such that K(SI)x = SI, and K is obviously an expression such that Kx = Kx, and so S(K(SI))K is an expression such that S(K(SI))Kx = SI(Kx). We can check this: S(K(SI))Kx = K(SI)x(Kx) = SI(Kx), since K(SI)x = SI. Therefore S(K(SI)) is a thrush. The reader can check this by computing S(K(SI))xy; he will end up with yx.

  Finally, for the bluebird (Problem 4): We must first find an expression X1 whose only variables are x and y such that the relation X1z = x(yz) holds. Well, since Kx is an expression such that Kxz = x and y is an expression such that yz = yz, then S(Kx)y is an expression such that S(Kx)yz = x(yz). Check: S(Kx)yz = Kxz (yz) = x(yz). So X1 can be taken to be S(Kx)y. It involves only the variables x and y.