#5: The Cantor Set and the Cantor Function

The Cantor set C is a fractal that is obtained by repeatedly removing the middle third of a segment. Start with the closed interval [0,1]. Remove the open interval (\frac{1}{3},\frac{2}{3}) to obtain [0,\frac{1}{3}] \cup [\frac{2}{3},1], i.e. two disjoint closed segments. Remove the middle thirds of those two segments, and you end up with four disjoint segments. After infinitely many steps, the result is called the Cantor set. The diagram below is only an approximation after a finite number of steps.

Does anything remain?

Let C_0 = [0,1], let C_1 = C_0 - (\frac{1}{3}, \frac{2}{3}), and let C_n be the result after n steps. Then we can write the Cantor set as C = \cap_{n=0}^\infty C_n. As it turns out, each C_n, being a finite union of compact sets, is compact. Moreover, C_{n+1} \subset C_n for all n, so C is an intersection of shrinking compact sets. Therefore C is compact and non-empty.

Hausdorff (Fractal) Dimension

If you split the Cantor set in half at the point 0.5, it appears that both sides, scaled by a factor, are miniature Cantor sets. And if you split each of those miniature Cantor sets at their halfway points, you get even smaller Cantor sets. And so on.

Since there are 2 exact miniature copies each at 1/3 the original size, it follows that the Hausdorff dimension of the Cantor set should be \displaystyle \frac{\log 2}{\log 3} \approx 0.631. This can be more rigorously checked by invoking the definition of Hausdorff measure, but we will not do so here.

How large is the Cantor set?

It depends on what you mean by “large.” We can try two measurements of its “size”: dimension 1 and dimension 0. Recall that a 1-dimensional object is just a line, and a 0-dimensional object is a point. So, we can ask how “long” the Cantor set is and how many points it contains.

To answer the first question, note that each step, we remove a third of what is remaining. So, letting \text{vol}_1(X) denote the 1-dimensional volume, or length, of X, we find that \text{vol}_1(C_n) = \left(\frac{2}{3}\right)^n. Taking the limit as n goes to infinity, we find that \text{vol}_1(C) = 0. This means the Cantor set has measure 0 in the real line.

The second question, which concerns the number of points in the Cantor set, is a bit trickier. There are a few ways to tackle this. Intuitively, the endpoints 0 and 1 of C_0 are in the Cantor set. So are the endpoints of C_1, etc., as they are never removed (only middles are removed). Since there are 2^n disjoint segments in C_n, it follows there are 2 \cdot 2^n endpoints in C_n. This implies the number of points in C is greater than 2^n for every n \geq 0. It follows that C has an infinite number of points.

In fact, the cardinality of the number of points in Cantor set is uncountably infinite. One proof is topological (as in Munkres, p. 178). An argument earlier showed that C is compact. Since every point in the Cantor set is a limit point (i.e., given any point in C, every neighborhood contains an infinite number of elements of C), there are no isolated points. There is a theorem saying that if a nonempty compact Hausdorff space has no isolated points, it is uncountable. Since \mathbb{R} is a Hausdorff space (in fact, it is a metric space), the hypotheses of the theorem are satisfied, and the result follows.

Binary and ternary expansions

A second proof that the Cantor set is uncountable uses a property of binary and ternary expansions. Write every real number in [0,1] in ternary expansion. We must be careful, as real numbers do not have unique binary, ternary, or even decimal representations (for instance, 0.999… = 1). An example in ternary is that 1/3 = 0.1 = 0.0222…. Then the Cantor set is precisely those numbers that do not have a 1 in at least one of their ternary expansions. Since 1/3 can be written as 0.0222…, which does not contain a 1, 1/3 is in the Cantor set. However, the number 5/9 = 0.12 cannot be written with no 1’s, so 5/9 is not in the Cantor set.

Then construct a function f : C \to \mathbb{R} which basically changes points in the Cantor set into binary, by changing all 2’s in their ternary expansion into 1’s, and leaving the 0’s as 0’s.

For example, the number 1/3, which in ternary can be written as 0.0222…, would be mapped to 0.0111…, which is precisely 1/2 in binary. Note that this map is not one-to-one, as the number 2/3, which is written in ternary as 0.2, is mapped to 0.1, which in binary is also 1/2.

It is clear that the function f takes points in the Cantor set to real numbers in [0,1]. As shown above, it is not one-to-one, but it is onto. Given any real number in [0,1], take its binary expansion, change all the 1’s to 2’s, and put the result in ternary. Since f is a surjection onto [0,1], which is uncountable, it must be that the Cantor set is uncountable.

The Cantor function

The Cantor function, also known as the Cantor Staircase, is a bizarre function that is continuous and has a derivative of 0 at every point where it is differentiable. In fact, it is differentiable at every point other than on the Cantor set, which is a set of measure zero. The term we use in math to denote “except on a set of measure zero” is the word “almost,” so we may say that the Cantor function is differentiable almost everywhere.

Here is a graph of the Cantor function:

It is not obvious that this function is continuous. But first, I haven’t even defined the function yet! Since I used f earlier, I will use g here. As it turns out, g will not be too different from f.

First, let g : \mathbb{R} \to \mathbb{R} map all of (-\infty, 0) to 0 and all of (1, \infty) to 1. Then it remains to map [0,1] onto [0,1]. For x \in [0,1], expand x in its ternary expansion.

  • If x \in C, then g(x) = f(x). That is, given a point in the Cantor set, map it as we defined above for f: change all the 2’s into 1’s, and then read the result in binary. It is well-defined as non-unique representations of a number are mapped to the same thing. For instance, even though 1/3 may be written as 0.1 or 0.0222…, we find that f(0.1) = 1/2 in binary and f(0.0222...) = 1/2 in binary as well.
  • If x \notin C, then it must have a 1 somewhere in its ternary expansion. Change everything after the 1 to 0, then apply f, i.e. change all the 2’s into 1’s, and read the result in binary. For example, 5/9 = 0.12 in ternary. Everything after the 1 turns into 0, so it becomes 0.1. Changing the 2’s into 1’s leaves 0.1. Interpreting this in binary results in 1/2.

In fact, it is not too hard to see that the function is constant on any removed middle-third interval, i.e. on any interval not in the Cantor set. Let a = 1/3 = 0.0222... and b = 2/3 = 0.2. Both of these are mapped to 1/2. Any number c between 1/3 and 2/3 is written as c = 0.1 c_1 c_2 c_3 \dots. All the c_1, c_2, c_3, \dots are changed to zero, and the result 0.1 is mapped to 1/2. Thus the function is constant on the middle-third segment from 1/3 to 2/3. We could have chosen a and b to be the endpoints of any middle-third interval and the argument holds, the only difference being there a finite number of digits in front of the leading 1.

The Cantor function is continuous – Proof

Constant parts of a function are continuous, so it remains to show that g is continuous on the Cantor set. Now we may use the old episilon-delta formulation of continuity in calculus. Given a point y \in C, we wish to show that for any \epsilon > 0, there exists \delta > 0 such that |x - y| < \delta implies |g(x) - g(y)| < \epsilon.

Given \epsilon, let n be such that 2^{-n} < \epsilon. Then \delta = 3^{-n} suffices. To see this, suppose that g(x) \neq g(y), then there must be some binary digit where they first differ, let n be the index of this digit. Now suppose x and y are separated by no more than 3^{-n}, then their ternary expansions are the same up to the first n-1 digits. Then g(x) and g(y) in binary are the same up to the first n-1 digits, and thus they are separate by no more than 2^{-n}.

Final remark

Note that the Cantor function g hits every value between 0 and 1, i.e. it is surjective on [0,1]. Thus it manages to rise from 0 to 1 despite being constant almost everywhere.

More Info

For more information about the Cantor set or the Cantor function, check out the following:

For more information about the background and/or theorems used, see:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s