Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy was invented independently by Kleene (1943) and Mostowski (1946). The arithmetical hierarchy is important in computability theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic. 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 and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets. The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted and for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters. If a formula is logically equivalent to a formula with only bounded quantifiers, then is assigned the classifications and . The classifications and are defined inductively for every natural number n using the following rules: If is logically equivalent to a formula of the form , where is , then is assigned the classification . If is logically equivalent to a formula of the form , where is , then is assigned the classification . A formula is equivalent to a formula that begins with some existential quantifiers and alternates times between series of existential and universal quantifiers; while a 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, every formula is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned the classification or it will be assigned the classifications and for every m > n.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (12)

Related units (3)

Related concepts (25)

Related courses (2)

Related lectures (6)

QFT without infinities and hierarchy problem

Sander Johannes Nicolaas Mooij

The standard way to do computations in Quantum Field Theory (QFT) often results in the requirement of dramatic cancellations between contributions induced by a "heavy" sector into the physical observables of the "light" (or low energy) sector - the phenome ...

ELSEVIER2023

Placement of Virtual Containers on NUMA systems: A Practical and Comprehensive Model

Baptiste Joseph Eustache Lepers

Our work addresses the problem of placement of threads, or virtual cores, onto physical cores in a multicore NUMA system. Different placements result in varying degrees of contention for shared resources, so choosing the right placement can have a large ef ...

2018

Placement of Virtual Containers on NUMA systems: A Practical and Comprehensive Model

Baptiste Joseph Eustache Lepers

USENIX ASSOC2018

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. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine.

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.

Turing reduction

In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for .

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

MATH-318: Set theory

Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,

Complexity Theory: P and NP CS-119(c): Information, Computation, Communication

Explores complexity classes P and NP, practical algorithms, non-polynomial problems, and efficient solution verification.

Distributed Intelligent Systems: Energy Efficiency in Wireless Sensor Networks ENG-466: Distributed intelligent systems

Delves into energy-saving design principles in wireless sensor networks, exploring motivating applications and intelligent algorithms for energy efficiency.

Nonlinear Model Predictive Control: Stability and Design Steps EE-715: Optimal control

Explores Nonlinear Model Predictive Control principles, stability analysis, design steps, and practical considerations.