Here we prove that an uncountable separable metric space has very few Borel subsets. More precisely:

Theorem: Let $X$ be an infinite separable metric space and let $\mathcal{B}_X$ denote the set of Borel subsets of $X$. Then $\mathrm{card} (\mathcal{B}_X) = 2^{\aleph_0}$.

As a corollary, we deduce that $\mathbb{R}$ has $2^{2^{\aleph_0}}$ subsets whose only $2^{\aleph_0}$ are Borel sets.

First, we need to define the Borel hierarchy:

Definition: Let $X$ be a metric space and let $\Sigma_1$ (resp. $\Pi_1$) denote the family of open (resp. closed) subsets of $X$. Then, we define $\Sigma_{\alpha}$ and $\Pi_{\alpha}$ for any ordinal $\alpha<\omega_1$ by transfinite induction using:

$\displaystyle \Sigma_{\alpha}= \left( \bigcup\limits_{\beta< \alpha} \Pi_{\alpha} \right)_{\sigma}$ and $\displaystyle \Pi_{\alpha} \left( \bigcup\limits_{\beta < \alpha} \Sigma_{\alpha} \right)_{\delta}$,

where for all $\mathcal{F} \subset \mathfrak{P}(X)$,

$\mathcal{F}_{\sigma} = \left\{ \bigcup\limits_{i \in I} F_i \mid F_i \in \mathcal{F}, \ I \ \text{countable} \right\}$ and $\mathcal{F}_{\delta} = \left\{ \bigcap\limits_{i \in I} F_i \mid F_i \in \mathcal{F}, \ I \ \text{countable} \right\}$.

Finally, let $\Delta_{\alpha}= \Sigma_{\alpha} \cap \Pi_{\alpha}$ for all $\alpha<\omega_1$.

Lemma1: Let $\alpha< \omega_1$ be an ordinal and $A \subset X$. Then $A \in \Sigma_{\alpha}$ if and only if $X \backslash A \in \Pi_{\alpha}$.

Proof. Easy by transfinite induction. The details are left to the reader. $\square$

Lemma 2: Let $X$ be a metric space. We have the following inclusions:

$\begin{matrix} & & \Sigma_1 & & & & \Sigma_2 & & & \\ & \nearrow & & \searrow & & \nearrow & & \searrow & & \\ \Delta_1 & & & & \Delta_2 & & & & \Delta_3 & \dots \\ & \searrow & & \nearrow & & \searrow & & \nearrow & & \\ & & \Pi_1 & & & & \Pi_2 & & & \end{matrix}$

Proof. First, the inclusions $\Delta_{\alpha} \subset \Sigma_{\alpha}, \Pi_{\alpha}$ are clear.

Let $O \in \Sigma_1$. Clearly, $O$ is a $G_{\delta}$-set ie. $O \in \Pi_2$. Moreover, it is a $F_{\sigma}$-set ie. $O \in \Sigma_2$:

$\displaystyle O=f^{-1} ( (0,+ \infty) ) = \bigcup\limits_{n \geq 1} f^{-1} ([1/n,+ \infty))$ where $f : x \mapsto d(x,X \backslash O)$.

Therefore, $\Sigma_1 \subset \Sigma_2 \cap \Pi_2= \Delta_2$. Using lemma 1, we also deduce $\Pi_1 \subset \Delta_2$.

Now, it is easy to show that $\Sigma_{\alpha},\Pi_{\alpha} \subset \Delta_{\alpha+1}$ by transfinite induction. $\square$

Lemma 3: Let $X$ be a metric space. Then $\displaystyle \mathcal{B}_X = \bigcup\limits_{\alpha<\omega_1} \Sigma_{\alpha} = \bigcup\limits_{\alpha < \omega_1} \Pi_{\alpha} = \bigcup\limits_{\alpha<\omega_1} \Delta_{\alpha}$.

Proof. It is easy to show by transfinite induction that $\Sigma_{\alpha},\Pi_{\alpha} \subset \mathcal{B}_X$ for all $\alpha < \omega_1$, hence

$\displaystyle \bigcup\limits_{\alpha < \omega_1} \Sigma_{\alpha}, \bigcup\limits_{\alpha< \omega_1} \Pi_{\alpha}, \bigcup\limits_{\alpha< \omega_1} \Delta_{\alpha} \subset \mathcal{B}_X$.

For convenience, let $\mathcal{B} = \bigcup\limits_{\alpha< \omega_1} \Sigma_{\alpha}$. Then

• $\mathcal{B}$ contains the open subset of $X$.
• $\mathcal{B}$ is stable under countable union:

Let $A_1,A_2, \dots \in \mathcal{B}$. For all $i \geq 1$, $\alpha_i<\omega_1$ be an ordinal such that $A_i \in \Sigma_{\alpha_i}$. Let $\alpha= 2+\sup\limits_{i \geq 1} \alpha_i$. Using lemma 2,

$\displaystyle \bigcup\limits_{i \geq 1} A_i \in \bigcup\limits_{i \geq 1} \Sigma_{\alpha_i} \subset \bigcup\limits_{i \geq 1} \Pi_{\alpha_i+1} \subset \left( \bigcup\limits_{\beta<\alpha} \Pi_{\beta} \right)_{\sigma}= \Sigma_{\alpha}$.

• $\mathcal{B}$ is stable under complement:

Let $A \in \mathcal{B}$ and $\alpha<\omega_1$ such that $A \in \Sigma_{\alpha}$. According to lemmas 1 and 2,

$\displaystyle X \backslash A \in \Pi_{\alpha} \subset \left( \bigcup\limits_{\beta < \alpha+1} \Pi_{\beta} \right)_{\sigma} = \Sigma_{\alpha+1}$.

Therefore, $\mathcal{B}_X \subset \mathcal{B}$ and finally $\mathcal{B}_X= \bigcup\limits_{\alpha<\omega_1} \Sigma_{\alpha}$.

The other equalities follows from $\Sigma_{\alpha} \subset \Pi_{\alpha+1},\Delta_{\alpha+1}$ given by lemma 2. $\square$

Proof of the theorem: First, we show that $|\Sigma_1| \leq 2^{\aleph_0}$.

Let $Q \subset X$ be a countable dense subset and $O \subset X$ be an open subspace. For all $q \in O \cap Q$, define $r(q)= \sup \{ r>0 \mid B(q,r) \subset O \}>0$; if $q \in Q \backslash O$, let $r(q)=-1$. For $q \in O \cap Q$ fixed, let $(p_n(q))$ be an increasing sequence of rationals converging to $r(q)$. Then,

$\displaystyle O= \bigcup\limits_{q \in Q} B(q,r(q))= \bigcup\limits_{q \in Q} \bigcup\limits_{n \geq 0} B(q,p_n(q))$.

The map $O \mapsto ((p_n(q)))$ defines an injection $\Sigma_1 \hookrightarrow (\mathbb{Q}^{\mathbb{N}})^Q$, hence $|\Sigma_1| \leq \aleph_0^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0}$. In particular, we also have $|\Pi_1|= |\Sigma_1| \leq 2^{\aleph_0}$.

Because $|\mathcal{F}_{\sigma}|, | \mathcal{F}_{\delta}| \leq | \mathcal{F}^{\mathbb{N}}| = |\mathcal{F}|^{\aleph_0}$ for all $\mathcal{F} \subset \mathfrak{P}(X)$, it is easy to show by transfinite induction that $|\Sigma_{\alpha}|,|\Pi_{\alpha}| \leq 2^{\aleph_0}$ for all $\alpha< \omega_1$.

Using lemma 3, we deduce that

$\displaystyle |\mathcal{B}_X| = \left| \bigcup\limits_{\alpha< \omega_1} \Sigma_{\alpha} \right| \leq \aleph_1 \cdot 2^{\aleph_0} \leq 2^{\aleph_0} \cdot 2^{\aleph_0} = 2^{\aleph_0}$.

Moreover, $\mathfrak{P}(Q) \subset \mathcal{B}_X$ so $|\mathcal{B}_X| \geq 2^{\aleph_0}$. $\square$

For more information, we can see Srivastava’s book, A Course on Borel Sets. In particular, a topological proof of our theorem for Polish spaces can be found there.