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

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.

Solved by gpt-5.6-sol high.