Projective hierarchy

In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is \( {\boldsymbol {\Sigma }}_{n}^{1} \) for some positive integer n. Here A is

\( {\boldsymbol {\Sigma }}_{1}^{1} \) if A is analytic
\( {\boldsymbol {\Pi }}_{n}^{1}\) if the complement of A, \( X\setminus A \), is \( {\boldsymbol {\Sigma }}_{n}^{1} \)
\( {\boldsymbol {\Sigma }}_{{n+1}}^{1} \) if there is a Polish space Y and a \( {\boldsymbol {\Pi }}_{n}^{1} \) subset \( C\subseteq X\times Y \) such that A is the projection of C; that is, \( A=\{x\in X \mid \exists y\in Y (x,y)\in C\} \)

The choice of the Polish space Y in the third clause above is not very important; it could be replaced in the definition by a fixed uncountable Polish space, say Baire space or Cantor space or the real line.

Relationship to the analytical hierarchy

There is a close relationship between the relativized analytical hierarchy on subsets of Baire space (denoted by lightface letters \( \Sigma \) and \( \Pi ) \) and the projective hierarchy on subsets of Baire space (denoted by boldface letters \( } \boldsymbol{\Sigma} \)and \( \boldsymbol{\Pi}) \). Not every \( {\boldsymbol {\Sigma }}_{n}^{1} \) subset of Baire space is \( \Sigma^1_n \). It is true, however, that if a subset X of Baire space is \( {\boldsymbol {\Sigma }}_{n}^{1} \) then there is a set of natural numbers A such that X is \( \Sigma _{n}^{{1,A}} \). A similar statement holds for \( {\boldsymbol {\Pi }}_{n}^{1} \) sets. Thus the sets classified by the projective hierarchy are exactly the sets classified by the relativized version of the analytical hierarchy. This relationship is important in effective descriptive set theory.

A similar relationship between the projective hierarchy and the relativized analytical hierarchy holds for subsets of Cantor space and, more generally, subsets of any effective Polish space.
Table

Lightface		Boldface
Σ0 0 = Π0 0 = Δ0 0 (sometimes the same as Δ0 1)		Σ0 0 = Π0 0 = Δ0 0 (if defined)
Δ0 1 = recursive		Δ0 1 = clopen
Σ0 1 = recursively enumerable	Π0 1 = co-recursively enumerable	Σ0 1 = G = open	Π0 1 = F = closed
Δ0 2		Δ0 2
Σ0 2	Π0 2	Σ0 2 = Fσ	Π0 2 = Gδ
Δ0 3		Δ0 3
Σ0 3	Π0 3	Σ0 3 = Gδσ	Π0 3 = Fσδ
⋮		⋮
Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = arithmetical		Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = boldface arithmetical
⋮		⋮
Δ0 α (α recursive)		Δ0 α (α countable)
Σ0 α	Π0 α	Σ0 α	Π0 α
⋮		⋮
Σ0 ωCK 1 = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1 = hyperarithmetical		Σ0 ω1 = Π0 ω1 = Δ0 ω1 = Δ1 1 = B = Borel
Σ1 1 = lightface analytic	Π1 1 = lightface coanalytic	Σ1 1 = A = analytic	Π1 1 = CA = coanalytic
Δ1 2		Δ1 2
Σ1 2	Π1 2	Σ1 2 = PCA	Π1 2 = CPCA
Δ1 3		Δ1 3
Σ1 3	Π1 3	Σ1 3 = PCPCA	Π1 3 = CPCPCA
⋮		⋮
Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = analytical		Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = P = projective
⋮		⋮

References
Kechris, A. S. (1995), Classical Descriptive Set Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94374-9
Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License