Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Arithmetical hierarchy

+ Save concept

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. [1]

44 relations: Analytical hierarchy, Andrzej Mostowski, Baire space (set theory), Borel hierarchy, Borel set, Bounded quantifier, Cantor space, Cartesian product, Complement (set theory), Complexity, Computability theory, Course-of-values recursion, E (complexity), Effective descriptive set theory, Effective Polish space, Existential quantification, Halting problem, Hierarchy (mathematics), Hyperarithmetical theory, Indicator function, Interpretability logic, Intersection (set theory), Many-one reduction, Mathematical logic, Oracle machine, Pairing function, Peano axioms, Pointclass, Polynomial hierarchy, Post's theorem, Prenex normal form, Primitive recursive function, Recursive set, Recursively enumerable set, Second-order arithmetic, Set (mathematics), Stephen Cole Kleene, Tarski–Kuratowski algorithm, Tuple, Turing degree, Turing jump, Turing reduction, Union (set theory), Universal quantification.

Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.

New!!: Arithmetical hierarchy and Analytical hierarchy · See more »

Andrzej Mostowski

Andrzej Mostowski (1 November 1913 – 22 August 1975) was a Polish mathematician.

New!!: Arithmetical hierarchy and Andrzej Mostowski · See more »

Baire space (set theory)

In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology.

New!!: Arithmetical hierarchy and Baire space (set theory) · See more »

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.

New!!: Arithmetical hierarchy and Borel hierarchy · See more »

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.

New!!: Arithmetical hierarchy and Borel set · See more »

Bounded quantifier

In the study of formal theories in mathematical logic, bounded quantifiers are often included in a formal language in addition to the standard quantifiers "∀" and "∃".

New!!: Arithmetical hierarchy and Bounded quantifier · See more »

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.

New!!: Arithmetical hierarchy and Cantor space · See more »

Cartesian product

In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets.

New!!: Arithmetical hierarchy and Cartesian product · See more »

Complement (set theory)

In set theory, the complement of a set refers to elements not in.

New!!: Arithmetical hierarchy and Complement (set theory) · See more »


Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.

New!!: Arithmetical hierarchy and Complexity · See more »

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

New!!: Arithmetical hierarchy and Computability theory · See more »

Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion.

New!!: Arithmetical hierarchy and Course-of-values recursion · See more »

E (complexity)

In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O(n) and is therefore equal to the complexity class DTIME(2O(n)).

New!!: Arithmetical hierarchy and E (complexity) · See more »

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

New!!: Arithmetical hierarchy and Effective descriptive set theory · See more »

Effective Polish space

In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation.

New!!: Arithmetical hierarchy and Effective Polish space · See more »

Existential quantification

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

New!!: Arithmetical hierarchy and Existential quantification · See more »

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 (i.e., halt) or continue to run forever.

New!!: Arithmetical hierarchy and Halting problem · See more »

Hierarchy (mathematics)

In mathematics, a hierarchy is a set-theoretical object, consisting of a preorder defined on a set.

New!!: Arithmetical hierarchy and Hierarchy (mathematics) · See more »

Hyperarithmetical theory

In recursion theory, hyperarithmetic theory is a generalization of Turing computability.

New!!: Arithmetical hierarchy and Hyperarithmetical theory · See more »

Indicator function

In mathematics, an indicator function or a characteristic function is a function defined on a set X that indicates membership of an element in a subset A of X, having the value 1 for all elements of A and the value 0 for all elements of X not in A. It is usually denoted by a symbol 1 or I, sometimes in boldface or blackboard boldface, with a subscript specifying the subset.

New!!: Arithmetical hierarchy and Indicator function · See more »

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, tolerance, cotolerance, and arithmetic complexities.

New!!: Arithmetical hierarchy and Interpretability logic · See more »

Intersection (set theory)

In mathematics, the intersection A ∩ B 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.

New!!: Arithmetical hierarchy and Intersection (set theory) · See more »

Many-one reduction

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem.

New!!: Arithmetical hierarchy and Many-one reduction · See more »

Mathematical logic

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.

New!!: Arithmetical hierarchy and Mathematical logic · See more »

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

New!!: Arithmetical hierarchy and Oracle machine · See more »

Pairing function

In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number.

New!!: Arithmetical hierarchy and Pairing function · See more »

Peano axioms

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.

New!!: Arithmetical hierarchy and Peano axioms · See more »


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.

New!!: Arithmetical hierarchy and Pointclass · See more »

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 P, NP and co-NP to oracle machines.

New!!: Arithmetical hierarchy and Polynomial hierarchy · See more »

Post's theorem

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

New!!: Arithmetical hierarchy and Post's theorem · See more »

Prenex normal form

A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers (referred to as the prefix) followed by a quantifier-free part (referred to as the matrix).

New!!: Arithmetical hierarchy and Prenex normal form · See more »

Primitive recursive function

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive).

New!!: Arithmetical hierarchy and Primitive recursive function · See more »

Recursive set

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set.

New!!: Arithmetical hierarchy and Recursive set · See more »

Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if.

New!!: Arithmetical hierarchy and Recursively enumerable set · See more »

Second-order arithmetic

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.

New!!: Arithmetical hierarchy and Second-order arithmetic · See more »

Set (mathematics)

In mathematics, a set is a collection of distinct objects, considered as an object in its own right.

New!!: Arithmetical hierarchy and Set (mathematics) · See more »

Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

New!!: Arithmetical hierarchy and Stephen Cole Kleene · See more »

Tarski–Kuratowski algorithm

In computability theory and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy and analytical hierarchy.

New!!: Arithmetical hierarchy and Tarski–Kuratowski algorithm · See more »


In mathematics, a tuple is a finite ordered list (sequence) of elements.

New!!: Arithmetical hierarchy and Tuple · See more »

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.

New!!: Arithmetical hierarchy and Turing degree · See more »

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 with an oracle for.

New!!: Arithmetical hierarchy and Turing jump · See more »

Turing reduction

In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987).

New!!: Arithmetical hierarchy and Turing reduction · See more »

Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.

New!!: Arithmetical hierarchy and Union (set theory) · See more »

Universal quantification

In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all".

New!!: Arithmetical hierarchy and Universal quantification · See more »

Redirects here:

AH (complexity), Arithmetic hierarchy, Arithmetic reducibility, Arithmetical reducibility, Kleene hierarchy, Kleene–Mostowski hierarchy, Pi-0-1 sentence, Pi-0-1 sentences, Pi-0-2 sentence.


[1] https://en.wikipedia.org/wiki/Arithmetical_hierarchy

Hey! We are on Facebook now! »