Arithmetical hierarchy

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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 formulas Arithmetical hierarchy_section_0

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

Relativized arithmetical hierarchies Arithmetical hierarchy_section_2

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

Extensions and variations Arithmetical hierarchy_section_5

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

Examples Arithmetical hierarchy_section_7

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

See also: Post's theorem Arithmetical hierarchy_sentence_16

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 = Arithmetical hierarchy_cell_0_5_2

Π

2 = 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

See also Arithmetical hierarchy_section_13

Arithmetical hierarchy_unordered_list_0


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Arithmetical hierarchy.