arithmetical hierarchy (original) (raw)

The first level consists of formulas with only bounded quantifiers, the corresponding relations are also called the Primitive Recursive relations (this definition is equivalent to the definition from computer science). This level is called any of Δ00, Σ00 and Π00, depending on context.

A formula ϕ is Σn0 if there is some Δ00 formula ψ such that ϕ can be written:

Similarly, ϕ is a Πn0 relation if there is some Δ00 formula ψ such that:

A formula is Δn0 if it is both Σn0 and Πn0. Since each Σn0 formula is just the negation of a Πn0 formula and vice-versa, the Σn0 relations are the complements of the Πn0 relations.

The relations in Δ10=Σ10∩Π10 are the Recursive relations.

Higher levels on the hierarchy correspond to broader and broader classes of relations. A formula or relation which is Σn0 (or, equivalently, Πn0) for some integer n is called arithmetical.

The superscript 0 is often omitted when it is not necessary to distinguish from the analytic hierarchy.

Functions can be described as being in one of the levels of the hierarchy if the graph of the function is in that level.