Kurt Gödel
1906 
1978
He turned the lens of mathematics on itself and hit upon his
famous "incompleteness theorem" — driving a stake through the
heart of formalism
By DOUGLAS HOFSTADTER for Time Magazine
Kurt Gödel was born in 1906 in Brunn, then part of the
AustroHungarian Empire and now part of the Czech Republic, to a
father who owned a textile factory and had a fondness for logic
and reason and a mother who believed in starting her son's
education early. By age 10, Gödel was studying math, religion
and several languages. By 25 he had produced what many consider
the most important result of 20th century mathematics: his
famous "incompleteness theorem." Gödel's astonishing and
disorienting discovery, published in 1931, proved that nearly a
century of effort by the world's greatest mathematicians was
doomed to failure.
To appreciate Gödel's theorem, it is crucial to understand how
mathematics was perceived at the time. After many centuries of
being a typically sloppy human mishmash in which vague
intuitions and precise logic coexisted on equal terms,
mathematics at the end of the 19th century was finally being
shaped up. Socalled formal systems were devised (the prime
example being Russell and Whitehead's Principia Mathematica) in
which theorems, following strict rules of inference, sprout from
axioms like limbs from a tree. This process of theorem sprouting
had to start somewhere, and that is where the axioms came in:
they were the primordial seeds, the Urtheorems from which all
others sprang.
The beauty of this mechanistic vision of mathematics was that it
eliminated all need for thought or judgment. As long as the
axioms were true statements and as long as the rules of
inference were truth preserving, mathematics could not be
derailed; falsehoods simply could never creep in. Truth was an
automatic hereditary property of theoremhood.
The set of symbols in which statements in formal systems were
written generally included, for the sake of clarity, standard
numerals, plus signs, parentheses and so forth, but they were
not a necessary feature; statements could equally well be built
out of icons representing plums, bananas, apples and oranges, or
any utterly arbitrary set of chicken scratches, as long as a
given chicken scratch always turned up in the proper places and
only in such proper places. Mathematical statements in such
systems were, it then became apparent, merely precisely
structured patterns made up of arbitrary symbols.
Soon it dawned on a few insightful souls, Gödel foremost among
them, that this way of looking at things opened up a brandnew
branch of mathematics — namely, metamathematics. The familiar
methods of mathematical analysis could be brought to bear on the
very patternsprouting processes that formed the essence of
formal systems — of which mathematics itself was supposed to be
the primary example. Thus mathematics twists back on itself,
like a selfeating snake.
Bizarre consequences, Gödel showed, come from focusing the lens
of mathematics on mathematics itself. One way to make this
concrete is to imagine that on some far planet (Mars, let's say)
all the symbols used to write math books happen — by some
amazing coincidence — to look like our numerals 0 through 9.
Thus when Martians discuss in their textbooks a certain famous
discovery that we on Earth attribute to Euclid and that we would
express as follows: "There are infinitely many prime numbers,"
what they write down turns out to look like this:
"84453298445087 87863070005766619463864545067111." To us it
looks like one big 46digit number. To Martians, however, it is
not a number at all but a statement; indeed, to them it declares
the infinitude of primes as transparently as that set of 34
letters constituting six words a few lines back does to you and
me.
Now imagine that we wanted to talk about the general nature of
all theorems of mathematics. If we look in the Martians'
textbooks, all such theorems will look to our eyes like mere
numbers. And so we might develop an elaborate theory about which
numbers could turn up in Martian textbooks and which numbers
would never turn up there. Of course we would not really be
talking about numbers, but rather about strings of symbols that
to us look like numbers. And yet, might it not be easier for us
to forget about what these strings of symbols mean to the
Martians and just to look at them as plain old numerals?
By such a simple shift of perspective, Gödel wrought deep magic.
The Gšdelian trick is to imagine studying what might be called
"Martianproducible numbers" (those numbers that are in fact
theorems in the Martian textbooks), and to ask questions such
as, "Is or is not the number 8030974 Martianproducible (M.P.,
for short)?" This question means, Will the statement '8030974'
ever turn up in a Martian textbook?
Gšdel, in thinking very carefully about this rather surreal
scenario, soon realized that the property of being M.P. was not
all that different from such familiar notions as "prime number,"
"odd number" and so forth. Thus earthbound number theorists
could, with their standard tools, tackle such questions as,
"Which numbers are M.P. numbers, and which are not?" for
example, or "Are there infinitely many nonM.P. numbers?"
Advanced math textbooks — on Earth, and in principle on Mars as
well — might have whole chapters about M.P. numbers.
And thus, in one of the keenest insights in the history of
mathematics, Gödel devised a remarkable statement that said
simply, "X is not an M.P. number" where X is the exact number we
read when the statement "X is not an M.P. number" is translated
into Martian math notation. Think about this for a little while
until you get it. Translated into Martian notation, the
statement "X is not an M.P. number" will look to us like just
some huge string of digits — a very big numeral. But that string
of Martian writing is our numeral for the number X (about which
the statement itself talks). Talk about twisty; this is really
twisty! But twists were Gšdel's specialty — twists in the fabric
of spacetime, twists in reasoning, twists of all sorts.
By thinking of theorems as patterns of symbols, Gšdel discovered
that it is possible for a statement in a formal system not only
to talk about itself, but also to deny its own theoremhood. The
consequences of this unexpected tangle lurking inside
mathematics were rich, mindboggling and — rather oddly — very
sad for the Martians. Why sad? Because the Martianslike
Russell and Whitehead — had hoped with all their hearts that
their formal system would capture all true statements of
mathematics. If Gšdel's statement is true, it is not a theorem
in their textbooks and will never, ever show up — because it
says it won't! If it did show up in their textbooks, then what
it says about itself would be wrong, and who — even on Mars —
wants math textbooks that preach falsehoods as if they were
true?
The upshot of all this is that the cherished goal of
formalization is revealed as chimerical. All formal systems — at
least ones that are powerful enough to be of interest — turn out
to be incomplete because they are able to express statements
that say of themselves that they are unprovable. And that, in a
nutshell, is what is meant when it is said that Gödel in 1931
demonstrated the "incompleteness of mathematics." It's not
really math itself that is incomplete, but any formal system
that attempts to capture all the truths of mathematics in its
finite set of axioms and rules. To you that may not come as a
shock, but to mathematicians in the 1930s, it upended their
entire world view, and math has never been the same since.
Gödel's 1931 article did something else: it invented the theory
of recursive functions, which today is the basis of a powerful
theory of computing. Indeed, at the heart of Gödel's article
lies what can be seen as an elaborate computer program for
producing M.P. numbers, and this "program" is written in a
formalism that strongly resembles the programming language Lisp,
which wasn't invented until nearly 30 years later.
Gšdel the man was every bit as eccentric as his theories. He and
his wife Adele, a dancer, fled the Nazis in 1939 and settled at
the Institute for Advanced Study in Princeton, where he worked
with Einstein. In his later years Gödel grew paranoid about the
spread of germs, and he became notorious for compulsively
cleaning his eating utensils and wearing ski masks with eye
holes wherever he went. He died at age 72 in a Princeton
hospital, essentially because he refused to eat. Much as formal
systems, thanks to their very power, are doomed to
incompleteness, so living beings, thanks to their complexity,
are doomed to perish, each in its own unique manner.
JACANA HOME PAGE

CLASSIC VIDEO CLIPS

JACANA ASTRONOMY SITE
JACANA PHOTO LIBRARY 
OLD MAUN PHOTO GALLERY 
MAUN PHONE DIRECTORY
FREE FONTS 
PIC OF THE DAY

GENERAL LIBRARY 
MAP LIBRARY 
TECHNICAL LIBRARY
HOUSE PLANS LIBRARY

MAUN EMAIL, WEBSITE & SKYPE LIST

BOTSWANA GPS COORDINATES
MAUN SAFARI WEB LINKS 
FREE SOFTWARE 
JACANA WEATHER PAGE
JACANA CROSSWORD LIBRARY 
JACANA CARTOON PAGE 
DEMOTIVATIONAL POSTERS
This web page was last updated on:
10 December, 2008
