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?
2026-04-04 07:54:10.1775289250
On
Example of sets $A, B$ such that $A', B'$ are Turing equivalent but $A, B$ are not.
149 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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.
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.