# Borel sets with countable sections *Written by Claude Opus 5.5 (Anthropic), October 2026, adapting a proof by GPT-6.1 Sol (OpenAI). Self-checked by the writing AI. Public domain (CC0).* Let \(X\) and \(Z\) be standard Borel spaces and \(E\subseteq X\times Z\) a Borel set. The projection of \(E\) to \(X\) need not be Borel: projections of Borel sets are only Souslin sets in general. When every vertical section \(E_x=\{z:(x,z)\in E\}\) is countable, much more is true. The *Lusin–Novikov theorem* (Theorem 3.1) says that \(E\) is then the union of the graphs of countably many Borel maps defined on Borel subsets of \(X\). Consequently the projection of \(E\) is Borel, the counting function \(x\mapsto\#E_x\) is Borel, a point of \(E_x\) can be chosen in a Borel way, and a countable-to-one Borel map carries Borel sets to Borel sets (Corollary 3.2). These facts are used for countable equivalence relations and transversals of measured groupoids in Measured groupoids and transverse measures. The proof codes the sections by trees. Section 1 fixes the language of trees and proves a boundedness lemma: a Borel family of well-founded trees has a common countable height (Lemma 1.2). Section 2 codes a Borel map with closed graph so that its fibres become the branches of a Borel family of trees (Lemma 2.2). Section 3 removes, by a transfinite derivative, the nodes that cannot split; for countable sets of branches the derivative empties every tree after countably many steps, and each branch is read off at the step where its last splitting node disappears. We assume the lessons Polish spaces and standard Borel spaces and The Effros Borel structure, and countable ordinals with transfinite induction and recursion from the core course [Mathematical Logic, Set Theory and Computability](https://kokunoyumeto.github.io/program-matematika-indonesia/en/#course-C80). Section 1 lists exactly what is used. The proof follows Section 5 of [GPT-6.1 Sol, Transverse measures of foliations], which is in the public domain (CC0). This lesson checks it, measures well-founded trees by a leaf-removal derivative instead of rank functions, and adds the details of the closed coding and of the corollaries. The theorem is stated, with a different proof, as Theorem 13.6 in [Tserunyan], and its uniformization form is recalled in [Kechris–Wolman 2024, Theorem 1.4]. ## 1. Trees, heights and a boundedness lemma ### Conventions and results used \(\mathbb N=\{0,1,2,\ldots\}\), and \(\Lambda=\mathbb N^{\mathbb N}\) is the Baire space with the product topology. \(\mathbb N^{<\mathbb N}\) is the countable set of finite sequences (*words*) of natural numbers, including the empty word \(\varnothing\). We write \(|s|\) for the length of \(s\), \(s\sqsubseteq t\) when \(s\) is a prefix of \(t\), \(s\sqsubset t\) when moreover \(s\neq t\), \(s{}^\frown n\) for the word \(s\) followed by \(n\), and \(w|n\) for the word of the first \(n\) terms of \(w\in\Lambda\). Two words are *comparable* if one is a prefix of the other. A *tree* is a set \(T\subseteq\mathbb N^{<\mathbb N}\) that contains every prefix of each of its words; the empty tree is allowed. A *branch* of \(T\) is a \(w\in\Lambda\) with \(w|n\in T\) for every \(n\), and \([T]\) is the set of branches. \(T\) is *well-founded* if \([T]=\varnothing\). Trees on another countable alphabet, such as \(\mathbb N\times\mathbb N\), are defined in the same way and are trees on \(\mathbb N\) after a bijection of the alphabet with \(\mathbb N\). The set \(\mathrm{Tr}\) of trees is a subset of \(\{0,1\}^{\mathbb N^{<\mathbb N}}\), a compact metrizable space with the product topology. A map \(x\mapsto T_x\) from a measurable space into \(\mathrm{Tr}\) is called *Borel* if every set \(\{x:s\in T_x\}\) is measurable. We use the following results. - **(P1)** Every nonempty Polish space is a continuous image of \(\Lambda\) (Polish spaces and standard Borel spaces, Theorem 1.1). - **(P2)** If \(Y\) is a standard Borel space and \(f\) an injective Borel map of \(Y\) into a standard Borel space, then \(f(Y)\) is Borel and \(f\) is a Borel isomorphism onto \(f(Y)\) (Polish spaces and standard Borel spaces, Theorem 4.3(5)). - **(P3)** Let \((X,\tau)\) be Polish. Call a topology *admissible* if it is Polish, contains \(\tau\), and has the same Borel sets. Every Borel set is clopen for some admissible topology, and the topology generated by countably many admissible topologies is admissible. A Borel subset of a standard Borel space is standard. (The Effros Borel structure, Theorem 2.2 and steps (b) and (c) of its proof.) - **(P4)** Countable ordinals, transfinite induction and transfinite recursion: the core course [Mathematical Logic, Set Theory and Computability](https://kokunoyumeto.github.io/program-matematika-indonesia/en/#course-C80), whose set theory part is the Open Logic Project's *Set Theory*, chapters *Ordinals* and *Stages and Ranks*; the first contains the Burali-Forti theorem that the ordinals do not form a set. An ordinal is *countable* if it has countably many predecessors. - **(P5)** Cantor's intersection theorem: in a complete metric space, a decreasing sequence of nonempty closed sets with diameters tending to \(0\) has exactly one common point. ### Heights of well-founded trees For a tree \(T\) let \(\partial T=\{s\in T:\ s{}^\frown n\in T\text{ for some }n\}\), the tree \(T\) without its leaves. Define by transfinite recursion \[ T^{[0]}=T,\qquad T^{[\alpha+1]}=\partial\big(T^{[\alpha]}\big),\qquad T^{[\lambda]}=\bigcap_{\alpha<\lambda}T^{[\alpha]}\ \ (\lambda\text{ a limit}). \] These are trees, and they decrease. **Lemma 1.1.** 1. If \(T\) is well-founded, then \(T^{[\alpha]}=\varnothing\) for some countable ordinal \(\alpha\). The least such \(\alpha\) is the *height* \(\operatorname{ht}(T)\). 2. If \(h:T\to U\) is a map between trees with \(h(s)\sqsubset h(t)\) whenever \(s\sqsubset t\), then \(h(T^{[\alpha]})\subseteq U^{[\alpha]}\) for every \(\alpha\). In particular, if \(U\) is well-founded, so is \(T\), and \(\operatorname{ht}(T)\le\operatorname{ht}(U)\). **Proof.** (1) Fix an enumeration of \(\mathbb N^{<\mathbb N}\). If \(T^{[\alpha+1]}=T^{[\alpha]}\) for some \(\alpha\), then \(T^{[\beta]}=T^{[\alpha]}\) for all \(\beta\ge\alpha\), by transfinite induction. Let \(\alpha\) be the least ordinal with \(T^{[\alpha+1]}=T^{[\alpha]}\); it exists, because otherwise the first word of \(T^{[\beta]}\setminus T^{[\beta+1]}\) would define an injective map from the class of all ordinals into the countable set \(\mathbb N^{<\mathbb N}\) (the sets \(T^{[\beta]}\setminus T^{[\beta+1]}\) are disjoint), and by Replacement the ordinals would form a set, against the Burali-Forti theorem (P4). The same map, restricted to the predecessors of \(\alpha\), is injective, so \(\alpha\) is countable. Put \(S=T^{[\alpha]}\). Every word of \(S\) has a one-letter extension in \(S\). If \(S\neq\varnothing\), start at the empty word (which lies in \(S\), a nonempty tree) and repeatedly append the least \(n\) that keeps the word in \(S\); this defines a branch of \(S\subseteq T\). As \(T\) is well-founded, \(S=\varnothing\). (2) By induction on \(\alpha\). The case \(\alpha=0\) is clear, and limits follow from the intersection. Let \(s\in T^{[\alpha+1]}\), so \(s{}^\frown n\in T^{[\alpha]}\) for some \(n\). By induction \(h(s{}^\frown n)\in U^{[\alpha]}\), and it properly extends \(h(s)\). Since \(U^{[\alpha]}\) is a tree, it contains \(h(s)\) and the one-letter extension of \(h(s)\) that is a prefix of \(h(s{}^\frown n)\). So \(h(s)\in\partial U^{[\alpha]}=U^{[\alpha+1]}\). If \(U\) is well-founded, then \(U^{[\operatorname{ht}(U)]}=\varnothing\), so \(T^{[\operatorname{ht}(U)]}=\varnothing\); then \(T\) has no branch, since every word of a branch lies in every \(T^{[\alpha]}\) (each word of a branch has a one-letter extension on the branch). \(\square\) **Lemma 1.2** (boundedness). Let \(X\) be a standard Borel space and \(x\mapsto T_x\) a Borel map into \(\mathrm{Tr}\) such that every \(T_x\) is well-founded. Then there is a countable ordinal \(\theta\) with \(T_x^{[\theta]}=\varnothing\) for every \(x\in X\). **Proof.** We may assume \(X\neq\varnothing\) and that \(X\) is a Polish space. The countably many sets \(\{x:s\in T_x\}\) are Borel. By (P3), each is clopen for an admissible topology, and the topology generated by these countably many admissible topologies is admissible; in it all these sets are clopen, so \(x\mapsto T_x\) is continuous into \(\mathrm{Tr}\). By (P1) there is a continuous surjection \(\varphi\) of \(\Lambda\) onto \(X\) with this topology. Put \(f=T_\cdot\circ\varphi\), a continuous map \(\Lambda\to\mathrm{Tr}\) whose values are exactly the trees \(T_x\). Let \(U\) be the set of pairs \((u,s)\) of words of the same length such that \(u\sqsubseteq z\) and \(s\in f(z)\) for some \(z\in\Lambda\). We view \(U\) as a set of words on the alphabet \(\mathbb N\times\mathbb N\), the \(k\)-th letter of \((u,s)\) being \((u_k,s_k)\). It is a tree: if \((u,s)\) is witnessed by \(z\), each pair of prefixes of the same length is witnessed by \(z\), because \(f(z)\) is a tree. \(U\) is well-founded. Suppose \((z,y)\in\Lambda\times\Lambda\) were a branch, and for each \(n\) choose \(z_n\in\Lambda\) with \(z|n\sqsubseteq z_n\) and \(y|n\in f(z_n)\). Then \(z_n\to z\). Fix \(k\). For \(n\ge k\), \(y|k\in f(z_n)\), as a prefix of \(y|n\). The set of trees containing \(y|k\) is closed in \(\mathrm{Tr}\) and \(f\) is continuous, so \(y|k\in f(z)\). Thus \(y\) is a branch of \(f(z)\), which is impossible. For \(z\in\Lambda\), the map \(h_z(s)=(z|\,|s|,\ s)\) sends \(f(z)\) into \(U\) and strictly increasing pairs to strictly increasing pairs. By Lemma 1.1(2), \(f(z)^{[\theta]}=\varnothing\) with \(\theta=\operatorname{ht}(U)\), a countable ordinal by Lemma 1.1(1). \(\square\) ## 2. Coding a Borel map by trees **Lemma 2.1** (closed embedding). Let \(Y\) be a Polish space with a countable base of clopen sets. Then \(Y\) is homeomorphic to a closed subset of \(\Lambda\). **Proof.** Fix a complete compatible metric. We build partitions \(\mathcal P_n\) (\(n\ge1\)) of \(Y\) into countably many nonempty clopen sets of diameter at most \(2^{-n}\), each \(\mathcal P_{n+1}\) refining \(\mathcal P_n\), and put \(\mathcal P_0=\{Y\}\). Given a cell \(C\) of \(\mathcal P_n\), every point of \(C\) lies in a basic clopen subset of \(C\) of diameter at most \(2^{-n-1}\). Countably many of these cover \(C\), since the base is countable; subtracting from each the union of the earlier ones keeps them clopen, and we discard the empty ones. Enumerate the cells of each \(\mathcal P_n\) by an initial segment of \(\mathbb N\), and let \(c(y)\in\Lambda\) be the sequence whose \(n\)-th term is the index of the cell of \(\mathcal P_n\) containing \(y\) (with \(c(y)_0=0\)). The map \(c\) is continuous, because the cells are open, and injective, because the diameters tend to \(0\). Call \(w\in\Lambda\) *allowed* if \(w_0=0\), each \(w_n\) indexes a cell of \(\mathcal P_n\), and the cell indexed by \(w_{n+1}\) lies in the cell indexed by \(w_n\). The allowed sequences form a closed set, since each condition involves two coordinates. Every \(c(y)\) is allowed. Conversely, for an allowed \(w\) the cells indexed by \(w_n\) are nonempty, closed and decreasing, with diameters tending to \(0\), so by (P5) they have one common point \(y\), and \(c(y)=w\). So \(c(Y)\) is the closed set of allowed sequences. Finally \(c^{-1}\) is continuous on \(c(Y)\): if \(c(y_k)\to c(y)\), then for each \(n\) eventually \(y_k\) lies in the cell of \(\mathcal P_n\) containing \(y\), whose diameter is at most \(2^{-n}\). \(\square\) **Lemma 2.2** (coding). Let \(p:Y\to X\) be a Borel map between standard Borel spaces. There are a Polish topology on \(X\), a homeomorphism \(c\) of \(Y\), with a suitable Polish topology having the same Borel sets, onto a closed set \(c(Y)\subseteq\Lambda\), and a Borel map \(x\mapsto T_x\) from \(X\) into \(\mathrm{Tr}\) such that \(p\) is continuous and \[ [T_x]=\{c(y):\ p(y)=x\}\qquad\text{for every }x\in X. \] **Proof.** Fix Polish topologies on \(X\) and \(Y\), a compatible metric \(d\) on \(X\) and a countable base \((V_k)\) of \(X\). By (P3), the topology \(\tau_0\) generated by admissible topologies on \(Y\) in which the Borel sets \(p^{-1}(V_k)\) are open is admissible, and \(p\) is continuous for it. Recursively, let \(\tau_{m+1}\) be an admissible topology, containing \(\tau_m\), in which every member of a fixed countable base \(\mathcal B_m\) of \(\tau_m\) is clopen (P3). The topology \(\tau_\infty\) generated by all \(\tau_m\) is admissible (P3). The sets of \(\bigcup_m\mathcal B_m\) are clopen in \(\tau_\infty\), and their finite intersections form a countable base of \(\tau_\infty\). So \((Y,\tau_\infty)\) is a Polish space with a countable base of clopen sets, and \(p\) is continuous. Lemma 2.1 gives the homeomorphism \(c\) onto a closed set \(c(Y)\subseteq\Lambda\). Let \(R=\{(p(y),c(y)):y\in Y\}\), the graph of the continuous map \(p\circ c^{-1}\) on the closed set \(c(Y)\), read with the coordinates exchanged; it is closed in \(X\times\Lambda\). For a word \(s\) put \[ U_s=\bigcup\big\{B_d(x',2^{-|s|}):\ (x',w)\in R,\ s\sqsubseteq w\big\},\qquad T_x=\{s:\ x\in U_s\}. \] Each \(U_s\) is open, so \(x\mapsto T_x\) is Borel. If \(s\sqsubseteq s'\), then \(U_{s'}\subseteq U_s\), since the radius only grows and every \(w\) extending \(s'\) extends \(s\); so \(T_x\) is a tree. If \((x,w)\in R\), then \(x\in U_{w|n}\) for every \(n\), so \(w\in[T_x]\). Conversely, let \(w\in[T_x]\). For each \(n\) there is \((x_n,w_n)\in R\) with \(d(x_n,x)<2^{-n}\) and \(w|n\sqsubseteq w_n\). Then \((x_n,w_n)\to(x,w)\), and \((x,w)\in R\) because \(R\) is closed. \(\square\) ## 3. The Lusin–Novikov theorem For a tree \(T\) define the *splitting derivative* by transfinite recursion: \(T^{\langle0\rangle}=T\), \(T^{\langle\lambda\rangle}=\bigcap_{\alpha<\lambda}T^{\langle\alpha\rangle}\) for limits, and \[ T^{\langle\alpha+1\rangle}=\big\{s\in T^{\langle\alpha\rangle}:\ s\sqsubseteq t,\ s\sqsubseteq t'\text{ for two incomparable }t,t'\in T^{\langle\alpha\rangle}\big\}. \] These are trees: if \(s\) has two incomparable extensions in \(T^{\langle\alpha\rangle}\), so has each prefix of \(s\). **Theorem 3.1** (Lusin–Novikov). Let \(X\) and \(Z\) be standard Borel spaces and \(E\subseteq X\times Z\) a Borel set all of whose sections \(E_x\) are countable. Then there are countably many Borel sets \(D_k\subseteq X\) and Borel maps \(f_k:D_k\to Z\) with \[ E=\bigcup_k\{(x,f_k(x)):\ x\in D_k\}. \] **Proof.** *Coding.* By (P3), \(E\) is a standard Borel space. Apply Lemma 2.2 to the projection \(p:E\to X\). For every \(x\), \([T_x]=c(p^{-1}(x))\) is countable. *Uniform emptiness.* A *splitting system* of height \(n\ge1\) in a tree \(T\) is a sequence \(\sigma=(\sigma_1,\ldots,\sigma_n)\) of finite sets of words of \(T\), where \(\sigma_1\) consists of one word and, for \(k