Open main menu

Projective hierarchy

In the mathematical field of descriptive set theory, a subset of a Polish space is projective if it is for some positive integer . Here is

  • if is analytic
  • if the complement of , , is
  • if there is a Polish space and a subset such that is the projection of ; that is,

The choice of the Polish space 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 hierarchyEdit

There is a close relationship between the relativized analytical hierarchy on subsets of Baire space (denoted by lightface letters   and  ) and the projective hierarchy on subsets of Baire space (denoted by boldface letters   and  ). Not every   subset of Baire space is  . It is true, however, that if a subset X of Baire space is   then there is a set of natural numbers A such that X is  . A similar statement holds for   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.

TableEdit

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


ReferencesEdit

  • 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