= Solution
Assume multiplication in $M$ were recursive. The multiplication half of Tennenbaum's coding argument says that, for a fixed nonstandard code $c$, both
$$
\{n\in\mathbb N:M\models\operatorname{Bit}(c,\bar n)\}
\quad\text{and its complement}
$$
are 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.
Back to article page
