Isomorphism of lattices of recursively enumerable sets

Abstract:

Let $\omega = \{ 0,1,2,\ldots \}$, and for $A\subseteq \omega$, let $\mathcal E^A$ be the lattice of subsets of $\omega$ which are recursively enumerable relative to the “oracle” $A$. Let $(\mathcal E^A)^*$ be $\mathcal E^A/\mathcal I$, where $\mathcal I$ is the ideal of finite subsets of $\omega$. It is established that for any $A,B\subseteq \omega$, $(\mathcal E^A)^*$ is effectively isomorphic to $(\mathcal E^B)^*$ if and only if $A’\equiv _T B’$, where $A’$ is the Turing jump of $A$. A consequence is that if $A’\equiv _T B’$, then $\mathcal E^A\cong \mathcal E^B$. A second consequence is that $(\mathcal E^A)^*$ can be effectively embedded into $(\mathcal E^B)^*$ preserving least and greatest elements if and only if $A’\leq _T B’$.