To Mock a Mocking Bird

by Raymond M. Smullyan

Gxyzw = xw(yz)

  “Can you see how to derive it from B and T?”

  · · ·

  “We could go on endlessly deriving birds from B and T,” said Bravura, “but it is now getting chilly and Mrs. Bravura has prepared a nice dinner for us. Tomorrow I will tell you about some other birds.”

  SOLUTIONS

  1 · Given a bluebird B, we are to show that for any birds C and D, there is a bird E that composes C with D. Well, BCD is such a bird E, because for any bird x, (BCD)x = ((BC)D)x = C(Dx). Therefore BCD composes C with D.

  2 · We saw in the solution to Problem 1 of Chapter 9 that if y is any bird that composes x with M, then x is fond of the bird yy. Now, BxM composes x with M (according to the last problem), and so x must be fond of (BxM)(BxM).

  Let us double-check: (BxM)(BxM) = BxM(BxM) = x(M(BxM)) = x((BxM)(BxM))—because M(BxM) = (BxM(BxM)). So (BxM)(BxM) = x((BxM)(BxM)), or what is the same thing, x((BxM)(BxM)) = (BxM)(BxM), which means that x is fond of the bird (BxM)(BxM).

  The expression (BxM)(BxM) can be shortened to M(BxM). So x is fond of M(BxM).

  3 · We have just seen that for any bird x, x is fond of M(BxM). If we take x to be the mockingbird M, then M is fond of M(BMM). Now, in the solution to Problem 2 in Chapter 9, we saw that any bird of which the mockingbird is fond must be egocentric. Therefore M(BMM) is egocentric.

  Let us double-check: M(BMM) = (BMM)(BMM) = BMM(BMM) = M(M(BMM)) = (M(BMM))(M(BMM)). And so we see that M(BMM) = (M(BMM))(M(BMM)), or what is the same thing, (M(BMM))(M(BMM)) = M(BMM), which means that M(BMM) is egocentric.

  4 · Since for any bird x, x is fond of M(BxM), then the kestrel K is fond of M(BKM). Therefore M(BKM) is hopelessly egocentric, according to the solution of Problem 9 of Chapter 9, in which we saw that any bird of which the kestrel is fond must be hopelessly egocentric.

  5 · It is sometimes easiest to work these problems backward. We are looking for a bird D such that Dxyzw = (xy)(zw). Let us look at the expression (xy)(zw) and see how we can get back to Dxyzw, where D is the bird to be found. Well, we look at the expression (xy) as a unit—call it A—and so (xy)(zw) = A(zw), which we recognize as BAzw, which is B(xy)zw. So the first step of the “backward” argument is to recognize (xy)(zw) as B(xy)zw. Next, we look at the front end B(xy) of the expression and recognize it as BBxy. And so B(xy)zw is BBxyzw. Therefore we take D to be the bird BB.

  Let us double-check by running the argument forward.

  Dxyzw = BBxyzw, since D = BB.

  = B(xy)zw, since BBxy = B(xy).

  = (xy)(zw) = xy(zw)

  6 · Since we have already found the dove D from B, we are free to use it. In other words, in any solution for B1 in terms of B and D, we can replace D by BB, thus getting a solution in terms of B alone.

  Again we will work the problem backward.

  x(yzw) = x((yz)w) = Bx(yz)w. We recognize Bx(yz) as DBxyz, and so Bx(yz)w = DBxyzw. Therefore x(yzw) = DBxyzw, or what is the same thing, DBxyzw = x(yzw). We can therefore take B1 to be the bird DB. The reader can check the solution by running the argument forward.

  In terms of B alone, B1 = (BB)B, which also can be written B1 = BBB.

  7 · We will use the bird B1 found in the last problem. Again we will work the problem backward.

  xy(zwv) = (xy)(zwv). Looking at (xy) as a unit, we can see that (xy)(zwv) = B1(xy)zwv. Also B1(xy) = BB1xy, so B1(xy)zwv = BB1xyzwv. And so we take E to be the bird BB1.

  In terms of B alone, E = BB1 = B(BBB).

  To illustrate a point, suppose we tried to find E directly from B, without using any birds previously derived from B. We could proceed as follows:

  We look at the expression xy(zwv). The first thing we try to do is to free the last letter v from parentheses. Well, xy(zwv) = (xy)((zw)v) = B(xy)(zw)v. Now we have freed v from parentheses. We next work on the expression B(xy)(zw), and we would like to free w from parentheses. Looking at B(xy) as a unit, we see that B(xy)(zw) = B(B(xy))zw. We have now freed w from parentheses, and as good fortune would have it we have freed z as well. It remains merely to work on B(B(xy)). We wish to free y from parentheses, but since it is enclosed in two pairs of parentheses, we first free it from the outer pair. Well, B(B(xy)) = BBB(xy). We now look at BBB as a unit and see that BBB(xy) = B(BBB)xy. And so we take E to be B(BBB), which is the same solution we got before.

  In this analysis, we have substantially duplicated the labor of deriving the bird B1, and had this problem been posed before Problem 6, we would have had to do this. The moral is that in solving these problems, the reader should be on the lookout for solutions to earlier problems that might be helpful.

  8 · Starting from scratch, the solution would be long. Using the eagle of the last problem, the solution is easy:

  x(yzwv) = x((yzw)v) = Bx(yzw)v

  But Bx(yzw) is EBxyzw, so Bx(yzw)v = EBxyzwv. So we take B2 to be EB.

  In terms of B alone, B2 = B(BBB)B.

  9 · There are two ways we can go about this which will be interesting to compare.

  Our first method uses the dove D. Now, xyz(wv) = (xy)z(wv). Looking at (xy) as a unit, we see that (xy)z(wv) = D(xy)zwv. Also D(xy) = BDxy, and so D(xy)zwv = BDxyzwv. And so we take D1 to be BD, which in terms of B alone is B(BB).

  We can also look at the matter this way: xyz(wv) = (xyz)(wv). Looking at (xyz) as a unit, we see that (xyz)(wv) = B(xyz)wv. However, B(xyz) we recognize as B1Bxyz. Therefore B1B is also a solution.

  Now, B1 = BBB, so B1B = BBBB. But BBBB = B(BB), and so we really get the same solution.

  10 · We use the bird D1 of the last problem. Looking at (zw) as a unit, x(y(zw)) = Bxy(zw) = D1Bxyzw. So we take B3 to be D1B.

  In terms of B alone, B3 = B(BB)B.

  11 · Again, we can go about this two ways. On the one hand, if we look at (yz) as a unit, then x(yz)(wv) = Dx(yz)wv. Also Dx(yz) = DDxyz, and so we can take D2 to be DD, which in terms of B is BB(BB).

  On the other hand, we can look at x(yz) as a unit and see that x(yz)(wv) = B(x(yz))wv. But B(x(yz)) = B3Bxyz, and so B3B is also a solution.

  It is really the same solution, since B3B = B(BB)BB = BDBB = D(BB) = DD, which in turn is BB(BB).

  We might remark that we have proved a stronger result than was called for: We were required to derive D2 from B, but we have in fact succeeded in deriving it from D, since D2 = DD. Therefore if we were not told that the forest contains a bluebird, but were given only the weaker condition that it contains a dove, this would still be enough to imply that the forest contains a dovekie.

  12 · We will prove the stronger result that if the forest contains an eagle (without necessarily containing a bluebird) then it must contain a bald eagle.

  Looking at (y1y2y3) as a unit, we see that x(y1y2y3)(z1z2z3) = Ex(y1y2y3)z1z2z3. But Ex(y1y2y3) = EExy1y2y3, and so x(y1y2y3)(z1z2z3) = Ex(y1y2y3)z1z2z3 = EExy1y2y3z1z2z3. And so we take Ě to be EE.

  In terms of B, the bird EE is B(BBB)(B(BBB)).

  13, 14, and 15 · First, we shall do Problem 14: Given W and I, the bird WI is a mockingbird, because for any bird x, WIx = Ixx = xx, since Ix = x.

  Now for Problem 15: Given W and K, the bird WK is an identity bird, because for any bird x, WKx = Kxx = x.

  Putting these two problems together, WK is an identity bird, and hence W(WK) should be a mockingbird by Problem 14. Let us check:

  W(WK)x = WKxx = (WKx)x = (Kxx)x = xx.

  Yes, W(WK) is a mockingbird. This solves Problem 13.

  16 · For any bird A whatsoever, the bird CKA is an identity bird, because for any bird x, CKAx = KxA = x. So, for example, CKK is an identity bird; so is CKC.

  17 · CI is a thrush, because for any birds x and y, CIxy = Iyx = yx.

  18 · The given condition of the problem implies that the thrush T is fond of some bird A. Thus TA = A. Then for any bird x, TAx = Ax. Also TAx = xA, since T is a thrush. Therefore Ax = xA, and so A commutes with every bird x.

  19 · Given the bluebird B and the mockingbird M, as well as the thrush T, we know from Problem 2 of this chapter that T is fond of the bird M(BTM). Remember that for a
ny bird x, x is fond of M(BxM). Therefore, according to the last problem, M(BTM) commutes with every bird.

  20 · We will work the problem backward: yzx = Tx(yz). We recall the dove D and we see that Tx(yz) = DTxyz. Therefore we take R to be DT. In terms of B and T alone, R = BBT.

  21 · Working the problem backward, with only a robin available, we find the solution virtually forced on us! We want to get xzy back into the position xyz. Well, xzy = Ryxz—what else can we do? Now, Ryx = RxRy—again, what other move could we make? Finally, RxR = RRRx.

  Retracing our steps, RRRx = RxR, hence RRRxy = RxRy = Ryx. Since RRRxy = Ryx, then RRRxyz = Ryxz = xzy. Therefore we take our cardinal C to be the bird RRR.

  A bonus question: When written in terms of B and T, C = (BBT)(BBT)(BBT). This expression can be shortened by one letter: C = RRR = BBTRR = B(TR)R, since BBTR = B(TR). So C = B(T(BBT))(BBT).

  The expression B(T(BBT))(BBT) has only eight letters and is Alonzo Church’s expression for a cardinal. Personally, I find it easier to remember the cardinal as RRR.

  22 · a. Cx = RRRx = RxR

  b. Since Cx = RxR and R = BBT, then Cx = BBTxR = B(Tx)R.

  23 · Yes; CC is a robin, because CCxy = Cyx, hence CCxyz = Cyxz = yzx.

  24 · We will work the problem backwards: zyx = Rxzy = (Rx)zy = C(Rx)yz = BCRxyz. And so we take F to be BCR.

  25 · We can also analyze the situation this way: zyx = Tx(zy) = Tx(Tyz) = ETxTyz = (ETx)Tyz = TT(ETx)yz, because (ETx)T = TT(ETx). Continuing, TT(ETx) = ETTETx, hence TT(ETx)yz = ETTETxyz. Therefore we can take F to be ETTET.

  26 · If we take F to be BCR, as in Problem 24, then in terms of B and T, the bird F = B(B(T(BBT))(BBT))(BBT).

  We get a shorter solution if we express F as ETTET and then reduce to B and T. This is done as follows: ETTET = B(BBB)TTET, because E = B(BBB). Now B(BBB)TTET = BBB(TT)ET = B(B(TT))ET = B(TT)(ET) = B(TT)(B(BBB)T). And so we get a solution shorter by four letters.

  27 · zxy = Fyxz = CFxyz, because Fyx = CFxy. We therefore can take V to be CF.

  28 · According to law (a) stated in Problem 22, CF = RFR, and CF is a vireo. So RFR is a vireo.

  29 · Yes; CV is a finch, because CVxyz = Vyxz = zyx.

  30 · For any bird A, the bird RAK must be an identity bird, because RAKx = KxA = x. So, for example, RRK and RKK are both identity birds.

  31 · xywz = (xy)wz = C(xy)zw = BCxyzw. And so we take C* to be BC.

  32 · Actually, we can get the bird R* from just C*: xzwy = C*xzyw. Also C*xzy = C*C*xyz, therefore C*xzyw = C*C*xyzw. So, xzwy = C*C*xyzw. We therefore take R* to be C*C*.

  33 · We can get F* from B, C*, and R* as follows: xwzy = R*xywz = (R*x)ywz = C*(R*x)yzw = BC*R*xyzw, since C*(R*x) = BC*R*x, so we take F* to be BC*R*.

  34 · Just as we got V from C and F (V = CF), we can get V* from C* and F*.

  xwyz = F*xzyw = C*F*xyzw, because F*xzy = C*F*xyz. And so we take V* to be C*F*.

  35 · The secret here is remarkably simple! Take C** to be BC*; R** to be BR*; F** to be BF*; and V** to be BV*.

  36 · C*T is a vireo, because C*Txyz = Txzy = zxy. This means that BCT is a vireo.

  37 · We can get Q from a bluebird B and a cardinal C as follows:

  y(xz) = Byxz = CBxyz, since Byx = CBxy.

  And so we take Q to be CB.

  In terms of B and T, Q = CB = RRRB = RBR = BBBTBR = B(TB)R = B(TB)(BBT).

  38 · We will now find a good use for the starred birds of “some relatives of bluebirds and thrushes.” x(zy) = Bxzy = C*Bxyz. We can therefore take Q1 to be C*B. In terms of B and C, we take Q1 to be BCB.

  39 · y(zx) = Byzx = R*Bxyz. We can therefore take Q2 to be R*B. In terms of B and C, we take Q2 to be BC(BC)B or, more simply, C(BCB).

  40 · Suppose the forest contains a cardinal C. If a quixotic bird Q1 is present, a CQ1 must be a quizzical bird, because CQ1xyz = Q1yxz = y(zx). On the other hand, if a quizzical bird Q2 is present, then CQ2 must be a quixotic bird, because CQ2xyz = Q2yxz = x(zy).

  41 · z(xy) = Bzxy = V*Bxyz. We can therefore take Q3 to be V*B.

  However, Q3 can be gotten directly from B and T much more simply: z(xy) = T(xy)z = BTxyz. And so it is simpler to take Q3 to be BT.

  42 · z(yx) = Bzyx = F*Bxyz. And so we can take Q4 to be F*B. Another solution follows from the next problem.

  43 · Suppose a cardinal C is present. If a quirky bird Q3 is present, then CQ3 must be a quacky bird, because CQ3xyz = Q3yxz = z(yx). On the other hand, if a quacky bird Q4 is present, then CQ4 must be a quirky bird, because CQ4xyz = Q4yxz = z(xy).

  Since BT is a quirky bird, then C(BT) is a quacky bird, and so for Q4 we can take C(BT) instead of F*B.

  44 · Yes; Q1T is a quacky bird, since Q1Txyz = T(yx)z = z(yx).

  Since we can take Q1 to be BCB, then Q1T = BCBT = C(BT), and we get the same solution as if we took Q4 to be CQ3.

  45 · QT(QQ) is a bluebird because QT(QQ)xyz = QQ(Tx)yz = Tx(Qy)z = Qyxz = x(yz).

  46 · QQ(QT) is a cardinal, since QQ(QT)xyz = QT(Qx)yz = Qx(Ty)z = Ty(xz) = (xz)y = xzy.

  47 · xw(yz) = Cx(yz)w = B(Cx)yzw = BBCxyzw. And so we take G to be BBC.

  The bird G has some curious properties, as we will see later on.

  12

  Mockingbirds, Warblers, and Starlings

  MORE ON MOCKINGBIRDS

  Inspector Craig returned early the next morning and again found Professor Bravura in the garden. The first thing that struck Craig was the singing of a distant bird whose song was the strangest that Craig had ever heard. It seemed totally disjointed; first there was a simple melodic line and then, out of the blue, a trill that seemed totally unrelated to the melody. Then followed a melody in a completely unrelated key!

  “You’ve never heard a mockingbird before?” asked Bravura, who noticed Craig’s astonishment.

  “I guess not! It sounds almost mad!”

  “Oh, well,” said Bravura, “it remembers bits and snatches from the other birds and doesn’t always put them together in the most logical order. I must say, though, that this particular mockingbird sounds wilder than any I’ve ever heard.

  “Let me tell you some combinatorial properties of the mockingbird M,” continued Bravura. “It has what is called a duplicative effect—it causes repetition of variables. It has this in common with the lark and the warbler. No bird derivable from B and T can have a duplicative effect, so the mockingbird is quite independent of them—it is definitely not derivable from B and T. But from the three birds B, T, and M, a whole variety of important birds can be derived.”

  1 • The Bird M2

  “A very simple, but useful, example is the bird M2—which I sometimes call a ‘double’ mockingbird—defined by the condition:

  M2xy = xy(xy)

  “This bird is derivable from just B and M. That’s pretty obvious, isn’t it?”

  2 • Larks

  “You recall the lark L satisfying the condition Lxy = x(yy). Well, L is derivable from B, T, and M. One way is to derive it from B, C, and M, or from B, R, and M. Can you see how?”

  • 3 •

  “I might mention, incidentally, that L is also derivable from the bluebird B and the warbler W. Can you see how? Actually, this fact is rather important.”

  • 4 •

  “My favorite construction of a lark,” said Bravura, “uses just the mockingbird M and the queer bird Q. It is also the simplest! Can you see how it’s done?”

  WARBLERS

  Just then a warbler flew by.

  “Tell me,” said Craig, “can a warbler be derived from B, T, and M? Since a lark can, I would not be too surprised if a warbler can.”

  “Ah, that’s a good question,” replied Bravura, “and it has a fascinating history. The logician Alonzo Church was interested in the entire class of birds derivable from the four birds B, T, M, and I. My forest happens to follow the thinking of Church; all my birds are derivable from B, T, M, and I. Now, in 1941, Church showed how to derive a warbler from B, T, M, and I. His method was both bizarre and ingenious; his expression for W in terms of B, T, M,
and I involved twenty-four letters and thirteen pairs of parentheses! I will tell you about it another time.” Note to reader: I discuss this in some of the exercises of this chapter.

  “Shortly after,” continued Bravura, “the logician J. Barkley Rosser found a much shorter expression—one with only ten letters. In looking at his expression, I noticed that he didn’t use the identity bird I at all, hence your guess was correct: A warbler can be derived from just B, T, and M. It can be derived even more simply from B, C, and M—and more simply still from B, C, R, and M. But first let me tell you about another bird closely related to W.”

  5 • The Bird W’

  “Show that from B, T, and M you can derive a bird W’ satisfying the following condition:

  W’xy = yxx

  “We might call W’ a converse warbler,” said Bravura. “Curiously enough, W’ is easier to derive than W. It is particularly simple to derive W’ from B, R, and M. Can you see how?”

  6 • The Warbler

  “Now that you have W’, it is simple to get W. In fact, W can be derived from B, R, C, and M using an expression of only four letters. Can you see how?”

  • 7 •

  “Now express W in terms of B, T, and M. This can be done with an expression of only ten letters, and there are two such expressions.”

  8 • A Question

  “You now see that W is derivable from B, T, and M. Is a mockingbird M derivable from B, T, and a warbler W?”

  9 • Two Relatives of W