NationMaster - Encyclopedia: Arithmetical hierarchy

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. Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ... In mathematical logic an arithmetic set or arithmetical set is a countable set which can be defined by a formula of first order arithmetic. ... Proposition is a term used in logic to describe the content of assertions. ...

The Tarski-Kuratowski algorithm provides an upper bound for the degree of solvability of an arithmetic formula. In computability theory and mathematical logic the Tarskiâ€“Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of arithmetic formulas. ...

1 Definition
2 Examples
3 Properties
4 Relation to Turing machines

Definition

The arithmetical hierarchy are three families of collections of sets (or formulas) called $Pi^0_n$ , $Sigma^0_n$ , and $Delta^0_n$ , for natural numbers n. The collections are recursively defined as In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory. ...

$Sigma^0_0$ is the collection of recursive sets

$Sigma^0_{n+1}$ is the collection of A-recursive sets for an $A in Sigma^0_n$

$Pi^0_n$ the collection of co-A-recursive sets

$Delta^0_n := Sigma^0_n cap Pi^0_n$

Alternatively they can be defined as the collection of arithmetic formulas with a certain number of quantifiers. A formula is in the level $Sigma^0_n$ if it satisfies a proposition quantified first by $exists$ , and a total of n alternating existential ( $exists$ ) and universal ( $forall$ ) natural-number quantifiers; formulas are classified as $Pi^0_n$ in an equivalent fashion, except that the quantifiers commence with $forall$ . A set is $Sigma^0_n$ (resp. $Pi^0_n$ ) if and only if it is definable by a formula of that complexity. In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ... In computability theory relative computability or relativized computability is the study of computability concepts relative to a given set. ... In computability theory relative computability or relativized computability is the study of computability concepts relative to a given set. ... In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. ... In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ...

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 is a $Sigma^0_n$ formula and a $Pi^0_n$ formula, which both happen to define the set in question.

Examples

$Sigma^0_0 = Pi^0_0 = Sigma^0_1 cap Pi^0_1$ , the collection of recursive sets

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

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

In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if it... In formal number theory a GÃ¶del numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a GÃ¶del number (GN). ... In formal number theory a GÃ¶del numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a GÃ¶del number (GN). ... In computability theory computable functions or Turing computable functions are the basic objects of study. ...

Properties

the collections $Pi^0_n$ and $Sigma^0_n$ are closed under union and intersection of their respective elements
$Delta^0_n subset Pi^0_n$ and $Delta^0_n subset Sigma^0_n$
$Pi^0_n subset Pi^0_{n+1}$ and $Sigma^0_n subset Sigma^0_{n+1}$ (which means the hierarchy does not collapse)
$Sigma^0_n cup Pi^0_n subset Delta^0_{n+1}$
$emptyset^{(n)}$ (the n-th Turing jump of the empty set) is m-complete in $Sigma^0_n$
$mathbb{N} setminus emptyset^{(n)}$ is m-complete in $Pi^0_n$
$emptyset^{(n-1)}$ is Turing complete in $Delta^0_n$

In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... In computability theory, the Turing degree of a subset of the natural numbers , is the equivalence class consisting of all subsets of equivalent to under Turing reducibility. ... In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. If we have an algorithm N which solves instances of B, we can use it to solve instances of A in: the time... In computability theory, a Turing reduction from a problem A to a problem B is, intuitively, a reduction which easily solves A, assuming B is easy to solve. ...

Relation to Turing machines

Suppose that there is an oracle machine capable of calculating all the functions in a level $Delta^0_n$ . This machine is incapable of solving its own halting problem (Turing's proof still applies). The halting problem for $Delta^0_n$ in fact sits in $Delta^0_{n+1}$ . In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...

Post's theorem describes the close connection between the arithmetical hierarchy and the Turing degrees. In computability theory Posts theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. ... In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ...

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

Results from FactBites:

"Associative Digital Network Theory" - book preface, Nico F. Benschop (1026 words)
	Known principles of discrete mathematics, especially finite semigroups, residue arithmetic and boolean logic (lattices) are interpreted in terms of practical DN design issues.
	Historically, non-commutative and idempotent algebras diverged from arithmetic in the nineteenth century.
	Our aim is to emphasize again their arithmetic nature, for practical engineering purposes such as efficient synthesis of binary logic and state machines.

PlanetMath: arithmetical hierarchy (246 words)
	The arithmetical hierarchy is a hierarchy of either (depending on the context) formulas or relations.
	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.
	This is version 14 of arithmetical hierarchy, born on 2002-08-06, modified 2003-12-11.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m

Contents

Definition GA_googleFillSlot("encyclopedia_square");

Examples

Properties

Relation to Turing machines

Definition