# Proving that $\mathcal{S} = \{E\subset X: E \text{ is countable or } X\setminus E \text{ is countable}\}$ is the smallest $\sigma$-algebra

Suppose $$X$$ is a set and $$\mathcal{A}$$ is the set of subsets of $$X$$ that consist of exactly one element: $$\mathcal{A} = \{\{x\}:x \in X\}.$$ Prove that the smallest $$\sigma$$-algebra on $$X$$ containing $$\mathcal{A}$$ is the set of all subsets $$E$$ of $$X$$ such that $$E$$ is countable or $$E^c$$ is countable.

To prove this, I first want to show that $$\mathcal{S}$$ is a $$\sigma$$-algebra where $$\mathcal{S} = \{E\subset X: E \text{ is countable or } X\setminus E \text{ is countable}\}.$$

My question: I've already shown that $$\mathcal{S}$$ is a $$\sigma$$-algebra. Now, I think I need to show that $$\mathcal{A}$$ is contained in $$\mathcal{S}$$. How can I show this (since both $$\mathcal{A}$$ and $$\mathcal{S}$$ are sets of sets)? So, how can $$\mathcal{A}$$ be contained in $$\mathcal{S}$$? Also, lastly, I think I need to show that $$\mathcal{S}$$ is the intersection of all $$\sigma$$-algebras on $$X$$ that contain $$\mathcal{A}$$. Can someone show how this can be proven?

• $\mathcal A$ is contained in $\mathcal S$ means $\mathcal A \subseteq \mathcal S$. You can proceed with the smallest $\sigma$-algebra part by showing that any $\sigma$-algebra containing $\mathcal A$ must contain $\mathcal S$. Commented Mar 10, 2021 at 17:17
• @IzaakvanDongen To show that $\mathcal{A}\subset\mathcal{S}$, I have: Let $P\in\mathcal{A}$. Then $P=\{x\}$ for some $x\in X$. Since $P$ is finite, and hence countable, $P\in\mathcal{S}$. Is this all that was needed to show that $\mathcal{A}\subset\mathcal{S}$? Commented Mar 10, 2021 at 17:24
• Yes, that's exactly right! Commented Mar 10, 2021 at 17:26
• @Ricky_Nelson That works, but that's not the interesting part of the proof. What you need to show is that if $\mathcal A\subset\mathcal M$, and $\mathcal M$ is a $\sigma$-algebra, then $S\subset\mathcal M$. Commented Mar 10, 2021 at 17:26
• @DonThousand Can you please elaborate on how this can be shown? Also, according to your argument, would we not need to show that $\mathcal{A}\subset\mathcal{S}$? Commented Mar 10, 2021 at 17:31

As you said you have already proved that $$\mathcal{S} = \{E\subseteq X: E \text{ is countable or } X\setminus E \text{ is countable}\}$$ is in fact a $$\sigma$$-algebra.

Now, we have $$\mathcal{A} = \{\{x\}:x \in X\}$$ and let us prove that the smallest $$\sigma$$-algebra containing $$\mathcal{A}$$ is equal to $$\mathcal{S}$$.

Since for each $$x \in X$$ , $$\{x\}$$ is countable, we have that $$\mathcal{A} \subseteq \mathcal{S}$$.

Since $$\mathcal{S}$$ is a $$\sigma$$-algebra, it follows that $$\sigma(\mathcal{A}) \subseteq \mathcal{S} \tag{1}$$ where $$\sigma(\mathcal{A})$$ is the smallest $$\sigma$$-algebra containing $$\mathcal{A}$$ (the $$\sigma$$-algebra generated by $$\mathcal{A}$$).

Now let us prove that $$\mathcal{S} \subseteq \sigma(\mathcal{A})$$.

We will begin by proving the claim:

Every countable set $$F\subseteq X$$ is in $$\sigma(\mathcal{A})$$.

Proof of the claim: Since for every $$x \in X$$ , $$\{x\} \in \mathcal{A} \subseteq \sigma(\mathcal{A})$$ and every countable set $$F\subseteq X$$ is a countable union of single-point sets, we have that $$F \in \sigma(\mathcal{A})$$ (because $$\sigma(\mathcal{A})$$ is a $$\sigma$$-algebra). So, every countable subset of $$X$$ is in $$\sigma(\mathcal{A})$$ . $$\square$$

Now, for any $$E \in \mathcal{S}$$, we have two possibilities:

1. $$E$$ is countable. In this case, it follows directly from the claim that $$E \in \sigma(\mathcal{A})$$.
2. $$X\setminus E$$ is countable. In this case, it follows directly from the claim that $$X\setminus E \in \sigma(\mathcal{A})$$. Since $$\sigma(\mathcal{A})$$ is a $$\sigma$$-algebra, we have $$X\setminus(X\setminus E) \in \sigma(\mathcal{A})$$. But $$X\setminus(X\setminus E) =E$$, so we have $$E \in \sigma(\mathcal{A})$$.

So, in both cases, we have that $$E \in \sigma(\mathcal{A})$$. So, we have:

$$\mathcal{S}= \{E\subseteq X: E \text{ is countable or } X\setminus E \text{ is countable}\} \subseteq \sigma(\mathcal{A}) \tag{2}$$

From $$(1)$$ and $$(2)$$, $$\sigma(\mathcal{A}) = \mathcal{S}$$ It means, the smallest $$\sigma$$-algebra containing $$\mathcal{A}$$ is equal to $$\mathcal{S}$$.

• Thanks for your answer! One question: how does $X\setminus E$ being countable imply that $X\setminus E \in \sigma(\mathcal{A})$? (This is right above (2) in your answer.) Commented Mar 10, 2021 at 23:38
• @Ricky_Nelson Just before that sentence, we have proved that : "Now, since for every $x \in X$ , $\{x\} \in \mathcal{A} \subseteq \sigma(\mathcal{A})$ and every countable set $E\subseteq X$ is a countable union of single-point sets, we have that $E \in \sigma(\mathcal{A})$ (because $\sigma(\mathcal{A})$ is a $\sigma$-algebra). " So, every countable set is in $\sigma(\mathcal{A})$. Commented Mar 11, 2021 at 0:52
• @Ricky_Nelson I have updated the answer to include more details. Please, take a look and let me know if you have any further question. Commented Mar 11, 2021 at 1:17
• Makes perfect sense now, thanks so much! Commented Mar 11, 2021 at 1:17