# Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or KleeneMostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Arithmetical hierarchy_sentence_0

Any set that receives a classification is called arithmetical. Arithmetical hierarchy_sentence_1

The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic. Arithmetical hierarchy_sentence_2

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. Arithmetical hierarchy_sentence_3

The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets. Arithmetical hierarchy_sentence_4

## The arithmetical hierarchy of sets of natural numbers Arithmetical hierarchy_section_1

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 φ. Arithmetical hierarchy_sentence_5

That is, for all natural numbers n, Arithmetical hierarchy_sentence_6

A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the set of natural numbers. Arithmetical hierarchy_sentence_7

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. Arithmetical hierarchy_sentence_8

These are in fact related by the use of a pairing function. Arithmetical hierarchy_sentence_9

## Arithmetic reducibility and degrees Arithmetical hierarchy_section_3

Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility. Arithmetical hierarchy_sentence_10

## The arithmetical hierarchy of subsets of Cantor and Baire space Arithmetical hierarchy_section_4

There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy. Arithmetical hierarchy_sentence_11

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. Arithmetical hierarchy_sentence_12

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. Arithmetical hierarchy_sentence_13

## Meaning of the notation Arithmetical hierarchy_section_6

The following meanings can be attached to the notation for the arithmetical hierarchy on formulas. Arithmetical hierarchy_sentence_14

## Properties Arithmetical hierarchy_section_8

The following properties hold for the arithmetical hierarchy of sets of natural numbers and the arithmetical hierarchy of subsets of Cantor or Baire space. Arithmetical hierarchy_sentence_15

## Relation to Turing machines Arithmetical hierarchy_section_9

### Computable sets Arithmetical hierarchy_section_10

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). Arithmetical hierarchy_sentence_17

### Summary of main results Arithmetical hierarchy_section_11

Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees. Arithmetical hierarchy_sentence_18

In particular, it establishes the following facts for all n ≥ 1: Arithmetical hierarchy_sentence_19

## Relation to other hierarchies Arithmetical hierarchy_section_12

Arithmetical hierarchy_table_general_0

 LightfaceArithmetical hierarchy_cell_0_0_0 BoldfaceArithmetical hierarchy_cell_0_0_2 Σ 0 = Π 0 = Δ 0 (sometimes the same as Δ 1)Arithmetical hierarchy_cell_0_1_0 Σ 0 = Π 0 = Δ 0 (if defined)Arithmetical hierarchy_cell_0_1_2 Δ 1 = recursiveArithmetical hierarchy_cell_0_2_0 Δ 1 = clopenArithmetical hierarchy_cell_0_2_2 Σ 1 = recursively enumerableArithmetical hierarchy_cell_0_3_0 Π 1 = co-recursively enumerableArithmetical hierarchy_cell_0_3_1 Σ 1 = G = openArithmetical hierarchy_cell_0_3_2 Π 1 = F = closedArithmetical hierarchy_cell_0_3_3 Δ 2Arithmetical hierarchy_cell_0_4_0 Δ 2Arithmetical hierarchy_cell_0_4_2 Σ 2Arithmetical hierarchy_cell_0_5_0 Π 2Arithmetical hierarchy_cell_0_5_1 Σ 2 = FσArithmetical hierarchy_cell_0_5_2 Π 2 = GδArithmetical hierarchy_cell_0_5_3 Δ 3Arithmetical hierarchy_cell_0_6_0 Δ 3Arithmetical hierarchy_cell_0_6_2 Σ 3Arithmetical hierarchy_cell_0_7_0 Π 3Arithmetical hierarchy_cell_0_7_1 Σ 3 = GδσArithmetical hierarchy_cell_0_7_2 Π 3 = FσδArithmetical hierarchy_cell_0_7_3 ⋮Arithmetical hierarchy_cell_0_8_0 ⋮Arithmetical hierarchy_cell_0_8_2 Σ <ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = arithmeticalArithmetical hierarchy_cell_0_9_0 Σ <ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = boldface arithmeticalArithmetical hierarchy_cell_0_9_2 ⋮Arithmetical hierarchy_cell_0_10_0 ⋮Arithmetical hierarchy_cell_0_10_2 Δ α (α recursive)Arithmetical hierarchy_cell_0_11_0 Δ α (α countable)Arithmetical hierarchy_cell_0_11_2 Σ αArithmetical hierarchy_cell_0_12_0 Π αArithmetical hierarchy_cell_0_12_1 Σ αArithmetical hierarchy_cell_0_12_2 Π αArithmetical hierarchy_cell_0_12_3 ⋮Arithmetical hierarchy_cell_0_13_0 ⋮Arithmetical hierarchy_cell_0_13_2 Σ ω 1 = Π ω 1 = Δ ω 1 = Δ 1 = hyperarithmeticalArithmetical hierarchy_cell_0_14_0 Σ ω1 = Π ω1 = Δ ω1 = Δ 1 = B = BorelArithmetical hierarchy_cell_0_14_2 Σ 1 = lightface analyticArithmetical hierarchy_cell_0_15_0 Π 1 = lightface coanalyticArithmetical hierarchy_cell_0_15_1 Σ 1 = A = analyticArithmetical hierarchy_cell_0_15_2 Π 1 = CA = coanalyticArithmetical hierarchy_cell_0_15_3 Δ 2Arithmetical hierarchy_cell_0_16_0 Δ 2Arithmetical hierarchy_cell_0_16_2 Σ 2Arithmetical hierarchy_cell_0_17_0 Π 2Arithmetical hierarchy_cell_0_17_1 Σ 2 = PCAArithmetical hierarchy_cell_0_17_2 Π 2 = CPCAArithmetical hierarchy_cell_0_17_3 Δ 3Arithmetical hierarchy_cell_0_18_0 Δ 3Arithmetical hierarchy_cell_0_18_2 Σ 3Arithmetical hierarchy_cell_0_19_0 Π 3Arithmetical hierarchy_cell_0_19_1 Σ 3 = PCPCAArithmetical hierarchy_cell_0_19_2 Π 3 = CPCPCAArithmetical hierarchy_cell_0_19_3 ⋮Arithmetical hierarchy_cell_0_20_0 ⋮Arithmetical hierarchy_cell_0_20_2 Σ <ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = analyticalArithmetical hierarchy_cell_0_21_0 Σ <ω = Π <ω = Δ <ω = Σ 0 = Π 0 = Δ 0 = P = projectiveArithmetical hierarchy_cell_0_21_2 ⋮Arithmetical hierarchy_cell_0_22_0 ⋮Arithmetical hierarchy_cell_0_22_2