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

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.