Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, formula_1, and over functions from formula_1 to formula_1. The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.
The analytical hierarchy of formulas.
The notation formula_4
indicates the class of formulas in the language of second-order arithmetic with no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, which indicate this choice of language. Each corresponding boldface symbol denotes the corresponding class of formulas in the extended language with a parameter for each real; see projective hierarchy for details.
A formula in the language of second-order arithmetic is defined to be formula_5 if it is logically equivalent to a formula of the form formula_6 where formula_7 is formula_8. A formula is defined to be formula_9 if it is logically equivalent to a formula of the form formula_10 where formula_7 is formula_12. This inductive definition defines the classes formula_13 and formula_14 for every natural number formula_15.
Because every formula has a prenex normal form, every formula in the language of second-order arithmetic is formula_13 or formula_14 for some formula_15. Because meaningless quantifiers can be added to any formula, once a formula is given the classification formula_13 or formula_14 for some formula_15 it will be given the classifications formula_22 and formula_23 for all formula_24 greater than formula_15.
The analytical hierarchy of sets of natural numbers.
A set of natural numbers is assigned the classification formula_13 if it is definable by a formula_13 formula. The set is assigned the classification formula_14 if it is definable by a formula_14 formula. If the set is both formula_13 and formula_14 then it is given the additional classification formula_32.
The formula_33 sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by hyperarithmetical theory.
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 is the set of all infinite sequences of natural numbers. These are both Polish spaces.
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 formula_13 if it is definable by a formula_13 formula. The set is assigned the classification formula_14 if it is definable by a formula_14 formula. If the set is both formula_13 and formula_14 then it is given the additional classification formula_32.
A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from formula_41 to formula_41 to the characteristic function of its graph. A subset of Baire space is given the classification formula_13, formula_14, or formula_32 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 power 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.
Extensions.
As is the case with the arithmetical hierarchy, a relativized version of the analytical hierarchy can be defined. The language is extended to add a constant set symbol "A". A formula in the extended language is inductively defined to be formula_46 or formula_47 using the same inductive definition as above. Given a set formula_48, a set is defined to be formula_49 if it is definable by a formula_46 formula in which the symbol formula_51 is interpreted as formula_48; similar definitions for formula_53 and formula_54 apply. The sets that are formula_49 or formula_53, for any parameter "Y", are classified in the projective hierarchy.
Properties.
For each formula_15 we have the following strict containments:
A set that is in formula_13 for some "n" is said to be analytical. Care is required to distinguish this usage from the term analytic set which has a different meaning.