🪴 GoDeep
Search
← University Challenge
⚛️

Science · Mathematics

Gödel's incompleteness theorems

1931

Mathematics — logic and foundations

Two results published in 1931 by the Austrian logician Kurt Gödel that ended the programme of putting all of mathematics on a complete and provably consistent axiomatic footing. The first says that any consistent formal system rich enough to express ordinary arithmetic contains true statements it cannot prove. The second says that no such system can prove its own consistency. Gödel's method was to encode statements about proofs as statements about numbers, and then construct a sentence that in effect asserts its own unprovability.

How to spot them

  • ▸Any consistent system strong enough for arithmetic has true but unprovable statements
  • ▸No such system can prove its own consistency
  • ▸Published in 1931, wrecking Hilbert's formalist programme
  • ▸The trick is to number statements so that arithmetic can talk about itself
  • ▸Its author starved himself to death in 1978, fearing his food was poisoned

Key facts

A 1931 paper 'On formally undecidable propositions of Principia Mathematica and related systems' (1931)

The paper that ended Hilbert's programme

The numbering scheme that lets arithmetic make statements about its own proofs

Gödel numbering — each formula gets a unique integer code

A sentence that in effect asserts 'this statement cannot be proved'

The self-referential construction at the heart of the first theorem

The 1931 results that ended Hilbert's hope of proving arithmetic consistent from within (1931)

Hilbert's programme, announced in the 1920s and abandoned after these theorems

The 1979 Pulitzer-winning book that braided the logician with an artist and a composer (1979)

Douglas Hofstadter's Gödel, Escher, Bach: an Eternal Golden Braid

A logical loophole in the US Constitution, raised at a 1947 citizenship hearing with Einstein present (1947)

The famous Princeton anecdote; Einstein and Morgenstern steered the judge off the subject

A rotating-universe solution to Einstein's field equations allowing closed timelike curves (1949)

Presented as a birthday present to Einstein at Princeton — a universe in which time travel is possible

Einstein's companion on the daily walk home across the Princeton campus

Einstein said in later years that he came to the Institute chiefly for the privilege of walking home with him

Key ideas

  • The first theorem does not say mathematics is inconsistent or that some truths are unknowable in principle: it says no single consistent, effectively axiomatised system can capture all arithmetical truth.
  • The second theorem follows from the first: if a system could prove its own consistency, it could prove the Gödel sentence too, and so would be inconsistent.
  • The liar paradox — 'this sentence is false' — is the informal ancestor; Gödel replaced 'false' with 'unprovable', which can be expressed arithmetically.

Quick-fire facts

  • •Kurt Gödel (1906–1978) was born in Brünn, now Brno, and moved to the Institute for Advanced Study at Princeton in 1940
  • •The theorems were published in 1931 in Monatshefte für Mathematik, when he was 25
  • •They demolished David Hilbert's programme of proving mathematics complete and consistent by finitary means
  • •Gödel also proved the completeness theorem for first-order logic in his 1929 doctoral thesis — a different and positive result
  • •In 1940 he proved that the axiom of choice and the continuum hypothesis are consistent with the other axioms of set theory; Paul Cohen completed the independence result in 1963
  • •In 1949 he found a solution to Einstein's field equations describing a rotating universe with closed timelike curves, and gave it to Einstein for his seventieth birthday
  • •He claimed to have found a logical loophole in the US Constitution at his 1947 citizenship hearing; Einstein and Oskar Morgenstern accompanied him and steered the judge away from it
  • •He suffered from severe paranoia about poisoning and, after his wife Adele was hospitalised, refused to eat; he died of starvation in Princeton in 1978 weighing about 29 kg
  • •Douglas Hofstadter's Gödel, Escher, Bach won the 1980 Pulitzer Prize for General Non-Fiction
  • •Alan Turing's 1936 halting problem and Alonzo Church's work gave equivalent limitative results in computation
  • •Gödel also produced a formal version of the ontological argument for the existence of God

Drill it — 8 cards

1 / 8new card

Sources