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.