Can there be computable non-standard models of PA in a weaker sense?

Question

By Tennenbaum's theorem, in the usual sense of computability for models, neither addition nor multiplication can be computable in a countable non-standard model of PA.

Weak version:

Can addition or multiplication become computable if non-equality only needs to be computably enumerable, rather than computable?

In other words, can there be a countable structure on which [either addition is computable or multiplication is computable] and some quotient of that structure is a non-standard model of PA?

If I understand the proof of the addition version of Tennenbaum's theorem correctly, then for addition to be computable there would need to be a representative $r_0$ of a non-standard number such that $\{r : r\text{ represents the same element as }r_0\}$ ​ is not computably enumerable.

I'm mainly after an answer to either version, rather than both, so the following will be quite strong.

Super-Strong version:

Are there a computable function ​ $d : \{0,1,2,3,\ldots\}^2 \to \mathbb{Q}$ and binary operations $+_M$ and $\times_M$ on $\{0,1,2,3,\ldots\}$ ​ (by Tennenbaum, they can't be computable) such that

• composing d with the inclusion from $\mathbb{Q}$ to the real numbers gives a metric and
• the induced metric space is complete and
• there is an algorithm that approximates $+_M$ and $\times_M$ to arbitrary accuracy and
• $+_M$ and $\times$ make $\{0,1,2,3,\ldots\}$ into the non-standard part of a model of PA

The standard part could just be put in with distance 1 from everything, so requiring it to be a non-standard part is stronger than requiring it be a full non-standard model.

Furthermore, we can get a non-standard model in the sense of the weak version from any witnesses to the truth of the Super-Strong version, by taking the set of well formed expression using ${0, 1,{+},{\times}, {(\; , )}}$ and elements of the metric space, and noting that both operations are computable.

Answer 1

This is a great question!

Let me give a meager partial answer, for the case where we are talking about nonstandard models of true arithmetic.

Theorem. No nonstandard model of true arithmetic arises as the quotient of a structure $\langle N,+,\cdot\rangle$ by an equivalence relation $\approx$, if $+$ is computable and $\approx$ is co-c.e. Indeed, there is no model of true arithmetic that is the quotient of a structure $\langle N,+,\cdot\rangle$ by an equivalence relation $\approx$, if both $+$ and $\approx$ are arithmetic.

Proof. Suppose that $\mathcal{N}=\langle N,+,\cdot\rangle/\approx$ is a model of true arithmetic, and $+$ and $\approx$ are each arithmetically definable. Let $Z\subset\mathbb{N}$ be an arithmetic set that is not computable from $+$ and $\approx$, such as the jump of the join of this operation and relation. Let $[s]_\approx>\mathbb{N}$ be a nonstandard element in the quotient structure, and consider $Z^{\mathcal{N}}\cap [s]$, using the arithmetic definition of $Z$. Since $\mathcal{N}$ is a model of true arithmetic, this set agrees with $Z$ on the standard numbers. Since $Z^{\mathcal{N}}\cap [s]$ is a finite set in $\mathcal{N}$, it is coded in the model. So there is some $r$ such that $i\in Z\iff \mathcal{N}\models p_i$ divides $[r]$, where $p_i$ is the $i^{\rm th}$ prime. Using the operation $+$ and the relation $\approx$ as oracles, we can compute whether $\mathcal{N}$ thinks that $p_i$ divides $[r]$. Specifically, we search for a solution to $r\approx p_i\cdot x+y$, where $y$ is equivalent to one of the corresponding numbers less than $p_i$, and then check whether $y\approx 0$. Note that since $p_i$ is standard finite, we can compute $p_i\cdot x$ by repeated addition of $x$, and so we need only $+$. In this way, we can compute $Z$ from those oracles, contrary to the choice of $Z$. QED

Another way to think about the argument is this: there is no arithmetically definable nonstandard model of true arithmetic. This is essentially the same as Tennenbaum, and the point now is that if you had an arithmetic quotient structure, then you could produce an actual arithmetic structure, which is impossible.

By paying a little closer attention to complexity, the same argument shows:

Theorem. If $\langle N,+,\cdot\rangle/\approx$ is a nonstandard model of arithmetic that is $\Sigma_2$-sound, then it cannot be that $+$ and $\approx$ are computable from $0'$.

Proof. We simply take $Z=0''$ in the previous argument. If the model is $\Sigma_2$ sound, then it will agree on the standard elements of $0''$, and so using $0'$ as an oracle, we would be able to compute both $+$ and $\approx$, and hence the coded version of $0''$, giving a contradiction. QED

Here is a slightly improved version:

Theorem. If $\mathcal{N}=\langle N,+,\cdot\rangle/\approx$ is a nonstandard model of PA, then every real in the standard system of $\mathcal{N}$ is computable from $+$ and $\approx$.

Proof. Suppose that $Z$ is in the standard system of $\mathcal{N}$, so that it is coded in $\mathcal{N}$, in the sense that there is $r\in N$ such that $i\in Z\iff p_i$ divides $r$ in $\mathcal{N}$. Using $+$ and $\approx$ as oracles, we can find $x$ and $y<p_i$ for which $r\approx p_i\cdot x+y$, and then check whether $y\approx 0$. So $Z$ is computable from $+\oplus\approx$. QED

So the models of PA that do arise in the way you describe must have comparatively low standard systems. If there is any real in the standard system of the quotient $\langle N,+,\cdot\rangle/\approx$ that is not computable from $0'$, then it cannot be that $+$ is computable and $\approx$ is co-c.e.