Countable and Co-Countable Sets

Exercise 1 - Analysis, Measure and Probability

The most conservative collection of ‘manageable’ sets is

\[\mathcal{M} = \{\{x\} ; x \in \mathbf{X} \}\]

the singleton subsets of $\mathbf{X}$. Let

\[\mathcal{C} := \{\mathbf{C} \subset \mathbf{X}; \text{either } \mathbf{C} \text{ is countable, or } \mathbf{X}\setminus \mathbf{C} \text{ is countable} \}\]

Show that $\mathcal{C} = \sigma(\mathcal{M})$, the sigma-algebra of countable and co-countable sets.

Proof:

Let $A \in \mathcal{C}$. Then, either $A \subset \mathbf{X}$ is countable or $\mathbf{X} \setminus A$ is countable. If $A$ is countable, then

\[A = \bigcup_{x \in A} \{x\} \in \sigma(\mathcal{M})\]

since $\sigma(\mathcal{M})$ is closed under countable unions. If $A$ is not countable, then $\mathbf{X} \setminus A$ is countable.

\[A = \bigcap_{x \in \mathbf{X} \setminus A} \mathbf{X} \setminus \{x\} \in \sigma(\mathcal{M})\]

since $\sigma(\mathcal{M})$ is closed under countable intersections. Hence, $ \mathcal{C} \subseteq \sigma( \mathcal{M})$. Next, suppose that $A \in \sigma(\mathcal{M})$. Then, there exists a countable number of subsets $U_n \subset \mathbf{X}$ such that

\[A = \bigcup_{n=1}^{\infty} U_n\]

but $U_n = {x_n}$ for some $x \in \mathbf{X}$. Hence, $A$ is countable and thus $\sigma(\mathcal{M}) \subseteq \mathcal{C}$. Therefore, $ \mathcal{C} = \sigma( \mathcal{M})$.