# If $S$ is an infinite $\sigma$ algebra on $X$ then $S$ is not countable

I am going over a tutorial in my real analysis course and there is an exercise that I don't understand a part of his solution.

The exercise is:

Let $S$ be an infinite $\sigma$ algebra on $X$ .Prove that $S$ is not countable.

The proof given is:

Assume by negation $S=\{A_{i}\}_{i=1}^{\infty}$. For each $x\in X$ define $B_{x}:=\cap_{x\in A_{i}}A_{i}$. Note that $B_{x}\in S$ since this is a countable intersection.

Claim: If $B_{x}\cap B_{y}\neq\emptyset$ then $B_{x}=B_{y}$.

Proof:

If $z\in B_{x}\cap B_{y}$ then $B_{z}\subseteq B_{x}\cap B_{y}$. If $x\not\in B_{z}$then $B_{x}\setminus B_{z}$ is a set in $S$ containing $x$ and is strictly contained in $B_{x}$, in contradiction to the definition of $B_{x}$.

Hence $B_{z}=B_{x}$and similarly $B_{z}=B_{y}$ hence $B_{x}=B_{y}$.

Now consider $\{B_{x}\}_{x\in X}$ - If there is a finite sets of the form $B_{x}$ then $S$ is a union of a finite number of disjoint sets hence it is finite. We conclude there is an infinite number of sets of the form $B_{x}$. $\cup_{i\in A}B_{x_{i}}$ where $A\subseteq\mathbb{N}$ is of at least cardinality $\aleph$.

There are couple of things I don't understand in this proof:

1. Why the fact that we found a set ($B_{x}\setminus B_{z}$) in $S$ containing $x$ and is strictly contained in $B_{x}$ a contradiction ?

2. Why if there are only a finite number of different sets of the form $B_{x}$ then $S$ is a union of a finite number of disjoint sets and is finite ?

-
You may find it helpful to think about the case where the $\sigma$-algebra $S$ separates points; i.e. for every $x,y \in X$ there exists $A \in S$ with $x \in A$, $y \notin A$. In this case, $B_x = \{x\}$, and the problem reduces to showing that the discrete $\sigma$-algebra on an infinite set is uncountable. – Nate Eldredge Mar 4 '13 at 2:36

1. Because $B_x$ is supposed to be the intersection of all measurable sets containing $x$, but you've found a measurable set containing $x$ strictly inside $B_x$.

2. Because for any measurable set $T$, we have $T=\bigcup_{x\in T}B_x$. Thus, if there are $n$ distinct sets of the form $B_x$, then there are at most $2^n$ elements of $S$.

-
Thanks Zev! ${}$ – Belgi Mar 4 '13 at 1:44
No problem, glad to help! – Zev Chonoles Mar 4 '13 at 1:45
Could someone explain why we must have strict containment? I see how it's possible, but what if nothing is removed ? – NS248 May 26 '14 at 5:49

One can actually change the argument of @Josef slightly to obtain a correct proof. This is probably also what @ncmathsadist is hinting at, although he does not indicate how to obtain the countably infinite collection of disjoint subsets.

Incidentially, the argument below even shows that an infinite $\sigma$-algebra is not only uncountable, but it has at least the cardinality of the continuum.

Let $(A_n)_{n \in \Bbb{N}}$ be a sequence of pairwise distinct (not necessarily disjoint) sets in $S$.

For an arbitrary subset $M \subset X$ let $M^1 := M$ and $M^{-1} := M^c$.

For a sequence $\omega = (\omega_n)_{n} \in \{\pm 1\}^\Bbb{N}$, define

$$B^\omega := \bigcap_{n \in \Bbb{N}} A_n^{\omega_n}.$$

Observe that $B^\omega \in A$, because it is a countable intersection of elements of $A$.

ALso note that $B^\omega \cap B^\gamma = \emptyset$ for $\gamma = (\gamma_n)_n \neq \omega$, because there is some $n$ such that $\gamma_n \neq \omega_n$, so that

$$B^\omega \cap B^\gamma \subset A_n^{\omega_n} \cap A_n^{\gamma_n} = \emptyset.$$

Finally, note that for $n \in \Bbb{N}$ arbitrary, we have (why?)

$$A_n = \bigcup_{\omega \text{ with } \omega_n = 1} B^\omega .$$

Hence, if the set $\{B^\omega \mid \omega \in \{\pm 1\}^\Bbb{N} \}$ where finite, it would easily follow that there could only be finitely many distinct $A_n$, a contradiction.

Hence, there is an infinite family $\omega^{(n)}$ with $B^{\omega^{(n)}} \neq B^{\omega^{(m)}}$ for $n \neq m$.

Let $C_n := B^{\omega^{(n)}}$. By discarding (at most) one set, we can assume $C_n \neq \emptyset$ for all $n$. Using the pairwise disjointness of the $C_n \neq \emptyset$, it is now easy to see that the map

$$\Gamma : \{0,1\}^\Bbb{N} \to A, (\alpha_n) \mapsto \biguplus_{n \text{ with } \alpha_n = 1} C_n$$

is injective, because

$$\Theta : A \to \{0,1\}^\Bbb{N}, M \mapsto \left(n \mapsto \begin{cases} 1, & \text{if }M\cap C_{n}\neq\emptyset\\ 0, & \text{if }M\cap C_{n}=\emptyset \end{cases} \right)$$

is a left inverse for $\Gamma$.

-

Warning: the following proof is incorrect!

As ncmathsadist mentioned before, there is also a direct prove. For those who want to know how to proceed:

Let be $\mathcal{S}$ an infinite $\sigma$-Algebra. Take any pairwise distinct sets $A_1,A_2,\ldots\in\mathcal{S}$. Then \begin{align*}G_0&=A_0^\complement\cap A_1\cap A_2\cap A_3\cap\cdots,\\ G_1&=A_0\cap A_1^\complement\cap A_2\cap A_3\cap\cdots,\\ G_2&=A_0\cap A_1\cap A_2^\complement\cap A_3\cap\cdots,\\ \vdots\end{align*} all lie in $\mathcal{S}$, because the countable intersection is closed in $\sigma$-Algebras, and it is easy to see, that they are pairwise disjoint. But also the countable and finite union of any collection of the $G_k’s$ must lie in $\mathcal{S}$.

You will recognise, that for distinct collections, you’ll get different unions (because the $G_k$’s are pairwise disjoint). Wich Collection you choose, you can encode with a binary sequence $a_0,a_1,a_2,\ldots$ by setting $a_k=1$ for taking $G_k$ into the collection and $a_k=0$ otherwise. So you get an injection from $\{0,1\}^\mathbb{N}$ to $\mathcal{S}$. But you already know, that $\{0,1\}^\mathbb{N}$ is an uncountable set. And that’s why $\mathcal{S}$ must also be uncountable.

-
Thanks. I like this direct proof. – NS248 May 25 '14 at 21:20
Joseph, can you point out, why all but finitely many Gi s are not empty? – Somabha Mukherjee Aug 11 '14 at 17:01
They aren't, if $A_0$ and $A_1$ happen to to be disjoint, then $G_3,G_4,...$ are all empty. – bringingdownthegauss Sep 17 '14 at 3:11
@bringingdownthegauss You are right, my proof is incomplete. But I see no way to correct it. It seems, that there is no other way to proof it as the questioner did. What should I do with an incorrect answer in stackexchange? – Josef Sep 24 '14 at 17:38
@Josef: Below, I have indicated a variant of your argument, which yields a correct proof. – PhoemueX Oct 17 '14 at 22:05

Proof by picture:

Take a collection of finitely many disjoint elements of the sigma algebra. Then the picture below shows gives some intuition as to why one can always add a element to this set of pairwise dijoint sets.

Once you have a infinite collection of pairwise disjoint sets one can identify each of these as distinct elements where unions of sets are also distinct. So by taking all countable unions on this collection one would generate a set with uncountably many elements as it is the power set of a countable set.

-
How do we know we don't get stuck in choosing some finite family of sets that happens to cover everything, making the choice of the "next" element impossible? – hardmath Oct 4 '14 at 15:35
Easy, we have an infinite collection of sets in our $\sigma$ algebra. There are only a finite number of sets that can be unions of sets from our collection $2^k$ for a collection of k disjoint sets. Thus we can find a set that is not the union of these sets and thus it's complement intersected with a set in the collection and itself intersected with a set are nonempty and disjoint. – asd Oct 4 '14 at 15:43
But even if we have an infinite collection of sets, a finite number of them might cover the union of all of them. While a $k$ cardinality family of disjoint subsets form only a finite number of unions, and we can pick a subset distinct from these, that doesn't show the one we pick will not be contained in their union. – hardmath Oct 4 '14 at 15:51
I think I might understand your concern. The idea the picture is meant to convey is not quite "adding" but "carving" instead. If some set A is contained in their union but not equal to their union for some subcollection then it follows that $A^\complement \cap B_n$ is non-empty which is in the σ algebra and disjoint with $A \cap B_n$ also being in the $\sigma$ algebra. Now of course we have to replace the sets containing some part of A with their respective intersection with the complement of A, and intersection with A. – asd Oct 4 '14 at 16:23

Show that if a $\sigma$-algebra is infinite, that it contains a countably infinite collection of disjoint subsets. An immediate consequence is that the $\sigma$-algebra is uncountable.

-
Can you explain that a little more please? – Twink Feb 24 '14 at 1:40
What is the cardinality of the power set of a countably infinite set? – ncmathsadist Sep 12 '14 at 13:19
$2^{\mathbb{N}}$? – Badshah Sep 20 '14 at 14:46