Arithmetical hierarchy

The arithmetic hierarchy is a concept of mathematical logic. Classifies amounts of natural numbers which are defined in the language of Peano arithmetic, according to the complexity of their definitions. The arithmetic definable quantities are also referred to as arithmetic. The arithmetic hierarchy plays an important role in computability theory. The hyperarithmetische hierarchy and the analytic hierarchy expand the arithmetic hierarchy.

Definition

Classification of formulas

The arithmetic hierarchy classifies formulas in the language of Peano arithmetic in classes named, and for natural numbers n

The lowest level consists of formulas that define a decidable relation. These form the class. The other classes, for each number n defined inductively as follows:

• If is equivalent to a formula where in lies, then lies in.
• If is equivalent to a formula where in lies, then lies in.
• (for all n )

Every arithmetic formula is equivalent to a formula in Pränexnormalform alternately a universal and an existential quantifier has. In a first - formula is an existential quantifier; at a formula one universal quantifier. Each formula is equivalent to the negation of a formula.

Since every formula redundant quantifiers that bind variables not occurring, can be added, all formulas are in or even in, and for all m > n

Alternatively, the lowest class are defined so that it only contains formulas that are equivalent to a formula that has only limited quantifiers. In this case, the lowest class contains less relations; all other classes remain unchanged.

Classification of sets and relations

A set X of natural numbers is defined by a formula in the language of Peano arithmetic, if X contains exactly the numbers that satisfy, ie:

Wherein the term in the language of the arithmetic is representing the number. A set is called arithmetic if it is defined by a formula of Peano arithmetic. A set X of natural numbers is, or if it is defined by a formula in the corresponding class. Likewise also ratios or amounts of k- tuples of natural numbers can be classified if one considers formulas with k free variables.

Related to predictability

The decidable sets are exactly the sets. The recursively enumerable sets correspond to the sets. Beyond this, there is a close relationship between the arithmetic hierarchy and the Turing degrees. After the set of post is valid for all n ≥ 1:

• ( the n-th Turing jump of the empty set ) is many-one complete for.
• The quantities are exactly the quantities that are recursively enumerable in.
• Is complete under Turing reduction for.