Editing Arithmetical hierarchy (section)

==The arithmetical hierarchy of subsets of Cantor and Baire space==

The [[Cantor space]], denoted <math>2^{\omega}</math>, is the set of all infinite sequences of 0s and 1s; the [[Baire space (set theory)|Baire space]], denoted <math>\omega^{\omega}</math> or <math>\mathcal{N}</math>, is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers.

The ordinary axiomatization of [[second-order arithmetic]] uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space.   A subset of Cantor space is assigned the classification <math>\Sigma^0_n</math> if it is definable by a <math>\Sigma^0_n</math> formula.  The set is assigned the classification <math>\Pi^0_n</math> if it is definable by a <math>\Pi^0_n</math> formula.  If the set is both <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> then it is given the additional classification <math>\Delta^0_n</math>.  For example, let <math>O\subseteq 2^{\omega}</math> be the set of all infinite binary strings that aren't all 0 (or equivalently the set of all non-empty sets of natural numbers).  As <math>O=\{ X\in 2^\omega | \exists n (X(n)=1) \} </math> we see that <math>O</math> is defined by a <math>\Sigma^0_1</math> formula and hence is a <math>\Sigma^0_1</math> set.

Note that while both the elements of the Cantor space (regarded as sets of natural numbers) and subsets of the Cantor space are classified in arithmetic hierarchies,  these are not the same hierarchy.  In fact the relationship between the two hierarchies is interesting and non-trivial.  For instance the <math>\Pi^0_n</math> elements of the Cantor space are not (in general) the same as the elements <math>X</math> of the Cantor space so that <math>\{X\}</math> is a <math>\Pi^0_n</math> subset of the Cantor space.  However, many interesting results relate the two hierarchies.

There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy.
*A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from <math>\omega</math> to <math>\omega</math> to the [[indicator function|characteristic function]] of its graph.   A subset of Baire space is given the classification <math>\Sigma^0_n</math>, <math>\Pi^0_n</math>, or <math>\Delta^0_n</math> if and only if the corresponding subset of Cantor space has the same classification.
*An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second-order arithmetic; then the arithmetical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space.  This alternate definition gives exactly the same classifications as the first definition.

A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables.  The arithmetical hierarchy can be defined on any [[effective Polish space]]; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second-order arithmetic.

Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of natural numbers.  In fact boldface <math>\mathbf{\Sigma}^0_n</math> is just the union of <math>\Sigma^{0,Y}_n</math> for all sets of natural numbers ''Y''.  Note that the boldface hierarchy is just the standard hierarchy of [[Borel hierarchy|Borel sets]].