Suslin's Theorem and the Separation Theorem

The Lusin separation theorem and Suslin's theorem provide the fundamental structural results for analytic and coanalytic sets, characterizing Borel sets as exactly those that are both analytic and coanalytic.

Lusin Separation

Theorem9.7Lusin separation theorem

If $A$ and $B$ are disjoint analytic subsets of a Polish space $X$ , then they can be separated by a Borel set: there exists a Borel set $C$ with $A \subseteq C$ and $B \cap C = \emptyset$ .

Proof

We use the tree representation of analytic sets. Write $A = p[\mathcal{T}_A]$ and $B = p[\mathcal{T}_B]$ where $\mathcal{T}_A, \mathcal{T}_B$ are trees on $\omega \times \omega$ and $p$ is the projection to the first coordinate.

Key Lemma: Two sets $A = p[S_A]$ and $B = p[S_B]$ (projections of trees) are Borel-separable iff they are "separated at every finite level." Formally, define $A_s = p[\mathcal{T}_A \cap N_s]$ for basic open $N_s$ . A combinatorial argument on the trees shows:

If $A \cap B = \emptyset$ but $A$ and $B$ are not Borel-separable, then one can find sequences converging to a point in $A \cap B$ (since the trees cannot be "untangled" at any finite level, forcing an intersection at the limit). This contradicts $A \cap B = \emptyset$ .

More precisely: assume $A$ and $B$ cannot be separated by a Borel set. Build a Cantor-scheme (a tree of finite sequences) such that at each node, neither $A$ nor $B$ restricted to the corresponding neighborhood can be Borel-separated from the other. The branches of this scheme produce a point in $A \cap B$ , contradiction. $\blacksquare$

■

Suslin's Theorem

Theorem9.2Suslin's theorem

A subset of a Polish space is Borel if and only if it is both analytic and coanalytic:

$\boldsymbol{\Delta}^1_1 := \boldsymbol{\Sigma}^1_1 \cap \boldsymbol{\Pi}^1_1 = \mathbf{Borel}.$

Proof

Every Borel set is analytic (by definition) and coanalytic (complement of a Borel set is Borel, hence analytic). So $\mathbf{Borel} \subseteq \boldsymbol{\Delta}^1_1$ .

Conversely, if $A$ is both analytic and coanalytic, then $A$ and $X \setminus A$ are disjoint analytic sets. By Lusin separation, there exists a Borel set $C$ with $A \subseteq C \subseteq X \setminus (X \setminus A) = A$ . So $C = A$ , and $A$ is Borel. $\blacksquare$

■

Applications

ExampleIdentifying Borel sets

To show a set $A$ is Borel, it suffices to show both $A$ and its complement are analytic. This is often easier than constructing $A$ explicitly from open sets via countable operations.

For instance, the set of continuous nowhere-differentiable functions in $C([0,1])$ is $\boldsymbol{\Pi}^1_1$ (coanalytic). To determine whether it is Borel, one must check whether it is also $\boldsymbol{\Sigma}^1_1$ . (It turns out to be a dense $G_\delta$ , hence Borel, by the Baire category theorem applied to Banach-Mazur games.)

RemarkThe first separation theorem fails at higher levels

While disjoint $\boldsymbol{\Sigma}^1_1$ sets can always be separated by a Borel ( $= \boldsymbol{\Delta}^1_1$ ) set, disjoint $\boldsymbol{\Sigma}^1_2$ sets cannot always be separated by a $\boldsymbol{\Delta}^1_2$ set (this is independent of ZFC). Under projective determinacy, the separation theorem holds at odd projective levels: disjoint $\boldsymbol{\Sigma}^1_{2n+1}$ sets can be separated by $\boldsymbol{\Delta}^1_{2n+1}$ sets.