Editing Arithmetical hierarchy (section)

== Examples ==

* The <math>\Sigma^0_1</math> sets of numbers are those definable by a formula of the form <math>\exists n_1 \cdots \exists n_k \psi(n_1,\ldots,n_k,m)</math> where <math>\psi</math> has only bounded quantifiers.  These are exactly the [[recursively enumerable set]]s.
* The set of natural numbers that are indices for [[Turing machine]]s that compute total functions is <math>\Pi^0_2</math>.  Intuitively, an index <math>e</math> falls into this set if and only if for every <math>m</math> "there is an <math>s</math> such that the Turing machine with index <math>e</math> halts on input <math>m</math> after <math>s</math> steps".  A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of [[Peano arithmetic]] by a <math>\Sigma^0_1</math> formula.
* Every <math>\Sigma^0_1</math> subset of [[Baire space]] or [[Cantor space]] is an [[open set]] in the usual [[topological space|topology]] on the space.  Moreover, for any such set there is a computable enumeration of [[Gödel number]]s of basic open sets whose union is the original set. For this reason, <math>\Sigma^0_1</math> sets are sometimes called ''effectively open''.  Similarly, every <math>\Pi^0_1</math> set is closed and the <math>\Pi^0_1</math> sets are sometimes called ''effectively closed''.
* Every arithmetical subset of Cantor space or Baire space is a [[Borel set]].  The lightface [[Borel hierarchy]] extends the arithmetical hierarchy to include additional Borel sets.  For example, every <math>\Pi^0_2</math> subset of Cantor or Baire space is [[G-delta set|a <math>G_\delta</math> set]], that is, a set that equals the intersection of countably many open sets.   Moreover, each of these open sets is <math>\Sigma^0_1</math> and the list of Gödel numbers of these open sets has a computable enumeration.  If <math>\phi(X,n,m)</math> is a <math>\Sigma^0_0</math> formula with a free set variable <math>X</math> and free number variables <math>n,m</math> then the <math>\Pi^0_2</math> set <math>\{X \mid \forall n \exists m \phi(X,n,m)\}</math> is the intersection of the <math>\Sigma^0_1</math> sets of the form <math>\{ X \mid \exists m \phi(X,n,m)\}</math> as <math>n</math> ranges over the set of natural numbers.
* The <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math> formulas can be checked by going over all cases one by one, which is possible because all their quantifiers are bounded. The time for this is polynomial in their arguments (e.g. polynomial in <math>n</math> for <math>\varphi(n)</math>); thus their corresponding decision problems are included in [[E (complexity)|E]] (as <math>n</math> is exponential in its number of bits). This no longer holds under alternative definitions of <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math> that allow the use of [[primitive recursive function]]s, as now the quantifiers may be bounded by any primitive recursive function of the arguments.
* The <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math> formulas under an alternative definition, that allows the use of [[primitive recursive function]]s with [[bounded quantifier]]s, correspond to sets of natural numbers of the form <math>\{n: f(n) = 0\}</math> for a primitive recursive function <math>f</math>. This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive <math>f</math>, <math>\forall k<n: f(k)=0</math> is the same as  <math>f(0)+f(1)+...f(n-1)=0</math>, and <math>\exists k<n: f(k)=0</math> is the same as  <math> f(0)\cdot f(1)\cdot\ldots\cdot f(n-1)=0</math>; with [[course-of-values recursion]] each of these can be defined by a single primitive recursive function.