Proof of Intervals Are Borel, and Rays, Half-Open Intervals and Rational Intervals Generate the Borel Sigma-Algebra of the Real Line

Throughout, $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{T}_{d_{\mathbb{R}}})$ by Borel Sigma-Algebra of a Metric Space (i) and Borel Sigma-Algebra of a Metric Space (ii), with $\mathcal{T}_{d_{\mathbb{R}}}$ the set of open subsets of $\mathbb{R}$. For a set $\mathcal{C}$ of subsets of $\mathbb{R}$, $\sigma(\mathcal{C})$ is a $\sigma$-algebra on $\mathbb{R}$ containing $\mathcal{C}$, by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (iii), and $\sigma(\mathcal{C})\subseteq\mathcal{F}$ for every $\sigma$-algebra $\mathcal{F}$ on $\mathbb{R}$ with $\mathcal{C}\subseteq\mathcal{F}$, by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (iv). Every open subset of $\mathbb{R}$ belongs to $\mathcal{B}(\mathbb{R})$, by Borel Sets of a Metric Space: Open and Closed Sets, Points, Open Sets of Subspaces, and Subspaces (i). The set $\mathbb{Q}\times\mathbb{Q}$ is countable by Countable Sets: a Bijection from ℕ onto ℕ×ℕ, Finite Sets, Subsets, Surjective Images, Images, Products, and the Integers and Rationals (x), and it is not empty, as $(0,0)\in\mathbb{Q}\times\mathbb{Q}$; so by Countable Set (i) there is a surjective map $s:\mathbb{N}\to\mathbb{Q}\times\mathbb{Q}$. We fix one. For $k\in\mathbb{N}$, $s(k)\in\mathbb{Q}\times\mathbb{Q}$ is an ordered pair of elements of $\mathbb{Q}$ by The Cartesian Product of Two Classes (i), and we let $q_{k}=s(k)_{1}$ and $r_{k}=s(k)_{2}$ be its first and second components. By The Cartesian Product of Two Classes (i), $s(k)=(u,v)$ for some $u,v\in\mathbb{Q}$, and then $q_{k}=u$ and $r_{k}=v$ by The Components of an Ordered Pair (i); so $s(k)=(q_{k},r_{k})$ with $q_{k},r_{k}\in\mathbb{Q}$, and $q_{k}$ and $r_{k}$ are real numbers, $\mathbb{Q}$ being identified with a subset of $\mathbb{R}$ by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (v). From here on no ordered pair is written with parentheses: for real numbers $a,b$, in particular for $q_{k},r_{k}$, the symbol $(a,b)$ denotes the open interval of Intervals of the Real Line (ii), and values of $s$ are described in words.

For $x\in\mathbb{R}$ and real $\varepsilon>0$, Open Ball in a Metric Space (ii) and The Distance on the Real Numbers (i) give

$$B_{d_{\mathbb{R}}}(x,\varepsilon)=\{y\in\mathbb{R}:|x-y|<\varepsilon\}=(x-\varepsilon,x+\varepsilon). \tag{1}$$

Here $x-\varepsilon$ and $x+\varepsilon$ are real numbers (Differences, Quotients and Absolute Values of Real Numbers, Read in the Type Real (i)), and the second equality holds because, for $y\in\mathbb{R}$, $|x-y|<\varepsilon$ if and only if $x-\varepsilon<y<x+\varepsilon$. Indeed, $x-y\in\mathbb{R}$ by Differences, Quotients and Absolute Values of Real Numbers, Read in the Type Real (i). If $y\le x$, then $0\le x-y$ and $|x-y|=x-y$ by Differences, Quotients and Absolute Values of Real Numbers, Read in the Type Real (iii), so $|x-y|<\varepsilon$ if and only if $x-\varepsilon<y$, while $y\le x<x+\varepsilon$ holds anyway as $0<\varepsilon$. If $x<y$, then $x-y<0$ and $|x-y|=-(x-y)=y-x$ by Differences, Quotients and Absolute Values of Real Numbers, Read in the Type Real (iii), so $|x-y|<\varepsilon$ if and only if $y<x+\varepsilon$, while $x-\varepsilon<x<y$ holds anyway. These steps add a real number to both sides of an inequality and rearrange sums and negatives (The Real Numbers as a Type (vi), The Real Numbers as a Type (iv)), and use totality and transitivity of $\le$ (The Real Numbers as a Type (v)).

Open subsets as unions of rational intervals. Let $U\subseteq\mathbb{R}$ be open. Let $W:\mathbb{N}\to\mathcal{P}(\mathbb{R})$ be the map with $W_{k}=(q_{k},r_{k})$ if $q_{k}\le r_{k}$ and $(q_{k},r_{k})\subseteq U$, and $W_{k}=(0,0)$ otherwise (Maps Defined by Cases (i), with $\mathbb{N}$ and $\mathcal{P}(\mathbb{R})$ for its $A$ and $B$ and with $s$ and $U$ among its parameters: the condition on $k$ is predicative, and both values are expressions built from defined set symbols used properly and lie in $\mathcal{P}(\mathbb{R})$, namely the open interval, a defined set symbol used properly at all real arguments with values in $\mathcal{P}(\mathbb{R})$ by Intervals of the Real Line as Defined Set Symbols, Typed Terms and Values of Maps (i), applied to the real numbers $q_{k},r_{k}$, respectively $0,0$, where $q_{k}=s(k)_{1}$ and $r_{k}=s(k)_{2}$ are the components of the value $s(k)$, an ordered pair, and so are defined set symbols used properly by Functions, Values of a Function, and Functions from One Class to Another (ii) and The Components of an Ordered Pair (i)). No real $x$ satisfies $0<x<0$ (The Real Numbers as a Type (v)), so the open interval $(0,0)$ is $\emptyset$; as $0\in\mathbb{Q}$ and $0\le0$, every $W_{k}$ is contained in $U$ and equals $(q,r)$ for some $q,r\in\mathbb{Q}$ with $q\le r$. Hence $\bigcup_{k}W_{k}\subseteq U$. Conversely, let $x\in U$. By Open Subset of a Metric Space (i) there is a real $\varepsilon>0$ with $B_{d_{\mathbb{R}}}(x,\varepsilon)\subseteq U$, that is $(x-\varepsilon,x+\varepsilon)\subseteq U$ by (1). By The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (x) there are $q,r\in\mathbb{Q}$ with $x-\varepsilon<q<x$ and $x<r<x+\varepsilon$. Then $q\le r$, $x\in(q,r)$ and $(q,r)\subseteq(x-\varepsilon,x+\varepsilon)\subseteq U$, by transitivity (The Real Numbers as a Type (v)). Since $s$ is surjective, there is $k\in\mathbb{N}$ such that $s(k)$ is the ordered pair with first coordinate $q$ and second coordinate $r$, that is, $q_{k}=q$ and $r_{k}=r$. Then $q_{k}\le r_{k}$ and $(q_{k},r_{k})\subseteq U$, so $x\in(q_{k},r_{k})=W_{k}$. Therefore $U=\bigcup_{k\in\mathbb{N}}W_{k}$, which proves (i).

A criterion. Let $\mathcal{F}$ be a $\sigma$-algebra on $\mathbb{R}$ with $(q,r)\in\mathcal{F}$ for all $q,r\in\mathbb{Q}$. We show $\mathcal{B}(\mathbb{R})\subseteq\mathcal{F}$. For open $U\subseteq\mathbb{R}$, take $(W_{k})$ as in (i); it is a sequence in $\mathcal{P}(\mathbb{R})$ with all values in $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$, hence a sequence in $\mathcal{F}$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v), so $U=\bigcup_{k}W_{k}\in\mathcal{F}$ by σ-Algebra and Measurable Space (i). Thus $\mathcal{T}_{d_{\mathbb{R}}}\subseteq\mathcal{F}$, and $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{T}_{d_{\mathbb{R}}})\subseteq\mathcal{F}$. We refer to this as (2).

Intervals. Let $I$ be an interval of $\mathbb{R}$, and let

$$O=\{x\in I:a<x<b\text{ for some }a,b\in I\},\quad L=\{x\in I:x\le y\text{ for every }y\in I\},\quad M=\{x\in I:y\le x\text{ for every }y\in I\}.$$

The set $O$ is open. Indeed, let $x\in O$, with $a,b\in I$ and $a<x<b$, and let $\varepsilon=x-a$ if $x-a\le b-x$ and $\varepsilon=b-x$ otherwise. Both differences are real numbers (Differences, Quotients and Absolute Values of Real Numbers, Read in the Type Real (i)) and positive, as $a<x<b$ (The Real Numbers as a Type (vi), The Real Numbers as a Type (iv)); so $\varepsilon$ is a positive real number with $\varepsilon\le x-a$ and $\varepsilon\le b-x$ by totality of $\le$ (The Real Numbers as a Type (v)), that is, $a\le x-\varepsilon$ and $x+\varepsilon\le b$ (The Real Numbers as a Type (vi), The Real Numbers as a Type (iv)). If $y\in B_{d_{\mathbb{R}}}(x,\varepsilon)$, then $x-\varepsilon<y<x+\varepsilon$ by (1), so $a<y<b$ by transitivity (The Real Numbers as a Type (v)); hence $y\in I$ by Intervals of the Real Line (i), applied with $a\le y\le b$, and $y\in O$. So $B_{d_{\mathbb{R}}}(x,\varepsilon)\subseteq O$, $O$ is open by Open Subset of a Metric Space (i), and $O\in\mathcal{B}(\mathbb{R})$.

The set $L$ has at most one element, since $x,x'\in L$ give $x\le x'$ and $x'\le x$, so $x=x'$ by antisymmetry (The Real Numbers as a Type (v)). Thus $L=\emptyset$, which lies in $\mathcal{B}(\mathbb{R})$ by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vi), or $L=\{x\}$ for the element $x$ of $L$, which lies in $\mathcal{B}(\mathbb{R})$ by Borel Sets of a Metric Space: Open and Closed Sets, Points, Open Sets of Subspaces, and Subspaces (iii), applied to $(\mathbb{R},d_{\mathbb{R}})$, a metric space as $d_{\mathbb{R}}$ is a metric on $\mathbb{R}$ by The Absolute Value Metric on the Real Numbers (i). In the same way $M\in\mathcal{B}(\mathbb{R})$.

Finally $I=O\cup L\cup M$. The inclusion $\supseteq$ holds as $O$, $L$ and $M$ are subsets of $I$. Let $x\in I\setminus O$. Then there are no $a,b\in I$ with $a<x$ and $x<b$, so either no $a\in I$ satisfies $a<x$, and then $x\le y$ for every $y\in I$ by totality of $\le$ (The Real Numbers as a Type (v)), that is $x\in L$; or no $b\in I$ satisfies $x<b$, and then $x\in M$. Hence $I=O\cup L\cup M\in\mathcal{B}(\mathbb{R})$ by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vii).

For $a,b\in\mathbb{R}$, each of the sets $(a,b)$, $[a,b]$, $[a,b)$, $(a,b]$, $(a,\infty)$, $[a,\infty)$, $(-\infty,b)$ and $(-\infty,b]$ of Intervals of the Real Line (ii) and Intervals of the Real Line (iii) is an interval by Basic Facts about Intervals of the Real Line (vi), and so belongs to $\mathcal{B}(\mathbb{R})$. This proves (ii).

Rays. Let $\mathcal{R}=\{(a,\infty):a\in\mathbb{R}\}$ and $\mathcal{R}'=\{(-\infty,a]:a\in\mathbb{R}\}$. Each of these, and likewise $\mathcal{H}$ and $\mathcal{I}$ below, is a set: it is the subclass of the set $\mathcal{P}(\mathbb{R})$ of those $z$ that equal an interval of the stated form for some real, respectively rational, endpoints (with $a<b$ for $\mathcal{H}$), a predicative condition on $z$ as the intervals are defined set symbols given by predicative formulas (Intervals of the Real Line as Defined Set Symbols, Typed Terms and Values of Maps (i)), so a set by Sets and Maps: Ordinary Notation (iii); and $\mathcal{E}=\{\emptyset\}\cup\mathcal{H}$ is then a set by Sets and Maps: Ordinary Notation (iv). Both $\mathcal{R}$ and $\mathcal{R}'$ are contained in $\mathcal{B}(\mathbb{R})$ by (ii), so $\sigma(\mathcal{R}')\subseteq\mathcal{B}(\mathbb{R})$. For $a\in\mathbb{R}$, $(a,\infty)=\mathbb{R}\setminus(-\infty,a]$ by totality of $\le$ (The Real Numbers as a Type (v)), which lies in $\sigma(\mathcal{R}')$ by σ-Algebra and Measurable Space (i); so $\mathcal{R}\subseteq\sigma(\mathcal{R}')$ and $\sigma(\mathcal{R})\subseteq\sigma(\mathcal{R}')$. It remains to show $\mathcal{B}(\mathbb{R})\subseteq\sigma(\mathcal{R})$, for which we verify the hypothesis of (2) for $\mathcal{F}=\sigma(\mathcal{R})$.

Let $b\in\mathbb{R}$, and let $J:\mathbb{N}\to\mathcal{P}(\mathbb{R})$ be the map with $J_{k}=(-\infty,q_{k}]$ if $q_{k}<b$ and $J_{k}=\emptyset$ otherwise (Maps Defined by Cases (i), with $\mathbb{N}$ and $\mathcal{P}(\mathbb{R})$ for its $A$ and $B$ and with $s$ and $b$ among its parameters, as for $W$: the condition is predicative, $\emptyset$ is a defined set symbol, and the ray $(-\infty,q_{k}]$ is the defined set symbol of Intervals of the Real Line as Defined Set Symbols, Typed Terms and Values of Maps (i) at the real number $q_{k}=s(k)_{1}$, itself a defined set symbol used properly). Each $J_{k}$ lies in $\sigma(\mathcal{R})$: $(-\infty,q_{k}]=\mathbb{R}\setminus(q_{k},\infty)$, by totality of $\le$ (The Real Numbers as a Type (v)), lies there by σ-Algebra and Measurable Space (i), and $\emptyset$ by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vi); so $(J_{k})$ is a sequence in $\sigma(\mathcal{R})$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v). Every $J_{k}$ is contained in $(-\infty,b)$, since $y\le q_{k}<b$, and so $y<b$ (The Real Numbers as a Type (v)), for $y\in(-\infty,q_{k}]$ when $q_{k}<b$. If $x<b$, then by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (x) there is $u\in\mathbb{Q}$ with $x<u<b$; with $k\in\mathbb{N}$ such that $s(k)$ is the ordered pair with both coordinates $u$, which exists as $s$ is surjective, we have $q_{k}=u<b$ and $x\in J_{k}$. Hence $(-\infty,b)=\bigcup_{k}J_{k}\in\sigma(\mathcal{R})$ by σ-Algebra and Measurable Space (i). For $q,r\in\mathbb{Q}$ we get $(q,r)=(q,\infty)\cap(-\infty,r)\in\sigma(\mathcal{R})$ by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (ix). By (2), $\mathcal{B}(\mathbb{R})\subseteq\sigma(\mathcal{R})$. Together, $\mathcal{B}(\mathbb{R})\subseteq\sigma(\mathcal{R})\subseteq\sigma(\mathcal{R}')\subseteq\mathcal{B}(\mathbb{R})$, which proves (iii).

Half-open intervals. Let $\mathcal{H}=\{(a,b]:a,b\in\mathbb{R},\ a<b\}$, so that $\mathcal{E}=\{\emptyset\}\cup\mathcal{H}$ for the set $\mathcal{E}$ of the statement. By (ii) and Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vi), $\mathcal{H}\subseteq\mathcal{E}\subseteq\mathcal{B}(\mathbb{R})$; hence $\sigma(\mathcal{E})\subseteq\mathcal{B}(\mathbb{R})$, and $\sigma(\mathcal{H})\subseteq\sigma(\mathcal{E})$ because $\mathcal{H}\subseteq\mathcal{E}\subseteq\sigma(\mathcal{E})$. We verify the hypothesis of (2) for $\mathcal{F}=\sigma(\mathcal{H})$. Let $q,r\in\mathbb{Q}$. If $r\le q$, then no real $x$ satisfies $q<x<r$ (The Real Numbers as a Type (v)), so $(q,r)=\emptyset\in\sigma(\mathcal{H})$ by Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (vi). If $q<r$, let $K:\mathbb{N}\to\mathcal{P}(\mathbb{R})$ be the map with $K_{k}=(q,q_{k}]$ if $q<q_{k}<r$ and $K_{k}=\emptyset$ otherwise (Maps Defined by Cases (i), with $\mathbb{N}$ and $\mathcal{P}(\mathbb{R})$ for its $A$ and $B$ and with $s$, $q$ and $r$ among its parameters, as for $W$: the condition is predicative, $\emptyset$ is a defined set symbol, and the half-open interval $(q,q_{k}]$ is the defined set symbol of Intervals of the Real Line as Defined Set Symbols, Typed Terms and Values of Maps (i) at the real numbers $q$ and $q_{k}=s(k)_{1}$, the latter itself a defined set symbol used properly); each $K_{k}$ lies in $\mathcal{H}$ or is empty, so lies in $\sigma(\mathcal{H})$, and $(K_{k})$ is a sequence in $\sigma(\mathcal{H})$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v). Every $K_{k}$ is contained in $(q,r)$, as $q<y\le q_{k}<r$ gives $q<y<r$ (The Real Numbers as a Type (v)). If $q<x<r$, then by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness (x) there is $u\in\mathbb{Q}$ with $x<u<r$; with $k\in\mathbb{N}$ such that $s(k)$ is the ordered pair with both coordinates $u$, which exists as $s$ is surjective, we have $q<x<u=q_{k}<r$, so $x\in(q,u]=K_{k}$. Hence $(q,r)=\bigcup_{k}K_{k}\in\sigma(\mathcal{H})$ by σ-Algebra and Measurable Space (i). By (2), $\mathcal{B}(\mathbb{R})\subseteq\sigma(\mathcal{H})$, and so $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{H})=\sigma(\mathcal{E})$. This proves (iv).

$\mathcal{E}$ is a set of subsets of $\mathbb{R}$ containing $\emptyset$. Let $A,A'\in\mathcal{E}$. If $A=\emptyset$ or $A'=\emptyset$, then $A\cap A'=\emptyset\in\mathcal{E}$. Otherwise $A=(a,b]$ and $A'=(c,e]$ with $a<b$ and $c<e$; let $m=c$ if $a\le c$ and $m=a$ otherwise, and let $n=b$ if $b\le e$ and $n=e$ otherwise, so that, by totality of $\le$, $m$ is the larger of $a$ and $c$ and $n$ the smaller of $b$ and $e$. For real $x$, $x\in A\cap A'$ if and only if $a<x$, $c<x$, $x\le b$ and $x\le e$, that is, if and only if $m<x\le n$, by totality and transitivity of $\le$ (The Real Numbers as a Type (v)). So $A\cap A'=(m,n]\in\mathcal{H}$ if $m<n$; otherwise $n\le m$ by totality, no real $x$ satisfies $m<x\le n$ (The Real Numbers as a Type (v)), and $A\cap A'=\emptyset$; in both cases $A\cap A'\in\mathcal{E}$. Hence $\mathcal{E}$ is a $\pi$-system on $\mathbb{R}$ by π-System (i). This proves (v).

Rational intervals. Let $\mathcal{I}=\{(q,r):q,r\in\mathbb{Q}\}$. By (ii), $\mathcal{I}\subseteq\mathcal{B}(\mathbb{R})$, so $\sigma(\mathcal{I})\subseteq\mathcal{B}(\mathbb{R})$; and $\mathcal{I}\subseteq\sigma(\mathcal{I})$, so $\mathcal{B}(\mathbb{R})\subseteq\sigma(\mathcal{I})$ by (2). This proves (vi).