How to prove that the Lebesgue $\sigma$-Algebra is not countably generated?

Question

How to prove that there can't exist a countable set $\{A_1,A_2,\dots\}\subset \mathcal{L}(\mathbb{R})$ (where $\mathcal{L}(\mathbb{R})$ denotes the family of all Lebesgue measurable sets) such that $\sigma(\{A_1,A_2,\dots\})=\mathcal{L}(\mathbb{R})$?

(I know that the cardinality of $\mathcal{L}$ is equal to the cardinality of all subsets of $\mathbb{R}$ and hence larger then the cardinality of the borel sets but I'm not familiar with any deeper hierarchy results. Is there a more or less elementary proof?)

Answer 1

Let me mount the kind of cardinality argument to which you allude.

You had asked for a proof that the $\sigma$-algebra of Lebesgue measurable sets is not countably generated. But in fact, a much stronger claim is true:

Theorem. The $\sigma$-algebra of all Lebesgue measurable sets is not generated by any family of size continuum.

Proof. First, I claim that the $\sigma$-algebra generated by any family of size at most continuum itself has size at most continuum. (In particular, every countably generated $\sigma$-algebras have size at most continuum.)

The reason is that we can perform the generation process concretely in a transfinite process of length $\omega_1$. We begin with the generating family, which has size at most continuum. At each stage, we form the next collection by taking all possible countable unions, countable intersections, and complements of what we already have; at limit stages of the process, we gather together all the sets we have formed before that stage. If we began with at most continuum many sets, then since there are only at most continuum many countable subsets of a set of size continuum, it follows that the next stage will also have size at most continuum. And at countable limit stages, we have a countable union of previous families, all of size at most continuum, and so the collection at that stage also has size at most continuum.

By stage $\omega_1$, we have generated the $\sigma$-algebra, since all countable collections from what we have at that stage have already appeared altogether at a countable stage. So we have $\omega_1$ many stages, each with at most size continuum many sets, making the generated family of size at most continuum, which establishes the initial claim.

Second, since every subset of a Lebesgue measure zero set is measurable, and there are sets, such as the Cantor set, which have measure zero and size continuum, it follows that there are $2^{2^{\aleph_0}}$ many Lebesgue measurable sets. This is strictly larger than the continuum, and so by the above it cannot be generated by any family of size at most continuum. $\Box$

Answer 2

We can use the notion of an analytic set to prove that not only that the Borel sets have cardinality continuum but that any countably generated $\sigma$-algebra also has cardinality continuum.

Let $Y$ be a Polish space. Recall that a subset $A\subseteq Y$ is analytic if $A=\emptyset$ or $A=f[\mathbb{N}^\mathbb{N}]$ for some continuous $f:\mathbb{N}^\mathbb{N}\rightarrow\mathbb{R}$. We say that $A\subseteq Y$ is co-analytic if the complement $A^c$ is analytic. There are only continuumly many functions $f:\mathbb{N}^\mathbb{N}\rightarrow Y$, so there are only continuumly many analytic sets.

I claim that the collection $\mathcal{B}$ of subsets $A\subseteq Y$ that are both analytic and co-analytic form a $\sigma$-algebra that contains all closed subsets of $Y$. In fact, the set $\mathcal{B}$ is just the Borel $\sigma$-algebra, but we do not need to prove this fact to conclude that there are continuumly many Borel sets.

If $A_n\subseteq Y$ is analytic and non-empty for each $n\in\mathbb{N}$, then for all $n$, let $f:\mathbb{N}^\mathbb{N}\rightarrow\mathbb{R}$ be a function with $f_n[\mathbb{N}^\mathbb{N}]=A_n$ for all $n$. Then define a function $f:\mathbb{N}^\mathbb{N}\rightarrow Y$ by setting $f((n,a_0,a_1,a_2,a_3,\dots))=f_n(a_0,a_1,a_2,\dots)$. Then $f[\mathbb{N}^\mathbb{N}]=\bigcup_{n=0}^\infty A_n$.

To show that the collection of analytic subsets of $Y$ is closed under countable intersection, we first recall (this is not too hard to prove) that a subset $A\subseteq Y$ is analytic if and only if there is some Polish space $X$ and some continuous $f:X\rightarrow A$. Suppose now that $A_n\subseteq Y$ is analytic and non-empty for each $n$. Then for each $n$, let $X_n$ be a Polish space and let $f_n:X_n\rightarrow Y$ be a continuous function with $f_n[X_n]=A_n$. Then let $X\subseteq\prod_{n\in\omega}X_n$ be the (possibly empty) closed subset consisting of all tuples $(x_n)_{n\in\omega}$ where $f_m(x_m)=f_n(x_n)$ for $m,n\in\omega$. Then define the continuous function $f:X\rightarrow Y$ by letting $f((x_n)_{n=0}^\infty)=f(x_0)$. Then $f[X]=\bigcap_{n=0}^\infty A_n$. Therefore, the countable intersection of analytic subsets is analytic. We may now conclude that the collection $\mathcal{B}$ of analytic and co-analytic sets is a $\sigma$-algebra. The set $\mathcal{B}$ clearly has cardinality at most continuum, so we are good.

Let $Y$ be a set and let $A_n\subseteq Y$ for all $n$. For simplicity, suppose that the sets $A_n$ are separating. Then define a function $\iota:Y\rightarrow 2^\mathbb{N}$ by letting $\iota(y)=\{n\in\mathbb{N}:y\in A_n\}$. Then give $Y$ the coarsest topology such that the mapping $\iota$ is continuous. Then the sets $A_n$ along with the sets $A_n^c$ form a subbasis of clopen subsets of $Y$ that generate the topology on $Y$.

Let $\mathcal{C}$ be the collection of sets of the form $\iota^{-1}[A]$ for some $A\subseteq 2^\omega$ that is both analytic and co-analytic. Then $\mathcal{C}$ is a $\sigma$-algebra containing each $A_n$. Since $2^\omega$ has at most continuumly many analytic sets, the $\sigma$-algebra $\mathcal{C}$ has cardinality at most continuum. Since there are more than continuumly many Lebesgue measurable sets, if $Y=\mathbb{R}$, then $\mathcal{C}$ does not contain all the Lebesgue measurable sets.

Going from the countable case to the continuum case

We have established that if $\mathcal{A}$ is a countably generated $\sigma$-algebra, then $\mathcal{A}$ has cardinality continuum. We can extend this fact to show that every $\sigma$-algebra generated by continuumly many elements has cardinality continuum as well.

Suppose that $Y$ is a set, and $\mathcal{G}$ is a collection of at most continuumly many subsets of $Y$. Then for each $\mathcal{H}\subseteq P(Y)$, let $C(\mathcal{H})$ denote the $\sigma$-algebra generated by $\mathcal{H}$. Then $\bigcup\{C(\mathcal{H}):\mathcal{H}\subseteq\mathcal{G},|\mathcal{H}|\leq\aleph_0\}$ is a $\sigma$-algebra containing $\mathcal{G}$, but since each $C(\mathcal{H})$ has cardinality continuum and there are at most continuumly many countable subsets of $\mathcal{G}$, we conclude that $C(\mathcal{G})$ must also have cardinality continuum.

I think that most people would find the proof using the transfinite inductive construction of the $\sigma$-algebra of length $\omega_1$ to be simpler except if one wants to avoid thinking about the ordinal $\omega_1$ for some reason.

Answer 3

By Hewitt/Stromberg (1965), Real and Abstract Analysis, Theorem (10.23) we have $|\sigma(\cal{E})| \leq |\cal{E}|^{\aleph_0}$, where $|\cal{E}| \geq 2$ and $\cal{E} \subset \cal{P}$$(X)$, $X$ an arbitrary set, $|A|$ the cardinality of a set $A$ and $\sigma(\cal{E})$ the $\sigma$-algebra generated by $\cal{E}$. In particular, if $\cal{E}$ is countable then $\sigma(\cal{E}) \leq \aleph_0^{\aleph_0}$. Let now $X \subset \mathbb{R}$ be Lebesgue-measurable with $\lambda(X) = 0$ and $|X| = \mathbb{R}$, f.i. be the Cantor set, then $\cal{P}$$(X) \subset \cal{L}(\mathbb{R})$ and $\sigma(\{A_1 \cap X, A_2 \cap X, \ldots) = \cal{P}$$(X)$, if $\sigma(A_1, A_2, \ldots) = \cal{L}(\mathbb{R})$, a contradiction.