BREAKING NEWS
Projective hierarchy

Summary

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

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

The choice of the Polish space ${\displaystyle 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 ${\displaystyle \Sigma }$  and ${\displaystyle \Pi }$ ) and the projective hierarchy on subsets of Baire space (denoted by boldface letters ${\displaystyle {\boldsymbol {\Sigma }}}$  and ${\displaystyle {\boldsymbol {\Pi }}}$ ). Not every ${\displaystyle {\boldsymbol {\Sigma }}_{n}^{1}}$  subset of Baire space is ${\displaystyle \Sigma _{n}^{1}}$ . It is true, however, that if a subset X of Baire space is ${\displaystyle {\boldsymbol {\Sigma }}_{n}^{1}}$  then there is a set of natural numbers A such that X is ${\displaystyle \Sigma _{n}^{1,A}}$ . A similar statement holds for ${\displaystyle {\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 ⋮ ⋮ ReferencesEdit
• 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