arithmetical hierarchy

The arithmetical hierarchy is a hierarchy of either (depending on the context) formulasMathworldPlanetmathPlanetmath or relationsMathworldPlanetmath. The relations of a particular level of the hierarchy are exactly the relations defined by the formulas of that level, so the two uses are essentially the same.

The first level consists of formulas with only bounded quantifiers, the corresponding relations are also called the Primitive Recursive relations (this definition is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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:

 where Q is either  or , whichever maintains the pattern of alternating quantifiers

The Σ10 relations are the same as the Recursively Enumerable relations.

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

 where Q is either  or , whichever maintains the pattern of alternating quantifiers

A formula is Δn0 if it is both Σn0 and Πn0. Since each Σn0 formula is just the negationMathworldPlanetmath of a Πn0 formula and vice-versa, the Σn0 relations are the complementsPlanetmathPlanetmath 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.

Title arithmetical hierarchy
Canonical name ArithmeticalHierarchy
Date of creation 2013-03-22 12:55:11
Last modified on 2013-03-22 12:55:11
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 19
Author CWoo (3771)
Entry type Definition
Classification msc 03B10
Synonym arithmetic hierarchy
Synonym arithmetic
Synonym arithmetical
Synonym arithmetic formula
Synonym arithmetical formulas
Related topic AnalyticHierarchy
Defines sigma n
Defines sigma-n
Defines pi n
Defines pi-n
Defines delta n
Defines delta-n
Defines recursive
Defines recursively enumerable
Defines delta-0
Defines delta 0
Defines delta-1
Defines delta 1
Defines arithmetical