Raymond Smullyan: The Reals Are Uncountable
Smullyan is one of the great popular expositors of logic, as well as author of several books on puzzles and games. The probability version of Cantor’s proof is re-cast following Smullyan’s angle as a two-player game, further challenging readers who doubt
- PDF / 219,420 Bytes
- 5 Pages / 441 x 666 pts Page_size
- 15 Downloads / 223 Views
16
Raymond Smullyan is a great writer of popular books on logic—especially books on various forms of the liar paradox. He is also a first-rate logician whose book on set theory with Melvin Fitting was just republished by Dover. This book gives a very readable and somewhat unusual approach to set theory, especially the independence results of Kurt Gödel and Paul Cohen. We will use an example from their book to explain Georg Cantor’s famous diagonal argument. I have an idea why some people have difficulty with Cantor’s beautiful proof. If you know it well, you may wish to read on anyway; if you do not know it or do not believe it, then please read on and see if I have something to say. I have discussed the argument before, but still feel there is something to add to the discussion. I have never had the pleasure of meeting Smullyan, but have heard a number of stories about him. One concerns the etiquette at Yale University, where I had my first job in the Computer Science department. One day I wrote a letter and gave it to a secretary to type up on our CS letterhead. My letter started Dear Dr. X: I am sending you my referee report on . . .
The letter came back slightly changed Dear Mr. X: I am sending you my referee report on . . .
I immediately asked why the change from “Dr.” to “Mr.”? The answer was: “This is Yale, we assume that all professionals have doctorates and call them ‘Mr.’ or ‘Ms.’ and so we never use any formal titles.” Okay I was new, I was young, so the letter went out as changed. Later on I heard a story about Smullyan, who had given a talk at Yale, in the 1950s, before he had his PhD. After his talk there was tea in his honor, and his host introduced Smullyan around to all. Mr. Blue, Mr. Green, Ms. Red, Mr. Yellow, and so on, I would like to introduce you to Smullyan. R.J. Lipton, K.W. Regan, People, Problems, and Proofs, DOI 10.1007/978-3-642-41422-0_16, © Springer-Verlag Berlin Heidelberg 2013
87
88
16
Raymond Smullyan: The Reals Are Uncountable
Note, the introduction was to “Smullyan” not “Mr. Smullyan.” I do not know firsthand if the story is true or not, but I like it very much. Oh well. Let’s turn to the classic argument of Cantor that proves the reals are uncountable. Somehow his argument is subtle, and many do not “get it.” There are some who are puzzled when they first see the proof, there are others who never understand it, and there are some who do not believe it at all. I would like to use Alice and Bob to help explain what the roadblock may be to understanding Cantor.
16.1
Alice and Bob Play Some Games
Consider the following simple game that Alice challenges Bob to play. Alice picks a natural number X, which she hides from Bob. Bob then must try and guess the number. This is a pretty tough game for Bob, but Alice is quite fair. She allows Bob to make an infinite number of guesses. It should be clear that Bob has a simple winning strategy. He just announces his strategy; he will say 1, 2, 3, 4, . . . , Eventually he will say X and he will win the game. Alice agrees. She then ch
Data Loading...
