4
$\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
  • $\begingroup$ By the truth predicate, you just mean the elementary diagram, correct? $\endgroup$ – Noah Schweber Nov 21 '17 at 3:39
  • $\begingroup$ @NoahSchweber yes $\endgroup$ – PyRulez Nov 21 '17 at 4:57
6
$\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. 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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