1
Kurt Gödel
Metamathematical results on formally undecidable propositions:
Completeness vs. Incompleteness
Motto: The delight in seeing and comprehending is the most beautiful gift of nature.
(A.Einstein)
1.
Life and work
1
Kurt Gödel was a solitary genius, whose work influenced all the subsequent developments in
mathematics and logic. The striking fundamental results in the decade 1929-1939 that made
Gödel famous are the completeness of the first-order predicate logic proof calculus, the
incompleteness of axiomatic theories containing arithmetic, and the consistency of the axiom
of choice and the continuum hypothesis with the other axioms of set theory. During the same
decade Gödel made other contributions to logic, including work on intuitionism and
computability, and later, under the influence of his friendship with Einstein, made a
fundamental contribution to the theory of space-time. In this article I am going to summarize
the most outstanding results on incompleteness and undecidability that changed the
fundamental views of modern mathematics.
Kurt Friedrich Gödel was born 28 April 1906, the second son of Rudolf and Marianne
(Handschuh) Gödel, in Brno, Pekařská 5,
2
in Moravia, at that time the Austrio-Hungarian
province, now a part of the Czech Republic. This region had a mixed population that was
predominantly Czech with a substantial German-speaking minority, to which Gödel’s parents
belonged. Following the religion of his mother rather than his “old-catholic” father, the
Gödels had Kurt baptized in the Lutheran church. In 1912, at the age of six, he was enrolled
in the Evangelische Volksschule, a Lutheran school in Brno. Gödel’s ethnic patrimony is
neither Czech nor Jewish, as is sometimes believed. His father Rudolf had come from Vienna
to work in Brno’s textile industry, while his mother’s family came from the Rhineland region
for the work in textiles. At the age of six or seven Kurt contracted rheumatic fever and,
despite eventual full recovery, he came to believe that he had suffered permanent heart
damage as a result. Here are the early signs of Gödel’s later preoccupation with his health.
From 1916 to 1924, Kurt carried on his school studies at the Deutsches Staats-
Realgymnasium (Grammar School), where he excelled particularly in mathematics, languages
and religion. Dr. Cyril Kubánek, professor of catholic religion, was Gödel’s professor of
philosophical propedeutics. Gödel probably obtained his interest in the philosophy of
Immanuel Kant at this stage, which appears to have prevented him from later fully accepting
the neo-positivist ideas of the Vienna circle. All the school register records testify to a great
intellectual talent
3
.
The World War I took place during Gödel’s school years; it appears to have had little
direct effect on him and his family. The collapse of the Austro-Hungarian empire at war’s end
together with absorption of Moravia, Bohemia and Slovakia into the new Czechoslovak
1
Sources: Feferman (1986), Dawson (1984), Malina-Novotný (1996), Archives of Brno
2
At that time also Brünn, Bäckergasse 5.
3
A rarity can be found, however, in these reports: the evaluation excellent (“sehr gut”) is stereotypically
repeated in the end of every year; the only lower evaluation was on the first semester report – in mathematics.
2
Republic in 1918 also little affected the Gödels. After the war, the family continued life much
as before, comfortably settled in the villa on Pellicova 8a in Brno.
Following his graduation from the Real-gymnasium in Brno in 1924, Gödel went to
Vienna to begin his studies at the University. He was influenced by the number-theorist
Philipp Furtwängler, but Professor Hans Hahn became Gödel’s principal teacher, a
mathematician of the new generation, interested in modern analysis and set-theoretic
topology, as well as logic, the foundations of mathematics and the philosophy of science. It
was Hahn who introduced Gödel to the group of philosophers around Moritz Schlick, which
was later known as the “Vienna Circle” and became identified with the philosophical doctrine
of logical positivism or logical empiricism
4
. Gödel attended meetings of the Circle quite
regularly in the period 1924-1928. But in the following years he gradually moved away from
it, though he maintained contact with some of its members, particularly with Rudolf Carnap.
The sphere of concerns of the Circle members must have influenced Gödel. He was
acquainted with Ernst Mach’s empiricist-positivist philosophy of science
5
and Bertrand
Russell’s logistic program, although he reports first studying the Principia Mathematica
several years later. It seems that the most direct influences on Gödel were Carnap’s lectures
on mathematical logic and the publication of Grundzűge der theoretischen Logik by David
Hilbert and Wilhelm Ackermann.
Hilbert posed as an open problem the question of whether there is a complete system of
axioms and derivation rules for the first-order predicate logic. In other words, whether using
the rules of the first-order system, it is possible to derive every logically valid statement.
Gödel arrived at a positive solution to this completeness problem in the summer of 1929. The
work became his doctoral dissertation and was published in a revised version in 1930. The
Completeness Theorem is now the most fundamental theorem of model theory and
mathematical proof theory.
Gödel’s personal life changed in 1927 when he met Adele Nimbursky, a dancer who had
been married before and was six years older than Kurt. Owing to the difference in their social
situation, the developing relationship led to objections from Kurt’s father. Although Kurt’s
father died not long after, Kurt and Adele were not to be married for another ten years. The
death of Kurt’s father in 1929 was unexpected; fortunately he left his family in comfortable
financial circumstances. Gödel’s mother retained the villa in Brno and took an apartment in
Vienna with her two sons. Three days after his father’s death, Kurt made an application
6
for
release from nationality obligations in Czechoslovakia. He was released on condition that he
would acquire state nationality in Austria within two years.
The ten years 1929–1939 were the most productive period in Gödel’s intense life in
mathematical logic, culminating in his greatest discoveries. It was the period of pursuit of
avoiding paradoxes and inconsistencies in mathematics that had destroyed Frege’s effort to
establish a formal proof system for mathematics at the end of the 19
th
Century. David Hilbert
(1862-1943), an outstanding German mathematician, put forward a new proposal for the
foundation of classical mathematics which has come to be known as Hilbert’s Program.
Pursuing Hilbert’s program, Gödel started to work on the consistency problem for
arithmetic and realized that the notion of provability can be formalized in arithmetic. He also
saw that non-paradoxical arguments analogous to the well-known Liar paradox in ordinary
language could be carried out by substituting the notion of provability for that of truth.
Surprisingly, these efforts eventually led him to a most unexpected result, his proof of
4
For a detailed discussion of Gödel’s relations to the Vienna circle, see Köhler (1991)
5
Max Plank’s lectures, 1907, the most brilliant exposition of relativity of the period.
6
Source: Archiv Brno, Certificate of domicile dated Feb 26, 1929.