Completeness and Incompleteness Theorems

⚡ Key Takeaways

Gödel's Completeness Theorem (1929): in first-order logic, a sentence is provable from a theory iff it is true in every model — syntax matches semantics. Gödel's Incompleteness Theorems (1931): any consistent, recursively axiomatizable theory extending elementary arithmetic (i) fails to prove some true arithmetic sentence (First) and (ii) cannot prove its own consistency (Second). Applies to all of formal mathematics built on first-order logic and arithmetic. Due to Kurt Gödel, Vienna, 1929–1931.

💡 The Core Insight

Completeness says: the proof system loses no information about validity. Incompleteness says: no single recursive theory captures all truths of arithmetic, because a theory able to talk about its own syntax can construct a sentence asserting its own unprovability. The bridge between syntax and semantics in one direction (completeness) is precisely what lets us reflect a theory's proof relation into arithmetic, enabling the self-reference that drives incompleteness.

DefinitionSyntactic and Semantic Consequence

Fix a first-order language $\mathcal{L}$ . Let $T$ be a set of $\mathcal{L}$ -sentences and $\varphi$ an $\mathcal{L}$ -sentence.

$T \vdash \varphi$ (" $\varphi$ is provable from $T$ ") means there is a finite formal derivation of $\varphi$ from $T$ using the axioms and rules of a sound, fixed deductive calculus (e.g. a Hilbert system or natural deduction).
$T \models \varphi$ (" $\varphi$ is a semantic consequence") means every $\mathcal{L}$ -structure $\mathcal{M}$ that satisfies all of $T$ also satisfies $\varphi$ :

1

\quad T \models \varphi \;\iff\; \forall \mathcal{M}\,\big( \mathcal{M} \models T \implies \mathcal{M} \models \varphi \big).

Derivation hint: this is the definition of the satisfaction relation $\models$ between structures and sentences, universally quantified over models of $T$ . Here $\mathcal{M} = (M, I)$ is a domain $M$ with interpretation $I$ of the symbols; $\mathcal{M} \models \varphi$ is defined by Tarski's recursion on formula structure.

TheoremGödel–Henkin Completeness Theorem

For any first-order theory $T$ and sentence $\varphi$ ,

2

\quad T \vdash \varphi \;\iff\; T \models \varphi.

Derivation hint: $(\Rightarrow)$ is soundness, proved by induction on derivation length; $(\Leftarrow)$ is the substantive direction, proved via the model existence theorem below. Equivalently (the Model Existence form): a theory $T$ is consistent iff it has a model.

3

\quad \mathrm{Con}(T) \;\iff\; \exists \mathcal{M}\,(\mathcal{M} \models T).

Derivation hint: take contrapositive of $(\Leftarrow)$ of [2] with $\varphi = \bot$ ; $T \nvdash \bot$ iff $T$ has a model.

DefinitionRecursively Axiomatizable, Consistent, Complete Theory

A theory $T$ is:

recursively axiomatizable if it has a set of axioms whose Gödel numbers form a recursive (decidable) set;
consistent if $T \nvdash \bot$ , i.e. for no $\varphi$ do we have both $T\vdash\varphi$ and $T\vdash\neg\varphi$ ;
(negation-)complete if for every sentence $\varphi$ , $T \vdash \varphi$ or $T \vdash \neg\varphi$ ;
$\omega$ -consistent if there is no formula $\psi(x)$ with $T \vdash \exists x\,\psi(x)$ yet $T\vdash \neg\psi(\underline{n})$ for every numeral $\underline{n}$ .

TheoremGödel's First Incompleteness Theorem

Let $T$ be a consistent, recursively axiomatizable theory that interprets a modest fragment of arithmetic (e.g. Robinson arithmetic $\mathsf{Q}$ ). Then $T$ is incomplete: there is a sentence $G_T$ such that

4

\quad T \nvdash G_T \quad\text{and}\quad T \nvdash \neg G_T,

Derivation hint: construct $G_T$ via the diagonal lemma so that $T \vdash G_T \leftrightarrow \neg\mathrm{Prov}_T(\ulcorner G_T \urcorner)$ ; consistency blocks $T\vdash G_T$ , $\omega$ -consistency (Rosser's trick removes this) blocks $T \vdash \neg G_T$ . provided $T$ is $\omega$ -consistent (Rosser's strengthening needs only consistency). Moreover, if $T$ is sound (true in $\mathbb{N}$ ), then $G_T$ is true but unprovable.

TheoremGödel's Second Incompleteness Theorem

Let $T \supseteq \mathsf{PA}$ (Peano Arithmetic) be consistent and recursively axiomatizable. Let $\mathrm{Con}(T) := \neg\mathrm{Prov}_T(\ulcorner \bot \urcorner)$ . Then

5

\quad T \nvdash \mathrm{Con}(T).

Derivation hint: formalize the First Incompleteness proof inside $T$ to obtain $T \vdash \mathrm{Con}(T) \to G_T$ ; since $T\nvdash G_T$ , also $T \nvdash \mathrm{Con}(T)$ . The formalization requires the provability predicate to satisfy the Hilbert–Bernays–Löb derivability conditions:

6

\quad \begin{aligned} &\text{(D1)}\quad T\vdash\varphi \implies T\vdash \mathrm{Prov}_T(\ulcorner\varphi\urcorner),\\ &\text{(D2)}\quad T\vdash \mathrm{Prov}_T(\ulcorner\varphi\to\psi\urcorner)\to(\mathrm{Prov}_T(\ulcorner\varphi\urcorner)\to\mathrm{Prov}_T(\ulcorner\psi\urcorner)),\\ &\text{(D3)}\quad T\vdash \mathrm{Prov}_T(\ulcorner\varphi\urcorner)\to\mathrm{Prov}_T(\ulcorner\mathrm{Prov}_T(\ulcorner\varphi\urcorner)\urcorner). \end{aligned}

Derivation hint: D1 follows from $\Sigma_1$ -completeness; D2 from internalizing modus ponens; D3 from internalizing D1 — these are exactly the axioms of the modal logic $\mathsf{GL}$ .

ProofCompleteness via Henkin's Construction

We prove the Model Existence Theorem [3]: every consistent $T$ has a model. Equation [2]'s nontrivial direction follows because if $T\nvdash\varphi$ then $T\cup\{\neg\varphi\}$ is consistent, hence has a model, which falsifies $\varphi$ , giving $T\not\models\varphi$ . 1. Henkin expansion. Extend $\mathcal{L}$ to $\mathcal{L}^*$ by adding a fresh constant $c_\psi$ for each formula $\psi(x)$ with one free variable. Add Henkin axioms $\exists x\,\psi(x) \to \psi(c_\psi)$ for each. The resulting theory $T^*$ is conservative and still consistent (each axiom can be added without contradiction by a finitary argument). 2. Maximal consistent extension. By Lindenbaum's lemma (Zorn / enumeration), extend $T^*$ to a maximal consistent theory $T^{**}$ : for every sentence $\sigma$ , exactly one of $\sigma, \neg\sigma$ lies in $T^{**}$ . $T^{**}$ remains a Henkin theory. 3. Term model. Let the domain be the set of closed $\mathcal{L}^*$ -terms modulo the equivalence $t \sim s \iff (t = s) \in T^{**}$ . Interpret function and relation symbols by membership in $T^{**}$ . Each equivalence class has a witnessing Henkin constant. 4. Truth Lemma. By induction on formula complexity, for every sentence $\sigma$ :

7

\quad \mathcal{M}^{**} \models \sigma \iff \sigma \in T^{**}.

Derivation hint: atomic case by construction of the term model; Boolean cases use maximal consistency; existential case uses the Henkin witness $c_\psi$ . 5. Conclusion. Since $T \subseteq T^{**}$ , the term model $\mathcal{M}^{**}$ satisfies $T$ . Restricting the interpretation back to $\mathcal{L}$ gives a model of $T$ . $\blacksquare$ The argument uses the Axiom of Choice (via Lindenbaum) in general; for countable $\mathcal{L}$ only a weak fragment (König / Boolean prime ideal) is needed.

∎

ProofFirst Incompleteness via the Diagonal Lemma

1. Arithmetization of syntax. Assign Gödel numbers to symbols, formulas, and finite sequences. Key fact: the relation $\mathrm{Proof}_T(p, n)$ — " $p$ codes a $T$ -proof of the formula with code $n$ " — is primitive recursive, hence representable in $\mathsf{Q}$ . Define $\mathrm{Prov}_T(n) := \exists p\, \mathrm{Proof}_T(p,n)$ , a $\Sigma_1$ formula. 2. Diagonal Lemma. For any formula $\theta(x)$ there is a sentence $\sigma$ with

8

\quad T \vdash \sigma \leftrightarrow \theta(\ulcorner\sigma\urcorner).

Derivation hint: let $\mathrm{diag}$ be the recursive function sending $\ulcorner\chi(x)\urcorner \mapsto \ulcorner\chi(\ulcorner\chi(x)\urcorner)\urcorner$ ; apply $\theta\circ\mathrm{diag}$ to its own code. 3. The Gödel sentence. Apply the diagonal lemma with $\theta(x) := \neg\mathrm{Prov}_T(x)$ , obtaining $G_T$ with

9

\quad T \vdash G_T \leftrightarrow \neg\mathrm{Prov}_T(\ulcorner G_T\urcorner).

Derivation hint: substitute $\theta = \neg\mathrm{Prov}_T$ into [8]; $G_T$ "says" it is not provable. 4. Not provable. If $T \vdash G_T$ , then by D1 $T\vdash \mathrm{Prov}_T(\ulcorner G_T\urcorner)$ , but $T\vdash G_T \to \neg\mathrm{Prov}_T(\ulcorner G_T\urcorner)$ from [9], so $T$ proves both $\mathrm{Prov}_T$ and $\neg\mathrm{Prov}_T$ — contradiction with consistency. Hence $T\nvdash G_T$ . 5. Not refutable. If $T\vdash\neg G_T$ , then $T\vdash \mathrm{Prov}_T(\ulcorner G_T\urcorner)$ , i.e. $T$ proves $\exists p\,\mathrm{Proof}_T(p,\ulcorner G_T\urcorner)$ . But since $T\nvdash G_T$ , no number actually codes such a proof; $\omega$ -consistency forbids proving the existential while refuting every instance. Hence $T\nvdash\neg G_T$ . 6. Rosser's improvement. Replace $\mathrm{Prov}_T$ by Rosser's "provable with no shorter refutation" predicate; the parallel argument needs only plain consistency. $\blacksquare$

∎

KG

Kurt Gödel

1906–1978

Born in Brünn (now Brno), Gödel announced the Completeness Theorem in his 1929 doctoral dissertation at the University of Vienna and the Incompleteness Theorems at the September 1930 Königsberg conference, with the full paper Über formal unentscheidbare Sätze... appearing in 1931. A member of the Vienna Circle's periphery, he overturned Hilbert's program of finitary consistency proofs. Emigrating to Princeton's Institute for Advanced Study in 1940, he became Einstein's closest walking companion, later proving the consistency of the Continuum Hypothesis and Choice via the constructible universe $L$ (1938–40) and discovering rotating-universe solutions to general relativity (1949). His Platonism and methodical caution shaped the foundations of mathematical logic.

🧠 Intuition

Think of completeness as a dictionary that translates perfectly in both directions between the language of proofs and the language of meaning. If something is true under every possible interpretation, the calculus can always find a finite proof of it — no truth slips through the syntactic net. This is a remarkable finiteness result: validity, which is quantified over a proper class of structures, is certified by a finite object (a proof). Incompleteness then exploits the very richness of arithmetic. Because numbers can encode anything finite — including formulas and proofs — a theory of arithmetic can describe its own proof system. The Gödel sentence is a careful self-referential sentence, "I am not provable here." If the theory proved it, the theory would prove a falsehood (it is provable), so a consistent theory cannot. But then the sentence is true. Truth has outrun proof — not because of a flaw in the theory, but because no consistent recursive theory can be both complete and capable of self-description. The Second Theorem sharpens this: a system cannot pull itself up by its own bootstraps to certify its own coherence.

Figure

Syntax–semantics correspondence (completeness) versus the truth–provability gap (incompleteness)

```svg

```

ExampleCompactness as a Corollary — Coloring an Infinite Graph

Given. Let $G$ be an infinite graph (vertex set $V$ , edge relation $E$ ) such that every finite subgraph is 3-colorable. Show $G$ itself is 3-colorable, using the Compactness Theorem (a direct consequence of completeness).

Steps. 1. Introduce, for each $v\in V$ and color $i\in\{1,2,3\}$ , a propositional variable $c_{v,i}$ (" $v$ has color $i$ "). 2. Form the theory $T$ : (a) $c_{v,1}\vee c_{v,2}\vee c_{v,3}$ for each $v$ ; (b) $\neg(c_{v,i}\wedge c_{v,j})$ for $i\ne j$ ; (c) $\neg(c_{u,i}\wedge c_{w,i})$ for each edge $\{u,w\}\in E$ and each color $i$ . 3. Any finite subset $T_0\subseteq T$ mentions finitely many vertices, forming a finite subgraph, which by hypothesis is 3-colorable — giving a model of $T_0$ . So $T$ is finitely satisfiable. 4. By Compactness, $T$ has a model $\mathcal{M}$ . Read off the coloring: assign $v$ the unique color $i$ with $\mathcal{M}\models c_{v,i}$ .

Answer.

\boxed{G \text{ is 3-colorable; the global coloring is the model guaranteed by completeness/compactness.}}

The whole strength came from [3]: consistency (here, finite satisfiability) yields a model.

ExampleComputing the Gödel Number Growth and Why

G_T

Is True

Given. Work in $\mathsf{PA}$ . Suppose we use the standard Gödel numbering where a symbol sequence $s_1 s_2 \cdots s_k$ with codes $a_1,\dots,a_k$ receives number $\prod_{i=1}^{k} p_i^{a_i}$ ( $p_i$ the $i$ th prime). Estimate the order of magnitude of $\ulcorner G_T\urcorner$ for a Gödel sentence whose formula string has length $k = 200$ with average symbol code $\bar a = 12$ , and explain why $G_T$ must be true.

Steps. 1. The 200th prime is $p_{200} = 1223$ . The number is bounded above by $p_{200}^{\,k\bar a}$ roughly, but the exact value is $\prod_{i=1}^{200} p_i^{a_i}$ . 2. Order of magnitude (base-10 digits): $\log_{10} \ulcorner G_T\urcorner = \sum_i a_i \log_{10} p_i \approx k\,\bar a \cdot \overline{\log_{10}p}$ . With $\overline{\log_{10}p}\approx \log_{10}(600)\approx 2.78$ , we get $\approx 200\cdot 12 \cdot 2.78 \approx 6672$ digits. 3. Truth argument. $G_T$ asserts $\neg\mathrm{Prov}_T(\ulcorner G_T\urcorner)$ . We proved (Step 4 of the First Incompleteness proof) that $T\nvdash G_T$ when $T$ is consistent. Therefore no natural number $p$ actually codes a $T$ -proof of $G_T$ , so the statement "there is no proof of $G_T$ " is true in $\mathbb{N}$ .

Answer.

\boxed{\ulcorner G_T\urcorner \text{ has } \approx 6.7\times 10^{3} \text{ decimal digits; } G_T \text{ is true in }\mathbb{N}\text{ yet unprovable in }T.}

The astronomical size is irrelevant to the logic — what matters is that $G_T$ is a perfectly definite arithmetic statement.

⚠️ Common mistake

"The Completeness Theorem contradicts the Incompleteness Theorem." It does not. Completeness is about the deductive calculus of first-order logic: $\vdash$ matches $\models$ . Incompleteness is about a particular theory $T$ failing to decide every sentence. A theory can be incomplete as a set of axioms even though the logic is complete as a proof system. The Gödel sentence $G_T$ is genuinely not a semantic consequence of $T$ (there are models of $T$ where it fails, namely non-standard models), so completeness rightly does not prove it — there is no contradiction at all.

⚠️ Common mistake

"Incompleteness shows mathematics is inconsistent / unreliable." No. It shows no single consistent recursive theory captures all arithmetic truth, and cannot certify its own consistency from within. Consistency of $\mathsf{PA}$ is provable — Gentzen proved it in 1936 using transfinite induction up to $\varepsilon_0$ , a principle not formalizable inside $\mathsf{PA}$ . Reliability is unaffected; what fails is the dream of a self-certifying, all-deciding finite axiom system.

CounterexampleA Complete but Non-arithmetic Theory Escapes Incompleteness

The hypotheses of the First Incompleteness Theorem are essential. The theory $\mathsf{Th}(\mathbb{R}, +, \cdot, <, 0, 1)$ — the real closed field axioms — is complete and decidable (Tarski, 1948). It does not contradict Gödel because it cannot define the integers as a subset, so it cannot arithmetize its own syntax. Likewise Presburger arithmetic (natural numbers with $+$ but no $\times$ ) is complete and decidable. Multiplication together with addition is exactly what enables the coding that triggers incompleteness.

connection

The Completeness Theorem is the entry point to Model Theory: it guarantees models exist, underwriting the Compactness Theorem and the Löwenheim–Skolem Theorems, from which non-standard models of arithmetic and analysis (the foundation of Nonstandard Analysis) flow. The arithmetization of syntax connects incompleteness to Computability Theory: $\mathrm{Prov}_T$ being $\Sigma_1$ is the same phenomenon as recursively enumerable sets, and the unsolvability of the Halting Problem gives an alternative route to the First Incompleteness Theorem. The Second Theorem is the semantic content of the modal logic Provability Logic ( $\mathsf{GL}$ ), via Solovay's completeness theorem, and underlies Löb's Theorem. Finally, Tarski's Undefinability of Truth is the close cousin obtained by diagonalizing the (undefinable) truth predicate rather than the (definable) provability predicate.

🔬 Where this appears

⏳ History

- 1900 — Hilbert poses his second problem: prove the consistency of arithmetic, launching the finitist program.

- 1928 — Hilbert and Ackermann pose the Entscheidungsproblem and ask whether first-order logic is complete.

- 1929 — Gödel proves the Completeness Theorem in his Vienna dissertation, answering Hilbert–Ackermann affirmatively.

- 1930 (Sept., Königsberg) — Gödel announces the First Incompleteness Theorem; von Neumann immediately grasps and independently derives the Second.

- 1931 — Gödel publishes Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, establishing both Incompleteness Theorems.

- 1936 — Gentzen proves the consistency of

\mathsf{PA}

by transfinite induction to

\varepsilon_0

; Turing and Church independently settle the Entscheidungsproblem negatively, linking incompleteness to undecidability.

- 1936 — Rosser strengthens the First Theorem to require only consistency (not

\omega

-consistency).

- 1949 — Henkin gives the streamlined model-theoretic proof of completeness now standard.

- 1955 — Löb proves Löb's Theorem; the Hilbert–Bernays–Löb derivability conditions crystallize the Second Theorem's hypotheses, later subsumed by Solovay's 1976 arithmetical completeness of

\mathsf{GL}

.

open-problem

Several deep issues persist around the incompleteness phenomenon. (1) Intensionality of the Second Theorem. $\mathrm{Con}(T)$ depends on how provability is formalized; Feferman (1960) exhibited a provability predicate (not satisfying D3) under which a $T$ "proves its own consistency" — clarifying that the Second Theorem requires the natural, derivability-condition-satisfying formalization. Pinning down the canonical notion remains philosophically contested. (2) Concrete mathematical independence. Beyond artificial Gödel sentences, the Paris–Harrington theorem (1977), the Hydra game (Kirby–Paris), and Goodstein's theorem give natural combinatorial statements independent of $\mathsf{PA}$ ; the program of finding ever more "mathematically ordinary" independent statements (e.g. in graph minor theory, Friedman's work on $\mathsf{ZFC}$ -independence) is open-ended. (3) The ordinal analysis frontier. Determining the proof-theoretic ordinals of strong theories (notably full second-order arithmetic $\Pi^1_1\text{-}\mathsf{CA}_0$ and beyond) is among the hardest active problems in proof theory. (4) Absolute provability. Whether there is a sharp, theory-independent notion of "the mathematical truths humans can in principle know" — and whether it can be a recursive theory — connects incompleteness to open questions in the philosophy of mathematics.

Completeness and Incompleteness Theorems

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also