ART

In the mathematical field of descriptive set theory, 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 \mid \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.

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{\Sigma} \)and \( \boldsymbol{\Pi}) \). Not every \( {\boldsymbol {\Sigma }}_{n}^{1} \) subset of Baire space is \( \Sigma^1_n \). 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.
Table

Lightface Boldface
Σ0
0 = Π0
0 = Δ0
0 (sometimes the same as Δ0
1)
Σ0
0
= Π0
0
= Δ0
0
(if defined)
Δ0
1 = recursive
Δ0
1
= clopen
Σ0
1 = recursively enumerable
Π0
1 = co-recursively enumerable
Σ0
1
= G = open
Π0
1
= F = closed
Δ0
2
Δ0
2
Σ0
2
Π0
2
Σ0
2
= Fσ
Π0
2
= Gδ
Δ0
3
Δ0
3
Σ0
3
Π0
3
Σ0
3
= Gδσ
Π0
3
= Fσδ
Σ0
= Π0
= Δ0
= Σ1
0 = Π1
0 = Δ1
0 = arithmetical
Σ0
= Π0
= Δ0
= Σ1
0
= Π1
0
= Δ1
0
= boldface arithmetical
Δ0
α (α recursive)
Δ0
α
(α countable)
Σ0
α
Π0
α
Σ0
α
Π0
α
Σ0
ωCK
1
= Π0
ωCK
1
= Δ0
ωCK
1
= Δ1
1 = hyperarithmetical
Σ0
ω1
= Π0
ω1
= Δ0
ω1
= Δ1
1
= B = Borel
Σ1
1 = lightface analytic
Π1
1 = lightface coanalytic
Σ1
1
= A = analytic
Π1
1
= CA = coanalytic
Δ1
2
Δ1
2
Σ1
2
Π1
2
Σ1
2
= PCA
Π1
2
= CPCA
Δ1
3
Δ1
3
Σ1
3
Π1
3
Σ1
3
= PCPCA
Π1
3
= CPCPCA
Σ1
= Π1
= Δ1
= Σ2
0 = Π2
0 = Δ2
0 = analytical
Σ1
= Π1
= Δ1
= Σ2
0
= Π2
0
= Δ2
0
= P = projective


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

 

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License