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.