Content deleted Content added
m →Reductions weaker than Turing reducibility: typo in L(A) |
|||
Line 48:
* [[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 [[recursive ordinal]] α.
*[[Constructible universe#Relative constructibility|Relative constructibility]]: A set ''A'' is relatively constructible from a set ''B'' if ''A'' is in ''L''
== References ==
| |||