Editing Many-one reduction (section)

==Degrees==
The relation <math>\equiv_m</math> indeed is an [[equivalence relation|equivalence]], its [[equivalence classes]] are called m-degrees and form a poset <math>\mathcal D_m</math> with the order induced by <math>\leq_m</math>.<ref name="Odifreddi89" /><sup>p.257</sup>

Some properties of the m-degrees, some of which differ from analogous properties of [[Turing degree|Turing degrees]]:<ref name="Odifreddi89" /><sup>pp.555--581</sup>
* There is a well-defined jump operator on the m-degrees.
* The only m-degree with jump '''0'''<sub>m</sub>&prime; is '''0'''<sub>m</sub>.
* There are m-degrees <math>\mathbf a>_m\boldsymbol 0_m'</math> where there does not exist <math>\mathbf b</math> where <math>\mathbf b'=\mathbf a</math>.
* Every countable linear order with a least element embeds into <math>\mathcal D_m</math>.
* The first order theory of <math>\mathcal D_m</math> is isomorphic to the theory of second-order arithmetic.

There is a characterization of <math>\mathcal D_m</math> as the unique poset satisfying several explicit properties of its [[Ideal_(set_theory)|ideals]], a similar characterization has eluded the Turing degrees.<ref name="Odifreddi89" /><sup>pp.574--575</sup>

[[Myhill isomorphism theorem|Myhill's isomorphism theorem]] can be stated as follows: "For all sets <math>A,B</math> of natural numbers, <math>A\equiv B\iff A\equiv_1 B</math>." As a corollary, <math>\equiv</math> and <math>\equiv_1</math> have the same equivalence classes.<ref name="Odifreddi89" /><sup>p.325</sup> The equivalences classes of <math>\equiv_1</math> are called the ''1-degrees''.