2
$\begingroup$

Wikipedia gives a recurrence relation for the $nth$ Cantor Set: $C_n = \frac{C_{n-1}}{3} \cup(\frac{2}{3}+\frac{C_{n-1}}{3})$.

http://en.wikipedia.org/wiki/Cantor_Set#Construction_and_Formula_of_the_ternary_set

How does one verify such a relation? I considered using induction, but I couldn't do much more than the base case with this one. Can someone provide on how to use induction with a recurrence relation?

2 Answers 2

5

$C_n$ isn’t a Cantor set; it’s the $n$-th approximation to the middle-thirds Cantor set, the $n$-th stage in the construction of the middle-thirds Cantor set. There really isn’t anything to verify: $C_n=\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\tag{1}$ is the recursion step of a definition whose initial step is $C_0=[0,1]$. The middle-thirds Cantor set is then defined to be $C=\bigcap_{n\in\Bbb N}C_n\;,$ and it’s at this point that there’s something to prove $-$ namely, that this $C$ has the various properties of the Cantor set.

For instance, in order to prove that $C$ is closed in $\Bbb R$, it suffices to show that each $C_n$ is closed. $C_0$ is certainly closed, so it suffices to show that the construction in $(1)$ preserves closedness. This isn’t hard: the map $\Bbb R\to\Bbb R:x\mapsto\frac{x}3$ is a homeomorphism, so if $C_{n-1}$ is closed, so is $\frac13C_{n-1}$. Similarly, translation by $\frac23$ is a homeomorphism, so $\frac23+\frac12C_{n-1}$ is closed. Finally, the union of two closed sets is closed, so $C_n$ is closed.

Similarly, one can use induction to show that $C_n\subseteq C_{n-1}$ for each $n\in\Bbb N$. It’s easy to verify directly that $C_1\subseteq C_0$. Now assume that $C_n\subseteq C_{n-1}$ for some $n\in\Bbb N$: $C_n=\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\subseteq C_{n-1}\;.$ Then

$\begin{align*} C_{n+1}&=\frac{C_n}3\cup\left(\frac23+\frac{C_n}3\right)\\ &=\frac13\left(\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\right)\cup\left(\frac23+\frac13\left(\frac{C_{n-1}}3\cup\left(\frac23+\frac{C_{n-1}}3\right)\right)\right)\\ &\subseteq\frac13C_{n-1}\cup\left(\frac23+\frac13C_{n-1}\right)\\ &=C_n\;, \end{align*}$

as desired.

With more work one can use this definition to show that $C$ contains no non-trivial interval.

Added: To see that this construction not only gives a Cantor set but gives the familiar middle-thirds Cantor set, look at the numbers in $[0,1]$ in terms of their ternary expansions. First, $C_0=\left\{\sum_{n\ge 1}\frac{a_n}{3^n}:a_n\in\{0,1,2\}\text{ for }n\ge 1\right\}\;.$ For convenience let me write $0.a_1a_2a_3\dots$ instead of $\sum_{n\ge 1}\frac{a_n}{3^n}$. Then $C_0$ contains all of the ternary expansions $0.a_1a_2a_3\dots$. Multiplying by $\frac13$ just moves every digit one place to the right, changing $0.a_1a_2a_3\dots$ to $0.0a_1a_2a_3\dots$, and adding $\frac23$ to each of these numbers gives us all of the ternary expansions of the form $0.2a_1a_2a_3\dots$. In other words, $C_1$ consists of the numbers in $[0,1]$ with ternary expansions beginning with $0$ or $2$: we’ve stripped out those numbers that have only ternary expansions beginning with $1$, i.e., those in $\left(\frac13,\frac23\right)$.

At each stage the recursion in $(1)$ takes the numbers in $C_{n-1}$, shifts their ternary expansions one place to the right, and inserts a leading $0$ or $2$. Thus, the numbers in $C_2$ are those with ternary expansions whose first two digits are either $0$ or $2$, and in general $C_n$ contains those numbers in $[0,1]$ with ternary expansions whose first $n$ digits are all either $0$ or $2$.

This is exactly the same thing that happens when we remove the open middle thirds in the other recursive construction.

  • 0
    That clears everything up. Thank you for the nice answer(s)!2012-07-03
4

Instead of considering the $n^{th}$ stage of the Cantor set to be the $n-1^{st}$ with the middle third of each segment removed, it uses the alternate construction of taking the $n-1^{st}$ stage, shrinking by a factor of $3$, and duplicating the shrunk version in the interval $[\frac 23,1]$. If you take a point that is in $C_{n-1}$ it has a ternary expansion $0.a_1a_2a_3\ldots$ where the first $n-1$ digits are $0$ or $2$. For $C_n$ it is taken to $0.0a_1a_2a_3\ldots$ and $0.2a_1a_2a_3\ldots$, so each one has the first $n$ digits either $0$ or $2$.