Arithmetical hierarchy on arvau

Wikipedia / 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 formulass 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 of formulas

The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic for natural numbers n (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain

is logically equivalent to a formula in which all quantifiers are bounded.

are defined inductively for every natural number n using the following rules:

formula is equivalent to a formula that begins with some existential quantifiers times between series of existential and universal quantifiers 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 for every m > 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 (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,

. A set is definable in first-order arithmetic if it is defined by some formula in the language of Peano arithmetic.

Each set X is a natural number, as follows. If X formula then X. If X formula then X. If X.

formulas.

A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the set of natural numbers. Instead of formulas with one free variable, formulas with k free first-order variables are used to define the arithmetical hierarchy on sets of k-tuples of natural numbers. These are in fact related by the use of a pairing function.

Meaning of the notation

The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.

formulas.

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

has only bounded quantifiers. These are exactly the recursively enumerable sets.
The set of natural numbers that are indices for Turing machines steps". A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of Peano arithmetic formula.
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 sets are sometimes called effectively open sets are sometimes called effectively closed.
Every arithmetical subset of Cantor space or Baire space is a Borel set. The lightface Borel hierarchy subset of Cantor or Baire space is G_\delta set ranges over the set of natural numbers.
); thus their corresponding decision problems are included in E that allow the use of primitive recursive functions, as now the quantifiers may be bounded by any primitive recursive function of the arguments.
formulas under an alternative definition, that allows the use of primitive recursive functions with bounded quantifiers; with course-of-values recursion each of these can be defined by a single primitive recursive function.

Relativized arithmetical hierarchies

Just as we can define what it means for a set X to be recursive 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 in Y. To do so, fix a set of natural numbers Y and add a predicate for membership of Y to the language of Peano arithmetic. We then say that X formula in this expanded language. In other words, X formula allowed to ask questions about membership of Y 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 natural numbers. Let X be the set of numbers divisible by an element of Y. Then X so X as well, since we could bound both quantifiers by n).

Arithmetic reducibility and degrees

Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility.

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 for some natural number n. A set X is arithmetical in a set Y, if X is definable as some formula in the language of Peano arithmetic extended by a predicate for membership of Y. Equivalently, X is arithmetical in Y if X for some natural number n is: X is arithmetically reducible to Y.

is reflexive and transitive defined by the rule

is an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered.

The arithmetical hierarchy of subsets of Cantor and Baire space

The Cantor space, is the set of all infinite sequences of 0s and 1s; the Baire space, is the set of all infinite sequences of natural numbers. Elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers.

The ordinary axiomatization of second-order arithmetic set.

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.

to the characteristic function if and only if the corresponding subset of Cantor space has the same classification.
An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second-order arithmetic; then the arithmetical 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; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second-order arithmetic.

for all sets of natural numbers Y. The boldface hierarchy is just the standard hierarchy of Borel sets.

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, since using primitive recursive functions in first-order Peano arithmetic and thus all higher classes in the hierarchy remain unaffected.

are defined inductively with the following rules.

as the latter was formerly defined. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.

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.

are closed under finite unionss and finite intersectionss of their respective elements.
.
. Thus the hierarchy does not collapse. This is a direct consequence of Post's theorem.
.
For example, for a universal Turing machine T, the set of pairs (n,m) such that T halts on n but not on m.
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 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, both S. This means that S.

Similarly, for every set S, both S and are therefore (by Post's theorem) 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

No oracle machine is capable of solving its own halting problem.

Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees. In particular, it establishes the following facts for all n ≥ 1:

(the nth Turing jump of the empty set) is many-one complete.
.
is Turing complete.

The polynomial hierarchy of the arithmetical hierarchy.