# The Cantor set, I

This is post # 6 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

The goal is this post is to construct the Cantor set and demonstrate that the Cantor set has the same cardinality as the set of all real numbers. In the next post we discuss the topological properties of the Cantor set.

The Construction
For each positive integer $n=1,2,3,\cdots$, let $S_n=\left\{0,1\right\}$ be the set of all sequences zeros and ones of length $n$. Each $Sn$ has $2^n$ sequences. For each $f \in S_n$, we can tag on a $0$ or $1$ and obtain an element of $S_{n+1}$. For example, for $011000 \in S_6$, both $0110000, 0110001 \in S_7$.

Let $A_0=[0,1]$ be the unit interval. Remove the middle third open interval $(\frac{1}{3},\frac{2}{3})$ from $A_0$. Label the remaining two intervals by $B_0=[0,\frac{1}{3}]$ and $B_1=[\frac{2}{3},1]$. Let $A_1=B_0 \cup B_1$ be the union of these two closed intervals.

Consider the stage at $n=2$. For $0 \in S_1$, remove the middle third of $B_0$ and obtain $B_{00}=[0,\frac{1}{9}]$ and $B_{01}=[\frac{2}{9},\frac{1}{3}]$. For $1 \in S_1$, remove the meddle third of $B_1$ and obtain $B_{10}=[\frac{2}{3},\frac{7}{9}]$ and $B_{11}=[\frac{8}{9},1]$. Let $A_2=B_{00} \cup B_{01} \cup B_{10} \cup B_{11}$. Note that the length of each closed interval $B_{ij}$ is $\displaystyle \frac{1}{3^2}=\frac{1}{9}$.

Suppose we have the following at the $n^{th}$ stage, where $n \ge 1$.

• The closed interval $B_f$ has been defined for each $f \in S_n$.
• The length of each $B_f$ is $\frac{1}{3^n}$.
• $A_n=\bigcup \limits_{h \in S_n} B_h$.

We now define the closed intervals in stage $n+1$. For each closed interval $B_f$, we remove the middle third open intervals and obtain two closed intervals $B_{f0}$ and $B_{f1}$ where each has length $\frac{1}{3^{n+1}}$. Let $A_{n+1}$ be defined as:

$\displaystyle A_{n+1}=\bigcup \limits_{f \in S_n} (B_{f0} \cup B_{f1})=\bigcup \limits_{g \in S_{n+1}} B_g$

We now define the Cantor set $C=\bigcap \limits_{i=0}^{\infty} A_j$. This is a nonempty set subset of the unit interval. The point $0 \in C$ since $0 \in B_0 \cap B_{00} \cap B_{000} \cap \cdots$. Being the union of finitely many closed intervals, each $A_n$ is a closed subset of $[0,1]$. Thus each $A_n$ is a compact subset of $[0,1]$. Any nested decreasing sequence of compact subsets of the real line is nonempty. See the post The Euclidean topology of the real line (4) – Compactness. In the remainder of this post, we show that the Cantor set $C$ has the cardinality continuum.

General Discussion
Let $A$ and $B$ be sets. A function $f:A \rightarrow B$ is a one-to-one function if for $x,y \in A$ with $x \ne y$, $f(x) \ne f(y)$, that is, distinct elements of the domain are mapped to distinct elements of the range. A function $f:A \rightarrow B$ is said to be a surjection if i$f(A)=B$, i.e. every point in the set $B$ is mapped by some point of $A$. A function $f:A \rightarrow B$ is said to be a bijection if it is both a one-to-one function and a surjection.

The sets $A$ and $B$ have the same cardinality if there is a bijection $f:A \rightarrow B$. When $A$ and $B$ have the same cardinality, we use the notation $\lvert A \lvert=\lvert B \lvert$. For example, the set of all rational numbers has the same cardinality as the integers since we can define a bijection between the two sets. More informally, we can put the rational numbers in an exhaustive list indexed by the integers. When a set has the same cadinality as the set of real numbers, we say that the set has cardinality continuum.

When there is a one-to-one function $f:A \rightarrow B$, we denote this condition by $\lvert A \lvert \le \lvert B \lvert$. Obviously when $A \subset B$, we have $\lvert A \lvert \le \lvert B \lvert$. The Cantor–Bernstein–Schroeder theorem states that when there are one-to-one functions $f:A \rightarrow B$ and $g:B \rightarrow A$, we have $\lvert A \lvert=\lvert B \lvert$. In other words, if $\lvert A \lvert \le \lvert B \lvert$ and $\lvert B \lvert \le \lvert A \lvert$, we have $\lvert A \lvert=\lvert B \lvert$. We utilize this fact when we show that the Cantor set and the set of all real numbers have the same cardinality.

The Cardinality of the Cantor Set
Let $\omega=\left\{0,1,2,3,\cdots\right\}$ be the set of all nonnegative integers. Let $S_{\omega}$ be the set of all infinite sequences of 0’s and 1’s. Let $\mathcal{P}(\omega)$ be the set of subsets of $\omega$. The cardinality of the Cantor set follows from the following relationship:

$\displaystyle \lvert \mathbb{R} \lvert \le \lvert \mathcal{P}(\omega) \lvert = \lvert S_{\omega} \lvert = \lvert C \lvert \le \lvert \mathbb{R} \lvert$

The inequality $\lvert C \lvert \le \lvert \mathbb{R} \lvert$ is clear since the Cantor set is a subset of the real line. The following claims establish the relationship.

Claim 1 $\lvert S_{\omega} \lvert = \lvert C \lvert$
This follows from the contruction of the Cantor set. Let $y \in C$. At each stage of the construction, there are $2^n$ many closed intervals and the point $y$ belongs to exactly one of these intervals, say $B_{f_n}$. At the next stage, the point $y$ belongs to one of the closed intervals as a result of splitting $B_{f_n}$ by removing the middle third. Since the lengths of $B_{f_n}$ approaches to zero, we have $\left\{y\right\}=\bigcap \limits_{n=1}^{\infty} B_{f_n}$.

Note that for each $f_n$ and $f_{n+1}$ agree on the first $n$ coordinates. Thus the finite sequences form an countably infinite sequence $f \in S_{\omega}$ such that $f$ and $f_n$ agree on the first $n$ coordinates of $f$. Let $H(y)=f$.

We just describe a mapping $H: C \rightarrow S_{\omega}$. This mapping is one-to-one. For $x,y \in C$ where $x \ne y$, there must be some stage $n$ where $x$ and $y$ belong to disjoint closed intervals. Otherwise, $x=y$. Let $n$ be the least integer such that $x$ and $y$ belong to disjoint closed intervals. Then $x$ and $y$ belong to the same interval $B_{g}$ in stage $n-1$. However, $x$ and $y$ belong to disjoint closed intervals at stage $n$, say $x \in B_{g0}$ and $y \in B_{g1}$. As a result, $H(x)$ and $H(y)$ disagree at the $n^{th}$ coordinate, implying $H(x) \ne H(y)$.

No point in $S_{\omega}$ is missed by the mapping $H$. For each $f \in S_{\omega}$, let $f_n$ be the sequence of its first $n$ coordinates. Then the sequence of closed intervals $B_{f_n}$ collapses to a point $x$. It is clear that $H(x)=f$. $\blacksquare$

Claim 2 $\lvert \mathcal{P}(\omega) \lvert = \lvert S_{\omega} \lvert$
The surjection is defined by an indicator function. For each $A \in \mathcal{P}(\omega)$, $F(A) \in S_{\omega}$ such that the $n^{th}$ coordinate $F(A)_n$ is:

$\displaystyle F(A)_n=\left\{\begin{matrix}0&\thinspace n \notin A \\{1}&\thinspace n \in A \end{matrix}\right.$

It can be verified that $F: \mathcal{P}(\omega) \rightarrow S_{\omega}$ is a one-to-one map and that $F(\mathcal{P}(\omega))=S_{\omega}$. $\blacksquare$

Claim 3 $\lvert \mathbb{R} \lvert \le \lvert \mathcal{P}(\omega) \lvert$
Let $\mathbb{Q}$ be the set of all rational numbers. Since $\lvert \mathbb{Q} \lvert=\lvert \omega \lvert$, we have $\lvert \mathcal{P}(\mathbb{Q}) \lvert=\lvert \mathcal{P}(\omega) \lvert$. We now define a one-to-one map $G: \mathbb{R} \rightarrow \mathcal{P}(\mathbb{Q})$.

For each $x \in \mathbb{R}$, let $G(x)=\left\{r \in \mathbb{Q}: r. It is clear that $G(x) \ne G(y)$ for $x \ne y$.

Links to previous posts on the topology of the real line:
The Euclidean topology of the real line (1)
The Euclidean topology of the real line (2)
The Euclidean topology of the real line (3) – Completeness
The Euclidean topology of the real line (4) – Compactness
The Cantor bus tour

1. I think there is a typo in the first line of the construction, $S_n$ should be defined as $\{0,1\}^n$.