= Solution
\b[There is no computable presentation of a <Nonstandard model of Peano arithmetic>.] We prove <Tennenbaum theorem> by obtaining a <computable set> separating two <recursively inseparable sets>.
Fix an effective enumeration $(\varphi_e)$ of <partial computable functions>, implemented by deterministic machines, and put
$$
U=\{e:\varphi_e(e)\downarrow=0\},\qquad V=\{e:\varphi_e(e)\downarrow=1\}.
$$
These are disjoint <computably enumerable sets>. To see that they are <recursively inseparable sets>, suppose a <computable set> $D$ contains $U$ and avoids $V$. Its <indicator function> has some index $k$. If $\varphi_k(k)=0$, then $k\in U\subseteq D$, contradicting that output. If $\varphi_k(k)=1$, then $k\in V$, contradicting $D\cap V=\varnothing$. Thus neither output is possible.
Let $M\models\mathrm{PA}$ be a <Nonstandard model of Peano arithmetic>. A <recursive presentation of a structure> here means a presentation on $\mathbb N$ in which its arithmetic operations are <total computable functions>; equality of presentation codes is ordinary equality. Write $\bar n$ for the element represented by the standard numeral $n$. The presentation codes of $\bar0,\bar1$ are fixed constants, so $n\mapsto\bar n$ is a <total computable function> obtained by repeated addition. Presentation codes and the arithmetic values they name must be kept distinct.
Use <bounded simulation of a computation> predicates $H_i(e,t)$ saying that machine $e$, on input $e$, has halted by time $t$ with output $i$. We can choose these as <primitive recursive> predicates represented in <Peano arithmetic>. Determinism and induction on the computation length give, provably in <Peano arithmetic>, monotonicity in $t$ and
$$
\forall e\,\forall t\,\forall s\;\neg\bigl(H_0(e,t)\land H_1(e,s)\bigr).
$$
A genuine standard halting computation has a finite certificate which <Peano arithmetic> verifies. Consequently, if $e\in U$ or $e\in V$, the corresponding $H_i(\bar e,\bar t)$ holds in $M$ for some standard $t$.
Choose a nonstandard element $c$ of $M$. It exceeds every standard numeral. Let $p_e$ be the $e$th <prime number>, starting with $p_0=2$. <Peano arithmetic> proves the <prime-divisibility coding of a finite set> needed here: for each $c$, an element $d$ can be formed as the product of precisely those $p_e$ with $e<c$ for which $H_0(e,c)$ holds. Formally,
$$
M\models\forall e<c\;\bigl(p_e\mid d\ \longleftrightarrow\ H_0(e,c)\bigr).
$$
This is an internally finite product, not a claim that its externally observed index set is finite. Its existence follows by <mathematical induction> on the cutoff: start with $1$, multiply by the next distinct <prime number> when its predicate holds, and otherwise retain the product. <Unique prime factorization> ensures that earlier divisibility decisions are preserved. The standard prime enumeration and these finite-product constructions are provably total in <Peano arithmetic>.
Define the external subset $D=\{e\in\mathbb N:M\models p_{\bar e}\mid d\}$. If $e\in U$, its standard halting time is below $c$, and monotonicity gives $H_0(\bar e,c)$, so $e\in D$. If $e\in V$, its output-one certificate and the provable incompatibility above exclude $H_0(\bar e,c)$, so $e\notin D$. Hence $D$ separates $U$ and $V$.
Finally $D$ is a <computable set>. Given standard $e$, compute the ordinary integer $p_e$ and its numeral in the presentation. Enumerate all presentation codes $q$, and for each test the finitely many standard remainders $0\le r<p_e$ for
$$
d=\bar p_e\cdot q+\bar r.
$$
Each test is decidable using the assumed <total computable functions>. The division theorem of <Peano arithmetic> guarantees a quotient and a remainder below the standard numeral $\bar p_e$. Every element below that numeral is one of $\bar0,\ldots,\overline{p_e-1}$, so the search terminates; the remainder is unique. Return yes exactly when $r=0$. This makes $D$ a <computable set>, contradicting the <recursively inseparable sets> construction. Therefore
$$
\boxed{M\models\mathrm{PA}\text{ nonstandard}\ \Longrightarrow\ M\text{ has no recursive presentation}.}
$$
Back to article page
