Descriptive Set Theory — Mathematics Knowledge System

Overview

Descriptive set theory studies the complexity of subsets of Polish spaces (complete separable metric spaces), classifying them through the Borel and projective hierarchies. It connects logic, topology, and measure theory, and has deep interactions with determinacy axioms, large cardinals, and effective computability.

Intuition

Start with open sets in $\mathbb{R}$. Closed under countable unions: $G_\delta$ sets. Closed under countable intersections: $F_\sigma$ sets. Continue transfinitely to build the Borel hierarchy. Beyond Borel: analytic sets (projections of Borel sets), co-analytic sets, and further up the projective hierarchy. Higher levels require stronger set-theoretic axioms.

Formal Definition

Definition

\mathbf{\Sigma}^0_1 = \text{open sets}, \quad \mathbf{\Pi}^0_1 = \text{closed sets}, \quad \mathbf{\Delta}^0_1 = \text{clopen sets}

Base of the Borel hierarchy

borel-base

\mathbf{\Sigma}^0_{\alpha} = \left\{ \bigcup_{n} A_n : A_n \in \mathbf{\Pi}^0_{\beta_n},\, \beta_n < \alpha \right\}

Sigma-level of the Borel hierarchy at ordinal alpha

borel-sigma

\mathbf{\Sigma}^1_1 = \{ A \subseteq X : A = \pi(B),\, B \in \mathbf{\Pi}^0_1(X \times \omega^\omega) \}

Analytic sets: continuous images (projections) of closed sets

analytic

\mathbf{\Pi}^1_1 = \complement \mathbf{\Sigma}^1_1 \quad (\text{co-analytic sets})

Co-analytic sets: complements of analytic sets

co-analytic

Notation

Notation	Meaning
$\mathbf{\Sigma}^0_\alpha$	Level α of the Borel hierarchy (countable unions of lower Π sets)
$\mathbf{\Pi}^0_\alpha$	Level α of the Borel hierarchy (complements of Σ sets)
$\mathbf{\Sigma}^1_1$	Analytic sets: projections of Borel sets
$\mathbf{\Pi}^1_1$	Co-analytic sets: complements of analytic sets
$\mathbf{\Delta}^1_1$	Borel sets = analytic ∩ co-analytic

Theorems

Theorem 1: Suslin's Theorem

A subset of a Polish space is Borel iff it is both analytic (\mathbf{\Sigma}^1_1) and co-analytic (\mathbf{\Pi}^1_1): \mathbf{\Delta}^1_1 = \mathbf{B} (Borel sets).

Theorem 2: Perfect Set Property for Analytic Sets

Every uncountable analytic subset of a Polish space contains a perfect subset (a closed set with no isolated points), hence has cardinality \mathfrak{c} = 2^{\aleph_0}.

Theorem 3: Borel Determinacy (Martin 1975)

Every Borel game on \omega is determined: in the infinite two-player perfect-information game G(A) for A \in \mathbf{B}, one of the two players has a winning strategy.

Worked Examples

For each rational $q \in \mathbb{Q}$, the singleton $\{q\}$ is closed ($\mathbf{\Pi}^0_1$) and hence $\mathbb{R} \setminus \{q\}$ is open ($\mathbf{\Sigma}^0_1$).
The irrationals equal $\bigcap_{q \in \mathbb{Q}} (\mathbb{R} \setminus \{q\})$ — a countable intersection of open sets — which is by definition a $G_\delta$ set ($\mathbf{\Pi}^0_2$).
$\mathbb{R} \setminus \mathbb{Q} = \bigcap_{q \in \mathbb{Q}} (\mathbb{R} \setminus \{q\}) \in \mathbf{\Pi}^0_2$

Answer: $\mathbb{R} \setminus \mathbb{Q}$ is a $G_\delta$ ($\mathbf{\Pi}^0_2$) set, but not $F_\sigma$ by Baire category arguments.

Practice Problems

Difficulty 7/10

Show that the set $\{f \in C([0,1]) : f \text{ is differentiable at some point}\}$ is analytic.

Difficulty 8/10

State Suslin's theorem and explain why $\mathbf{\Sigma}^1_1 \setminus \mathbf{\Pi}^1_1 \neq \emptyset$ (i.e., there exist analytic non-Borel sets).

Difficulty 9/10

What is projective determinacy (PD) and why is it not provable from ZFC alone?

Historical Background

The field grew from attempts to understand 'definable' sets of reals in analysis. Borel, Baire, and Lebesgue studied measurability at the turn of the 20th century. Suslin discovered analytic sets (projections of Borel sets) in 1917 after finding an error in Lebesgue's work. Luzin and his Moscow school developed the projective hierarchy. Modern descriptive set theory, following Moschovakis and Martin, links the hierarchy intimately to large cardinal axioms and determinacy.

1898
Borel introduces Borel sets
Émile Borel
1905
Lebesgue studies measurable sets and Baire category
Henri Lebesgue
1917
Suslin discovers analytic sets and the error in Lebesgue's claim
Mikhail Suslin
1920s
Luzin and Moscow school develop the projective hierarchy
Nikolai Luzin
1975
Martin proves Borel determinacy from ZFC
Donald Martin

Summary

Descriptive set theory classifies subsets of Polish spaces by complexity: Borel, analytic, projective.
The Borel hierarchy $\mathbf{\Sigma}^0_\alpha / \mathbf{\Pi}^0_\alpha$ is indexed by countable ordinals.
Analytic sets ($\mathbf{\Sigma}^1_1$) are projections of Borel sets; they are all measurable and have the perfect set property.
Suslin's theorem: a set is Borel iff it is both analytic and co-analytic.
Higher levels of the projective hierarchy depend on large cardinal axioms and determinacy.

References

BookKechris, A. Classical Descriptive Set Theory. Springer, 1995.
BookMoschovakis, Y. Descriptive Set Theory (2nd ed.). AMS, 2009.