Archive

Posts Tagged ‘convergence’

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

October 19, 2013 Leave a comment

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].

Advertisements