information:classification
Weaker reductions

According to the Church–Turing thesis, a Turing reduction is the most general form of an effectively calculable reduction. Nevertheless, weaker reductions are also considered. Set A {\displaystyle A} is said to be arithmetical in B {\displaystyle B} if A {\displaystyle A} is definable by a formula of Peano arithmetic with B {\displaystyle B} as a parameter. The set A {\displaystyle A} is hyperarithmetical in B {\displaystyle B} if there is a recursive ordinal α {\displaystyle \alpha } such that A {\displaystyle A} is computable from B (α) {\displaystyle B^{(\alpha)}}, the α -iterated Turing jump of B {\displaystyle B}. The notion of relative constructibility is an important reducibility notion in set theory.