Timeline for How similar are the c.e. degrees and the CEA(Cohen) degrees?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 14, 2021 at 22:18 | comment | added | Theodore Slaman | Very nice: that interesting point never occurred to me. It's open whether every element of $\mathcal{R}$ is definable. It would hold if $\mathcal{R}$ could be biinterpretable with first order arithmetic $N$. Relativizing, $\mathcal{R}_X$ could be biinterpretable with first order arithmetic using parameters to identify an interpretation of $N$ with a predicate for $X$. Then there would be $\vec{p}$ such that every $d$ in $\mathcal{R}_X$ is definable from $\vec{p}$. That is also open for $\mathcal{R}$. Weaker yet, it is open whether the automorphism group of $\mathcal{R}$ is countable. | |
| May 14, 2021 at 5:45 | comment | added | 喻 良 | @JoeMiller Nice observation. Similarly for sufficiently random and/or generic degrees. | |
| May 14, 2021 at 3:35 | comment | added | Joe Miller | 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. | |
| May 13, 2021 at 20:29 | comment | added | Theodore Slaman | 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. | |
| May 13, 2021 at 20:26 | comment | added | Noah Schweber | 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. | |
| May 13, 2021 at 20:21 | comment | added | Noah Schweber | 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?) | |
| May 13, 2021 at 20:20 | vote | accept | Noah Schweber | ||
| May 13, 2021 at 20:13 | history | answered | Theodore Slaman | CC BY-SA 4.0 |