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.
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.
The Gödelian Puzzle Book: Puzzles, Paradoxes and Proofs
240
The Gödelian Puzzle Book: Puzzles, Paradoxes and Proofs
240eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
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.
Product Details
| ISBN-13: | 9780486315775 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 08/21/2013 |
| Series: | Dover Math Games & Puzzles |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 240 |
| File size: | 2 MB |
About the Author
Raymond Smullyan (1919–2017), mathematician, logician, magician, creator of extraordinary puzzles, philosopher, pianist, and man of many parts. The first Dover book by Raymond Smullyan was First-Order Logic (1995). Recent years have brought a number of his magical books of logic and math puzzles: The Lady or the Tiger (2009); Satan, Cantor and Infinity (2009); an original, never-before-published collection, King Arthur in Search of His Dog and Other Curious Puzzles (2010); and Set Theory and the Continuum Problem (with Melvin Fitting, also reprinted by Dover in 2010). More will be coming in subsequent years.
In the Author's Own Words:
"Recently, someone asked me if I believed in astrology. He seemed somewhat puzzled when I explained that the reason I don't is that I'm a Gemini."
"Some people are always critical of vague statements. I tend rather to be critical of precise statements: they are the only ones which can correctly be labeled 'wrong.'" — Raymond Smullyan
Read an Excerpt
The Gödeliäm Puzzle Book
Puzzles, Paradoxes and Proofs
By Raymond M. Smullyan
Dover Publications, Inc.
Copyright © 2013 Raymond M. SmullyanAll rights reserved.
ISBN: 978-0-486-31577-5
CHAPTER 1
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 was empty. The purpose now was to determine from the messages which envelope contained the bill. Here are the messages:
1. Of the two sentences, at least one is false.
2. The bill is in this envelope.
I then explained that if the one taking this test could correctly prove where the bill was, he or she could keep it, but for the privilege of taking this test, I would charge 25¢. After some thoughts, one man volunteered. I then asked him where the bill was, and to prove that he was right. He said, "If Sentence 1 were false, it would be true that at least one was false, and you would have a contradiction. Therefore Sentence 1 must be true, hence at least one of the sentences is false, as Sentence 1 correctly says. Therefore Sentence 2 is false, and so the bill is really in Envelope 1." I said, "Very well, open Envelope 1." He did so, and it was empty! He then opened Envelope 2, and there was the bill!
At this point, he, and other members of the audience looked puzzled. I then asked, "How come the bill was in Envelope 2 instead of Envelope 1?" One member of the audience yelled, "Because you obviously were lying!" I assured the audience that at no time did I lie, and indeed I never did! So given the fact that I did not he, what is the explanation?
Problem 1. What is the explanation of why the bill was in Envelope 2, despite the volunteer's purported proof that the bill was in Envelope 1? What was wrong with the proof he gave? [Answers to problems are given at the end of chapters. Realize, though, that sometimes there are more ways than one to arrive at the solution to a given problem.]
At this point, the volunteer owed me 25¢. I then told the audience that I felt a little bit guilty about having won a quarter by such a trick. And so I said to the volunteer, "I want to give you a chance to win your money back, so I'll play you for double or nothing." [This got a general laugh.] "In fact," I continued, "I'll be even more generous!" I then handed him two $10 bills and told him that he could have his quarter back and even keep some of the money I just gave him, but he would have to agree to something first. I told him I was about to make a statement. If he wanted the deal I was proposing, he had to promise to give me back one of the bills if the statement was false. But if the statement turned out to be true, then he must keep both bills. "That's a pretty good deal, isn't it?" I asked. "You are bound to get at least $10, and possibly $20!" He agreed. I then made a statement such that in order for him to keep to the agreement, the only way was to pay me $1000!
Problem 2. What statement would accomplish this?
At this point the poor fellow owed me a thousand dollars. Later I will tell you how I gave him a chance (sic!) to regain his thousand dollars, but first I wish to tell you of a related incident (which I also told the audience): Many years ago, when I was a graduate student at Princeton, I would frequently visit New York City. On one of my visits I met a very charming lady musician. On my first date with her, I asked her to do me a favor. I told her that I would make a statement in a moment, and I asked her whether she would give me her autograph if the statement turned out to be true. She replied, "I don't see why not." And I said that if the statement was false, she should not give me her autograph. She agreed. I then made a statement such that in order for her to keep her word, she had to give me, not her autograph, but a kiss!
Problem 3. What statement would work?
Now, the statement I gave in the solution to the last problem had to be false, and she had to give me a kiss. However, there is another statement I could have made which would have had to be true, after which she would also have had to give me a kiss.
Problem 4. What statement could that be?
There is still another statement I could have made (a more interesting one, I believe) which could be either true or false, but in either case, she would have to give me a kiss. [There is no way of knowing whether the statement is true or false before the lady acts.]
Problem 5. What statement would accomplish this?
Anyway, whatever statement I would have made, it was a pretty sneaky way of winning a kiss, wasn't it? Well, what happened next was even more interesting. Instead of collecting the kiss, I suggested we play for double or nothing. She, being a good sport, agreed. And so she soon owed me two kisses, then with another logic trick four, then eight, then sixteen, then thirty-two, and things kept doubling and escalating and doubling and escalating and before I knew it, we were married! And I was married to Blanche, the charming lady musician, for over 48 years.
Once at breakfast I had the following conversation with Blanche:
Ray Is NO the correct answer to this question?
Blanche To what question?
Ray To the question I just asked. Is NO the correct answer to that question?
Blanche No, of course not!
Ray Aha, you answered NO, didn't you!
Blanche Yes.
Ray And did you answer correctly?
Blanche Why, yes!
Ray Then NO is the correct answer to the question.
Blanche That's right.
Ray Then when I asked you what the correct answer is, you should have answered YES, not NO!
Blanche Oh yes, that's right! I should have answered YES.
Ray No, you shouldn't! If you answered YES, you would be affirming that NO is the correct answer so why would you give the incorrect answer YES?
Blanche You're confusing me!
Fortunately, Blanche did not divorce me for this!
It's sometimes annoying for a wife to have an overly rational husband, isn't it? The following dialogue from my book "This Book Needs No Title" well illustrates this:
Wife Do you love me?
Husband Well of course! What a ridiculous question!
Wife You don't, love me!
Husband Now what kind of nonsense is this?
Wife Because if you really loved me, you couldn't have done what you did!
Husband I have already explained it to you that the reason I did what I did was not, that I don't love you, but because of such and such.
Wife But this such and such is only a rationalization! You really did it because of so and so, and this so and so would never be if you really loved me.
Etc., etc.!
Next Day
Wife Darling, do you love me?
Husband I'm not so sure!
Wife What!
Husband I thought I did, but the argument you gave me yesterday proving that I don't is not too bad!
I already told you how on my first date with Blanche, I won a kiss using logic. Here is another way of winning a kiss: I say to a lady, "I'll bet you that I can kiss you without touching you." After giving a precise definition of kissing and of touching, she realizes that it is logically impossible, and takes the bet. I then tell her to close her eyes. She does so, I then give her a kiss and say, "I lose!"
This is reminiscent of the prank in which you go into a bar with a friend who orders a martini. You place a tumbler on the martini and say, "I'll bet you a quarter that I can drink the martini without removing the tumbler." He accepts the bet. You then remove the tumbler, drink the martini and give him a quarter!
This is reminiscent of the story of a programmer and an engineer sitting next to each other on an airplane. The following conversation ensued:
Programmer Would you like to play a game?
Engineer No, I want to sleep.
Programmer It's a very interesting game!
Engineer No, I want to sleep.
Programmer I ask you a question. If you don't know the answer, you pay me five dollars. Then you ask me a question and if I don't know the answer, then I pay you five dollars.
Engineer No, no, I want to sleep.
Programmer I'll tell you what! If you don't know the answer to my question, you pay me five dollars, but if I don't know the answer to your question, I'll pay you fifty dollars!
Engineer O.K. Here's a question. What goes up the hill with four legs and comes down with five legs?
The programmer then took out his portable computer and worked on the question for an hour, but got nowhere. And so he handed the engineer fifty dollars. The engineer said nothing, but put the fifty dollars in his pocket. The programmer, a bit miffed, said, "Well, what's the answer?" The engineer then handed him five dollars.
Coming back now to my lecture and the guy who owed me a thousand dollars, I said to him , "I really feel sorry for you, and so I will give you back your thousand dollars on condition that you answer a yes/no question truthfully for me." He agreed. I then asked him a question such that the only way he could keep his word was by paying me, not a thousand dollars, but a million dollars!
Problem 6. What question would work?
At this point, I said to him , "I am now in a very generous mood, and so I'll tell you what I'm going to do! I'll give you back your million dollars on condition that you give me the answer to another yes/no question, but this time you don't have to answer truthfully! Your answer can be either true or false; you have the option! There is obviously no way I can trick you now, right?" He agreed that it was obviously impossible for me to con him under the given conditions, and so he accepted. Ah, but there was a way I could con him! The next question I asked was such that he had to pay me, not a million dollars, but a billion dollars!
(Continues...)
Excerpted from The Gödeliäm Puzzle Book by Raymond M. Smullyan. Copyright © 2013 Raymond M. Smullyan. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Contents
Part I—Puzzles, Paradoxes, Infinity and other Curiosities,Chapter I A Chatty Personal Introduction,
Chapter II Some Curious Adventures,
Chapter III The Strange Island of Musica,
Chapter IV Four Metapuzzles,
Chapter V Certified Knights and Knaves,
Chapter VI Paradoxical?,
Chapter VII Infinity and Induction,
Chapter VIII Introducing Self-Reference,
Chapter IX Fixed Point Puzzles,
Chapter X Some Curious Systems,
Chapter XI How to Stump a Decision Machine,
Chapter XII Some Additional Gödelian Puzzles,
Part II—Provability, Truth and the Undecidable,
Chapter XIII Truth and Provability,
Chapter XIV Syntactic Incompleteness Theorems,
Chapter XV Provability in Stages,
Chapter XVI Formal Systems and Recursion,
Chapter XVII Incompleteness and Undecidability,
Chapter XVIII First-Order Arithmetic,
Chapter XIX Arithmetic Truth Is Not Formalizable,
Chapter XX The Incompleteness of Peano Arithmetic,
References,