# Projective hierarchy

(Redirected from Projective set)

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 α ... ... Σ = Π = Δ = Δ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 ... ...