# How to derive closed formulas of Cantor set?

The Cantor set $$\mathcal{C}$$ is defined as follows: $$\mathcal{C}:=\bigcap_{n=0}^{\infty}C_n$$ where $$C_0=[0,1]$$ and $$C_{n+1} = \dfrac{C_n}{3} \bigcup\left(\dfrac{2}{3}+\dfrac{C_n}{3}\right)$$.

From Wikiwand's page, The explicit formulas of Cantor sets are

$$\mathcal{C} = \bigcap_{n=0}^{\infty} \bigcup_{k=0}^{3^n-1} \left(\left[\frac{3k+0}{3^{n+1}}\,,\, \frac{3k+1}{3^{n+1}}\right] \cup \left[\frac{3k+2}{3^{n+1}}\,,\,\frac{3k+3}{3^{n+1}}\right] \right) \space (1)$$ and $$\mathcal{C} = [0,1] \setminus \bigcup\left\{\left(\frac {3k+1}{3^n}, \frac{3k+2}{3^n}\right) \,\middle\vert\, k,n\in \mathbb Z^+\right\} \space (2)$$

I have tried for several days to get $$(1)$$ and $$(2)$$ from the definition of Cantor set, but to no avail.

Could you please help me derive formulas $$(1)$$ and $$(2)$$? Thank you so much!

• I changed the finite intersection to a finite union, as per the page. BTW It's not wikipedia's page but wikiwand...? A sort of commercial (ads (!)) rip-off it seems. – Henno Brandsma Jan 19 '19 at 9:18
• Thank you so much @HennoBrandsma! You are correct. – LE Anh Dung Jan 19 '19 at 9:20
• The second formula is wrong semantically: you cannot substract a set of intervals (!) from $[0,1]$. There are unions missing.. – Henno Brandsma Jan 19 '19 at 9:20
• @HennoBrandsma I have fixed it :) – LE Anh Dung Jan 19 '19 at 9:22
• Since $\mathcal{C}=\bigcup_{n\ge 0}C_n$, to avoid confusion your notation in (1) should probably start the dummy variable $n$ at $0$, not at $1$. – J.G. Jan 19 '19 at 9:35

The finite union in (1) is just the expression for $$C_n$$; you can prove its truth by induction. And $$C = \bigcap_n C_n$$ by definition.

Then (2) follows by de Morgan: the complement of $$C_n$$ in $$[0,1]$$ is just a finite union of open intervals and the complement of $$C$$ is just the union of the complements of the $$C_n$$. You then take the complement of that to get $$C$$ back.

• Hi @Henno. Let $T_n=\bigcup_{k=0}^{3^n-1} \left(\left[\frac{3k+0}{3^{n+1}}\,,\, \frac{3k+1}{3^{n+1}}\right] \cup \left[\frac{3k+2}{3^{n+1}}\,,\,\frac{3k+3}{3^{n+1}}\right] \right)$. As a result, $T_0=[0,\frac{1}{3}]\cup [\frac{2}{3},1]$ and $T_1=[0,\frac{1}{9}]\cup [\frac{2}{9},\frac{3}{9}]\cup [\frac{3}{9},\frac{4}{9}]\cup [\frac{5}{9},\frac{6}{9}] \cup[\frac{6}{9},\frac{7}{9}]\cup [\frac{8}{9},1]$. As a result, $T_0=C_1$, but $T_1\neq C_2$. I am unable to verify that the formulas given in Wikipedia is correct or not. Please help me check the formula! – LE Anh Dung Jan 19 '19 at 12:11
• @LeAnhDung every $C_n$ is a disjoint union of $2^n$ many intervals of length $\frac{1}{3^n}$, so the formulae on the wikiwand page are wrong. – Henno Brandsma Jan 19 '19 at 12:24
• @LeAnhDung also see my answer here for a more accurate description. – Henno Brandsma Jan 19 '19 at 12:30
• Hi @Henno, I think that formula is correct. Although $T_n=:\bigcup_{k=0}^{3^n-1} \left(\left[\frac{3k+0}{3^{n+1}}\,,\, \frac{3k+1}{3^{n+1}}\right] \cup \left[\frac{3k+2}{3^{n+1}}\,,\,\frac{3k+3}{3^{n+1}}\right] \right)$ is not equal to $C_n$. But the redundant intervals in $T_{n+1}$ and $T_n$ are actually disjoint. As you can see in my previous comment, $[\frac{3}{9},\frac{4}{9}]\cup [\frac{5}{9},\frac{6}{9}]$ from $T_1$ are disjoint with $T_0$. From this observation, I guess $T_1\cap T_0=C_2$ and $\bigcap \{T_0,\cdots,T_n\}=C_{n+1}$. – LE Anh Dung Jan 19 '19 at 12:33
• I am mainly concerned with the explicit formulas of Cantor set, while your answer in that link does not address that :) – LE Anh Dung Jan 19 '19 at 12:34

I have figured out the proof and posted it as an answer here. It will be great and beneficial if someone helps me verify my attempt. Thank you so much!

Let $$\mathbf{L}(x)=\dfrac{x}{3}$$ and $$\mathbf{R}(x)=\dfrac{x+2}{3}$$. Let $$I_0=[0,1]$$ and $$I_{n+1}=\mathbf{L}(I_n) \cup \mathbf{R}(I_n)$$. Cantor set is defined as follows: $$\mathcal{C}:=\bigcap_{n=0}^{\infty} I_n$$

Theorem: $$\mathcal{C} = [0,1] - \bigcup_{n=0}^{\infty} \bigcup_{k=0}^{3^n-1} \left( \frac{3k+1}{3^{n+1}} ,\frac{3k+2}{3^{n+1}}\right)$$

Let $$T_n=I_0-I_n$$ for all $$n\in\Bbb N$$.

Lemma 1: $$T_{n+1}=\mathbf{L}(T_n) \cup T_1 \cup \mathbf{R}(T_n)$$

Proof:

Notice that $$\mathbf{R}(T_n)=\mathbf{R}(I_0-I_n)=\mathbf{R}(I_0)- \mathbf{R}(I_n) \subseteq \mathbf{R}(I_0) \subseteq I_0-\mathbf{L}(I_0)$$. Thus $$(I_0-\mathbf{L}(I_0)) \cap\mathbf{R}(T_n)=\mathbf{R}(T_n)$$. Similarly, $$\mathbf{L}(T_n) \subseteq \mathbf{L}(I_0) \subseteq I_0 -\mathbf{R}(I_0)$$ and thus $$(I_0-\mathbf{R}(I_0)) \cap\mathbf{L}(T_n)=\mathbf{L}(T_n)$$. Moreover, $$\mathbf{L}(T_n)\cap\mathbf{R}(T_n) \subseteq \mathbf{L}(I_0)\cap\mathbf{R}(I_0)=\emptyset$$.

By the definition of $$T_{n+1}$$:

\begin{align}T_{n+1} &=I_0-I_{n+1}\\ &=I_0-(\mathbf{L}(I_n) \cup \mathbf{R}(I_n))\\ &=(I_0-\mathbf{L}(I_n)) \cap (I_0 - \mathbf{R}(I_n))\\ &=[I_0-\mathbf{L}(I_0-T_n)] \cap [I_0 - \mathbf{R}(I_0-T_n)]\\ &=[I_0-(\mathbf{L}(I_0)-\mathbf{L}(T_n))] \cap [I_0 - (\mathbf{R}(I_0)-\mathbf{R}(T_n))]\\ &=[(I_0-\mathbf{L}(I_0)) \cup \mathbf{L}(T_n)] \cap [(I_0-\mathbf{R}(I_0)) \cup \mathbf{R}(T_n)]\\ &= [(I_0-\mathbf{L}(I_0)) \cap (I_0-\mathbf{R}(I_0))] \cup [(I_0-\mathbf{L}(I_0)) \cap\mathbf{R}(T_n)] \cup [\mathbf{L}(T_n)\cap(I_0-\mathbf{R}(I_0))] \cup [\mathbf{L}(T_n)\cap\mathbf{R}(T_n)]\\ &=[I_0 -\mathbf{(L}(I_0)\cup\mathbf{R}(I_0))]\cup \mathbf{R}(T_n) \cup \mathbf{L}(T_n)\\ &=(I_0-I_1)\cup \mathbf{R}(T_n) \cup \mathbf{L}(T_n)\\ &= T_1 \cup \mathbf{R}(T_n) \cup \mathbf{L}(T_n)\\ &=\mathbf{L}(T_n) \cup T_1 \cup \mathbf{R}(T_n)\end{align}

Lemma 2: $$\bigcup_{m=0}^{n+1} \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right) = \left(\frac{1}{3},\frac{2}{3} \right) \cup \left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^{m+1}-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right]$$

Proof:

Let $$t=m+1$$. Then $$RHS=\left(\frac{1}{3},\frac{2}{3} \right) \cup \left[\bigcup_{t=1}^{n+1} \bigcup_{k=0}^{3^t-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right)\right]$$.

Moreover, $$\bigcup_{t=0}^0 \bigcup_{k=0}^{3^t-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right) = \bigcup_{k=0}^{3^0-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right) = \bigcup_{k=0}^0 \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right)=$$ $$\left(\frac{1}{3},\frac{2}{3} \right)$$.

It follows that $$RHS = \left [ \bigcup_{t=0}^0 \bigcup_{k=0}^{3^t-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right) \right] \cup \left[\bigcup_{t=1}^{n+1} \bigcup_{k=0}^{3^t-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right)\right]=$$ $$\bigcup_{t=0}^{n+1} \bigcup_{k=0}^{3^t-1} \left(\frac{3k+1}{3^{t+1}}, \frac{3k+2}{3^{t+1}}\right) = \bigcup_{m=0}^{n+1} \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right) =LHS$$.

Lemma 3: $$T_{n+1}=\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)$$

Proof:

We prove the assertion by induction on $$n$$. It is clear that it trivially holds for $$n=0$$. Let it hold for a positive integer $$n$$.

Notice that $$\frac{1}{3} < \frac{3k+1}{3^{m+2}} < \frac{3k+2}{3^{m+2}} < \frac{2}{3}$$ for all $$3^m \le k \le 2.3^m-1$$. It follows that $$\bigcup_{m=0}^n \bigcup_{k=3^{m}}^{2.3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right) \subseteq \left(\frac{1}{3},\frac{2}{3} \right)$$ and thus $$\left(\frac{1}{3},\frac{2}{3} \right)= \left [ \left(\frac{1}{3},\frac{2}{3} \right) \cup \left( \bigcup_{m=0}^n \bigcup_{k=3^{m}}^{2.3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right) \right)\right ]$$.

By Lemma 1,

$$T_{(n+1)+1}=T_{n+2}=\mathbf{L}(T_{n+1}) \cup T_1 \cup \mathbf{R}(T_{n+1})$$

$$=\mathbf{L}\left(\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)\right) \cup \left(\frac{1}{3},\frac{2}{3} \right) \cup \mathbf{R}\left(\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)\right)$$

$$=\left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right] \cup \left(\frac{1}{3},\frac{2}{3} \right) \cup \left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1+2.3^{m+1}}{3^{m+2}}, \frac{3k+2+2.3^{m+1}}{3^{m+2}}\right)\right]$$

$$=\left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right] \cup \left(\frac{1}{3},\frac{2}{3} \right) \cup \left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3(k+2.3^m)+1}{3^{m+2}}, \frac{3(k+2.3^m)+2}{3^{m+2}}\right)\right]$$

$$=\left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right] \cup \left(\frac{1}{3},\frac{2}{3} \right) \cup \left [\bigcup_{m=0}^n \bigcup_{k=2.3^{m}}^{3^{m+1}-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right]$$

$$=\left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right] \cup \left [ \left(\frac{1}{3},\frac{2}{3} \right) \cup \left( \bigcup_{m=0}^n \bigcup_{k=3^{m}}^{2.3^m-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right) \right)\right ] \cup \left[ \bigcup_{m=0}^n \bigcup_{k=2.3^{m}}^{3^{m+1}-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right]$$

$$= \left(\frac{1}{3},\frac{2}{3} \right) \cup \left[\bigcup_{m=0}^n \bigcup_{k=0}^{3^{m+1}-1} \left(\frac{3k+1}{3^{m+2}}, \frac{3k+2}{3^{m+2}}\right)\right]$$ $$=\bigcup_{m=0}^{n+1} \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)$$ by Lemma 2

We proceed to prove our main theorem.

$$\mathcal{C}:=\bigcap_{n=0}^{\infty} I_n=\bigcap_{n=0}^{\infty} (I_0-T_n)=I_0-\bigcup_{n=0}^{\infty} T_n=I_0-\bigcup_{n=1}^{\infty}T_n$$ [since $$T_0=\emptyset$$]

$$=I_0-\bigcup_{n=0}^{\infty}T_{n+1}=I_0-\bigcup_{n=0}^{\infty}\bigcup_{m=0}^n \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)$$

$$=I_0-\bigcup_{m=0}^{\infty} \bigcup_{k=0}^{3^m-1} \left(\frac{3k+1}{3^{m+1}}, \frac{3k+2}{3^{m+1}}\right)$$

$$=I_0-\bigcup_{n=0}^{\infty} \bigcup_{k=0}^{3^n-1} \left(\frac{3k+1}{3^{n+1}}, \frac{3k+2}{3^{n+1}}\right)$$.

This completes the proof.