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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s