arithmetical hierarchy#The arithmetical hierarchy of formulas

The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain {{Clarify|text=set parameters.|date=August 2024}}

If a formula $\backslash phi$ is logically equivalent to a formula having no unbounded quantifiers, i.e. in which all quantifiers are bounded quantifiers then $\backslash phi$ is assigned the classifications $\backslash Sigma^0\_0$ and $\backslash Pi^0\_0$.

The classifications $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ are defined inductively for every natural number n using the following rules:

• If $\backslash phi$ is logically equivalent to a formula of the form $\backslash exists\; m\_1\; \backslash exists\; m\_2\backslash cdots\; \backslash exists\; m\_k\; \backslash psi$, where $\backslash psi$ is $\backslash Pi^0\_n$, then $\backslash phi$ is assigned the classification $\backslash Sigma^0\_\{n+1\}$.
• If $\backslash phi$ is logically equivalent to a formula of the form $\backslash forall\; m\_1\; \backslash forall\; m\_2\backslash cdots\; \backslash forall\; m\_k\; \backslash psi$, where $\backslash psi$ is $\backslash Sigma^0\_n$, then $\backslash phi$ is assigned the classification $\backslash Pi^0\_\{n+1\}$.

A $\backslash Sigma^0\_n$ formula is equivalent to a formula that begins with some existential quantifiers and alternates $n-1$ times between series of existential and universal quantifiers; while a $\backslash Pi^0\_n$ formula is equivalent to a formula that begins with some universal quantifiers and alternates analogously.

Because every first-order formula has a prenex normal form, every formula is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned the classification $\backslash Sigma^0\_n$ or $\backslash Pi^0\_n$ it will be assigned the classifications $\backslash Sigma^0\_m$ and $\backslash Pi^0\_m$ for every m > n. The only relevant classification assigned to a formula is thus the one with the least n; all the other classifications can be determined from it.

A set X of natural numbers is defined by a 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,

:$n\; \backslash in\; X\; \backslash Leftrightarrow\; \backslash mathbb\{N\}\; \backslash models\; \backslash varphi(\backslash underline\; n),$

where $\backslash underline\; n$ is the numeral in the language of arithmetic corresponding to $n$. A set is definable in first-order arithmetic if it is defined by some formula in the language of Peano arithmetic.

Each set X of natural numbers that is definable in first-order arithmetic is assigned classifications of the form $\backslash Sigma^0\_n$, $\backslash Pi^0\_n$, and $\backslash Delta^0\_n$, where $n$ is a natural number, as follows. If X is definable by a $\backslash Sigma^0\_n$ formula then X is assigned the classification $\backslash Sigma^0\_n$. If X is definable by a $\backslash Pi^0\_n$ formula then X is assigned the classification $\backslash Pi^0\_n$. If X is both $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ then $X$ is assigned the additional classification $\backslash Delta^0\_n$.

Note that it rarely makes sense to speak of $\backslash Delta^0\_n$ formulas; the first quantifier of a formula is either existential or universal. So a $\backslash Delta^0\_n$ set is not necessarily defined by a $\backslash Delta^0\_n$ formula in the sense of a formula that is both $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$; rather, there are both $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ formulas that define the set. For example, the set of odd natural numbers $n$ is definable by either $\backslash forall\; k(n\backslash neq\; 2\backslash times\; k)$ or $\backslash exists\; k(n=2\backslash times\; k+1)$.

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 first-order 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.

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

The subscript $n$ in the symbols $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ indicates the number of alternations of blocks of universal and existential first-order quantifiers that are used in a formula. Moreover, the outermost block is existential in $\backslash Sigma^0\_n$ formulas and universal in $\backslash Pi^0\_n$ formulas.

The superscript $0$ in the symbols $\backslash Sigma^0\_n$, $\backslash Pi^0\_n$, and $\backslash Delta^0\_n$ indicates the type of the objects being quantified over. Type 0 objects are natural numbers, and objects of type $i+1$ are functions that map the set of objects of type $i$ to the natural numbers. Quantification over higher type objects, such as functions from natural numbers to natural numbers, is described by a superscript greater than 0, as in the analytical hierarchy. The superscript 0 indicates quantifiers over numbers, the superscript 1 would indicate quantification over functions from numbers to numbers (type 1 objects), the superscript 2 would correspond to quantification over functions that take a type 1 object and return a number, and so on.

• The $\backslash Sigma^0\_1$ sets of numbers are those definable by a formula of the form $\backslash exists\; n\_1\; \backslash cdots\; \backslash exists\; n\_k\; \backslash psi(n\_1,\backslash ldots,n\_k,m)$ where $\backslash psi$ has only bounded quantifiers. These are exactly the recursively enumerable sets.
• The set of natural numbers that are indices for Turing machines that compute total functions is $\backslash Pi^0\_2$. Intuitively, an index $e$ falls into this set if and only if for every $m$ "there is an $s$ such that the Turing machine with index $e$ halts on input $m$ after $s$ steps". A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of Peano arithmetic by a $\backslash Sigma^0\_1$ formula.
• Every $\backslash Sigma^0\_1$ subset of Baire space or Cantor space is an open set in the usual topology on the space. Moreover, for any such set there is a computable enumeration of Gödel numbers of basic open sets whose union is the original set. For this reason, $\backslash Sigma^0\_1$ sets are sometimes called effectively open. Similarly, every $\backslash Pi^0\_1$ set is closed and the $\backslash Pi^0\_1$ sets are sometimes called effectively closed.
• Every arithmetical subset of Cantor space or Baire space is a Borel set. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every $\backslash Pi^0\_2$ subset of Cantor or Baire space is a $G\_\backslash delta$ set, that is, a set that equals the intersection of countably many open sets. Moreover, each of these open sets is $\backslash Sigma^0\_1$ and the list of Gödel numbers of these open sets has a computable enumeration. If $\backslash phi(X,n,m)$ is a $\backslash Sigma^0\_0$ formula with a free set variable $X$ and free number variables $n,m$ then the $\backslash Pi^0\_2$ set $\backslash \{X\; \backslash mid\; \backslash forall\; n\; \backslash exists\; m\; \backslash phi(X,n,m)\backslash \}$ is the intersection of the $\backslash Sigma^0\_1$ sets of the form $\backslash \{\; X\; \backslash mid\; \backslash exists\; m\; \backslash phi(X,n,m)\backslash \}$ as $n$ ranges over the set of natural numbers.
• The $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$ formulas can be checked by going over all cases one by one, which is possible because all their quantifiers are bounded. The time for this is polynomial in their arguments (e.g. polynomial in $n$ for $\backslash varphi(n)$); thus their corresponding decision problems are included in E (as $n$ is exponential in its number of bits). This no longer holds under alternative definitions of $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$ that allow the use of primitive recursive functions, as now the quantifiers may be bounded by any primitive recursive function of the arguments.
• The $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$ formulas under an alternative definition, that allows the use of primitive recursive functions with bounded quantifiers, correspond to sets of natural numbers of the form $\backslash \{n:\; f(n)\; =\; 0\backslash \}$ for a primitive recursive function $f$. This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive $f$,

Just as we can define what it means for a set X to be recursive relative to another set Y by allowing the computation defining X to consult Y as an oracle we can extend this notion to the whole arithmetic hierarchy and define what it means for X to be $\backslash Sigma^0\_n$, $\backslash Delta^0\_n$ or $\backslash Pi^0\_n$ in Y, denoted respectively $\backslash Sigma^\{0,Y\}\_n$, $\backslash Delta^\{0,Y\}\_n$ and $\backslash Pi^\{0,Y\}\_n$. To do so, fix a set of natural numbers Y and add a predicate for membership of Y to the language of Peano arithmetic. We then say that X is in $\backslash Sigma^\{0,Y\}\_n$ if it is defined by a $\backslash Sigma^0\_n$ formula in this expanded language. In other words, X is $\backslash Sigma^\{0,Y\}\_n$ if it is defined by a $\backslash Sigma^\{0\}\_n$ formula allowed to ask questions about membership of Y. Alternatively one can view the $\backslash Sigma^\{0,Y\}\_n$ sets as those sets that can be built starting with sets recursive in Y and alternately taking unions and intersections of these sets up to n times.

For example, let Y be a set of natural numbers. Let X be the set of numbers divisible by an element of Y. Then X is defined by the formula $\backslash phi(n)=\backslash exists\; m\; \backslash exists\; t\; (Y(m)\backslash land\; m\backslash times\; t\; =\; n)$ so X is in $\backslash Sigma^\{0,Y\}\_1$ (actually it is in $\backslash Delta^\{0,Y\}\_0$ as well, since we could bound both quantifiers by n).

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

A set is arithmetical (also arithmetic and arithmetically definable) if it is defined by some formula in the language of Peano arithmetic. Equivalently X is arithmetical if X is $\backslash Sigma^0\_n$ or $\backslash Pi^0\_n$ for some natural number n. A set X is arithmetical in a set Y, denoted $X\; \backslash leq\_A\; Y$, if X is definable as some formula in the language of Peano arithmetic extended by a predicate for membership of Y. Equivalently, X is arithmetical in Y if X is in $\backslash Sigma^\{0,Y\}\_n$ or $\backslash Pi^\{0,Y\}\_n$ for some natural number n. A synonym for $X\; \backslash leq\_A\; Y$ is: X is arithmetically reducible to Y.

The relation $X\; \backslash leq\_A\; Y$ is reflexive and transitive, and thus the relation $\backslash equiv\_A$ defined by the rule

:$X\; \backslash equiv\_A\; Y\; \backslash iff\; X\; \backslash leq\_A\; Y\; \backslash land\; Y\; \backslash leq\_A\; X$

is an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under $\backslash leq\_A$.

The Cantor space, denoted $2^\{\backslash omega\}$, is the set of all infinite sequences of 0s and 1s; the Baire space, denoted $\backslash omega^\{\backslash omega\}$ or $\backslash mathcal\{N\}$, is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers.

The ordinary axiomatization of second-order arithmetic uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification $\backslash Sigma^0\_n$ if it is definable by a $\backslash Sigma^0\_n$ formula. The set is assigned the classification $\backslash Pi^0\_n$ if it is definable by a $\backslash Pi^0\_n$ formula. If the set is both $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ then it is given the additional classification $\backslash Delta^0\_n$. For example, let $O\backslash subseteq\; 2^\{\backslash omega\}$ be the set of all infinite binary strings that aren't all 0 (or equivalently the set of all non-empty sets of natural numbers). As $O=\backslash \{\; X\backslash in\; 2^\backslash omega\; |\; \backslash exists\; n\; (X(n)=1)\; \backslash \}$ we see that $O$ is defined by a $\backslash Sigma^0\_1$ formula and hence is a $\backslash Sigma^0\_1$ set.

Note that while both the elements of the Cantor space (regarded as sets of natural numbers) and subsets of the Cantor space are classified in arithmetic hierarchies, these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the $\backslash Pi^0\_n$ elements of the Cantor space are not (in general) the same as the elements $X$ of the Cantor space so that $\backslash \{X\backslash \}$ is a $\backslash Pi^0\_n$ subset of the Cantor space. However, many interesting results relate the two hierarchies.

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

• A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from $\backslash omega$ to $\backslash omega$ to the characteristic function of its graph. A subset of Baire space is given the classification $\backslash Sigma^0\_n$, $\backslash Pi^0\_n$, or $\backslash Delta^0\_n$ if and only if the corresponding subset of Cantor space has the same classification.
• An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second-order arithmetic; then the arithmetical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition.

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.

Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of natural numbers. In fact boldface $\backslash mathbf\{\backslash Sigma\}^0\_n$ is just the union of $\backslash Sigma^\{0,Y\}\_n$ for all sets of natural numbers Y. Note that the boldface hierarchy is just the standard hierarchy of Borel sets.

It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for each primitive recursive function. This variation slightly changes the classification of $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$, since using primitive recursive functions in first-order Peano arithmetic requires, in general, an unbounded existential quantifier, and thus some sets that are in $\backslash Sigma^0\_0$ by this definition are strictly in $\backslash Sigma^0\_1$ by the definition given in the beginning of this article. The class $\backslash Sigma^0\_1$ and thus all higher classes in the hierarchy remain unaffected.

A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used. Every computable relation is defined to be $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$. The classifications $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ are defined inductively with the following rules.

• If the relation $R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,\; m\_k)\backslash ,$ is $\backslash Sigma^0\_n$ then the relation $S(n\_1,\backslash ldots,\; n\_l)\; =\; \backslash forall\; m\_1\backslash cdots\; \backslash forall\; m\_k\; R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,m\_k)$ is defined to be $\backslash Pi^0\_\{n+1\}$
• If the relation $R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,\; m\_k)\backslash ,$ is $\backslash Pi^0\_n$ then the relation $S(n\_1,\backslash ldots,n\_l)\; =\; \backslash exists\; m\_1\backslash cdots\; \backslash exists\; m\_k\; R(n\_1,\backslash ldots,n\_l,m\_1,\backslash ldots,m\_k)$ is defined to be $\backslash Sigma^0\_\{n+1\}$

This variation slightly changes the classification of some sets. In particular, $\backslash Sigma^0\_0=\backslash Pi^0\_0=\backslash Delta^0\_0$, as a class of sets (definable by the relations in the class), is identical to $\backslash Delta^0\_1$ as the latter was formerly defined. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.

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

• The collections $\backslash Pi^0\_n$ and $\backslash Sigma^0\_n$ are closed under finite unions and finite intersections of their respective elements.
• A set is $\backslash Sigma^0\_n$ if and only if its complement is $\backslash Pi^0\_n$. A set is $\backslash Delta^0\_n$ if and only if the set is both $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$, in which case its complement will also be $\backslash Delta^0\_n$.
• The inclusions $\backslash Pi^0\_n\; \backslash subsetneq\; \backslash Pi^0\_\{n+1\}$ and $\backslash Sigma^0\_n\; \backslash subsetneq\; \backslash Sigma^0\_\{n+1\}$ hold for all $n$. Thus the hierarchy does not collapse. This is a direct consequence of Post's theorem.
• The inclusions $\backslash Delta^0\_n\; \backslash subsetneq\; \backslash Pi^0\_n$, $\backslash Delta^0\_n\; \backslash subsetneq\; \backslash Sigma^0\_n$ and $\backslash Sigma^0\_n\; \backslash cup\; \backslash Pi^0\_n\; \backslash subsetneq\; \backslash Delta^0\_\{n+1\}$ hold for $n\; \backslash geq\; 1$.

:*For example, for a universal Turing machine T, the set of pairs (n,m) such that T halts on n but not on m, is in $\backslash Delta^0\_2$ (being computable with an oracle to the halting problem) but not in $\backslash Sigma^0\_1\; \backslash cup\; \backslash Pi^0\_1$.

:*$\backslash Sigma^0\_0\; =\; \backslash Pi^0\_0\; =\; \backslash Delta^0\_0\; =\; \backslash Sigma^0\_0\; \backslash cup\; \backslash Pi^0\_0\; \backslash subseteq\; \backslash Delta^0\_1$. The inclusion is strict by the definition given in this article, but an identity with $\backslash Delta^0\_1$ holds under one of the variations of the definition given above.

{{See also|Post's theorem}}

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

By Post's theorem, both S and its complement are in $\backslash Sigma^0\_1$. This means that S is both in $\backslash Sigma^0\_1$ and in $\backslash Pi^0\_1$, and hence it is in $\backslash Delta^0\_1$.

Similarly, for every set S in $\backslash Delta^0\_1$, both S and its complement are in $\backslash Sigma^0\_1$ and are therefore (by Post's theorem) recursively enumerable by some Turing machines T₁ and T₂, respectively. For every number n, exactly one of these halts. We may therefore construct a Turing machine T that alternates between T₁ and T₂, halting and returning 1 when the former halts or halting and returning 0 when the latter halts. Thus T halts on every n and returns whether it is in S; so S is computable.

The Turing computable sets of natural numbers are exactly the sets at level $\backslash Delta^0\_1$ of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level $\backslash Sigma^0\_1$.

No oracle machine is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for a $\backslash Delta^\{0,Y\}\_n$ oracle in fact sits in $\backslash Sigma^\{0,Y\}\_\{n+1\}$.

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:

• The set $\backslash emptyset^\{(n)\}$ (the nth Turing jump of the empty set) is many-one complete in $\backslash Sigma^0\_n$.
• The set $\backslash mathbb\{N\}\; \backslash setminus\; \backslash emptyset^\{(n)\}$ is many-one complete in $\backslash Pi^0\_n$.
• The set $\backslash emptyset^\{(n-1)\}$ is Turing complete in $\backslash Delta^0\_n$.

The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved). It gives a finer classification of some sets of natural numbers that are at level $\backslash Delta^0\_1$ of the arithmetical hierarchy.

{{pointclasses}}

• Analytical hierarchy
• Lévy hierarchy
• Hierarchy (mathematics)
• Interpretability logic
• Polynomial hierarchy

{{Reflist}}

{{refbegin}}

• {{citation |first=Giorgie |last=Japaridze |author-link = Giorgi Japaridze|title=The logic of arithmetical hierarchy |journal=Annals of Pure and Applied Logic |volume=66 |issue=2 |year=1994 |pages=89–112 |doi = 10.1016/0168-0072(94)90063-9 |zbl = 0804.03045 }}.
• {{citation |last=Moschovakis |first=Yiannis N. |author-link=Yiannis N. Moschovakis |title=Descriptive Set Theory |publisher=North Holland |year=1980 |isbn=0-444-70199-0 |zbl = 0433.03025 |series = Studies in Logic and the Foundations of Mathematics |volume =100 }}.
• {{citation |last=Nies |first=André |title = Computability and randomness |series = Oxford Logic Guides |volume=51 |location=Oxford |publisher=Oxford University Press |year=2009 |isbn=978-0-19-923076-1 |zbl = 1169.03034 }}.
• {{citation |last=Rogers |first = H. Jr. |author-link = Hartley Rogers Jr.|title = Theory of recursive functions and effective computability |publisher=McGraw-Hill | year=1967 |zbl = 0183.01401 |location=Maidenhead }}.

{{refend}}

{{-}}

{{ComplexityClasses}}

Category:Mathematical logic hierarchies

Category:Computability theory

Category:Effective descriptive set theory

Category:Hierarchy

Category:Complexity classes