# Classification of recursively enumerable sets

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

• See en.wikipedia.org/wiki/…. Recursively enumerable Turing degrees are dense. Dec 6 '20 at 13:56
• 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$ ?
– byk7
Dec 6 '20 at 14:58
• Since Turing reducibility extends many-one reducibility, yes it does: if $A\not\ge_TB$ then a fortiori $A\not\ge_m B$. 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).