I would like to use the Cantor set to illustrate the fact that the Borel measure is not complete.
To do so, I saw different sources (wiki and math.stackexchange, if I understood well) using the cardinality of the power set of the Cantor set which is greater than the cardinality the power set of the Borel sets. Therefore, there is necessary at least one subset of the Cantor set that is not a Borel set.
I found this nice. But now, I would like to prove this inequality between the power sets cardinality. How would you do that ?
Best Answer
The hard part is proving the cardinality of the set of all Borel sets is only $2^{\aleph_0}.$ There is a proof of this fact by transfinite induction that can be found in a lot of places. (You start with the open and closed sets of which there are clearly $2^{\aleph_0}$-many, then you show you can iteratively construct the set of Borel sets from this in $\omega_1$ steps, each time adding only $2^{\aleph_0}$ more sets.)
Then, if you can prove the easier fact that the Cantor set has cardinality $2^{\aleph_0},$ then you know the set of subsets of the Cantor set has cardinality $2^{2^{\aleph_0}},$ which by Cantor’s theorem is greater than $2^{\aleph_0}.$
EDIT - More detailed sketch of the proof as requested.
The Borel $\sigma$-algebra $\mathcal B$ is the smallest $\sigma$-algebra on $\mathbb R$ containing all the open sets. A $\sigma$-algebra on $\mathbb R$ is a collection of subsets of $\mathbb R$ that is closed under complements and countable unions.
Intuitively, we can think about starting with all the open sets and their complements (i.e. the closed sets). Clearly these are Borel sets, but will not be all of them because there are countable unions of closed sets that are neither open nor closed (for instance, half-open intervals are Borel, but we don't have them in our collection yet since they are neither open nor closed). So we can add to our collection all countable unions of open and closed sets and then add in complements of all of these in attempt to get a $\sigma$-algebra. But do we succeed? In other words, is this resulting collection closed under countable unions? It turns out it is not.
So we need to keep repeating this procedure of adding new Borel sets given by countable unions of what came before and their complements. Will it eventually close, and if so, how many iterations will it take?
The answer is that it will close, but even an infinite number of iterations is not enough. We need to iterate it through all countable ordinals, in other words up to the first uncountable ordinal $\omega_1.$
We can define a sequence $\mathcal A_\alpha$ of collections of subsets of $\mathbb R$ by transfinite recursion as follows :
The claim is that $\mathcal B = \mathcal A_{\omega_1}.$
Now that we have a recursive definition, we can use induction to prove things about this sequence. The first thing we can show is that for all $\alpha,$ $ \mathcal A_\alpha \subseteq \mathcal B.$ Well, we won't show it, I will leave it as an exercise for you. The way to do it is to show the following three things using the recursive definition above
Once you're done with that, you have proven $A_{\omega_1}\subseteq \mathcal B,$ which is one direction of the equality.
To prove the other direction, first observe that we only need to show that $A_{\omega_1}$ is a $\sigma$-algebra containing all open sets (why?) and the part about containing all open sets is trivial. So we must show it is a $\sigma$-algebra, i.e. that it is closed under countable unions and complements.
The complements part is easy. Observe that if $X\in \mathcal A_{\omega_1},$ then $X\in \mathcal A_\beta$ for some ordinal $\beta < \omega_1$ (by the recursive definition, using the fact that $\omega_1$ is a limit ordinal). Then observe that by our definition, each $\mathcal A_\beta$ is closed under complements. (You can prove this by transfinite induction if it is not obvious. And even we didn't know $A_\beta$ was closed under complements, if you follow the definition, it is clear the complement of any $X\in \mathcal A_\beta$ will get picked up in stage $\beta+1,$ since $X^c$ is the complement of a countable union of sets in $\mathcal A_{\beta}.$)
Now we need to show closure under countable unions, so let $X_i\in \mathcal A_{\omega_1}$ for $i=1,2,\ldots,$ and let $X=\bigcup_{i=1}^\infty X_i.$ We need to show $X\in \mathcal A_{\omega_1}.$ This is where we discover why we need to iterate up through $\omega_1.$ Or, rather, where you discover this, cause I'm leaving this part as an exercise too. The key fact about $\omega_1$ you need is that any sequence $\alpha_1,\alpha_2,\ldots $ of countable ordinals is bounded in $\omega_1.$ In other words, there is an ordinal $\beta < \omega_1$ that has $\beta > \alpha_i$ for all $i\in \mathbb N.$
Then once you're done with that, you have shown $\mathcal A_{\omega_1} = \mathcal B.$ Now you can prove $|\mathcal A_{\omega_1}| = 2^{\aleph_0}.$ By transfinite induction (how else?). Show
The hard part should be the second part, where you have to show that the collection of all countable unions of a collection of $2^{\aleph_0}$-many sets has cardinality $2^{\aleph_0}.$
Now, you have shown $|\mathcal A_\alpha| = 2^{\aleph_0}$ for all $\alpha<\omega_1.$ And that does it. $\mathcal A_{\omega_1} = \bigcup_{\alpha < \omega_1} \mathcal A_{\alpha},$ so cardinal arithmetic gives $$ |\mathcal A_{\omega_1}| \le \omega_1 \cdot 2^{\aleph_0} = 2^{\aleph_0},$$ since $\omega_1 \le 2^{\aleph_0}.$