# Proof: a representation of the Borel σ-algebra on reals

This post elaborates on the proof of a proposition in page 17 of the book “Probability with martingales” by David Williams. The relevant proposition is first stated; the Borel σ-algebra $\mathcal{B}:=\mathcal{B}(\mathbb{R})$ on the set $\mathbb{R}$ of real numbers is given by $\mathcal{B}=\sigma (\pi (\mathbb{R}))$, where $\sigma(\pi(\mathbb{R}))$ denotes the sigma algebra on $\mathbb{R}$ generated by $\pi (\mathbb{R})=\{(-\infty, x]:x\in\mathbb{R}\}$.

It is reminded that the Borel σ-algebra $\mathcal{B}(S)$ on a set $S$ is the σ-algebra $\sigma(\mathcal{O})$ generated by the family $\mathcal{O}$ of open subsets of $S$, i.e. $\mathcal{B}(S):=\sigma(\mathcal{O})$.

Two lemmas are provided before proceeding with the proof.

Lemma 1

Let $S$ be a set, and let $\mathcal{C}_1,\mathcal{C}_2$ be two collections of subsets of $S$. If $\mathcal{C}_1\subseteq\sigma(\mathcal{C}_2)$, then $\sigma(\mathcal{C}_1)\subseteq\sigma(\mathcal{C}_2)$.

Proof of lemma 1

$\sigma(\mathcal{C}_2)$ is a σ-algebra on $S$ that contains $\mathcal{C}_1$ and $\sigma(\mathcal{C}_1)$ is the intersection of all σ-algebras on $S$ that contain $\mathcal{C}_1$, so $\sigma(\mathcal{C}_1)\subseteq\sigma(\mathcal{C}_2)$.

Lemma 2

Every open subset $G$ of $\mathbb{R}$ in the Euclidean metric space $(\mathbb{R},\|\cdot\|)$ can be represented uniquely as a countable union of disjoint open intervals.

Proof of lemma 2

This lemma appears also as theorem 1.3, p. 6, in the book “Real analysis: measure theory, integration and Hilbert spaces” by Elias M. Stein and Rami Shakarchi, where a partial proof is provided as uniqueness is not established. In what follows, the proof from Stein’s and Shakarchi’s book is reproduced in more detail, plus uniqueness is proved.

Let $G$ be an open subset of $\mathcal{R}$ and $x\in G$. Introduce the sets $\mathcal{A}_x:=\{a\in\mathbb{R}: a and $\mathcal{B}_x:=\{b\in\mathbb{R}: x. Moreover, let $a_x:=\mbox{inf}\mathcal{A}_x$ and $b_x:=\mbox{sup}\mathcal{B}_x$, allowing for $a_x,b_x$ to be infinite. Consider also the interval $I_x:=(a_x,b_x)$.

It will be shown that $I_x\subseteq G$. Let $y\in I_x$. Assume that $(\forall a\in\mathcal{A}_x)y\le a$, in which case $y$ is a lower bound of $\mathcal{A}_x$, so $y\le a_x$, thus contradicting the assumption $y\in I_x=(a_x, b_x)$. Hence, there exists $a\in\mathcal{A}_x$ such that $a. By a symmetric argument, there exists $b\in\mathcal{B}_x$ such that $y. So, $y\in (a,b)\subseteq (a_x,b_x)$. If $y=x$, then obviously $y\in G$. If $y\neq x$, then $y\in (a,x)\cup (x, b)$. Note that $a\in\mathcal{A}_x$ means that $(a,x)\subseteq G$. So, if $y\in (a,x)$, then $y\in G$. Similarly, if $y\in (x,b)$, then $y\in G$. Thus, $y\in I_x\Rightarrow y\in G$, which means that $I_x\subseteq G$.

$(\forall x\in G) I_x\subseteq G\Rightarrow\underset{x\in G}{\bigcup}I_x\subseteq G$. Furthermore, let $y\in G$. As $G=G^{o}$, there exists $r>0$ such that $(x-r,x+r)\subseteq G$. It follows from $y-r and $(y-r,y)\subseteq (y-r,y+r)\subseteq G$ that $y\in\mathcal{A}_y$. In a similar way, $y\in\mathcal{B}_y$. So, $a_y\le y\le b_y\Rightarrow y\in I_y\subseteq\underset{x\in G}{\bigcup}I_x$. Hence, $G=\underset{x\in G}{\bigcup}I_x$.

Assume that $I_x\cap I_y\neq\emptyset$, in which case $I_x\cup I_y$ is also an open interval. It is straightforward to confirm that if $I$ is an open interval containing $x$ and being contained in $G$, then $I\subseteq I_x$. So, $I_x\cup I_y\subseteq I_x$ and $I_x\cup I_y\subseteq I_y$, which yields $I_x=I_y$. It has been shown that $I_x\cap I_y\neq\emptyset\Rightarrow I_x=I_y$. By contraposition, $I_x\neq I_y\Rightarrow I_x\cap I_y=\emptyset$, which means that the sets of the collection $\{I_x:x\in G\}$ are pairwise disjoint.

For every set $I_x$ in $\{I_x :x\in G\}$, pick a rational $q_x\in I_x$. The set $S:=\{q_x: q_x\in I_x\}$ of selected rationals is obviously a subset of the set $\mathbb{Q}$ of rationals. $S\subseteq\mathbb{Q}$ implies the cardinality inequality $|S|\le |Q|$, so $S$ is a countable set. Since  $|\{I_x :x\in G\}|=|S|$, it is deduced that the collection $\{I_x :x\in G\}$ is also countable.

It has been proved so far that $G$ can be expressed as a countable union of disjoint open intervals. Although not pertinent to the subsequent proof, it will be shown that such representation is unique for the sake of completeness of exposition.

Let $\{I_k : k\in K\}$ and $\{J_{\ell} : \ell\in L\}$ be two collections of disjoint open intervals such that $G=\underset{k\in K}{\bigcup}I_k=\underset{\ell\in L}{\bigcup}J_{\ell}$.

For any $k\in K$, it holds that $I_k=\underset{\ell\in L}\bigcup(I_k\cap J_{\ell})$. Moreover, the sets of the collection $\{I_k\cap J_{\ell}:\ell\in L\}$ are pairwise disjoint. Since $I_k$ and $J_{_\ell}$ are open, $(I_k\cap J_{\ell})^{o}=I_k^{o}\cap J_{\ell}^{o}=I_k\cap J_{\ell}$, which means that $I_k\cap J_{\ell}$ is also open.

In the collection $\{I_k\cap J_{\ell}:\ell\in L\}$, at least one set is non-empty, otherwise trivially $G=\emptyset$.

In the Euclidean metric space $(\mathbb{R},\|\cdot\|)$, every interval is a connected set. Since $I_k$ is an interval, it is connected. Furthermore, a subset $S$ of a metric space $E$ is connected, if and only if there is no open cover $\{A,B\}$ of $S$ such that $S\cap A\neq\emptyset$, $S\cap B\neq\emptyset$ and $S\cap A\cap B=\emptyset$. Hence, by also considering that $I_k$ is connected, it is deduced that at most one set in $\{I_k\cap J_{\ell}:\ell\in L\}$ is non-empty.

So, exactly one set in $\{I_k\cap J_{\ell}:\ell\in L\}$ is non-empty, say $I_k\cap J_{\ell}$. Consequently, $I_k=I_k\cap J_{\ell}$, which in turns gives $I_k\subseteq J_{\ell}$.

In an analogous manner, starting from $J_{\ell}=\underset{k\in K}\bigcup(J_{\ell}\cap I_k)$, it is concluded that $J_{\ell}\subseteq I_k$. So, $I_k=J_{\ell}$, therefore the collections $\{I_k : k\in K\}$ and $\{J_{\ell} : \ell\in L\}$ coincide.

Proof of $\boldsymbol{\mathcal{B}(\mathbb{R})=\sigma(\pi(\mathbb{R}))}$

Let $\mathcal{O}$ be the family of open subsets in the Euclidean metric space $(\mathbb{R},\|\cdot\|)$. It will be shown that the Borel σ-algebra $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{O})$ on $\mathbb{R}$ is equal to the σ-algebra $\sigma(\pi(\mathbb{R}))$ on $\mathbb{R}$ generated by $\pi (\mathbb{R})=\{(-\infty, x]:x\in\mathbb{R}\}$.

Firstly, it will be proved that $\pi (\mathbb{R})\subseteq\sigma(\mathcal{O})$. Consider a set $(-\infty, x]\in\pi (\mathbb{R})$. Note that $(-\infty, x]=\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$. Indeed, for $y\in\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$, it holds that $(\forall n\in\mathbb{N})y. Now assume that $x, in which case $y-x>0$, so by the Archimedean property, there exists $n_o \in\mathbb{N}$ such that $0<1/n_o , whence $x+1/n_o, which is a contradiction. Thus, $y\le x$, i.e. $y\in(-\infty,x]$. It has been established that $\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)\subseteq (-\infty,x]$. Obviously  $(-\infty,x]\subseteq\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$ holds too.

Since $(-\infty,x+1/n)\in\mathcal{O}$ and $\sigma(\mathcal{O})$ is a σ-algebra on $\mathbb{R}$, the countable intersection $(-\infty, x]=\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$ belongs to $\sigma(\mathcal{O})$.

With the help of lemma 1, $\pi (\mathbb{R})\subseteq\sigma(\mathcal{O})$ yields $\sigma(\pi (\mathbb{R}))\subseteq\sigma(\mathcal{O})=\mathcal{B}(\mathbb{R})$.

To prove the converse set inequality $\sigma(\mathcal{O}) \subseteq\sigma(\pi (\mathbb{R}))$, start by proving that $\mathcal{O}\subseteq\sigma(\pi (\mathbb{R}))$. Along these lines, consider an open set $G\in\mathcal{O}$. It is known from lemma 2 that $X$ can be written as a countable union of open intervals.

Let $(a, b)$ be one of these open intervals in the countable union. Recall from the proof of lemma 2 that $a, b$ can be infinite. Consequently, four cases are distinguished:

1. $a\in\mathbb{R}, b\in\mathbb{R}$. Set $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$, where $\epsilon=(b-a)/2$. This case will be treated in detail.
2. $a=-\infty, b\in\mathbb{R}$. Set $(-\infty, b)=\underset{n\in\mathbb{N}}{\bigcup}(-\infty,b-\epsilon/n]$, where $\epsilon=(b-a)/2$.
3. $a\in\mathbb{R}, b=\infty$. Set $(a,\infty)=\underset{n\in\mathbb{N}}{\bigcup}(a,n]$.
4. $a=\infty, b=\infty$. Set $(-\infty, \infty)=(-\infty,c]\cup(c,\infty)$ for any real $c$, which leads back to case 3.

Case 1 is now treated in detail. The equality $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$ is proved by observing that $y\in (a,b)\Leftrightarrow (\exists n_o \in\mathbb{N}) a. Leaving aside the remaining trivial deductions among these equivalences, it will be clarified that $y\in (a,b)\Rightarrow (\exists n_o \in\mathbb{N}) a. So, $y means $0 < (b-y)/\epsilon$. By the Archimedean property, there exists $n_o\in\mathbb{N}$ such that $0 < 1/n_o < (b-y)/\epsilon$, whence $y.

A set of the form $(a, u], a, can be written as $(a,u]=(-\infty, u]\cap(-\infty, a]^{c}$. So, the sets $(a,b-\epsilon/n], n\in\mathbb{N}$, appearing in $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$ can be expressed as $(a,b-\epsilon/n]=(-\infty,b-\epsilon/n]\cap(-\infty, a]^{c}$. Thereby, $(-\infty,b-\epsilon/n]\in\pi(\mathbb{R})$ and $(-\infty,a]\in\pi(\mathbb{R})$ along with the fact that $\sigma (\pi(\mathbb{R}))$ is a σ-algebra lead to $(a,b-\epsilon/n]\in\sigma (\pi(\mathbb{R}))$. So, $(a,b)\in\sigma (\pi(\mathbb{R}))$, which implies $\mathcal{O}\subseteq\sigma(\pi (\mathbb{R}))$. Finally, $\sigma(\mathcal{O}) \subseteq\sigma(\pi (\mathbb{R}))$ by application of lemma 1, so $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{O}) =\sigma(\pi (\mathbb{R}))$.