# Proof of Baire’s category theorem

The book “Probability with martingales” by David Williams provides a proof of Baire’s category theorem in p. 203-204. This blog post reproduces the proof in greater detail to clarify some of the statements that are left to the book reader to confirm.

Baire’s category theorem is stated as follows:

If a complete metric space $S$ can be written as a union $S=\underset{n\in\mathbb{N}}{\cup}F_n$ of a countable sequence of closed sets $F_n,n\in\mathbb{N}$, then at least one of these closed sets contains an open ball.

The theorem was proved for $\mathbb{R}^d$ by René-Louis Baire in his PhD thesis “Sur les fonctions de variable réelles“.

Assume a complete metric space $(S,\rho)$ with some metric $\rho:S\times S\rightarrow \mathbb{R}$, which need not be necessarily the Euclidean metric space $(\mathbb{R}^d, |\cdot|)$.

Start by assuming that none of $F_n,n\in\mathbb{N}$, contains an open ball. Moreover, assume that none of the complements $F_n^c,n\in\mathbb{N}$, is empty. If there exists an empty complement $F_n^c=\emptyset$, then $F_n=S$, which is a trivial case of finite union that will be treated at the end of the proof separately.

Since $F_1$ is closed, $F_1^c$ is open, i.e. $F_1^c=(F_1^c)^{\mathrm{o}}$. Due to $F_1^c$ being non-empty, there exists $x_1\in F_1^c=(F_1^c)^{\mathrm{o}}$. Hence, there exists $\epsilon_1 >0$ so that the open ball $B(x_1,\epsilon_1)$ with center $x_1$ and radius $\epsilon_1$ satisfies $B(x_1,\epsilon_1)\subseteq F_1^c$.

By assumption, $F_2$ contains no open ball, so $B(x_1, \epsilon_1/2)\not\subseteq F_2$, which means that $B(x_1, \epsilon_1/2)\cap F_2^c \neq\emptyset$. Furthermore, $B(x_1, \epsilon_1/2)\cap F_2^c$ is an open set as the intersection of the open sets $B(x_1, \epsilon_1/2)$ and $F_2^c$. Thus, there exist $x_2\in B(x_1, \epsilon_1/2)\cap F_2^c$ and $\epsilon_2>0$ with $\epsilon_2<\min \{\epsilon_1/2,1/2\}$ such that $B(x_2,\epsilon_2)\subseteq B(x_1,\epsilon_1/2)\cap F_2^c$. Note that $B(x_2,\epsilon_2)\subseteq B(x_1,\epsilon_1/2)$.

Inductively, choose $\epsilon_n<\min \{\epsilon_{n-1}/2,1/n\},n\in\mathbb{N}$, to introduce the n-th ball $B(x_n,\epsilon_n)\subseteq B(x_{n-1},\epsilon_{n-1}/2)\cap F_n^c$. This way, a countable sequence of nested balls is defined with $B(x_n,\epsilon_n)\subseteq B(x_{n-1},\epsilon_{n-1}/2)$. It will be shown that the centers of these balls make up a Cauchy sequence $(x_n)$. According to the Archimedean property, for any $\epsilon > 0$, there exists $n_0\in\mathbb{N}$ such that $0< 1/n_o < \epsilon$. Let $m,n\in\mathbb{N}$ be natural numbers with $m>n_o$ and $n>n_o$. Using the triangle inequality, $\rho (x_m, x_n) \le \rho (x_m, x_{n_o})+\rho (x_{n_o}, x_n)$. Obviously, $x_n\in B(x_n,\epsilon_n)$. Since $n>n_o$, it follows that $B(x_n,\epsilon_n)\subseteq B(x_{n_o}, \epsilon_{n_o}/2)$, so $x_n\in B(x_{n_o}, \epsilon_{n_o}/2)$. Apparently, $x_n\in B(x_{n_o}, \epsilon_{n_o}/2)$ implies $\rho(x_n,x_{n_o})<\epsilon_{n_o}/2$. As $\epsilon_{n_o}<1/n_o$ and $1/n_o < \epsilon$, it follows that $\rho(x_n,x_{n_o})<\epsilon/2$. Similarly, $\rho(x_m,x_{n_o})<\epsilon/2$, which leads to $\rho (x_m, x_n) < \epsilon$, so the ball centers constitute the Cauchy sequence $(x_n)$. The metric space $(S, \rho)$ has been assumed to be complete, so the Cauchy sequence $(x_n)$ is convergent, therefore its limit $x:=\lim{x_n}$ exists in $S$.

The next step is to show that the limit $x$ of the ball centers $(x_n)$ belongs to the intersection of these balls, i.e. $x\in\underset{n\in\mathbb{N}}{\cap}B(x_n,\epsilon_n)$. Let $n\in \mathbb{N}$ and $m\in\mathbb{N}$ with $m>n$. By applying the triangle inequality, $\rho (x, x_n) \le \rho (x, x_m)+\rho (x_m, x_n)$. Notice that $m>n$ yields $x_m\in B(x_m,\epsilon_m)\subseteq B(x_n, \epsilon_n/2)$, hence $\rho (x_m, x_n) <\epsilon_n/2$, which leads to $\rho (x, x_n) \le \rho (x, x_m)+\epsilon_n/2$. Observe that $(x_m)$ is a subsequence of $(x_n)$, which means that $\underset{m\rightarrow\infty}{\lim}\rho (x, x_m)=0$. So, taking the limit as $m\rightarrow \infty$ produces  $\rho (x, x_n) \le \epsilon_n/2$, whence $x\in B(x_n,\epsilon_n)$ for any $n \in \mathbb{N}$, thus $x\in\underset{n\in\mathbb{N}}{\cap}B(x_n,\epsilon_n)$.

It is obvious from $B(x_n,\epsilon_n)\subseteq B(x_{n-1},\epsilon_{n-1}/2)\cap F_n^c$ that $B(x_n,\epsilon_n)\subseteq F_n^c$. Consequently, $x\in\underset{n\in\mathbb{N}}{\cap}B(x_n,\epsilon_n)\subseteq\underset{n\in\mathbb{N}}{\cap}F_n^c=\left(\underset{n\in\mathbb{N}}{\cup}F_n\right)^c=S^c$. The contradiction $x\in S^c=\emptyset$ has been reached, which completes the proof.

The case of finite union $S=\overset{k}{\underset{n=1}{\cup}}F_n$ is simpler, as it is not needed to construct an infinite sequence of open balls and then take the limit of their centers. Instead, it suffices to observe that the center $x_k$ of the smallest ball $B(x_k,\epsilon_k)$ satisfies $x_k\in\overset{k}{\underset{n=1}{\cap}}B(x_n,\epsilon_n)\subseteq\overset{k}{\underset{n=1}{\cap}} F_n^c$, leading to the analogous contradiction $x_k\in S^c=\emptyset$.

On a final note, it is emphasized that the existence of the countable sequence of ball centers $(x_n)$ is based on the axiom of choice.