Measure and Dimension of the Cantor Set

Steven R. Dunbar
Department of Mathematics and Statistics
University of Nebraska-Lincoln

David Fowler
Department of Curriculum and Instruction
University of Nebraska-Lincoln

ã Copyright  Steven R. Dunbar, David Fowler, 1992, All rights reserved.  T

Before Starting

Get["CantorSet.ma"]

Lebesgue Measure

Measure Zero

A subset  E of the real line R which can be covered by a countable collection of open intervals whose total length is arbitrarily small is said to be a set of measure zero.  The classical excluded-middle-thirds Cantor set C is a set of measure zero.

Here are three stages in determining the measure of the classical Cantor set.  At each stage we use open sets containing the intervals remaining after the middle-third removal process.

lines[l_List] :=
    Map[Line[{{#[[1]],0}, {#[[2]], 0}}] &,l];

superSets[f_,delta_]:=Map[{#[[1]]-delta,#[[2]]+delta} &, f]

rarc[s_]:=Circle[{(s[[1]]+s[[2]])/2,0},
					  (s[[2]]-s[[1]])/2, {-Pi/6,Pi/6}];

larc[s_]:=Circle[{(s[[1]]+s[[2]])/2,0},
					  (s[[2]]-s[[1]])/2, {5Pi/6,7Pi/6}];

Table[Show
		[Graphics
			[{Thickness[0.01], lines[intervals[k]],{Thickness[.001],
			Line[{{-0.1,0},{1.1,0}}],
			Map[larc,superSets[intervals[k], 0.1/2^k]],
			Map[rarc,superSets[intervals[k], 0.1/2^k]]
			}}],
			PlotRange->{{-0.1,1.1},{-1,1}},
			AspectRatio->.5],{k,3}];

We can show the Cantor has measure zero by using the sets resulting from the excluded-middle-thirds process.  We directly compute the total length of the intervals remaining after each of the stages of the middle-third removal process.  The reader should verify that this is permissible, since we are covering the classical  Cantor set with closed intervals instead of open intervals as in the definition.

Table[  Apply[Plus, Minus[Apply[Subtract, intervals[i], {1}]]],
 {i, 10}]

N[%]

Lebesgue Measure

In R, the class of Borel sets is the smallest collection of subsets of R such that
	(1) every open set and every closed set is a Borel set.
	(2) the union of every finite or countable collection of Borel sets is a Borel set, 	and the intersection of any finite or countable collection of Borel sets is a Borel set.

We call  m a measure on R if m assigns a non-negative number m(A), possibly ¥, called the measure  of  A to each set A  in some class of subsets of R (for instance the Borel sets) such that:
	(1)	 m(é) = 0
	(2)	m(A) £ m(B), for A Í B
	(3)	If A1, A2, ... is a countable sequence of sets then
				m(Èi=1¥ Ai) £ åi=1¥ m(Ai)
				
		with equality if the Ai are disjoint Borel  sets.

For open and closed intervals, we take the Lebesgue measure to be  m((a,b)) = b-a, and m([a,b]) = b-a.  If A = È[ai,bi] is a finite or countable union of intervals, then m(A) =å(bi-ai).  For an arbitrary Borel  set A on the real line, define
	m(A) = inf ( å (bi-ai) : A  Í È[ai,bi])
that is, we look at all coverings of A by countable unions of intervals and take the smallest total interval length possible.

Table[  Apply[Plus, 
	Minus[Apply[Subtract, cantorSet[{0,2}, 1/2.5, 1/2.5, i], {1}]]],
	{i,9}]

Apply[Plus, 
	Minus[Apply[Subtract, cantorSet[{0,2}, 1/2.5, 1/2.5, 12], {1}]]]

From this it would appear that the generalized Cantor set of ratio 1/2.5, 1/2.5  on [0,2] has Lebesgue measure zero.   Indeed this is the case, since  at each stage of the construction there are 2n intervals of length 2 (2/5)n containing the Cantor set under consideration.  Thus the measure is zero.

Box-Counting Dimension

Consider a subet E of the real line R, and consider  the d-mesh on R given by the collection of intervals [n d, (n+1) d] where n is an integer.  Let Nd(F) be the number of d-mesh intervals which intersect the set F, Nd(F) = card{n : [n d, (n+1) d] Ç F ¹ Æ}.

Show[ Graphics[ {Thickness[.004], lines[intervals[5]]}],
Frame -> True,
FrameTicks -> {Automatic, None},
GridLines -> {Table[i/40, {i,0,40}], None},
PlotRange -> {{0,1}, {-0.05, 0.05}},
AspectRatio -> 0.1,
PlotRegion -> {{0,0.8},{0,0.8}} ]
(* Plot parameters obtained by experimentation.  
Parameters added to give proper effect. *)

Then define the box-counting dimension of F as
                                              ( log(Nd(F))
          dimB(F) =         lim    -----------------
                                   d -> 0       -log d
  provided  the limit exists.

To determine the  box-counting dimension of the Cantor set with this definition requires a double limiting  process, one using the excluded-middle-thirds process to generate approximations to the Cantor set, and the other using boxes of a given size.  Nevertheless, without proving the required theorem validating the double-limit process, we can make experimental approximations to the box-counting dimension of the Cantor set.

We will take the list of endpoints generated by the middle-thirds process at stage n as an approximation to the Cantor set.  Then multiply each point of this set by 1/d and take the Floor  of the result.  This gives the box-index of each point   Then taking the Union gives a list of the distinct box-indices which contain an endpoint of the Cantor set.  The cardinality is then given by the Length of the list.

boxCount[l_List, delta_] :=
	Length[ Union[ Floor[(1/delta)*l]]]

boxCount[Flatten[intervals[5]], 1/40]

approxDimension[ l_List, delta_] := 
	N[ Log[ boxCount[l,delta]]/(-Log[delta])]

approxDimension[ Flatten[intervals[10]], 1/2^10]

Alternative definitions of the box-counting dimension exist, for instance one can let Nd(F) be the smallest number of balls of radius d that cover F, or the largest number of disjoint balls of radius d that cover F.  Theorems are needed to establish that these alternate definitions are equivalent.  Taking the first alternate definition as the smallest number of balls of radius d needed to cover F, taking F as the classical Cantor set, taking  d = 1/3n, then clearly it requires at most 2n such balls to cover.  Then the dimension will be (less than)
	lim n->0 (log(2n)/(-log(1/3n))) = log(2)/log(3) = 0.63093...

Later we will get  theorem allowing us to calculate the dimension without approximating the limiting process in certain cases.

Hausdorff Dimension

Let F be a subset of R, and let s be a non-negative number.  For any d > 0, define	Hds(F) = inf{ å |Ui|s : { Ui} is a d-cover of F}.   Here |U| = sup{ | x-y | : x,y Î U} is the diameter of U.  A countable collection {Ui} is said to be a d-cover of F if  F Ì È Ui. and each of the Ui has diameter less than d.  Define the Hausdorff s-measure as 
	Hs(F) = lim d->0 Hds(F)
Usually this limit is either 0 or ¥.  Finally define the Hausdorff dimension of F as
	dimH(F) = inf{ s : Hs(F) = 0} = sup{s : Hs(F) = ¥}.  Note that if s = dimH(F), then Hs(F) may be 0, ¥ or some finite value.

For the Cantor set, let d > 0 given.  For n so large that 1/3n < d, the intervals remaining after n stages of the middle third removal process are a  d-cover of the Cantor set C.  Then it is easy to graph Hds(C) as a function of s for several sizes of d.

Plot[ { Apply[Plus, Minus[Apply[Subtract, intervals[2], {1}]]^s],
        Apply[Plus, Minus[Apply[Subtract, intervals[5], {1}]]^s],
        Apply[Plus, Minus[Apply[Subtract, intervals[7], {1}]]^s]},
 {s,0,1}, PlotRange->{{0,1}, {0,10}}]

For d < 0.63, it appears that Hds(C) is increasing and getting very large as d -> 0.  For d > 0.63 it appears that Hds(C) is going to zero as d -> 0.  From this, we should conjecture (and prove!) that dimH(C) » 0.63.

Similarity Dimension

A set of mappings S1, S2,¼Sm: Rn  -> Rn is said to be a set of contractive similarities if 
	| Si(x) - Si(y)| = ci |x - y|, for all x,y Î Rn and for all i = 1¼m. 
The ci are called the ratios of the similarities.   The following theorem is fundamental:

Theorem:  Let mappings S1, S2,¼Sm: Rn  -> Rn be a set of contractive similarities on
D Ì Rn.  Then there exists a unique non-empty compact subset F that is invariant for the Si, i.e.  which satisfies
		F =  Èi=1m Si(F).
Moreover, if we define a transformation S on the set of non-empty compact sets by 
			S(E) =  Èi=1m Si(E).
and write Sk for the kth iterate of S given by S0(E) = E, Sk(E) = S(Sk-1(E)) for k ³ 1, then
		F = Çk=1¥ Sk(E)
for any set E in the set of non-empty compact sets such that Si(E) Ì E for each i.
The Cantor set is an application of this idea which we have already seen in the context of the deterministic  iteration of the iterated-function-system idea:

i0 = {{0,1}}  (* A list of intervals, here 1 interval *)

affinemaps = {{0,1/3},{2/3, 1/3}}
(* Affine maps 0 + (1/3)x and 2/3 + (1/3)x  *)

mapUnion[i0,affinemaps]

mapUnion[%, affinemaps]

NestList[mapUnion[#, affinemaps] &, i0, 4] //MatrixForm

Here is another illustration of this theorem, this time in R2.

affinemaps = {   { {0,0}, {{1/2,0},{0,1/2}}  },
				 { {1/2,0}, {{1/2,0},{0,1/2}} },
				 { {1/4,Sqrt[3]/4}, {{1/2,0},{0,1/2}} }
			 }

e = { {{0,0},{1,0},{1,1},{0,1}} }  (* a list of polygons! *)

imagegon[pgon_] := Table[ 
		Map[
			affinemaps[[i,1]] + affinemaps[[i,2]] . # &, 
			pgon],
		{i,Length[affinemaps]}]

itergon[pgon_] := Partition[Flatten[imagegon[Flatten[pgon,1]],1],4]

graphgon[pgon_,gray_] := {GrayLevel[gray], Map[Polygon, itergon[pgon]]}

Show[ Graphics[ Table[ graphgon[e2,0.5]]]

seq = NestList[itergon,e,6];

Do[seq[[i]] = 
	{GrayLevel[1.0 - i*(0.9)/Length[seq]],Map[Polygon, seq[[i]]]},
	{i,1,Length[seq]} ]

Length[seq]

Show[Graphics[seq], AspectRatio -> Automatic]

The set of mappings S1,¼Sm satisfy the open set condtion if there is a non-empty bounded open set V such that
	V É  Èi=1m  Si(V).
Here is an illustration showing that the previous example in R2 satisfies the open set condition.

affinemaps = {   { {0,0}, {{1/2,0},{0,1/2}}  },
				 { {1/2,0}, {{1/2,0},{0,1/2}} },
				 { {1/4,Sqrt[3]/4}, {{1/2,0},{0,1/2}} }
			 }

pgon = { {0,0},{1,0},{1,1},{0,1}}

imagegons = Table[ 
		Map[
			affinemaps[[i,1]] + affinemaps[[i,2]] . # &, 
			pgon],
		{i,Length[affinemaps]}]

Show[ Graphics[ { GrayLevel[0.7], Polygon[ pgon], 
	GrayLevel[0.3], Map[Polygon, imagegons] }], Axes -> True,
	 AspectRatio -> 1, PlotRange -> All ]

Similarity Dimension Theorem:  Suppose that the open set condition holds for the similarities Si on  Rn with ratios ci for 1 £ i £ m.  If F is the invariant set satisfying 
	F =  Èi=1m Si(F)
then dimH(F) = dimB(F) = s, where s is given by 
	åi=1m  cis  =  1.

Using this theorem and the illustration above demonstrating that the affine mappings defing the Cantor set satisfy the open set condition, we can find the Hausdorff dimension of the Cantor set.

Solve[ (1/3)^s + (1/3)^s ==1, s]

N[%]

Basic Exercises

1. a.) Suppose that instead of calculating the Lebesgue measure of the classical Cantor set with the closed intervals of the ith stage of the excluded middle third construction, we more properly use open intervals.  Suppose we cover the Cantor set  with open sets extending the intervals remaining after the middle-third removal process by an amount 1/100 on each side.  That is, if [aij,bij] is the jth interval in the ith stage of the excluded middle third process, use (aij -1/100, bij+1/100) as an open interval in the cover of the Cantor set.  Will this result in the Lebesgue measure? Explain.  
	b) Extend the intervals at the ith stage by 1/(100 2i) on each side.  Wil this result in the Lebesgue measure?
	c) Extend the intervals at the ith stage by 1/(100 5i) on each side.  What happens?

2. Find the Lebesgue measure of the set {0, 1/2, 1/3, 1/4, 1/5, ...}

3. Find the capacity dimension of the set {0, 1/2, 1/3, 1/4, 1/5,...}

4. Find the Hausdorff dimension of the set {0, 1/2, 1/3, 1/4, 1/5, ...}

5. Find the similarity dimension of the graph of the Cantor function.

6. Find the similarity  dimension of a generalized Cantor set determined by the ratios r1, and r2.

7.  Find the dimension of the Sierpinski gasket.

Try For Yourself

1. Show that for any x in the open interval (0,1), there are points a, b in the classical Cantor set C such that |a-b| = x.  Thus, in some sense, the Cantor set may be thin, but it is somewhat evenly distributed.

2.  Construct a Cantor-like set which has positive Lebesgue measure

3.  Under the hypotheses of the similarity dimension theorem, show that Hds(F) £ |F|s.  (This is the easy half of the proof of the theorem.  The reverse inequality is much more technical and difficult.)

Have Fun With Mathematica

Prepare a graph or diagram of the approximate box counting dimension of the Cantor set as a function of two parameters:  the stage n of approximation of the Cantor set by the excluded-middle-third process, and the box size d.  Display how the approximations approach the dimension of the Cantor set.

References

Standard textbooks on Lebesgue measure are

Principles of  Mathematical  Analysis,3rd edition, Chapter 10, Walter Rudin, McGraw-Hill, New York, 1976
Real and Complex Analysis, 3rd edition, Walter Rudin, McGraw-Hill, New York, 1987
Real Analysis, 3rd edition,  H. L. Royden, Macmillan, New York, 1988.

Our brief  and simplified treament  is based on the discussion in
Fractal Geometry, K. J. Falconer, J. Wiley and Sons, New York, 1990.

The box-counting dimension is also known as the fractal dimension and the capacity dimension and it is a popular measure of a set because it is relatively easy to approximate numerically.  A reference with a number of examples is 
	Fractals Everywhere, Michael Barnsley, Academic Press, New York, 1988.

The Hausdorff dimension is older, more classical and somewhat harder to compute, although it has more satisfying theoretical properties.   Some references to its properties and history are
	The Geometry of Fractal Sets, K. J. Falconer, Cambridge University Press,
	 Cambridge, 1986
and
	Fractal Geometry, K. J. Falconer, J. Wiley and Sons, New York, 1990.

An excellent treatment of the similarity dimension, from which our treatment is adapted is in

Fractal Geometry, K. J. Falconer, J. Wiley and Sons, New York, 1990.