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 if(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<x\right\}. 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

Advertisements

One thought on “The Cantor set, I

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s