Projective hierarchy

Short description: Descriptive set theory concept

"Projective set" redirects here. For the card game, see Projective Set (game).

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

* Σ11 if A is analytic
* Πn1 if the complement of A, X∖A, is Σn1
* Σn+11 if there is a Polish space Y and a Πn1 subset C⊆X×Y such that A is the projection of C onto X; that is, A={x∈X∣∃y∈Y:(x,y)∈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.

## 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 Σ and Π) and the projective hierarchy on subsets of Baire space (denoted by boldface letters Σ and Π). Not every Σn1 subset of Baire space is Σn1. It is true, however, that if a subset X of Baire space is Σn1 then there is a set of natural numbers A such that X is Σn1,A. A similar statement holds for Πn1 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. Stated in terms of definability, a set of reals is projective iff it is definable in the language of second-order arithmetic from some real parameter.[1]

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

|

Σ00 = Π00 = Δ00 (sometimes the same as Δ01)  | Σ00 = Π00 = Δ00 (if defined)
Δ01 = recursive | Δ01 = clopen
Σ01 = recursively enumerable | Π01 = co-recursively enumerable  | Σ01 = G = open | Π01 = F = closed
Δ02 | Δ02
Σ02 | Π02 | Σ02 = Fσ | Π02 = Gδ
Δ03 | Δ03
Σ03 | Π03 | Σ03 = Gδσ | Π03 = Fσδ
⋮  | ⋮
Σ0<ω = Π0<ω = Δ0<ω = Σ10 = Π10 = Δ10 = arithmetical | Σ0<ω = Π0<ω = Δ0<ω = Σ10 = Π10 =  Δ10 = boldface arithmetical
⋮  | ⋮
Δ0α (α recursive)  | Δ0α (α countable)
Σ0α | Π0α | Σ0α | Π0α
⋮  | ⋮
Σ0ωCK1 = Π0ωCK1 = Δ0ωCK1 = Δ11 = hyperarithmetical | Σ0ω1 = Π0ω1 = Δ0ω1 = Δ11 = B = Borel
Σ11 = lightface analytic  | Π11 = lightface coanalytic  | Σ11 = A = analytic | Π11 = CA = coanalytic
Δ12 | Δ12
Σ12 | Π12 | Σ12 = PCA  | Π12 = CPCA
Δ13 | Δ13
Σ13 | Π13 | Σ13 = PCPCA  | Π13 = CPCPCA
⋮  | ⋮
Σ1<ω = Π1<ω = Δ1<ω = Σ20 = Π20 = Δ20 = analytical | Σ1<ω = Π1<ω = Δ1<ω = Σ20 = Π20 =  Δ20 = P = projective
⋮  | ⋮

## See also

* Borel hierarchy

## References

1. ↑ J. Steel, "What is... a Woodin cardinal?". Notices of the American Mathematical Society vol. 54, no. 9 (2007), p.1147.

* 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=3990751"