BREAKING NEWS

## Summary

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 _{n}^{1}$ . 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 ⋮ ⋮ ReferencesEdit
• Kechris, A. S. (1995), Classical Descriptive Set Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94374-9
• Rogers, Hartley (1987) , The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3