The Lumenary · First-year graduate

Descriptive set theory

Name: ______________________

Date: ______________________

You will learn to

Define Polish spaces, Baire space and Cantor space, and represent closed sets by trees
Define the Borel hierarchy and locate standard sets in it, using the Baire category theorem to prove non-membership
Prove that every uncountable analytic set contains a perfect set and hence has cardinality $2^{\aleph_0}$
Prove the Lusin separation theorem and deduce Suslin's theorem that the Borel sets are exactly the sets that are both analytic and coanalytic
Explain why projections of Borel sets need not be Borel, and what ZFC, $V = L$ and large cardinals say about projective sets

1.
Where does $\Q$ sit in the Borel hierarchy of $\R$ ?
- A. $\Sigma^0_2$ ( $F_\sigma$ ) but not $\Pi^0_2$ ( $G_\delta$ )
- B.Open
- C.Closed
- D. $G_\delta$ but not $F_\sigma$
2.
Which of these spaces (with their usual topologies) are Polish? Choose all that apply.
- A.The irrationals $\R \setminus \Q$
- B.The open interval $(0, 1)$
- C.Cantor space $2^\N$
- D. $\Q$
- E. $\ell^\infty$ , the bounded real sequences with the sup norm
3.
Which kind of subset of $\R^2$ can have a projection onto the $x$ -axis that is not Borel?
- A.A $G_\delta$ subset of $\R^2$
- B.A closed subset of $\R^2$
- C.An open subset of $\R^2$
- D.A compact subset of $\R^2$
4.
In the proof that an uncountable analytic set $A = f[\mathcal N]$ contains a perfect set, why do we first remove the open set $U$ (the union of the $N_s$ with $f[N_s]$ countable)?
- A.So that every basic set meeting $F = \mathcal N \setminus U$ has uncountable image, and the construction can always split.
- B.To make $A$ closed.
- C.To make $f$ injective on $F$ .
- D.Because $U$ is uncountable.
5.
Let $X = \{0\} \cup \{\tfrac1n : n \ge 1\} \cup \{\tfrac1m + \tfrac1n : m, n \ge 1\}$ , a closed subset of $\R$ . The derived set $X'$ removes the isolated points. How many times must the derivative be applied before the empty set is reached (the Cantor–Bendixson rank of $X$ )?
6.
Mazurkiewicz (1936) studied $D = \{f \in C[0, 1] : f \text{ is differentiable at every point}\}$ , where $C[0, 1]$ has the sup norm. Which statement is correct?
- A. $D$ is coanalytic but not Borel.
- B. $D$ is a $G_\delta$ set.
- C. $D$ is comeagre in $C[0, 1]$ .
- D. $D$ is analytic but not coanalytic.
7.
Which Lean statement formalises (one direction of) Suslin's theorem in a Hausdorff space with Borel σ-algebra?
- A.AnalyticSet A → AnalyticSet Aᶜ → MeasurableSet A
- B.MeasurableSet A → AnalyticSet A
- C.AnalyticSet A → MeasurableSet A
- D.AnalyticSet A → AnalyticSet B → Disjoint A B → MeasurablySeparable A B
8.
The Lean proof of rat_not_isGδ applies Dense.inter_of_Gδ to two sets. What does it conclude, and why is that a contradiction?
- A.That $\Q \cap (\R \setminus \Q)$ is dense — impossible, since this set is empty and $\R$ is non-empty.
- B.That $\Q$ is meagre.
- C.That $\Q$ is closed.
- D.That $\R$ is countable.
9.
A tree on $\{0, 1\}$ is given by a predicate tree(s) on binary strings. Write split_height(tree, n): the height of the largest full binary tree whose branching nodes are branching nodes of the tree, within depth $n$ . Recursively, at a node $t$ of length $n$ the height is $0$ ; otherwise it is the maximum of the children's heights and, if both children are in the tree, $1 + \min$ of their heights.
Computational — Practice

Answer key — Descriptive set theory

1.
$\Q = \bigcup_{q} \{q\}$ is $F_\sigma = \Sigma^0_2$ . If it were also $G_\delta$ , then $\Q$ and $\R \setminus \Q$ would be two dense $G_\delta$ sets with empty intersection, contradicting the Baire category theorem. So $\Q \in \Sigma^0_2 \setminus \Pi^0_2$ .
2.
The irrationals, $(0, 1)$ and $2^\N$ are Polish. $\Q$ fails complete metrisability (Baire category) and $\ell^\infty$ fails separability.
3.
Projections of open, closed or compact sets are open, $F_\sigma$ or compact respectively — all Borel — because $\R^2$ is $\sigma$ -compact. But a $G_\delta$ subset of $\R^2$ can be homeomorphic to a closed subset of $\R \times \N^\N$ , whose projections are exactly the analytic sets, some of which are not Borel. This is where Lebesgue's argument broke down.
4.
Removing $U$ costs only the countable set $f[U]$ , and afterwards every non-empty piece $N_s \cap F$ has uncountable image. This is what lets the construction choose, at every node, two points with distinct images and separate them by disjoint balls — producing a Cantor scheme and an embedded copy of $2^\N$ .
5.
$X' = \{0\} \cup \{\tfrac1k : k \ge 1\}$ (each $\tfrac1k$ is the limit of $\tfrac1k + \tfrac1n$ ), $X'' = \{0\}$ , and $X''' = \varnothing$ . So the rank is $3$ . Closed countable sets are exactly the closed sets whose derivatives reach $\varnothing$ at some countable ordinal — this is Cantor–Bendixson.
6.
$f \in D$ iff for every $x \in [0, 1]$ the difference quotients at $x$ form a Cauchy family — a universal quantifier over the reals in front of a Borel condition, so $D$ is $\Pi^1_1$ . Mazurkiewicz showed it is not Borel (it is $\Pi^1_1$ -complete). Generic continuous functions are nowhere differentiable, so $D$ is meagre.
7.
AnalyticSet A → AnalyticSet Aᶜ → MeasurableSet A (the lesson's suslin_from_lusin and suslin). The Lusin separation theorem (option d) is the tool used to prove it.
8.
Assuming $\Q$ is $G_\delta$ , the theorem gives that $\Q \cap \{x : x \text{ irrational}\}$ is dense. That set is empty, and the empty set is not dense in the non-empty space $\R$ (Dense.nonempty). This is the Baire category argument of the lesson.
9.
```
def split_height(tree, n, t=''):
    if len(t) == n:
        return 0
    kids = [t + b for b in '01' if tree(t + b)]
    heights = [split_height(tree, n, c) for c in kids]
    best = max(heights, default=0)
    if len(kids) == 2:
        best = max(best, 1 + min(heights))
    return best
```
For the 'at most two 1s' tree the answer stays $2$ however deep we look — its body is countable, of Cantor–Bendixson rank $3$ . For a perfect tree it grows without bound. But as the lesson's experiment shows, unbounded growth does not prove that the body is uncountable: finite truncations cannot decide the perfect set dichotomy.