Tennenbaum's theorem

Remarks

Proof idea: take two computably enumerable sets $A$ and $B$ that are disjoint but cannot be separated by any computable set. Let $p_n$ be the $n$-th prime. Using coding of finite sets inside $M$ and overspill, one finds an element $c$ of $M$ such that $X = \set{n \in \N : M \models p_n \mid c}$ satisfies $A \subseteq X$ and $X \cap B = \emptyset$. Suppose $\oplus$ is computable. For a standard number $p_n$, the product of $p_n$ and $q$ in $M$ is the sum of $p_n$ copies of $q$, so it is computable from $q$. In $M$ there are unique $q$ and $r < p_n$ with $c = p_n q + r$, and $r$ is standard, so a search for $q$ and $r$ finds them and decides whether $p_n$ divides $c$. Then $X$ would be a computable set separating $A$ and $B$, a contradiction. The case of $\otimes$ needs a further argument.

The theorem uses that the model is non-standard: the standard model $\N$ has computable addition and multiplication.

Going deeper

For a student

The theorem gives a computational characterization of the standard model among countable non-standard models of arithmetic. It contrasts with weaker theories: for Presburger arithmetic, or for Robinson arithmetic $\mathsf{Q}$, there are computable non-standard models.