Editing Analytical hierarchy (section)

== The analytical hierarchy on subsets of Cantor and Baire space ==
The analytical hierarchy can be defined on any [[effective Polish space]]; the definition is particularly simple for Cantor and Baire space because they fit with the language of ordinary second-order arithmetic. [[Cantor space]] is the set of all infinite sequences of 0s and 1s; [[Baire space (set theory)|Baire space]] is the set of all infinite sequences of natural numbers. These are both [[Polish space]]s.

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^1_n</math> if it is definable by a <math>\Sigma^1_n</math> formula (with one free set variable and no free number variables). The set is assigned the classification <math>\Pi^1_n</math> if it is definable by a <math>\Pi^1_n</math> formula. If the set is both <math>\Sigma^1_n</math> and <math>\Pi^1_n</math> then it is given the additional classification <math>\Delta^1_n</math>.

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 characteristic function of its graph. A subset of Baire space is given the classification <math>\Sigma^1_n</math>, <math>\Pi^1_n</math>, or <math>\Delta^1_n</math> if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second-order arithmetic; then the analytical 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.

Because Cantor space is [[homeomorphic]] to any finite Cartesian power of itself, and Baire space is homeomorphic to any finite Cartesian power of itself, the analytical hierarchy applies equally well to finite Cartesian powers of one of these spaces.
A similar extension is possible for countable powers and to products of powers of Cantor space and powers of Baire space.