1
$\begingroup$

I recently had an exam where I had to prove the uncountability of the Cantor set $\mathcal{C}$. I produced a proof which I thought surely would be the classic proof, but to my surprise I can't seem to find this argument anywhere online after a couple of searches. The proof demonstrates an injection $f: \{0, 1\}^\mathbb{N} \to \mathcal{C}$ (where $\{0, 1\}^\mathbb{N}$ is the set of infinite bitstrings).

Notations: Denote by $C_n$ to be the "approximation" of the Cantor set after the $n$th iteration. For example, $C_0 = [0,1]$, $C_1 = [0, 1/3] \cup [2/3, 1]$, $C_2 = [0, 1/9] \cup [2/9, 1/3] \cup [2/3, 7/9] \cup [8/9, 1]$, and so on.

Let $b$ be any finite bitstring. Denote the last bit of $b$ as $b^{-1}$, and denote the bitstring obtained by omitting the last bit of $b$ as $b_{-1}$. For example, $(011011)^{-1} = 1$ and $(011011)_{-1} = 01101$. Also define the function $$ C(b) = \begin{cases} [0, 1] & \text{if } b = \epsilon \text{, the empty bitstring} \\ \text{(closed) left third of } C(b_{-1}) & \text{if } b^{-1} = 0 \\ \text{(closed) right third of } C(b_{-1}) & \text{if } b^{-1} = 1 \end{cases} $$ For example, $C_{01}$ denotes the right third of the left third of $C(\epsilon) = [0,1]$, namely $C_{01} = [2/9, 1/3]$. It can be seen that for any input of length $n$, $C$ returns a unique disjoint interval that constitutes $C_n$ (where $C_n$, as in the lecture, is the resulting set of intervals after the $n$th iteration of the Cantor procedure).

Finally, we define some notation for infinite bitstrings. Let $i$ be an infinite bitstring. Denote its first $n$ bits as $i_n$. For example, $(10110 \cdots)_2 = 10$.

The Injection: Define $f$ as the following, which takes in an infinite bitstring $i$: $$f(i) = \bigcap_{n \in \mathbb{N}} C(i_n)$$ Intuitively, this function can be thought of consuming an infinite bitstring, and starting at $[0,1]$, it "hops" to the left third of the current interval if the current bit examined is zero, and "hops" to the right third of the current interval if the current bit examined is one.

What Must be Shown: It seems to me that two things must be shown:

  1. $f$ always returns a real number in the Cantor set.

  2. $f$ is injective.

To show the first, note that $f(i)$ an intersection of (descending) non-empty nested intervals, and thus by the nested interval theorem, there is a non-trivial intersection. As each $C(i_n)$ is a subset of $C_n$, it follows that $f(i)$ contains only members of the Cantor set. Finally, each of the nested intervals is one-third the length of the previous, so there is only one real number contained in $f(i)$, for any infinite bitstring $i$.

To show the second, suppose we have two infinite bitstrings $i$ and $j$ with $i \neq j$. Let $n$ be the first bit in which they differ (by assumption, $n$ must be finite, or else $i = j$). WLOG, assume that the $n$th bit of $i$ is 0, and the $n$th bit of $j$ is 1. By definition of $C$, $C(i_n)$ is the left third of $C(i_{n - 1})$, while $C(j_n)$ is the right third of $C(j_{n - 1})$. By assumption, $i_{n - 1} = j_{n - 1}$, so it follows that $C(i_n)$ and $C(j_n)$ are the left and right third, respectively, of the same interval $C(i_{n - 1})$. In particular, they must be disjoint. However, by definition of $f$, $f(i)$ must be an element of $C(i_n)$, while $f(j)$ must be an element of $C(j_n)$. Since $C(i_n) \cap C(j_n) = \emptyset$, it follows that $f(i) \neq f(j)$. Hence, $f$ is injective.

Questions:

  1. Is this construction correct?

  2. This construction is similar, but definitely not the same, as the classic proof of $\mathcal{C}$'s uncountability. If this proof is correct, is there a reason it's not commonly phrased this way (and instead phrased using ternary numbers and such)?

$\endgroup$
1
  • 1
    $\begingroup$ One very similar approach is to instead convert each sequence of bits into a sequence of points in the Cantor set. At each step, we take the left endpoint of either the first or second closed interval obtained from the last one. So $(0,0,1,1,\ldots)$ becomes $(0,0,\frac{2}{27},\frac{8}{81},\ldots)$. It is clear from construction that the resulting sequence is bounded and increasing, hence convergent. Since $C$ is closed, the limit is automatically in $C$. $\endgroup$
    – pancini
    Oct 16, 2020 at 19:27

1 Answer 1

1
$\begingroup$

Your argument is correct. It is actually a special case of an argument used to show that if $S$ is a closed subset of a complete metric space, and $S$ has no isolated points, then $|S|\ge 2^\omega=\mathfrak{c}$, so in particular $S$ is uncountable.

As you say, it is very similar to the argument using ternary representations: those representations correspond in a natural way to your binary sequences. One reason for introducing the ternary representations is that they are useful when one wants to work with the actual numerical values of the points of the Cantor set. Another might be that they are likely to be a bit more familiar to many students than the purely topological reasoning that you employed — or at least a bit less unfamiliar.

You might be interested in the answers to this question, which give several different proofs of the uncountability of the Cantor set. For instance, I gave one that is essentially a topological version of the diagonal argument.

$\endgroup$
4
  • $\begingroup$ Thanks for the insights and the references! Can you explain the notation $2^\omega$ and $\mathfrak{c}$? $\endgroup$
    – paulinho
    Oct 16, 2020 at 20:57
  • $\begingroup$ @paulinho: Both are standard notations for the cardinality of $\Bbb R$; another is $2^{\aleph_0}$. Does that help, or should I say more? $\endgroup$ Oct 16, 2020 at 21:08
  • $\begingroup$ I figured as much, but does $\omega$ mean anything by itself? Does it refer to the cardinality of the natural numbers? $\endgroup$
    – paulinho
    Oct 16, 2020 at 22:03
  • $\begingroup$ @paulinho: It’s the smallest infinite ordinal and hence the smallest infinite cardinal, so yes, $|\Bbb N|=\omega=\aleph_0$. I take (well-orderable) cardinals to be the initial ordinals, i.e., the ordinals that are the smallest of any given cardinality. Assuming the axiom of choice, these are all of the cardinals. (Without the axiom of choice there can also be cardinals that are not well-ordered and hence are not ordinals, but $\Bbb N$ is well-ordered, so its cardinality is as well.) $\endgroup$ Oct 16, 2020 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .