Arithmetical hierarchy

From Free net encyclopedia

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. Layers in the hierarchy are defined as those formulas which satisfy a proposition (description) of a certain complexity.

The Tarski-Kuratowski algorithm provides an upper bound for the degree of solvability of an arithmetic formula.

1 Definition
2 Examples
3 Properties
4 Relation to Turing machines
5 See also
6 References

[edit]

Definition

The arithmetical hierarchy are three families of collections of sets (or formulas) called <math>\Pi^0_n</math>, <math>\Sigma^0_n</math>, and <math>\Delta^0_n</math>, for natural numbers n. The collections are recursively defined as

<math>\Sigma^0_0</math> is the collection of recursive sets

<math>\Sigma^0_{n+1}</math> is the collection of A-recursive sets for an <math>A \in \Sigma^0_n</math>

<math>\Pi^0_n</math> the collection of complements of A-recursive sets

<math>\Delta^0_n := \Sigma^0_n \cap \Pi^0_n</math>

Alternatively they can be defined as the collection of arithmetic formulas with a certain number of quantifiers. A formula is in the level <math>\Sigma^0_n</math> if it satisfies a proposition quantified first by <math>\exists</math>, and a total of n alternating existential (<math>\exists</math>) and universal (<math>\forall</math>) natural-number quantifiers; formulas are classified as <math>\Pi^0_n</math> in an equivalent fashion, except that the quantifiers commence with <math>\forall</math>. A set is <math>\Sigma^0_n</math> (resp. <math>\Pi^0_n</math>) if and only if it is definable by a formula of that complexity.

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

The superscript indicates the type of the objects being quantified over, 0 standing for the natural numbers. Quantification over a higher type, such as sets of natural numbers, is described by a superscript greater than 0, as in the analytical hierarchy. In other words, the superscript 0 indicates first-order logic, 1 stands for second-order logic, and so on.

[edit]

Examples

<math>\Sigma^0_0 = \Pi^0_0 = \Sigma^0_1 \cap \Pi^0_1</math>, the collection of recursive sets

<math>\Sigma^0_1</math> are those propositions with one existential quantifier, <math>\exists x_1 : </math> proposition holds. These are precisely the recursively enumerable sets.

Given a Gödel numbering <math>\varphi_i</math> then <math>\{i | \varphi_i \in \mathbf{R}^{(1)}\} \in \Pi^0_2</math> (the set of gödel numbers of the total computable functions with one parameter)

[edit]

Properties

the collections <math>\Pi^0_n</math> and <math>\Sigma^0_n</math> are closed under finite unions and finite intersections of their respective elements
<math>\Delta^0_n \subsetneq \Pi^0_n</math> and <math>\Delta^0_n \subsetneq \Sigma^0_n</math>
<math>\Pi^0_n \subsetneq \Pi^0_{n+1}</math> and <math>\Sigma^0_n \subsetneq \Sigma^0_{n+1}</math> (which means the hierarchy does not collapse)
<math>\Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1}</math>
<math>\emptyset^{(n)}</math> (the n-th Turing jump of the empty set) is m-complete in <math>\Sigma^0_n</math>
<math>\mathbb{N} \setminus \emptyset^{(n)}</math> is m-complete in <math>\Pi^0_n</math>
<math>\emptyset^{(n-1)}</math> is Turing complete in <math>\Delta^0_n</math>

[edit]

Relation to Turing machines

Suppose that there is an oracle machine capable of calculating all the functions in a level <math>\Delta^0_n</math>. This machine is incapable of solving its own halting problem (Turing's proof still applies). The halting problem for <math>\Delta^0_n</math> in fact sits in <math>\Delta^0_{n+1}</math>.

Post's theorem describes the close connection between the arithmetical hierarchy and the Turing degrees.

The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy, in which polynomial length bounds are placed on the strings involved, or equivalently, polynomial time bounds are placed on the Turing machines involved.

[edit]