Projective hierarchy

Short description: Descriptive set theory concept

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.

## Contents

* 1 Relationship to the analytical hierarchy
* 2 Table
* 3 See also
* 4 References

## 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

* Borel hierarchy

## 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Projective hierarchy. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Projective_hierarchy&oldid=3367264"