### Archive

Posts Tagged ‘convergence’

## Countable Intersections and Unions of Sets: A Discussion on an Example in Williams “Probability with Martingales”

As homework for students, I recently set the task of understanding the Example/Warning in Section 1.11 of Williams’ book “Probability with Martingales“. I provide here my own ‘solution’ to this homework exercise. There is no need to refer to Williams’ book as the following is self-contained.

Let $V = \{v_1,v_2,\cdots\}$ be the set of rational numbers between 0 and 1 inclusive; because the rational numbers are countable, they can be enumerated as $v_1,v_2,\cdots$. Define the sets $I_{n,k} = (v_n - \frac1{k2^n},v_n+\frac1{k2^n}) \cap [0,1]$. Here, $(v_n-\frac1{k2^n},v_n+\frac1{k2^n})$ is the open interval of width $\frac1{k2^{n-1}}$ centred at the rational number $v_n$, and intersecting it with the closed interval $[0,1]$ simply eliminates any “end effects” by keeping all sets within $[0,1] \subset \mathbb{R}$. For a fixed $n$, note that $I_{n,k}$ monotonically decreases to $\{v_n\}$ as $k \rightarrow \infty$. In particular, $\cup_{n=1}^\infty \cap_{k=1}^\infty I_{n,k} = V$.

Of interest is what the set $H = \cap_{k=1}^\infty \cup_{n=1}^\infty I_{n,k}$ looks like. A straightforward calculation shows $H \supset V$, but do you think $H = V$, or $H = [0,1]$, or something else?  Is $\sqrt{2}-1 \in H$?

For any finite $N$ and $K$$\cap_{k=1}^K \cup_{n=1}^N I_{n,k} = \cup_{n=1}^N \cap_{k=1}^K I_{n,k}$.  Believing this to continue to hold in the limit as $N,K \rightarrow \infty$ is a flawed argument for $H=V$.  (Note: normally, union and intersection cannot be interchanged, but here, the sets $I_{n,k}$ are decreasing in $k$. In particular, $\cap_{k=1}^K I_{n,k} = I_{n,K}$.) To see the difference between the finite and infinite cases, note that $x$ being an element of $\cap_{k=1}^K \cup_{n=1}^N I_{n,k}$ means precisely that $\forall k$, $\exists n_k$ such that $x \in I_{n_k,k}$.  Here, a subscript $k$ adorns $n$ to emphasise that the choice of $n$ is allowed to depend on $k$. That $x$ is an element of $\cup_{n=1}^N \cap_{k=1}^K I_{n,k}$ means precisely that $\exists n$, $\forall k$, $x \in I_{n,k}$.  The key difference is that here, a single $n$ must work for all $k$.  In the finite case, the choice $n_k = n_K$ works for all $k$. If $K$ is infinite though, there is no such thing as $n_\infty$ that could serve in place of $n_K$.

A flawed argument for $H = [0,1]$ can be based on the denseness of rationals: every $x \in [0,1]$ is the limit of a sequence of rational numbers, and since $\cup_n I_{n,k}$ contains not only every rational number, but also a neighbourhood of every rational number, it “must” therefore contain all numbers in $[0,1]$. It is insightful to understand where the flaw is.  Let $x \in [0,1]$ be an irrational number. Let $i_1 < i_2 < \cdots$ be an increasing sequence of indices such that $v_{i_1},v_{i_2},\cdots \rightarrow x$. Whether $x \in \cap_k \cup_n I_{i_n,k}$ depends on which is faster: the convergence of $v_{i_n} \rightarrow x$, or the convergence of $\frac1{k2^{i_n}} \rightarrow 0$. To illustrate, assume that $|v_{i_n} - x | = \frac1{2^n}$. (For pedants, interpret this equality as approximate equality; the difference between a rational and irrational number cannot exactly equal a rational number.) Then even though $v_{i_n} \rightarrow x$, the convergence is sufficiently slow that $x \notin I_{i_n,k}$ for all $k$. (Note $2^n \geq 2^{i_n}$ because $i_n \geq n$.)

The pendulum swings back: perhaps then $H = V$ because no sequence can converge sufficiently quickly to an irrational number? To demonstrate that this is false, consider the following procedure for choosing $v_1,v_2,\cdots$ to ensure that $\sqrt{2}-1 \in H$. It suffices to construct a sequence $v_1,v_3,v_5,\cdots$ that converges quickly to $\sqrt{2}-1 \in H$ because the remaining rational numbers can be assigned (in arbitrary order) to $v_2,v_4,v_6,\cdots$.  Simply choose $v_n$, for $n$ odd, to be a rational number within $\frac1{n2^n}$ of $\sqrt{2}-1$.  (This can always be arranged by taking sufficiently many terms in the decimal expansion $0.414214\cdots$ of $\sqrt2-1$.) Then, no matter how large $k$ is chosen, $\sqrt2-1 \in I_{n,k}$ when $n$ is an odd number greater than $k$, hence $\sqrt2-1 \in H$.

The above has already demonstrated that limits cannot be interchanged; a sequence $v_1,v_2,\cdots$ of rational numbers was constructed such that $\sqrt2-1$ is in $H$ and hence $H \neq V$. This is not the argument used by Williams, but being constructive in nature might mean it is a more transparent argument.

The higher-level argument in Williams’ book reveals more information about $H$.  Williams uses the Baire category theorem to deduce that $H$ must be uncountable, hence $H \supsetneq V$ regardless of how $v_1,v_2,\cdots$ are chosen. Furthermore, the Lebesgue measure of $H$ is easily shown to be zero, therefore, $H$ does not contain any open intervals, and in particular $H \subsetneq [0,1]$. (Proof: the Lebesgue measure of $I_{n,k}$ is at most $\frac1{k2^{n-1}}$.  Since $\sum_{n=1}^\infty \frac1{2^{n-1}} = 2$, the Lebesgue measure of $\cup_n I_{n,k}$ is at most $\frac2k$.  As $k \rightarrow \infty$, this goes to zero, hence the measure of $H$ must be zero.)

For completeness, the fact that $H$ is uncountable will be derived. The trick is to consider the complement $H^c = [0,1] \setminus H$. If it can be shown that the complement $H^c$ is “too small” then $H$ must be uncountable.  De Morgan’s law implies that $H^c = \cup_{k=1}^\infty \left( \cup_{n=1}^\infty I_{n,k} \right)^c$.   (Exercise: prove from first principles that $\left( \cap_{k=1}^\infty G_k \right)^c = \cup_{k=1}^\infty G_k^c$.)  Let $F_n = \left( \cup_{n=1}^\infty I_{n,k} \right)^c$.  Since $\cup_{n=1}^\infty I_{n,k}$ contains all the rational numbers, $F_n$ can contain only irrational numbers.  In particular, $F_n$ does not contain any open interval. Each $I_{n,k}$ is open and hence $\cup_{n=1}^\infty I_{n,k}$ is open. Thus, $F_n$ is a closed set not containing any open intervals. Such sets are called nowhere dense. Since $H^c$ is the countable union of nowhere dense sets, it is a meagre set. If $H$ is countable then it too would be meagre, and hence $H \cup H^c$ would be meagre. Yet $H \cup H^c = [0,1]$, and $[0,1]$ is a Baire space, meaning meagre sets are “small”.  In particular, the whole space $[0,1]$ cannot be meagre, a contradiction.  Therefore, $H$ must be uncountable.

The conclusion then is that $H$ depends on the actual ordering $v_1,v_2,\cdots$ of the rationals, yet regardless of how the rationals are ordered, $H$ will be an uncountable set of Lebesgue measure zero. In particular, $V \subsetneq H \subsetneq [0,1]$.