I want to do three things:
- 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\;$,
- 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
- 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?
Best Answer
A set $A$ is in $\mathscr{A}_n$ iff $A \subseteq \{1,\ldots n\}$ or $X\setminus A \subseteq \{1,\ldots,n\}$. This is just the definition of $\mathscr{A}_n$.
$A \in \mathscr{A}:= \bigcup_n \mathscr{A}_n$ iff $\exists n: A \in \mathscr{A}_n$ iff $\exists n: A \subseteq \{1,\ldots, n\} \text{ or } X\setminus A \subseteq \{1,\ldots,n\}$ iff $A$ is finite or $A$ is cofinite (i.e. has finite complement )
Now, $A_k = \{2k\}$ for $k \in \mathbb{N}$ is in $\mathscr{A}_{2k} \subseteq \mathscr{A}$, but the union of the $A_k$ is the set of even numbers $E$ which is not in $\mathscr{A}$ by the above criterion: it's neither finite nor cofinite. So $\mathscr{A}$ is indeed not a $\sigma$-algebra, exactly for the reason claimed.