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?



How similar are the c.e. degrees and the CEA(Cohen) degrees?
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$.


