Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 120 / 3

A Sigma-1 formula is a formula equivalent in arithmetic to $\exists y_1\cdots \exists y_r\delta$, where $\delta$ is bounded. A Pi-1 formula is similarly equivalent to $\forall y_1\cdots \forall y_r\delta$ with $\delta$ bounded.

Solved by gpt-5.6-sol high.

The total function $f:{\mathbb{N}}^k\to \mathbb{N}$ is Sigma-1 represented in $T$ when there is a Sigma-1 formula $F(\mathbf{x},y)$ such that, for every standard tuple $\mathbf{n}$ and $m=f(\mathbf{n})$,Thus $T$ proves the correct unique output on every standard input.

Solved by gpt-5.6-sol high.

The Diagonal lemma says that for every one-variable formula $\theta (x)$ there is a sentence $\gamma$ such thatLet $d(n)$ be the computable function taking the code of a one-variable formula $\alpha (x)$ to the code of $\alpha (\bar{n})$. By the assumed representation theorem, choose a Sigma-1 formula $D(x,y)$ representing $d$. Given $\theta$, putand let $b=┌\beta ┐$. Taking $\gamma =\beta (\bar{b})$, representability proves in $T$ that the unique relevant $y$ is $d(b)=┌\gamma ┐$, yielding the required equivalence.

Solved by gpt-5.6-sol high.

Suppose such a formula $\theta (x)$ existed. Apply the Diagonal lemma to $\neg \theta (x)$ to obtain a sentence $\sigma$ for whichBecause $M\models {\mathrm{PA}}^{-}$, the equivalence holds in $M$. But the defining property of $\theta$ says $M\models \theta (┌\sigma ┐)$ exactly when $M\models \sigma$, producing $M\models \sigma$ exactly when $M/\models \sigma$, a contradiction.

Solved by gpt-5.6-sol high.

The Tennenbaum theorem states that no countable nonstandard model of Peano arithmetic has a presentation on $\mathbb{N}$ in which both its addition and multiplication operations are recursive.

Solved by gpt-5.6-sol high.

Assume multiplication in $M$ were recursive. The multiplication half of Tennenbaum's coding argument says that, for a fixed nonstandard code $c$, bothare computably enumerable from the multiplication table. The proof uses the canonical prime-power coding in PA; bounded inequalities are replaced by existential sum-of-four-squares conditions using the Lagrange four-square theorem, and the resulting witnesses can be searched for effectively from multiplication. Dovetailing the two searches decides the coded set. Applied to $c$, this would make $X$ recursive, contradicting the hypothesis. Therefore multiplication in $M$ cannot be recursive.

Solved by gpt-5.6-sol high.