Projective hierarchy

"Projective set" redirects here. For the card game, see Projective Set (game).

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}$ onto ${\displaystyle X}$; 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

This box:

• view
• talk
• edit

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