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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Henno Brandsma Jan 19 '19 at 9:18
  • $\begingroup$ Thank you so much @HennoBrandsma! You are correct. $\endgroup$ – LE Anh Dung Jan 19 '19 at 9:20
  • 1
    $\begingroup$ The second formula is wrong semantically: you cannot substract a set of intervals (!) from $[0,1]$. There are unions missing.. $\endgroup$ – Henno Brandsma Jan 19 '19 at 9:20
  • $\begingroup$ @HennoBrandsma I have fixed it :) $\endgroup$ – LE Anh Dung Jan 19 '19 at 9:22
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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! $\endgroup$ – LE Anh Dung Jan 19 '19 at 12:11
  • $\begingroup$ @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. $\endgroup$ – Henno Brandsma Jan 19 '19 at 12:24
  • $\begingroup$ @LeAnhDung also see my answer here for a more accurate description. $\endgroup$ – Henno Brandsma Jan 19 '19 at 12:30
  • $\begingroup$ 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}$. $\endgroup$ – LE Anh Dung Jan 19 '19 at 12:33
  • $\begingroup$ I am mainly concerned with the explicit formulas of Cantor set, while your answer in that link does not address that :) $\endgroup$ – 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)$$


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]$$


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)$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.