question about m-degrees : Is $<_m$ except $\{\mathbb{N} \}$, $\{\emptyset\}$ total order?

Question

I'm recently reading computability theory(nigel cutland p.162.). This book introduces $m$-degree $a,b,c...$ and defines $a<_mb$ and shows this is partial order.$<_m$ is a partial order because of $\bf{0}=\{\emptyset\}$, $\bf{n}$=$\{\mathbb{N}\}$. Naturally I come to ask the case of $<_m$ without $\bf{0}$ and $\bf{n}$. Is it true or not?

Definitions

$A\leq_mB$ iff there's total $\mu$-recursive function $f$ such that $x\in A\Leftrightarrow f(x)\in B$

$A\equiv_mB$ iff $A\leq_mB$ and $B\leq_mA$

$m$-degree $d_m(A)=\{B\subset \mathbb{N}|A\equiv_m B\}$ denoted as $a,b,c..$

Answer 1

Let $A$ be your favorite recursively enumerable but not decidable set -- such as HALT.

There cannot be a many-one reduction $f$ from $A$ to $A^\complement$ -- because if there were, we could decide $x\in A$ by looking for both $x$ and $f(x)$ in parallel in an enumeration of $A$.

For exactly the same reason, there cannot be a reduction from $A^\complement$ to $A$.

So their m-degrees are incomparable.

Answer 2

There is actually a complete characterization of the partial order of $m$-degrees (see for example Odifreddi's article in the Handbook of Computability Theory). This is unusual, there are not similar characterizations of other structures such as the Turing degrees.

One corollary of the characterization is that every finite distributive upper semilattice embeds into the upper semilattice of $m$-degrees. So the overall structure of the $m$-degrees is quite complex and is not at all like a linear order.