Me pregunto si lo siguiente es cierto, $$ A\equiv_TB\iff '\equiv_TB' $$ donde $A, B\subseteq\omega$ y $A'$ denota el salto de Turing de $A$. He podido Mostrar la dirección de avance, pero han sido incapaces de demostrar lo contrario. Estoy empezando a pensar que lo contrario no y buscando un ejemplo. ¿Alguna sugerencia?
Respuestas
¿Demasiados anuncios?
clintp
Puntos
5127
De hecho, existen conjuntos de $A,B$ tal que $A'\equiv_T B'$ aún $A'\not\equiv_T B$, al menos en ciertas teorías (por lo que es coherente). Una familia de ejemplos proviene de los llamados de alto conjuntos, que son computably enumerable conjuntos tales que a $A'\geq_T\emptyset''$. Desde $A\leq \emptyset'$ si $A'\equiv_T\emptyset''$ a la pregunta de si $A,\emptyset'$ son un par se reduce a si $\emptyset'\leq A$, es decir, si $A$ es completa. Un ejemplo de una gran no-conjunto completo $A$ es proporcionado aquí, pero el ejemplo se basa en el fortalecimiento de axiomas para la inducción.
noah
Puntos
61
Similar a la respuesta de @Alex, también hay conjuntos de baja . Un conjunto de $A\subseteq \omega$ es baja si $A' \leq 0'$ (para que $A' \equiv_{T} 0'$). Aviso que cualquier bajo $0<A<0'$ sería un contraejemplo a lo contrario de su declaración. La construcción de la extensión finita de Kleene-Post de grados incomparables construye dos tales sistemas.
