Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them.
Any set that receives a classification is called arithmetical.
The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic.
The Tarski–Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines.
The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.
The arithmetical hierarchy of formulas
The arithmetical hierarchy of sets of natural numbers
A set X of natural numbers is defined by formula φ in the language of Peano arithmetic (the first-order language with symbols "0" for zero, "S" for the successor function, "+" for addition, "×" for multiplication, and "=" for equality), if the elements of X are exactly the numbers that satisfy φ.
That is, for all natural numbers n,
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the set of natural numbers.
Instead of formulas with one free variable, formulas with k free number variables are used to define the arithmetical hierarchy on sets of k-tuples of natural numbers.
These are in fact related by the use of a pairing function.
Relativized arithmetical hierarchies
Arithmetic reducibility and degrees
Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility.
The arithmetical hierarchy of subsets of Cantor and Baire space
There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables.
The arithmetical hierarchy can be defined on any effective Polish space; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second-order arithmetic.
Extensions and variations
Meaning of the notation
The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.
Examples
Properties
The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space.
Relation to Turing machines
See also: Post's theorem
Computable sets
If S is a Turing computable set, then both S and its complement are recursively enumerable (if T is a Turing machine giving 1 for inputs in S and 0 otherwise, we may build a Turing machine halting only on the former, and another halting only on the latter).
Summary of main results
Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees.
In particular, it establishes the following facts for all n ≥ 1:
Relation to other hierarchies
| Lightface | Boldface | ||
| Σ
0 = Π 0 = Δ 0 (sometimes the same as Δ 1) |
Σ
0 = Π 0 = Δ 0 (if defined) | ||
| Δ
1 = recursive |
Δ
1 = clopen | ||
| Σ | Π
1 = co-recursively enumerable |
Σ
1 = G = open |
Π
1 = F = closed |
| Δ
2 |
Δ
2 | ||
| Σ
2 |
Π
2 |
Σ
2 = Fσ |
Π
2 = Gδ |
| Δ
3 |
Δ
3 | ||
| Σ
3 |
Π
3 |
Σ
3 = Gδσ |
Π
3 = Fσδ |
| ⋮ | ⋮ | ||
| Σ
<ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = arithmetical |
Σ
<ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = boldface arithmetical | ||
| ⋮ | ⋮ | ||
| Δ
α (α recursive) |
Δ
α (α countable) | ||
| Σ
α |
Π
α |
Σ
α |
Π
α |
| ⋮ | ⋮ | ||
| Σ
ω 1 = Π ω 1 = Δ ω 1 = Δ 1 = hyperarithmetical |
Σ
ω1 = Π ω1 = Δ ω1 = Δ 1 = B = Borel | ||
| Σ
1 = lightface analytic |
Π
1 = lightface coanalytic |
Σ
1 = A = analytic |
Π
1 = CA = coanalytic |
| Δ
2 |
Δ
2 | ||
| Σ
2 |
Π
2 |
Σ
2 = PCA |
Π
2 = CPCA |
| Δ
3 |
Δ
3 | ||
| Σ
3 |
Π
3 |
Σ
3 = PCPCA |
Π
3 = CPCPCA |
| ⋮ | ⋮ | ||
| Σ
<ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = analytical |
Σ
<ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = P = projective | ||
| ⋮ | ⋮ | ||
See also
Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Arithmetical hierarchy.