I have been thinking about the $\sigma$-field generated by a system $S$ as the limit of a series of $\sigma$-operations such as complements and countable unions. Such a recursive procedure for generating $\sigma(S)$ fails to generate all the required sets when, as I tacitly imagined, it is applied only countably many times.
This can be seen by means of a clever diagonal argument which involves constructing a bijection between the sets thus generated and the real unit interval. The gist of the proof is that when we only use countably many recursive steps, we can enumerate the resulting sets by means of sequences of integers, and this leaves the construction open to a diagonal counterexample.
The Playing Field
Let's first agree on a canonical defition of the Borel field $\mathcal{B}$ over $(0,1]$: For the present purposes, we will identify it as the $\sigma$-field generated by the intervals with rational endpoints, including the empty set.This seed set $S$ is countable and can therefore be enumerated, for instance as
$\emptyset$, $(0,1]$, $(0,\frac{1}{2}]$, $(\frac{1}{2},1]$, $(0,\frac{1}{3}]$, $(\frac{1}{3},\frac{1}{2}]$, $(\frac{1}{3},1]$, $(0,\frac{1}{4}]$, $(\frac{1}{4},\frac{1}{3}]$, $(\frac{1}{4},\frac{1}{2}]$, …For the purposes of this argument, let's further restrict the permitted $\sigma$-operations to
- complementation;
- countable unions.
$$
\Psi(A_1,A_2,A_3,A_4,\ldots)\;=\; A_1^c \cup A_2 \cup A_3 \cup A_4 \cup \ldots
$$to a countable sequence of sets. We can then translate
\begin{eqnarray}
A^c &=& A^c \cup \emptyset \cup \emptyset \cup \emptyset \cup \emptyset \ldots \\
\cup_{i=1}^{\infty}A_i &=& \emptyset \cup A_1 \cup A_2 \cup A_3 \cup \ldots
\end{eqnarray}Any $\sigma$-operation is then a matter of applying $\Psi$ to some countable sequence of sets.
The Elements of Construction
This allows us to describe our inductive procedure in terms of a recursive function $R$ that uses $\Psi$ as a subroutine. We define the base case as a projection:$$
R_0(A_1,A_2,A_3,\ldots) \;=\; A_1.
$$In order to define the recursion step, we first need to recall that $\mathbb{N}$ and $\mathbb{N}\times \mathbb{N}$ are equipotent, as can be seen from the following array:
$$
\begin{array}{ccccc}
1 & 2 & 4 & 7 & \ldots \\
3 & 5 & 8 & 12 & \ldots \\
6 & 9 & 13 & 18 & \ldots \\
10 & 14 & 19 & 25 & \ldots \\
\vdots & \vdots & \vdots & \vdots &
\end{array}
$$This array can be used to map a countable sequences of sets onto a countable sequence of countable sequences. We use this unraveling trick for the recursive step:
$$
R_n(A_1,A_2,\ldots) \;=\; \Psi( R_{n-1}(A_1,A_2,A_4,\ldots), R_{n-1}(A_3,A_5,A_8,\ldots), \ldots )
$$This way, we can, by a careful selection of rational intervals $A_1,A_2,A_3,\ldots$, select any countable sequence of $R_{n-1}$-sets we like and feed that sequence into a new $\Psi$-construction.
This trick, then, transforms a sequence of rational intervals into an $R_n$-set. In other words, any level $n$ set can be obtained in a (nominally) single step by feeding an appropriate sequence of level 0 sets into the recursive function $R_n$.
From Sequences to Sets
We now finally put$$
R(A_1,A_2,\ldots) \;=\; R_1(A_1,A_2,\ldots) \cup R_2(A_3,A_5,\ldots) \cup R_3(A_6,A_9,\ldots) \cup \ldots
$$This format covers all sets that can be obtained by any finite level of recursion.
For instance, if a set can be produced by level 17 recursion, we can choose the sequence $A_1,A_2,A_3,\ldots$ so that all $R_i$ except $R_{17}$ return the empty set, while $R_{17}$ returns the set we are interested in. This is achieved by constructing the sequence $A_1,A_2,A_3,\ldots$ so that it splits into just the right subsequences.
In other words, we now have a method for picking out any set that requires only finite recursion by specifying an appropriate sequence of rational intervals. Since there are only countably many rational intervals, the selection of a specific finite-level recursive set is therefore a matter of selecting an appropriate sequence of natural numbers.
Stone to Stone
The set of countably infinite sequences of positive integers is equipotent with the real unit interval.Specifically, Billingsley suggests that we use the bijection $b$ which for its $k$th integer takes the distance between the $(k-1)$st and the $k$th occurrence of the digit 1 in the binary expansion of the number $\omega\in(0,1]$.
Under this bijection,
$$
b\left(\frac{1}{3}\right) \;=\; b\left(.010101\ldots\right) \;=\; (2,2,2,2,\ldots).
$$For this definition to work, there has to be infinitely many 1s in the binary expansion. This can be guaranteed by always choosing the non-terminating binary expansion of $\omega$, so that, for instance,
$$
b\left(\frac{1}{2}\right) \;=\; b\left(.111111\ldots\right) \;=\; (1,1,1,1,\ldots).
$$Incidentally, this choice also fixes the ambiguity problems we might otherwise have, making $b$ a true bijection.
Because of the construction above, the output of this function can be fed into another function that translates the infinite sequences of integers into an infinite sequence of rational intervals, which is then translated into a recursive set. In other words, we can map any real number $\omega\in(0,1]$ onto a finite-recursion set $s(\omega)$. This establishes a surjection of the real numbers into the system of sets that can be obtained by finitely many $\sigma$-operations on the rational intervals.
The Diagonal
The set we now need for our diagonal counterargument is$$
B = \{\omega\in (0,1]: \omega \not\in s(\omega)\}.
$$This set cannot be obtained by finite application of $\sigma$-operations to the rational intervals.
If it could, there would be at least one $\omega_0\in (0,1]$ such that $B=s(\omega_0)$. But by construction, $\omega_0\in s(\omega_0)$ holds if and only if $B\not \in s(\omega_0)$; so $B$ and $s(\omega_0)$ must disagree at least about the element $\omega_0$ and possibly about others. This contradicts the assertion that $B=s(\omega_0)$. Hence, $B$ cannot be obtainable by a finite number of recursive operations.
On the other hand, $B$ is a Borel set. Billingsley gives a complicated argument for this which is a notational nightmare, but I think he is just expressing a proof by induction.
Proof Sketch
The first step of the argument introduces a building block called $D_k$. This is the set of real numbers that are members of $A_k(\omega)$, the $k$th interval on their own list. For instance, $\omega=1/3$ is mapped onto the constant interval list$$
(0,1], (0,1], (0,1], (0,1], \ldots
$$since $b(1/3)=(2,2,2,\ldots)$, and $(0,1]$ is the second interval on the list. It thus follows that $1/3\in A_k(1/3)$ for all $k$, and thus $1/3 \in D_k$ for all $k$.
The sets $D_k$ are Borel sets. This follows from the fact that the set of binary numbers with a specific $k$th waiting time is a Borel set, and that any rational interval is a Borel set.
The second part of the argument uses a translation between the set
$$
R_n(A_{m_1}(\omega), A_{m_2}(\omega), A_{m_3}(\omega), \ldots)
$$and the set
$$
R_n(D_{m_1}, D_{m_2}, D_{m_3}, \ldots)
$$for an arbitrary integer sequence $m_1, m_2, m_3, \ldots$. This equality is proven by induction.
Using this translation, the set $B^c = \{\omega\in s(\omega)\}$ can then be rewritten as a countable union of sets of this form. This shows that $B$ is indeed a Borel set, since the $D_k$ are.
No comments :
Post a Comment