Meet Me Halfway

A logician goes to an island of knights and knaves. Knights always tell the truth; knaves always lie. One of the locals says “either I’m a knave or there’s gold on this island”. Is there gold on the island?

This kind of puzzle is a staple of the puzzle books of Raymond Smullyan, and Forever Undecided: A Puzzle Guide To Gödel is no exception. This isn’t just a compendium of brainteasers intended solely for entertainment though; Smullyan has a serious purpose. He’s explaining some of the main results in provability logic by recasting them in terms of the beliefs of logicians with various characteristics when faced with this sort of knight/knave puzzle. It’s a clever idea, and very much the kind of clever idea you would expect Raymond Smullyan to have.

It’s helpful to cast results like Gödel’s incompleteness theorems and Löb’s theorem in different terms, and especially in fairly concrete terms about things people say or the output of a computer program. It helps to explain the content of the results, and helps readers understand their significance. One thing Smullyan is pretty keen to get across is that the impossibility of a system of arithmetic proving its own consistency doesn’t give any reason for thinking such systems aren’t consistent. This makes sense, since we already knew that an inconsistent system could prove its own consistency - inconsistent systems prove everything - so if a system says it’s consistent that’s no reason to think it is. If you ask a resident of the knight-knave island if they’re a knight, knights and knaves will both say they are. Similarly, if you want to know if a system’s consistent, you shouldn’t ask the system itself, and the fact people didn’t properly figure this out until Gödel discovered that consistent systems wouldn’t answer the question doesn’t change that.

As well as discussing the results, the book also contains lots of exercises, with reasonably generous solutions. These are analogous to the kind of exercises you might get in a textbook on provability logic, except they’re expressed in different terms. Now, you might think that doing it in terms of knights and knaves and so on would make the whole thing so much fun that the hard work of getting your head round this material wouldn’t feel like hard work, and before you knew it you’d have all the proofs of the main results in provability logic at your fingertips. This was not my experience. The material is just as hard, and now you have to learn a bunch of new terminology. It isn’t Smullyan’s fault that this stuff is hard, but there are things I think he could have done to make it a bit easier.

First, the book doesn’t have an index, and the chapter headings are often whimsical (“It ain’t necessarily so!”), vague (“More Consistency Predicaments”), or related to the island-hopping framing device (“In Search of Oona”). This makes it difficult to go back and remind yourself of material when it comes up again. This is bad enough when reading a novel, but in a textbook it’s not really excusable. Smullyan hasn’t set out to write a textbook, but he wanted the material to be comprehensible to someone who (unlike me) was approaching it for the first time, and an index and analytic table of contents would have helped with that a lot.

Second, the book introduces a lot of new terminology: reasoners of type 1, 2, 3, 4, 1*, G, G* and Q; normal, regular, peculiar, modest, conceited, reflexive and stable reasoners; Gödelian systems, Löbian systems, and so on. Being a doofus, I wasn’t able to keep all the definitions in my head. Since there was no convenient way of looking them up, a lot of the time I couldn’t understand the exercises until I looked at the solutions to see what followed from a reasoner being regular or stable or of type 3 or whatever. This isn’t really satisfactory, so I skipped a lot of the exercises and solutions, and when I didn’t skip the exercises I often didn’t really know what I was being asked. An appendix in the back saying what all these definitions mean would have been a great help. The last chapter gives a summary of the main results, but that’s not the same thing and doesn’t make the exercises more comprehensible. I’m considering writing an appendix myself and sticking it in the back in case I or anyone else reads my copy of the book again. It’d take some work though, as the definitions are scattered throughout the book and there’s no index.

So, who’s the book for? I think you’d really enjoy the book if you liked whimsical logic puzzles and were already very familiar with the technical material. (I like whimsical logic puzzles but was only reasonably familiar with the technical material.) You’d also probably get some scholarly benefit from reading the book if your understanding of the proofs of the results was better than your understanding of what the results amount to. I’m the opposite, and I expect that’s normal for people who encounter it through studying philosophy. I guess if you encountered it through studying maths then things might be the right way round for you. Who else would like the book? Well, someone who liked puzzles and would be interested in provability logic but hadn’t seen any of the results before would probably like the book at first but find it became a bit of a slog about 100 pages in. If they’re the sort of person who can read a maths textbook without looking at the index, the contents page or a list of definitions used in the book, then they’d probably be fine. Here’s what Smullyan says about the target audience in the preface:

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.

I think that’s a bit optimistic, and if he wanted neophytes to apply themselves and master the entire book then he should have met them halfway with an index, and appendix and a better contents page. But I’ve no doubt people enjoyed the lectures.