5
$\begingroup$

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.)
$\endgroup$
2

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 21, 2017 at 3:47
  • $\begingroup$ Is the atomic diagram the set of atomic statements true in a model? $\endgroup$ Nov 21, 2017 at 18:03
  • $\begingroup$ @PyRulez And negated atomic; and with parameters from the model. $\endgroup$ Nov 21, 2017 at 20:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.