Projective hierarchy

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$ onto $X$ ; 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 _{n}^{1}$ . 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
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (sometimes the same as Δ⁰ ₁)		Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (if defined)
Δ⁰ ₁ = recursive		Δ⁰ ₁ = clopen
Σ⁰ ₁ = recursively enumerable	Π⁰ ₁ = co-recursively enumerable	Σ⁰ ₁ = G = open	Π⁰ ₁ = F = closed
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂ = F_σ	Π⁰ ₂ = G_δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃ = G_δσ	Π⁰ ₃ = F_σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = arithmetical		Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = boldface arithmetical
⋮		⋮
Δ⁰ _α (α recursive)		Δ⁰ _α (α countable)
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK ₁ = Π⁰ _ω^CK ₁ = Δ⁰ _ω^CK ₁ = Δ¹ ₁ = hyperarithmetical		Σ⁰ _ω₁ = Π⁰ _ω₁ = Δ⁰ _ω₁ = Δ¹ ₁ = B = Borel
Σ¹ ₁ = lightface analytic	Π¹ ₁ = lightface coanalytic	Σ¹ ₁ = A = analytic	Π¹ ₁ = CA = coanalytic
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = analytical		Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Relationship to the analytical hierarchy

Table

See also

References