To Mock a Mocking Bird

by Raymond M. Smullyan

  Therefore if A is fond of x, then Ax = x, and A is compatible with A, which means that A is happy.

  8 · Suppose H is a happy bird. Then there are birds x and y such that Hx = y and Hy = x. Since Hx = y, then we can substitute Hy for x (since Hy = x) and obtain H(Hy) = y. Also, by the composition condition C1, there is a bird B that composes H with H, and so By = H(Hy) = y. So By = y, which means that B is fond of y. Since B is fond of some bird y, then B is normal.

  9 · We are given the conditions of Problem 1, hence every bird is fond of at least one bird. In particular, the kestrel K is fond of some bird A. Thus KA = A. Hence for every bird x, (KA)x = Ax. Also (KA)x = A, since K is a kestrel. Therefore Ax = A. Since for every bird x, Ax = A, then A is hopelessly egocentric.

  We can also look at the matter this way: If the kestrel K is fond of a bird A, then KA = A. Also KA is fixated on A, and since KA = A, then A is fixated on A, which means that A is hopelessly egocentric. And so we see that any bird of which the kestrel is fond must be hopelessly egocentric.

  10 · Of course it does! If x is fixated on y, then for every bird z, xz = y, hence in particular, xy = y, which means that x is fond of y.

  11 · If K is egocentric, then K is fond of K. But we proved in Problem 9 that any bird of which K is fond must be hopelessly egocentric, and so if K is egocentric, K is hopelessly egocentric.

  12 · Suppose that Kx is egocentric. Then (Kx)(Kx) = Kx. But also (Kx)(Kx) = x, because for any bird y, (Kx)y = x, so this is also true when y is the bird Kx. Therefore Kx = x, because Kx and x are both equal to the bird (Kx)(Kx), so they are equal to each other. This means that K is fond of x.

  13 · Suppose A is hopelessly egocentric. Then Ax = A and Ay = A, so Ax = Ay; they are both equal to A. Thus the statement is true.

  14 · Yes, it does follow. Suppose A is hopelessly egocentric. Then Ax = A, hence (Ax)y = Ay and Ay = A, so (Ax)y = A.

  15 · Suppose A is hopelessly egocentric. Then for any birds x and y, (Ax)y = A, according to the last problem. Also Ax = A, since A is hopelessly egocentric. Therefore (Ax)y = Ax, since (Ax)y and Ax are both equal to A. Therefore, for any bird y, (Ax)y = Ax, which means that Ax is hopelessly egocentric.

  16 · Suppose Kx = Ky and that K is a kestrel. Then for any bird z, (Kx)z = (Ky)z. But (Kx)z = x and (Ky)z = y, so x = (Kx)z = (Ky)z = y. Therefore x = y.

  17 · Suppose A is fixated on x and A is fixated on y; we will show that x = y.

  Take any bird z. Then Az = x, since A is fixated on x, and Az = y, since A is fixated on y. Therefore x and y are both equal to the bird Az, and so x = y.

  18 · Suppose K is fond of Kx. Then K(Kx) = Kx. Now, K(Kx) is fixated on Kx, whereas Kx is fixated on x. But since K(Kx) and Kx are the same bird, then the same bird is fixated on both Kx and x, which makes Kx = x, according to the last problem. Therefore K is fond of x.

  19 · We will show that the only way a kestrel can be egocentric is that it is the only bird in the forest!

  Proof 1: Suppose that K is an egocentric kestrel. Then K is hopelessly egocentric, according to Problem 11. Now let x and y be any birds in the forest, and we will show that x = y.

  Since K is hopelessly egocentric, then Kx = K and Ky = K, so Kx = Ky. Therefore, according to Problem 16, x = y. So any birds x and y in the forest are identical with each other, and there is only one bird in the forest. Since we are given that K is in the forest, then K is the only bird in the forest.

  Proof 2: Again we use the fact that since K is egocentric, then K is hopelessly egocentric. Now let x be any bird in the forest. Then Kx is fixated on x, since K is a kestrel, and also Kx = K, since K is hopelessly egocentric. Therefore K is fixated on x, since Kx is fixated on x and Kx is the bird K. This proves that K is fixated on every bird x in the forest. But by Problem 17, K cannot be fixated on more than one bird, hence all the birds of the forest must be identical.

  20 · Yes, it does. Suppose I is agreeable. Then for any bird x there is a bird y such that xy = Iy. But Iy = y, hence xy = y. Thus x is fond of y.

  21 · Yes, it does. Suppose every bird x is fond of some bird y. Then xy = y, but also Iy = y, and so bird I agrees with x on the bird y.

  22 · Both conclusions follow.

  1. We are given that I is an identity bird and that any two birds are compatible. Now, take any bird B. Then B is compatible with I, so there are birds x and y such that Bx = y and Iy = x. Since Iy = x, then y = x, because y = Iy. Since y = x and Bx = y, then Bx = x, so B is fond of the bird x. Therefore every bird B is fond of some bird x.

  2. This follows from the first conclusion and Problem 21.

  23 · Suppose I is an identity bird and I is hopelessly egocentric. Take any bird x. Then Ix = I, since I is hopelessly egocentric, but also Ix = x, since I is an identity bird. Then x = I, so again we have the sad fact that there is only one bird in the forest; every bird x is identical with I.

  24 · Suppose L is a lark and I is an identity bird. Then for any bird x, (LI)x = I(xx) = xx. Therefore LI is a mockingbird. This means that if someone calls out I to L, then L names a mockingbird.

  25 · This is quite simple. Suppose L is a lark. Then for any birds x and y, (Lx)y = x(yy). This is also true when y is the bird Lx, and so (Lx)(Lx) = x((Lx)(Lx)). And so, of course, x((Lx)(Lx)) = (Lx)(Lx), which means that x is fond of the bird (Lx)(Lx). So every bird x is normal.

  For help in solving future problems, we make a note of the fact that for any lark L, any bird x is fond of the bird (Lx)(Lx).

  26 · We will show that if L is a hopelessly egocentric lark, then every bird is fond of L.

  Suppose L is a lark and that L is hopelessly egocentric. Since L is hopelessly egocentric, then for any birds x and y, (Lx)y = L, according to Problem 14. In particular, taking Lx for y, (Lx)(Lx) = L. But x is fond of (Lx)(Lx), as we proved in the last problem. Therefore x is fond of L, since (Lx)(Lx) = L. This proves that every bird x is fond of L.

  27 · This is an interesting proof! We have already proved in Problem 18 that if K is fond of Kx, then K is fond of x. In particular, taking K for x, if K is fond of KK, then K is fond of K.

  Now suppose L is a lark of the forest and K is a kestrel of the forest and that L is fond of K. Then LK = K, hence (LK)K = KK. But (LK)K = K(KK), since L is a lark. Therefore KK = K(KK)—they are both equal to (LK)K—which makes K fond of KK. Then K is fond of K, as we showed in the last paragraph. Hence K is egocentric. Then by Problem 19, K is the only bird in the forest. But this contradicts the given fact that L is in the forest and L ≠ K.

  28 · Suppose K is fond of L. Then by the solution to Problem 9, L is hopelessly egocentric. Therefore, by Problem 26, every bird is fond of L.

  29 · Suppose the forest contains a lark L. Then by Problem 25, every bird is fond of at least one bird. In particular, the bird LL is fond of some bird y. (This constitutes our first trick!) Therefore (LL)y = y, but (LL)y = L(yy), because L is a lark, and so for any bird x, (Lx)y = x(yy). Therefore L(yy) = y, since they are both equal to (LL)y. Therefore (L(yy))y = yy. (This is our second trick!) But (L(yy))y = (yy)(yy). This can be seen by substituting (yy) for x in the equation (Lx)y = x(yy). So yy and (yy)(yy) are both equal to (L(yy))y, hence (yy)(yy) = yy, which means that yy is egocentric.

  This proves that if y is any bird of whom LL is fond, then yy must be egocentric. Furthermore, LL is fond of some bird y, according to Problem 25.

  We can actually compute a bird y of which LL is fond. We saw in the solution to Problem 25 that for any bird x, x is fond of (Lx)(Lx). Therefore LL is fond of (L(LL))(L(LL)). So we can take (L(LL))(L(LL)) for the bird y. Our egocentric bird is then ((L(LL))(L(LL)))((L(LL))(L(LL))).

  * For handy reference to the birds, each is alphabetically listed in “Who’s Who Among the Birds.”

  10

  Is There a Sage Bird?

  Inspector Craig of Scotland Yard was a man of many interests. His activities in crime detection, law, logic, number machines, retrograde analysis, vampirism, philosophy, and theology are familiar to readers of my earlier puzzle books. He was e
qually interested in ornithological logic—a field that applies combinatory logic to the study of birds. He was therefore delighted to hear about the bird forest of the last chapter and decided to visit it and do some “inspecting.”

  When he arrived, the first thing he did was to interview the bird sociologist of the forest, whose name was Professor Fowler. Professor Fowler told Craig of the two laws C1 and C2, the basic composition law and the existence of a mockingbird, from the first problem of the last chapter. From this, Inspector Craig was of course able to deduce that every bird was fond of at least one bird.

  “However,” explained Craig to Fowler, “I would like to go a bit more deeply into the matter. I am what mathematical logicians call a constructivist. I am not satisfied to know merely that given any bird x, there exists somewhere in the forest a bird y of which x is fond; I would like to know how, given a bird x, I can find such a bird y. Is there by any chance a bird in this forest that can supply such information?”

  “I really don’t understand your question,” replied Fowler. “What do you mean by a bird’s supplying such information?”

  “What I want to know,” said Craig, “is whether or not there is some special bird which, whenever I call out the name of a bird x to it, will respond by naming a bird of which x is fond. Do you know whether there is such a bird?”

  “Oh, now I understand what you mean,” said Fowler, “and your question is a very interesting one! All I can tell you is that it has been rumored that there is such a bird, but its existence in this forest has not been substantiated. Such birds are called sage birds—sometimes oracle birds—but, as I said, we don’t know if there are any sage birds here. According to some history books, whose authenticity, however, is uncertain, sage birds were first observed in Greece—in Delphi, in fact—which might account for their also being called oracle birds. Accordingly, the Greek letter Ө is used to denote a sage bird. If there really is such a bird, then it has the remarkable property that for any bird x, x is fond of the bird Өx—in other words, x(Өx) = Өx. Or, as you might put it, if you call out x to Ө, then Ө will name a bird of which x is fond.

  “I have been trying to find a sage bird for a long time now, but I’m afraid I haven’t been very successful. If you could throw any light on the matter, I would be enormously grateful!”

  Inspector Craig rose, thanked Professor Fowler, and told him that he would devote some thought to the matter. Craig then spent the day walking through the forest concentrating deeply on the problem. The next morning he returned to Professor Fowler.

  “I doubt very much,” said Craig, “that—from just the two conditions C1 and C2 that you have told me—it can be determined whether or not this forest contains a sage bird.

  “The trouble is this,” he explained: “We know that there is a mockingbird M. And we know that for any bird x there is some bird y that composes x with the mockingbird M. Then, as you know, x is fond of the bird yy. But given the bird x, how does one find a bird y that composes x with M? If there were some bird A that supplied this information, then the problem would be solvable. But from what you have told me, I have no reason to believe that there is such a bird.”

  “Oh, but there is such a bird,” replied Fowler. “I’m sorry, but I forgot to tell you that we do have a bird A such that whatever bird x you call out to A, A will respond by naming a bird that composes x with M. That is, for any bird x, the bird Ax composes x with M.”

  “Splendid!” said Craig. “That completely solves your problem: This forest does contain a sage bird.”

  How did Craig know this?

  “Wonderful!” said Fowler, after Craig proved that the forest contained a sage bird.

  “And now, what are your plans? You know, perhaps, that this forest is only one of a whole chain of remarkable bird forests. You should definitely visit Curry’s Forest, and before you come to that, you will pass through a forest unusually rich in bird life. You will probably want to spend a good deal of time there; there is so much to learn!”

  Craig thanked Professor Fowler and departed for the next forest. He little realized that this was only the beginning of a summer-long venture!

  SOLUTION

  This problem, though important, is really quite simple!

  To begin with, the bird A described by Fowler is nothing more nor less than a lark! The reason is this: To say that for every bird x, the bird Ax composes x with M is to say that for any bird x and any bird y, (Ax)y = x(My). But My = yy, so x(My) = x(yy). Therefore the bird A described by Fowler satisfies the condition that for any birds x and y, (Ax)y = x(yy), which means that A is a lark.

  And so the problem boils down to this: Given a mockingbird M, a lark L, and the basic composition condition C1, prove that the forest contains a sage bird.

  Well, we have shown in the solution to Problem 25 of the last chapter that any bird x is fond of the bird (Lx)(Lx), hence x is fond of M(Lx), since M(Lx) = (Lx)(Lx). Now, by the basic composition condition C1, there is a bird Ө that composes M with L. This means that for any bird x, Өx = M(Lx). Since x is fond of M(Lx) and M(Lx) = Өx, then x is fond of Өx, which means that Ө is a sage bird.

  In short, any bird that composes M with L is a sage bird.

  The theory of sage birds (technically called fixed point combinators) is a fascinating and basic part of combinatory logic; we have only scratched the surface. We will go more deeply into the theory of sage birds in a later chapter, but we must first turn our attention to some of the more basic birds, which we will do in the next two chapters.

  11

  Birds Galore

  In the next bird forest Craig visited, the resident bird sociologist was named Professor Adriano Bravura. Professor Bravura had an aristocratic, somewhat proud bearing, which many mistook for haughtiness. Craig soon realized that this impression was quite misleading; Professor Bravura was an extremely dedicated scholar who, like many scholars, was often absentminded and abstracted, and this “abstractedness” was what was so often mistaken for detachment and lack of concern for other human beings. Actually, Professor Bravura was a very warmhearted person who took a great interest in his students. Craig learned an enormous amount from him—as will the reader!

  “We have many, many interesting birds in this forest,” said Bravura to Craig at the first interview, “but before I tell you about them, it will be best for me to explain to you a well-known abbreviation concerning parentheses.”

  Professor Bravura then took a pencil and a pad of paper and placed it so that Craig could see what he was writing.

  “Suppose I write down xyz,” said Bravura. “Without further explanation, this notation is ambiguous; you cannot know whether I mean (xy)z or x(yz). Well, the convention is that we will mean (xy)z—or, as we say, if parentheses are omitted, they are to be restored to the left. This is the tradition in combinatory logic, and after a little practice, it makes complex expressions more easily readable.

  “The same convention applies to even more complex expressions—for example, let us look at the expression (xy)zw. We look at (xy) as a unit, and so (xy)zw is really ((xy)z)w. What is xyzw? We first restore parentheses to the leftmost part, which is xy, and so xyzw is (xy)zw, which in turn is ((xy)z)w. And so xyzw is simply an abbreviation for ((xy)z)w.

  “Other examples,” said Bravura: “x(yz)w = (x(yz))w, whereas x(yzw) = x((yz)w).

  “I think you should now try the following exercises to be sure that you fully grasp the principle of restoring parentheses to the left.”

  Here are the exercises Bravura gave Craig; the answers are given immediately afterward.

  Exercises: In each of the following cases, fully restore parentheses to the left.

  a. xy(zwy)v = ?

  b. (xyz)(wvx) = ?

  c. xy(zwv)(xz) = ?

  d. xy(zwv)xz = ? Note: The answer is different from that for (c)!

  e. x(y(zwv))xz = ?

  f. Is the following true or false?

  xyz(AB) = (xyz)(AB)

  g. Suppose A1 = A2. Can w
e conclude that BA1 = BA2? And can we conclude that A1B = A2B?

  h. Suppose xy = z. Which of the following conclusions is valid? Note: Tricky and important!

  1. xyw = zw

  2. wxy = wz

  Answers:

  a. xy(zwy)v = ((xy)((zw)y))v

  b. (xyz)(wvx) = ((xy)z)((wv)x)

  c. xy(zwv)(xz) = ((xy)((zw)v))(xz)

  d. xy(zwv)xz = (((xy)((zw)v))x)z

  e. x(y(zwv))xz = ((x(y((zw)v)))x)z

  f. True; both sides reduce to ((xy)z)(AB).

  g. Both conclusions are correct.

  h. Suppose xy = z.

  1. xyw = zw says that (xy)w = zw, and this is correct, since the birds (xy) and xy are identical and we are given that xy = z, and hence (xy) = z.

  2. wxy = wz says that (wx)y = wz, and this certainly does not follow from the fact that xy = z! What does follow is that w(xy) = wz, but this is very different from (wx)y = wz.

  So the first conclusion follows, but the second does not.

  BLUEBIRDS

  “Now that we have gone through these preliminaries,” said Bravura, “we can get on to the more interesting things about this forest.

  “As I have told you, we have many fascinating birds here. A bird of basic importance is the bluebird—by which I mean a bird B such that for all birds x, y, z, the following holds:

  Bxyz = x(yz)

  “In unabbreviated notation,” said Bravura, “I would have written: ((Bx)y)z = x(yz). However, I find it much easier to read: Bxyz = x(yz).”

  • 1 •

  “Why are bluebirds of basic importance?” asked Craig.

  “For many reasons, which you will see,” replied Bravura. “For one thing, if a forest contains a bluebird—which this forest fortunately does—then the basic composition law must hold: For any bird C and D, there is a bird E that composes C with D. Can you see why?”