3

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!

Akira
  • 17,367
  • 1
    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 09:18
  • Thank you so much @HennoBrandsma! You are correct. – Akira Jan 19 '19 at 09:20
  • 1
    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 09:20
  • @HennoBrandsma I have fixed it :) – Akira Jan 19 '19 at 09: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 09:35
  • Hi @J.G., I am not sure how $\bigcup_{k=0}^{3^{n-1}-1}$ is well defined at $n=0$. Please suggest how to fix it! – Akira Jan 19 '19 at 09:37
  • @LeAnhDung Because we're decrementing $n$ by $1$, we replace $n-1$ with $n$ so the upper limit becomes $3^n-1$. – J.G. Jan 19 '19 at 09:42
  • Hi @J.G., I think you're probably wrong. I have just checked your idea. With your fix, the set will contain elements from $[2, 3]$. – Akira Jan 19 '19 at 09:48
  • @LeAnhDung Well, you'd also need to adjust the quantities the $\bigcup$ works with. But I do think it's worth summing over $n\ge 0$. A few edits to your question ago, you were (IIRC) closer to what you need for that. – J.G. Jan 19 '19 at 09:51
  • Hi @J.G., I have adjust the formula to reflect your suggestion. Could you please have a check on it? – Akira Jan 19 '19 at 09:57
  • @LeAnhDung That formula looks sensible, taking an explicit intersection of the $C_{n+1}$. On second thoughts, if we're starting there maybe the $n$ label should start at $1$ after all, so the set we're writing in terms of $n$ is $C_n$. – J.G. Jan 19 '19 at 10:06
  • The formulae are wrong, already on the quoted page. – Henno Brandsma Jan 19 '19 at 12:57
  • The formulas seem correct to me. I have posted a proof as an answer for reference. – Akira Jan 21 '19 at 03:47

2 Answers2

2

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.

Henno Brandsma
  • 242,131
  • 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! – Akira 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}$. – Akira 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 :) – Akira Jan 19 '19 at 12:34
  • @LeAnhDung The explicit formula is all $x$ that can be written as $\sum_{n=1}^\infty \frac{a_n}{3^n}$ where all $a_n \in {0,2}$. – Henno Brandsma Jan 19 '19 at 12:40
  • @LeAnhDung As I said, the $T_n$ (but with open intervals) are the complements of the $C_n$. – Henno Brandsma Jan 19 '19 at 12:42
  • Hi @Henno, I have asked a related question here. It seems to me that nobody is interested in it. Please help me prove the theorem! Many thanks for you! – Akira Jan 21 '19 at 13:22
0

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.

Community
  • 1
Akira
  • 17,367