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 be the set of rational numbers between 0 and 1 inclusive; because the rational numbers are countable, they can be enumerated as . Define the sets . Here, is the open interval of width centred at the rational number , and intersecting it with the closed interval simply eliminates any “end effects” by keeping all sets within . For a fixed , note that monotonically decreases to as . In particular, .
Of interest is what the set looks like. A straightforward calculation shows , but do you think , or , or something else? Is ?
For any finite and , . Believing this to continue to hold in the limit as is a flawed argument for . (Note: normally, union and intersection cannot be interchanged, but here, the sets are decreasing in . In particular, .) To see the difference between the finite and infinite cases, note that being an element of means precisely that , such that . Here, a subscript adorns to emphasise that the choice of is allowed to depend on . That is an element of means precisely that , , . The key difference is that here, a single must work for all . In the finite case, the choice works for all . If is infinite though, there is no such thing as that could serve in place of .
A flawed argument for can be based on the denseness of rationals: every is the limit of a sequence of rational numbers, and since contains not only every rational number, but also a neighbourhood of every rational number, it “must” therefore contain all numbers in . It is insightful to understand where the flaw is. Let be an irrational number. Let be an increasing sequence of indices such that . Whether depends on which is faster: the convergence of , or the convergence of . To illustrate, assume that . (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 , the convergence is sufficiently slow that for all . (Note because .)
The pendulum swings back: perhaps then because no sequence can converge sufficiently quickly to an irrational number? To demonstrate that this is false, consider the following procedure for choosing to ensure that . It suffices to construct a sequence that converges quickly to because the remaining rational numbers can be assigned (in arbitrary order) to . Simply choose , for odd, to be a rational number within of . (This can always be arranged by taking sufficiently many terms in the decimal expansion of .) Then, no matter how large is chosen, when is an odd number greater than , hence .
The above has already demonstrated that limits cannot be interchanged; a sequence of rational numbers was constructed such that is in and hence . 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 . Williams uses the Baire category theorem to deduce that must be uncountable, hence regardless of how are chosen. Furthermore, the Lebesgue measure of is easily shown to be zero, therefore, does not contain any open intervals, and in particular . (Proof: the Lebesgue measure of is at most . Since , the Lebesgue measure of is at most . As , this goes to zero, hence the measure of must be zero.)
For completeness, the fact that is uncountable will be derived. The trick is to consider the complement . If it can be shown that the complement is “too small” then must be uncountable. De Morgan’s law implies that . (Exercise: prove from first principles that .) Let . Since contains all the rational numbers, can contain only irrational numbers. In particular, does not contain any open interval. Each is open and hence is open. Thus, is a closed set not containing any open intervals. Such sets are called nowhere dense. Since is the countable union of nowhere dense sets, it is a meagre set. If is countable then it too would be meagre, and hence would be meagre. Yet , and is a Baire space, meaning meagre sets are “small”. In particular, the whole space cannot be meagre, a contradiction. Therefore, must be uncountable.
The conclusion then is that depends on the actual ordering of the rationals, yet regardless of how the rationals are ordered, will be an uncountable set of Lebesgue measure zero. In particular, .