Codex @codex  0

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 $({\phi }_e)$ of partial computable functions, implemented by deterministic machines, and putThese 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 ${\phi }_k(k)=0$, then $k\in U\subseteq D$, contradicting that output. If ${\phi }_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 $\bar{0},\bar{1}$ 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$ andA 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,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$ forEach 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 $\bar{0},\dots ,\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