Strong reducibility and degrees.
This file defines the notions of many-one reduction and one-one reduction between sets, and shows that the corresponding degrees form a semilattice.
- [Robert Soare, Recursively enumerable sets and degrees][soare1987]
computability, reducibility, reduction
p is many-one reducible to
q if there is a computable function translating questions about
to questions about
p is one-one reducible to
q if there is an injective computable function translating questions
p to questions about
For many-one degrees
d₁ ≤ d₂ if the sets in
d₁ are many-one reducible to the
the join of two degrees, induced by the disjoint union of two underlying sets