HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians
Stephen Cole Kleene Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
and Andrzej Mostowski) classifies certain sets based on the
complexity Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generall ...
of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy is important in
recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
,
effective descriptive set theory Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive ...
, and the study of formal theories such as
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
. 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 In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an importa ...
and the
analytical hierarchy In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
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 In first-order logic, a first-order theory is given by a set of axioms in some language. This entry lists some of the more common examples used in model theory and some of their properties. Preliminaries For every natural mathematical structure ...
. The classifications are denoted \Sigma^0_n and \Pi^0_n for natural numbers ''n'' (including 0). The Greek letters here are
lightface In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
symbols, which indicates that the formulas do not contain set parameters. If a formula \phi is logically equivalent to a formula without quantifiers, then \phi is assigned the classifications \Sigma^0_0 and \Pi^0_0. Since any formula with
bounded quantifier In the study of formal theories in mathematical logic, bounded quantifiers (a.k.a. restricted quantifiers) are often included in a formal language in addition to the standard quantifiers "∀" and "∃". Bounded quantifiers differ from "∀" and " ...
s can be replaced by a formula without quantifiers (for example, \exists x < 2, \phi(x) is equivalent to \phi(0)\vee\phi(1)), we can also allow \phi to have bounded quantifiers. 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 m_1 \exists m_2\cdots \exists m_k \psi, where \psi is \Pi^0_n, then \phi is assigned the classification \Sigma^0_. *If \phi is logically equivalent to a formula of the form \forall m_1 \forall m_2\cdots \forall m_k \psi, where \psi is \Sigma^0_n, then \phi is assigned the classification \Pi^0_. A \Sigma^0_n formula is equivalent to a formula that begins with some
existential quantifier In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, w ...
s and alternates n-1 times between series of existential and
universal quantifier In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other w ...
s; while a \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 A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in prop ...
, every formula is assigned at least one classification. Because redundant 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_r and \Pi^0_r for every ''r'' > ''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.


The arithmetical hierarchy of sets of natural numbers

A set ''X'' of natural numbers is defined by a formula φ in the language of
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
(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 \in X \Leftrightarrow \mathbb \models \varphi(\underline n), where \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 \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. For example, the set of odd natural numbers n is definable by either \forall k(n\neq 2\times k) or \exists k(n=2\times k+1). A parallel definition is used to define the arithmetical hierarchy on finite
Cartesian power In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
s of the set of 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''-
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of natural numbers. These are in fact related by the use of a
pairing function In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number. Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural ...
.


Relativized arithmetical hierarchies

Just as we can define what it means for a set ''X'' to be
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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^_n \Delta^_n and \Pi^_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^_n if it is defined by a \Sigma^0_n formula in this expanded language. In other words, ''X'' is \Sigma^_n if it is defined by a \Sigma^_n formula allowed to ask questions about membership in ''Y''. Alternatively one can view the \Sigma^_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 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)\land m\times t = n) so ''X'' is in \Sigma^_1 (actually it is in \Delta^_0 as well since we could bound both quantifiers by n).


Arithmetic reducibility and degrees

Arithmetical reducibility is an intermediate notion between
Turing reducibility In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
and
hyperarithmetic reducibility In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an importa ...
. 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 as 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^_n or \Pi^_n for some integer ''n''. A synonym for X \leq_A Y is: ''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 \land Y \leq_A X is 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 In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the ...
, denoted 2^, is the set of all infinite sequences of 0s and 1s; the
Baire space In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior. According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are ...
, denoted \omega^ or \mathcal, 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 In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. A precurs ...
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 O\subset 2^ 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=\ 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, 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 \ 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 In mathematics, the term "characteristic function" can refer to any of several distinct concepts: * The indicator function of a subset, that is the function ::\mathbf_A\colon X \to \, :which for a given subset ''A'' of ''X'', has value 1 at points ...
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 In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in effective descriptive set theory and in constructive analysis. In particular, standard examples of ...
; 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 \mathbf^0_n is just the union of \Sigma^_n for all sets of integers ''Y''. Note that the boldface hierarchy is just the standard hierarchy of
Borel sets In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are named a ...
.


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 In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
. This variation slightly changes the classification of \Sigma^0_0=\Pi^0_0=\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 \Sigma^0_0 by this definition are in \Sigma^0_1 by the definition given in the beginning of this article. \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 \Sigma^0_0=\Pi^0_0=\Delta^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_ * 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_ This variation slightly changes the classification of some sets. In particular, \Sigma^0_0=\Pi^0_0=\Delta^0_0, as a class of sets (definable by the relations in the class), is identical to \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.


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 In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
. 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 set In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
s. * 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 or Baire space is a
Borel set In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are named ...
. 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 \ is the intersection of the \Sigma^0_1 sets of the form \ as ''n'' ranges over the set of natural numbers. * The \Sigma^0_0=\Pi^0_0=\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 \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 \Sigma^0_0=\Pi^0_0=\Delta^0_0, which allow the use of primitive recursive functions, as now the quantifiers may be bound by any primitive recursive function of the arguments. * The \Sigma^0_0=\Pi^0_0=\Delta^0_0 formulas under an alternative definition, that allows the use of primitive recursive functions with bounded quantifiers, correspond to sets of integers of the form \ for a primitive recursive function ''f''. This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive ''f'', \forall k is the same as f(0)+f(1)+...f(n)=0, and \exists k is the same as f(0)*f(1)*...f(n)=0; with
course-of-values recursion In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence \lan ...
each of these can be defined by a single primitive recursion function.


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
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
s and finite
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
s 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 \Pi^0_n \subsetneq \Pi^0_ and \Sigma^0_n \subsetneq \Sigma^0_ hold for all n. Thus the hierarchy does not collapse. This is a direct consequence of
Post's theorem In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. Background The statement of Post's theorem uses several concepts relating to definability and re ...
. * The inclusions \Delta^0_n \subsetneq \Pi^0_n, \Delta^0_n \subsetneq \Sigma^0_n and \Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_ hold for n \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 \Delta^0_2 (being computable with an oracle to the halting problem) but not in \Sigma^0_1 \cup \Pi^0_1, . :*\Sigma^0_0 = \Pi^0_0 = \Delta^0_0 = \Sigma^0_0 \cup \Pi^0_0 \subset \Delta^0_1. The inclusion is strict by the definition given in this article, but an identity with \Delta^0_1 holds under one of the variations of the definition given above.


Relation to Turing machines


Computable sets

If S is a Turing computable set, then both S and its
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
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 In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. Background The statement of Post's theorem uses several concepts relating to definability and re ...
, both S and its complement are in \Sigma^0_1. This means that S is both in \Sigma^0_1 and in \Pi^0_1, and hence it is in \Delta^0_1. Similarly, for every set S in \Delta^0_1, both S and its complement are in \Sigma^0_1 and are therefore (by
Post's theorem In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. Background The statement of Post's theorem uses several concepts relating to definability and re ...
) recursively enumerable by some Turing machines T1 and T2, respectively. For every number n, exactly one of these halts. We may therefore construct a Turing machine T that alternates between T1 and T2, 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.


Summary of main results

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 In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
is capable of solving its own
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
(a variation of Turing's proof applies). The halting problem for a \Delta^_n oracle in fact sits in \Sigma^_.
Post's theorem In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. Background The statement of Post's theorem uses several concepts relating to definability and re ...
establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the
Turing degree In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Overview The concept of Turing degree is fund ...
s. In particular, it establishes the following facts for all ''n'' ≥ 1: * The set \emptyset^ (the ''n''th
Turing jump In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
of the empty set) is many-one complete in \Sigma^0_n. * The set \mathbb \setminus \emptyset^ is many-one complete in \Pi^0_n. * The set \emptyset^ is
Turing complete Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
in \Delta^0_n. The
polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...
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.


Relation to other hierarchies


See also

*
Analytical hierarchy In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
*
Lévy hierarchy In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This i ...
*
Hierarchy (mathematics) In mathematics, a hierarchy is a set-theoretical object, consisting of a preorder defined on a set. This is often referred to as an ordered set, though that is an ambiguous term that many authors reserve for partially ordered sets or totally o ...
*
Interpretability logic Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability ...
*
Polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...


References

* . * . * . * . {{ComplexityClasses Mathematical logic hierarchies Computability theory Effective descriptive set theory Hierarchy Complexity classes