Reduction (computability theory): Difference between revisions

Revision as of 02:43, 26 February 2007

Revision as of 02:52, 26 February 2007

Line 45:

== Reductions weaker than Turing reducibility ==

Although Turing reducibility is the most general effective reducibility, therethat areis reducibility relationseffective, weaker thanreducibility this thatrelations are commonly studied. These notionsreducibilities are emphasizerelated theto 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 arithemticalarithmetical 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 hyperarithemticalhyperarithmetical 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''[''B''], the smallest model of [[ZFC set theory]] containing ''B'' and all the ordinals.

== References ==