Arithmetic hierarchy
The arithmetic hierarchy is a concept of mathematical logic . It classifies sets of natural numbers , which are definable in the language of Peano arithmetic , according to the complexity of their definitions. The arithmetically definable quantities are also referred to as arithmetic . The arithmetic hierarchy plays an important role in computability theory . The hyperarithmetic hierarchy and the analytic hierarchy expand the arithmetic hierarchy upward.
definition
Classification of formulas
The arithmetic hierarchy classifies formulas in the language of Peano arithmetic into classes called , and for natural numbers n .
The lowest level is formed by formulas that define a decidable relation . These form the class . The other classes are inductively defined for each number n as follows:
- If is equivalent to a formula where in is, then in is .
- If is equivalent to a formula where in is, then in is .
- (for all n )
Every arithmetic formula is equivalent to a formula in prenex normal form , which has an alternating universal and an existential quantifier. A formula starts with an existential quantifier; a universal quantifier for a formula. Every formula is equivalent to the negation of a formula.
Since redundant quantifiers that do not bind any occurring variable can be added to every formula, all formulas are in or also in and for all m> n .
Alternatively, the lowest class can be defined to contain only formulas that are equivalent to a formula that has only bounded quantifiers . In this case the lowest class contains fewer relations; all other classes remain the same.
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 those numbers that satisfy, i.e. H.:
where is the term in arithmetic language that represents the number . A set is called arithmetic when it is defined by a formula of Peano arithmetic . An amount X of natural numbers , , or , if it is defined by a formula in the corresponding class. Relationships or sets of k -tuples of natural numbers can also be classified if one considers formulas with k free variables.
Relation to predictability
The decidable sets are exactly the sets. The recursively enumerable sets are the -sets. There is also a close relationship between the arithmetic hierarchy and the Turing degrees . According to Post's theorem, the following applies to everyone :
- (the -th Turing jump of the empty set) is complete for many-one .
- The sets in are exactly the sets that can be recursively enumerated in .
- is completely under Turing reduction for .
literature
- Hartley Rogers: Theory of recursive functions and effective computability . McGraw-Hill, 1967.