Reduction Function

Let .
A total Computable function is a reduction from to if for all we have:

We also say that is many-to-one reducible to .
We write
Note that is a Partial Preorder

The following proposition says that is at most as complicated as
(in the computability sense).

Proposition

If and is Computable, then so is .
If and is Computably Enumerable, then so is .