5
$\begingroup$

Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions?

It is something which I have been unclear with for a while (from a Computability Theory POV).

$\endgroup$
6
$\begingroup$

No - even within (say) the class of $\Sigma_1$ (= c.e., r.e., semidecidable, ...) sets, there is lots of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions).

The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing degree is strictly between ${\bf 0}$ (= computable) and ${\bf 0'}$ (= halting problem)? This was answered about a decade later by the Friedberg-Muchnik theorem, which showed that there are Turing-incomparable (so a fortiori many-one-incomparable) c.e. sets. Their argument generalizes immediately to get a countably infinite sequence of Turing-incomparable c.e. sets. Later, Sacks proved that whenever we have c.e. sets $A<_TB$ we can in fact find a sequence $(C_i)_{i\in\mathbb{N}}$ of c.e. sets which are Turing-incomparable to each other and which all lie strictly between $A$ and $B$ in terms of Turing reducibility (this is basically his density theorem + a bit of elaboration). Note that Sacks' theorem also shows that there are infinite increasing and infinite decreasing sequences of Turing degrees as well as infinite antichains.

So there is extremely rich non-linearity there. In fact, though, that's only the beginning of the story. The structure of $\mathcal{R}$ (= the Turing degrees of c.e. sets, ordered by Turing reducibility) turns out to be extremely complicated, and there are still many major open questions about it. Soare's old book Recursively enumerable sets and degrees contains a lot of information on the topic, which really picks up in earnest at chapter $7$ (where priority arguments, the method developed by Friedberg and Muchnik and later elaborated by Sacks and others, are first introduced); Soare also wrote a medium-length survey paper on the topic.


EDIT: Even though it's not directly related to the OP let me address a common related question: namely, how the c.e. degrees (= Turing degrees of c.e. sets) sit inside the poset of all Turing degrees.

We know that every c.e. set is Turing reducible to the halting problem, so every c.e. degree is $\le_T{\bf 0'}$. The converse however is false: there are degrees below ${\bf 0'}$ which are not c.e. degrees. There is a "syntactic" characterization of $\{{\bf d}: {\bf d}\le_T{\bf 0'}\}$ but it's more complicated; see here.

(Incidentally, the easiest way I know to prove the existence of a non-c.e. degree below ${\bf 0'}$ is to $(i)$ prove Sacks' density theorem and $(ii)$ construct a minimal noncomputable degree below ${\bf 0'}$. This is rather a lot of work, but as far as I know there's no easier way of doing this!)

There is however a sense in which the degrees below ${\bf 0'}$ are "c.e. in flavor." Specifically, say that a set $X\subseteq\mathbb{N}$ is $2$-c.e. if $X=A\setminus B$ for c.e. sets $A,B$. We can similarly define $3$-c.e. and $n$-c.e. sets for all finite $n$, and even continue this into the transfinite in a precise sense. The resulting "hierarchy" (scarequotes since it's not linear!) is called the Ershov hierarchy, and with help from the limit lemma we can show that every set computable from ${\bf 0'}$ is $\alpha$-c.e. for some ordinal (or rather, ordinal notation) $\alpha$. The fact that $\le_T{\bf 0'}$ doesn't imply c.e. is extended by a general, if somewhat technical, non-collapsing result for the Ershov hierarchy; for example, there is a $2$-c.e. set not Turing-equivalent to any c.e. set (which I believe is due to Cooper).

$\endgroup$
1
  • $\begingroup$ Thank you so much for your insightful and exhaustive answer, Noah. I am familiar with some of Sacks Theorems, but I was unable to associate which theorem are you referring to. Is this the one in his book “Degrees of Unsolvability” , Ch “A continuum of mutually incomparable degrees” ? Or am I looking in the wrong place. Also, much, much thanks for your insight on the Ershov Hierarchy, I did not even know about it. $\endgroup$ – Danish A. Alvi Apr 14 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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