Cantor set to show that the Borel measure is not complete 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 ?
 A: 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 :


*

*$\mathcal A_0$ is the collection of all subsets of $\mathbb R$ that are either open or closed.

*For a successor ordinal $\alpha+1,$ $\mathcal A_{\alpha+1}$ is the collection of all sets that are either a countable union of sets in $\mathcal A_\alpha,$ or the complement of a countable union of sets in $\mathcal A_\alpha.$

*For a limit ordinal $\lambda,$ $\mathcal A_\lambda = \bigcup_{\alpha<\lambda} \mathcal A_\alpha.$


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


*

*$\mathcal A_0\subseteq \mathcal B.$

*If $\mathcal A_\alpha \subseteq \mathcal B,$ then $\mathcal A_{\alpha+1}\subseteq \mathcal B.$

*If $\lambda$ is a limit ordinal and $\mathcal A_\alpha \subseteq \mathcal B$ for all $\alpha<\lambda,$ then $\mathcal A_\lambda \subseteq \mathcal B.$


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 


*

*$|\mathcal A_0| = 2^{\aleph_0}$.

*If $|\mathcal A_\alpha| = 2^{\aleph_0},$ then $|\mathcal A_{\alpha+1}| = 2^{\aleph_0}.$

*If $\lambda$ is a limit ordinal and $|\mathcal A_\alpha| = 2^{\aleph_0}$ for all $\alpha < \lambda,$ then $|\mathcal A_\lambda| = 2^{\aleph_0}.$


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}.$ 
