projective hierarchy

In the mathematical field of descriptive set theory, a subset $A$ of a Polish space $X$ is projective if it is $\boldsymbol^1_n$ for some positive integer $n$. Here $A$ is
* $\boldsymbol^1_1$ if $A$ is analytic
* $\boldsymbol^1_n$ if the complement of $A$, $X\setminus A$, is $\boldsymbol^1_n$
* $\boldsymbol^1_$ if there is a Polish space $Y$ and a $\boldsymbol^1_n$ subset $C\subseteq X\times Y$ such that $A$ is the projection of $C$; that is, $A=\$

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$ and $\boldsymbol$). Not every $\boldsymbol^1_n$ subset of Baire space is $\Sigma^1_n$. It is true, however, that if a subset ''X'' of Baire space is $\boldsymbol^1_n$ then there is a set of natural numbers ''A'' such that ''X'' is $\Sigma^_n$. A similar statement holds for $\boldsymbol^1_n$ 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

References

*
* {{Citation , last1=Rogers , first1=Hartley , author-link= Hartley Rogers, title=The Theory of Recursive Functions and Effective Computability , orig-year=1967 , publisher=First MIT press paperback edition , isbn=978-0-262-68052-3 , year=1987

Descriptive set theory
Mathematical logic hierarchies