Content deleted Content added
Line 47:
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 <math>B^{(n)}</math>, the ''n''th [[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 <math>\Delta^1_1</math> 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 <math>B^{(\alpha)}</math>, the ''α''th [[Turing jump]] of ''B'', for some ''B''-[[recursive ordinal]] α.
*[[Constructible universe#Relative constructibility|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.
| |||