Editing Arithmetical hierarchy (section)

== The arithmetical hierarchy of sets of natural numbers ==

A set ''X'' of natural numbers is defined by a formula ''&phi;'' in the language of [[Peano arithmetic]] (the first-order language with symbols "0" for zero, "S" for the successor function, "+" for addition, "&times;" for multiplication, and "=" for equality), if the elements of ''X'' are exactly the numbers that satisfy ''&phi;''.  That is, for all natural numbers ''n'',
:<math>n \in X \Leftrightarrow \mathbb{N} \models \varphi(\underline n),</math>
where <math>\underline n</math> is the numeral in the language of arithmetic corresponding to <math>n</math>. A set is definable in first-order arithmetic if it is defined by some formula in the language of Peano arithmetic.

Each set ''X'' of natural numbers that is definable in first-order arithmetic is assigned classifications of the form <math>\Sigma^0_n</math>, <math>\Pi^0_n</math>, and <math>\Delta^0_n</math>, where <math>n</math> is a natural number, as follows.  If ''X'' is definable by a <math>\Sigma^0_n</math> formula then ''X'' is assigned the classification <math>\Sigma^0_n</math>.  If ''X'' is definable by a <math>\Pi^0_n</math> formula then ''X'' is assigned the classification <math>\Pi^0_n</math>.  If ''X'' is both <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> then <math>X</math> is assigned the additional classification <math>\Delta^0_n</math>.

Note that it rarely makes sense to speak of <math>\Delta^0_n</math> formulas; the first quantifier of a formula is either existential or universal. So a <math>\Delta^0_n</math> set is not necessarily defined by a <math>\Delta^0_n</math> formula in the sense of a formula that is both <math>\Sigma^0_n</math> and <math>\Pi^0_n</math>; rather, there are both <math>\Sigma^0_n</math>  and  <math>\Pi^0_n</math> formulas that define the set. For example, the set of odd natural numbers <math>n</math> is definable by either <math>\forall k(n\neq 2\times k)</math> or <math>\exists k(n=2\times k+1)</math>.

A parallel definition is used to define the arithmetical hierarchy on finite [[Cartesian power]]s of the set of natural numbers.  Instead of formulas with one free variable, formulas with ''k'' free first-order variables are used to define the arithmetical hierarchy on sets of ''k''-[[tuple]]s of natural numbers. These are in fact related by the use of a [[pairing function]].