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.