ALSO BY RAYMOND SMULLYAN
Theory of Formal Systems
First Order Logic
The Tao Is Silent
What Is the Name of This Book?
This Book Needs No Title
The Chess Mysteries of Sherlock Holmes
The Chess Mysteries of the Arabian Knights
The Lady or the Tiger?
Alice in Puzzle-Land
5000 B.C.
THIS IS A BORZOI BOOK
PUBLISHED BY ALFRED A. KNOPF, INC.
Copyright © 1985 by Raymond Smullyan
All rights reserved under International and Pan-American
Copyright Conventions. Published in the United States by Alfred
A. Knopf, Inc., New York, and simultaneously in Canada by
Random House of Canada Limited, Toronto. Distributed by
Random House, Inc., New York.
Library of Congress Cataloging in Publication Data
Smullyan, Raymond M. To mock a mockingbird.
1. Philosophical recreations. 2. Puzzles. 3. Logic.
1. Title.
GV1507.P43S68 1985 793.73 84-48737
eISBN: 978-0-307-81979-6
v3.1
To the memory of HASKELL CURRY—
an early pioneer in combinatory logic
and an avid bird-watcher
Contents
Cover
Other Books by This Author
Title Page
Copyright
Dedication
Acknowledgments
Preface
PART I · LOGIC PUZZLES 1 The Prize—and Other Puzzles
2 The Absentminded Logician
3 The Barber of Seville
4 The Mystery of the Photograph
PART II · KNIGHTS, KNAVES, AND THE FOUNTAIN OF YOUTH 5 Some Unusual Knights and Knaves
6 Day-Knights and Night-Knights
7 Gods, Demons, and Mortals
8 In Search of the Fountain of Youth
PART III · TO MOCK A MOCKINGBIRD 9 To Mock a Mockingbird
10 Is There a Sage Bird?
11 Birds Galore
12 Mockingbirds, Warblers, and Starlings
13 A Gallery of Sage Birds
PART IV · SINGING BIRDS 14 Curry’s Lively Bird Forest
15 Russell’s Forest
16 The Forest Without a Name
17 Gödel’s Forest
PART V · THE MASTER FOREST 18 The Master Forest
19 Aristocratic Birds
20 Craig’s Discovery
PART VI · THE GRAND QUESTION! 21 The Fixed Point Principle
22 A Glimpse into Infinity
23 Logical Birds
24 Birds That Can Do Arithmetic
25 Is There an Ideal Bird?
Epilogue
Who’s Who Among the Birds
Acknowledgments
I wish to express my thanks to Nancy Spencer for expert typing and secretarial assistance, and to the Philosophy Department of Indiana University for providing me with ideal working conditions. My thanks go to Professor George Boolos at M.I.T. for reading this entire manuscript and for making many useful suggestions. Melvin Rosenthal, the production editor, has done a very conscientious job. My editor, Ann Close, has been wonderful, as usual, and enormously helpful with this whole project.
Raymond Smullyan
Elka Park, New York
November 1984
Preface
Before I tell you what this book is about, I would like to relate a true and delightful incident.
Shortly after the publication of my first puzzle book—called What Is the Name of This Book?—I received a letter from an unknown female suggesting an alternative solution to one of the puzzles, which I found more elegant than the one I had given. She closed the letter with “Love” and signed her name. I had absolutely no idea who she was, or whether she was married or single. I wrote back expressing my appreciation of her solution and asked whether I might use it in a subsequent edition. I also suggested that if she had not already graduated from college she might consider majoring in mathematics, since she showed definite mathematical talent. Shortly after, she replied: “Thank you for your gracious letter. You have my permission to use my solution. I am nine and a half years old and am in fifth grade.”
She was particularly fond of puzzles about knights and knaves (truth-tellers and liars). Indeed, these puzzles have proved extremely popular with young and old alike, and I have accordingly devoted the first eight chapters of this book to new puzzles of this type. They range from extremely elementary to the very subtle metapuzzle in Chapter 8 on the Fountain of Youth. (Anyone solving that puzzle deserves to be knighted!) The rest of the book strikes out in a totally different direction, and goes into much deeper logical waters than any of my earlier puzzle books. You will learn some fascinating things about combinatory logic. This remarkable subject is currently playing an important role in computer science and artificial intelligence, and so this book is quite timely. (I didn’t plan it that way; I just happened to be lucky!) Despite the profundity of the subject, it is no more difficult to learn than high school algebra or geometry. Since computer science has now found its way into the high school curriculum, could it be possible that combinatory logic will soon follow suit?
Combinatory logic is an abstract science dealing with objects called combinators. What their objects are need not be specified; the important thing is how they act upon each other. One is free to choose for one’s “combinators” anything one likes (for example, computer programs). Well, I have chosen birds for my combinators—motivated, no doubt, by the memory of the late Professor Haskell Curry, who was both a great combinatory logician and an avid bird-watcher. The main reason I chose combinatory logic for the central theme of this book was not for its practical applications, of which there are many, but for its great entertainment value. Here is a field considered highly technical, yet perfectly available to the general public; it is chock-full of material from which one can cull excellent recreational puzzles, and at the same time it ties up with fundamental issues in modern logic. What could be better for a puzzle book?
PART ONE
LOGIC
PUZZLES
1
The Prize—and Other Puzzles
THREE LITTLE PUZZLES
1 • The Flower Garden
In a certain flower garden, each flower was either red, yellow, or blue, and all three colors were represented. A statistician once visited the garden and made the observation that whatever three flowers you picked, at least one of them was bound to be red. A second statistician visited the garden and made the observation that whatever three flowers you picked, at least one was bound to be yellow.
Two logic students heard about this and got into an argument. The first student said: “It therefore follows that whatever three flowers you pick, at least one is bound to be blue, doesn’t it?” The second student said: “Of course not!”
Which student was right, and why?
2 • What Question?
There is a question I could ask you that has a definite correct answer—either yes or no—but it is logically impossible for you to give the correct answer. You might know what the correct answer is, but you cannot give it. Anybody other than you might possibly be able to give the correct answer, but you cannot!
Can you figure out what question I could have in mind?
3 • Which Way Would You Bet?
Here is an old chestnut concerning probability: Choose your favorite baseball team and consider the scores it will make next season. Which do you bet will be the larger number—the sum of these scores or the product of these scores?
Speaking of probability and statistics, there is
the story of a statistician who told a friend that he never took airplanes: “I have computed the probability that there will be a bomb on the plane,” he explained, “and although this probability is low, it is still too high for my comfort.” Two weeks later, the friend met the statistician on a plane. “How come you changed your theory?” he asked. “Oh, I didn’t change my theory; it’s just that I subsequently computed the probability that there would simultaneously be two bombs on a plane. This probability is low enough for my comfort. So now I simply carry my own bomb.”
HOW DO YOU WIN YOUR PRIZE?
4 • The Three Prizes
Suppose I offer to give you one of three prizes—Prize A, Prize B, or Prize C. Prize A is the best of the three, Prize B is middling, and Prize C is the booby prize. You are to make a statement; if the statement is true, then I promise to award you either Prize A or Prize B, but if your statement is false, then you get Prize C—the booby prize.
Of course it is easy for you to be sure to win either Prize A or Prize B; all you need say is: “Two plus two is four.” But suppose you have your heart set on Prize A—what statement could you make which would force me to give you Prize A?
5 • A Fourth Prize Is Added
I now add a fourth prize—Prize D. This prize is also a booby prize. The conditions now are that if you make a true statement, I promise to give you either Prize A or Prize B, but if you make a false statement, you get one of the two booby prizes—Prize C or Prize D.
Suppose you happen to know in advance what the four prizes are, and for some reason or other, you like Prize C better than any of the other prizes.
Incidentally, this situation is not necessarily unrealistic. I recall that as a child I was at a birthday party where I won a prize, but became very envious of the kid who won the booby prize, because I liked his prize much more than mine! In fact, the booby prize seemed to be a general favorite, since we all spent most of the day playing with it.
Getting back to the present puzzle, what statement could you make that would force me to give you Prize C?
6 • You Wish to Confound Me!
Again, we have the four prizes of the last problem and the same conditions. Now, suppose you don’t give a hoot for any of the prizes; you merely wish to confound me by making a statement that will force me to break my promise.
What statement would do this?
Note: This problem is essentially the same as the one known as the Sancho Panza paradox, a discussion of which is included in the solution.
SOLUTIONS
1 · The first student was right, and here is why. From the first statistician’s report it follows that there cannot be more than one yellow flower, because if there were two yellows, you could pick two yellows and one blue, thus having a group of three flowers that contained no red. This is contrary to the report that every group of three is bound to contain at least one red flower. Therefore there cannot be more than one yellow flower. Similarly, there cannot be more than one blue flower, because if there were two blues, you could pick two blue flowers and one yellow and again have a group of three that contained no red. And so from the first statistician’s report it follows that there is at most one yellow flower and one blue. And it follows from the report of the second statistician that there is at most one red flower, for if there were two reds, you could pick two reds and one blue, thus obtaining a group of three that contained no yellow. It also follows from the second report that there cannot be more than one blue, although we have already deduced this from the first report.
The upshot of all this is that there are only three flowers in the entire garden—one red, one yellow, and one blue! And so it is of course true that whatever three flowers you pick, one of them must be blue.
2 · Suppose I ask you: “Is no your answer to this question?” If you answer yes, then you are affirming that no is your answer to the question, which is of course wrong. If you answer no, then you are denying that no is your answer, although no was your answer. It is therefore impossible for you to answer the question correctly even though the question does have a correct answer: Either you answer no or you don’t. If you do, then yes is the correct answer; if you don’t, then no is the correct answer, but in neither case can you give the correct answer.
3 · The chances are that the sum will be the larger number, because your team will probably score at least one zero, and one zero makes the entire product zero.
4 · If you want to win Prize A, what you should say is: “I will not get Prize B.” What can I do? If I give you Prize C, then your statement has turned out to be true—you didn’t get Prize B—so I have given you the booby prize for making a true statement, which I cannot do. If I give you Prize B, then your statement has turned out to be false, but I can’t give you Prize B for having made a false statement. Therefore I am forced to give you Prize A. You have then made a true statement—you didn’t get Prize B—and have accordingly been awarded one of the two prizes offered for making a true statement.
Of course the statement “I will get either Prize A or Prize C” also works.
5 · To win Prize C, you need merely say: “I will get Prize D.” I leave the proof to the reader.
6 · To force me to break my promise, you need merely say: “I will get one of the booby prizes.” What can I do? If I give you a booby prize your statement has turned out to be true and I have broken my promise by giving you a booby prize. If I give you either Prize A or Prize B, then I have again violated the conditions of my promise, because you have made a false statement, and I should have given you a booby prize instead.
My promise was really a dangerous one, since I could have no way of knowing in advance whether or not I would be able to keep it. Whether or not I can keep it actually depends on what you do, as you have just seen. The situation is similar to the famous Sancho Panza paradox that Cervantes described in one episode of Don Quixote. In a certain town, the inhabitants had a decree that whenever a stranger crossed the bridge and entered the town, he was required to make a statement. If the statement was false, then the decree ordered that the stranger be hanged. If the statement was true, then he was to pass freely. What statement could the stranger make that would make it impossible for the decree to be carried out? The answer is for the stranger to say: “I will be hanged.” It is then impossible for the inhabitants to carry out the decree.
2
The Absentminded Logician
ONLY THREE WORDS?
The puzzles of this chapter constitute as good an introduction to the logic of lying and truth-telling as I know. I will start with an old puzzle of mine and take off from there.
1 • John, James, and William
We are given three brothers named John, James, and William. John and James (the two J’s) always lie, but William always tells the truth. The three are indistinguishable in appearance. You meet one of the three brothers on the street one day and wish to find out whether he is John (because John owes you money). You are allowed to ask him one question answerable by yes or no, but the question may not contain more than three words! What question would you ask?
2 • A Variant
Suppose we change the above conditions by making John and James both truthful and William a liar. Again you meet one of the three and wish to find out if he is John. Is there now a three-word yes/no question that can accomplish this?
3 • A More Subtle Puzzle
We now have only two brothers (identical twins). One of them is named Arthur and the other has a different name. One of the two always lies and the other always tells the truth, but we are not told whether Arthur is the liar or the truth-teller. One day you meet the two brothers together, and you wish to find out which one is Arthur. Note that you are not interested in finding out which one lies and which one tells the truth, but only in finding out which one is Arthur. You are allowed to ask just one of them a question answerable by yes or no, and again the question may not contain more than three words. What question would you ask?
�
�� 4 •
Suppose that instead of wanting to find out which one is Arthur, you want to find out whether Arthur is the liar or the truth-teller. Again there is a three-word question that will do this. What three-word question will work? There is a pretty symmetry between the solutions of this and the last problem!
• 5 •
This time, all you are interested in finding out is which of the two brothers you meet is the liar and which is the truth-teller. You don’t care which one is Arthur, or whether Arthur is the liar or the truth-teller. What three-word question will accomplish this?
• 6 •
Next you are told to ask one of the brothers just one three-word question. If he answers yes, you will get a prize; if he answers no, then you get no prize. What question would you ask?
THE NELSON GOODMAN PRINCIPLE
If it were not for the restriction that the question contain no more than three words, all six of the above problems could be solved by a uniform method! This method is embodied in a famous puzzle invented about forty years ago by the philosopher Nelson Goodman. For those not familiar with the puzzle, here it is.
Given an individual who either always lies or always tells the truth, and given any proposition whose truth or falsity you wish to determine and whose truth or falsity is known by the individual, there is a way of determining this by asking just one yes/no question. For example, suppose the individual is standing at the fork of a road; one road leads to the town of Pleasantville, which you wish to visit, and the other road doesn’t. The individual knows which road leads to Pleasantville, but he either always lies or always tells the truth. What question would you ask him to find out which is the correct road to Pleasantville?
To Mock a Mocking Bird Page 1
