Projective hierarchy

From Wikipedia, the free encyclopedia

In the mathematical field of descriptive set theory, a subset $A$ of a Polish space $X$ is projective if it is $\boldsymbol{\Sigma}^1_n$ for some positive integer $n$ . Here $A$ is

$\boldsymbol{\Sigma}^1_1$ if $A$ is analytic
$\boldsymbol{\Pi}^1_n$ if the complement of $A$ , $X\setminus A$ , is $\boldsymbol{\Sigma}^1_n$
$\boldsymbol{\Sigma}^1_{n+1}$ if there is a Polish space $Y$ and a $\boldsymbol{\Pi}^1_n$ 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\}$

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.

[edit] 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}^1_n$ subset of Baire space is $\Sigma^1_n$ . It is true, however, that if a subset X of Baire space is $\boldsymbol{\Sigma}^1_n$ then there is a set of natural numbers A such that X is $\Sigma^{1,A}_n$ . A similar statement holds for $\boldsymbol{\Pi}^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.

[edit] References

Kechris, A. S. (1995), Classical Descriptive Set Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94374-9
Rogers, Hartley (1987), The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3