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.
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.
Andrzej Mostowski (1 November 1913 – 22 August 1975) was a Polish mathematician.
In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology.
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.
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.
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 "∃".
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 (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.
In set theory, the complement of a set refers to elements not in.
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.
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.
In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion.
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)).
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).
In mathematical logic, an effective Polish space is a complete separable metric space that has a computable presentation.
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".
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.
In mathematics, a hierarchy is a set-theoretical object, consisting of a preorder defined on a set.
In recursion theory, hyperarithmetic theory is a generalization of Turing computability.
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.
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.
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.
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.
Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number.
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.
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 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.
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
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).
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).
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.
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.
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.
In mathematics, a set is a collection of distinct objects, considered as an object in its own right.
Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.
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.
In mathematics, a tuple is a finite ordered list (sequence) of elements.
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.
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.
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).
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.
In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all".