The History of AI

The incompleteness theorems

Era 1 · The foundations (1763–1942) › Logic and the foundations of mathematics

Lineage
Symbols and logic
Kind
Publication

Who

University of Vienna

What happened

Kurt Gödel publishes "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" in Monatshefte für Mathematik und Physik (vol. 38, pp. 173–198).

Why it mattered

Every consistent formal system capable of arithmetic contains statements it can neither prove nor refute, and it cannot prove its own consistency. The encoding of formulas as numbers opens the way for Church and Turing.

The full story

Kurt Gödel was 24 and working at the University of Vienna when, on September 7, 1930, at a conference in Königsberg, Gödel announced almost in passing, during a discussion, a result that changed logic. The paper reached the journal on November 17 and was published in 1931.

It contains two theorems. The first says that any consistent formal system capable of a minimum of arithmetic is incomplete: there are statements it can neither prove nor refute. The second says that such a system cannot prove its own consistency.

The technique matters as much as the result. Gödel assigns a number to every symbol, formula, and proof, so that talking about proofs becomes talking about numbers. With this encoding Gödel builds a statement that amounts to saying that it cannot itself be proved.

The second theorem struck at Hilbert's program, which was looking for exactly that proof of consistency, even though Gödel had begun working on the subject intending to contribute to it. John von Neumann, who was in Königsberg, grasped the reach of the result at once. The next day, in the same city, Hilbert closed an address with the words now on Hilbert's tombstone: "We must know. We will know." Between 1934 and 1936 Gödel, Church, and Turing each proposed, separately, exact definitions of what a computable function is, and they turned out to be equivalent.

Under the hood

The key technique is arithmetization. Gödel assigns a number to each symbol and combines those numbers, using powers of primes, into a single number for each formula and each proof. That way, "the sequence of formulas d proves the formula f" becomes a relation between two numbers that arithmetic itself can express.

With this Gödel builds a formula G that says, by way of its own number, "G is not provable." If the system is consistent, G cannot be proved; and if it is somewhat more than consistent, G cannot be refuted either. The second theorem applies the same argument to the formula that expresses "the system is consistent."

Common misconceptions

  • What people often say: Gödel proved that mathematics is contradictory, or that nothing can be known for certain.

    In fact: What Gödel proved is that a consistent formal system with arithmetic leaves some statements undecided and cannot prove its own consistency. Most of mathematics goes on being proved as usual.

  • What people often say: The incompleteness theorems say there are truths no method can reach.

    In fact: They are about a fixed formal system. A statement one system cannot decide can be proved in a stronger one, which will in turn have undecided statements of its own.

Videos

Builds on

  • Hilbert's 23 problems (August 8, 1900)

    Inherited, with no proven direct link

    The second problem asks for a proof that arithmetic is consistent; Gödel's second theorem shows it cannot be proved by arithmetic's own means

  • Principia Mathematica (1910)

    Documented direct influence

    The paper names Principia Mathematica in its title and takes its system as the case it studies

Leads to

  • On Computable Numbers (November 30, 1936)

    Documented direct influence

    Turing compares the paper's result with Gödel's theorem and explains how it differs (section 8)

  • Finite Combinatory Processes (September 1936)

    Documented direct influence

    From its first sentence the paper presents itself as a development in the line of Gödel's incompleteness theorem and Church's unsolvable problems

Threads that pass through here

Sources

How to cite

“The incompleteness theorems.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/godel-incompleteness

This entry was last reviewed on November 13, 2026.

Open in the interactive timeline