4
$\begingroup$

It's quite easy to show that there are only three recursive sets up to m-equivalence, namely $\emptyset,\{1\},\mathbb N.$ Can we state something "similarly short" for recursively enumerable sets, like there are only 4 recursively enumerable sets up to m-equivalence – $\emptyset,\{1\},K,\mathbb N$ (where $K=\{i\mid\varphi_i(i)\text{ is def.}\}$)? More specifically, is every non-recursive recursively enumerable set m-equivalent to $K$?

$\endgroup$
3
  • $\begingroup$ See en.wikipedia.org/wiki/…. Recursively enumerable Turing degrees are dense. $\endgroup$
    – Ariel
    Commented Dec 6, 2020 at 13:56
  • $\begingroup$ I am not sure if that answers my question, because I don't know much about Turing equivalence. Does it imply that there is a non-recursive r.e. set $A$ such that $K\nleq_m A$ ? $\endgroup$
    – byk7
    Commented Dec 6, 2020 at 14:58
  • 1
    $\begingroup$ Since Turing reducibility extends many-one reducibility, yes it does: if $A\not\ge_TB$ then a fortiori $A\not\ge_m B$. $\endgroup$ Commented Dec 6, 2020 at 20:18

1 Answer 1

3
$\begingroup$

There are lots of these. Even with respect to Turing reducibility (which extends $m$-reducibility: if $A\not\ge_TB$ then $A\not\ge_mB$), the structure of c.e. sets is extremely rich.

That said, constructing an infinite non-recursive r.e. $A$ with $A<_mK$ is significantly easier than constructing one with $A<_T K$. The former was done by Post in 1944 who introduced the notions of creative and simple sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the priority method).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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