Raymond M. Smullyan - The Gödelian Puzzle Book: Puzzles, Paradoxes and Proofs

THE GDRIN

PUZZLE BOOK

THE GDELIM

PUZZLE BOOK

Puzzles, Paradoxes and Proofs

Raymond M. Smullyan

DOVER PUBLICATIONS, INC.

Mineola, New York

Copyright

Copyright 2013 by Raymond M. Smullyan

All rights reserved.

Bibliographical Note

The Gdelian Puzzle Book is a new work, first published by Dover Publications, Inc., in 2013.

International Standard Book Number

eISBN-13: 978-0-486-31577-5

Manufactured in the United States by Courier Corporation

49705401 2013

www.doverpublications.com

PREFACE

This book, like hardly any others, explains the pioneering discoveries of the amazing logician Kurt Gdel through recreational logic puzzles. Its title is based on the fact that almost all the puzzles of the book are centered around Gdels celebrated result.

In the first quarter of the twentieth century there were some mathematical systems in existence that were so comprehensive that it was generally assumed that every mathematical statement could either be proved or disproved within the system. In 1931 Gdel astounded the entire mathematical world by showing that this was not the case [Gdel, 1931]: For each of the mathematical systems in question, there must always be mathematical statements that can be neither proved nor disproved within the system. Indeed, Gdel provided an actual recipe for exhibiting in each such system, a sentence which must be true, but not provable, in the system. This famous result is known as Gdels Theorem.

The essential idea behind Gdels proof is this:

Gdel assigned to each mathematical sentence of the system a number, now known as the Gdel number of the sentence. He then constructed a most ingenious sentence S that asserted that a certain number n was the Gdel number of a sentence that was not provable in the system. Thus this sentence S was true if and only if n was the Gdel number of an unprovable sentence. But the amazing thing is that n was the Gdel number of the very sentence S! Thus S asserted that its own Gdel number was the Gdel number of an unprovable sentence. Thus in effect, S was a self-referential sentence that asserted its own non-provability. This meant that either S was true and not provable or S was false but provable. The latter alternative seemed completely out of the question since it was obvious from the nature of the system in question that only true sentences could be proved in the system. Thus Gdels sentence S was true but not provable in the system. Its truth was known only by going outside the system and noting some of its properties.

How did Gdel manage to construct such an ingenious sentence? It is the purpose of this book to explain how, in terms that are completely comprehensible to the general publiceven those with no background at all in mathematical logic. I have written this book so that it should be perfectly comprehensible to any reasonably bright high-school student. This is actually the first of my popular logic puzzle books in which I give a complete proof of Gdels theorem for one particularly important mathematical system, as well as provide a host of generalizations that have never been published before, and should therefore be of interest, not only to the general reader, but to the logical specialist as well. These generalizations can be found in

On the whole, I have written this book in a very informal style. After the chatty introductory first three of its chapters contain my generalized Gdel theorems, which are unusual in that they do not involve the usual machinery of symbolic logic! I have deferred symbolic logicthe logical connectives and quantifiersto the last three chapters, which begin by explaining its basics and what is known as first-order arithmetic followed by a presentation of the famous axiom system known as Peano Arithmetic. And I give a complete proof there of Gdels celebrated result that there are sentences of Peano Arithmetic that cannot be proved or disproved with in that axiom system.

Gdels discoveries have led to an even more important result: Is there any purely mechanical method of determining which mathematical statements are true and which are false? This brings us to the subject of decision. theory, better known as recursion theory, which today plays such a vital role in computer science. of this book explains some basics of this important field. It turns out that in fact there is no purely mechanical method of deciding which mathematical statements are true and which are not! No computer can possibly settle all mathematical questions. It seems that brains and ingenuity are, and always will be, required. In the witty words of the mathematician Paul Rosenbloom, this means that Man can never eliminate the necessity of using his own intelligence, regardless of how cleverly he tries!

I would like to thank Dr. Sue Toledo for her very helpful editing work on this book.

TABLE OF CONTENTS

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 doesnt exist, or you dont exist, but you wont 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, Im 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 thats only one mans 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? Isnt everybody?

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

Do you have any rational evidence that you are now awake? Isnt 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.