• Images
• Videos
• Documents
• Books
• Articles

The analytical hierarchy of formulas

The notation Σ 0 1 = Π 0 1 = Δ 0 1 {\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 Σ n + 1 1 {\displaystyle \Sigma _{n+1}^{1}} if it is logically equivalent to a formula of the form ∃ X 1 ⋯ ∃ X k ψ {\displaystyle \exists X_{1}\cdots \exists X_{k}\psi } where ψ {\displaystyle \psi } is Π n 1 {\displaystyle \Pi _{n}^{1}} . A formula is defined to be Π n + 1 1 {\displaystyle \Pi _{n+1}^{1}} if it is logically equivalent to a formula of the form ∀ X 1 ⋯ ∀ X k ψ {\displaystyle \forall X_{1}\cdots \forall X_{k}\psi } where ψ {\displaystyle \psi } is Σ n 1 {\displaystyle \Sigma _{n}^{1}} . This inductive definition defines the classes Σ n 1 {\displaystyle \Sigma _{n}^{1}} and Π n 1 {\displaystyle \Pi _{n}^{1}} for every natural number n {\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 Σ n 1 {\displaystyle \Sigma _{n}^{1}} or Π n 1 {\displaystyle \Pi _{n}^{1}} for some n {\displaystyle n} . Because meaningless quantifiers can be added to any formula, once a formula is given the classification Σ n 1 {\displaystyle \Sigma _{n}^{1}} or Π n 1 {\displaystyle \Pi _{n}^{1}} for some n {\displaystyle n} it will be given the classifications Σ m 1 {\displaystyle \Sigma _{m}^{1}} and Π m 1 {\displaystyle \Pi _{m}^{1}} for all m {\displaystyle m} greater than n {\displaystyle n} .

The analytical hierarchy of sets of natural numbers

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

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

A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from ω {\displaystyle \omega } to ω {\displaystyle \omega } to the characteristic function of its graph. A subset of Baire space is given the classification Σ n 1 {\displaystyle \Sigma _{n}^{1}} , Π n 1 {\displaystyle \Pi _{n}^{1}} , or Δ n 1 {\displaystyle \Delta _{n}^{1}} 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.

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 Σ n 1 , A {\displaystyle \Sigma _{n}^{1,A}} or Π n 1 , A {\displaystyle \Pi _{n}^{1,A}} using the same inductive definition as above. Given a set Y {\displaystyle Y} , a set is defined to be Σ n 1 , Y {\displaystyle \Sigma _{n}^{1,Y}} if it is definable by a Σ n 1 , A {\displaystyle \Sigma _{n}^{1,A}} formula in which the symbol A {\displaystyle A} is interpreted as Y {\displaystyle Y} ; similar definitions for Π n 1 , Y {\displaystyle \Pi _{n}^{1,Y}} and Δ n 1 , Y {\displaystyle \Delta _{n}^{1,Y}} apply. The sets that are Σ n 1 , Y {\displaystyle \Sigma _{n}^{1,Y}} or Π n 1 , Y {\displaystyle \Pi _{n}^{1,Y}} , for any parameter Y, are classified in the projective hierarchy, and often denoted by boldface Greek letters to indicate the use of parameters.²

Examples

• For a relation ≺ {\displaystyle \prec } on N 2 {\displaystyle \mathbb {N} ^{2}} , the statement " ≺ {\displaystyle \prec } is a well-order on N {\displaystyle \mathbb {N} } " is Π 1 1 {\displaystyle \Pi _{1}^{1}} . (Not to be confused with the general case for well-founded relations on sets, see Lévy hierarchy)
• The set of all natural numbers that are indices of computable ordinals is a Π 1 1 {\displaystyle \Pi _{1}^{1}} set that is not Σ 1 1 {\displaystyle \Sigma _{1}^{1}} .
  • These sets are exactly the ω 1 C K {\displaystyle \omega _{1}^{CK}} -recursively-enumerable subsets of ω {\displaystyle \omega } . [Bar75, p. 168]
• A function f : N → N {\displaystyle f:\mathbb {N} \to \mathbb {N} } is definable by Herbrand's 1931 formalism of systems of equations if and only if f {\displaystyle f} is hyperarithmetical.³
• The set of continuous functions f : [ 0 , 1 ] → [ 0 , 1 ] {\displaystyle f:[0,1]\to \mathbb {[} 0,1]} that have the mean value property is no lower than Δ 2 1 {\displaystyle \Delta _{2}^{1}} on the hierarchy.⁴
• The set of elements of Cantor space that are the characteristic functions of well orderings of ω {\displaystyle \omega } is a Π 1 1 {\displaystyle \Pi _{1}^{1}} set that is not Σ 1 1 {\displaystyle \Sigma _{1}^{1}} . In fact, this set is not Σ 1 1 , Y {\displaystyle \Sigma _{1}^{1,Y}} for any element Y {\displaystyle Y} of Baire space.
• If the axiom of constructibility holds then there is a subset of the product of the Baire space with itself that is Δ 2 1 {\displaystyle \Delta _{2}^{1}} and is the graph of a well ordering of Baire space. If the axiom holds then there is also a Δ 2 1 {\displaystyle \Delta _{2}^{1}} well ordering of Cantor space.

Properties

For each n {\displaystyle n} we have the following strict containments:

Π n 1 ⊂ Σ n + 1 1 {\displaystyle \Pi _{n}^{1}\subset \Sigma _{n+1}^{1}} , Π n 1 ⊂ Π n + 1 1 {\displaystyle \Pi _{n}^{1}\subset \Pi _{n+1}^{1}} , Σ n 1 ⊂ Π n + 1 1 {\displaystyle \Sigma _{n}^{1}\subset \Pi _{n+1}^{1}} , Σ n 1 ⊂ Σ n + 1 1 {\displaystyle \Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}} .

A set that is in Σ n 1 {\displaystyle \Sigma _{n}^{1}} 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, namely Σ 1 1 {\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}} .⁵

Table

Pointclasses v t e
Lightface		Boldface
Σ00 = Π00 = Δ00 (sometimes the same as Δ01)		Σ00 = Π00 = Δ00 (if defined)
Δ01 = recursive		Δ01 = clopen
Σ01 = recursively enumerable	Π01 = co-recursively enumerable	Σ01 = G = open	Π01 = F = closed
Δ02		Δ02
Σ02	Π02	Σ02 = Fσ	Π02 = Gδ
Δ03		Δ03
Σ03	Π03	Σ03 = Gδσ	Π03 = Fσδ
⋮		⋮
Σ0<ω = Π0<ω = Δ0<ω = Σ10 = Π10 = Δ10 = arithmetical		Σ0<ω = Π0<ω = Δ0<ω = Σ10 = Π10 = Δ10 = boldface arithmetical
⋮		⋮
Δ0α (α recursive)		Δ0α (α countable)
Σ0α	Π0α	Σ0α	Π0α
⋮		⋮
Σ0ωCK1 = Π0ωCK1 = Δ0ωCK1 = Δ11 = hyperarithmetical		Σ0ω1 = Π0ω1 = Δ0ω1 = Δ11 = B = Borel
Σ11 = lightface analytic	Π11 = lightface coanalytic	Σ11 = A = analytic	Π11 = CA = coanalytic
Δ12		Δ12
Σ12	Π12	Σ12 = PCA	Π12 = CPCA
Δ13		Δ13
Σ13	Π13	Σ13 = PCPCA	Π13 = CPCPCA
⋮		⋮
Σ1<ω = Π1<ω = Δ1<ω = Σ20 = Π20 = Δ20 = analytical		Σ1<ω = Π1<ω = Δ1<ω = Σ20 = Π20 = Δ20 = P = projective
⋮		⋮

See also

• Arithmetical hierarchy
• Lévy hierarchy

• Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill.
• Kechris, A. (1995). Classical Descriptive Set Theory (Graduate Texts in Mathematics 156 ed.). Springer. ISBN 0-387-94374-9.

• Analytical hierarchy at PlanetMath.

References

1. P. Odifreddi, Classical Recursion Theory (1989), p.378. North-Holland, 0-444-87295-7 /wiki/Piergiorgio_Odifreddi ↩

2. P. D. Welch, "Weak Systems of Determinacy and Arithmetical Quasi-Inductive Definitions" (2010 draft ver., p. 3). Accessed 31 July 2022. https://people.maths.bris.ac.uk/~mapdw/det17.pdf ↩

3. P. Odifreddi, Classical Recursion Theory (1989), p.33. North-Holland, 0-444-87295-7 ↩

4. Quintanilla, M. (2022). "The realm numbers in inner models of set theory". arXiv:2206.10754 [math.LO]. /wiki/ArXiv_(identifier) ↩

5. T. Jech, "The Brave New World of Determinacy" (PDF download). Book review, Bulletin of the American Mathematical Society, vol. 5, number 3, November 1981 (pp.339--349). /wiki/Thomas_Jech ↩