16
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ For the weak version, there is a kind of trivial answer: Pick any countable non-standard model of peano, and consider the set of well formed expression using $+$,$*$,$($,$)$ and element of your model. You obtain a countable set with an addition and a multiplication that are computable and your initial model is the quotient of this by simply sending any expression to its evaluaton. And I don't understand the strong form: you assumed that $f$ and $d$ where compuable, so why do you need an algorithme the approximate $f$ ? also why wouldn't this be a computable model ? $\endgroup$ Oct 14, 2015 at 10:31
  • $\begingroup$ Excellent point about the weak version. $\:$ I did indeed have an error in my description of the strong version (f shouldn't be assumed computable), although I don't see how the computability of d had anything to do with that. $\;\;\;\;$ $\endgroup$
    – user5810
    Oct 14, 2015 at 11:42
  • $\begingroup$ It seems to me that in the weak version, you can assume without loss that the functions are giving you the (free) term algebra, since if they don't, then you can modify to one where they do. $\endgroup$ Oct 14, 2015 at 13:05
  • $\begingroup$ You ask specifically for the case where one operation is computable, but can you already rule out the case where both operations are computable? That is, can a nonstandard model of PA arise as the quotient of a computable structure $\langle N,+,\cdot\rangle$ by a co-c.e. equivalence relation? $\endgroup$ Oct 14, 2015 at 13:06
  • $\begingroup$ @JoelDavidHamkins : $\;\;\;$ I head meant for the "Super-Strong" version to obviously be stronger than the weak version. $\:$ It is in fact stronger, since one can use the free term algebra on the metric space (so that inequality will be c.e.), but that's certainly not obvious. $\:$ Based on the idea of the free term algebra over the metric space, I'm about to simplify the statement of the Super-Strong version in a way that I believe gives something equivalent to what was there when you commented. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user5810
    Oct 14, 2015 at 13:30

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ Since it only uses standard $p_i\hspace{-0.02 in}$, your argument doesn't need a multiplication oracle. $\hspace{1.6 in}$ $\endgroup$
    – user5810
    Oct 14, 2015 at 20:35
  • $\begingroup$ Ah, yes, of course. We search for $x$ and $y$ and then just add $x$ to itself $p_i$ times, and then add $y$. $\endgroup$ Oct 14, 2015 at 20:59
  • 2
    $\begingroup$ PA (and any consistent r.e. theory for that matter) has a model which is a quotient of the term algebra by a low $\Delta_2$ congruence relation. I find it difficult to imagine how an argument along these lines could differentiate between $\Pi_1$ and low $\Delta_2$ relations, which suggests that getting rid of the extra soundness assumptions might be tricky (if the result holds at all). $\endgroup$ Oct 14, 2015 at 21:47
  • $\begingroup$ I edited to have the argument rely only on + instead of both + and times. $\endgroup$ Oct 15, 2015 at 0:11
  • 2
    $\begingroup$ Using the third theorem, you can strengthen the second theorem as follows: no nonstandard $\Sigma_1$-sound model of $I\Sigma_1$ is a quotient $\langle N,+,\cdot\rangle/{\approx}$ where $+$ and $\approx$ are $\Sigma_2$. First, if they were $\Sigma_2$, they would actually be $\Delta_2$. Second, the other assumptions are enough to give that every pair of disjoint $\Sigma_2$ sets is separated by a set from the standard system; you can apply this to a $\Delta_2$-inseparable pair. $\endgroup$ Oct 15, 2015 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.