Descriptive set theory · The Lumenary

Lens

MotivationH

Lebesgue's mistake

In 1905 Henri Lebesgue, studying functions "representable analytically", asserted in passing that the projection of a Borel subset of the plane onto a line is again Borel. The proof looked routine: projection commutes with unions. It does not commute with intersections, and around 1916 Mikhail Suslin, a student of Nikolai Lusin in Moscow, found the error. He defined the class of analytic sets — projections of Borel sets — and proved that it is strictly larger than the class of Borel sets, while still behaving well: every uncountable analytic set has the cardinality of the continuum.

This launched descriptive set theory: the study of definable sets of reals and of other Polish spaces, organised by the complexity of their definitions. Its guiding theme is that definable sets are well behaved — no definable set should be a counterexample to the continuum hypothesis, or non-measurable — and its methods combine point-set topology, set theory and logic. Today it is also a tool: it measures the complexity of classification problems in algebra and dynamics, and it explains which constructions in analysis need the axiom of choice.

IntuitionH

Complexity as quantifiers

Membership in an open subset of $\R$ is witnessed by finite information: $x \in U$ because some rational interval around $x$ lies in $U$ — an existential quantifier over $\N$ . A closed set is the complement: $x \in F$ if no finite approximation refutes it — a universal quantifier over $\N$ . Each further alternation of quantifiers over $\N$ climbs a level of the Borel hierarchy: $G_\delta$ sets are " $\forall n\, \exists m$ ", $F_{\sigma\delta}$ sets are " $\forall n\, \exists m\, \forall k$ ", and so on transfinitely.

A projection adds a quantifier over a whole real: $x \in \pi[B]$ iff there exists $y$ with $(x, y) \in B$ . That is a different kind of quantifier — a search through uncountably many candidates — and it is why projections escape the Borel sets. In Baire space $\N^\N$ such a search is a search for an infinite branch through a tree.

A closed subset of Cantor space $2^\N$ is the set of infinite branches of a tree of finite binary strings. Here: the sequences with at most one $1$. Its branches are $000\ldots$ and the sequences $0\cdots 0 1 0 0 \ldots$; every branch except $000\ldots$ is isolated, so this closed set is countable.

DefinitionsH

Polish spaces, trees and hierarchies

Definition— Polish space

A topological space is Polish if it is separable and completely metrisable. Examples: $\R^n$ , $[0, 1]$ , $\C$ , every separable Banach space, Baire space $\mathcal N = \N^\N$ and Cantor space $\mathcal C = 2^\N$ (product topologies), and the irrationals $\R \setminus \Q$ , which are homeomorphic to $\mathcal N$ via continued fractions. Countable products and $G_\delta$ subspaces of Polish spaces are Polish. $\Q$ is not Polish (by the Baire category theorem).

Definition— trees

A tree on a set $A$ is a set $T$ of finite sequences from $A$ closed under initial segments; its body $[T]$ is the set of infinite sequences all of whose initial segments lie in $T$ . $T$ is pruned if every node has a proper extension in $T$ , and well-founded if $[T] = \varnothing$ . The basic open sets of $A^\N$ are $N_s = \{x : s \subset x\}$ . The closed subsets of $A^\N$ are exactly the bodies of (pruned) trees: $F = [T_F]$ with $T_F = \{x \restriction n : x \in F, n \in \N\}$ .

Definition— the Borel hierarchy

In a metrisable space $X$ , let $\Sigma^0_1$ be the open sets; for $1 \le \alpha \lt \omega_1$ let $\Pi^0_\alpha$ be the complements of $\Sigma^0_\alpha$ sets, and let $\Sigma^0_\alpha$ (for $\alpha \gt 1$ ) consist of countable unions of sets in $\bigcup_{\beta \lt \alpha} \Pi^0_\beta$ . Put $\Delta^0_\alpha = \Sigma^0_\alpha \cap \Pi^0_\alpha$ . So $\Pi^0_1$ = closed, $\Sigma^0_2 = F_\sigma$ , $\Pi^0_2 = G_\delta$ . The Borel sets — the smallest $\sigma$ -algebra containing the open sets — are $\bigcup_{\alpha \lt \omega_1} \Sigma^0_\alpha$ . (These are the classical "boldface" classes, often printed in bold.)

Definition— analytic, coanalytic, projective

A subset $A$ of a Polish space $X$ is analytic ( $\Sigma^1_1$ ) if it is empty or a continuous image of $\mathcal N$ ; equivalently, the projection of a closed subset of $X \times \mathcal N$ , or of a Borel subset of $X \times Y$ for some Polish $Y$ . It is coanalytic ( $\Pi^1_1$ ) if its complement is analytic, and $\Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1$ . The projective hierarchy continues: $\Sigma^1_{n+1}$ sets are projections of $\Pi^1_n$ sets, $\Pi^1_{n+1}$ their complements.

Definition— perfect set property

A set is perfect if it is closed, non-empty and has no isolated points. A set $A$ has the perfect set property if it is countable or contains a perfect subset. A non-empty perfect subset of a Polish space contains a homeomorphic copy of $\mathcal C$ , so it has cardinality $2^{\aleph_0}$ ; hence no set with the perfect set property is a counterexample to CH.

Explore

The hierarchy at a glance

Hooked arrows are inclusions, all proper in any uncountable Polish space (Lebesgue, using universal sets). The Borel hierarchy has $\omega_1$ levels; above it come the projective classes, starting with the analytic and coanalytic sets, whose intersection is exactly the Borel sets by Suslin's theorem.

The Borel hierarchy (open, closed,

F_\sigma

G_\delta

, …, through all countable ordinals) and the first projective classes.

\Delta^1_1

is the class of Borel sets.

Try placing sets on the diagram as you read: a closed interval, $\Q$ , the irrationals, the set of sequences in $2^\N$ with infinitely many $1$ s, the set of everywhere-differentiable functions in $C[0, 1]$ .

Worked examplesH

Locating sets

Example— Rationals and irrationals

$\Q \subseteq \R$ is a countable union of closed singletons, so it is $\Sigma^0_2$ . It is not $\Pi^0_2$ : the irrationals are a dense $G_\delta$ , and if $\Q$ were a $G_\delta$ too, the Baire category theorem would make the empty set $\Q \cap (\R \setminus \Q)$ dense. Dually the irrationals are $\Pi^0_2$ but not $\Sigma^0_2$ . (The formal section proves this in Lean.)

Example— Sets of sequences

In $2^\N$ : $\{x : x(0) = 1\}$ is clopen; $\{x : \exists n\, x(n) = 1\}$ is open, not closed; $\{x : x \text{ has infinitely many } 1\text{s}\} = \bigcap_n \bigcup_{m \gt n} \{x : x(m) = 1\}$ is $\Pi^0_2$ , and by the same Baire category argument not $\Sigma^0_2$ ; the set of $x$ whose averages $\frac1n \sum_{i \lt n} x(i)$ converge to $\frac12$ is $\Pi^0_3$ ("for every $k$ there is $N$ such that for all $n \ge N$ the average is within $1/k$ ").

Example— Beyond Borel

Coding trees on $\N$ by points of $2^{\N^{\lt\N}}$ , the set $\mathrm{IF}$ of ill-founded trees (those with an infinite branch) is analytic: $T \in \mathrm{IF}$ iff $\exists x \in \mathcal N\; \forall n\; x \restriction n \in T$ . The set $\mathrm{WF}$ of well-founded trees is coanalytic. Neither is Borel; they are complete for their classes. Mazurkiewicz (1936) showed that the set of everywhere-differentiable functions in $C[0, 1]$ is coanalytic but not Borel — a natural set of analysis beyond the Borel hierarchy.

ProofH

The perfect set theorem and Suslin's theorem

Throughout, $X$ is a Polish space with a compatible complete metric $d$ .

Theorem— Perfect set theorem for analytic sets (Suslin 1917)

Every uncountable analytic set $A \subseteq X$ contains a homeomorphic copy of $\mathcal C$ . In particular it contains a perfect set and has cardinality $2^{\aleph_0}$ .

Proof

Let $A = f[\mathcal N]$ with $f : \mathcal N \to X$ continuous. Let $U$ be the union of all basic open sets $N_s$ with $f[N_s]$ countable; $f[U]$ is countable, being a countable union of countable sets. Put $F = \mathcal N \setminus U$ , a closed set, non-empty since $A$ is uncountable.

Key property: if $N_s \cap F \neq \varnothing$ then $f[N_s \cap F]$ is uncountable. Otherwise $f[N_s] \subseteq f[N_s \cap F] \cup f[U]$ would be countable, so $N_s \subseteq U$ , contradicting $N_s \cap F \neq \varnothing$ .

We assign to each finite binary string $u$ a finite sequence $s_u \in \N^{\lt\N}$ with $N_{s_u} \cap F \neq \varnothing$ . Let $s_\varnothing = \varnothing$ . Given $s_u$ , the key property gives $y_0, y_1 \in N_{s_u} \cap F$ with $f(y_0) \neq f(y_1)$ . Choose disjoint closed balls $B_0 \ni f(y_0)$ and $B_1 \ni f(y_1)$ of radius at most $2^{-|u|}$ . By continuity of $f$ at $y_i$ there is a proper extension $s_{u\frown i}$ of $s_u$ with $y_i \in N_{s_{u\frown i}}$ and $f[N_{s_{u\frown i}}] \subseteq B_i$ .

For $z \in \mathcal C$ , the sequences $s_{z \restriction n}$ extend one another and their lengths increase, so they converge to a point $y_z \in \mathcal N$ ; since each $N_{s_{z\restriction n}}$ meets the closed set $F$ , $y_z \in F$ . The map $g(z) = f(y_z)$ is continuous. It is injective: if $z \neq z'$ first differ at place $n$ , then $g(z)$ and $g(z')$ lie in the two disjoint balls chosen at stage $u = z \restriction n$ . As $\mathcal C$ is compact, $g$ is a homeomorphism onto $g[\mathcal C] \subseteq A$ , a compact set without isolated points.

∎

So no analytic set is a counterexample to CH. For closed sets this is the Cantor–Bendixson theorem; for Borel sets it was proved by Alexandrov and by Hausdorff (1916).

Two sets $P, Q$ are Borel-separated if some Borel set $C$ satisfies $P \subseteq C$ and $C \cap Q = \varnothing$ .

Theorem— Lemma (separation is countably additive)

If $P = \bigcup_m P_m$ , $Q = \bigcup_n Q_n$ , and each $P_m$ is Borel-separated from each $Q_n$ , then $P$ is Borel-separated from $Q$ .

Proof

If $C_{mn}$ separates $P_m$ from $Q_n$ , then $C = \bigcup_m \bigcap_n C_{mn}$ is Borel, contains every $P_m$ , and is disjoint from every $Q_n$ .

∎

Theorem— Lusin separation theorem (1927)

If $A$ and $B$ are disjoint analytic subsets of $X$ , there is a Borel set $C$ with $A \subseteq C$ and $C \cap B = \varnothing$ .

Proof

We may assume $A = f[\mathcal N]$ and $B = g[\mathcal N]$ with $f, g$ continuous. Suppose $A$ and $B$ are not Borel-separated. Since $f[N_s] = \bigcup_i f[N_{s \frown i}]$ and $g[N_t] = \bigcup_j g[N_{t \frown j}]$ , the lemma shows: if $f[N_s]$ and $g[N_t]$ are not Borel-separated, then neither are $f[N_{s\frown i}]$ and $g[N_{t \frown j}]$ for some $i, j$ . Starting from $s = t = \varnothing$ we obtain $x, y \in \mathcal N$ such that $f[N_{x \restriction n}]$ and $g[N_{y \restriction n}]$ are not Borel-separated for any $n$ . But $f(x) \in A$ and $g(y) \in B$ are distinct, so they have disjoint open neighbourhoods $V$ and $W$ ; by continuity, for large $n$ , $f[N_{x \restriction n}] \subseteq V$ and $g[N_{y \restriction n}] \subseteq W$ , and the open set $V$ separates them — a contradiction.

∎

Theorem— Suslin's theorem (1917)

A subset of a Polish space is Borel if and only if it is both analytic and coanalytic: $\Delta^1_1 =$ Borel.

Proof

Borel sets are analytic (the formal section cites Mathlib's proof: a Borel set is closed in a finer Polish topology, hence a continuous image of $\mathcal N$ ), and so are their complements. Conversely, if $A$ and $X \setminus A$ are analytic, the Lusin separation theorem gives a Borel $C$ with $A \subseteq C$ and $C \cap (X \setminus A) = \varnothing$ , i.e. $A = C$ .

∎

Theorem— Theorem (Suslin): an analytic set that is not Borel

There is an analytic subset of $\mathcal N$ that is not coanalytic, hence not Borel.

Proof

(Sketch.) There is a universal analytic set $\mathcal U \subseteq \mathcal N \times \mathcal N$ : every analytic subset of $\mathcal N$ is a section $\mathcal U_a = \{x : (a, x) \in \mathcal U\}$ . (Code closed subsets of $\mathcal N \times \mathcal N$ by trees, and trees by points of $\mathcal N$ ; then project.) The diagonal $D = \{x : (x, x) \in \mathcal U\}$ is analytic. If its complement were analytic, it would be $\mathcal U_a$ for some $a$ , and then $a \in D \iff (a, a) \in \mathcal U \iff a \in \mathcal U_a \iff a \notin D$ .

∎

The same diagonal argument as in Cantor's and Gödel's theorems. Lebesgue's claim fails because projections can produce any analytic set — for instance, $D$ is the projection of a closed subset of $\mathcal N \times \mathcal N$ — while injective continuous images of Borel sets are Borel (the Lusin–Souslin theorem).

ExplanationH

Projective sets and the limits of ZFC

The good behaviour of analytic sets does not continue up the projective hierarchy in ZFC alone.

What ZFC proves. $\Sigma^1_1$ sets have the perfect set property (above), and $\Sigma^1_1$ and $\Pi^1_1$ sets are Lebesgue measurable and have the property of Baire (Lusin, Sierpiński). Every uncountable $\Sigma^1_2$ set has cardinality $\aleph_1$ or $2^{\aleph_0}$ (a consequence of Shoenfield absoluteness and the analysis of $\Sigma^1_2$ sets as unions of $\aleph_1$ Borel sets).
What $V = L$ gives. In Gödel's $L$ there is a $\Sigma^1_2$ well-order of the reals, hence a $\Delta^1_2$ set that is not Lebesgue measurable, and an uncountable $\Pi^1_1$ set with no perfect subset. So ZFC cannot prove that $\Pi^1_1$ sets have the perfect set property, nor that $\Delta^1_2$ sets are measurable (if ZFC is consistent).
What large cardinals give. Determinacy of infinite games is the unifying principle. Gale and Stewart (1953) showed open games are determined; Martin (1975) proved Borel determinacy in ZFC. Martin and Steel (1989) proved that if there are infinitely many Woodin cardinals then every projective set is determined (projective determinacy), and determinacy implies the perfect set property, Lebesgue measurability and the Baire property for all projective sets.

So the regularity of definable sets of reals, which ZFC establishes at the first level, is settled at all projective levels by large cardinal axioms — one of the strongest arguments for adopting them (see large cardinals).

Formal mathematicsF

Polish spaces and analytic sets in Lean

Mathlib has substantial descriptive set theory. Baire space is Polish, and closed sets in a metric space are $G_\delta$ :

baire_space_polishLean 4Applies a library theoremFormally verified

/-- **Baire space** `𝒩 = ℕ^ℕ`, with the product of discrete topologies, is Polish (separable
and completely metrisable): a countable product of Polish spaces is Polish. Mathlib provides the
instance. -/
theorem baire_space_polish : PolishSpace (ℕ → ℕ) :=
  inferInstance