arithmetical hierarchy

arithmetical hierarchy
A classification of sets of natural numbers by the complexity of the formulas in the language of Peano arithmetic that define them, specifically by the number of alternations of A and E in the defining formula given the formula is in prenex normal form.
Syn: arithmetic hierarchy, Kleene hierarchy

Wikipedia foundation.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Arithmetical hierarchy — In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The… …   Wikipedia

  • Arithmetical set — In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.A function f:subseteq… …   Wikipedia

  • Hierarchy (mathematics) — In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of… …   Wikipedia

  • Polynomial hierarchy — 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.DefinitionsThere are multiple equivalent definitions of the classes of the polynomial …   Wikipedia

  • Analytical hierarchy — In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them. The analytical hierarchy of… …   Wikipedia

  • 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. Each Borel set is assigned a unique countable ordinal number… …   Wikipedia

  • Wadge hierarchy — In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge… …   Wikipedia

  • arithmetic hierarchy — noun arithmetical hierarchy …   Wiktionary

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”