# Is there an oracle that can compute something iff it is computable in every countable model that is equivalent to $(V, \in)$?

Let us work in Kelly-morse set theory, so we can talk about $$V$$. For some model $$M=(\mathbb N, \in_M)$$ that is elementary equivalent $$(V, \in)$$, we can have an oracle that corresponds to $$(\mathbb N, \in_M)$$'s truth predicate. We will say that $$M$$ is a true countable model of set theory, and we will call the oracle $$O_M$$.

My question is, is there an oracle that can compute a function iff every oracle $$O_M$$ for ever true countable model of set theory can compute the function?

Such an oracle would at least be able to determine if a first order sentence without free variables is true in $$(V, \in)$$. My conjecture is it does exist, and is defined by the previous statement.

Some notes:

• For any definable set, there is a Turing machine with oracle $$O_M$$ that outputs a number corresponding to that set.
• Any $$O_M$$ (for true countable M) can calculate Rayo's function. (Another question to ask would be if a Turing machine equipped with an oracle for Rayo's function let's you determine truth of statements in $$(V, \in)$$ without free variables.)
• By the truth predicate, you just mean the elementary diagram, correct? Nov 21, 2017 at 3:39
• @NoahSchweber yes Nov 21, 2017 at 4:57

Yes - this real is exactly the parameter-free theory of $$V$$ (or anything Turing-equivalent to it).

One direction is immediate: if $$M$$ is elementarily equivalent to $$V$$, then from the elementary diagram of $$M$$ we can compute the theory of $$V$$ (just look at the parameter-free sentences). It's the other direction that is interesting, and the key is that Henkinization is effective: from any complete consistent first-order theory $$T$$ we can uniformly compute a model of $$T$$ together with its elementary diagram.

Note that this applies to arbitrary structures, not just $$V$$: the reals computable from the elementary diagram of any structure $$\mathcal{N}$$ elementarily equivalent to $$\mathcal{M}$$ are exactly the reals computable from $$Th(\mathcal{M})$$.

Incidentally, a very similar-sounding question has a very different answer in general. Given a structure $$\mathcal{A}$$, we can look at its copies - those structures $$\mathcal{B}$$ with domain $$\mathbb{N}$$ which are isomorphic to $$\mathcal{A}$$. We can ask what reals are computable from (the atomic diagram of) every copy of $$\mathcal{A}$$. Interestingly, even very complicated structures can have very little computing power in this sense; e.g. Linda Jean Richter showed in Degrees of Structures (JSTOR) that if $$\mathcal{L}$$ is a linear order, it has no computing power - for every noncomputable real $$x$$ there is some copy $$\mathcal{J}$$ of $$\mathcal{L}$$ whose atomic diagram doesn't compute $$x$$. If you're interested in this sort of question, Ash and Knight's book Computable Structures and the Hyperarithmetical Hierarchy is the standard reference.

It's also worth noting that for any computable theory $$T$$ and any noncomputable set $$x$$, there is a model of $$T$$ whose atomic diagram does not compute $$x$$; moreover, any such theory has a model with a low atomic (or even elementary) diagram - even a really complicated theory like ZFC.

• Very nice! I was trying all kinds of complicated things with standard systems and omitting types. But of course, I wasn't using the completeness of the theory, for which Henkinization is computable. Nov 21, 2017 at 3:47
• Is the atomic diagram the set of atomic statements true in a model? Nov 21, 2017 at 18:03
• @PyRulez And negated atomic; and with parameters from the model. Nov 21, 2017 at 20:32