Projective hierarchy

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|(\exists y\in Y)<x,y>\in C\}$

Note that 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 and the projective hierarchy on subsets of Baire space. 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.