Forever Undecided Read online

  THIS IS A BORZOI BOOK

  PUBLISHED BY ALFRED A. KNOPF, INC.

  Copyright © 1987 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.

  Forever undecided, a puzzle guide to Gödel.

  1. Gödel’s theorem. 2. Mathematical recreations. I. Title.

  QA9.65.S68 1987 511.3 86–45297

  eISBN: 978-0-307-96246-1

  Once again, I would like to thank my editor, Ann Close, and the production editor, Melvin Rosenthal, for all their expert assistance, and my typist, Nancy Spencer, for her excellent secretarial help.

  v3.1

  Dedicated to All Consistent Reasoners

  Who Can Never Know That They Are Consistent

  Contents

  Cover

  Title Page

  Copyright

  Dedication

  Preface

  Part I

  YOU MIGHT BE SURPRISED!

  1 A Diabolical Puzzle

  2 Surprised?

  Part II

  THE LOGIC OF LYING AND TRUTH TELLING

  3 The Census Taker

  4 In Search of Oona

  5 An Interplanetary Tangle

  Part III

  KNIGHTS, KNAVES, AND PROPOSITIONAL LOGIC

  6 A Bit of Propositional Logic

  7 Knights, Knaves, and Propositional Logic

  8 Logical Closure and Consistency

  Part IV

  LET’S BE CAREFUL!

  9 Paradoxical?

  10 The Problem Deepens

  Part V

  THE CONSISTENCY PREDICAMENT

  11 Logicians Who Reason About Themselves

  12 The Consistency Predicament

  13 Gödelian Systems

  14 More Consistency Predicaments

  Part VI

  SELF-FULFILLING BELIEFS AND LÖB’S THEOREM

  15 Self-Fulfilling Beliefs

  16 The Rajah’s Diamond

  17 Löb’s Island

  Part VII

  IN DEEPER WATERS

  18 Reasoners of Type G

  19 Modesty, Reflexivity, and Stability

  Part VIII

  CAN’T DECIDE!

  20 Forever Undecided

  21 More Indecisions!

  Part IX

  POSSIBLE WORLDS

  22 It Ain’t Necessarily So!

  23 Possible Worlds

  24 From Necessity to Provability

  Part X

  THE HEART OF THE MATTER

  25 A Gödelized Universe

  26 Some Remarkable Logic Machines

  27 Modal Systems Self-Applied

  Part XI

  FINALE

  28 Modal Systems, Machines, and Reasoners

  29 Some Strange Reasoners!

  30 In Retrospect

  Other Books by This Author

  Preface

  IS IT possible for a rational human being to be in a position in which he cannot believe that he is consistent without losing his consistency in the process? That is one of the main themes of this book. It is modelled on the famous discovery of Kurt Gödel (the so-called Second Incompleteness Theorem) that any consistent mathematical system with enough power to do what is known as elementary arithmetic must suffer from the surprising limitation that it can never prove its own consistency!

  There are several reasons why I have transferred Gödel’s argument from the formal domain of mathematical systems and the propositions provable in them to the realm of human beings and the propositions believed by them. For one thing, human beings and their beliefs are far more familiar to the nonspecialist than abstract mathematical systems, and so I can thus explain the essentials of Gödel’s ideas in a language that everybody can understand. Also, putting these matters in human terms has an enormous psychological appeal and turns out to be highly relevant to the ever-growing field of artificial intelligence.

  As with my earlier puzzle books, I start off with a host of puzzles about liars and truth tellers (knaves and knights). Aside from the novelty of these problems (almost all of them are published here for the first time), there is an important added feature—namely, that interspersed with these puzzles is an introductory account of symbolic logic (a subject that is fortunately being taught today in many of our high schools) and an explanation of how this valuable technique can systematically solve whole tracts of puzzles of the knight–knave variety. (This should be of particular interest to teachers of logic—at either the high school or college level—who wish to enliven their logic courses with creative and challenging puzzles.) Therefore, the knowledge that the reader will gain will pay off handsomely in clarifying the later and more profound chapters on Gödel’s work.

  Another theme of the later chapters—and of equal interest to artificial intelligence—is that of self-fulfilling beliefs. Under what circumstances can the mere belief in a proposition cause the belief to be true? (Could this have anything to do with religion?) There is an important theorem of the logician M. H. Löb that is highly relevant here. This theorem is closely related to Gödel’s theorem, and when stated first in terms of reasoners and their beliefs, it is within easy grasp of the general reader.

  Although my primary emphasis is on belief systems, by no means do I stop there. As the book advances, the reader is led to a deeper and deeper understanding of how these belief systems are related to important systems of mathematics. This in turn leads us to the philosophically fascinating subject of possible world semantics—a field conceived by Leibniz and brought to perfection in this century by the logician Saul Kripke. This subject also is playing a major role today in computer science and artificial intelligence.

  I have lectured a good deal on all this material to such diverse groups as bright high school students and Ph.D.’s in mathematics, philosophy, and computer science. The responses of both groups were equally gratifying—they were intrigued. Indeed, any neophyte who is good at math or science can thoroughly master this entire book (though some application will be needed), yet many an expert will find here a wealth of completely new and fresh material.

  It is remarkable how logic, philosophy, psychology, artificial intelligence, computer science, and mathematics are drawing closer and closer together these days. We are living in an exciting era!

  RAYMOND SMULLYAN

  Elka Park, N.Y.

  July 1986

  • Part I •

  YOU MIGHT BE SURPRISED!

  • 1 •

  A Diabolical Puzzle

  I BELIEVE that the following puzzle may well be the most diabolical puzzle ever invented (and if it is, I proudly take credit for the invention).

  Two people—A and B—each make an offer, which is given below. The problem is to determine which of the offers is better.

  A’s Offer: You are to make a statement. If the statement is true, you get exactly ten dollars. If the statement is false, then you get either less than ten or more than ten dollars, but not exactly ten dollars.

  B’s Offer: You are to make a statement. Regardless of whether the statement is true or false, you get more than ten dollars.

  Which of the two offers would you prefer? Most people decide that B’s offer is better, since it guarantees more than ten dollars, whereas with A’s offer, there is no certainty of winning more than ten. And it does seem that B’s offer is better, but seeming is sometimes deceptive. In fact, I will make an offer of my own: If any of you are
willing to make me A’s offer, I’ll pay you twenty dollars in advance. Anyone game? (Before taking me up on it, you had better read the rest of this chapter!)

  • • •

  I will not give the solution to the above problem until after first considering some simpler, related puzzles.

  In my book To Mock a Mockingbird, I presented the following puzzle: Suppose I offer two prizes—Prize 1 and Prize 2. You are to make a statement. If the statement is true, then I am to give you one of the two prizes (not saying which one). If your statement is false, then you get no prize. Obviously you can be sure of winning one of the two prizes by saying: “Two plus two is four,” but suppose you have your heart set on Prize 1; what statement could you make that would guarantee that you will get Prize 1?

  The solution I gave is that you say: “You will not give me Prize 2.” If the statement is false, then what it says is not the case, which means that I will give you Prize 2. But I can’t give you a prize for making a false statement, and so the statement can’t be false. Therefore, it must be true. Since it is true, then what it says is the case, which means that you will not get Prize 2. But since your statement was true, I must give you one of the two prizes, and since it is not Prize 2, it must be Prize 1.

  As we will see shortly, this little puzzle is closely related to Gödel’s famous Incompleteness Theorem. To find out how, let us consider a similar puzzle (actually, the same puzzle in a different guise). First, we go to the Island of Knights and Knaves (which plays a prominent role in this book) in which every inhabitant is either a knight or a knave. On this island knights make only true statements and knaves make only false ones.

  Suppose now that there are two clubs on this island—Club I and Club II. Only knights are allowed to be members of either club; knaves are rigorously excluded from both. Also, every knight is a member of one and only one of the two clubs. You visit the island one day and meet an unknown native who makes a statement from which you can deduce that he must be a member of Club I. What statement can he have made from which you can deduce this?

  In analogy with the last problem, the speaker could have said: “I am not a member of Club II.” If the speaker were a knave, then he really couldn’t be a member of Club II and would have made a true statement, which a knave cannot do. Therefore he must be a knight, and his statement must have been true; he really isn’t a member of Club II. But since he is a knight, he must be a member of a club—so he belongs to Club I.

  The analogy should be obvious: Club I corresponds to those who make true statements and will get Prize 1; Club II corresponds to those who make true statements and will get Prize 2.

  These puzzles embody the essential idea behind Gödel’s famous sentence that asserts its nonprovability in a given mathematical system. Suppose we classify all the true sentences of the system (like the knights in the puzzle above) into two groups: Group I consists of all sentences of the system which, though true, are not provable in the system; and Group II consists of all the sentences which are not only true but are actually provable in the system. What Gödel did was to construct a sentence that asserted that it was in Group II—the sentence can be paraphrased, “I am not provable in the system.” If the sentence were false, then what it says would not be the case, which would mean that it is provable in the system, which it cannot be (since all sentences provable in the system are true). Hence the sentence must be true, and, as it says, it is not provable in the system. Thus Gödel’s sentence is true, but not provable in the system.

  We will have much to say about Gödel sentences in the course of this book. For now, I wish to consider some more variants of the Prize Puzzle.

  1. First Variant

  Again I offer two prizes—Prize 1 and Prize 2. If you make a true statement, I will give you at least one of the two prizes and possibly both. If you make a false statement, you get no prize. Suppose you are ambitious and wish to win both prizes. What statement would you make? (Solutions appear at the ends of chapters unless otherwise specified.)

  2. Second Variant

  This time the rules change a bit: If you make a true statement, you get Prize 2; if you make a false statement, you don’t get Prize 2 (you might or might not get Prize 1). Now what statement will win you Prize 1?

  3. A Perverse Variant

  Suppose that in a perverse frame of mind, I now tell you that if you make a false statement, you will get one of the two prizes, but if you make a true statement, you get no prize. What statement will win Prize 1?

  4. More on the Diabolical Puzzle

  Now let us return to the puzzle that opened this chapter: What was diabolical was my offer to pay you twenty dollars for making me A’s offer, because if you took me up on it, I could win as much from you as I liked—say, a million dollars. Can you see how?

  SOLUTIONS

  1. A statement that works is: “I will either get both prizes or no prize.” If the statement is false, then what it says is not the case, which means that you will get exactly one prize. But you can’t get a prize for a false statement. Therefore the statement must be true, and you really will get either both prizes or no prize. Since you did not make a false statement, which would result in no prize, you must get both prizes.

  2. Just say: “I will get no prize.” If the statement is true, then on the one hand you get no prize (as the statement says), but on the other hand, you get Prize 2 for having made a true statement. This is a clear contradiction, hence the statement must be false. Then, unlike what the statement says, you must get a prize. You can’t get Prize 2 for a false statement, so you get Prize 1.

  3. This time say: “I will get Prize 2.” I leave the proof to the reader.

  4. All I have to do is say: “You will neither pay me exactly ten dollars nor exactly one million dollars.” If my statement is true, then on the one hand you will not pay me either exactly ten dollars or exactly a million dollars, but on the other hand you must pay me exactly ten dollars for having made a true statement. This is a contradiction, hence the statement can’t be true and must be false. Since it is false, what it says is not the case, which means that you will pay me either exactly ten dollars or exactly a million dollars, but you can’t pay me exactly ten dollars for a false statement, hence you must pay me a million dollars.

  Anyone still game?

  • 2 •

  Surprised?

  LET US now turn to the paradox at the surprise examination—a paradox that is quite relevant to the consideration of Gödel in this book. We will look at it in the following form: On a Monday morning, a professor said to his class, “I will give you a surprise examination someday this week. It may be today, tomorrow, Wednesday, Thursday, or Friday at the latest. On the morning of the day of the examination, when you come to class, you will not know that this is the day of the examination.”

  Well, a logic student reasoned as follows: “Obviously I can’t get the exam on the last day, Friday, because if I haven’t gotten the exam by the end of Thursday’s class, then on Friday morning I’ll know that this is the day, and the exam won’t be a surprise. This rules out Friday, so I now know that Thursday is the last possible day. And, if I don’t get the exam by the end of Wednesday, then I’ll know on Thursday morning that this must be the day (because I have already ruled out Friday), hence it won’t be a surprise. So Thursday is also ruled out.”

  The student then ruled out Wednesday by the same argument, then Tuesday, and finally Monday, the day on which the professor was speaking. He concluded: “Therefore I can’t get the exam at all; the professor cannot possibly fulfill his statement.” Just then, the professor said: “Now I will give you your exam.” The student was most surprised!

  What was wrong with the student’s reasoning?

  Dozens of articles have been written about this famous problem, and uniform agreement about the correct analysis does not yet seem to have been reached. My own view is very briefly as follows:

  Let me put myself in the student’s place. I claim that I could g
et a surprise examination on any day, even on Friday! Here is my reasoning: Suppose Friday morning comes and I haven’t gotten the exam yet. What would I then believe? Assuming I believed the professor in the first place (and this assumption is necessary for the problem), could I consistently continue to believe the professor on Friday morning if I hadn’t gotten the exam yet? I don’t see how I could. I could certainly believe that I would get the exam today (Friday), but I couldn’t believe that I’d get a surprise exam today. Therefore, how could I trust the professor’s accuracy? Having doubts about the professor, I wouldn’t know what to believe. Anything could happen as far as I’m concerned, and so it might well be that I could be surprised by getting the exam on Friday.

  Actually, the professor said two things: (1) You will get an exam someday this week; (2) You won’t know on the morning of the exam that this is the day. I believe it is important that these two statements should be separated. It could be that the professor was right in the first statement and wrong in the second. On Friday morning, I couldn’t consistently believe that the professor was right about both statements, but I could consistently believe his first statement. However, if I do, then his second statement is wrong (since I will then believe that I will get the exam today). On the other hand, if I doubt the professor’s first statement, then I won’t know whether or not I’ll get the exam today, which means that the professor’s second statement is fulfilled (assuming he keeps his word and gives me the exam). So the surprising thing is that the professor’s second statement is true or false depending respectively on whether I do not or do believe his first statement. Thus the one and only way the professor can be right is if I have doubts about him; if I doubt him, that makes him right, whereas if I fully trust him, that makes him wrong! I don’t know whether this curious point has been taken into consideration before.