The Gödelian Puzzle Book

Puzzles, Paradoxes and Proofs

Raymond M. Smullyan

• Publisher: Dover Publications
• Year: 2013
• ISBN:
  9780486315775
• Topic: Mathematik
• Subtopic: Spiele in der Mathematik

These brand-new recreational logic puzzles provide entertaining variations on Gödel's incompleteness theorems, offering ingenious challenges related to infinity, truth and provability, undecidability, and other concepts. Created by the celebrated logician Raymond Smullyan, the puzzles require no background in formal logic and will delight readers of all ages.
The two-part selection of puzzles and paradoxes begins with examinations of the nature of infinity and some curious systems related to Gödel's theorem. The first three chapters of Part II contain generalized Gödel theorems. Symbolic logic is deferred until the last three chapters, which give explanations and examples of first-order arithmetic, Peano arithmetic, and a complete proof of Gödel's celebrated result involving statements that cannot be proved or disproved. The book also includes a lively look at decision theory, better known as recursion theory, which plays a vital role in computer science.

PART I

PUZZLES, PARADOXES, INFINITY AND OTHER CURIOSITIES

CHAPTER I

A CHATTY PERSONAL INTRODUCTION

Let me introduce myself by what might be termed a meta-introduction, by which I mean that I will tell you of three amusing introductions I have had in the past.

1. The first was by the logician Professor Melvin Fitting, formerly my student, whom I will say more about later on. I must first tell you of the background of this introduction. In my puzzle book “What is the Name of this Book?” I gave a proof that either Tweedledee or Tweedledum exists, but there is no way to tell which. Elsewhere I constructed a mathematical system in which there are two sentences such that one of them must be true but not provable in the system, but there is no way to know which one it is. [Later in this book, I will show you this system.] All this led Melvin to once introduce me at a math lecture by saying, “I now introduce Professor Smullyan, who will prove to you that either he doesn’t exist, or you don’t exist, but you won’t know which!”

2. On another occasion, the person introducing me said at one point, “Professor Smullyan is unique.” I was in a mischievous mood at the time, and I could not help interrupting him and saying, “I’m sorry to interrupt you Sir, but I happen to be the only one in the entire universe who is not unique!”

3. This last introduction (perhaps my favorite) was by the philosopher and logician Nuel Belnap Jr., and could be applicable to anybody. He said, “I promised myself three things in this introduction: First, to be brief, second, not to be facetious, and third, not to refer to this introduction.”

I particularly liked the last introduction because it involved self-reference, which is a major theme of this book.

I told you that I would tell you more about Melvin Fitting. He really has a great sense of humor. Once when he was visiting at my house, someone complained of the cold. Melvin then said, “Oh yes, as it says in the Bible, many are cold but few are frozen.” Next morning I was driving Melvin through town, and at one point he asked me, “Why are all these signs advertising slow children?”

On another occasion, we were discussing the philosophy of solipsism (which is the belief “I am the only one who exists!”). Melvin said, “Of course I know that solipsism is the correct philosophy, but that’s only one man’s opinion.” This reminds me of a letter a lady wrote to Bertrand Russel, in which she said, “Why are you surprised that I am a solipsist? Isn’t everybody?”

I once attended a long and boring lecture on solipsism. At one point I rose and said, “At this point, I’ve become an anti-solipsist. I believe that everybody exists except me.”

Do you have any rational evidence that you are now awake? Isn’t it logically possible that you are now asleep and dreaming all this? Well, I once got into an argument with a philosopher about this. He tried to convince me that I had no rational evidence to justify believing that I was now awake. I insisted that I was perfectly justified in being certain that I was awake. We argued long and tenaciously, and I finally won the argument, and he conceded that I did have rational evidence that I was awake. At that point I woke up.

Coming back to Melvin Fitting, his daughter Miriam is really a chip off the old block. When she was only six years old, she and her father were having dinner at my house. At one point Melvin did not like the way Miriam was eating, and said, “That’s no way to eat, Miriam!” She replied, “I’m not eating Miriam!” [Pretty clever for a six-year old, don’t you think?]

One summer, Melvin, who was writing his doctoral thesis with me, was out of town. We corresponded a good deal, and I ended one of my letters saying, “And if you have any questions, don’t hesitate to call me collect and reverse the charges.” [Get it?]

I would like to tell you now of an amusing lecture I recently gave at a logic conference in which I was the keynote speaker. The title of my talk was “Coercive Logic and Other Matters.” I began by saying, “Before I begin speaking, there is something I would like to say.” This got a general laugh. I then explained that what I just said was not original, but was part of a manuscript of the late computer scientist Saul Gorn about sentences which somehow defeat themselves. He titled this collection “Saul Corn’s compendium of rarely used clichés.” It contains such choice items as:

1. Half the lies they tell about me are true.

2. These days, every Tom Dick and Harry is named “John.”

3. I am a firm believer in optimism, because without optimism, what is there?

4. I’m not leaving this party till I get home!

5. If Beethoven was alive today, he would turn over in his grave!

6. I’ll see to it that your project deserves to be funded.

7. This book fills a long needed gap.

8. A monist is one who believes that anything less than everything is nothing.

9. A formalist is one who cannot understand a theory unless it is meaningless.

10. The reason that I don’t believe in astrology is because I’m a Gemini.

The last one was mine. I used that line frequently in the days that I was a magician. In those days, people often asked me whether I had ever sawed a lady in half. I always replied that I have sawed dozens of ladies in half, and I’m learning the second half of the trick now.

Next, I told the logic group that I had prepared two different lectures for the evening, and I would like them to choose which of the two they would prefer. I then explained that one of the lectures was very impressive and the other was understandable. [This got a good laugh].

Next, I said that I would give a test to see if members of the audience could do simple propositional logic. I displayed two envelopes and explained that one of them contained a dime and the other one didn’t. On the faces of the envelopes were written the following sentences:

1. The sentences on the two envelopes are both false.

2. The dime is in the other envelope.

I explained that each sentence is, of course, either true or false, and that if anyone could deduce from these sentences where the dime was, he could have the dime. But for the privilege of taking this test, I would charge a nickel. Would anyone volunteer to give me a nickel for the privilege of doing this? I got a volunteer. I then told him, “You are not allowed to just guess where the dime is; you must give a valid proof before the envelope is opened.” He agreed. I said, “Very well. Where is the dime, and what is your proof?” He replied, “If the first sentence, the sentence on Envelope 1, were true, then what it says would be the case, which would mean that both sentences are false, hence the first sentence would be false, which is a clear contradiction. Therefore the first sentence can’t be true; it must be false. Thus it is false that both sentences are false, hence at least one must be true, and since it is not the first, it must be the second, and so the dime must be in the other envelope, as the sentence says.”

“That sounds like good reasoning,” I said. “Open Envelope 1.” He did so, and sure enough there was the dime.

After congratulating him, I said that the next test would be a little bit more difficult. Again I showed two envelopes with messages written on them, and I explained that one of them contained a dollar bill and the other w...