Editing Many-one reduction (section)

=== Subsets of natural numbers ===

Given two sets <math>A,B \subseteq \mathbb{N}</math> one says <math>A</math> is '''many-one reducible''' to <math>B</math> and writes
:<math>A \leq_{\mathrm{m}} B</math>
if there exists a [[total computable function]] <math>f</math> with <math>x\in A</math> iff <math>f(x)\in B</math>. 

If the many-one reduction <math>f</math> is [[Injective function|injective]], one speaks of a one-one reduction and writes <math>A \leq_1 B</math>.

If the one-one reduction <math>f</math> is [[Surjective function|surjective]], one says <math>A</math> is '''[[computable isomorphism|recursively isomorphic]]''' to <math>B</math> and writes<ref name="Odifreddi89">[[Piergiorgio Odifreddi|P. Odifreddi]], ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.</ref><sup>p.324</sup>
:<math>A\equiv B</math>