Exercises and Puzzles II
I've finally managed to introduce the provability predicate and its properties without mentioning representability and recursiveness. The exercise is then to derive Löb's theorem and Gödel's incompleteness theorems. Unfortunately these deductions are not as simple as I thought they were. Probably too difficult for an introductory book.
I've also just made up this puzzle, which is not very difficult I think. ("Not very difficult" even in the ordinary sense of "not very difficult", not only in the David Chalmers sense.)
The city X is struck by a mysterious murder series. All inhabitants of X fear the murderer and take part in the investigations. The murderer however only fears inspectors A and B. For inspector A knows that the murderer lives at 27 or 29 Y lane, and inspector B knows that the murderer does not live in the same house as inspector A. Inspector A in fact lives at 27 Y lane, which is in the middle of the pictorial old part of X. Prove that inspector B lives at 29 Y lane.[Update: Dave Chalmers initiated the renaming of Y avenue to "Y lane".]