Arithmetical hierarchy

Arithmetical hierarchy

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 hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets.

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" (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters.

If a formula phi is logically equivalent to a formula with only bounded quantifiers then phi 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 phi is logically equivalent to a formula of the form exists n_1 cdots exists n_k psi, where psi is Pi^0_n, then phi is assigned the classification Sigma^0_{n+1}.
*If phi is logically equivalent to a formula of the form forall n_l cdots forall n_k psi, where psi is Sigma^0_n, then phi 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.

The arithmetical hierarchy of sets of natural numbers

Say a set "X" is defined by formula φ(n) in the language of Peano arithmetic if n in X leftrightarrow mathbb{N} models phi(n). That is to say that the elements of "X" are exactly the numbers that satisfy φ. 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 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.

Relativized arithmetical hierarchies

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 Sigma^0_n, Delta^0_n or Pi^0_n in "Y", denoted respectively Sigma^{0,Y}_n Delta^{0,Y}_n and Pi^{0,Y}_n. To do so fix a set of integers "Y" and add a predicate for membership in "Y" to the language of Peano arithmetic. We then say that "X" is in Sigma^{0,Y}_n if it is defined by a Sigma^0_n formula in this expanded language. In other words "X" is Sigma^{0,Y}_n if it is defined by a Sigma^{0}_n formula allowed to ask questions about membership in "Y". Alternatively one can view the Sigma^{0,Y}_n sets as those sets that can be built starting with sets recursive in "Y" and alternatively projecting and taking the complements of these sets up to "n" times.

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

Arithmetic reducibility and degrees

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 Sigma^0_n or Pi^0_n for some integer "n". A set "X" is arithmetical in a set "Y", denoted X leq_A Y, if "X" is definable a some formula in the language of Peano arithmetic extended by a predicate for membership in "Y". Equivalently, "X" is arithmetical in "Y" if "X" is in Sigma^{0,Y}_n or Pi^{0,Y}_n for some integer "n". A synonym for X leq_A Yis: "X" is arithmetically reducible to "Y"

The relation X leq_A Y is reflexive and transitive, and thus the relation equiv_A defined by the rule

: X equiv_A Y Leftrightarrow X leq_A Y and Y leq_A Xis an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under leq_A.

The arithmetical hierarchy of subsets of Cantor and Baire space

The Cantor space, denoted 2^{omega}, is the set of all infinite sequences of 0s and 1s; the Baire space, denoted omega^{omega} or 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 integers and elements of the Baire space with functions from integers to integers.

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. For example let Osubset 2^{omega} be the set of all infinite binary strings which aren't all 0 (or equivalently the set of all non-empty sets of integers). As O={ Xin 2^omega | exists n (X(n)=1) } we see that O is defined by a Sigma^0_1 formula and hence is a Sigma^0_1 set.

Note that while both the elements of the Cantor space (regarded as sets of integers) and subsets of the Cantor space are classified in arithmetic hierarchies but these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non-trivial. For instance the Pi^0_n elements of the Cantor space are not (in general) the same as the elements X of the Cantor space so that {X} is a 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 omega to omega 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.

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

Extensions and variations

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

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.

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 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 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_delta 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 phi(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.

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 the set is both Sigma^0_n and Pi^0_n, in which case its complement will also be Delta^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.

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 is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for a Delta^{0,Y}_n oracle in fact sits in 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:
* The set emptyset^{(n)} (the "n"th 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.

See also

* Recursion theory
* Effective descriptive set theory
* Analytical hierarchy
* Interpretability logic
* Hierarchy (mathematics)

References

* [http://www.csc.villanova.edu/~japaridz/ G.Japaridze] , "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
*
* cite book | author=Rogers, H. | title= Theory of recursive functions and effective computability
publisher=McGraw-Hill | year=1967


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • arithmetical hierarchy — noun A classification of sets of natural numbers by the complexity of the formulas in the language of Peano arithmetic that define them, specifically by the number of alternations of A and E in the defining formula given the formula is in prenex… …   Wiktionary

  • Arithmetical set — In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.A function f:subseteq… …   Wikipedia

  • Hierarchy (mathematics) — In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of… …   Wikipedia

  • Polynomial hierarchy — In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co NP to oracle machines.DefinitionsThere are multiple equivalent definitions of the classes of the polynomial …   Wikipedia

  • Analytical hierarchy — In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them. The analytical hierarchy of… …   Wikipedia

  • Borel hierarchy — In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number… …   Wikipedia

  • Wadge hierarchy — In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge… …   Wikipedia

  • arithmetic hierarchy — noun arithmetical hierarchy …   Wiktionary

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”