Godel's Incompleteness Theorems

💡 The Core Insight

Any formal system powerful enough to express arithmetic is either incomplete (contains true but unprovable statements) or inconsistent (can prove contradictions). Moreover, no such system can prove its own consistency—self-verification is impossible for sufficiently expressive mathematical systems.

Definition

Gödel's Incompleteness Theorems: Let $T$ be a recursively axiomatizable formal theory in a first-order language $\mathcal{L}$ containing the language of arithmetic $\mathcal{L}_A = \{0, S, +, \cdot, <\}$ . We say $T$ represents arithmetic if it contains Peano arithmetic (PA) or a subsystem capable of expressing all primitive recursive functions. A formula $\varphi$ is decidable in $T$ if either $T \vdash \varphi$ or $T \vdash \neg\varphi$ . The theory $T$ is:

Consistent if there is no formula $\varphi$ such that both $T \vdash \varphi$ and $T \vdash \neg\varphi$
Complete if every sentence $\varphi$ in $\mathcal{L}$ is decidable in $T$
$\omega$ -consistent if for any formula $\varphi(x)$ , if $T \vdash \varphi(\overline{n})$ for all $n \in \mathbb{N}$ , then $T \nvdash \exists x\, \neg\varphi(x)$

Here $\overline{n}$ denotes the numeral representing $n$ (i.e., $S(S(\cdots S(0)\cdots))$ with $n$ applications of the successor function $S$ ).

TheoremGödel's Incompleteness Theorems

First Incompleteness Theorem [1]: Let $T$ be a consistent, recursively axiomatizable theory that represents arithmetic. Then there exists a sentence $G_T$ in the language of $T$ such that: 1. $T \nvdash G_T$ and $T \nvdash \neg G_T$ (i.e., $G_T$ is undecidable in $T$ ) 2. If $T$ is $\omega$ -consistent, then $G_T$ is true in the standard model $\mathbb{N}$

Second Incompleteness Theorem [2]: Let $T$ be a consistent, recursively axiomatizable theory that represents arithmetic and contains a certain minimal amount of proof theory (sufficient to formalize basic properties of provability). Let $\text{Con}(T)$ be a sentence expressing "T is consistent" (formalized as $\neg\text{Prov}_T(\ulcorner 0=1\urcorner)$ where $\text{Prov}_T$ is the provability predicate for $T$ ). Then:

T \nvdash \text{Con}(T)

Proof

We prove the First Incompleteness Theorem. The proof proceeds in several stages.

Stage 1: Gödel Numbering We establish an effective coding of syntactic objects as natural numbers. Define a Gödel numbering $\ulcorner \cdot \urcorner : \text{Formulas} \to \mathbb{N}$ that assigns to each symbol, term, formula, and finite sequence of formulas a unique natural number. For example:

Assign prime numbers to basic symbols: $\ulcorner 0 \urcorner = 2$ , $\ulcorner S \urcorner = 3$ , $\ulcorner + \urcorner = 5$ , etc.
For a sequence $(a_1, \ldots, a_n)$ , use $\ulcorner (a_1, \ldots, a_n) \urcorner = 2^{a_1} \cdot 3^{a_2} \cdots p_n^{a_n}$ where $p_i$ is the $i$ -th prime

This encoding is primitive recursive, meaning both the encoding and decoding functions are computable.

Stage 2: Representability of Syntactic Notions Since $T$ represents arithmetic, it can express primitive recursive relations. In particular, there exists a formula $\text{Proof}_T(x, y)$ in the language of $T$ such that for any formula $\varphi$ and sequence of formulas $\pi$ :

\pi \text{ is a proof of } \varphi \text{ in } T \iff \mathbb{N} \models \text{Proof}_T(\ulcorner \pi \urcorner, \ulcorner \varphi \urcorner)

Define the provability predicate:

\text{Prov}_T(y) := \exists x\, \text{Proof}_T(x, y)

By the representability theorem, for any formula $\varphi$ :

If $T \vdash \varphi$ , then $T \vdash \text{Prov}_T(\ulcorner \varphi \urcorner)$

Stage 3: The Diagonal Lemma This is the technical heart of the proof. For any formula $\psi(x)$ with one free variable, there exists a sentence $\delta$ such that:

T \vdash \delta \leftrightarrow \psi(\ulcorner \delta \urcorner)

To construct $\delta$ , define the diagonalization function $\text{diag}(x)$ which maps $\ulcorner \varphi(x) \urcorner$ to $\ulcorner \varphi(\overline{\ulcorner \varphi(x) \urcorner}) \urcorner$ . Let $D(x, y)$ represent this function in $T$ . Consider:

\theta(x) := \psi(z) \text{ where } D(x, z)

Now set $\delta := \theta(\ulcorner \theta \urcorner)$ . By construction and the properties of $D$ :

\delta = \psi(\ulcorner \theta(\overline{\ulcorner \theta \urcorner}) \urcorner) = \psi(\ulcorner \delta \urcorner)

Stage 4: The Gödel Sentence Apply the Diagonal Lemma to $\psi(y) := \neg\text{Prov}_T(y)$ . This yields a sentence $G_T$ such that:

T \vdash G_T \leftrightarrow \neg\text{Prov}_T(\ulcorner G_T \urcorner)

The sentence $G_T$ "says of itself" that it is not provable in $T$ .

Stage 5: $G_T$ is Undecidable Suppose $T \vdash G_T$ . Then by representability of provability, $T \vdash \text{Prov}_T(\ulcorner G_T \urcorner)$ . But $T \vdash G_T \leftrightarrow \neg\text{Prov}_T(\ulcorner G_T \urcorner)$ , so $T \vdash \neg G_T$ . This contradicts consistency of $T$ . Therefore $T \nvdash G_T$ . Now suppose $T \vdash \neg G_T$ . Then $T \vdash \text{Prov}_T(\ulcorner G_T \urcorner)$ by the biconditional. But if $T$ is $\omega$ -consistent, since $T \nvdash G_T$ , there is no proof of $G_T$ , so for all $n \in \mathbb{N}$ , $\mathbb{N} \models \neg\text{Proof}_T(\overline{n}, \ulcorner G_T \urcorner)$ . By representability, $T \vdash \neg\text{Proof}_T(\overline{n}, \ulcorner G_T \urcorner)$ for all $n$ . But $\omega$ -consistency then implies $T \nvdash \exists x\, \text{Proof}_T(x, \ulcorner G_T \urcorner)$ , i.e., $T \nvdash \text{Prov}_T(\ulcorner G_T \urcorner)$ , contradicting our assumption. Therefore $T \nvdash \neg G_T$ .

Stage 6: Truth of $G_T$ Assuming $\omega$ -consistency, we've shown $T \nvdash G_T$ . This means there is no proof of $G_T$ in $T$ , so $\mathbb{N} \models \neg\text{Prov}_T(\ulcorner G_T \urcorner)$ . But $G_T \leftrightarrow \neg\text{Prov}_T(\ulcorner G_T \urcorner)$ holds in $\mathbb{N}$ (since the biconditional is provable in $T$ and $T$ is sound for arithmetic). Therefore $\mathbb{N} \models G_T$ . This completes the proof of the First Incompleteness Theorem. □

∎

⚠️ Common mistake

Common Misconception: Gödel's theorems do NOT say "there are true statements that cannot be proven" in an absolute sense. The Gödel sentence $G_T$ is unprovable in the specific system $T$ , but may well be provable in a stronger system $T'$ . What the theorems establish is that no single formal system can capture all arithmetical truths—there is no "final" complete axiomatization. The undecidability is always relative to a particular formal system. Additionally, the Second Incompleteness Theorem requires that $T$ can formalize enough of its own proof theory (the "Hilbert-Bernays-Löb derivability conditions"). Not every theory satisfying the First Theorem necessarily satisfies the Second.

mathematician

Kurt Gödel (1931) — Proved both incompleteness theorems in his paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I," revolutionizing mathematical logic and ending Hilbert's program for a complete and consistent foundation of mathematics.

visualization

Example1

The Gödel Sentence for Peano Arithmetic Let $T = \text{PA}$ , Peano arithmetic with axioms including the induction schema. We construct the explicit Gödel sentence $G_{\text{PA}}$ . First, we establish a Gödel numbering. Assign:

Variables $v_0, v_1, v_2, \ldots$ the codes $2^{2 \cdot 0 + 1}, 2^{2 \cdot 1 + 1}, 2^{2 \cdot 2 + 1}, \ldots$
Logical symbols: $\ulcorner \neg \urcorner = 3$ , $\ulcorner \to \urcorner = 5$ , $\ulcorner \forall \urcorner = 7$
Arithmetic symbols: $\ulcorner 0 \urcorner = 11$ , $\ulcorner S \urcorner = 13$ , $\ulcorner + \urcorner = 15$ , $\ulcorner \cdot \urcorner = 17$ , $\ulcorner = \urcorner = 19$

For a formula like $\forall v_0 (v_0 + 0 = v_0)$ , its Gödel number is computed using the sequence encoding. The provability predicate $\text{Prov}_{\text{PA}}(y)$ can be written explicitly as a $\Sigma_1$ formula:

\text{Prov}_{\text{PA}}(y) = \exists x\, (\text{IsProof}(x) \land \text{Concludes}(x, y))

where $\text{IsProof}(x)$ checks that $x$ codes a valid sequence of formulas each following from previous ones by PA axioms and inference rules, and $\text{Concludes}(x, y)$ checks that the last formula in the sequence coded by $x$ is the formula coded by $y$ . The Diagonal Lemma produces $G_{\text{PA}}$ such that:

\text{PA} \vdash G_{\text{PA}} \leftrightarrow \neg\text{Prov}_{\text{PA}}(\overline{\ulcorner G_{\text{PA}} \urcorner})

Explicitly, $G_{\text{PA}}$ is a $\Pi_1$ sentence (of the form $\forall x\, \psi(x)$ for some bounded formula $\psi$ ). While we cannot write out the millions of symbols in $G_{\text{PA}}$ explicitly, its structural form is determined: it asserts that no number codes a proof of itself. By the First Incompleteness Theorem, $\text{PA} \nvdash G_{\text{PA}}$ and $\text{PA} \nvdash \neg G_{\text{PA}}$ , yet $G_{\text{PA}}$ is true in $\mathbb{N}$ .

Example2

The Rosser Sentence: Weakening $\omega$ -Consistency to Consistency The original Gödel sentence requires $\omega$ -consistency to conclude truth. J. B. Rosser (1936) refined the construction to need only consistency. Define a modified provability notion:

\text{Prov}^R_T(y) := \exists x\, [\text{Proof}_T(x, y) \land \forall z < x\, \neg\text{Proof}_T(z, \ulcorner\neg y\urcorner)]

This says " $y$ is provable and its proof comes before any proof of $\neg y$ ." By the Diagonal Lemma, construct $R_T$ such that:

T \vdash R_T \leftrightarrow \neg\text{Prov}^R_T(\ulcorner R_T \urcorner)

Claim: If $T$ is consistent, then $T \nvdash R_T$ and $T \nvdash \neg R_T$ . Proof of claim: Suppose $T \vdash R_T$ . Let $\pi$ be a proof with Gödel number $p$ . Then $\mathbb{N} \models \text{Proof}_T(\overline{p}, \ulcorner R_T \urcorner)$ . If $T \vdash \neg R_T$ via some proof with number $q$ , and $q < p$ , then $\mathbb{N} \models \text{Proof}_T(\overline{q}, \ulcorner\neg R_T\urcorner) \land q < p$ , so $\mathbb{N} \models \neg\text{Prov}^R_T(\ulcorner R_T \urcorner)$ . But the equivalence gives $\mathbb{N} \models R_T \leftrightarrow \neg\text{Prov}^R_T(\ulcorner R_T \urcorner)$ , and we assumed $T \vdash R_T$ , so $\mathbb{N} \models R_T$ , contradiction. If $q > p$ (or no such $q$ exists), then $\mathbb{N} \models \text{Prov}^R_T(\ulcorner R_T \urcorner)$ , so $\mathbb{N} \models \neg R_T$ , contradicting $\mathbb{N} \models R_T$ . Similarly, if $T \vdash \neg R_T$ via proof number $q$ , then by the equivalence, $T \vdash \text{Prov}^R_T(\ulcorner R_T \urcorner)$ , meaning some proof of $R_T$ exists with number $p < q$ , contradicting consistency. The Rosser sentence thus gives undecidability from consistency alone.

Counterexample

Why Recursive Axiomatizability is Necessary Consider the theory $T_{\text{true}} = \{\varphi : \mathbb{N} \models \varphi\}$ , the set of all true sentences of arithmetic. This theory is:

Complete: Every sentence is decidable (either true or false)
Consistent: No contradiction is true in $\mathbb{N}$
Represents arithmetic: Contains all of PA

This appears to violate the First Incompleteness Theorem! The resolution: $T_{\text{true}}$ is not recursively axiomatizable. There is no computable procedure to enumerate its axioms. By Tarski's Undefinability Theorem, the set of Gödel numbers of true arithmetic sentences is not arithmetically definable, hence not recursively enumerable. Without recursive axiomatizability, we cannot effectively construct the provability predicate $\text{Prov}_T(y)$ needed for the diagonal argument. The hypothesis is essential: only theories with algorithmically recognizable proofs are subject to incompleteness. Similarly, Presburger arithmetic (arithmetic with only addition, no multiplication) is complete and consistent, but this is possible because it cannot represent all primitive recursive functions—it lacks the expressive power needed for Gödel's construction.

🧠 Intuition

The Liar Paradox Made Precise Gödel's construction is a formalization of the liar paradox. Consider the sentence "This sentence is false." If it's true, then it's false; if it's false, then it's true—contradiction. Gödel's genius was to replace "false" with "unprovable in $T$ ," yielding "This sentence is unprovable in $T$ ." This is not paradoxical but merely undecidable:

If provable, then (by soundness) true, so it says something true about itself (being unprovable), contradiction
If disprovable, then provably false, but it says it's unprovable—inconsistency
If unprovable, then it's true about itself, but we can't prove it in $T$

The self-reference is achieved not through vague linguistic tricks but through the rigorous mechanism of Gödel numbering, allowing formulas to "talk about" their own syntactic structure by arithmetic means. Think of it as giving each formula a social security number, then writing formulas that compute with these numbers to refer back to themselves. Visually: imagine a computer program that contains its own source code as a string and checks whether that source code halts. The program has "self-knowledge" through encoding. Gödel sentences have mathematical self-knowledge through arithmetic encoding of syntax.

connection

Computability Theory and the Halting Problem The First Incompleteness Theorem is intimately connected to Turing's Halting Problem. A theory $T$ is complete and consistent iff the set $\{n : T \vdash \varphi_n\}$ (where $\varphi_n$ is the $n$ -th formula) is decidable. But Gödel's theorem shows this set is undecidable for theories representing arithmetic. More precisely, by the MRDP theorem (Matiyasevich-Robinson-Davis-Putnam), every recursively enumerable set is Diophantine. Thus the halting set $K = \{e : \varphi_e(e) \downarrow\}$ can be represented by a polynomial Diophantine equation. If PA were complete, we could decide whether this equation has solutions, solving the halting problem—contradiction. This connection runs deep: both incompleteness and uncomputability stem from diagonalization. The Gödel sentence uses logical diagonalization; the halting problem uses computational diagonalization. Both show inherent limitations of formal methods through self-referential constructions. This unity was recognized early: Church, Turing, and Kleene all worked on both foundations of logic and computation in the 1930s, seeing them as aspects of the same mathematical phenomenon.

Gödel's Incompleteness Theorems

Overview

Core Theory

Examples and Applications

Historical Development

Connections to Other Areas

What You Need First

What This Opens Up

See Also