The Cantor set is a fractal that is obtained by repeatedly removing the middle third of a segment. Start with the closed interval
. Remove the open interval
to obtain
, 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 , let
, and let
be the result after
steps. Then we can write the Cantor set as
. As it turns out, each
, being a finite union of compact sets, is compact. Moreover,
for all
, so
is an intersection of shrinking compact sets. Therefore
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 . 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 denote the 1-dimensional volume, or length, of
, we find that
. Taking the limit as
goes to infinity, we find that
. 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 and
of
are in the Cantor set. So are the endpoints of
, etc., as they are never removed (only middles are removed). Since there are
disjoint segments in
, it follows there are
endpoints in
. This implies the number of points in
is greater than
for every
. It follows that
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 is compact. Since every point in the Cantor set is a limit point (i.e., given any point in
, every neighborhood contains an infinite number of elements of
), 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
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 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 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 takes points in the Cantor set to real numbers in
. As shown above, it is not one-to-one, but it is onto. Given any real number in
, take its binary expansion, change all the 1’s to 2’s, and put the result in ternary. Since
is a surjection onto
, 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 earlier, I will use
here. As it turns out,
will not be too different from
.
First, let map all of
to 0 and all of
to 1. Then it remains to map
onto
. For
, expand
in its ternary expansion.
- If
, then
. That is, given a point in the Cantor set, map it as we defined above for
: 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
in binary and
in binary as well.
- If
, then it must have a 1 somewhere in its ternary expansion. Change everything after the 1 to 0, then apply
, 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 and
. Both of these are mapped to 1/2. Any number
between 1/3 and 2/3 is written as
. All the
are changed to zero, and the result
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
and
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 is continuous on the Cantor set. Now we may use the old episilon-delta formulation of continuity in calculus. Given a point
, we wish to show that for any
, there exists
such that
implies
.
Given , let
be such that
. Then
suffices. To see this, suppose that
, then there must be some binary digit where they first differ, let
be the index of this digit. Now suppose
and
are separated by no more than
, then their ternary expansions are the same up to the first
digits. Then
and
in binary are the same up to the first
digits, and thus they are separate by no more than
.
Final remark
Note that the Cantor function hits every value between 0 and 1, i.e. it is surjective on
. 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:
- Wiki: http://en.wikipedia.org/wiki/Cantor_set
- Wiki: http://en.wikipedia.org/wiki/Cantor_function
- Cut The Knot: http://www.cut-the-knot.org/do_you_know/cantor.shtml
For more information about the background and/or theorems used, see:
Pingback: A continuous bijection from the Cantor Set to [0,1] – Math Solution