A set 
of integers is said to be one-one reducible
to a set 
(
) if there is a one-one recursive function 
such that for every 
,
 |
(1)
|
and
 |
(2)
|
Similarly, a set 
of integers is many-one reducible to set 
(
)
if there is a recursive function 
such that for every 
,
 |
(3)
|
and
 |
(4)
|
Here, the two reducibility relations are reflexivity and transitivity.
One-one reducibility implies many-one reducibility. Any set reducible to a recursive set is recursive itself. Any set reducible to a recursively enumerable set is recursively enumerable itself. The above facts are commonly used in recursive undecidability proofs done by reduction to nonrecursive sets.
Two sets are one-one/many-one equivalent if each of them is one-one/many-one reducible to the other. One-one equivalence, many-one equivalence, and recursive isomorphism are all equivalence relations.
If sets 
and 
are recursively
isomorphic, then they are one-one equivalent and vice versa.
If a class (also called degree) of equivalent sets contains a recursive set, then all sets from the equivalence class are recursive. If a class (degree) contains a recursively enumerable set, then all sets from the equivalence class are recursively enumerable.
There exist a maximum degree to which all other degrees of recursively enumerable sets can be one-one reduced. The same is true for many-one reducibility. The sets
from each of the two maximum degrees are called complete. For example, the set of
all 
such that 
is convergent belongs to the maximum degree for both
one-one and many-one reducibilities, where 
denotes a recursive
function whose Gödel number is 
.
If set 
is many-one complete, then it is one-one
complete, and vice versa.
Although, one-one and many-one reducibilities themselves do not coincide on non-recursive, recursively enumerable sets. There are non-recursive, recursively enumerable sets that are not complete.
Note that a few other notions of reducibility are defined and investigated in theory of recursive functions.
