Tennenbaum's theorem

Tennenbaum's theorem says that no countable nonstandard model of Peano arithmetic can have both addition and multiplication computable under a presentation of its domain by the natural numbers.

Choose disjoint computably enumerable, recursively inseparable sets $A,B$. A nonstandard arithmetic model internally codes the elements enumerated into $A$ below a nonstandard stage by divisibility by standard primes. If the model's addition and multiplication were computable, division by each standard prime would decide the coded standard set. It would contain $A$ and avoid $B$, contradicting recursive inseparability.