Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 120 / 2

A Sigma-1 formula is a formula equivalent in first-order arithmetic towhere $\delta$ is bounded. A Pi-1 formula is similarly equivalent to $\forall y_1\cdots \forall y_k\delta$ with bounded $\delta$.

The diagonal lemma states that for every formula $\theta (x)$ with one free variable there is a sentence $\gamma$ such thatThe same conclusion holds in every theory extending the arithmetic needed to formalize substitution.

The crude incompleteness theorem says that every consistent recursively axiomatized extension $T$ of $P{A}^{-}$ is incomplete.

Suppose instead that $T$ were complete. Enumerating proofs until either $\sigma$ or $\neg \sigma$ appears would decide theoremhood, so its characteristic function ${\chi }_T$ would be total recursive. By the assumed representation theorem, choose a formula $R(x)$ such that $P{A}^{-}$ proves $R(\bar{n})$ when ${\chi }_T(n)=1$ and proves $\neg R(\bar{n})$ when ${\chi }_T(n)=0$. The diagonal lemma supplies $\gamma$ withIf $T⊢\gamma$, then ${\chi }_T(┌\gamma ┐)=1$, so $T⊢R(┌\gamma ┐)$ and is inconsistent. If $T⊢\neg \gamma$, then the characteristic value is zero, so $T⊢\neg R(┌\gamma ┐)$ and hence $T⊢\gamma$, again a contradiction. Completeness must therefore fail.

The recursive theory $T=P{A}^{-}+\phi$ is consistent because $\mathbb{N}\models T$. By the Gödel-Rosser theorem it has an undecidable sentence $\rho$, so both $T+\rho$ and $T+\neg \rho$ are consistent. Exactly one of $\rho ,\neg \rho$ is false in $\mathbb{N}$; add that one to $T$. The first-order completeness theorem gives a model, and the Downward Lowenheim-Skolem theorem gives a countable model $M$. Then $M\models P{A}^{-}+\phi$, but $M$ disagrees with $\mathbb{N}$ on the chosen sentence and is therefore not elementarily equivalent to it.

Disjoint sets $A,B\subseteq \mathbb{N}$ are recursively inseparable when there is no recursive $C\subseteq \mathbb{N}$ such that

Consistency of $P{A}^{-}$ makes $A$ and $B$ disjoint. Suppose a recursive set $C$ separated them, and let $R(x)$ represent its total characteristic function in $P{A}^{-}$. By the diagonal lemma, choose a sentence $\sigma$ satisfyingPut $n=┌\sigma ┐$. If $n\in C$, representability gives $P{A}^{-}⊢R(\bar{n})$ and hence $P{A}^{-}⊢\neg \sigma$, so $n\in B$, contradicting $B\cap C=\varnothing$. If $n\notin C$, representability gives $P{A}^{-}⊢\neg R(\bar{n})$ and hence $P{A}^{-}⊢\sigma$, so $n\in A\subseteq C$, again a contradiction. Therefore $A$ and $B$ are recursively inseparable.