PMATH 930: Descriptive Set Theory

Andy Zucker

Estimated study time: 1 hr 1 min

Table of contents

Sources and References

Alexander S. Kechris, Classical Descriptive Set Theory, Springer Graduate Texts in Mathematics 156, 1995. (Primary reference throughout.)
Su Gao, Invariant Descriptive Set Theory, CRC Press Monographs and Surveys in Pure and Applied Mathematics 139, 2009.
Yiannis N. Moschovakis, Descriptive Set Theory, second edition, AMS Mathematical Surveys and Monographs 155, 2009.
David Marker, Lecture Notes on Descriptive Set Theory, University of Illinois at Chicago (publicly available).
Slawomir Solecki, Descriptive Set Theory and Polish Group Actions (lecture notes).
Jacques Stern, Effective Descriptive Set Theory (supplementary perspective on analytic sets and trees).

Chapter 1: Polish Spaces

1.1 Complete Separable Metrizable Spaces

Descriptive set theory begins with a deceptively simple topological category. A topological space \( X \) is called a Polish space if it admits a compatible metric \( d \) such that \( (X, d) \) is complete and separable — that is, every Cauchy sequence converges and there is a countable dense subset. The definition is purely topological: what matters is the existence of such a metric, not any particular choice of it. Two homeomorphic spaces are either both Polish or neither.

The canonical examples permeate all of mathematics. The real line \( \mathbb{R} \) with its standard metric is Polish. So is any closed interval \( [0,1] \), any separable Banach space (with its norm metric), the Hilbert space \( \ell^2(\mathbb{N}) \), the Cantor space \( 2^\omega \), and the Baire space \( \omega^\omega \). Countable products of Polish spaces are Polish: if each \( (X_n, d_n) \) is Polish, one places

\[ d\bigl((x_n),(y_n)\bigr) = \sum_{n=0}^\infty 2^{-n} \frac{d_n(x_n,y_n)}{1 + d_n(x_n,y_n)}, \]

obtaining a compatible complete metric on \( \prod_n X_n \). In particular, the countable power \( \mathbb{R}^\omega \) is Polish, and the Hilbert cube \( [0,1]^\omega \) is compact Polish.

The Baire space \( \mathcal{N} = \omega^\omega \) — infinite sequences of natural numbers with the product of the discrete topology on \( \omega \) — deserves special attention. Its basic open sets are cylinder sets

\[ N_s = \{ x \in \omega^\omega : s \prec x \}, \]

where \( s \in \omega^{<\omega} \) is a finite sequence and \( \prec \) denotes “is an initial segment of.” A compatible complete metric is

\[ d(x,y) = 2^{-\min\{n : x(n) \neq y(n)\}}, \]

with the convention \( d(x,x) = 0 \). The Baire space is zero-dimensional (it has a clopen basis), totally disconnected, and nowhere locally compact. It plays a universal role in the theory: every Polish space is a continuous image of \( \mathcal{N} \).

The Cantor space \( \mathcal{C} = 2^\omega \) is the compact counterpart: infinite binary sequences, again with the product topology. It is the unique (up to homeomorphism) compact, metrizable, perfect, totally disconnected space — this is Brouwer’s theorem. Every compact metrizable space is a continuous image of \( \mathcal{C} \).

A metrizable space \( X \) is zero-dimensional if it has a basis of clopen sets. Equivalently, the topology is generated by a metric that takes only the values \( 0 \) and \( 1 \) on connected components, but more usefully: every open cover has a refinement by pairwise disjoint clopen sets.

1.2 Urysohn Metrization and Topological Characterizations

The classical Urysohn metrization theorem states that every second-countable regular space embeds into \( [0,1]^\omega \), and therefore into a Polish space. For our purposes, the refined statement is what matters:

Theorem (Urysohn Metrization). A topological space is Polish if and only if it is second-countable, regular, and \( T_1 \), and admits a compatible complete metric.

Every Polish space embeds as a subspace of the Hilbert cube \( [0,1]^\omega \), which is the universal compact metrizable space. More precisely, every separable metrizable space embeds in \( [0,1]^\omega \), and the space is Polish if and only if its image in \( [0,1]^\omega \) is a \( G_\delta \) set (a countable intersection of open sets). This is one of the first deep structural results:

Theorem (Alexandrov). A subspace \( Y \) of a Polish space \( X \) is Polish if and only if \( Y \) is a \( G_\delta \) subset of \( X \).

For the direction that matters in practice: suppose \( Y = \bigcap_n U_n \) with each \( U_n \) open in \( X \). Fix a compatible complete metric \( d \) on \( X \) with \( d \leq 1 \). Define a new metric on \( Y \) by \[ d'(y, z) = d(y, z) + \sum_{n=0}^\infty 2^{-n} \left| \frac{1}{d(y, X \setminus U_n)} - \frac{1}{d(z, X \setminus U_n)} \right|, \]

where \( d(y, X \setminus U_n) > 0 \) since \( y \in U_n \). One checks that \( d' \) is compatible with the subspace topology and that \( (Y, d') \) is complete: a Cauchy sequence for \( d' \) is Cauchy for \( d \), hence converges in \( X \), and the additional terms force the limit to lie in every \( U_n \), thus in \( Y \).

For the converse: if \( Y \) is Polish, its image under any homeomorphism into \( [0,1]^\omega \) is \( G_\delta \) by a Baire category argument — a complete metric space is of second category in itself, and the only second-category subsets of a Polish space that are also metrizable by a complete metric are the \( G_\delta \) subsets.

The irrationals \( \mathbb{R} \setminus \mathbb{Q} \) form a \( G_\delta \) subset of \( \mathbb{R} \) (each rational is a closed set, so the irrationals are a countable intersection of open dense sets). By Alexandrov's theorem, the irrationals are Polish. In fact, the irrationals are homeomorphic to the Baire space \( \omega^\omega \) — this is a classical result proved by exhibiting an explicit homeomorphism via continued fractions.

1.3 Closed Sets and Subspaces

Closed subsets of Polish spaces are Polish. This follows immediately from the fact that closed sets are \( G_\delta \): a closed set \( F \subseteq X \) satisfies \( F = \bigcap_n (X \setminus \{x : d(x,F) \geq 1/n\})^c \ldots \) but more directly, \( F \) is itself complete under the restriction of any compatible complete metric on \( X \), since a Cauchy sequence in \( F \) converges in \( X \) and the limit must lie in \( F \) (closed sets are sequentially closed in metric spaces).

The category of Polish spaces and continuous maps is well-behaved in the following sense: countable products, closed subspaces, and \( G_\delta \) subspaces are Polish. However, open subsets of Polish spaces need not be closed, yet they are Polish (since every open set is \( F_\sigma \) in itself... more carefully, open sets are locally closed and their complement is closed, making them \( G_\delta \) in the ambient space). Arbitrary subspaces are not Polish in general: \( \mathbb{Q} \) is not Polish (it is not a \( G_\delta \) in \( \mathbb{R} \) by the Baire category theorem).

Chapter 2: Baire Category

2.1 The Baire Category Theorem

One of the most powerful tools in descriptive set theory — and in analysis generally — is the Baire category theorem. A subset \( A \) of a topological space is nowhere dense if its closure has empty interior, meager (or first category) if it is a countable union of nowhere dense sets, and comeager if its complement is meager.

Theorem (Baire Category Theorem). In a completely metrizable space (or in a locally compact Hausdorff space), every comeager set is dense. Equivalently, the intersection of countably many open dense sets is dense.

Let \( (X, d) \) be completely metrizable and let \( \{ U_n \}_{n \in \omega} \) be open dense sets. We show \( \bigcap_n U_n \) is dense by finding, for any nonempty open \( V \), a point in \( V \cap \bigcap_n U_n \).

Since \( U_0 \) is dense, \( V \cap U_0 \) is nonempty and open. Choose a closed ball \( \overline{B}(x_0, r_0) \subseteq V \cap U_0 \) with \( r_0 < 1 \). Inductively, given \( \overline{B}(x_n, r_n) \), use density of \( U_{n+1} \) to find \( \overline{B}(x_{n+1}, r_{n+1}) \subseteq B(x_n, r_n) \cap U_{n+1} \) with \( r_{n+1} < 2^{-(n+1)} \). The sequence \( (x_n) \) is Cauchy (since \( d(x_m, x_n) < 2^{-m} \) for \( m < n \)), hence converges to some \( x \in X \). By construction, \( x \in \overline{B}(x_n, r_n) \subseteq U_n \) for all \( n \), and \( x \in V \).

The consequence is that no nonempty Polish space is meager in itself. This may be rephrased: Polish spaces are of second category. The Baire category theorem supplies a dichotomy — any subset of a Polish space either is meager (small, in the topological sense) or contains a comeager \( G_\delta \) subset (large).

2.2 The Baire Property

A set \( A \subseteq X \) has the Baire property if there exists an open set \( U \) such that the symmetric difference \( A \triangle U \) is meager. Equivalently, \( A \) is measurable in the \( \sigma \)-algebra generated by the open sets and the meager sets.

Theorem. In a Polish space, every Borel set has the Baire property. More strongly, every analytic set has the Baire property.

The Baire property is preserved under countable unions and intersections, and complements. The collection of sets with the Baire property forms a \( \sigma \)-algebra containing all open sets and all meager sets.

2.3 The Banach-Mazur Game

The Banach-Mazur game provides a gametheoretic characterization of the Baire property, giving insight into why the category-theoretic approach to “largeness” is natural.

Let \( X \) be a topological space and \( A \subseteq X \). The Banach-Mazur game \( \mathbf{G}^{**}(A) \) is played as follows. Players I and II alternately choose nonempty open sets, with II required to choose a subset of I's most recent set: \[ U_0 \supseteq V_0 \supseteq U_1 \supseteq V_1 \supseteq U_2 \supseteq V_2 \supseteq \cdots \]

Player I wins if \( \bigcap_n V_n \cap A \neq \emptyset \); Player II wins if \( \bigcap_n V_n \cap A = \emptyset \), i.e., if \( \bigcap_n V_n \subseteq A^c \).

Theorem (Banach-Oxtoby). In a Polish space \( X \), Player II has a winning strategy in \( \mathbf{G}^{**}(A) \) if and only if \( A \) is meager. Player I has a winning strategy if and only if \( A \) is comeager in some nonempty open set.

This result has striking consequences. It shows that the notion of meagerness is invariant under the “projective” operations that appear throughout descriptive set theory — a set defined by a game where one player can force the outcome into the set must have the Baire property. The Banach-Mazur game is the prototype for the Gale-Stewart and other determinacy games that appear in the deeper parts of the subject.

2.4 Baire Category and Definability

The Baire category theorem has profound consequences for definability in Polish spaces. A classical application: in \( \mathbb{R} \), a function that is measurable with respect to the Borel \( \sigma \)-algebra satisfies Lusin’s theorem (it is continuous on large compact subsets) and must therefore be “tame” in a precise topological sense. The connection to category theory is that Borel functions are exactly those that are continuous on a comeager set.

The set of continuous functions in \( C([0,1]) \) that are differentiable at some point is meager. This was Banach's result: the generic continuous function (in the sense of Baire category) is nowhere differentiable. The proof constructs, for each \( n \), the open dense set \( U_n \) of functions that are "locally \( n \)-Lipschitz somewhere," and shows the complement contains all nowhere-differentiable functions.

Chapter 3: The Borel Hierarchy

3.1 Pointclasses and the Hierarchy

The Borel sets in a topological space are the sets in the smallest \( \sigma \)-algebra containing the open sets. In a Polish space, the Borel sets stratify into a transfinite hierarchy indexed by countable ordinals, and this stratification is proper — at each level, there are genuinely new sets that did not appear at earlier levels.

Fix a Polish space \( X \). The Borel hierarchy is defined by transfinite induction:

\( \boldsymbol{\Sigma}^0_1 \) = the open sets.
\( \boldsymbol{\Pi}^0_1 \) = the closed sets (complements of open sets).
For \( \alpha \geq 2 \): \( \boldsymbol{\Sigma}^0_\alpha \) consists of all countable unions of sets from \( \bigcup_{\beta < \alpha} \boldsymbol{\Pi}^0_\beta \).
\( \boldsymbol{\Pi}^0_\alpha \) consists of the complements of \( \boldsymbol{\Sigma}^0_\alpha \) sets.
\( \boldsymbol{\Delta}^0_\alpha = \boldsymbol{\Sigma}^0_\alpha \cap \boldsymbol{\Pi}^0_\alpha \).

In this notation, \( \boldsymbol{\Sigma}^0_2 \) sets are \( F_\sigma \) (countable unions of closed sets), \( \boldsymbol{\Pi}^0_2 \) sets are \( G_\delta \) (countable intersections of open sets), \( \boldsymbol{\Sigma}^0_3 \) sets are \( G_{\delta\sigma} \), and so on. The Borel \( \sigma \)-algebra equals \( \bigcup_{\alpha < \omega_1} \boldsymbol{\Sigma}^0_\alpha = \bigcup_{\alpha < \omega_1} \boldsymbol{\Pi}^0_\alpha \).

Each class \( \boldsymbol{\Sigma}^0_\alpha \) is closed under countable unions and finite intersections; \( \boldsymbol{\Pi}^0_\alpha \) is closed under countable intersections and finite unions; and \( \boldsymbol{\Delta}^0_\alpha \) is a Boolean algebra. The inclusions

\[ \boldsymbol{\Delta}^0_\alpha \subsetneq \boldsymbol{\Sigma}^0_\alpha \subsetneq \boldsymbol{\Delta}^0_{\alpha+1} \]

are all proper in any uncountable Polish space.

3.2 Universal Sets and the Hierarchy’s Properness

The proof that the hierarchy is proper uses a diagonal argument via universal sets.

A set \( U \subseteq \mathcal{N} \times X \) is universal for \( \boldsymbol{\Sigma}^0_\alpha(X) \) if \( U \in \boldsymbol{\Sigma}^0_\alpha(\mathcal{N} \times X) \) and every \( \boldsymbol{\Sigma}^0_\alpha \) subset of \( X \) is of the form \( U_y = \{ x : (y, x) \in U \} \) for some \( y \in \mathcal{N} \).

Theorem. For every countable ordinal \( \alpha \geq 1 \) and every uncountable Polish space \( X \), there exist sets universal for \( \boldsymbol{\Sigma}^0_\alpha(X) \) and \( \boldsymbol{\Pi}^0_\alpha(X) \). In particular, \( \boldsymbol{\Sigma}^0_\alpha(X) \neq \boldsymbol{\Pi}^0_\alpha(X) \) and \( \boldsymbol{\Sigma}^0_\alpha(X) \subsetneq \boldsymbol{\Sigma}^0_{\alpha+1}(X) \).

The diagonalization argument is the same as for any universal set: if \( U \) is universal for \( \boldsymbol{\Sigma}^0_\alpha(X) \) in \( \mathcal{N} \times \mathcal{N} \), then \( D = \{ x \in \mathcal{N} : (x,x) \notin U \} \) is \( \boldsymbol{\Pi}^0_\alpha \) but not \( \boldsymbol{\Sigma}^0_\alpha \).

3.3 Borel Measurable Functions

A function \( f : X \to Y \) between Polish spaces is Borel measurable (or simply Borel) if \( f^{-1}(U) \) is Borel in \( X \) for every open \( U \subseteq Y \). The Borel functions form a natural category: they are closed under composition, and the Borel sets are exactly those whose characteristic functions are Borel.

A function \( f : X \to Y \) is Borel of class \( \alpha \) if \( f^{-1}(U) \in \boldsymbol{\Sigma}^0_{\alpha+1}(X) \) for every open \( U \subseteq Y \). Class 0 functions are the continuous ones.

A fundamental result is that Borel functions can be approximated by piecewise continuous functions on \( G_\delta \) pieces, and every Borel function on a Polish space is measurable with respect to any Borel probability measure.

3.4 The Wadge Order

The Wadge order provides a finer analysis of the Borel hierarchy. For subsets \( A \subseteq X \) and \( B \subseteq Y \), we write \( A \leq_W B \) (A is Wadge reducible to B) if there exists a continuous function \( f : X \to Y \) with \( A = f^{-1}(B) \). The relation \( \leq_W \) is a quasi-order, and the resulting partial order (modulo Wadge equivalence) is the Wadge hierarchy. In the Baire space, the Wadge hierarchy is a well-quasi-order on Borel sets (under determinacy axioms), and the Borel pointclasses \( \boldsymbol{\Sigma}^0_\alpha, \boldsymbol{\Pi}^0_\alpha \) appear as natural levels.

Chapter 4: Standard Borel Spaces

4.1 Borel Isomorphisms

Two Polish spaces may be topologically very different — one compact, one not; one connected, one totally disconnected — yet from the Borel point of view, all uncountable Polish spaces look the same. This is the content of the Borel isomorphism theorem, one of the most elegant results in the subject.

A standard Borel space is a measurable space \( (X, \mathcal{B}) \) where \( \mathcal{B} \) is the Borel \( \sigma \)-algebra of some Polish topology on \( X \). A Borel isomorphism between standard Borel spaces is a bijection that is Borel measurable in both directions.

Theorem (Borel Isomorphism Theorem). Any two uncountable standard Borel spaces are Borel isomorphic. In particular, every uncountable Polish space is Borel isomorphic to \( \mathbb{R} \).

The proof proceeds in stages. First, one shows that the Cantor space \( 2^\omega \) is Borel isomorphic to \( [0,1] \) (via the binary expansion map, which is a Borel isomorphism off a countable set). Then one shows that any uncountable Polish space contains a Borel isomorphic copy of \( 2^\omega \) as a Borel subset, and uses the Schröder-Bernstein argument at the Borel level.

The key tool is the Cantor-Bendixson theorem: every closed subset of a Polish space is a disjoint union of a perfect set and a countable set. A perfect Polish space (closed, no isolated points) is uncountable and contains a continuous embedding of the Cantor space. Therefore:

Corollary. Every uncountable Borel subset of a Polish space has cardinality \( 2^{\aleph_0} \). (The Borel perfect set property.)

4.2 Borel Injections and the Lusin-Souslin Theorem

A bijective Borel map between standard Borel spaces is a Borel isomorphism — the inverse is automatically Borel. This is the standard Borel space version of the open mapping theorem.

Theorem (Lusin-Souslin). Let \( X, Y \) be standard Borel spaces and \( f : X \to Y \) a Borel injection (one-to-one Borel function). Then \( f(X) \) is Borel in \( Y \) and \( f^{-1} : f(X) \to X \) is also Borel.

The key insight is that injective Borel images of Borel sets are Borel — this fails for mere measurable functions but holds for Borel functions into standard Borel spaces. The proof uses analytic sets: \( f(X) \) is analytic (a continuous image of a Polish space, since \( f \) restricted to a Borel subset is Borel, hence a fortiori analytic), and by the Luzin separation theorem, an analytic set that is also coanalytic is Borel. Since \( X \setminus f^{-1}(A) = f^{-1}(f(X) \setminus A) \) for Borel \( A \), the injectivity of \( f \) propagates the Borel property.

If \( E \) is a Borel equivalence relation on a Polish space \( X \) with countably many classes, the space of equivalence classes \( X/E \) is a standard Borel space, and the quotient map is a Borel injection on any Borel selector. This observation underpins the theory of Borel equivalence relations.

4.3 The Lusin-Novikov Uniformization Theorem

Uniformization asks: given a Borel set \( B \subseteq X \times Y \), can we find a Borel function \( f : \text{proj}_X(B) \to Y \) with \( (x, f(x)) \in B \) for all \( x \in \text{proj}_X(B) \)? In general, the answer is no — the projection of a Borel set need not be Borel, and no Borel selector need exist. However, under a countability condition, uniformization always works.

Theorem (Lusin-Novikov). Let \( X, Y \) be Polish spaces and \( B \subseteq X \times Y \) a Borel set such that every section \( B_x = \{y : (x,y) \in B\} \) is countable. Then \( \text{proj}_X(B) \) is Borel, and \( B = \bigcup_n \text{graph}(f_n) \) where each \( f_n : D_n \to Y \) is a Borel function with Borel domain \( D_n \subseteq \text{proj}_X(B) \).

In other words, any Borel set with countable sections can be covered by countably many Borel graphs. This theorem is the foundation for the Feldman-Moore theorem on countable Borel equivalence relations (Chapter 8).

Consider the equivalence relation on \( 2^\omega \) where \( x \sim y \) iff \( x \) and \( y \) differ in only finitely many coordinates. The graph of \( \sim \) (as a subset of \( 2^\omega \times 2^\omega \)) is Borel, and every equivalence class is countable (since each class consists of all sequences obtained by finitely many bit-flips). By Lusin-Novikov, the equivalence relation is the union of countably many Borel graphs, meaning it arises from a Borel action of a countable group.

Chapter 5: Analytic Sets

5.1 Definition and Basic Properties

The Borel hierarchy stops at level \( \omega_1 \), but the natural operations of descriptive set theory — continuous images, projections — can produce sets beyond the Borel hierarchy. The simplest level beyond Borel is the analytic sets, also called the \( \boldsymbol{\Sigma}^1_1 \) sets.

A subset \( A \) of a Polish space \( X \) is analytic (or \( \boldsymbol{\Sigma}^1_1 \)) if it is the continuous image of a Polish space. Equivalently, \( A \) is the projection of a closed subset of \( X \times \mathcal{N} \) onto \( X \). A set is coanalytic (or \( \boldsymbol{\Pi}^1_1 \)) if its complement is analytic.

Every Borel set is analytic (since Borel sets are Polish subspaces). Analytic sets are closed under countable unions, countable intersections, continuous images, and continuous preimages. They are not in general closed under complementation.

The equivalence between the two definitions is instructive: if \( f : \mathcal{N} \to X \) is continuous and surjective onto \( A \), then \( A = \text{proj}_X(\text{graph}(f)) \), and the graph is closed in \( \mathcal{N} \times X \) since \( f \) is continuous. Conversely, any projection of a closed subset \( F \subseteq \mathcal{N} \times X \) is a continuous image of \( F \) (which is Polish), namely via the projection map.

5.2 The Suslin Operation

The Suslin operation \( \mathcal{A} \) provides a combinatorial description of analytic sets.

Given a family of sets \( \{ A_s \}_{s \in \omega^{<\omega}} \) indexed by finite sequences, the Suslin scheme produces the set \[ \mathcal{A}(A_s) = \bigcup_{x \in \omega^\omega} \bigcap_{n \in \omega} A_{x \upharpoonright n}, \]

where \( x \upharpoonright n = (x(0), x(1), \ldots, x(n-1)) \).

Theorem. A subset of a Polish space is analytic if and only if it is the result of applying the Suslin operation to a family of closed sets. The Suslin operation applied to a family of Borel sets produces an analytic set, and every analytic set arises this way.

The Suslin operation generates more than just the Borel sets: one of the early results of classical descriptive set theory (due to Suslin, 1917) is that there exist analytic sets that are not Borel. The example is the set of codes of well-orderings of \( \omega \), which is \( \boldsymbol{\Pi}^1_1 \) but not Borel.

5.3 The Lusin Separation Theorem

The most important structural theorem about analytic sets is Lusin’s separation theorem, which explains why analytic sets are “almost Borel” in a precise sense.

Theorem (Lusin Separation). If \( A \) and \( B \) are disjoint analytic subsets of a Polish space \( X \), then there exists a Borel set \( C \) with \( A \subseteq C \) and \( C \cap B = \emptyset \). In other words, disjoint analytic sets can be separated by a Borel set.

The proof uses the tree representations of analytic sets. Represent \( A = p[\mathcal{T}] \) and \( B = p[\mathcal{S}] \), where \( \mathcal{T} \) and \( \mathcal{S} \) are trees on \( \omega \times \omega \) and \( p \) denotes projection. Since \( A \cap B = \emptyset \), the product tree \( \mathcal{T} \times \mathcal{S} \) is well-founded (no infinite branch exists through both trees simultaneously). One then defines a Borel rank function on the product tree and uses it to construct the separating Borel set.

Corollary. A subset \( A \) of a Polish space is Borel if and only if both \( A \) and \( X \setminus A \) are analytic (i.e., \( A \in \boldsymbol{\Delta}^1_1 \)).

This is the analytic-coanalytic dichotomy: \( \boldsymbol{\Delta}^1_1 \) sets are exactly the Borel sets. It follows that there exist analytic sets that are not Borel — namely, any \( \boldsymbol{\Sigma}^1_1 \setminus \boldsymbol{\Pi}^1_1 \) set.

5.4 Regularity Properties of Analytic Sets

Analytic sets enjoy all the classical regularity properties that Borel sets have, and the proofs go through uniformly.

Theorem. In a Polish space, every analytic set:

Has the Baire property.
Is Lebesgue measurable (with respect to any \( \sigma \)-finite Borel measure).
Has the perfect set property: it is either countable or contains a homeomorphic copy of the Cantor space.

The perfect set property for analytic sets is due to Souslin (1917) and is proved using the Cantor-Bendixson analysis of the tree associated to an analytic set. The Baire property follows from the Banach-Mazur game characterization. Measurability follows from the abstract approach to analytic sets via the Suslin operation on measurable sets.

Chapter 6: Trees and Ranks

6.1 Trees on \( \omega \)

A tree on a set \( A \) is a set \( T \subseteq A^{<\omega} \) of finite sequences closed under initial segments: if \( s \in T \) and \( t \prec s \), then \( t \in T \). The elements of \( T \) are the nodes, and a node \( s \in T \) is a leaf if no proper extension of \( s \) is in \( T \). An infinite branch (or path) through \( T \) is an infinite sequence \( x \in A^\omega \) such that every initial segment \( x \upharpoonright n \in T \).

A tree \( T \) is well-founded if it has no infinite branches. Otherwise, the set of infinite branches \( [T] = \{ x \in A^\omega : \forall n, x \upharpoonright n \in T \} \) is nonempty.

By König’s lemma, a finitely-branching tree on \( \omega \) is well-founded if and only if it is finite. But for infinitely-branching trees (the relevant case in descriptive set theory), a tree can be infinite yet well-founded.

The connection to topology is through the basic open sets of \( \omega^\omega \): the body \( [T] \) is a closed subset of \( \omega^\omega \), and every closed subset of \( \omega^\omega \) is the body of a unique pruned tree (a tree where every node has at least one extension).

6.2 The Kleene-Brouwer Ordering

The Kleene-Brouwer ordering on a tree \( T \) is a linear order defined by: \( s <_{KB} t \) if either \( t \prec s \) (t is a proper initial segment of s), or there exists a least \( k \) where \( s \) and \( t \) differ and \( s(k) < t(k) \).

Theorem. A tree \( T \) on \( \omega \) is well-founded if and only if the Kleene-Brouwer ordering \( <_{KB} \) is a well-order on \( T \).

This is the key theorem connecting tree well-foundedness to ordinals. The rank of \( T \) in the Kleene-Brouwer ordering (its order type) gives the rank of the well-founded tree, which is a countable ordinal.

6.3 Ranks on Well-Founded Trees

For a well-founded tree \( T \), the Cantor-Bendixson rank (or simply the rank) of a node \( s \in T \) is defined by transfinite induction:

\[ \rho_T(s) = \sup \{ \rho_T(t) + 1 : t \in T, s \prec t \text{ and } |t| = |s| + 1 \}, \]

where the supremum of the empty set is \( 0 \) (for leaves). The rank of the tree is \( \rho(T) = \rho_T(\emptyset) + 1 \).

Theorem. The function \( T \mapsto \rho(T) \) from well-founded trees on \( \omega \) to countable ordinals is surjective. The set of well-founded trees on \( \omega \), as a subset of \( 2^{\omega^{<\omega}} \), is \( \boldsymbol{\Pi}^1_1 \) but not Borel. For each countable ordinal \( \alpha \), the set \( \{ T : \rho(T) < \alpha \} \) is Borel.

6.4 Tree Representations of Analytic and Coanalytic Sets

The deep connection between trees and analytic/coanalytic sets is given by the following:

Theorem. A set \( A \subseteq \mathcal{N} \) is analytic if and only if there exists a tree \( T \) on \( \omega \times \omega \) such that \[ A = p[T] = \{ x \in \omega^\omega : \exists y \in \omega^\omega, \forall n, (x \upharpoonright n, y \upharpoonright n) \in T \}. \]

A set \( A \) is coanalytic if and only if \( A = \{ x : T_x \text{ is well-founded} \} \) for some uniformly definable family of trees \( T_x \) on \( \omega \).

The tree representation of coanalytic sets as sets of “codes of well-founded trees” explains why coanalytic sets are intimately related to ordinal analysis. The rank function on trees gives a Borel rank to elements of a coanalytic set, leading to the following fundamental result:

Theorem (Boundedness Lemma). If \( A \subseteq \mathcal{N} \) is analytic and \( A \subseteq \{ x : T_x \text{ is well-founded} \} \), then the ranks \( \{ \rho(T_x) : x \in A \} \) are bounded below \( \omega_1 \). In particular, a coanalytic set is Borel if and only if the corresponding ranks are bounded.

6.5 The Cantor-Bendixson Theorem Revisited

The Cantor-Bendixson theorem can be proved using tree ranks. For a closed set \( F \) in a Polish space, define the Cantor-Bendixson derivative \( F' \) as the set of accumulation points of \( F \). Iterate transfinitely: \( F^{(0)} = F \), \( F^{(\alpha+1)} = (F^{(\alpha)})' \), \( F^{(\lambda)} = \bigcap_{\alpha < \lambda} F^{(\alpha)} \) for limit \( \lambda \). There exists a countable ordinal \( \xi \) (the Cantor-Bendixson rank of \( F \)) such that \( F^{(\xi)} = F^{(\xi+1)} \), and \( F^{(\xi)} \) is perfect (possibly empty). The set \( F \setminus F^{(\xi)} \) is countable.

Theorem (Cantor-Bendixson). Every closed subset \( F \) of a Polish space is the disjoint union \( F = P \cup C \), where \( P \) is perfect and \( C \) is countable. In particular, every uncountable closed set contains a perfect subset and hence has cardinality \( 2^{\aleph_0} \).

Chapter 7: Polish Groups and Continuous Actions

7.1 Polish Groups

A Polish group is a topological group whose underlying topology is Polish — that is, it is a group equipped with a topology under which the group operations are continuous, and the topology is separable and completely metrizable. Unlike Polish spaces, a Polish group need not admit a compatible bi-invariant complete metric, though every Polish group is metrizable and admits a compatible left-invariant (and separately a right-invariant) complete metric.

The infinite symmetric group. Let \( S_\infty \) denote the group of all permutations of \( \omega \), with the topology inherited from \( \omega^\omega \): a basic open neighborhood of \( \sigma \) specifies the values of \( \sigma \) on finitely many elements. This is a Polish group under composition. It is not locally compact.

The group of homeomorphisms of \( 2^\omega \). With the compact-open topology, \( \text{Homeo}(2^\omega) \) is a Polish group.

Separable Banach spaces. Any separable Banach space is a Polish group under addition.

The unitary group. The unitary group \( U(\ell^2) \) with the strong operator topology is a Polish group.

Automorphism groups of countable structures. If \( \mathcal{M} \) is a countable first-order structure, \( \text{Aut}(\mathcal{M}) \) with the pointwise convergence topology is a closed subgroup of \( S_\infty \) and therefore a Polish group.

Theorem (Birkhoff-Kakutani). Every Polish group admits a compatible left-invariant metric. (It need not admit a bi-invariant complete metric.)

7.2 Continuous Actions and Orbit Equivalence Relations

Let \( G \) be a Polish group acting continuously on a Polish space \( X \) — that is, the action map \( G \times X \to X \) is jointly continuous. The orbit equivalence relation \( E_G^X \) is defined by

\[ x \mathrel{E_G^X} y \iff \exists g \in G, g \cdot x = y. \]

The orbits \( G \cdot x = \{ g \cdot x : g \in G \} \) partition \( X \).

A fundamental question is: how “complicated” are the orbits as subsets of \( X \)? One might hope that orbits are always Borel, but this is not immediately clear since orbits are images of the map \( g \mapsto g \cdot x \), which is continuous, from a Polish space. Thus orbits are analytic sets. The surprise is that they are in fact Borel:

Theorem (Effros). Let \( G \) be a Polish group acting continuously on a Polish space \( X \). Then every \( G \)-orbit is either open or meager in its closure. More precisely, the orbit \( G \cdot x \) is a \( G_\delta \) (hence Borel) subset of its closure if and only if the map \( g \mapsto g \cdot x \) is a quotient map \( G \to G \cdot x \).

In the locally compact case, orbits are always Borel (by the Effros theorem and the fact that locally compact Polish groups act as open maps). For general Polish groups, the Effros theorem provides the key dichotomy: each orbit is either a Borel set (specifically \( G_\delta \) in its closure) or a meager \( F_\sigma \) set.

7.3 Vaught Transforms

The Vaught transform is a key technical tool for analyzing orbit equivalence relations, particularly in the context of model theory and continuous logic. For a group action of \( G \) on \( X \) and a set \( A \subseteq X \), define:

\[ A^{*g} = \{ x \in X : \{ h \in G : h \cdot x \in A \} \text{ is comeager in } G \} \]\[ A^{\triangle g} = \{ x \in X : \{ h \in G : h \cdot x \in A \} \text{ is nonmeager in } G \} \]

These are the Vaught transforms of \( A \) with respect to the action. If \( A \) is Borel (resp. analytic), then so are \( A^{*g} \) and \( A^{\triangle g} \). The Vaught transform satisfies:

\( A^{*g} \subseteq A^{\triangle g} \),
Both sets are \( G \)-invariant (saturated by orbits),
\( A^{*g} = (A^{*g})^{*g} \), and
If \( A \) is open, then \( A^{\triangle g} = A^{*g} = \bigcup_{g \in G} g \cdot A \) (if the action is by homeomorphisms).

In the action of \( S_\infty \) on the set of linear orders on \( \omega \), the orbits are isomorphism types of countable linear orders. The Vaught transform can be used to show that certain isomorphism classes are Borel, while others are not.

7.4 Topological Dynamics and the Generic Point

A continuous action of \( G \) on \( X \) is topologically transitive if there exists a dense orbit (a generic point). By the Baire category theorem, if the action is transitive and \( G \) is a Polish group acting on a Polish space, then the set of generic points is comeager.

Chapter 8: Borel Equivalence Relations

8.1 Countable Borel Equivalence Relations

An equivalence relation \( E \) on a Polish space \( X \) is a Borel equivalence relation if it is a Borel subset of \( X \times X \). The study of Borel equivalence relations has emerged as a central organizing framework in modern descriptive set theory, connecting it to ergodic theory, topological dynamics, and model theory.

A Borel equivalence relation \( E \) on a Polish space \( X \) is countable if every equivalence class \( [x]_E \) is countable. It is finite if all classes are finite, and smooth if there exists a Borel function \( f : X \to Y \) (into a Polish space \( Y \)) with \( x \mathrel{E} y \iff f(x) = f(y) \).

Examples of countable Borel equivalence relations abound:

Tail equivalence on \( 2^\omega \): \( x \sim y \) iff \( x(n) = y(n) \) for all sufficiently large \( n \).
The orbit equivalence relation of any Borel action of a countable group \( \Gamma \) on a Polish space.
Turing equivalence on Cantor space (in the context of computability).

8.2 The Feldman-Moore Theorem

The Feldman-Moore theorem is the cornerstone of the structural theory of countable Borel equivalence relations. It asserts that every countable Borel equivalence relation arises from a group action.

Theorem (Feldman-Moore, 1977). Let \( E \) be a countable Borel equivalence relation on a Polish space \( X \). Then there exists a countable group \( \Gamma \) and a Borel action of \( \Gamma \) on \( X \) such that \( E = E_\Gamma^X \) (the orbit equivalence relation of the action).

By the Lusin-Novikov theorem (Theorem 4.3), since \( E \subseteq X \times X \) is Borel and all sections \( E_x = [x]_E \) are countable, we can write \[ E = \bigcup_{n \in \omega} \text{graph}(f_n), \]

where each \( f_n : D_n \to X \) is a Borel partial injection with Borel domain \( D_n \subseteq X \). By modifying the \( f_n \) (extending them to all of \( X \) as Borel involutions using the standard trick), we may assume each \( f_n : X \to X \) is a Borel bijection (automorphism of the space as a Borel space). The group \( \Gamma \) is then the group generated by \( \{ f_n \}_{n \in \omega} \) inside the group of Borel automorphisms of \( X \). One verifies: \( x \mathrel{E} y \) iff some finite composition of the \( f_n^{\pm 1} \) takes \( x \) to \( y \), i.e., iff \( x \) and \( y \) lie in the same \( \Gamma \)-orbit.

The Feldman-Moore theorem reduces the study of countable Borel equivalence relations to the study of orbit equivalence relations of countable group actions. This connects descriptive set theory with ergodic theory (where one studies measure-preserving actions) and topological dynamics.

8.3 Borel Reducibility

The correct notion of “comparison” between Borel equivalence relations is Borel reducibility:

Let \( E \) and \( F \) be Borel equivalence relations on Polish spaces \( X \) and \( Y \) respectively. We say \( E \) is Borel reducible to \( F \), written \( E \leq_B F \), if there exists a Borel function \( f : X \to Y \) such that \[ x \mathrel{E} x' \iff f(x) \mathrel{F} f(x') \]

for all \( x, x' \in X \). We say \( E \) and \( F \) are Borel bi-reducible (\( E \sim_B F \)) if \( E \leq_B F \) and \( F \leq_B E \).

The relation \( \leq_B \) formalizes “classification by \( F \)-invariants”: \( E \leq_B F \) means the \( E \)-classification problem can be solved using \( F \)-invariants. The study of the \( \leq_B \) order has revealed a rich hierarchy of complexity.

The simplest equivalence relations are the smooth ones, i.e., those reducible to equality on a Polish space \( (=_X) \). A Borel equivalence relation is smooth iff there exist Borel complete invariants.
The relation \( E_0 \) on \( 2^\omega \) (eventual equality) is the simplest non-smooth countable equivalence relation.
There exist countable Borel equivalence relations that are universal: every countable Borel equivalence relation Borel reduces to them. Examples include the orbit equivalence relation of the free part of the shift action of \( \mathbb{F}_2 \) (the free group on two generators) on \( 2^{\mathbb{F}_2} \).

8.4 The Dichotomy for Countable Borel Equivalence Relations

A classical dichotomy result:

Theorem (Harrington-Kechris-Louveau, 1990). Let \( E \) be a Borel equivalence relation on a Polish space. Then either \( E \) is smooth, or \( E_0 \leq_B E \). That is, \( E_0 \) is the simplest non-smooth Borel equivalence relation.

Here \( E_0 \) denotes eventual equality on \( 2^\omega \):

\[ x \mathrel{E_0} y \iff \exists N \forall n \geq N, x(n) = y(n). \]

The proof of the Harrington-Kechris-Louveau theorem uses Baire category methods (specifically, a game-theoretic argument) and is a model of how Baire category ideas interact with the structure of equivalence relations.

8.5 Hyperfinite Equivalence Relations

An equivalence relation is hyperfinite if it is the increasing union of finite Borel equivalence relations:

\[ E = \bigcup_{n=0}^\infty E_n, \quad E_0 \subseteq E_1 \subseteq \cdots, \quad \text{each } E_n \text{ finite Borel.} \]

Theorem (Weiss, Dye's Theorem in the Borel setting). \( E_0 \) is the unique (up to Borel bi-reducibility) hyperfinite non-smooth Borel equivalence relation. Every hyperfinite Borel equivalence relation is Borel reducible to \( E_0 \).

Theorem (Connes-Feldman-Weiss). For a countable group \( \Gamma \) acting in a measure-preserving way on a standard probability space, the orbit equivalence relation is hyperfinite (as a measure-class equivalence relation) if and only if \( \Gamma \) is amenable.

In the purely Borel setting (without measure), the characterization of hyperfinite equivalence relations is more delicate and is an active area of research.

Chapter 9: Standard Lebesgue Spaces

9.1 Lebesgue Measure and Standard Measure Spaces

A standard Lebesgue space (or standard probability space, or Lebesgue-Rohlin space) is a measure space \( (X, \mathcal{B}, \mu) \) that is isomorphic (as a measure space) to one of the following:

The unit interval \( [0,1] \) with Lebesgue measure, or
At most countably many atoms (point masses).

These are the only measure spaces that arise naturally from Polish spaces with Borel probability measures: any nonatomic Borel probability measure on an uncountable Polish space gives a standard Lebesgue space isomorphic to \( ([0,1], \lambda) \).

Theorem (Rohlin). Any standard Borel space with a nonatomic Borel probability measure is isomorphic as a measure space to \( ([0,1], \mathcal{B}([0,1]), \lambda) \).

This is the measure-theoretic analogue of the Borel isomorphism theorem. It says that, up to isomorphism, there is essentially one standard nonatomic probability space, just as there is essentially one uncountable standard Borel space.

9.2 Completion and the Null Ideal

In the context of standard Lebesgue spaces, the Borel \( \sigma \)-algebra is often completed with respect to the measure: the Lebesgue \( \sigma \)-algebra on \( [0,1] \) is the completion of the Borel \( \sigma \)-algebra, adding all subsets of null sets. The relationship between the Borel and Lebesgue \( \sigma \)-algebras reflects the relationship between topological (Baire category) and measure-theoretic notions of “smallness”:

A set is meager (topologically small) if it is a countable union of nowhere dense sets.
A set is null (measure-theoretically small) if its measure is zero.

Neither notion implies the other, and there exist sets that are meager but of full measure, and sets that are null but comeager.

Theorem (Regularity of Borel measures). Every Borel probability measure on a Polish space is inner regular (approximated by compact sets from inside) and outer regular (approximated by open sets from outside). In particular, analytic sets are measurable for any Borel probability measure.

Chapter 10: Further Topics and Connections

10.1 The Projective Hierarchy Beyond \( \boldsymbol{\Sigma}^1_1 \)

The analytic sets \( \boldsymbol{\Sigma}^1_1 \) and coanalytic sets \( \boldsymbol{\Pi}^1_1 \) are the first level of the projective hierarchy. The next levels are defined by alternating quantifiers over Polish spaces:

\( \boldsymbol{\Sigma}^1_2 \) (PCA): continuous images of coanalytic sets.
\( \boldsymbol{\Pi}^1_2 \) (CPCA): complements of \( \boldsymbol{\Sigma}^1_2 \) sets.
In general, \( \boldsymbol{\Sigma}^1_{n+1} \) is the class of continuous images of \( \boldsymbol{\Pi}^1_n \) sets.

Many questions about the regularity of projective sets (Lebesgue measurability, Baire property, perfect set property) are independent of ZFC for levels \( \geq 2 \). For instance, in Gödel’s constructible universe \( L \), there exists a \( \boldsymbol{\Delta}^1_2 \) set that is not Lebesgue measurable; under suitable large cardinal axioms, all projective sets are measurable.

10.2 Effective Descriptive Set Theory

The effective or lightface version of descriptive set theory replaces the boldface pointclasses \( \boldsymbol{\Sigma}^0_\alpha, \boldsymbol{\Pi}^0_\alpha \) with their effective (recursion-theoretic) counterparts \( \Sigma^0_n, \Pi^0_n \) (for \( n < \omega \)) and \( \Sigma^1_n, \Pi^1_n \). In the effective theory, one restricts to “definable” or “computable” witnesses, and the classical separation and uniformization theorems often have effective refinements.

The effective and classical theories are connected by the Kleene basis theorem, the Gandy-Harrington topology, and the theory of hyperdegrees. The effective theory provides metamathematical content to the classical results and is essential for understanding consistency results.

10.3 Equivalence Relations from Logic

Some of the most important examples of Borel equivalence relations arise from logic and model theory. For a first-order language \( \mathcal{L} \), the space of countable \( \mathcal{L} \)-structures with universe \( \omega \) is a Polish space (with the topology of pointwise convergence on the relations/functions). The isomorphism relation \( \cong_{\mathcal{L}} \) is an analytic equivalence relation, and it is Borel for many specific languages.

Theorem (Lopez-Escobar, Vaught). The isomorphism relation for countable graphs is a universal analytic equivalence relation — every analytic equivalence relation is Borel reducible to graph isomorphism.

This connects descriptive set theory to the classification problem in model theory: when can a class of structures be classified by a “simple” set of invariants?

10.4 Continuous Model Theory and Polish Metric Structures

Modern work connects descriptive set theory to continuous logic and Polish metric structures. A Polish metric structure is a complete separable metric space equipped with uniformly continuous functions and predicates. The logic of Polish metric structures (Ben Yaacov-Berenstein-Henson-Usvyatsov continuous logic) provides a natural framework where the analogs of Borel and analytic sets appear in the definability hierarchy of continuous formulas.

The orbit equivalence relations of automorphism groups of Fraïssé limits (like the random graph, the rational Urysohn space, the countable atomless Boolean algebra) are among the most-studied objects in the theory, and their position in the \( \leq_B \) hierarchy reflects deep combinatorial and model-theoretic properties of the structures.

10.5 The Glimm-Effros Dichotomy and Applications

The Glimm-Effros dichotomy — the Harrington-Kechris-Louveau theorem stated above — has important applications in operator algebras. In the original work of Glimm (1961) and Effros (1965) for locally compact group actions, the dichotomy was: either the orbit space is a “nice” Borel space (the action is type I, or “tame”) or the orbit space contains an isomorphic copy of the orbit space of \( E_0 \). The work of Harrington, Kechris, and Louveau established the purely Borel version, which applies to all Borel equivalence relations without any group action assumption.

Applications include:

Operator algebras: characterizing when a \( C^* \)-algebra has a “smooth” dual.
Topological dynamics: when does a minimal flow admit Borel complete invariants?
Ergodic theory: distinguishing orbit equivalence classes of group actions by Borel invariants.

Appendix: Key Theorems at a Glance

The following list summarizes the main theorems of the course for reference.

Alexandrov's Theorem. A subspace of a Polish space is Polish iff it is \( G_\delta \).

Baire Category Theorem. In a completely metrizable space, the intersection of countably many open dense sets is dense.

Cantor-Bendixson Theorem. Every closed subset of a Polish space is the union of a perfect set and a countable set.

Borel Isomorphism Theorem. Any two uncountable Polish spaces are Borel isomorphic.

Lusin-Souslin Theorem. The injective Borel image of a Borel set in a standard Borel space is Borel.

Lusin-Novikov Theorem. A Borel set with countable sections is a countable union of Borel graphs.

Lusin Separation Theorem. Disjoint analytic sets can be separated by a Borel set. Consequently, \( \boldsymbol{\Delta}^1_1 \) = Borel.

Perfect Set Property for Analytic Sets. Every uncountable analytic set contains a homeomorphic copy of the Cantor space.

Effros Theorem. Every orbit of a Polish group action on a Polish space is a Borel set (specifically, \( G_\delta \) in its closure).

Feldman-Moore Theorem. Every countable Borel equivalence relation is the orbit equivalence relation of a Borel action of a countable group.

Harrington-Kechris-Louveau Dichotomy. Every Borel equivalence relation is either smooth or admits \( E_0 \) as a Borel subequivalence relation.

Rohlin's Theorem. Any standard nonatomic probability space is isomorphic to \( ([0,1], \lambda) \).

Notation Index

Symbol	Meaning
\( \mathcal{N} = \omega^\omega \)	Baire space
\( \mathcal{C} = 2^\omega \)	Cantor space
\( \boldsymbol{\Sigma}^0_\alpha, \boldsymbol{\Pi}^0_\alpha, \boldsymbol{\Delta}^0_\alpha \)	Borel pointclasses at level \( \alpha \)
\( \boldsymbol{\Sigma}^1_1, \boldsymbol{\Pi}^1_1, \boldsymbol{\Delta}^1_1 \)	Analytic, coanalytic, Borel
\( [T] \)	Body (set of infinite branches) of tree \( T \)
\( p[T] \)	Projection of tree \( T \) on \( \omega \times \omega \)
\( \rho(T) \)	Rank of well-founded tree \( T \)
\( E_0 \)	Eventual equality on \( 2^\omega \)
\( E \leq_B F \)	\( E \) is Borel reducible to \( F \)
\( E_\Gamma^X \)	Orbit equivalence relation of \( \Gamma \) acting on \( X \)
\( A^{*g}, A^{\triangle g} \)	Vaught transforms of \( A \)
\( \mathcal{A}(A_s) \)	Suslin operation on Suslin scheme \( \{A_s\} \)