Arithmetical Hierarchy - Relativized Arithmetical Hierarchies

Relativized Arithmetical Hierarchies

Just as we can define what it means for a set X to be recursive relative to another set Y by allowing the computation defining X to consult Y as an oracle we can extend this notion to the whole arithmetic hierarchy and define what it means for X to be, or in Y, denoted respectively and . To do so, fix a set of integers Y and add a predicate for membership in Y to the language of Peano arithmetic. We then say that X is in if it is defined by a formula in this expanded language. In other words X is if it is defined by a formula allowed to ask questions about membership in Y. Alternatively one can view the sets as those sets that can be built starting with sets recursive in Y and alternatively projecting and taking the complements of these sets up to n times.

For example let Y be a set of integers. Let X be the set of numbers divisible by an element of Y. Then X is defined by the formula so X is in (actually it is in as well since we could bound both quantifiers by n).