Example of sets $A, B$ such that $A', B'$ are Turing equivalent but $A, B$ are not.

149 Views Asked by At

I have been wondering if the following statement is true, $$ A\equiv_TB\iff A'\equiv_TB' $$ where $A, B\subseteq\omega$ and $A'$ denotes the Turing jump of $A$. I have been able to show the forward direction, but have been unable to show the converse. I am starting to think that the converse fails and have been looking for an example. Any suggestions?

2

There are 2 best solutions below

1
On

There are indeed sets $A,B$ such that $A'\equiv_T B'$ yet $A'\not\equiv_T B$, at least in certain theories (so it is consistent). One family of examples comes from so-called high sets, which are computably enumerable sets such that $A'\geq_T\emptyset''$. Since $A\leq \emptyset'$, if $A'\equiv_T\emptyset''$ the question of whether $A,\emptyset'$ are such a pair boils down to whether $\emptyset'\leq A$, i.e. whether $A$ is complete. An example of a high non-complete set $A$ is provided here, but the example relies on strengthened axioms for induction.

0
On

Similar to @Alex's answer, there are also low sets. A set $A\subseteq \omega$ is low if $A' \leq 0'$ (so that $A' \equiv_{T} 0'$). Notice that any low $0<A<0'$ would then be a counterexample to the converse of your statement. The Kleene-Post finite-extension construction of incomparable degrees builds two such sets.