Editing Arithmetical hierarchy (section)

== Extensions and variations==

It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for each [[primitive recursive function]].  This variation slightly changes the classification of <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math>, since [[Gödel's_β_function#General_schema_with_parameters|using primitive recursive functions in first-order Peano arithmetic]] requires, in general, an unbounded existential quantifier, and thus some sets that are in <math>\Sigma^0_0</math> by this definition are strictly in <math>\Sigma^0_1</math> by the definition given in the beginning of this article. The class <math>\Sigma^0_1</math> and thus all higher classes in the hierarchy remain unaffected.

A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used.  Every computable relation is defined to be <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math>.  The classifications <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> are defined inductively with the following rules.
* If the relation <math>R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,</math> is <math>\Sigma^0_n</math> then the relation <math>S(n_1,\ldots, n_l) = \forall m_1\cdots \forall m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)</math> is defined to be <math>\Pi^0_{n+1}</math>
* If the relation <math>R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,</math> is <math>\Pi^0_n</math> then the relation <math>S(n_1,\ldots,n_l) = \exists m_1\cdots \exists m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)</math> is defined to be <math>\Sigma^0_{n+1}</math>
This variation slightly changes the classification of some sets. In particular, <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math>, as a class of sets (definable by the relations in the class), is identical to <math>\Delta^0_1</math> as the latter was formerly defined. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.