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, ${\displaystyle \mathbb {N} }$, and over functions from ${\displaystyle \mathbb {N} }$ to ${\displaystyle \mathbb {N} }$. 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 notation ${\displaystyle \Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}}$ indicates the class of formulas in the language of second-order arithmetic with number quantifiers but no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, indicating the language choice. 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 ${\displaystyle \Sigma _{n+1}^{1}}$ if it is logically equivalent to a formula of the form ${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$ where ${\displaystyle \psi }$ is ${\displaystyle \Pi _{n}^{1}}$. A formula is defined to be ${\displaystyle \Pi _{n+1}^{1}}$ if it is logically equivalent to a formula of the form ${\displaystyle \forall X_{1}\cdots \forall X_{k}\psi }$ where ${\displaystyle \psi }$ is ${\displaystyle \Sigma _{n}^{1}}$. This inductive definition defines the classes ${\displaystyle \Sigma _{n}^{1}}$ and ${\displaystyle \Pi _{n}^{1}}$ for every natural number ${\displaystyle n}$.

Kuratowski and Tarski showed in 1931 that every formula in the language of second-order arithmetic has a prenex normal form, and therefore is ${\displaystyle \Sigma _{n}^{1}}$ or ${\displaystyle \Pi _{n}^{1}}$ for some ${\displaystyle n}$. Because meaningless quantifiers can be added to any formula, once a formula is given the classification ${\displaystyle \Sigma _{n}^{1}}$ or ${\displaystyle \Pi _{n}^{1}}$ for some ${\displaystyle n}$ it will be given the classifications ${\displaystyle \Sigma _{m}^{1}}$ and ${\displaystyle \Pi _{m}^{1}}$ for all ${\displaystyle m}$ greater than ${\displaystyle n}$.

A set of natural numbers is assigned the classification ${\displaystyle \Sigma _{n}^{1}}$ if it is definable by a ${\displaystyle \Sigma _{n}^{1}}$ formula (with one free number variable and no free set variables). The set is assigned the classification ${\displaystyle \Pi _{n}^{1}}$ if it is definable by a ${\displaystyle \Pi _{n}^{1}}$ formula. If the set is both ${\displaystyle \Sigma _{n}^{1}}$ and ${\displaystyle \Pi _{n}^{1}}$ then it is given the additional classification ${\displaystyle \Delta _{n}^{1}}$.

The ${\displaystyle \Delta _{1}^{1}}$ sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by the hyperarithmetical theory.

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