6
$\begingroup$

Given reals $A,B,X$, let $A\le_{T/X}B$ iff $A\oplus X\le_TB\oplus X$. For each real $X$ we can define a version of the c.e. degrees over $X$: we look at the preorder on $X$-c.e. reals given by $\le_{T/X}$ (or, if preferred, take the corresponding partial order). Call this $\mathcal{R}_X$; equivalently, $\mathcal{R}_X$ could be given by the reals which are CEA $X$.

My question is the following:

Suppose $G$ is "sufficiently" Cohen generic. Is $\mathcal{R}_G\cong\mathcal{R}$?

Here $\mathcal{R}$ is the usual c.e. degrees. Incidentally, it's not hard to show that if $G,H$ are "sufficiently" Cohen generic then $\mathcal{R}_G\cong\mathcal{R}_H$. This is false.

I vaguely recall a result (due to Shore?) that the answer is no, but I can't track it down.

If the answer is no, I'm curious how similar they are nonetheless. For example, do $\mathcal{R}_G$ and $\mathcal{R}$ have the same $\Pi_3$ theories?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm being ignorant here: what does "sufficiently generic" mean? $\endgroup$
    – Jason Zesheng Chen
    Commented May 13, 2021 at 7:24
  • 2
    $\begingroup$ It means meeting or avoiding every set of strings from a sufficiently large (countable) collection of sets, e.g. every hyperarithmetic set of strings. $\endgroup$
    – Dan Turetsky
    Commented May 13, 2021 at 8:53
  • $\begingroup$ This old paper of Abraham and Shore is somewhat off-topic but very interesting - londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/… $\endgroup$
    – François G. Dorais
    Commented May 13, 2021 at 21:41

1 Answer 1

Reset to default
7
$\begingroup$

I am reading ≅ as meaning "elementarily equivalent."

There are several questions here. I believe that some of them are accessible by known methods. The first is that if $X$ is not (low-level)arithmetically definable, then $\mathcal{R}_X$ is not elementarily equivalent to $\mathcal{R}$. The proof should go by relativising the methods of

Nies, André ; Shore, Richard A. ; Slaman, Theodore A. Interpretability and definability in the recursively enumerable degrees. Proc. London Math. Soc. (3) 77 (1998), no. 2, 241--291.

They show that there is a way to interpret the structure of first order arithmetic in the theory of $\mathcal{R}.$ Relativizing, the method should show that there is an interpretation of the structure of first order arithmetic with a predicate for $X$ in $\mathcal{R}_X$. The elementary difference with $\mathcal{R}$ would be of the form, there is an interpretation of the structure of first order arithmetic with a unary predicate $U$ such that $U$ is not $\Sigma_k$, where $k$ is sufficiently large that it cannot be so represented in $\mathcal{R}$. It should suffice that $k=10$.

You might look at Shore's paper,

Shore, Richard A. Degree structures: local and global investigations. Bull. Symbolic Logic 12 (2006), no. 3, 369--389,

for a survey of known results and methods.

I agree that it would be interesting to know the exact complexity of the optimal elementary difference. That question also touches on the old and open problem of deciding the two-quantifier theory of $\mathcal{R}$. It would be very interesting if working above $X$ a generic, or a random, or anything at, made it possible to decide the two-quantifier theory of $\mathcal{R}_X$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is very nice, thanks! (I had intended "$\cong$" to be isomorphism; as a side question, do you know if it's substantially easier to show that $\mathcal{R}$ and $\mathcal{R}_G$ are not isomorphic if $G$ is sufficiently generic?) $\endgroup$
    – Noah Schweber
    Commented May 13, 2021 at 20:21
  • $\begingroup$ Re: the last paragraph, I suppose an interesting first step might be: is there an $X$ such that $\mathcal{R}_X$ and $\mathcal{R}$ have different $2$-quantifier theories? That already seems tricky unless I'm missing something. $\endgroup$
    – Noah Schweber
    Commented May 13, 2021 at 20:26
  • 3
    $\begingroup$ It's a little easier to show not isomorphic. You don't have to show that there is a definable collection of codes for standard models of arithmetic. You only have to show that there are parameters that code the standard model with a unary predicate for $X$. By the way, the same observation shows that if $G$ and $H$ are mutually arithmetically generic then $\mathcal{R}_G$ and $\mathcal{R}_H$ are not isomorphic. They are elementarily equivalent, since every sentence in the theory of $\mathcal{R}_G$ is decided by the empty condition. $\endgroup$
    – Theodore Slaman
    Commented May 13, 2021 at 20:29
  • 2
    $\begingroup$ I really like the last point, Ted. Similarly, the theory of $\mathcal{R}_X$ is decided on-a-cone. But since we can't hope to pick out the parameters that code $X$, it must be the case that on-a-cone not every element of $\mathcal{R}_X$ can be definable (in $\mathcal{R}_X$). Which is still open for $\mathcal{R}$, I think. $\endgroup$
    – Joe Miller
    Commented May 14, 2021 at 3:35
  • $\begingroup$ @JoeMiller Nice observation. Similarly for sufficiently random and/or generic degrees. $\endgroup$
    – 喻 良
    Commented May 14, 2021 at 5:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .