Reduction (recursion Theory) - Reductions Weaker Than Turing Reducibility

Reductions Weaker Than Turing Reducibility

Although Turing reducibility is the most general reducibility that is effective, weaker reducibility relations are commonly studied. These reducibilities are related to relative definability of sets over arithmetic or set theory. They include:

• Arithmetical reducibility: A set A is arithmetical in a set B if A is definable over the standard model of Peano arithmetic with an extra predicate for B. Equivalently, according to Post's theorem, A is arithmetical in B if and only if A is Turing reducible to, the nth Turing jump of B, for some natural number n. The arithmetical hierarchy gives a finer classification of arithmetical reducibility.
• Hyperarithmetical reducibility: A set A is hyperarithmetical in a set B if A is definable (see analytical hierarchy) over the standard model of Peano arithmetic with a predicate for B. Equivalently, A is hyperarithmetical in B if and only if A is Turing reducible to, the αth Turing jump of B, for some B-recursive ordinal α.
• Relative constructibility: A set A is relatively constructible from a set B if A is in L(B), the smallest transitive model of ZFC set theory containing B and all the ordinals.