The Gödelian Puzzle Book: Puzzles, Paradoxes and Proofs
Raymond M. Smullyan
Format: PDF / Kindle (mobi) / ePub
These brand-new recreational logic puzzles provide entertaining variations on Gödel's incompleteness theorems, offering ingenious challenges related to infinity, truth and provability, undecidability, and other concepts. Created by the celebrated logician Raymond Smullyan, the puzzles require no background in formal logic and will delight readers of all ages.
The two-part selection of puzzles and paradoxes begins with examinations of the nature of infinity and some curious systems related to Gödel's theorem. The first three chapters of Part II contain generalized Gödel theorems. Symbolic logic is deferred until the last three chapters, which give explanations and examples of first-order arithmetic, Peano arithmetic, and a complete proof of Gödel's celebrated result involving statements that cannot be proved or disproved. The book also includes a lively look at decision theory, better known as recursion theory, which plays a vital role in computer science.
If x is terminating, then the process of the original machine will terminate, and I will know that x is terminating. On the other hand, if x is non-terminating, then sx is terminating, hence the process of the duplicate machines will terminate, and I will then know that x is non-terminating. Thus if I could find a sage, I would then be able to determine which expressions are terminating and which are not.” “And have you found a sage?” asked Arnie with a smile. “No,” replied Bernie. “That’s what
solution of Problem 1 that a*a stumps U, hence a*a must also stump U' (Why?). Then a must stump U'# (since U'# is the diagonalizer of U'). Thus U'# is stumped by its own index a. Now let b be the index of U#'. Then, as we have seen in the solution of Problem 1, the number b*b stumps U. Hence b stumps U#, and so b also stumps the opposer U#' of U#. Thus U#' is stumped by its own index b. 3. Under the special conditions of this problem, for any number n, the index of Rn' is 2n, hence the index
He said that I could not prove he is a knight, but I just did! Hence he was wrong, and so he is a knave.” At this point the logician has become inconsistent! PART II PROVABILITY, TRUTH AND THE UNDECIDABLE CHAPTER XIII TRUTH AND PROVABILITY As already mentioned, Gödel showed that for mathematical systems of sufficient strength, there must always be sentences that are neither provable nor disprovable in the system [Gödel, 1931], Closely related to this is a result of the logician
(a) If A is representable then A is definable. (b) If A is definable then A is representable. (c) If H defines A then H represents A and H' represents the complement A of A. Problem 9. Prove that if some set is representable but not definable then the system (N) is incomplete. Problem 10. Prove that no superset of P0 disjoint from R0 can be definable in the system (N). Formal Systems. We now connect the subject of incompleteness with the recursion theory aspects of the last chapter. A
play the same instrument. M She is a pianist. What instrument does each play? Problem 3. Here is a rather easy puzzle about the strange island of Musica: On one of my visits there, I went to the home of a Mr. and Mrs. Smith. They owned a nice looking piano that I saw in their living room and I asked the wife whether it was a Steinway. She replied, “I am a violinist and our piano is not a Steinway.” Was the piano a Steinway or not? Problem 4. On another of my journeys to Musica, I visited the