# 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 . ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ Delta _ {n} ^ {0}}$ 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: ${\ displaystyle \ Delta _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Sigma _ {0} ^ {0}}$ • If is equivalent to a formula where in is, then in is .${\ displaystyle \ varphi}$ ${\ displaystyle \ exists x_ {1} \ exists x_ {2} \ cdots \ exists x_ {k} \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ Sigma _ {n + 1} ^ {0}}$ • If is equivalent to a formula where in is, then in is .${\ displaystyle \ varphi}$ ${\ displaystyle \ forall x_ {1} \ forall x_ {2} \ cdots \ forall x_ {k} \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ Pi _ {n + 1} ^ {0}}$ • ${\ displaystyle \ Delta _ {n} ^ {0} = \ Sigma _ {n} ^ {0} \ cap \ Pi _ {n} ^ {0}}$ (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. ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ 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 . ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ Sigma _ {m} ^ {0}}$ ${\ displaystyle \ Pi _ {m} ^ {0}}$ 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. ${\ displaystyle \ Delta _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Sigma _ {0} ^ {0}}$ ### 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.: ${\ displaystyle \ varphi (x)}$ ${\ displaystyle \ varphi (x)}$ ${\ displaystyle n \ in X \ Leftrightarrow \ mathbb {N} \ models \ varphi ({\ underline {n}}),}$ 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. ${\ displaystyle {\ underline {n}}}$ ${\ displaystyle n}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ ${\ displaystyle \ Pi _ {n} ^ {0}}$ ${\ displaystyle \ Delta _ {n} ^ {0}}$ ## 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 : ${\ displaystyle \ Delta _ {1} ^ {0}}$ ${\ displaystyle \ Sigma _ {1} ^ {0}}$ ${\ displaystyle n \ geq 1}$ • ${\ displaystyle \ emptyset ^ {(n)}}$ (the -th Turing jump of the empty set) is complete for many-one .${\ displaystyle n}$ ${\ displaystyle \ Sigma _ {n} ^ {0}}$ • The sets in are exactly the sets that can be recursively enumerated in .${\ displaystyle \ Sigma _ {n + 1} ^ {0}}$ ${\ displaystyle \ emptyset ^ {(n)}}$ • ${\ displaystyle \ emptyset ^ {(n-1)}}$ is completely under Turing reduction for .${\ displaystyle \ Delta _ {n} ^ {0}}$ ## literature

• Hartley Rogers: Theory of recursive functions and effective computability . McGraw-Hill, 1967.