Editing Arithmetical hierarchy (section)

== Relativized arithmetical hierarchies ==

Just as we can define what it means for a set ''X'' to be [[Recursive set|recursive]] relative to another set ''Y'' by allowing the computation defining ''X'' to consult ''Y'' as an [[oracle (computability)|oracle]] we can extend this notion to the whole arithmetic hierarchy and define what it means for ''X'' to be <math>\Sigma^0_n</math>, <math>\Delta^0_n</math> or <math>\Pi^0_n</math> in ''Y'', denoted respectively <math>\Sigma^{0,Y}_n</math>, <math>\Delta^{0,Y}_n</math> and <math>\Pi^{0,Y}_n</math>.  To do so, fix a set of natural numbers ''Y'' and add a [[predicate (logic)|predicate]] for membership of ''Y'' to the language of Peano arithmetic.  We then say that ''X'' is in <math>\Sigma^{0,Y}_n</math> if it is defined by a <math>\Sigma^0_n</math> formula in this expanded language.  In other words, ''X'' is <math>\Sigma^{0,Y}_n</math> if it is defined by a <math>\Sigma^{0}_n</math> formula allowed to ask questions about membership of ''Y''.  Alternatively one can view the <math>\Sigma^{0,Y}_n</math> sets as those sets that can be built starting with sets recursive in ''Y'' and alternately taking [[Union (set theory)|unions]] and [[Intersection (set theory)|intersections]] of these sets up to ''n'' times.

For example, let ''Y'' be a set of natural numbers.  Let ''X'' be the set of numbers [[divisible]] by an element of ''Y''.  Then ''X'' is defined by the formula <math>\phi(n)=\exists m \exists t (Y(m)\land m\times t = n)</math> so ''X'' is in <math>\Sigma^{0,Y}_1</math> (actually it is in <math>\Delta^{0,Y}_0</math> as well, since we could bound both quantifiers by ''n'').