Incompleteness, Undecidability, and Church's Theorem

The arithmetization of syntax attached a Gödel number to every expression and made the syntactic relations representable in $\text{Cn }{A}_E$. Self-reference now becomes a theorem. Throughout, the language is the language of $\mathfrak{N}$, so theory means a theory in that language and $\text{Cn }$ closes under its consequences. Write $┌\phi ┐$ for the numeral $S^{\#\phi }0$ that names the Gödel number of $\phi$; a formula $\beta$ with one free variable, evaluated at $┌\phi ┐$, then makes an assertion about $\phi$.¹

The fixed-point lemma

One construction underlies the rest: for any property $\beta$ of Gödel numbers there is a sentence that asserts $\beta$ holds of itself.

The sentence $\sigma$ can be read as saying $\beta$ is true of me. It says no such thing on its own — it is a string that, under $\mathfrak{N}$, speaks of numbers and their successors and products. Only because we have paired numbers with expressions can $\sigma$ be understood as referring to a formula, in this case itself.

Undefinability of truth

Applied to the set of true sentences, the lemma refutes any formula proposed to define truth. Let $\#\text{Th }\mathfrak{N}$ be the set of Gödel numbers of sentences true in $\mathfrak{N}$. This first application needs only the semantic form ${\models }_{\mathfrak{N}}\sigma \leftrightarrow \beta (┌\sigma ┐)$ of the fixed point, not provability in $A_E$.

Because every recursive set is definable in $\mathfrak{N}$ (recursive relations are arithmetical), an undefinable set cannot be recursive.

The theory of the natural numbers is undecidable: no algorithm tests, of an arbitrary arithmetic sentence, whether it is true.

Gödel's first incompleteness theorem

The undecidability of truth combines with the recursiveness bound (a complete recursive theory has a recursive theorem set, item 21) to force incompleteness on every reasonable axiomatization of arithmetic.

No consistent recursive set of true axioms decides all of arithmetic; in particular $\text{Cn }{A}_E\ne \text{Th }\mathfrak{N}$, and adding any recursive set of further truths does not close the gap. The proof of Tarski's theorem even exhibits the missing sentence. Fix a recursive $A\subseteq \text{Th }\mathfrak{N}$ and let $\beta$ define $\#\text{Cn }A$ in $\mathfrak{N}$ (available because $\#\text{Cn }A$ is recursively enumerable, hence arithmetical). The fixed point $\sigma$ against $\neg \beta$ indirectly says "I am not a theorem of $A$," and it is true and unprovable:

This is nearer Gödel's original route, which did not detour through truth in $\mathfrak{N}$.

Strong undecidability and incompleteness from consistency

Truth in $\mathfrak{N}$ is more than the argument needs. The same fixed-point move, run against a formula defining a recursive theory, shows that no consistent extension of the subtheory can be decidable; the axioms need not be true.

First, adding finitely many axioms preserves recursiveness of the theorem set, by the deduction theorem.

This is Gödel's theorem again, with "true in $\mathfrak{N}$:q weakened tomerely consistent with $A_E$." Any recursively axiomatized theory that so much as agrees with the finite subtheory is incomplete: the incompleteness is a fact about axiomatizability, not about truth.

Church's theorem

The smallest theory in the language is the set of valid sentences, $\text{Cn }\varnothing$. It is consistent with $A_E$ (their closure is $\text{Cn }{A}_E$), so strong undecidability applies to it directly.

First-order validity is undecidable: no algorithm tests an arbitrary sentence for logical truth. The result does not depend on the arithmetic vocabulary. It holds for any language containing at least one two-place predicate symbol, because the arithmetic can be interpreted there; on the other hand some minimum is needed — in the language of pure equality, or with only $\forall$ and one-place predicate symbols, validity is decidable.²

Recursive enumerability

The coded-deduction recursion places provability one quantifier away from recursiveness.

Existentially quantifying a defining formula shows every r.e. relation is definable in $\mathfrak{N}$, and collapsing a block of existential quantifiers into one (via sequence coding) shows the several characterizations agree.³ The r.e. relations are the formal counterpart of the effectively enumerable ones: a relation is effectively enumerable iff it is the domain of a decidable relation, and identifying decidable with recursive identifies the two notions (Church's thesis, second form).

Provability is the leading example of an r.e. set that need not be recursive.

The procedure never halts and never decides non-theoremhood: if $a$ is not a theorem, the search runs forever. This is the exact gap between provable and true. With a recursive set of axioms the theorems are at best recursively enumerable, whereas $\text{Th }\mathfrak{N}$ is not even definable in $\mathfrak{N}$. Expanding the language or adding axioms changes nothing: as long as deductions are recursively recognizable, the theorems stay merely r.e. The set of number-theoretic sentences provable in any standard axiomatic set theory is r.e., includes $A_E$, and (barring inconsistency) is consistent — so that set theory is itself nonrecursive and incomplete.

Weak representability

A recursive relation is represented outright: the theory settles each instance positively or negatively. An r.e. relation cannot be, unless it is recursive, but it can be represented halfway.

Membership is now signalled only by provability of the positive instance; nonmembership produces no proof of the negation, merely the absence of a proof of the instance. For an r.e. $Q$ with $a\in Q\iff \exists b⟨a,b⟩\in R$ and $\rho$ representing $R$, the formula $\exists v_2\rho (v_1,v_2)$ weakly represents $Q$ in $\text{Cn }{A}_E$; the nonmembership direction uses that $A_E$ is $\omega$-consistent, so $A_E⊢\neg \rho (┌a┐,S^{b}0)$ for every $b$ blocks $A_E⊢\exists v_2\rho (┌a┐,v_2)$.⁴

Representable, definable, and weakly representable line up exactly with recursive, arithmetical, and recursively enumerable.

The arithmetical hierarchy

Definability in $\mathfrak{N}$ admits degrees, organized by counting alternations of unbounded quantifiers over a recursive matrix. Let ${\Sigma }_1$ be the r.e. relations (one existential quantifier away from recursive) and ${\Pi }_1$ their complements. In general $Q\in {\Sigma }_k$ when it has the form $\{\vec{a}:\exists b_1\forall b_2\cdots ⟨\vec{a},\vec{b}⟩\in R\}$ with $k$ alternating quantifiers led by $\exists$ over recursive $R$, and $Q\in {\Pi }_k$ when the leading quantifier is $\forall$. Writing ${\Delta }_k={\Sigma }_k\cap {\Pi }_k$, the base case ${\Delta }_1$ is the recursive relations, which is the content of the complementary-enumerability theorem restated as ${\Delta }_1={\Sigma }_1\cap {\Pi }_1$.

Every arithmetical relation lands somewhere on the ladder: put its defining formula in prenex form, whose quantifier-free matrix defines a recursive relation (quantifier-free formulas are numeralwise determined by $A_E$), and read off the level from the quantifier prefix. Bounded quantifiers can be pushed inward past the counting, since $(\forall i<n)(\exists d)P\iff (\exists d)(\forall i<n)P$ after collapsing, so they never raise a relation's level. The hierarchy also lifts to theories: if $\#A$ is in ${\Sigma }_k$ for $k>0$, then $\#\text{Cn }A$ is again in ${\Sigma }_k$, so provability from a ${\Sigma }_k$ axiom set stays at level $k$.

Tarski's and Gödel's theorems divide cleanly. Tarski's says truth is not arithmetical at all: $\#\text{Th }\mathfrak{N}$ lies outside the whole hierarchy. Gödel's says provability, though low in the hierarchy (it is ${\Sigma }_1$), still does not coincide with truth. The second incompleteness theorem sharpens the second of these by turning the provability predicate on the consistency of the theory itself.