How to construct binary sequences associated to points of the Cantor set?

Question

Let $C\subset \mathbb{R}$ be the Cantor set, obtained from the interval $[0,1]\subset \mathbb{R}$ by removing the middle thirds of successive subintervals. That is, assuming $C_n$ constructed we let $C_{n+1}$ be the union of the intervals obtained by removing the middle thirds of all intervals contained in $C_n$ in the case we let $C_0=[0,1]$. In that case,

$$C = \bigcap_{n=0}^\infty C_n.$$

Now, I'm trying to show that there is a bijection between $C$ and the set of all sequences $(x_n)_{n\in \mathbb{N}}$ such that $x_n =0,1$. In other words, the sequences $x : \mathbb{N}\to \{0,1\}$. On this question I'm just concerned with the construction of a sequence associated to points of $C$.

Reading a little bit about the Cantor set, I've seem that every point inside $C$ can be written as

$$a = \sum_{k=1}^\infty a_k3^{-k},$$

where each $a_k$ is either $0$ or $2$. If we rewrite this as

$$a = \sum_{k=1}^\infty \dfrac{2}{3^k}b_k$$

i.e., if we set $2b_k = a_k$, and if we assume the map $a\mapsto (b_k)_{k\in \mathbb{N}}$ is a bijection then we are done, because each $b_k$ is either $0$ or $1$.

Although I've "got the idea" of the construction, I didn't quite understand how to write it down rigorously. The idea I've got is: if $x\in C$ then $x\in C_1$, so it can be on two subintervals. If it is on the first, associate $a_1=0$ if it is on the second $a_1 = 2$. In either case, $x\in C_2$ and is in one of the two subintervals of the subinterval of $C_1$ where $x$ is. In that case if it is on the first, associate $a_2=0$ and on the second $a_2 = 2$. Continuing this process for all $n\in \mathbb{N}$ we get a sequence $(a_n)_{n\in \mathbb{N}}$ and also the associated sequence $(b_n)_{n\in \mathbb{N}}$ with $b_n\in \{0,1\}$.

I'm in doubt on how to write down this properly in a rigorous way. I imagine I need to define $a_1$ and then define $a_n$ in terms of $a_{n-1}$. My way to write this is:

Let $a\in C$ be given. Since $a\in C$, we have $a\in C_n$ for all $n\in \mathbb{N}$. In particular, $a\in C_1$. If $a \in [0,1/3]$ set $a_1 = 0$, if $a\in [2/3,1]$ set $a_2 = 2$. Now supposing defined $a_1,\dots,a_{n-1}$ define $a_n$ in the following way: $C_{n-1}$ is the union of $2^{n-1}$ disjoint intervals $I_k$, if $a\in I_{k_0}$, since $a\in C_n$ also, we have that $a$ has to be in one of the two disjoint pieces of $I_{k_0}$ obtained when we build $C_n$. If he is on the first, set $a_n =0$, if on the second, set $a_n = 2$.

Is this correct? I feel it is not quite rigorous. Also, why $0$ and $2$? Why not $0$ on the first subinterval and $1$ on the second? I didn't quite get this idea yet.

So, how to understand and write more correctly this construction?

Answer 1

If you’ve already proved that the middle-thirds construction yields the set of real numbers that can be written in the form $a=\sum_{k\ge 1}\frac{a_k}{3^k}$, where each $a_k\in\{0,2\}$, then your first approach works fine. You can’t assume that the map $a\mapsto\langle b_k:k\in\Bbb Z^+\rangle$ is a bijection, but this is not hard to prove. If you’re starting from scratch, however, it’s easiest to work directly with the middle-thirds construction.

To start with you have $C_0=[0,1]$. For each finite sequence $\sigma$ of zeroes and ones we’ll define a closed interval $I_\sigma$ in such a way that if $n=|\sigma|$, the length of $\sigma$, then $I\subseteq C_n$. The only sequence of length $0$ is $\langle\rangle$, the empty sequence, and I set $I_{\langle\rangle}=C_0=[0,1]$. Now we essentially follow your idea. There are two sequences of length $1$, $\langle 0\rangle$ and $\langle 1\rangle$; let

$$I_{\langle 0\rangle}=\left[0,\frac13\right]\qquad\text{and}\qquad I_{\langle 1\rangle}=\left[\frac23,1\right]\;.$$

Clearly these are the two ‘pieces’ of $C_1$, and $C_1=I_{\langle 0\rangle}\cup I_{\langle 1\rangle}$.

At this point it’s handy to introduce a little more notation: for each non-negative integer $n$ let $\Sigma_n$ be the set of sequences of zeroes and ones of length $n$, so that $\Sigma_0=\{\langle\rangle\}$, and $\Sigma_1=\{\langle 0\rangle,\langle 1\rangle\}$. Suppose that for some $n$ we have defined an intervals $I_\sigma$ for each $\sigma\in\Sigma_n$ in such a way that they are the ‘pieces’ of $C_n$. For each $\sigma\in\Sigma_n$ let $I_\sigma=[a_\sigma,b_\sigma]$; in other words, we’re defining $a_\sigma$ and $b_\sigma$ to be the left and right endpoints of $I_\sigma$. In the middle-thirds construction the interval $I_\sigma$ is replaced by its left third, which we’ll call $I_{\sigma^\frown 0}$, and its right third, which we’ll call $I_{\sigma^\frown 1}$. (The notation $\sigma^\frown i$ denotes the sequence obtained by appending $i$ to the sequence $\sigma$. Thus, if $\sigma=\langle 0,1,1\rangle$, then $\sigma^\frown 0=\langle 0,1,1,0\rangle$.) And it’s straightforward now to define these subintervals of $I_\sigma$: since the length of $I_\sigma$ is $b_\sigma-a_\sigma$, we have

$$I_{\sigma^\frown 0}=\left[a_\sigma,a_\sigma+\frac13(b_\sigma-a_\sigma)\right]=\left[a_\sigma,\frac23a_\sigma+\frac13b_\sigma\right]\;,\tag{1}$$

and

$$I_{\sigma^\frown 1}=\left[b_\sigma-\frac13(b_\sigma-a_\sigma),b_\sigma\right]=\left[\frac13a_\sigma+\frac23b_\sigma,b_\sigma\right]\;.\tag{2}$$

Every sequence in $\Sigma_{n+1}$ is $\sigma^\frown i$ for some $\sigma\in\Sigma_n$ and $i\in\{0,1\}$, so we now have an $I_\sigma$ for each $\sigma\in\Sigma_{n+1}$. And since $C_n=\bigcup_{\sigma\in\Sigma_n}I_\sigma$, where the family $\{I_\sigma:\sigma\in\Sigma_n\}$ of intervals is pairwise disjoint, it follows immediately from the mechanics of the middle-thirds construction that $C_{n+1}=\bigcup_{\sigma\in\Sigma_{n+1}}I_\sigma$, where the family $\{I_\sigma:\sigma\in\Sigma_{n+1}\}$ is pairwise disjoint.

Note that we don’t actually have to find explicit formulas for the endpoints of the intervals, though we could in fact do so; it’s enough to have names for them and formulas for calculating them recursively. For example, from $(1)$ and $(2)$ we can deduce that in general

$$a_{\sigma^\frown 0}=a_\sigma,\quad b_{\sigma^\frown 0}=\frac23a_\sigma+\frac13b_\sigma,\quad a_{\sigma^\frown 1}=\frac13a_\sigma+\frac23b_\sigma,\quad\text{and}\quad b_{\sigma^\frown 0}=b_\sigma\;.$$

To complete the argument, for each infinite sequence $\sigma=\langle s_k:k\in\Bbb Z^+\rangle$ and each $n\in\Bbb Z^+$ let $\sigma_n=\langle s_1,\ldots,s_n\rangle$ be the initial subsequence of $\sigma$ of length $n$. For completeness you can let $\sigma_0=\langle\rangle$: that is, after all, the initial subsequence of $\sigma$ of length $0$. Now show that there is exactly one point in $\bigcap_{n\ge 0}I_{\sigma_n}$, and call that point $x_\sigma$. This gives you an injection from the set of infinite sequences of zeroes and ones to the Cantor set, and you complete the proof by verifying that the injection is also a surjection.

Showing that $\bigcap_{n\ge 0}I_{\sigma_n}$ is non-empty requires that you use compactness of the closed intervals. That it contains at most one point follows from the fact that if $\tau\in\Sigma_n$, then the length of the interval $I_\tau$ is $3^{-n}$; this is easily proved by induction on $n$.