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

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?

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 = F_{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.