Editing Arithmetical hierarchy (section)

== Arithmetic reducibility and degrees ==

Arithmetical reducibility is an intermediate notion between [[Turing reducibility]] and [[hyperarithmetic reducibility]].

A set is '''arithmetical''' (also '''arithmetic''' and '''arithmetically definable''') if it is defined by some formula in the language of Peano arithmetic.  Equivalently ''X'' is arithmetical if ''X'' is <math>\Sigma^0_n</math> or <math>\Pi^0_n</math> for some natural number ''n''.   A set ''X'' '''is arithmetical in''' a set ''Y'', denoted <math>X \leq_A Y</math>, if ''X'' is definable as some formula in the language of Peano arithmetic extended by a predicate for membership of ''Y''. Equivalently, ''X'' is arithmetical in ''Y'' if ''X'' is in <math>\Sigma^{0,Y}_n</math> or <math>\Pi^{0,Y}_n</math> for some natural number ''n''. A synonym for  <math>X \leq_A Y</math> is: ''X'' is '''arithmetically reducible''' to ''Y''.

The relation <math>X \leq_A Y</math> is [[Reflexive relation|reflexive]] and [[Transitive relation|transitive]], and thus the relation <math>\equiv_A</math> defined by the rule

:<math> X \equiv_A Y \iff X \leq_A Y \land Y \leq_A X</math>
is an [[equivalence relation]].  The [[equivalence classes]] of this relation are called the '''arithmetic degrees'''; they are [[partially ordered]] under <math>\leq_A</math>.