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..$

Can you summarize the definition of $<_m$? I suspect your "m-degree" may be the same thing as Turing degrees but am not sure. — hmakholm left over Monica, May 09 '18 at 09:06
Or perhaps equivalence under (unlimited-resources) many-one reductions? — hmakholm left over Monica, May 09 '18 at 09:11
I edited. Yes many-one reductions. I haven't studied Turing degrees yet(but I know definitions of Turing degrees) — fbg, May 09 '18 at 09:15

score 4 · Accepted Answer · answered May 09 '18 at 09:25

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.

score 3 · Answer 2 · answered May 09 '18 at 15:56

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.

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

2 Answers2