The Incomplete Gödel
Incompleteness: The Proof and Paradox of Kurt Gödel.
Rebecca Goldstein. 296 pp. W. W. Norton, 2005. $22.95.
A World Without Time: The Forgotten Legacy of Gödel and
Einstein. Palle Yourgrau. x + 210 pp. Basic Books, 2005. $24.
Such eminent 20th-century physicists as Albert Einstein, Niels Bohr
and Werner Heisenberg are well known to almost all scientists,
whether or not they happen to be physicists. Yet most scientists are
unfamiliar with eminent mathematicians from the same period, such as
David Hilbert (Germany) and Oswald Veblen (United States). A rare
exception is John von Neumann (Hungary and the United States), a
mathematician whose contributions to quantum mechanics, the
stored-program concept for computers, and the atomic bomb resonate
with many physical scientists.
One mathematician who deserves to be better known, and who was
highly esteemed by von Neumann, is Kurt Gödel (1906-1978). In
1951 Gödel shared the first Einstein Award with physicist
Julian Schwinger (who later won the Nobel Prize). At the award
ceremony, von Neumann gave a speech calling Gödel's work
"a landmark which will remain visible far in space and time."
Who was Gödel, and why was his work of fundamental
significance? These questions are the subject of two recent books,
both popularizations: Incompleteness: The Proof and Paradox of
Kurt Gödel, by Rebecca Goldstein, and A World
Without Time: The Forgotten Legacy of Gödel and
Einstein, by Palle Yourgrau. The association between Einstein
and Gödel began when the latter was a visiting member of the
renowned Institute for Advanced Study in Princeton for several years
in the 1930s. Later they became close friends. Veblen had brought
Gödel to the institute after hearing him speak at Karl Menger's
colloquium at the University of Vienna. And it was Veblen who saved
the physically frail Gödel from being drafted into the Nazi
army by getting him a non-quota immigrant visa so that he could
leave Austria permanently for the United States.
Gödel, who had originally intended to become a physicist, was
turned to mathematics by Philip Furtwängler's course on number
theory at the University of Vienna. Paralyzed from the neck down,
Furtwängler lectured from his wheelchair without notes while
his assistant wrote equations on the blackboard. Then Gödel,
seeking results of more fundamental significance than he could find
in number theory, moved to the new field of mathematical logic,
which Hilbert—the most influential mathematician of the early
20th century—had made mathematically respectable during the
1920s. (Earlier work on mathematical logic, by Bertrand Russell
among others, had reinforced the traditional tendency to regard
logic as part of philosophy—and hence subject to all of
philosophy's ambiguity—rather than as part of mathematics,
where exactness is the watchword.)
Gödel's doctoral thesis, which was vastly more important than
the average dissertation in mathematics, established the
"semantic completeness" of first-order logic—a
different matter from the "incompleteness" to be discussed
below. The thesis settled a major problem, which Hilbert had
proposed in 1928. What Gödel showed was that any sentence
S can be proved in a formal system (that is, in a formal
language, like a computer language, with a computable list of
sentences and of axioms) if and only if S is
"valid"—that is, true in all "models" (all
sets with appropriate functions and relations on the set). Thus he
established a connection between what is true in a formal system and
what can be proved in it.
Certainly Hilbert expected that the semantic completeness of
first-order logic could be established. However, neither he nor
anyone else expected that attempts to establish the semantic
completeness of the next more complicated kind of logic
(second-order logic) had to fail! Yet this conclusion
followed from Gödel's next results, his incompleteness
theorems, which had consequences for both first-order and
second-order logic. (Roughly speaking, first-order logic is adequate
only for the simplest parts of mathematics, whereas second-order
logic is needed to express adequately the parts of mathematics
dealing with the infinite. Technically, first-order logic allows the
quantifiers "for all x" and "there is some
x" to apply only when x is an object, whereas
second-order logic allows x also to be any set of objects.)
Gödel's two incompleteness theorems were his crowning
achievement. They have often been misunderstood in their popular
presentations. We must first be clear about what the theorems do
not say. They do not state that there are absolutely
unprovable truths. What the first theorem asserts is that if a
system of axioms can express the arithmetic of both addition and
multiplication of counting numbers (1, 2, 3 and so on), and if the
system is consistent (that is, if it does not imply a
contradiction), then there will be a sentence G of the
system that is unprovable in the system but is nevertheless true. If
this new sentence G is now added to the axioms of the
system, then applying Gödel's procedure to this enlarged system
will generate a new sentence H, which will be true but
unprovable in the system with the added axiom G. So it
would be more accurate to describe Gödel's theorems as having
to do with "incompletability" rather than
"incompleteness." The second incompleteness theorem states
that, given the same hypothesis as the first, one such true but
unprovable sentence expresses the consistency of the system.
Hilbert insisted that it is possible to prove the consistency of all
of classical mathematics (and, in particular, of both the counting
numbers and the real numbers) by using only the truths of the
elementary arithmetic of the counting numbers. The attempt to do so
became known as "Hilbert's program." Gödel's
incompleteness theorems showed that Hilbert was wrong; the
arithmetic of the counting numbers could not prove even its own
consistency, much less that of the real numbers!
For Gödel's proof to work, however, it is essential that
arithmetic have both addition and multiplication available.
In fact, if we consider the counting numbers with just addition (and
not multiplication) defined on them, then we can find a set of
axioms that prove all true first-order sentences in the
language of this system. So Hilbert was right—for this weaker system.
Returning to the arithmetic of counting numbers with addition and
multiplication: Why not simply take all the true sentences
of this system as axioms? What Gödel's theorems show, in this
case, is that there is no algorithm (or equivalently, no computer
program) that will decide whether any given sentence of arithmetic
is true or not. Although Hilbert had carefully distinguished the
"true" and the "provable" in a formal system, he
believed that these two concepts were in fact identical. He was
wrong. Yet he was never able to accept that Gödel had
mathematically proved him to be wrong.
The high points of Goldstein's book, Incompleteness, are
the first and last chapters, in which she gives some of the flavor
of Gödel's personality. The book starts with an imagined
description of Einstein walking home from the institute with
Gödel. Here she quotes the recollections of Ernst Gabor Straus
about Einstein's friendship with Gödel: Einstein was
"gregarious, happy, full of laughter and common sense."
Gödel, on the contrary, was "extremely solemn, very
serious, quite solitary and distrustful of common sense as a means
of arriving at the truth."
They were very, very dissimilar people, but for some reason
they understood each other well and appreciated each other
enormously. Einstein often mentioned that he felt that he should not
become a mathematician because the wealth of interesting and
attractive problems was so great that you could get lost in it
without ever coming up with anything of genuine importance. In
physics, he could see what the important problems were and could, by
strength of character and stubbornness, pursue them. But he told me
once, "Now that I've met Gödel, I know that the same thing
does exist in mathematics."
At the end of her book, Goldstein gives an absorbing account of the
last two decades of Gödel's life, after Einstein died. Here she
recounts the intellectual and personal isolation of Gödel in
his final years. His incipient paranoia finally overcame him, and he
starved himself to death for fear of being poisoned.
What is of lasting importance, however, is not Gödel's
psychological idiosyncrasies but the great conceptual depth of his
mathematical ideas. And unfortunately, between its first and last
chapters Goldstein's book is the "death of a thousand
cuts" to anyone who knows the history of mathematical logic and
of Gödel's work in particular. Like hydrofluoric acid, the
sheer accumulation of errors, both minor and major, erodes all the
trust that the informed reader might have had in her book. She even
gets the year in which Gödel first proved his incompleteness
theorem wrong—it was 1930, not 1929 as she suggests on page
156. She does not begin to understand the basis for Gödel's
mathematics, as she makes plain by stating (on page 139) that the
set of real numbers is of "higher ordinality" than the set
of natural numbers. What she meant was a completely different
concept, "higher cardinality." She even misunderstands
what the incompleteness theorems state, because she writes (on page
191) that "For Gödel, for each formal system there will be
truths expressible in that system that will not be provable."
But this is false, because there are infinitely many different
formal systems in which every truth expressible in the system is provable.
Unfortunately, Goldstein's errors are precisely the sort that many
copy editors would not catch: factual and conceptual errors. Such an
error occurs when Goldstein (on page 82) says that Olga Neurath was
the sister of Otto Neurath and the wife of Hans Hahn, when it was
actually the other way around: She was Neurath's wife and Hahn's
sister. Goldstein's book needed, prior to publication, a reader who
knew mathematical logic and its history and who could correct both
conceptual and factual flaws (such as the repeated misspelling of
the Austrian logician Georg Kreisel's name as "Kreisl").
The mathematical logician Simon Kochen, whom Goldstein thanks in her
acknowledgments, did not serve as such a reader; he has informed me
that he did not read the entire manuscript but merely pointed out
certain errors in her outline of the incompleteness theorems.
In sum, Goldstein does not understand mathematical logic and set
theory, the subjects of Gödel's mathematical work. Her book
would have benefited if she had just left them out and not pretended
to explain them. In any case, she should have avoided such
sophomoric touches as renaming first-order logic "limpid
logic." This strikes a mathematician as condescending. A
physicist might have the same reaction if Goldstein decided to
rename quantum mechanics "limpid physics."
Yourgrau's book, A World Without Time, although by no means
perfect, is a vast improvement on Goldstein's. He too tells the
story of Gödel's life, but with particular emphasis on the
friendship with Einstein. From that friendship emerged Gödel's
totally unexpected models of the general theory of relativity:
rotating universes in which it is possible to travel into the future
or the past if a spaceship can go at least two-thirds the speed of light.
Yourgrau discusses Gödel's incompleteness theorems more
adequately than Goldstein does. He understands that these theorems
originated from Gödel's attempt to carry out part of Hilbert's
program (in particular, to prove the consistency of the axioms for
the real numbers) and not from any attempt to refute that program.
And Yourgrau's prose is at least as compelling as Goldstein's.
In the end, Gödel's search for the deep truths of philosophy
and metaphysics—undertaken in the spirit of the great
philosopher/mathematician Gottfried Leibniz—was only partly
successful, even in his own opinion. Yet Gödel shared with
Einstein a deep-seated belief that the truth about physics and
mathematics was objective. This truth was not merely the creation of
the human mind but was there to be discovered.
In conclusion, the best biography of Gödel remains Logical
Dilemmas: The Life and Work of Kurt Gödel (A K Peters,
1997), by John W. Dawson, Jr., which recently became available in
paperback. Both Goldstein and Yourgrau rely heavily on Dawson's book
but do not always make it clear how much they do so.
If a reader wants to look at just one book about Gödel, it
should be Dawson's. Those who want a clear, simplified, but
fundamentally correct explanation of the incompleteness theorems
should read Ernst Nagel and James R. Newman's short book
Gödel's Proof. And those seeking a popular
introduction to Gödel's unusual rotating models of the laws of
general relativity should read Yourgrau's A World Without
Time. Goldstein's book, with its many errors, is best ignored.