Arithmetical hierarchy

From Wikipedia, the free encyclopedia

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene 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 analytical hierarchy extends the arithmetical hierarchy to classify additional formulas and sets.

1 The arithmetical hierarchy of formulas
2 The arithmetical hierarchy of sets of natural numbers
3 The arithmetical hierarchy of subsets of Cantor and Baire space
4 Extensions and variations
5 Meaning of the notation
6 Examples
7 Properties
8 Relation to Turing machines
9 See also
10 References

[edit] The arithmetical hierarchy of formulas

The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted $\Sigma^0_n$ and $\Pi^0_n$ for natural numbers n. The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.

If a formula $φ$ is logically equivalent to a formula with only bounded quantifiers then $φ$ is assigned the classifications $\Sigma^0_0$ and $\Pi^0_0$ .

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

If $φ$ is logically equivalent to a formula of the form $\exists n_1 \cdots \exists n_k \psi$ , where $ψ$ is $\Pi^0_n$ , then $φ$ is assigned the classification $\Sigma^0_{n+1}$ .
If $φ$ is logically equivalent to a formula of the form $\forall n_l \cdots \forall n_k \psi$ , where $ψ$ is $\Sigma^0_n$ , then $φ$ is assigned the classification $\Pi^0_{n+1}$ .

Because every formula is equivalent to a formula in prenex normal form, every formula with no set quantifiers is assigned at least one classification. Because meaningless quantifiers can be added to any formula, once a formula is assigned the classification $\Sigma^0_n$ or $\Pi^0_n$ it will be assigned the classifications $\Sigma^0_m$ and $\Pi^0_m$ for every m greater than n. The most important classification assigned to a formula is thus the one with the least n, because this is enough to determine all the other classifications.

[edit] The arithmetical hierarchy of sets of natural numbers

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

Note that it rarely makes sense to speak of $\Delta^0_n$ formulas; the first quantifier of a formula is either existential or universal. So a $\Delta^0_n$ set is not defined by a $\Delta^0_n$ formula; rather, there are both $\Sigma^0_n$ and $\Pi^0_n$ formulas that define the set.

A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the 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.

[edit] The arithmetical hierarchy of subsets of Cantor and Baire space

Cantor space is the set of all infinite sequences of 0s and 1s; Baire space is the set of all infinite sequences of 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 $\Sigma^0_n$ if it is definable by a $\Sigma^0_n$ formula. The set is assigned the classification $\Pi^0_n$ if it is definable by a $\Pi^0_n$ formula. If the set is both $\Sigma^0_n$ and $\Pi^0_n$ then it is given the additional classification $\Delta^0_n$ .

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 $ω$ to $ω$ to the characteristic function of its graph. A subset of Baire space is given the classification $\Sigma^1_n$ , $\Pi^1_n$ , or $\Delta^1_n$ if and only if the corresponding subset of Cantor space has the same classification.
An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second-order arithmetic; then the analytical 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.

[edit] Extensions and variations

The arithmetical hierarchy for formulas can be extended, using a parallel definition, to formulas in the language of Peano arithmetic with a set parameter added (that is, to formulas in the language of second-order arithmetic with no set quantifiers and a single set parameter). Thus a formula with parameter $A$ which meets the inductive definition for a $\Sigma^0_n$ formula is denoted $\Sigma^{0,A}_n$ , and the class $\Pi^{0,A}_n$ is defined similarly. For each set of natural numbers $Y$ we say that a set $X$ is $\Sigma^{0,Y}_n$ if $X$ is definable by a $\Sigma^{0,A}_n$ formula when the symbol $A$ is interpreted as $Y$ . The classes $\Pi^{0,Y}_n$ and $\Delta^{0,Y}_n$ are defined similarly. The hierarchy consisting of $\Sigma^{0,Y}_n$ , $\Pi^{0,Y}_n$ , and $\Delta^{0,Y}_n$ for every natural number $n$ and every set of natural numbers $Y$ is called the relativized arithmetical hierarchy.

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 some sets.

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 $\Sigma^0_0$ and $\Pi^0_0$ . The classifications $\Sigma^0_n$ and $\Pi^0_n$ are defined inductively with the following rules.

If the relation $R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,$ is $\Sigma^0_n$ then the relation $S(n_1,\ldots, n_l) = \forall m_1\cdots \forall m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)$ is defined to be $\Pi^0_{n+1}$
If the relation $R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,$ is $\Pi^0_n$ then the relation $S(n_1,\ldots,n_l) = \exists m_1\cdots \exists m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)$ is defined to be $\Sigma^0_{n+1}$

This variation slightly changes the classification of some sets. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.

[edit] Meaning of the notation

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

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

The superscript $0$ in the symbols $\Sigma^0_n$ , $\Pi^0_n$ , and $\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.

[edit] Examples

The $\Sigma^0_1$ sets of numbers are those definable by a formula of the form $\exists n_1 \cdots \exists n_k \psi(n_1,\ldots,n_k,m)$ where $ψ$ 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 $\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 $\Sigma^0_1$ formula.

Every $\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, $\Sigma^0_1$ sets are sometimes called effectively open. Similarly, every $\Pi^0_1$ set is closed and the $\Pi^0_1$ sets are sometimes called effectively closed.

Every arithmetical subset of Cantor space of Baire space is a Borel set. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every $\Pi^0_2$ subset of Cantor or Baire space is a $G δ$ set (that is, a set which equals the intersection of countably many open sets). Moreover, each of these open sets is $\Sigma^0_1$ and the list of Gödel numbers of these open sets has a computable enumeration. If $φ(X, n, m)$ is a $\Sigma^0_0$ formula with a free set variable X and free number variables $n, m$ then the $\Pi^0_2$ set $\{X \mid \forall n \exists m \phi(X,n,m)\}$ is the intersection of the $\Sigma^0_1$ sets of the form $\{ X \mid \exists m \phi(X,n,m)\}$ as n ranges over the set of natural numbers.

[edit] 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.

The collections $\Pi^0_n$ and $\Sigma^0_n$ are closed under finite unions and finite intersections of their respective elements.
A set is $\Sigma^0_n$ if and only if its complement is $\Pi^0_n$ . A set is $\Delta^0_n$ if and only if both the set and its complement are both $\Sigma^0_n$ and $\Pi^0_n$ .
The inclusions $\Delta^0_n \subsetneq \Pi^0_n$ and $\Delta^0_n \subsetneq \Sigma^0_n$ hold for $n \geq 1$
The inclusions $\Pi^0_n \subsetneq \Pi^0_{n+1}$ and $\Sigma^0_n \subsetneq \Sigma^0_{n+1}$ hold for all $n$ and the inclusion $\Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1}$ holds for $n \geq 1$ . Thus the hierarchy does not collapse.

[edit] Relation to Turing machines

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

No oracle machine capable of deciding all the sets in a level $\Delta^0_n$ of the arithmetical hierarchy for sets of natural numbers is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for $\Delta^0_n$ in fact sits in $\Sigma^0_{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:

The set $\emptyset^{(n)}$ (the nth Turing jump of the empty set) is many-one complete in $\Sigma^0_n$ .
The set $\mathbb{N} \setminus \emptyset^{(n)}$ is many-one complete in $\Pi^0_n$ .
The set $\emptyset^{(n-1)}$ is Turing complete in $\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 $\Delta^0_1$ of the arithmetical hierarchy.

[edit] See also

[edit] References

G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0.
Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill.

Retrieved from "http://en.wikipedia.org../../../a/r/i/Arithmetical_hierarchy.html"

Categories: Mathematical logic | Recursion theory | Effective descriptive set theory | Hierarchy