wikiwand.com

Projective hierarchy - Wikiwand

"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 ${\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

Summarize

Perspective

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

More information Lightface, Boldface ...

Pointclasses v t e
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
⋮	⋮

Projective hierarchy - Wikiwand

Relationship to the analytical hierarchy

Table

See also

References