20
$\begingroup$

What are the ways of proving that the Cantor set is uncountable apart from Cantor diagonalization? Are there any based on dynamical systems?

  • 8
    I don't know to what Cantor diagonalization you're referring here: the only proof I know that the Cantor set is uncountable uses writing elements in base 3 and then an onto function. Cantor Diagonalization is used to show that the set of all real numbers in $\,[0,1]\,$ is uncountable.2012-12-04
  • 0
    Some proofs are listed in the book "Measure and Category" by Oxtoby.2012-12-04
  • 2
    @DonAntonio given the "base 3" definition of the Cantor set, isn't a (direct) diagonalization the easiest way to show that it is uncountable?2012-12-04
  • 0
    I can't say, @TrevorWilson, but I don't see it that clear right now. It surely would surprise me if it were "simply" that because I haven't seen this, but of course I can't say is impossible.2012-12-05
  • 5
    @DonAntonio I just mean that the diagonal argument showing that the set of $\{0,2\}$-sequences is uncountable is exactly the same as the one showing that the set of $\{0,1\}$-sequences is uncountable. So introducing the interval $[0,1]$ only complicates things (as far as diagonal arguments are concerned.)2012-12-05
  • 0
    Oh, I see now what you mean...hehe. Yes, of course2012-12-05

7 Answers 7

27

Exercise: Show that Cantor set $C$ is equal to $$C = \left\{\sum_{n=1}^\infty \frac{a_n}{3^n}: a_n \in \{0, 2\}\right\}$$

Then:

One way to intuitively understand the cardinality of the Cantor set is to think of it as essentially the set of ternary (base 3) representations of all $x\in [0, 1] \subset \mathbb{R}$ which can be expressed using only the digits 0 and 2. That is, it is the set of all "trecimal expansions” of $x\in [0, 1] \subset \mathbb{R}$ that consist of of only zeros and twos: e.g. $0.0 \bar{0}_{\text{ base 3}} = 0 \in C, \; 0.2\bar{2}_{\text{ base 3}} = 1\in C,\;\; 0.2020202020202…_\text{(base 3)} \in C \;$, etc.

The set of all such $x$ is uncountable:
There are $2^{|\mathbb{N}|}$ distinct sequences consisting of only zeros and twos: for each $n\in \mathbb{N}$, there are two possible choices for any given $a_n : 0$ or $2$. Since there are uncountably many distinct sequences $\{a_n\} \in \{0, 2\}^\mathbb{N}$, there are uncountably many series $\large\sum {a_n\over 3^n}$, each of which represents a single point in the Cantor set.

Hence there are uncountably many points in the Cantor Set.

  • 0
    This is the most simplest, clearest and correct answer. I would upvote it, but I ran out of votes today ;)2012-12-04
  • 0
    thank you. Please post any different method (may be from some other field of mathematics) if you know. It is very difficult to find for me.2012-12-11
  • 10
    I don’t see how this answers the question. You haven’t avoided diagonalisation here — you’ve just emphasised other parts of the proof, and then skimmed quickly through the step that relies on diagonalisation (i.e. the step “Since there are uncountably many distinct sequences $\{a_n\} \in \{0,2\}^\mathbb{N}$, …”).2013-10-02
19

Instead of the diagonal proof directly, we can adapt Cantor's first proof of uncountability. Let $C$ be the cantor set, and let $E=\{u_1, u_2, \dots\}$ be a countable set. We construct a point of $C$ not in $E$. First, $C \subseteq [0,1/3]\cup [2/3,1]$, and point $u_1$ does not belong to both of those intervals, so there is an interval $I_1$ of length $1/3$ (one of the ones in the first stage of the construction of the Cantor set) with $u_1 \not\in I_1$. Now when we remove the middle third of $I_1$ we get two intervals of length $1/3^2$. As before, $u_2$ does not belong to both of these intervals, so there is an interval $I_2 \subset I_1$ of length $1/3^2$ (one of the ones in the second stage of the construction of the Cantor set) with $u_2 \not\in I_2$. Continue in this way to get $I_1 \supset I_2 \supset I_3 \supset \dots \supset I_k \supset \dots$ where $I_k$ has length $3^{-k}$ (one of the intervals in the $k$th stage of the construction of the Cantor set) and $u_k \not\in I_k$. Finally, we get a point $x \in \bigcap_{k=1}^\infty I_k$ where $x \in C$ but $x \ne u_k$ for all $k$.

  • 0
    I didn't understand how you said u_2 does not belong to both of these intervals. Can you please explain this ?2015-12-14
  • 0
    The two intervals are disjoint, so $u_2$ can belong to at most one of them.2015-12-14
  • 0
    Okie, you get existence of 'x' using Cantor intersection theorem and then x is not equal to any of u_k because x=u_k implys u_k belongs to I_k, which will be contradiction to our construcion of I_k. Did I got it right ?2015-12-15
17

You can use the ol' Baire Category argument: as a closed subspace of $\mathbb{R}$, the Cantor set is completely metrizable (the usual metric is complete) and is thus a Baire space. Therefore the Cantor set is not a countable union of nowhere-dense subsets. As the Cantor set is perfect, the singletons are nowhere dense (in the Cantor set), and so the Cantor set cannot be countable.

  • 1
    I have to admit that I fail to follow your argument. For example, $\mathbb N$ is a closed subset of $\mathbb R$ but somehow your argument doesn't apply there.2012-12-04
  • 2
    @MartinArgerami: An important point is that the singletons in $\mathbb{N}$ are not nowhere dense (they are open in the subspace).2012-12-04
  • 0
    Good point. Nice.2012-12-04
6

In the spirit of Arthur's answer, let's take some tools from a more advanced part of mathematics.

Theorem 1. Every countable and complete metric space is homeomorphic to a countable ordinal with the order topology.

Theorem 2. Every ordinal space contains isolated points. Furthermore, if the ordinal is infinite then there are infinitely many isolated points.

The Cantor space is compact and therefore complete with the metric induced by $\mathbb R$. If the Cantor space was countable then it would be isomorphic an ordinal and would therefore have isolated points. However the Cantor space does not have any isolated points, and therefore cannot be countable.

4

$\newcommand{\cl}{\operatorname{cl}}$Let $C$ be a Cantor set, and let $f:\Bbb N\to C$ be any function. For $n\in\Bbb N$ let $a_n=f(n)$, and let $A=\{a_n:n\in\Bbb N\}$.

Claim: $A\ne C$.

Since $A$ is an arbitrary countable subset of $C$, it follows from the claim that $C$ is uncountable.

Proof of Claim: Clearly $C$ is infinite, so there is some $x\in C\setminus\{a_0\}$. $C$ is $T_4$, so there is an open nbhd $V_0$ of $x$ such that $a_0\notin\cl V_0$. Suppose that for some $n\in\Bbb N$ we have a non-empty open set $V_n$ such that $\{a_k:k\le n\}\cap\cl V_n=\varnothing$. If $a_{n+1}\notin\cl V_n$, let $V_{n+1}=V_n$. Otherwise, use the fact that $C$ has no isolated points to fix $x\in V_n\setminus\{a_{n+1}\}$, and choose an open nbhd $V_{n+1}$ of $x$ such that $\cl V_{n+1}\subseteq V_n\setminus\{a_{n+1}\}$. In this way we recursively construct open sets $V_n$ such that for $n\in\Bbb N$, $\cl V_{n+1}\subseteq V_n$ and $\{a_k:k\le n\}\cap V_n=\varnothing$. It follows from the compactness of $C$ that $$\bigcap_{n\in\Bbb N}\cl V_n\ne\varnothing\;,$$ but clearly $$A\cap\bigcap_{n\in\Bbb N}\cl V_n=\varnothing\;,$$ so $A\ne C$. $\dashv$

3

Use a fat Cantor set, and show that it has positive Lebesgue measure. Then, remember that all countable sets are null.

  • 0
    All this shows is that the fat Cantor set is uncountable, no?2015-11-29
  • 0
    @Soke but then there is a natural bijection between any cantor subsets of an interval, so they all are of the same cardinality.2015-11-30
2

The canonical proof that the Cantor set is uncountable does not use Cantor's diagonal argument directly. It uses the fact that there exists a bijection with an uncountable set (usually the interval $[0,1]$).

Now, to prove that $[0,1]$ is uncountable, one does use the diagonal argument. I'm personally not aware of a proof that doesn't use it.

  • 1
    You can construct a bijection between $[0,1]$ and $\mathbb{R}$ in more than one way...2012-12-04
  • 0
    And do you know a proof that $\mathbb R$ is uncountable that doesn't use Cantor's diagonal argument?2012-12-04
  • 0
    depends, do you call the general proof that $|P(X)|>|X|$ as Cantor's diagonal argument ?2012-12-04
  • 1
    @MA: theorem 24.1, Munkres, Topology, uses only that any linear continuum in the order topology is uncountable (he underlined that he meant to prove it w/o relying on Cantor diagonal argument, to show it only depends on order relations).2012-12-04
  • 0
    @belgi: yes. ${ }$2012-12-04
  • 0
    @gnometorule: I don't see how Munkres' Theorem 24.1 proves that $\mathbb R$ is uncountable without using Cantor's diagonal argument.2012-12-04
  • 0
    Just using connectedness, and the R is a linear continuum; endowing it with order topology. As to details, just have a look at the proof (probably can be googled). It definitely doesn't rely on cantor; not only is it obvious from the proof, but he says once or twice he Kent to prove it w/o relying on it as most people (including me before reading this) only know the diagonal argument.2012-12-04
  • 0
    Strike that. I need more sleep.2012-12-04
  • 0
    It follows from 27.7. Munkres, which implies that closed intervals in R are uncountable. As a superset of an uncountable set is certainly uncountable, R is. The argument used in 27.7, though, doesn't use cantor diagonilization either; only topological properties.2012-12-04
  • 1
    @gnometorule: interesting! I didn't know about that.2012-12-04
  • 0
    The argument that @GEdgar mentions works just as well for the interval $[0,1]$: Keep cutting off pieces that contain consecutive elements of any given sequence in $[0,1]$. You'll end up with at least one point in $[0,1]$ that is not contained in that sequence.2012-12-04