0
$\begingroup$

I've been given the following explanation of why the Cantor set is uncountable using base-3 (shortened):

In base-3 we write some arbitrary number $x \in [0,1]$ as $$x = 0.b_1b_2b_3..._3 = \frac{b_1}{3}+\frac{b_2}{3^2}+\frac{b_3}{3^3} +\enspace ...$$ with $b_i \in \left\{0,1,2\right\}$. So we can write $x = \sum_{i=1}^{\infty}b_i3^{-i}$. In this format, the Cantor set has some properties. We divide $[0,1]$ into three equal pieces. The first digit, $b_1$, tells us whether $x$ is in the left, middle or right of a given line segment and so on. Assuming that $\exists$ some $k \in \mathbb{N}$ such that $b_k = 1$ then $x$ will be in some middle third of a given interval so $x \notin \mathcal{C}$. Conversely, by the definition of the base-3 expansion, if $b_n \in \left\{0,2\right\}$ for all $n \in \mathbb{N}$, $x$ will never be in the middle third of any interval, so $x \in \mathcal{C}$

With this formulation of the Cantor set we can easily show that it is uncountable. Suppose instead the opposite, that $\mathcal{C}$ is countable, so $\mathcal{C} = \left\{x^1, x^2, x^3, ...\right\}$ where each element of $\mathcal{C}$ is written like: $$x^1 = 0.b_1^1b_2^1b_3^1..._3$$ $$x^2 = 0.b_1^2b_2^2b_3^2..._3$$ $$x^3 = 0.b_1^3b_2^3b_3^3..._3$$ $$\vdots$$

Here is where I get lost:

Let $\left(b_1,b_2,b_3,...\right)$ be the sequence that differs from the diagonal sequence $\left(b_1^1,b_2^2,b_3^3,...\right)$. $\bf\text{In other words if $b_i^i = 2$ then $b_i = 0$.}$ As a result, $x = 0.b_1b_2b_3..._3$ never appears in $\mathcal{C}$!

Does this mean that because the element composed by this sequence differs at the diagonal every time that it will never equal to any element of $\mathcal{C}$? So we can't write every element of $\mathcal{C}$? Could we also say "if $b_i^i = 0$, then $b_i = 2$?".

$\endgroup$
3
  • 1
    $\begingroup$ Yes, yes, yes. This is the Cantor's diagonal argument $\endgroup$ – Pedro Apr 9 '20 at 12:18
  • $\begingroup$ Does this apply to all uncountably infinite sets? $\endgroup$ – yerman Apr 9 '20 at 12:20
  • 1
    $\begingroup$ Well, it can be used provided that the elements of the set are characterized by infinite sequences. (Diagonalization arguments also appear in different contexts, as in the proof of the Arzelà-Ascoli theorem) $\endgroup$ – Pedro Apr 9 '20 at 12:49
0
$\begingroup$

Yes, yes, yes. This is the Cantor's diagonal argument

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.