SOLUTIONS
1 · Let us first observe that it follows from Byrd’s first two laws that if y sings on all days on which x sings, then the bird Pxy must sing on all days. Reason: Suppose that y sings on all days on which x sings. Now consider any day. Either x sings on that day or it doesn’t. If x doesn’t, then Pxy sings on that day by Byrd’s second law. Now suppose x does sing on that day. Then y also sings on that day (because of the assumption that y sings on all days on which x sings), and hence Pxy must sing on that day by Byrd’s first law. This proves that regardless of whether x does or doesn’t sing on that day, the bird Pxy sings on that day. Hence Pxy sings on all days.
Now we will show that given any bird x, it sings on all days. Well, by Law 4, there is a bird y that sings on those and only those days on which Pyx sings. Now, consider any day on which y sings. Pyx also sings on that day, by Law 4, and since y sings on that day, then x sings on that day, by Law 3. This proves that x sings on all days on which y sings, and hence Pyx sings on all days, by the argument of the preceding paragraph. Then, since y sings on the same days as Pyx, the bird y sings on all days. Therefore, on any day at all, the bird y and the bird Pyx both sing, hence x also sings on that day, by Law 3. This proves that x sings on all days.
2 · If we are given just L alone or just C alone, then I see no way of proving that all the birds sing on all days, but if we are given both C and L, then we can derive Law 4 as follows:
Since the lark L is present, then every bird is fond of at least one bird; we recall that x is fond of Lx(Lx). Now take any bird x. Then the bird CPx is fond of some bird y, which means that CPxy = y, hence y = CPxy. But also CPxy = Pyx, and so y = Pyx. Then of course y sings on the very same days as Pyx, because y is the bird Pyx! Thus Law 4 follows.
3 · Suppose that instead of being given the presence of both C and L, we are given that there is a bird A present satisfying the condition Axyz = x(zz)y. Then for any birds x and y, APxy = P(yy)x. Hence APx(APx) = P(APx(APx))x, and so y = Pyx, where y is the bird APx(APx).
SOME BONUS EXERCISES
Exercise 1: Suppose we are given Byrd’s first three laws but not the fourth. Prove that for any bird x, y, and z the following facts hold:
a. Pxx sings on all days.
b. If Py(Pyx) sings on all days, so does Pyx.
c. If Pxy and Pyz sing on all days, so does Pxz.
d. If Px(Pyz) sings on all days, so does P(Pxy)(Pyz).
e. If Px(Pyz) sings on all days, so does Py(Pxz).
Exercise 2: Suppose we have a bird forest in which certain birds are called lively. We are not given a definition of lively, but we are told that there is a bird P such that the following three conditions hold:
a. For any birds x and y, if Px(Pxy) is lively, so is Pxy.
b. For any birds x and y, if x and Pxy are both lively, so is y.
c. For any bird x there is a bird y such that the birds Py(Pyx) and P(Pyx)y are both lively.
Show that all the birds of the forest are lively.
Exercise 3: The above exercise contains a somewhat stronger result than that of Problem 1 concerning Curry’s Forest. Define a bird of Curry’s Forest to be lively if it sings on all days. Then show that Byrd’s four laws imply that the three conditions above all hold. It then follows from Exercise 2 that all the birds of the forest sing on all days, hence the solution of Problem 1 is a corollary of Exercise 2.
15
Russell’s Forest
The next forest visited by Inspector Craig was known as Russell’s Forest. Almost as soon as Craig arrived, he had an interview with a bird sociologist named McSnurd. He told McSnurd about his experiences in the last forest.
“As far as I know,” said McSnurd, “we have no bird here satisfying Byrd’s four laws. What we do have is a special bird a such that for any bird x, the bird ax sings on those and only those days on which xx sings. Also, for any bird x, there is a bird x’ such that for every bird y, the bird x’y sings on those and only those days on which xy does not sing. I hope this information will prove helpful.”
Inspector Craig listened to this report with interest. Later that evening, sitting quietly in his room at the Bird Forest Inn, Craig reviewed the report and realized that McSnurd wasn’t a very good observer, because the two facts he reported were logically incompatible.
• 1 •
Why is McSnurd’s report inconsistent?
Solution: It is best that we give the solution immediately. Suppose McSnurd’s report were true. We consider the bird a satisfying the condition that for every bird x, ax sings on just those days on which xx sings. Then according to McSnurd’s second statement, there is a bird a’ such that for every bird x, a’x sings on just those days when ax doesn’t sing. But the days when ax doesn’t sing are just those days on which xx doesn’t sing (because ax sings on the very same days as xx), and so we have a bird a’ such that for every bird x, a’x sings on just those days when xx doesn’t sing. Since this holds for every bird x, it holds when x is the bird a’, and so a’a’ sings on those and only those days on which a’a’ doesn’t sing, which is obviously a contradiction.
This paradox is a genuine one and is like the paradox of the barber who shaves those and only those people who don’t shave themselves, or like Russell’s famous paradox of the set that contains as members those and only those sets that do not contain themselves as members. Such a set would contain itself as a member if and only if it doesn’t.
2 • A Follow-up
Inspector Craig was distinctly dissatisfied with Professor McSnurd, and so he asked one of the more learned inhabitants whether there were any other bird sociologists residing in Russell’s Forest.
“This I do not know,” was the reply, “but I do know that there is a meta-bird-sociologist in this forest; his name is Professor MacSnuff.”
“Just what is a meta-bird-sociologist?” asked Craig in amazement.
“A meta-bird-sociologist is one who studies the sociology of bird sociologists. Professor MacSnuff is the leading authority, not on bird sociology, about which he knows nothing, but on bird sociologists. He is familiar with all the bird sociologists in the world, hence he should know which ones reside here. I suggest you contact him.”
Craig expressed his thanks and then arranged an interview with MacSnuff.
“Yes, there is another bird sociologist here,” said MacSnuff. “His name is also McSnurd. He is a brother of the McSnurd you have already interviewed.”
Craig was delighted, and arranged an interview with this other McSnurd.
“Ah, yes,” said McSnurd. “My brother is not always accurate; he should not have told you what he did. What he should have said is that there is a bird here such that for any bird x, the bird x sings on those and only those days on which x does not sing. Also, this forest contains a sage bird, if that will help.”
Inspector Craig thanked him and left. “Oh drat!” said Craig to himself a moment later. “This McSnurd is as bad as his brother!”
How did Craig know this?
3 • A Second Follow-up
“Isn’t there any competent bird sociologist in this forest?” Craig asked MacSnuff on his second visit.
“There is only one more bird sociologist here,” said MacSnuff. “His name is also McSnurd and he is the brother of the other two McSnurds.”
None too hopefully, Craig arranged an appointment with the remaining McSnurd.
“Ah, yes,” said the third McSnurd. “Neither of my brothers is very good at either observing or reasoning. The last McSnurd you saw was right about the sage bird; I have seen one here myself. But he was wrong about the bird ; what he should have told you is that there is a bird A here such that for any birds x and y, the bird Axy sings on those and only those days on which neither x nor y sings. Now you shouldn’t get into any trouble.”
Does the third McSnurd’s story hold water?
SOLUTIONS
2 · Suppose McSnurd’s report were correct. Then for every bird x, Nx ≠ x—that is, Nx i
s unequal to x—because Nx sings on just those days on which x doesn’t. But since a sage bird is present, then every bird is fond of some bird, hence N is fond of some bird x, which means that Nx = x. This is a contradiction.
3 · The contradiction involved in this report is a bit more subtle and more interesting! Let us suppose the report is true. Take any bird x. Since there is a sage bird, then Ax, like every other bird, is fond of some bird y, so Axy = y. Thus y sings on those and only those days on which neither x nor y sings. If y ever sang on a given day, then neither x nor y would sing on that day, which means that y wouldn’t sing on that day and we would have a contradiction. Therefore y never sings at all. Now, suppose there were some day on which x doesn’t sing. Then neither x nor y sings on that day, hence Axy does sing on that day, and y sings on that day, contrary to the already proved fact that y never sings. Therefore x must sing on all days. And so we have proved that every bird x sings on all days, yet we have shown that for every bird x there is some bird y that never sings. This is obviously a contradiction.
16
The Forest Without a Name
Unable to find any reliable bird sociologist in Russell’s Forest, Craig left it in disgust. Over the next several days he wended his weary way to the forest of this story.
For the first few days of his sojourn here, he was unaccountably sad. He could not analyze just why he was sad, but the fact remained that he was sad. “Could it be the disappointing results of my visit to the last forest?” thought Craig. “No,” he concluded, “something else is also wrong, but I can’t put my finger on just what the something is!”
Craig brightened somewhat when he heard that the bird sociologist of this forest was the eminent Professor McSnurtle. Though a cousin of the McSnurd brothers, McSnurtle was known to be thoroughly reliable. Craig had read about him back home in the Encyclopedia of Bird Sociology, and the one thing that was emphasized was that McSnurtle never made mistakes! Craig was granted an interview.
“We have a special bird e,” said McSnurtle. “After years of research, I have established the following four laws concerning e.
Law 1: For any birds x and y, if exy sings on a given day, so does y.
Law 2: For any birds x and y, the bird x and the bird exy never sing on the same day.
Law 3: For any birds x and y, the bird exy sings on all days on which x doesn’t sing and y does sing.
Law 4: For any bird x there is a bird y such that y sings on the same days as eyx.
“That,” said McSnurtle proudly, “neatly sums up all I know about the singing habits of the birds of this forest.”
Inspector Craig pondered this analysis well. At one point he could not completely suppress a slightly disdainful expression.
“What’s wrong?” asked McSnurtle, who was quite a sensitive individual. “Have you found an inconsistency in my statements?”
“Oh, no,” replied Craig. “I thoroughly trust your reputation for complete accuracy. Only there is one question I would like to ask you: Have you ever heard any birds in this forest sing at all?”
Professor McSnurtle wracked his brain for several minutes. “Come to think of it, I don’t believe I ever have!” he finally replied.
“And I’m afraid you never will,” said Craig, rising. “You could have stated your laws more succinctly still by combining them into the one simple law: None of the birds of this forest ever sing. I see now why I’ve felt so sad here!”
How did Craig realize this?
SOLUTION
This is essentially Problem 1 of Curry’s Forest again. Let us say that a bird is silent on a given day if it doesn’t sing on that day. Then McSnurtle’s four laws can be equivalently stated as follows:
Law 1: If y is silent on a given day, then exy is silent on that day.
Law 2: If x is not silent on a given day, then exy is silent on that day.
Law 3: If the bird x and the bird exy are both silent on a given day, then y is silent on that day.
Law 4: For any bird x there is a bird y such that y is silent on those and only those days on which eyx is silent.
And so Byrd’s four laws for P hold for e if we simply replace “sings” by “is silent.” Then the same argument showing that all the birds of Curry’s Forest sing on all days shows that all the birds of this forest are silent on all days.
Epilogue: Many years later, the Forest Without a Name (which actually did have a name of a paradoxical sort) came to be known as the Forest of Silence.
17
Gödel’s Forest
Craig’s next adventure was far more delightful and also highly informative. After leaving the Forest Without a Name, he found himself in the lovely forest of this chapter. The first thing he noticed was the abundance of birds in song. They sang so beautifully—just like nightingales! The bird sociologist of this forest was a certain Professor Giuseppe Baritoni, who himself had been an excellent singer in his day.
“Now in this forest,” explained Baritoni, “we do not regard it of much importance which birds sing on which days; the important question is which birds can sing at all! Not all birds of this forest can sing. We have plenty of nightingales, and they all sing, as you may have gathered.”
“Oh, yes,” said Craig. “As a matter of fact, all the birds I have heard so far have sounded to me like nightingales. Are nightingales the only birds here who sing, or are there others?”
“Ah, a most interesting question!” replied Baritoni. “Unfortunately we have not found the answer. The only birds I have heard sing here are nightingales, and I don’t know anyone who has heard a singing bird that is not a nightingale. Still, that’s not conclusive evidence that nightingales are the only singing birds of this forest; it may be that there is some bird not yet discovered that sings but is not a nightingale. It would be most interesting if there were!
“As a matter of fact, a logician from the Institute for Advanced Study in Princeton once visited this forest many years ago, and when I told him some of the singing laws of this forest, he conjectured that it should be decidable on the basis of these laws whether or not there was such a bird. Unfortunately, he left one day quite suddenly, and I forgot his name. I have never heard from him since.”
“What are these laws?” asked Craig with enormous interest.
“Well,” explained Baritoni, “the first interesting thing about this forest is that all the birds are married. For any bird x, by x’ I mean the mate of x. The interesting thing is that for any birds x and y, the bird x’y sings if and only if xy does not sing.
“The second interesting thing is that every bird x has a distinguished relative x* called the associate of x. The bird x* is such that for every bird y, the bird x*y sings if and only if x(yy) sings.
“The third thing is that there is a special bird such that whenever you call the name of a nightingale to , responds by naming a bird that sings, but if you call to any bird that is not a nightingale, then responds by naming a bird that doesn’t sing. In other words, for any bird x, the bird x sings if and only if x is a nightingale.”
“Very interesting,” said Craig, who then took out his notebook and wrote down the following four conditions so he would not forget them.
Condition 1: All nightingales (of this forest) sing.
Condition 2: x’y sings if and only if xy doesn’t sing.
Condition 3: x*y sings if and only if x(yy) sings.
Condition 4: x sings if and only if x is a nightingale.
Inspector Craig thanked Professor Baritoni warmly, took his leave, and spent the day ambling through this lovely forest. He retired early that evening and, curiously enough, solved the problem in his sleep close to morning. “Eureka!” he exclaimed, jumping out of bed. “I must see Baritoni immediately!” And so he dressed hurriedly, snatched a quick breakfast, and walked briskly in the direction of Baritoni’s ornithological laboratory—an unusual thing for a well-bred British gentleman to do without an invitation, but Craig can surely be excused, considering his state of e
uphoria. He turned a sharp bend and almost walked headlong into Baritoni, who was out for his morning constitutional, humming a tune from Aïda.
“I have solved your problem!” exclaimed Craig exuberantly. “There is a bird in this forest that sings but is not a nightingale.
“Wonderful!” cried Baritoni, clapping his hands in joy. “But tell me, is there any way we can actually find such a bird?”
“That depends,” said Craig. “To begin with, if you know how to find a bird x and how to find a bird y, do you know how to find the bird xy?”
“Not necessarily,” replied Baritoni. “However, if I know how to locate x and I know the name of y, then I can find the bird xy: I simply go over to x and call out the name of y. Then x names the bird xy. Once I know the name of xy, I can find it, because I can find any bird whose name I know. It might take several hours, but it can be done.”
“Good enough!” said Craig. “Next, if you know the name of a bird x, can you find out the name of its spouse x’?”
“Oh, yes; I have a complete list of all the birds I know, telling me which is mated to which.”
“Also,” asked Craig, “if you know the name of a bird x, are you able to find the name of its associate x*?”
“Oh, yes; I have another such list.”
To Mock a Mocking Bird Page 13
