3

$\exists A \in \mathcal{P}(\mathbb{N}). (A \lt_T 0' \land \neg \exists B \in \Sigma_1. A \equiv_T B)$?

In words: does there exist a subset of natural numbers that is Turing reducible to the halting set but is not Turing equivalent to any computably enumerable set?

Carl Mummert
  • 81,604
Dávid Natingga
  • 2,889
  • 2
  • 27
  • 41

1 Answers1

2

Yes, there are.

There is a result from (G. E. Sacks, 1964) : r.e degree are dense. That means that if $A$ and $B$ are r.e Turing degrees (Turing degree that contains an enumerable set) such that $A<_TB$, then there is a r.e Turing degree such that $A<_TC<_TB$.

But there is another result that shows there are minimal degree : some degree $A$ such that $0<A$ but there is not any $B$ such that $0<B<A$. Of course such $A$ could not be r.e by previous result.

An article A Minimal Partial Degree ≤ 0' by Leonard P. Sasso, Jr. (1973) explains how to build such a minimal degree under $0'$.

Xoff
  • 10,310
  • This is true, but the Kleene-Post method was known far earlier as a way of making intermediate (but not r.e.) degrees. – Carl Mummert Jan 01 '15 at 14:17
  • @CarlMummert Interesting! I knew that method created intermediate degrees, but I thought (wrongly) it was not known whether they were re or not. Could you please give a link to the Kleene Post method ? – Xoff Jan 01 '15 at 14:21
  • I was thinking of the material in Chapter VI of Soare's book. I see your point: the sets generated there can be non-r.e., but that is not the precise goal, and I don't know history well enough to know whether anyone explicitly worked out a pair of non-r.e. intermediate degrees (even today, books seem to ignore this point). The other construction method that comes to mind, hyperimmune-free degrees, seems to date to Miller and Martin in 1968, after Sacks' theorem. – Carl Mummert Jan 01 '15 at 15:17