Note: Recall from Chapter 8 that if E composes C with D, it means that for every bird x, Ex = C(Dx).
2 • Bluebirds and Mockingbirds
“Suppose,” said Bravura, “that a bird forest contains a bluebird B and a mockingbird M. Since B is present, the composition law holds, as you have just seen. Therefore, as you know, it follows that every bird x is fond of some bird. However, since B is present, you can write down an expression in terms of B, M, x that describes a bird of which x is fond. Can you see how to write down such an expression?”
3 • Egocentric
“Given a bluebird B and a mockingbird M,” said Bravura, “can you see how to write down an expression for an egocentric bird?”
4 • Hopelessly Egocentric
“Now,” said Bravura, “suppose a forest contains a bluebird B, a mockingbird M, and a kestrel K. See if you can write down an expression in terms of B, M, and K for a hopelessly egocentric bird.”
SOME DERIVATIVES OF THE BLUEBIRD
“And now,” said Bravura, “let us forget about mockingbirds and kestrels for a while and concentrate on just the bluebird B. From just this one bird alone, many useful birds can be derived. Not all of them are of major importance, but several of them will crop up from time to time in the course of your study.”
5 • Doves
“For example, one fairly important bird is the dove, by which is meant a bird D such that for any birds x, y, z, w, the following condition holds:
Dxyzw = xy(zw)
“The bird D can be derived from B alone. Can you see how?”
6 • Blackbirds
“Then,” said Bravura, “there is the blackbird—a bird B1 such that for any birds x, y, z, w, the following condition holds:
B1xyzw = x(yzw)
“Prove that any forest containing a bluebird must also contain a blackbird.
“Of course,” added Bravura, “in deriving a blackbird from a bluebird, you are free to use the dove D if that is helpful, since you have already seen how D can be derived from B.”
7 • Eagles
“Then there is the eagle,” said Bravura, “by which is meant a bird E such that for any birds x, y, z, w, v, the following condition holds:
Exyzwv = xy(zwv)
“The eagle can be derived from just the bird B. Can you see how? Again, it will simplify your derivation to use birds already derived from B.”
8 • Buntings
“A bunting,” said Bravura, “is a bird B2 satisfying the following condition—for any birds x, y, z, w, v, of course:
B2xyzwv = x(yzwv)
“Given B, find a bunting B2.”
9 • Dickcissels
Bravura continued: “By a dickcissel I mean a bird D1 satisfying the following condition:
D1xyzwv = xyz(wv)
“Show how a dickcissel D1 can be derived from a bluebird B.”
10 • Becards
“Then there is the becard,” said Bravura, “a bird B3 such that for all birds x, y, z, w, the following condition holds:
B3xyzw = x(y(zw))
“Can you see how to derive a becard from a bluebird, and from any other birds already derived from B?”
11 • Dovekies
“Then there is the dovekie,” said Bravura, “which is a bird D2 satisfying the following condition:
D2xyzwv = x(yz)(wv)
“Can you see how to derive a dovekie D2 from a bluebird B?”
12 • Bald Eagles
“And now,” said Bravura, “given a bluebird B, see if you can derive a bald eagle—a bird Ê such that for all birds x, y1, y2, y3, z1, z2, z3, the following condition holds:
Êxy1y2y3z1z2z3 = x(y1y2y3)(z1z2z3).”
“I think you have had enough problems for today,” said Bravura. “We have now derived eight different birds from the one bird B. We could derive many more, but I think you have seen enough to get a good feeling for the behavior of the bluebird. All these birds—including B—belong to a family of birds known as compositors. They serve to introduce parentheses. The only two that you need remember are the bluebird B and the dove D; they are standard in the literature of combinatory logic. The other seven birds don’t have standard names, but I have found it convenient to give them names, as some of them will crop up again.
“Tomorrow, I will tell you about some very different birds.”
SOME OTHER BIRDS
Inspector Craig returned bright and early the next morning. He was surprised to find Professor Bravura in the garden, seated at a table with paper, pencils, and piles of notes. Two cups of freshly brewed steaming hot coffee had been laid out.
13 • Warblers
“Too beautiful a morning to work indoors,” said Bravura. “Besides, I may be able to show you some of the birds we discuss.
“Ah, there goes a warbler!” said Bravura. “This bird W is an important bird and is quite standard in combinatory logic. It is defined by the following condition:
Wxy = xyy
“Do not confuse this with the lark L!” cautioned Bravura. “Remember, Lxy = x(yy), whereas Wxy = xyy. These are very different birds!
“I have a nice little problem for you,” continued Bravura. “Prove that any forest containing a warbler W and a kestrel K must contain a mockingbird M.”
After a bit of time, Bravura said, “I see you are having difficulty. I think I will first give you two simpler problems.”
• 14 •
“Show that from a warbler W and an identity bird I we can get a mockingbird.”
Craig solved this quite easily.
• 15 •
“Now show that from a warbler W and a kestrel K we can get an identity bird.”
“Oh, I get the idea!” said Craig.
16 • Cardinals
Just then, a brilliant red bird flew by.
“A cardinal!” said Bravura. “One of my favorite birds! It also plays a basic role in combinatory logic. The cardinal C is defined by the following condition:
Cxyz = xzy
“The cardinal belongs to an important family of birds known as permuting birds. You see that in the above equation, the variables y and z have got switched around.
“Here’s an easy problem for you,” said Bravura. “Prove that any forest containing a cardinal and a kestrel must contain an identity bird.”
17 • Thrushes
“A bird closely related to the cardinal is the thrush,” said Bravura. “Why, there is one right over there! A thrush T is defined by the following condition:
Txy = yx
“The thrush is the simplest of the permuting birds,” said Bravura. “It is derivable from a cardinal C and an identity bird I. Can you see how?”
18 • Commuting Birds
“Two birds x and y are said to commute,” said Bravura, “if xy = yx. This means that it makes no difference whether you call out y to x, or x to y; you get the same response in either case.
“There’s an interesting thing about thrushes,” said Bravura. “If a forest contains a thrush, and if every bird of the forest is fond of some bird, then there must be at least one bird A that commutes with every bird. Can you see how to prove this?”
• 19 •
“Given a bluebird B, a thrush T, and a mockingbird M,” said Bravura, “find a bird that commutes with every bird.”
BLUEBIRDS AND THRUSHES
“Bluebirds and thrushes work beautifully together!” said Bravura. “From these two birds, you can derive a whole variety of birds known as permuting birds. For one thing, from a bluebird B and a thrush T, you can derive a cardinal—this was discovered by the logician Alonzo Church in 1941.”
“That sounds interesting,” said Craig. “How is it done?”
“The construction is a bit tricky,” said Bravura. “Church’s expression for a cardinal C in terms of B and T has eight letters, and I doubt that it can be done with fewer. I will simplify the problem for you by first deriving another bird—one useful in its own right.”
20 • Robins
>
“From B and T,” said Bravura, “we can derive a bird R called a robin which satisfies the following condition:
Rxyz = yzx
“Given a bluebird and a thrush, do you see how to derive a robin?”
21 • Robins and Cardinals
“And now, from just the robin alone, we can derive a cardinal. Can you see how? The solution is quite pretty!”
A bonus question: “Putting the last two problems together,” said Bravura, “you can see how to derive C from B and T. However, the solution you then get will contain nine letters. It can be shortened by one letter. Can you see how?”
22 • Two Useful Laws
“The following two laws are useful,” said Bravura. “We let R be BBT and C be RRR. Prove that for any bird x, the following facts hold:
a. Cx = RxR
b. Cx = B(Tx)R.”
23 • A Question
“You have just seen that a cardinal can be derived from a robin. Can a robin be derived from a cardinal?”
24 • Finches
“Ah, there goes a finch!” said Bravura. “A finch is a bird F satisfying the following condition:
Fxyz = zyx
“The finch is another permuting bird, of course, and it can also be derived from B and T. This can be done in several ways. For one thing, a finch can be easily derived from a bluebird, a robin, and a cardinal—and hence from a bluebird and a robin or from a bluebird and a cardinal. Can you see how?”
• 25 •
“Alternatively, a finch can be derived from a thrush T and an eagle E. Can you see how?”
• 26 •
“Now you have available two methods of expressing a finch in terms of a bluebird B and a thrush T. You will see that one of them yields a much shorter expression than the other.”
27 • Vireos
“Ah, there goes a vireo!” said Bravura in some excitement. “If you ever get to study combinatorial birds in relation to arithmetic—as doubtless you will—you will find the vireo to be of basic importance. The vireo V is also a permuting bird—it is defined by the following condition:
Vxyz = zxy
“The vireo has a sort of opposite effect to the robin,” commented Bravura. “This bird is also derivable from B and T. One way is to derive it from a cardinal and a finch. Can you see how?”
• 28 •
“How would you most easily express a vireo in terms of a finch and a robin?” asked Bravura. “It can be done with an expression of only three letters.”
29 • A Question
“I will later show you another way of deriving a vireo,” said Bravura. “Meanwhile I’d like to ask you a question. You have seen that a vireo is derivable from a cardinal and a finch. Is a finch derivable from a cardinal and a vireo?”
30 • A Curiosity
“Another curiosity,” said Bravura. “Show that any forest containing a robin and a kestrel must contain an identity bird.”
SOME RELATIVES
It was now about noon, and Mrs. Bravura—an exceedingly beautiful, delicate, and refined Venetian lady—brought out a magnificent lunch. After the royal repast, the lesson continued.
“I should now like to tell you about some useful relatives of the cardinal, robin, finch, and vireo,” said Bravura. “All of them can be derived from just the two birds B and T—in fact, from B and C.”
31 • The Bird C*
“First there is the bird C* called a cardinal once removed, satisfying the following condition:
C*xyzw = xywz
“Notice,” said Bravura, “that in this equation, if we erased x from both sides, and also erased the star, we would have the true statement Cyzw = ywz.
“This is the idea behind the term ‘once removed.’ The bird C* is like C, except that its action is ‘deferred’ until we skip over x; we then ‘act’ on the expression yzw as if we were using a cardinal.
“And now see if you can derive C* from B and C. This is quite simple!”
32 • The Bird R*
“The bird R*—a robin once removed—bears much the same relation to R as C* does to C. It is defined by the following condition:
R*xyzw = xzwy
“Show that R* is derivable from B and C—and hence from B and T.”
33 • The Bird F*
“By a finch once removed we mean a bird F* satisfying the following condition:
F*xyzw = xwzy
“Now derive F* from birds derivable from B and C.”
34 • The Bird V*
“Finally, we have the vireo once removed—a bird V* satisfying the following condition:
V*xyzw = xwzy
“Show how to derive V* from birds derivable from B and C.”
35 • Twice Removed
“Given birds B and C, find birds C**, R**, F**, V** such that for any birds x, y, z1, z2, z3 the following conditions hold:
C**xyz1z2z3 = xyz1z3z2
R**xyz1z2z3 = xyz2z3z1
F**xyz1z2z3 = xyz3z2z1
V**xyz1z2z3 = xyz3z1z2
“These are the birds C, R, F, V twice removed. They will occasionally be useful.”
36 • Vireos Revisited
“You have seen that a vireo is derivable from a cardinal and a finch. It is also derivable from the two birds C* and T. Can you see how?”
QUEER BIRDS
“And now,” said Bravura, “we turn to an interesting family of birds which both parenthesize and permute. They are all derivable from B and T.”
37 • Queer Birds
“The most important member of the family is the queer bird Q defined by the following condition:
Qxyz = y(xz)
“As you can see, Q both introduces parentheses and permutes the order of the letters x and y.
“A comparison of Q with the bluebird B is worth noting: For any birds x and y, the bird Bxy composes x with y, whereas Qxy composes y with x.
“The bird Q is quite easily derived from B and one other bird that you have already derived from B and T. Can you see which one and how?”
38 • Quixotic Birds
“The queer bird Q has several cousins; perhaps the most important one is the quixotic bird Q1 defined by the condition:
Q1xyz = x(zy)
“Show that Q1 is derivable from B and T. Again, you may of course use any birds previously derived from B and T.”
39 • Quizzical Birds
“Then there is the quizzical bird Q2—another cousin of Q. It is defined by the condition:
Q2xyz = y(zx)
“Show that Q2 is derivable from B and T.”
40 • A Problem
“Here is a little problem for you,” said Bravura. “Suppose we are given that a certain bird forest contains a cardinal, but we are not given that it contains a bluebird or a thrush. Prove that if the forest contains either a quixotic bird or a quizzical bird, then it must contain the other as well.”
41 • Quirky Birds
“Another cousin of Q is the quirky bird Q3 defined by the following condition:
Q3xyz = z(xy)
“Show that Q3 is derivable from B and T.”
42 • Quacky Birds
“The last cousin of Q is the quacky bird Q4 defined by the following condition:
Q4xyz = z(yx).”
“What a strange name!” exclaimed Craig.
“I didn’t name it; it was named after a certain Professor Quack, who discovered it. Anyhow, can you see how to derive it from B and T?”
43 • An Old Proverb
“There is an old proverb,” said Bravura, “that says that if a cardinal is present, then you can’t have a quirky bird without a quacky bird, or a quacky bird without a quirky bird. And if there isn’t such a proverb, then there should be! Can you see why the proverb is true?”
44 • A Question
“Is a quacky bird derivable from Q1 and T?”
45 • An Interesting Fact About the Queer Bird Q
“You have seen that the queer bird Q is derivable from the bluebird B and the thr
ush T. It is of interest that you can alternatively derive a bluebird B from a queer bird Q and a thrush T. Can you see how? The method is a bit tricky!”
• 46 •
“One can derive a cardinal C from Q and T more easily than from B and T—in fact, you need an expression of only four letters. Can you find it?”
47 • Goldfinches
“Another bird derivable from B and T which I have found useful is the goldfinch G defined by the following condition:
To Mock a Mocking Bird Page 9
