Gödel's Incompleteness and the Nature of Mathematical Truth — Epoche C2
The claim under examination The claim to be examined is that Kurt Gödel's first incompleteness theorem shows some arithmetical statements to be neither true nor false — that formal undecidability is a kind of truth-value gap. It is not. The theorem does establish that any consistent, effectively axiomatised theory strong enough to talk about arithmetic contains a sentence it can neither prove nor refute; it does not follow, and is not the case, that such a sentence lacks a truth value. What the theorem separates is provability from truth, and the interest of the result lies entirely in how that separation is produced. Tracing the construction is therefore not a detour: the sentence's truth is read off its syntactic shape, and once one has seen the shape, the misreading becomes hard to sustain. A remark on what will not be assumed. Three hypotheses appear in every correct statement of the theorem, and the essay as it previously stood carried only two of them. Getting the third into view is the first order of business, because two of the misreadings in circulation are traceable to dropping it. The theorem, and which hypotheses do the work Let $F$ be a theory in a first-order language. Three conditions are required. First, $F$ is effectively axiomatised : there is an algorithm deciding what counts as an axiom of $F$, so that the relation "the finite object $p$ is a correct $F$-derivation of the sentence $\varphi$" is decidable. Second, $F$ is consistent. Third, $F$ interprets enough arithmetic — it suffices that $F$ contains Robinson arithmetic $Q$, the finitely axiomatised theory of successor, addition and multiplication with no induction schema at all. Under these three conditions there is a sentence $G_F$ in the language of $F$ with $F \not\vdash G_F$; and $F \not\vdash \neg G_F$ as well. Each hypothesis is doing identifiable work, and dropping any one of them yields a consistent counterexample to the conclusion. This is worth setting out, because the frequently repeated slogan that no formal system can be both complete and consistent is false as stated. Hypothesis dropped Witness Why it escapes Effective axiomatisation $\mathrm{Th}(\mathbb{N})$, the set of all sentences true in the natural numbers Complete and consistent by construction; but the axiom set is not decidable, indeed not even recursively enumerable, so nothing there is a formal system in the required sense. Enough arithmetic Presburger arithmetic (1929): first-order arithmetic with addition but no multiplication. Also the first-order theory of real closed fields (Tarski, 1951). Both are complete, consistent and decidable. Without multiplication one cannot define the coding of syntax on which everything below depends. Consistency Any inconsistent theory Complete, since it proves every sentence — the degenerate case the theorem must exclude. The exponent-and-factor question here is why the arithmetical requirement is so weak. One might expect that full Peano arithmetic, with its induction schema, would be needed to carry out the self-reference. It is not, and the reason is a single property of $Q$: it proves every true $\Sigma_1$ sentence, that is, every true sentence of the form "there exists a number such that (decidable condition)". Since "there is a derivation of $\varphi$" is exactly of that form, $\Sigma_1$-completeness is all the arithmetic the argument consumes. Induction is needed to prove things about the provability predicate — it is required for the second incompleteness theorem — but not to build the sentence or to run the first half of the argument. How the sentence is built The construction has three moving parts, and the second is where the effective-axiomatisation hypothesis is spent. First, an injective and effective coding of syntax into numbers: each formula $\varphi$ receives a code, written $\ulcorner \varphi \urcorner$, and each finite derivation likewise. Second, because derivation-checking is decidable, the relation "$x$ codes a derivation in $F$ of the sentence coded by $y$" is primitive recursive, and every primitive recursive relation is representable in $Q$ — there is a formula $\mathrm{Prf}_F(x,y)$ such that for actual numbers $m,n$, if the relation holds then $Q \vdash \mathrm{Prf}_F(\bar m, \bar n)$, and if it fails then $Q \vdash \neg\mathrm{Prf}_F(\bar m, \bar n)$, where $\bar m$ is the numeral for $m$. Provability is then the $\Sigma_1$ formula $\mathrm{Prov}_F(y) := \exists x\, \mathrm{Prf}_F(x,y)$. Note the asymmetry that will matter later: provability is definable inside the language, by a formula of a very simple quantifier form. Third, the diagonal lemma. For any formula $\psi(x)$ with one free variable there is a sentence $\sigma$ with $$F \vdash \sigma \leftrightarrow \psi(\ulcorner \sigma \urcorner).$$ The proof is a two-line trick worth stating because it is what makes the result constructive rather than an existence claim. Let $\mathrm{sub}(n,m)$ be the function returning the code of the formula obtained by substituting the numeral $\bar m$ for the free variable of the formula coded by $n$. Substitution on strings is a primitive recursive operation, so $\mathrm{sub}$ is representable. Put $\theta(x) := \psi(\mathrm{sub}(x,x))$ and let $\sigma := \theta(\ulcorner \theta \urcorner)$. Then $\mathrm{sub}(\ulcorner\theta\urcorner, \ulcorner\theta\urcorner)$ is precisely the code of $\theta(\ulcorner\theta\urcorner)$, which is the code of $\sigma$; so $\sigma$ says that $\psi$ holds of $\sigma$'s own code. Nothing about the content of $\psi$ was used, which is why the same trick delivers Tarski's theorem below and Löb's theorem elsewhere. Applying the lemma to $\psi(x) := \neg\mathrm{Prov}_F(x)$ yields the Gödel sentence: $$F \vdash G_F \leftrightarrow \neg\mathrm{Prov}_F(\ulcorner G_F \urcorner).$$ It is worth being exact about what "asserts its own unprovability" means, since the phrase invites the suspicion of a trick. $G_F$ is an ordinary arithmetical sentence — a statement that a ce