To Mock a Mocking Bird
Page 7
So! The Fountain of Youth is really somewhere on the Island of Knights and Knaves! Finding it, however, is a very different story. In general, it is not easy actually to find things on this crazy island! As a matter of fact, Reynolds didn’t find the Fountain of Youth on this particular visit; he merely found out for sure that the fountain was somewhere on the island, and he is planning to go back in search of it. But that is a topic for another book.
PART THREE
TO MOCK
A MOCKINGBIRD
9
To Mock a Mockingbird
A certain enchanted forest is inhabited by talking birds. Given any birds A and B, if you call out the name of B to A, then A will respond by calling out the name of some bird to you; this bird we designate by AB. Thus AB is the bird named by A upon hearing the name of B. Instead of constantly using the cumbersome phrase “A’s response to hearing the name of B,” we shall more simply say: “A’s response to B.” Thus AB is A’s response to B. In general, A’s response to B is not necessarily the same as B’s response to A—in symbols, AB is not necessarily the same bird as BA. Also, given three birds A, B, and C, the bird A(BC) is not necessarily the same as the bird (AB)C. The bird A(BC) is A’s response to the bird BC, whereas the bird (AB)C is the response of the bird AB to the bird C. The use of parentheses is thus necessary to avoid ambiguity; if I just wrote ABC, you could not possibly know whether I meant the bird A(BC) or the bird (AB)C.
Mockingbirds: By a mockingbird is meant a bird M such that for any bird x, the following condition holds:
Mx = xx
M is called a mockingbird for the simple reason that its response to any bird x is the same as x’s response to itself—in other words, M mimics x as far as its response to x goes. This means that if you call out x to M or if you call out x to itself, you will get the same response in either case.*
Composition: The last technical detail before the fun starts is this: Given any birds A, B, and C (not necessarily distinct) the bird C is said to compose A with B if for every bird x the following condition holds:
Cx = A(Bx)
In words, this means that C’s response to x is the same as A’s response to B’s response to x.
TO MOCK A MOCKINGBIRD
1 • The Significance of the Mockingbird
It could happen that if you call out B to A, A might call the same bird B back to you. If this happens, it indicates that A is fond of the bird B. In symbols, A is fond of B means that AB = B.
We are now given that the forest satisfies the following two conditions.
C1 (the composition condition): For any two birds A and B (whether the same or different) there is a bird C such that for any bird x, Cx = A(Bx). In other words, for any birds A and B there is a bird C that composes A with B.
C2 (the mockingbird condition): The forest contains a mockingbird M.
One rumor has it that every bird of the forest is fond of at least one bird. Another rumor has it that there is at least one bird that is not fond of any bird. The interesting thing is that it is possible to settle the matter completely by virtue of the given conditions C1 and C2.
Which of the two rumors is correct?
Note: This is a basic problem in the field known as combinatory logic. The solution, though not lengthy, is extremely ingenious. It is based on a principle that derives ultimately from the work of the logician Kurt Gödel. This principle will permeate parts of many of the chapters that follow.
2 • Egocentric?
A bird x is called egocentric (sometimes narcissistic) if it is fond of itself—that is, if x’s response to x is x. In symbols, x is egocentric if xx = x.
The problem is to prove that under the given conditions C1 and C2 of the last problem, at least one bird is egocentric.
3 • Story of the Agreeable Bird
Two birds A and B are said to agree on a bird x if their responses to x are the same—in other words if Ax = Bx. A bird A is called agreeable if for every bird B, there is at least one bird x on which A and B agree. In other words, A is agreeable if for every bird B there is a bird x such that Ax = Bx.
We now consider the following variant of Problem 1: We are given the composition condition C1, but we are not given that there is a mockingbird; instead, we are given that there is an agreeable bird A. Is this enough to guarantee that every bird is fond of at least one bird?
A bonus question: Why is Problem 1 nothing more than a special case of Problem 3? Hint: Is a mockingbird necessarily agreeable?
4 • A Question on Agreeable Birds
Suppose that the composition condition C1 of Problem 1 holds and that A, B, and C are birds such that C composes A with B. Prove that if C is agreeable then A is also agreeable.
5 • An Exercise in Composition
Again suppose that condition C1 holds. Prove that for any birds A, B, and C there is a bird D such that for every bird x, Dx = A(B(Cx)). This fact is quite useful.
6 • Compatible Birds
Two birds A and B, either the same or different, are called compatible if there is a bird x and a bird y, either the same or different, such that Ax = y and By = x. This means that if you call out x to A then you will get y as a response, whereas if you call out y to B, you will get x as a response.
Prove that if conditions C1 and C2 of Problem 1 hold, then any two birds A and B are compatible.
7 • Happy Birds
A bird A is called happy if it is compatible with itself. This means that there are birds x and y such that Ax = y and Ay = x.
Prove that any bird that is fond of at least one bird must be a happy bird.
8 • Normal Birds
We will henceforth call a bird normal if it is fond of at least one bird. We have just proved that every normal bird is happy. The converse is not necessarily true; a happy bird is not necessarily normal.
Prove that if the composition condition C1 holds and if there is at least one happy bird in the forest, then there is at least one normal bird.
HOPELESS EGOCENTRICITY
9 • Hopelessly Egocentric
We recall that a bird B is called egocentric if BB = B. We call a bird B hopelessly egocentric if for every bird x, Bx = B. This means that whatever bird x you call out to B is irrelevant; it only calls B back to you! Imagine that the bird’s name is Bertrand. When you call out “Arthur,” you get the response “Bertrand”; when you call out “Raymond,” you get the response “Bertrand”; when you call out “Ann,” you get the response “Bertrand.” All this bird can ever think of is itself!
More generally, we say that a bird A is fixated on a bird B if for every bird x, Ax = B. That is, all A can think of is B1 Then a bird is hopelessly egocentric just in the case that it is fixated on itself.
A bird K is called a kestrel if for any birds x and y, (Kx)y = x. Thus if K is a kestrel, then for every bird x, the bird Kx is fixated on x.
Given conditions C1 and C2 of Problem 1, and the existence of a kestrel K, prove that at least one bird is hopelessly egocentric.
10 • Fixation
If x is fixated on y, does it necessarily follow that x is fond of y?
11 • A Fact About Kestrels
Prove that if a kestrel is egocentric, then it must be hopelessly egocentric.
12 • Another Fact About Kestrels
Prove that for any kestrel K and any bird x, if Kx is egocentric then K must be fond of x.
13 • A Simple Exercise
Determine whether the following statement is true or false: If a bird A is hopelessly egocentric, then for any birds x and y, Ax = Ay.
14 • Another Exercise
If A is hopelessly egocentric, does it follow that for any birds x and y, (Ax)y = A?
15 • Hopeless Egocentricity Is Contagious!
Prove that if A is hopelessly egocentric, then for every bird x, the bird Ax is also hopelessly egocentric.
16 • Another Fact About Kestrels
In general, it is not true that if Ax = Ay then x = y. However, it is true if A
happens to be a kestrel K. Prove that if Kx = Ky then x = y. (We shall henceforth refer to this fact as the left cancellation law for kestrels.)
17 • A Fact About Fixation
It is possible that a bird can be fond of more than one bird, but it is not possible for a bird to be fixated on more than one bird. Prove that it is impossible for a bird to be fixated on more than one bird.
18 • Another Fact About Kestrels
Prove that for any kestrel K and any bird x, if K is fond of Kx, then K is fond of x.
19 • A Riddle
Someone once said: “Any egocentric kestrel must be extremely lonely!” Why is this true?
IDENTITY BIRDS
A bird I is called an identity bird if for every bird x the following condition holds:
Ix = x
The identity bird has sometimes been maligned, owing to the fact that whatever bird x you call to I, all I does is to echo x back to you. Superficially, the bird I appears to have no intelligence or imagination; all it can do is repeat what it hears. For this reason, in the past, thoughtless students of ornithology referred to it as the idiot bird. However, a more profound ornithologist once studied the situation in great depth and discovered that the identity bird is in fact highly intelligent! The real reason for its apparently unimaginative behavior is that it has an unusually large heart and hence is fond of every bird! So when you call x to I, the reason it responds by calling back x is not that it can’t think of anything else; it’s just that it wants you to know that it is fond of x!
Since an identity bird is fond of every bird, then it is also fond of itself, so every identity bird is egocentric. However, its egocentricity doesn’t mean that it is any more fond of itself than of any other bird!
Now for a few simple problems about identity birds.
• 20 •
Supposing we are told that the forest contains an identity bird I and that I is agreeable, in the sense of Problem 3. Does it follow that every bird must be fond of at least one bird? Note: We are no longer given conditions C1 and C2.
• 21 •
Suppose we are told that there is an identity bird I and that every bird is fond of at least one bird. Does it necessarily follow that I is agreeable?
• 22 •
Suppose we are told that there is an identity bird I, but we are not told whether I is agreeable or not. However, we are told that every pair of birds is compatible, in the sense of Problem 6. Which of the following conclusions can be validly drawn?
1. Every bird is normal—i.e., fond of at least one bird.
2. I is agreeable.
23 • Why?
The identity bird I, though egocentric, is in general not hopelessly egocentric. Indeed, if there were a hopelessly egocentric identity bird, the situation would be quite sad. Why?
LARKS
A bird L is called a lark if for any birds x and y the following holds:
(Lx)y = x(yy)
Larks have some interesting properties, as we will now see.
• 24 •
Prove that if the forest contains a lark L and an identity bird I, then it must also contain a mockingbird M.
• 25 •
One reason I like larks is this: If there is a lark in the forest, then it follows without further ado that every bird is fond of at least one bird. And so you see, the lark has a wonderful effect on the forest as a whole; its presence makes every bird normal. And since all normal birds are happy, by Problem 7, then a lark L in the forest causes all the birds to be happy!
Why is this true?
26 • Another Riddle
Why is a hopelessly egocentric lark unusually attractive?
• 27 •
Assuming that no bird can be both a lark and a kestrel—as any ornithologist knows!—prove that it is impossible for a lark to be fond of a kestrel.
• 28 •
It might happen, however, that a kestrel K is fond of a lark L. Show that if this happens, then every bird is fond of L.
• 29 •
Now let me tell you the most surprising thing I know about larks: Suppose we are given that the forest contains a lark L and we are not given any other information. From just this one fact alone, it can be proved that at least one bird in the forest must be egocentric!
The proof of this is a bit tricky. Given the lark L, we can actually write down an expression for an egocentric bird—and we can write it using just the letter L, with parentheses, of course. The shortest expression that I have been able to find has a length of 12, not counting parentheses. That is, we can write L twelve times and then by parenthesizing it the right way, have the answer. Care to try it? Can you find a shorter expression than mine that works? Can it be proved that there is no shorter expression in L that works? I don’t know! At any rate, see if you can find an egocentric bird, given the bird L.
SOLUTIONS
1 · The first rumor is correct; every bird A is fond of at least one bird. We prove this as follows:
Take any bird A. Then by condition C1, there is a bird C that composes A with the mockingbird M, because for any bird B, there is a bird C that composes A with B, so this is also true if B happens to be the mockingbird M. Thus for any bird x, Cx = A(Mx), or what is the same thing, A(Mx) = Cx. Since this equation holds for every bird x, then we can substitute C for x, thus getting the equation A(MC) = CC. But MC = CC, since M is a mockingbird, and so in the equation A(MC) = CC, we can substitute CC for MC, thus getting the equation A(CC) = CC. This means that A is fond of the bird CC!
In short, if C is any bird that composes A with M, then A is fond of the bird CC. Also, A is fond of MC, since MC is the same as the bird CC.
2 · We have just seen that conditions C1 and C2 imply that every bird is fond of at least one bird. This means, in particular, that the mockingbird M is fond of at least one bird E. Now we show that E must be egocentric.
First, ME = E, since M is fond of E. But also ME = EE, because M is a mockingbird. So E and EE are both identical with the bird ME, so EE = E. This means that E is fond of E—i.e., that E is egocentric.
Remark: Since E is egocentric and E = ME, then ME is egocentric. Doesn’t the word “ME” tell its own tale?
3 · We are given that the composition condition C1 holds and that there is an agreeable bird A.
Take any bird x. By the composition condition, there is some bird H that composes x with A. Since A is agreeable, then A agrees with H on some bird y. We will show that x must be fond of the bird Ay.
Since A agrees with H on y, then Ay = Hy. But since H composes x with A, then Hy = x(Ay). Therefore Ay = Hy = x(Ay), and so Ay = x(Ay), or what is the same thing, x(Ay) = Ay. This means that x is fond of Ay.
A bonus question: The mockingbird is certainly agreeable, because for any bird x, M agrees with x on the very bird x, since Mx = xx. In other words there is a bird y—namely x itself—such that My = xy.
Since every mockingbird is agreeable, then the given conditions of Problem 3 imply the given conditions of Problem 1, and therefore the solution of Problem 1 gives an alternative solution to Problem 3, though a more complicated one.
4 · We are given that C composes A with B and that C is agreeable. We are also given the composition condition. We are to show that A is agreeable.
Take any bird D. We must show that A agrees with D on some bird or other. Since the composition law holds, then there is a bird E that composes D with B. Also C agrees with E on some bird x, because C is agreeable—thus Cx = Ex. Also Ex = D(Bx), because E composes D with B, and Cx = A(Bx), because C composes A with B. Therefore, since Ex = D(Bx), we have A(Bx) = D(Bx). And so A agrees with D on the bird Bx. This proves that for any bird D, there is a bird on which A and D agree, which means that A is agreeable.
In short, A(Bx) = Cx = Ex = D(Bx).
5 · Suppose the composition law C1 holds. Take any birds A, B, and C. Then there is a bird E that composes B with C, and so for any bird x, Ex = B(Cx), and hence A(Ex) = A(B(Cx)). Using the composition law again, there
is a bird D that composes A with E, and hence Dx = A(Ex). Therefore Dx = A(Ex) = A(B(Cx)), and so Dx = A(B(Cx)).
6 · We are given that conditions C1 and C2 of Problem 1 hold. Therefore every bird is fond of at least one bird, according to the solution to Problem 1. Now take any birds A and B. By condition C1, there is a bird C that composes A with B. The bird C is fond of some bird—call it y. Thus Cy = y. Also Cy = A(By)—because C composes A with B. Therefore A(By) = y. Let x be the bird By. Then Ax = y, and of course By = x. This proves that A and B are compatible.
7 · To say that A is compatible with B doesn’t necessarily mean that there are two distinct birds x and y such that Ax = y and By = x; x and y may be the same bird. So if there is a bird x such that Ax = x and Bx = x, that surely implies that A and B are compatible. Thus if Ax = x, then A is automatically compatible with A, because Ax = y and Ay = x, when y is the same bird as x.