Raymond Smullyan - FOREVER UNDECIDED

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 Gdel.

1. Gdels theorem. 2. Mathematical recreations. I. Title.
QA9.65.S68 1987 511.3 8645297
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

I S 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 Gdel (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 Gdels 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 Gdels 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 featurenamely, 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 knightknave variety. (This should be of particular interest to teachers of logicat either the high school or college levelwho 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 Gdels work.

Another theme of the later chaptersand of equal interest to artificial intelligenceis 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. Lb that is highly relevant here. This theorem is closely related to Gdels 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 semanticsa 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 gratifyingthey 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

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 peopleA and Beach make an offer, which is given below. The problem is to determine which of the offers is better.

As 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.

Bs 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 Bs offer is better, since it guarantees more than ten dollars, whereas with As offer, there is no certainty of winning more than ten. And it does seem that Bs 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 As offer, Ill 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 prizesPrize 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 cant give you a prize for making a false statement, and so the statement cant be false. Therefore, it must be true. Since it is true, then what it says