Gödel's First Incompleteness Theorem

Gödel's first incompleteness theorem establishes fundamental limitations on formal systems: any consistent, sufficiently expressive formal system contains statements that are true but unprovable. This shatters Hilbert's dream of a complete axiomatization of mathematics.

Statement

Definition6.4Sufficient Conditions

A theory $T$ in the language of arithmetic is sufficiently strong if it extends Robinson arithmetic $Q$ (or equivalently, represents all computable functions). $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 \in \mathbb{N}$ .

Definition6.5Gödel Sentence

Using the diagonal lemma applied to the formula $\neg \mathrm{Prov}_T(x)$ (where $\mathrm{Prov}_T(x)$ formalizes " $x$ is the Gödel number of a sentence provable in $T$ "), there exists a sentence $G$ such that: $T \vdash G \leftrightarrow \neg \mathrm{Prov}_T(\ulcorner G \urcorner).$ The sentence $G$ asserts "I am not provable in $T$ ."

Example$G$ Is Undecidable

If $T$ is consistent: $T \not\vdash G$ (if it did, then $G$ would be false in $\mathbb{N}$ , but $T$ is meant to be sound). If $T$ is $\omega$ -consistent: $T \not\vdash \neg G$ (since $G$ is true in $\mathbb{N}$ , and $\neg G$ would mean "there exists a proof of $G$ ," but no standard number is such a proof). So $G$ is independent of $T$ .

Rosser's Improvement

Definition6.6Rosser's Theorem

Rosser's improvement weakens the hypothesis from $\omega$ -consistency to simple consistency: for any consistent, sufficiently strong theory $T$ , there exists a sentence $R$ that is independent of $T$ . The Rosser sentence $R$ says "for any proof of me, there is a shorter proof of my negation," using a more careful self-referential construction.

RemarkImpact on Foundations

The first incompleteness theorem implies that no single formal system can serve as a complete foundation for mathematics. For any consistent axiom system $T$ (PA, ZFC, etc.), there are true arithmetic statements not provable in $T$ . Adding such statements as axioms produces a stronger system, but this too is incomplete.