2

Say you have a c.e set $B$. Then $B$ is $m$-reducible to the halting set $K$. If I know additionally that $K \leq_T B$, can I infer $K \equiv_m B$?

Intuitively, I would say yes, as the Turing degree of $K$ i.e. $0’$ is the largest c.e. Turing degree and all c.e. sets are $m$-comparable to $K$. So the the only thing that could happen is $B \lneq_m K$. But then $K \leq_T B \lneq_m K$, which seems implausible.

Noah Schweber
  • 245,398
tim6her
  • 105

1 Answers1

2

Your intuition is reasonable, but it turns out to be wrong: there are indeed such sets!

A simple set is a co-infinite c.e. set with no infinite c.e. set in its complement. Simple sets need not be $\equiv_TK$ (indeed, there are low simple sets), but there are simple sets which are Turing-equivalent to $K$ (see the theorem at the bottom of page $304$ of Post's original paper.). $K$ itself is not simple - indeed, it is as far from simple as possible, namely creative - but no creative set is $m$-reducible to a simple set.

(I wrote earlier - and I blame my lack of sleep and caffeine - that no non-simple set could be $m$-reducible to a simple set. This is utter nonsense: let $S$ be simple and let $\hat{S}=\{2x: x\in S\}$. $\hat{S}$ is not simple - the set of odd numbers is an infinite c.e. set in the complement of $\hat{S}$ - but fixing some $n\not\in S$ we have that $\hat{S}\le_mS$ via the map sending $2k+1$ to $n$ and $2k$ to $k$ for all $k$. In my defence, it didn't take long for me to realize how bonkers my claim was.)

Incidentally, these sorts of considerations led Post and others to suspect that Post's problem ("are there Turing-incomparable c.e. sets?") would be answered by such "combinatorial" constructions. This turned out not to pan out, however - for example, there is a low simple set. Instead, the priority method was needed.

Noah Schweber
  • 245,398
  • In general, let me plug Post's paper; it's quite pleasant and readable, unlike many other papers from around that time, and it has real historical value. It's also illuminating to note the difference in "conceptual style" between Post's arguments there and priority arguments as introduced the next decade: Friedberg-Muchnik in my opinion really constituted the introduction of a whole new intuition. (One could quibble with this, arguing that it was presaged by the finite extension argument of Kleene-Post, but I think that's unfair to the novelty of the idea of priority and injury.) – Noah Schweber May 23 '18 at 16:51