Projective hierarchy
In the mathematical field of descriptive set theory, a subset [math]\displaystyle{ A }[/math] of a Polish space [math]\displaystyle{ X }[/math] is projective if it is [math]\displaystyle{ \boldsymbol{\Sigma}^1_n }[/math] for some positive integer [math]\displaystyle{ n }[/math]. Here [math]\displaystyle{ A }[/math] is
- [math]\displaystyle{ \boldsymbol{\Sigma}^1_1 }[/math] if [math]\displaystyle{ A }[/math] is analytic
- [math]\displaystyle{ \boldsymbol{\Pi}^1_n }[/math] if the complement of [math]\displaystyle{ A }[/math], [math]\displaystyle{ X\setminus A }[/math], is [math]\displaystyle{ \boldsymbol{\Sigma}^1_n }[/math]
- [math]\displaystyle{ \boldsymbol{\Sigma}^1_{n+1} }[/math] if there is a Polish space [math]\displaystyle{ Y }[/math] and a [math]\displaystyle{ \boldsymbol{\Pi}^1_n }[/math] subset [math]\displaystyle{ C\subseteq X\times Y }[/math] such that [math]\displaystyle{ A }[/math] is the projection of [math]\displaystyle{ C }[/math] onto [math]\displaystyle{ X }[/math]; that is, [math]\displaystyle{ A=\{x\in X \mid \exists y\in Y : (x,y)\in C\}. }[/math]
The choice of the Polish space [math]\displaystyle{ Y }[/math] 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 [math]\displaystyle{ \Sigma }[/math] and [math]\displaystyle{ \Pi }[/math]) and the projective hierarchy on subsets of Baire space (denoted by boldface letters [math]\displaystyle{ \boldsymbol{\Sigma} }[/math] and [math]\displaystyle{ \boldsymbol{\Pi} }[/math]). Not every [math]\displaystyle{ \boldsymbol{\Sigma}^1_n }[/math] subset of Baire space is [math]\displaystyle{ \Sigma^1_n }[/math]. It is true, however, that if a subset X of Baire space is [math]\displaystyle{ \boldsymbol{\Sigma}^1_n }[/math] then there is a set of natural numbers A such that X is [math]\displaystyle{ \Sigma^{1,A}_n }[/math]. A similar statement holds for [math]\displaystyle{ \boldsymbol{\Pi}^1_n }[/math] 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
See also
References
- Kechris, A. S. (1995), Classical Descriptive Set Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94374-9, https://archive.org/details/classicaldescrip0000kech
- Rogers, Hartley (1987), The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3
 |  |
