Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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.

share|improve this answer
    
Those "strengthened axioms of induction" are far far weaker than what is available in usual set theories like ZFC, which are the usual setting for recursion theory. Unless we are interested in the Reverse Mathematics of recursion theory, there is no issue with induction. –  Carl Mummert Mar 16 '12 at 13:49

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.