# How can complement of the Cantor set be the countable union of open intervals?

I studied a long back about Cantor sets. Today while explaining it to one of my friends I got stumped at the complement of the Cantor set. As far as I am aware of, the complement of the Cantor set is the countable union of intervals removed from $$[0,1]$$ to form the Cantor set. But I cannot make it clear to him as to why we are removing only countably many middle one third open intervals from the interval $$[0,1]$$ to form the Cantor set. In the first step we are removing one third interval from the middle of $$[0,1]$$ and that gives rise to two intervals. In the second step we are removing middle one third from each of the two intervals and thus we are left with four intervals. In the third step we are removing middle one third from each of the four intervals and we are thus left with eight intervals and in the next step we are to remove middle one third from each of the eight intervals and so on. So after $$n^{\text {th}}$$ step we are removing $$1 + 2 + 2^2 + \cdots + 2^n$$ intervals which is certainly greater than $$2^n.$$ Since $$2^{\aleph_0} = \mathfrak c,$$ it seems to me that as $$n$$ approaches infinity we are at least removing as many open intervals as the cardinality of the continuum $$\mathfrak c.$$

Where did I make erroneous considerations? Could anyone kindly point it out.

Sorry for the stupid question.

The cardinal arithmetic does not work like that. The fact that each set is of cardinality bigger than $$2^n$$ is not really important, and certainly does not translate to $$2^{\aleph_0}$$ at infinify.

We still have a finite set at each step. And countable union of finite sets is countable. In your particular case infinite countable, i.e. $$\aleph_0$$. And that is regardless of their concrete size.

• Oh! I get your point. If we are looking at the removed intervals at each step as points (of some set; namely the set of all such removed intervals) then you are essentially saying that the set of all such removed open intervals is anyway a countable union of finite sets and hence countable. Apr 14 at 17:12
• @AnilBagchi. In my answer by "set" I refer to the collection of intervals removed at step $n$. So intervals themselves are uncountable. But the collection of intervals at each step is finite. In other words $A,B$ may be uncountable, but $\{A,B\}$ is a finite set of size $2$. And it is the latter we analyze here. You may think about this as "picking a point from each interval" but it is slightly convoluted and unnatural imo. Apr 14 at 17:37

Not yet explicitly pointed out, the error you made was in assuming that $$\sup_{i∈ℕ} 2^{c_i} = 2^{\sup_{i∈ℕ} c_i}$$ for every sequence of cardinals $$(c_i)_{i∈ℕ}$$. Be careful not to swap operations unless they really can be swapped, such as supremum and the real exponentiation function. Note on the other hand that $$\sup_{i∈ℕ} 2^{k_i} = 2^{\sup_{i∈ℕ} k_i}$$ for every strictly increasing sequence of ordinals $$(k_i)_{i∈ℕ}$$. Ordinal exponentiation is different from cardinal exponentiation; in particular $$ω = 2^ω$$.

You may be overthinking this with the set cardinality equation. You've described an enumeration of the open intervals. In fact, since each interval has a distinct left-hand endpoint that is a rational number, this gives an injection from the set of intervals into the rationals, showing that the set is countable.

But we can say more if we like. After the first step, there's $$1$$, after the second step, there are $$2$$ more for a total of $$1 + 2 = 3$$, and after the $$n$$th step, there are $$2^n - 1$$ of them. This is a bijection from the naturals to the set of open intervals.

If we want to make it explicit, we have to write down a breadth-first enumeration of the infinite complete binary tree. Each node of the tree at depth $$n-1$$ corresponds to one of the $$2^{n-1}$$ new intervals of size $$3^{-n}$$ that we remove at step $$n$$. (Sketch a picture of, say, step $$n = 3$$ with $$2^2 = 4$$ new intervals, each of width $$\frac{1}{27}$$ if this is difficult to visualize.)

The bijection takes a positive integer $$k$$ and produce an interval $$I_k = (a_k, b_k)$$. Using the observation that node/interval $$I_k$$ will have two children $$I_{2k}$$ and $$I_{2k+1}$$, it seems natural to represent $$k$$ in binary: $$k = \sum_{j=0}^{n-1} b_j \, 2^j,$$ where $$2^{n-1} \leq k < 2^n$$. The most significant bit $$b_{n-1} = 1$$ is treated separately. The endpoints are easy to describe: \begin{align} a_k &= \frac{1}{3^n}\biggl(1 + 2\sum_{j=1}^{n-1} b_{j-1} \, 3^j \biggr) \\ b_k &= \frac{1}{3^n}\biggl(2 + 2\sum_{j=1}^{n-1} b_{j-1} \, 3^j \biggr) \end{align}

So, for example, with $$n = 3$$, the indices are $$k$$ such that $$4 \leq k < 8$$ and the intervals are: $$\begin{array}{cccc} k & b_2b_1b_0 & a_k & b_k \\ \hline 4 & 100 & \frac{1}{27} \bigl( 1 + 2(0 + 0) \bigr) = \frac{1}{27} & \frac{1}{27} \bigl( 2 + 2(0 + 0) \bigr) = \frac{2}{27} \\ 5 & 101 & \frac{1}{27} \bigl( 1 + 2(0 + 3) \bigr) = \frac{7}{27} & \frac{1}{27} \bigl( 2 + 2(0 + 3) \bigr) = \frac{8}{27} \\ 6 & 110 & \frac{1}{27} \bigl( 1 + 2(9 + 0) \bigr) = \frac{19}{27} & \frac{1}{27} \bigl( 2 + 2(9 + 0) \bigr) = \frac{20}{27} \\ 7 & 111 & \frac{1}{27} \bigl( 1 + 2(9 + 3) \bigr) = \frac{25}{27} & \frac{1}{27} \bigl( 2 + 2(9 + 3) \bigr) = \frac{26}{27} \end{array}$$