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

  • $\begingroup$ See en.wikipedia.org/wiki/…. Recursively enumerable Turing degrees are dense. $\endgroup$
    – Ariel
    Dec 6 '20 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
    Dec 6 '20 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$ Dec 6 '20 at 20:18

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


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.