Burden of Proof:
Raymond Smullyan Puzzles Over Kurt Gödel's Theorems
Raymond Smullyan
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.
He currently resides in the upper Catskill Mountains, where he
constantly entertains audiences with puzzles, jokes, magic, music
and readings - some of which can be found on the internet.
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
which contains at least elementary arithmetic, there must always
be a sentence which though true is not provable in the system.
Gödel proved this by showing how to construct a sentence which
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 currently 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 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 on 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 which 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 which 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."
