# Are there sets which are computable in one model, but uncomputable in another?

Suppose we have two models of set theory, $U$ and $V$ which have the same $\Bbb N$. Is it possible that there is a set $A\subseteq\Bbb N$ such that, in $U$, this set is computable, i.e. there is a number $e\in\Bbb N$ which is index of Turing machine recognizing $A$, but it doesn't hold in $V$? I believe answer to this question is "no", because it looks like TM computations are absolute between models with same natural numbers.

What will happen if we drop the requirement of them having the same $\Bbb N$? Can there be a set then, which is subset of both $\Bbb N^U$ and $\Bbb N^V$, and is computable in one universe but not another? Here there are wider possibilities, because we can have index $e$ which exists on one model and not another, and we can also have "longer" computations (i.e. amount of steps which exists in one model but not another).

Last, related, question, is about extending the models: suppose we have a model $V$ in which set $A\subseteq\Bbb N$ is uncomputable. Is it always the case that we can extend this model (e.g. add more natural numbers in some way) so that $A$ will become computable? One counterexample would be, say, $0'$, but it could also become computable, because there will be more indices of TMs, and $0'$ would cover only the old ones.

I tried to explain the above as clearly as I could. Thanks for all the feedback.

• Please clarify what you mean by $A$ being in 2 nonstandard models. Maybe you need to say that $\mathbb N^U$ and $\mathbb N^V$ are isomorphic and you are comparing $A$ and its image under the isomorphism, which is a member of the other model. But then the same absoluteness considerations should apply as in the standard case. The condition is just that there is some $e$ coding a function $f$ into $\{0,1\}$ such that for all $n$, $f(n) = 1$ iff $n \in A$. But this statement should transfer through the isomorphism. Nov 6, 2014 at 15:29
• @Monroe: There's a slight issue with the suggested clarification, every two countable non-standard models of $\sf PA$ are order-isomorphic. Nov 6, 2014 at 15:40
• A set $A \subseteq \mathbb{N}$ is computable iff $\exists n \in \omega \,.\, \forall m \in \omega \,.\, \exists k \in \omega \,.\, T(n,m,k) \land (U(k) \neq 0 \iff m \in A)$, where $T$ and $U$ are the Kleene predicate and function (primitive recursive). This is a $\Delta_0$-formula, therefore absolute for transitive classes. So at least the first part of your question has a positive answer: computability is absolute because it is expressible by a $\Delta_0$-formula. Nov 6, 2014 at 16:06
• Concerning the last question. Any infinite subset of $(\mathbb{N})^U$ in $U$ does not exist in any proper extension $V$ of $U$. Otherwise, $(\mathbb{N})^U$ belongs to $V$, a contradiction.
– 喻 良
Nov 6, 2014 at 18:08
• @LiangYu I don't see why this should be a contradiction. It can be the case that the subset of $\Bbb N^U$ becomes finite. Nov 6, 2014 at 18:12

If two models of set theory $U$ and $W$ have the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you observe the operation of Turing machines will be absolute between $U$ and $W$, and so they will think precisely the same sets are decidable. Furthermore, they will agree on the members of any arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets that they think are arithmetic. For example, in my paper, Satisfaction is not absolute, joint with Ruizhi Yang, we prove a number of instances of such models of set theory disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$ of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a Turing machine program $e$ that computes a relation $\lhd$ on $\mathbb{N}$, which both $U$ and $W$ think is a linear order on $\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$.

Another interesting example occurs with the construction of two models of set theory $U$ and $W$ which agree on the arithmetic structure $\mathbb{N}^U=\mathbb{N}^W$, and have a subset $A\subset \mathbb{N}$ in common, such that $U$ thinks $A$ is arithmetic, but $W$ does not. There are many more similar such strange examples in the paper.

Meanwhile, the answer to your question at the end is affirmative.

Theorem. If $M$ is any countable model of PA, and $A\subset M$ is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$, meaning that it satisfies induction in the expanded language, then there is an elementary end-extension $M\prec N$ such that $A$ is coded in $N$, in the sense that there is some $a\in N$ such that $i\in A$ if and only if $i\in M$ and $N$ thinks that the $i^{th}$ prime $p_i$ divides $a$ in $N$.

Thus, even though the set $A$ might not be computable in $M$, it becomes the initial segment of a computable set in $N$. For example, the halting problem of $M$ or indeed any definable subset of $M$ becomes the initial segment of a computable and indeed pseudo-finite set in $N$.

The theorem can be proved by means of a definable ultrapower of $\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$ either generically, or in $\omega$ many steps so that every function $f:M\to M$ that is definable in that structure and bounded by an element of $M$ is constant on a set in $U$. It follows that the ultrapower $N$, using all definable functions in $\langle M,+\cdot,A\rangle$, is an elementary top-extension, and $A$ will be coded since we may define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.

• Thanks, Joel, this is exactly what I was looking for! I have yet to read the paper, but I'm sure many interesting results are given there. Nov 7, 2014 at 13:07
• Good, and we'd welcome any comments. Follow through to the arxiv to get the preprint. Nov 7, 2014 at 14:28
• Incidentally, for anyone that is local to New York, I am speaking on this paper at NYU on Monday. See jdh.hamkins.org/…. Nov 7, 2014 at 14:35