$m$-degree of a simple set contains infinitely many $1$-degrees

22 Views Asked by At

Exercise 1.7.17. (e) of Li and Vitanyi: Show that the $m$-degree of a simple set contains infinitely many $1$-degrees consisting entirely of simple sets. $m$-degrees are equivalence classes of the many-to-one reducibility relation and $1$-degrees are equivalence classes for one-to-one. It's easy enough to see that a set that has the same $m$-degree as a simple set is itself simple, but I'm stuck on the rest. My only idea of what sets to look at is that we can make a simple set into the image of an injective recursive function, and then look at the range of iterated compositions of this function with itself. These do turn out to be simple as a sanity check, but I could be completely wrong and have no idea how to proceed if right.