Kurt Gödel

How to use this course

Kurt Gödel published little, and almost every paper changed its field. At 23 he proved that first-order logic is complete. At 24 he proved that arithmetic is not, and that no consistent system of its kind can prove its own consistency. In his thirties he showed that the axiom of choice and the continuum hypothesis cannot be refuted from the usual axioms of set theory. Later he found a solution of Einstein’s equations in which time travel is possible in principle. This course presents these results with full statements and proof sketches, alongside the story of a life spent between Vienna and Princeton.

Each technical lesson opens with a paragraph for the general reader, then gives precise statements, proof sketches and exercises with folded solutions. Lessons 04–07 form a sequence and should be read in order; Lessons 08, 09 and 10 can be read independently.

Timeline

Brünn, 1906–1924

Kurt Friedrich Gödel was born on 28 April 1906 in Brünn, the capital of Moravia in the Austro-Hungarian Empire. His father, Rudolf Gödel, was managing director and part owner of a textile firm; his mother, Marianne Handschuh, came from a family also connected with the textile trade. The family was German-speaking and comfortable. Kurt had one elder brother, Rudolf, who became a radiologist in Vienna.

As a child he was so curious that his family called him “Herr Warum”, Mr Why. A childhood bout of rheumatic fever left him with a lasting conviction that his heart was weak, an early instance of the worries about his health that followed him through life. He attended the Evangelische Volksschule from 1912 and the German-language Staats-Realgymnasium from 1916 to 1924, where he was an outstanding pupil, strongest in mathematics and languages.

When the empire collapsed in 1918, Brünn became part of the new state of Czechoslovakia and Gödel automatically became a Czechoslovak citizen. In 1924 he left for Vienna to study at the university.

Vienna and the Circle, 1924–1931

Gödel entered the University of Vienna intending to study physics. The lectures of the number theorist Philipp Furtwängler drew him to mathematics. In 1926 he began attending the Thursday meetings of the Vienna Circle, the group of philosophers and scientists around Moritz Schlick that included Rudolf Carnap, Hans Hahn, Otto Neurath and the young Karl Menger. He took part in discussions of Wittgenstein’s Tractatus and of logic, but he did not share the Circle’s positivism. He was already a Platonist, convinced that mathematical objects exist independently of us.

In 1928 he heard L. E. J. Brouwer lecture in Vienna on the foundations of mathematics, and in the same year he read the new textbook of David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik. It posed as an open problem whether every logically valid formula of first-order logic is provable. Gödel answered yes in his dissertation, written under Hans Hahn and completed in 1929. He received his doctorate in 1930 (Lesson 04). In 1929 he also gave up Czechoslovak citizenship for Austrian.

Hilbert had a larger goal: to prove by finitary means that classical mathematics is consistent. Gödel set out to contribute to this programme by proving the consistency of analysis relative to arithmetic. Instead he found that in any suitable formal system there are true arithmetical statements that cannot be proved.

He announced the result almost in passing at a conference on the epistemology of the exact sciences in Königsberg, on 7 September 1930, during a discussion with Carnap, Arend Heyting and John von Neumann. Von Neumann understood it at once. In November 1930 he wrote to Gödel that he had derived a corollary: the consistency of arithmetic cannot be proved in arithmetic. Gödel had already found this second theorem himself. The paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” was received by the Monatshefte für Mathematik und Physik on 17 November 1930 and appeared in volume 38 in 1931. The promised part II never appeared; part I was accepted as complete.

Between Vienna and Princeton, 1931–1940

The 1931 paper served as his habilitation thesis, accepted in 1932, and in March 1933 he became a Privatdozent at Vienna, with the right to lecture but no salary. He was soon invited to the new Institute for Advanced Study in Princeton, where he spent the academic year 1933–34 and gave lectures in the spring of 1934 on his incompleteness results. The notes, taken by Stephen Kleene and J. Barkley Rosser, introduced the Herbrand–Gödel definition of general recursive functions.

The years that followed were hard. On the return from the United States in 1934 he suffered a breakdown and spent time in a sanatorium. He returned to the IAS in the autumn of 1935, but depression cut the visit short. In June 1936 Moritz Schlick was shot dead on the steps of the University of Vienna by a former student, and Gödel suffered a further crisis. Through these years he nevertheless did his deepest work in set theory: by 1935 he had proved that the axiom of choice is consistent with the other axioms, and by 1937 that the generalized continuum hypothesis is as well (Lesson 08).

In September 1938 he married Adele Nimbursky, born Porkert, a divorcée six years older than he was, whom he had known since the late 1920s despite his family’s objections. The political situation was closing in. After the annexation of Austria in March 1938 he became a German citizen; the Privatdozent title was abolished, and his application for the new position of Dozent was delayed because of his past associations with Jewish members of the Vienna Circle. In 1939, now liable to be called up for military service, he was attacked in the street by young men who took him for a Jew. He spent the autumn of 1938 at the IAS and the spring of 1939 at the University of Notre Dame, then returned to Vienna.

Exit visas were finally arranged. Since the Atlantic route was too dangerous, Kurt and Adele Gödel left Vienna in January 1940, crossed Russia on the Trans-Siberian railway, sailed from Japan and reached San Francisco on 4 March 1940. They went on to Princeton, where he would spend the rest of his life.

The completeness theorem

For the general reader. Logic has two notions of consequence. A statement follows semantically from axioms if it is true in every situation where the axioms are true. It follows syntactically if there is a written proof using fixed rules. Gödel’s first great theorem says that for first-order logic the two notions coincide: whatever is true in all models can be proved.

Gödel proved the theorem for countable languages and finite or countable \(T\), using a reduction of formulas to a prenex normal form due to Thoralf Skolem. The proof now taught is Leon Henkin’s from 1949.

Henkin’s proof, in outline

1. Add new constants \(c_\varphi\) and axioms \(\exists x\,\varphi(x)\to\varphi(c_\varphi)\) for every formula \(\varphi(x)\), iterating so that the extended language is covered. The result is still consistent.
2. Extend to a maximal consistent set \(T^*\) (by enumerating sentences, or by Zorn’s lemma for uncountable languages).
3. Build a model whose elements are closed terms modulo the relation \(s\sim t\iff (s=t)\in T^*\). Declare an atomic sentence true iff it lies in \(T^*\).
4. Prove by induction on formulas that a sentence is true in this model iff it lies in \(T^*\). The witnesses \(c_\varphi\) handle the existential step.

Indeed, a proof of a contradiction from \(T\) uses only finitely many axioms. Gödel stated compactness for countable languages in his 1930 paper; Anatoly Maltsev extended it to arbitrary languages in 1936. Together with the downward Löwenheim–Skolem theorem, it shows that first-order axioms cannot pin down infinite structures up to isomorphism.

Arithmetization: numbers that talk about formulas

For the general reader. Gödel’s key technical idea was to give every symbol, formula and proof a code number. Statements about formulas, such as “this sequence of formulas is a proof of that one”, then become statements about numbers, and those can be written inside arithmetic itself. Arithmetic acquires the ability to talk about its own proofs.

Gödel numbering

Assign positive integers to the basic symbols. A string \(s_1s_2\cdots s_k\) gets the code \(\ulcorner s_1\cdots s_k\urcorner=2^{\#s_1}3^{\#s_2}\cdots p_k^{\#s_k}\), with \(p_k\) the \(k\)-th prime. A sequence of formulas, such as a proof, is coded the same way from the codes of its members. By unique factorization the code determines the string.

Primitive recursion

The primitive recursive functions are the smallest class containing zero, successor and projections, and closed under composition and under definition by recursion: \(h(\vec x,0)=f(\vec x)\), \(h(\vec x,y+1)=g(\vec x,y,h(\vec x,y))\). Gödel, who called them simply recursive, defined a chain of 46 functions and relations ending with the relation “\(x\) is the code of a proof of the formula with code \(y\)”. All but the last are primitive recursive.

The hard step is recursion, which needs to quantify over finite sequences using only \(+\) and \(\cdot\). Gödel’s solution is the function

In the 1934 Princeton lectures Gödel widened the class, following a suggestion of Jacques Herbrand, to the general recursive functions. After work of Alonzo Church, Kleene and Alan Turing, these were recognised as exactly the computable functions, and Gödel came to accept Turing’s analysis as the definitive one.

The first incompleteness theorem

For the general reader. Using code numbers, Gödel wrote down an arithmetical sentence that says, in effect, “I am not provable.” If the system proved it, the system would prove something false. So, if the system proves only truths, the sentence is unprovable, and therefore true. Every reasonable system for arithmetic leaves some true statement unproved, and adding it as a new axiom just produces a new one.

Proof. Let \(d\) be the primitive recursive function sending the code of a formula \(\chi(x)\) to the code of \(\chi(\underline{\ulcorner\chi\urcorner})\), and represent it by a formula \(D(x,y)\). Let \(\chi(x)\equiv\exists y\,(D(x,y)\wedge\psi(y))\), and \(\gamma\equiv\chi(\underline{\ulcorner\chi\urcorner})\). Then \(d(\ulcorner\chi\urcorner)=\ulcorner\gamma\urcorner\), and \(\gamma\) says that \(\psi\) holds of \(d(\ulcorner\chi\urcorner)\), which \(\mathsf{PA}\) can verify is \(\ulcorner\gamma\urcorner\).

Here \(T\) is \(\omega\)-consistent if there is no formula \(\varphi(x)\) with \(T\vdash\exists x\,\varphi(x)\) and \(T\vdash\neg\varphi(\underline n)\) for every \(n\). Gödel’s 1931 paper used the system P, a version of the simple type theory of Principia Mathematica over the natural numbers, and remarked that the argument applies to any system strong enough for arithmetic.

Proof. (1) If \(T\vdash G\), let \(p\) code the proof. Then \(\mathrm{Prf}_T(p,\ulcorner G\urcorner)\) is true, so by representability \(T\vdash\mathrm{Prf}_T(\underline p,\underline{\ulcorner G\urcorner})\), hence \(T\vdash\mathrm{Prov}_T(\underline{\ulcorner G\urcorner})\) and \(T\vdash\neg G\). So \(T\) is inconsistent. (2) If \(T\vdash\neg G\), then \(T\vdash\exists x\,\mathrm{Prf}_T(x,\underline{\ulcorner G\urcorner})\). By (1), no \(n\) codes a proof of \(G\), so \(T\vdash\neg\mathrm{Prf}_T(\underline n,\underline{\ulcorner G\urcorner})\) for each \(n\), violating \(\omega\)-consistency.

The second theorem and Hilbert’s programme

For the general reader. Hilbert hoped to secure all of mathematics by proving, with elementary methods, that its axioms never lead to a contradiction. Gödel’s second theorem shows that a consistent system cannot prove its own consistency. Elementary methods, which can be formalized inside the system, are therefore not enough.

Write \(\Box\sigma\) for \(\mathrm{Prov}_T(\underline{\ulcorner\sigma\urcorner})\) and \(\mathrm{Con}_T\) for \(\neg\Box(0=1)\). Gödel sketched the second theorem in 1931. Full proofs came from Hilbert and Paul Bernays in Grundlagen der Mathematik II (1939), and Martin Löb isolated the needed properties in 1955.

Proof. Part (1) of the first theorem says \(\mathrm{Con}_T\to\neg\Box G\). Its proof uses only the derivability conditions, so it can be carried out in \(T\): \(T\vdash\mathrm{Con}_T\to\neg\Box G\). Since \(T\vdash G\leftrightarrow\neg\Box G\), we get \(T\vdash\mathrm{Con}_T\to G\). If \(T\vdash\mathrm{Con}_T\), then \(T\vdash G\), contradicting the first theorem.

After Gödel

Hilbert’s programme in its original form was over, but its spirit survived. In 1936 Gerhard Gentzen proved the consistency of \(\mathsf{PA}\) using transfinite induction up to the ordinal \(\varepsilon_0=\sup\{\omega,\omega^\omega,\omega^{\omega^\omega},\dots\}\), a principle that is not provable in \(\mathsf{PA}\) but is arguably constructive. This began ordinal analysis. In 1977 Jeff Paris and Leo Harrington found the first natural combinatorial statement, a strengthening of Ramsey’s theorem, that is true but unprovable in \(\mathsf{PA}\).

Constructible sets: choice and the continuum

For the general reader. Georg Cantor asked whether there is an infinite size strictly between the whole numbers and the real numbers. Hilbert put this first on his famous list of problems in 1900. Gödel showed that the usual axioms of set theory cannot rule out Cantor’s guess that there is none. He built a slim inner universe of sets, each constructed in stages by explicit definitions, and showed that Cantor’s hypothesis holds there.

The hierarchy

For a set \(X\), let \(\mathrm{Def}(X)\) be the set of subsets of \(X\) definable in the structure \((X,\in)\) by a first-order formula with parameters from \(X\). Define by transfinite recursion

Choice. Each element of \(L\) appears first at some stage \(L_{\alpha+1}\) and is defined there by a formula with parameters. Order elements by stage, then by the code of the formula, then (recursively) by the parameters. This is a well-ordering of \(L\) definable in \(L\).

GCH. Assume \(V=L\) and let \(A\subseteq\omega_\alpha\). Then \(A\in L_\delta\) for some \(\delta\). Take an elementary substructure \(X\prec L_\delta\) (for suitable limit \(\delta\)) with \(\omega_\alpha\cup\{A\}\subseteq X\) and \(|X|=\aleph_\alpha\). Its collapse is some \(L_\beta\) with \(|\beta|=\aleph_\alpha\), so \(\beta<\omega_{\alpha+1}\). The collapse fixes every element of \(\omega_\alpha\), hence fixes \(A\). So every subset of \(\omega_\alpha\) lies in \(L_{\omega_{\alpha+1}}\), a set of size \(\aleph_{\alpha+1}\), and \(2^{\aleph_\alpha}\le\aleph_{\alpha+1}\).

Gödel believed that the continuum hypothesis is in fact false, and that \(V=L\) is not a true axiom. In 1963 Paul Cohen invented forcing and proved that \(\mathsf{ZF}\) is consistent with the negation of the axiom of choice, and \(\mathsf{ZFC}\) with the negation of the continuum hypothesis. Together the two results show that \(\mathsf{CH}\) is independent of \(\mathsf{ZFC}\).

Intuitionism, translations and Dialectica

For the general reader. Brouwer’s intuitionists rejected the law of excluded middle, and Hilbert’s formalists feared that intuitionism would cripple mathematics. Gödel found exact bridges between the two camps. He showed that classical arithmetic can be translated into intuitionistic arithmetic, so it is no less safe, and later gave a new kind of consistency proof based on computable functions of higher type.

In 1933 Gödel also interpreted intuitionistic propositional logic in the modal logic \(\mathsf{S4}\), reading “\(A\) is intuitionistically true” as “\(A\) is provable”, by prefixing \(\Box\) to subformulas.

The Dialectica interpretation (1958)

Published in the Swiss journal Dialectica, but based on ideas Gödel had developed since the early 1940s, this interpretation assigns to each formula \(A\) of \(\mathsf{HA}\) a quantifier-free formula \(A_D(x,y)\) of a system \(\mathsf T\) of primitive recursive functionals of finite type, so that \(A\) is interpreted as \(\exists x\,\forall y\,A_D(x,y)\). The key clause is implication: \((A\to B)^D\) asks for functionals transforming a witness for \(A\) into a witness for \(B\), and a counterexample for \(B\) into a counterexample for \(A\).

The functionals of \(\mathsf T\) are exactly those definable in a typed \(\lambda\)-calculus with recursion, and Gödel’s system \(\mathsf T\) became a prototype for typed programming languages. Ulrich Kohlenbach’s proof mining uses refinements of the interpretation to extract explicit bounds from classical proofs in analysis.

A rotating universe

For the general reader. Gödel’s daily walks with Einstein in Princeton turned his attention to relativity. For Einstein’s seventieth birthday in 1949 he found a model universe, consistent with Einstein’s equations, in which matter rotates everywhere and a traveller could in principle journey into his own past. For Gödel the result supported an old philosophical view that the passage of time is not an objective feature of the world.

The spacetime is homogeneous: every point looks like every other. In cylindrical coordinates adapted to the rotation, it can be written

The light cones tilt over as \(r\) increases. Beyond the radius where \(\sinh r=1\), the circles \(t,r,y=\text{const}\) are timelike and closed. Through every point of the spacetime passes a closed timelike curve, so there is no global time function, and no consistent division of events into a universal past and future.

Gödel later studied expanding rotating models (1950) and asked whether the observed universe rotates. Measurements of the cosmic microwave background constrain any global rotation to be extremely small. His solution remains the standard example in discussions of causality, and in 1992 Stephen Hawking’s chronology protection conjecture proposed that physics forbids such curves from being created.

Princeton, 1940–1978

At the Institute for Advanced Study Gödel was an ordinary member on yearly appointments from 1940, a permanent member from 1946, and a professor from 1953 until he became emeritus in 1976. He had no teaching duties and no doctoral students. His influence passed through conversation and correspondence, with visitors such as Georg Kreisel, Paul Cohen and the logician-philosopher Hao Wang, who recorded many of his views.

His closest friend was Albert Einstein. The two walked home together from the Institute almost daily until Einstein’s death in 1955, talking about physics, philosophy and politics. Einstein reportedly said that he went to his office mainly for the privilege of walking home with Gödel. When Gödel took his United States citizenship examination on 5 December 1947, Einstein and the economist Oskar Morgenstern accompanied him; according to Morgenstern’s account, Gödel had found what he thought was a logical flaw in the Constitution and the two had to steer him away from explaining it to the judge. He became a citizen in 1948.

His work turned increasingly to philosophy. He wrote on Bertrand Russell’s logic (1944), on Cantor’s continuum problem (1947, revised 1964), and on the relation between relativity and idealist philosophy (1949). In his 1951 Gibbs Lecture to the American Mathematical Society he argued that either the human mind infinitely surpasses any machine, or there are absolutely undecidable mathematical problems. He studied Leibniz and Husserl, and in the early 1970s circulated a modal-logic version of the ontological argument for the existence of God. Honours came steadily: the first Albert Einstein Award in 1951, shared with Julian Schwinger; honorary degrees from Yale and Harvard in 1951 and Amherst in 1952; membership of the National Academy of Sciences; Foreign Membership of the Royal Society in 1968; and the National Medal of Science in 1974. He declined honours from Austria.

His fears about his health and about being poisoned grew with age. He would eat only food prepared by his wife. When Adele was hospitalized in late 1977, he stopped eating. He died in Princeton Hospital on 14 January 1978, aged 71; the death certificate recorded malnutrition and inanition caused by a personality disturbance. Adele died in 1981 and left his papers to the Institute.

Legacy

Gödel’s collected works fill five volumes, of which the published papers occupy only two. Yet his results define the boundaries of the formal method.

• Logic and foundations: completeness and compactness are the starting point of model theory. Incompleteness ended the hope of a single complete formal basis for mathematics and created proof theory as a study of what systems can and cannot prove.
• Computability: arithmetization and recursive functions led directly to the work of Church, Kleene and Turing, and through Turing to theoretical computer science. Gödel’s 1956 letter to von Neumann asked, in effect, the P versus NP question. The Gödel Prize for theoretical computer science, established in 1993, bears his name.
• Set theory: the constructible universe began inner model theory, and with Cohen’s forcing it framed modern set theory, including the search for new axioms that Gödel advocated.
• Physics and philosophy: the Gödel universe is the standard example of a spacetime with closed timelike curves; his Platonism and his views on mind and machine remain live positions.
• Commemoration: the Association for Symbolic Logic has held an annual Gödel Lecture since 1990, and the Kurt Gödel Society was founded in Vienna in 1987.

Sources and further reading

Biography

1. J. J. O’Connor and E. F. Robertson, Kurt Gödel, MacTutor History of Mathematics.
2. Kurt Gödel, Wikipedia.
3. J. Kennedy, Kurt Gödel, Stanford Encyclopedia of Philosophy.
4. Second Conference on the Epistemology of the Exact Sciences (Königsberg, 1930), Wikipedia.
5. J. W. Dawson Jr., Logical Dilemmas: The Life and Work of Kurt Gödel, A K Peters, 1997.
6. H. Wang, Reflections on Kurt Gödel, MIT Press, 1987.

Mathematics

1. K. Gödel, Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatsh. Math. Phys. 37 (1930).
2. K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatsh. Math. Phys. 38 (1931).
3. K. Gödel, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory, Princeton, 1940.
4. K. Gödel, An example of a new type of cosmological solutions of Einstein’s field equations of gravitation, Rev. Mod. Phys. 21 (1949).
5. K. Gödel, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica 12 (1958).
6. K. Gödel, Collected Works, 5 vols., ed. S. Feferman et al., Oxford University Press, 1986–2003.
7. P. Smith, An Introduction to Gödel’s Theorems, 2nd ed., Cambridge, 2013.
8. T. Jech, Set Theory, 3rd millennium ed., Springer, 2003 (chapter 13 on \(L\)).
9. S. W. Hawking and G. F. R. Ellis, The Large Scale Structure of Space-Time, Cambridge, 1973 (section 5.7 on the Gödel universe).
10. P. Raatikainen, Gödel’s Incompleteness Theorems, Stanford Encyclopedia of Philosophy.