The union of a strictly increasing sequence of $\sigma$-algebras is not a $\sigma$-algebra

The union of a sequence of $\sigma$-algebras need not be a $\sigma$-algebra, but how do I prove the stronger statement below?

Let $\mathcal{F}_n$ be a sequence of $\sigma$-algebras. If the inclusion $\mathcal{F}_n \subsetneqq \mathcal{F}_{n+1}$ is strict, then the union $\bigcup_{n=1}^{\infty}\mathcal{F}_n$ is not a $\sigma$-algebra.

-
Do you know this to be the case? I ask, because I believe I have a simple counterexample (consider $\Omega = \mathbb{N}$). But, I'm quite rusty. – cardinal Mar 14 '11 at 13:35
Hint: For every $n$, there exists a set $A_n$ such that $A_n \in \mathcal{F}_n \setminus \mathcal{F}_{n-1}$. – cardinal Mar 14 '11 at 15:32
@joriki, please feel free to post an answer. Don't limit your participation on my behalf! Unfortunately, I won't have time to post anything substantive today at the very least. I'd want to do more careful checking of my attempt anyway. – cardinal Mar 15 '11 at 11:32
@gylns Sorry to be blunt but did you actually accept @Jonas's answer? You might have noticed the consensus amongst @joriki, @cardinal, @Jonas himself and me that there is still work to do on @Jonas's idea (or on any other) to reach a proof. – Did Mar 16 '11 at 13:19
Yes, I suggest to de-accept it. – Jonas Teuwen Mar 16 '11 at 20:19

This is not a complete solution as is indicated in the comments. Joriki's addition is also important. For complete solution, see A. Broughton and B. W. Huff: A comment on unions of sigma-fields. The American Mathematical Monthly, 84, no. 7 (1977), 553-554. (Thanks Didier for the reference)

The idea is to find a sequence of pairwise disjoint sets $F_n$ in $\mathcal F_{n + 1} \setminus \mathcal F_n$ and then prove that $F_n$ must actually be an element of $\mathcal F_n$ if $\mathcal F = \bigcup_n \mathcal F_n$ were a $\sigma$-algebra.

First pick a partition $N_1, N_2,\ldots$ of infinite sets of $\mathbb N$ and set

$$A_i = \bigcup_{n \in N_i} F_n.$$

So, by assumption $A_i$ is an element of $\mathcal F$. So, for every $i$ we have an $n_i$ such that $A_i \in \mathcal F_{n_i}$. Now, note that since $(\mathcal F_n)$ is strictly increasing, so we can choose $(n_i)$ to be strictly increasing as well.

Okay, nice. So now for every $j$ we can pick an integer $m_j \in N_j$ such that $m_j > n_j$. So now we set

$$B = \bigcup_n \, F_{m_n} \in \mathcal F.$$

So, eventually (for large $n$) $B$ will belong to all $\mathcal F_n$. So, eventually $B$ is in some $\mathcal F_{n_k}$(since $n_i$ is strictly increasing). By construction we now have that

$$A_k \cap B = A_{m_k} \in \mathcal F_{n_k}.$$

But! $n_k < m_k$ so $A_{m_k} \notin \mathcal F_{n_k}$. Contradiction.

So, now what is left is to show that such a disjoint sequence exists. Well, that is quite messy, so I will only add it if you want.

I would like to add that this is not my idea but that I have got the idea from somewhere in the past, but I forgot exactly where from.

-
I don't see why $(\mathcal{F_n})$ strictly increasing implies $n_i$ strictly increasing. If I understand correctly, the $N_i$ are arbitrary infinite sets without any particular relationship to each other -- then why should the $n_i$ bear any particular relationship to each other? – joriki Mar 15 '11 at 17:09
BTW, you didn't introduce the notation $\mathcal{F}=\bigcup_{n=1}^\infty\mathcal{F}_n$. – joriki Mar 15 '11 at 17:12
@joriki, $A_i$ is a sequence of sets and $A_i \in \mathcal{F}_{m(i)}$ for some mapping $m : \mathbb{N} \to \mathbb{N}$. Then, via a subsequence, I believe you can take the $n_i$ to be strictly increasing. Let $m(i) = \min\{j: A_i \in \mathcal{F}_j\}$. This is well defined by the assumptions and the construction. Define $n_i$ inductively. Let $n_1 = m(1)$, $n_i = (n_{i-1}+1) \vee m(i)$ for $i \geq 2$. I think there are other (possible) holes in the argument, though. The role of $\mathcal{F}_n$ does not appear to be clearly established, for example. – cardinal Mar 15 '11 at 17:30
If the sequence $(n_k)$ is bounded, then $B$ may not be in any $\mathcal F_{n_k}$, and you can't conclude that $A_k \cap B = F_{m_k} \in \mathcal F_{n_k}$ – mercio Mar 15 '11 at 17:32
@Jonas: You definitely should indicate clearly in your post that it is not a complete solution. // For a solution, see A. Broughton and B. W. Huff: A comment on unions of sigma-fields. The American Mathematical Monthly, 84, no. 7 (1977), 553-554. – Did May 25 '12 at 14:29

I want to do three things:

1. give a counterexample to Jonas' lemma that there is necessarily a sequence of pairwise disjoint sets $F_n\in\mathcal{F}_{n+1}\setminus\mathcal{F}_n\;$,
2. show that there is however a sequence of pairwise disjoint sets $G_{k}\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}$ for some strictly increasing sequence $n_k$ (so Jonas' proof still works), and
3. offer an alternative proof of the main statement, which also uses this modified lemma.

As a counterexample to the unmodified lemma, consider $\mathcal{F}_1=\{\emptyset,[0,6]\}$ and $\mathcal{F}_2$, $\mathcal{F}_3$ and $\mathcal{F}_4$ the $\sigma$-algebras generated by adding $[0,3]$, $[1,2]$ and $[4,5]$ respectively, to their predecessors. (To extend this to a strictly increasing sequence of $\sigma$-algebras, we can keep adding arbitrary intervals with new boundaries, e.g. $[2^{-n}/2,2^{-n}]$). If we choose $[0,3]$ as $F_1$, there are no new sets in $\mathcal{F}_3$ that are disjoint from it, and if we choose its complement instead, the same is true for $\mathcal{F}_4$.

So the best we can hope for is a sequence of pairwise disjoint sets $G_k\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}$ for some strictly increasing sequence $n_k$: Then we can form a new sequence of strictly increasing $\sigma$-algebras, $\mathcal{G}_k:=\mathcal{F}_{n_k}$, and then $G_k\in\mathcal{F}_{n_k+1}\setminus\mathcal{F}_{n_k}\subseteq\mathcal{G}_{k+1}\setminus\mathcal{G}_k$ will be a disjoint sequence as desired, and we can prove the claim for $\mathcal{G}=\bigcup G_k=\mathcal{F}$ without loss of generality. Thus, Jonas' proof will remain substantially intact. So let's show that there is such a sequence.

It's not clear (to me) from the question whether the $\mathcal{F}_n$ all have the same underlying set, so I'll first show that we can assume that they do without loss of generality. Each $\mathcal{F}_n$ contains its underlying set as an element, so the union $U$ of all these underlying sets is a countable union of elements of $\mathcal{F}$, and hence in $\mathcal{F}$, and hence in some $\mathcal{F}_{n_0}$. So all $\mathcal{F}_n$ after that have the same underlying set $U$, and without loss of generality we can drop the initial ones that don't.

Since the $\mathcal{F}_n$ are strictly increasing, we can choose some (not necessarily pairwise disjoint) sequence of sets $F_n\in\mathcal{F}_{n+1}\setminus\mathcal{F}_n$. (We need the axiom of countable choice to do that, but I suspect it would be difficult to impossible to prove any of this without some form of choice, so I won't worry about that in the following.)

Let's say $F_n$ is distinctive in $A\in\mathcal{F}_n$ if $F_n\cap A\notin\mathcal{F}_n$. This also implies $\overline{F_n}\cap A\notin\mathcal{F}_n$, since $\overline{\overline{F_n}\cap A}\cap A=(F_n\cup\overline{A})\cap A=F_n\cap A$. Also, if $F_n$ is distinctive in $A$ and $B\in\mathcal{F}_n$, then $F_n$ is distinctive in $A\cap B$ or in $A\cap \overline{B}$, for otherwise $F_n\cap A\cap B\in\mathcal{F_n}$ and $F_n\cap A\cap\overline{B}\in\mathcal{F_n}$ and thus $(F_n\cap A\cap B)\cup(F_n\cap A\cap\overline{B})=(F_n\cap A)\cap(B\cup\overline{B})=F_n\cap A\in\mathcal{F}_n$. (Since we're working within a single underlying set $U$, the complements are well-defined.)

Now let $n_0=0$ and $V_0=U$ and, by induction, construct a strictly increasing sequence $n_k$ together with sets $V_k$ and $G_k$ such that $V_k,G_k\in\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$ and $V_k,G_k\subseteq V_{k-1}$ for all $k\in\mathbb{N}$, that $G_k$ is disjoint from $G_j$ for all $k>j$, that $V_k$ is disjoint from $G_j$ for all $k\ge j$, and that for all $k$ infinitely many $F_n$ are distinctive in $V_k$.

There are no disjointness conditions to fulfill for $k=0$, so we merely have to note that infinitely many (namely all) of the $F_n$ are distinctive in $V_0=U$ (since $F_n\cap U=F_n\notin\mathcal{F}_n$) to get the induction off the ground. Then, assuming that $V_k$ and $G_k$ have the above properties for all $k<m$, take $n_m$ to be the first integer greater than $n_{m-1}$ such that $F_{n_m}$ is distinctive in $V_{m-1}$. This integer exists since infinitely many $F_n$ are distinctive in $V_{m-1}$. Consider $F_{n_m}$ and $\overline{F_{n_m}}$, which is also in $\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$. Every $F_j$ with $j>n_m$ that is distinctive in $V_{m-1}$ is distinctive in at least one of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$. Since there are infinitely many such $F_j$, we can choose $V_m$ to be one of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$ such that infinitely many $F_j$ are distinctive in $V_m$. Take $G_m$ to be the other of $V_{m-1}\cap F_{n_m}$ and $V_{m-1}\cap\overline{F_{n_m}}$. Since $V_{m-1}$, $F_{n_m}$ and $\overline{F_{n_m}}$ are all in $\mathcal{F}_{n_m+1}$, so are $V_m$ and $G_m$, and since $F_{n_m}$ is distinctive in $V_{m-1}$, neither $V_m$ nor $G_m$ is in $\mathcal{F}_{n_m}$. Thus $V_m,G_m\in\mathcal{F}_{n_m+1}\setminus\mathcal{F}_{n_m}$ as required. Also, since $V_{m-1}$ is disjoint from all $G_j$ with $j\le m-1$, i.e. $j<m$, so are $V_m$ and $G_m$, and $V_m$ is also disjoint from $G_m$, and hence from all $G_j$ with $j\le m$. That completes the induction, and thus the proof of the modified lemma, since the $G_k$ and $n_k$ for $k\in\mathbb{N}$ have the desired properties.

Now for the proof that I originally had in mind before I got sidetracked by the disjointness issue :-) It's similar in spirit to Jonas' proof in that it makes use of the fact that in cramming the uncountably many combinations of the $G_k$ into the countable sequence of the $\mathcal{G_k}$, one must invariably get ahead of oneself and generate some $G_k$ that wasn't supposed to be there yet.

Since the $G_k$ are disjoint, all their (finite and countably infinite) unions are distinct, and thus in one-to-one correspondence with (finite and countably infinite) binary strings, where a $1$ digit means that the corresponding $G_k$ is included in the union and a $0$ digit means that it isn't. All these unions must be in $\mathcal{G}$ if it is to be a $\sigma$-algebra. In particular, $G:=\bigcup G_k$ must be in $\mathcal{G}$, and thus in some $\mathcal{G}_{k_0}$. Without loss of generality, we can drop the $G_k$ with $k<k_0$ and assume that $G$ is in $G_1$, so that we can always form complements $\overline{G_k}\cap G$ in $G$, which corresponds to inverting all the digits in the corresponding string.

Now let's first try to derive a contradiction by trying to construct one of the $G_k$ in $\mathcal{G}_k$. To do this, we start with $G$ and first remove all $G_j$ for $j<k$ (which we can, since they are all in $\mathcal{G}_k$). Now assume that for each $j>k$ there is one of the above unions in $G_k$ such that its $j$-th digit differs from its $k$-th digit. If the $k$-th digit is $1$, we take the set itself, if it is $0$, we take its complement in $G$, thus inverting its digits. Then in either case the $k$-th digit is $1$ and the $j$-th digit is $0$ (since they differ by assumption). Now we can remove all $G_j$ for $j>k$ by intersecting with all these sets, leaving only $G_k$ and thus yielding the desired contradiction $G_k\in\mathcal{G}_k$. Thus, contrary to our assumption, there must be some $j>k$ such that the $j$-th and $k$-th digits coincide for all unions in $\mathcal{G}_k$, and this must be the case for all $k$.

This we can use to derive another contradiction, using a diagonal argument and forming a binary string as follows: Starting with $n_1=1$, in each step we choose $n_{i+1}>n_i$ such that the $n_{i+1}$-th and $n_i$-th digits coincide for all unions in $\mathcal{G}_{n_i}$, and we choose the $n_{i+1}$-th digit of the binary string being constructed such that it differs from the $n_i$-th digit. (The remaining digits can be chosen arbitrarily.) Then the union corresponding to this string is in none of the $\mathcal{G}_{n_i}$, and thus in none of the $\mathcal{G}_k$, and thus not in $\mathcal{G}$. This contradiction completes the proof.

Now one question remains: Either of the proofs (if we add the part about a pairwise disjoint sequence to Jonas' proof) is unlikely to be what whoever assigned the homework had in mind -- so is there a simpler proof?

-
Nice! And thanks for fixing my proof. I'll edit it and refer to yours for the lemma. – Jonas Teuwen Apr 4 '11 at 16:24
I think your argument that all $\sigma$-algebras live wlog on the same set is not quite correct. Let $\mathcal{F}_n$ be the power-set of $[0,n]$. Then there is no $n_0$ such that $\bigcup_n\bigcup\mathcal{F}_n\subseteq\mathcal{F}_{n_0}$. – Michael Greinecker May 11 '12 at 9:03
@Michael: Perhaps I hadn't made it sufficiently clear that, like Jonas' proof, this is a proof by contradiction that starts from the assumption that $\mathcal F$ is a $\sigma$-algebra. My proof for the underlying set uses that assumption, and your counterexample violates it (as in fact any counterexample must, since $\mathcal F$ is never a $\sigma$-algebra :-). – joriki Nov 26 '12 at 5:02
@joriki I see now. I thought the proof enters the contradictory la la land at a later stage. But I think the proof is, except for an intermediate step, semi-constructive. For each $\sigma$-algebra $\mathcal{U}\supseteq\bigcup_n\mathcal{F}_n$, you find an element $G\in\mathcal{U}\backslash\bigcup_n\mathcal{F}_n$. – Michael Greinecker Nov 26 '12 at 7:35