# 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? – Noah Schweber Nov 21 '17 at 3:39
• @NoahSchweber yes – PyRulez Nov 21 '17 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. Richter showed 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 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. – Joel David Hamkins Nov 21 '17 at 3:47
• Is the atomic diagram the set of atomic statements true in a model? – PyRulez Nov 21 '17 at 18:03
• @PyRulez And negated atomic; and with parameters from the model. – Noah Schweber Nov 21 '17 at 20:32