Best known for his Incompleteness Theorem, Kurt Gödel (1906-1978) is considered one of the most important mathematicians and logicians of the 20th century. By showing that the establishment of a set of axioms encompassing all of mathematics would never succeed, he revolutionized the world of mathematics, logic, and philosophy.
Raymond Smullyan was born in 1919 in Far Rockaway, New York. He earned his B.S. at the University of Chicago in 1955 and his Ph. D. at Princeton University in 1959. Smullyan has had a remarkably diverse sequence of careers—mathematician, magician, concert pianist, internationally known writer, having authored twenty-six books on a wide variety of subjects, six of which are academic, one of them being “Gödel’s Theorems.” His famous puzzle books are special, in that they are designed to introduce the general reader to deep results in mathematical logic.
Q: You are a trained logician having earned degrees from the University of Chicago and from Princeton University where you studied under, among others, Rudolf Carnap and Alonzo Church, respectively. On top of this, you’ve been a Professor of philosophy for many years at various colleges and universities. How did you go from writing highly technical treatises on logic to writing popular books on mathematical and logical puzzles?
A: I wanted to make puzzle books designed to enable the general reader to understand deep mathematical results in mathematical logic—particularly results related to Gödel’s famous Incompleteness Theorem, which is that in any mathematical system that contains at least elementary arithmetic, there must always be a sentence that though true is not provable in the system. Gödel proved this by showing how to construct a sentence that asserted its own non-provability in the system.
Q: You’ve written extensively on Gödel’s Incompleteness Theorems—some highly technical papers and several popular books. How would you suggest a novice approach Gödel’s work?
A: A novice who would like to have some idea of Gödel’s proof might try my book The Lady or the Tiger, or Forever Undecided, both of which introduce some of the basic ideas. I am writing a more comprehensive account for the novice, which is tentatively titled A Logical Journey.
Q: You’ve also written puzzles around Gödel’s proof, making his ideas more accessible to a layman. Can you give us an example?
A: To illustrate the essential idea behind Gödel’s proof, consider a system (S) that proves various English sentences and proves only true ones. What sentence must be such that it has to be true but not provable in the system? Well, one such sentence is: This Sentence is not provable in system (S). If the sentence were false, then contrary to what it says, it WOULD be provable in the system, which contradicts the given fact that the system proves only true sentences, and, therefore, the sentence cannot be false. Thus the sentence must be true, and so what it says really is the case—namely that it is not provable in the system. Thus, the sentence is true but not provable in the system. Alternatively, consider a country in which every inhabitant is either always truthful or always lies. A certain logician whose proofs are always correct, visited this country, and an inhabitant made a statement to him from which it follows that he must be truthful, but the logician can never prove that he is. What statement could that be? Well, one such statement is: “You can never prove that I am truthful.” I leave it to you to show that the inhabitant must be truthful, but the logician can never prove that he is.
Q: Gödel’s Incompleteness Theorems are what, in W.V. Quine’s words, “sealed his immortality.” But Gödel also made two other important discoveries. What were they?
A: Two other important results of Gödel are his Completeness Theorem—that all valid sentences of first-order logic are provable in any of the standard axiom systems—and his proof that the Continuum Hypotheses (that there exists no set intermediate in size between the set of positive integers and the set of points on the line) cannot be disproved from any of the known systems of set theory.
Q: Have the techniques that went into formulating Gödel’s proof of incompletability have any other use elsewhere?
A: Gödel’s discoveries have very important applications to computer science and to the mathematical field known as recursion theory, which deals with operations that can be performed by purely mechanical devices.
Q: Your teacher, Alonzo Church, extended the work of Gödel on the foundations of mathematics in a direction that bears on modern philosophy and computer science. Can you briefly explain how?
A: Contrary to the opinions of many philosophers, I do not believe that Gödel’s discoveries have any applications to philosophy whatsoever. It is enough that they are of extreme importance to mathematics and computer science.
Q: Alan Turing, the English mathematician, independently proposed a more direct but equivalent definition of computability in the form of a theoretical computing device known as a Turing machine. What exactly was his approach?
A: It is not possible in a short space to give an adequate account of the work of Alan Turing. Suffice it to say that he invented the concept of a machine—a so-called “Universal Turing Machine”—that can do what any purely mechanical device can never do. He then showed that there was a problem (known as the halting problem) that even this great machine could not possibly solve.
Q: You’ve argued that Tarski’s Undefinability Theorem deserves much of the attention garnered by Gödel’s Incompleteness Theorems. Why?
A: Tarski showed that truth in elementary arithmetic is not definable in elementary arithmetic, whereas Gödel showed that provability in the system of axiomatic elementary arithmetic IS definable in elementary arithmetic, and therefore provability and truth do not coincide, which means that some true sentence is not provable in the system. This yields an alternative and particularly elegant proof of Gödel’s theorem.
Q: How does Löb’s theorem, formulated by mathematical logician Martin Hugo Löb, relate to Gödel’s?
A: The sentence that Gödel constructed is one that asserts its own non-provability, and that sentence must be true but not provable (in the axiom system under consideration). The logician Leon Henkin then constructed a sentence that asserted that it WAS provable, and this sentence is either both true and provable or neither true nor provable, but is it provable or not? This remained an unsolved problem for many years until it was finally solved affirmatively (the sentence IS provable) by a theorem of Martin Löb, which also generalized Gödel’s great Second Incompleteness Theorem, which is that for each of the systems under consideration, the system cannot prove its own consistency! Löb’s theorem also opened up a whole new field of modal logic known as the logic of provability.
Q: What are you currently working on in the world of logic?
A: These days I work on topics connected with self-reference, which of course ties in with Gödel’s work and with computer science, as well as on my combined popular and academic book A Logical Journey. I am also very much involved with musical activity, and my piano playing and videos I made can be heard and seen on the internet—Raymond Smullyan.
Further Comments:
The work of Gödel, Tarski, Löb, Church, Post, Kleene, Turing, and many others all point to the fact that (in the prophetic words of Post, mathematics is and must remain creative. In other words, mathematics cannot be fully mechanized; ingenuity is always required. Or, in the delightfully witty words of Paul Rosenbloom, “Man can never eliminate the necessity of using his own intelligence, regardless of how cleverly he tries.”
SUGGESTED READING
  |   |   |
