Smullyan - To Mock a Mocking Bird

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 H ASKELL C URRY
an early pioneer in combinatory logic
and an avid bird-watcher

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

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 bookcalled 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 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 didnt 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 ones combinators anything one likes (for example, computer programs). Well, I have chosen birds for my combinatorsmotivated, 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 Prizeand Other Puzzles

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, doesnt it? The second student said: Of course not!

Which student was right, and why?

There is a question I could ask you that has a definite correct answereither yes or nobut 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?

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 numberthe 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 didnt change my theory; its 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.

Suppose I offer to give you one of three prizesPrize 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 Cthe 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 Awhat statement could you make which would force me to give you Prize A?