118 CHAPTER 6. HUTCHINSON™S THEOREM AND FRACTAL IMAGES.

as a distance on H(X). He proved

Proposition 6.1.1 The function h on H(X) — H(X) satsi¬es the axioms for

a metric and makes H(X) into a complete metric space. Furthermore, if

A, B, C, D ∈ H(X)

then

h(A ∪ B, C ∪ D) ¤ max{h(A, C), h(B, D)}. (6.3)

Proof. We begin with (6.3). If is such that A ‚ C and B ‚ D then clearly

A ∪ B ‚ C ∪ D = (C ∪ D) . Repeating this argument with the roles of A, C

and B, D interchanged proves (6.3).

We prove that h is a metric: h is symmetric, by de¬nition. Also, h(A, A) = 0,

and if h(A, B) = 0, then every point of A is within zero distance of B,and hence

must belong to B since B is compact, so A ‚ B and similarly B ‚ A. So

h(A, B) = 0 implies that A = B.

We must prove the triangle inequality. For this it is enough to prove that

d(A, B) ¤ d(A, C) + d(C, B),

because interchanging the role of A and B gives the desired result. Now for any

a ∈ A we have

d(a, B) = min d(a, b)

b∈B

¤ min (d(a, c) + d(c, b) ∀c ∈ C

b∈B

= d(a, c) + min d(c, b) ∀c ∈ C

b∈B

= d(a, c) + d(c, B) ∀c ∈ C

¤ d(a, c) + d(C, B) ∀c ∈ C.

The second term in the last expression does not depend on c, so minimizing

over c gives

d(a, B) ¤ d(a, C) + d(C, B).

Maximizing over a on the right gives

d(a, B) ¤ d(A < C) + d(C, B).

Maximizing on the left gives the desired

d(A, B) ¤ d(A, C) + d(C, A).

We sketch the proof of completeness. Let An be a sequence of compact non-

empty subsets of X which is Cauchy in the Hausdor¬ metric. De¬ne the set

A to be the set of all x ∈ X with the property that there exists a sequence of

points xn ∈ An with xn ’ x. It is straighforward to prove that A is compact

and non-empty and is the limit of the An in the Hausdor¬ metric.

6.1. THE HAUSDORFF METRIC AND HUTCHINSON™S THEOREM. 119

Suppose that K : X ’ X is a contraction. Then K de¬nes a transformation

on the space of subsets of X (which we continue to denote by K):

K(A) = {Kx|x ∈ A}.

Since K continuous, it carries H(X) into itself. Let c be the Lipschitz constant

of K. Then

d(K(A), K(B)) = max[min d(K(a), K(b))]

a∈A b∈B

¤ max[min cd(a, b)]

a∈A b∈B

= cd(A, B).

Similarly, d(K(B), K(A)) ¤ c d(B, A) and hence

h(K(A), K(B)) ¤ c h(A, B). (6.4)

In other words, a contraction on X induces a contraction on H(X).

The previous remark together with the following observation is the key to

Hutchinson™s remarkable construction of fractals:

Proposition 6.1.2 Let T1 , . . . , Tn be a collection of contractions on H(X) with

Lipschitz constants c1 , . . . , cn , and let c = max ci . De¬ne the transformation T

on H(X) by

T (A) = T1 (A) ∪ T2 (A) ∪ · · · ∪ Tn (A).

Then T is a contraction with Lipschitz constant c.

Proof. By induction, it is enough to prove this for the case n = 2. By (6.3)

h(T (A), T (B)) = h(T1 (A) ∪ T2 (A), T1 (B) ∪ T2 (B))

¤ max{h(T1 (A), h(T1 (B)), h(T2 (A), T2 (B))}

¤ max{c1 h(A, B), c2 h(A, B)}

= h(A, B) max{c1 , c2 } = c · h(A, B)

.

Putting the previous facts together we get Hutchinson™s theorem;

Theorem 6.1.1 Let K1 , . . . , Kn be contractions on a complete metric space

and let c be the maximum of their Lifschitz contants. De¬ne the Hutchinson

operator, K, on H(X) by

K(A) = K1 (A) ∪ · · · ∪ Kn (a).

Then K is a contraction with Lipschtz constant c.

120 CHAPTER 6. HUTCHINSON™S THEOREM AND FRACTAL IMAGES.

6.2 A¬ne examples

We describe several examples in which X is a subset of a vector space and each

of the Ti in Hutchinson™s theorem are a¬ne transformations of the form

Ti : x ’ A i x + b i

where bi ∈ X and Ai is a linear transformation.

6.2.1 The classical Cantor set.

Take X = [0, 1], the unit interval. Take

x x2

T1 : x ’ T2 : x ’

, +.

3 23

These are both contractions, so by Hutchinson™s theorem there exists a unique

closed ¬xed set C. This is the Cantor set.

To relate it to Cantor™s original construction, let us go back to the proof of

the contraction ¬xed point theorem applied to T acting on H(X). It says that

if we start with any non-empty compact subset A0 and keep applying T to it,

i.e. set An = T n A0 then Ab ’ C in the Hausdor¬ metric, h. Suppose we take

the interval I itself as our A0 . Then

1 2

A1 = T (I) = [0, ] ∪ [ , 1].

3 3

in other words, applying the Hutchinson operator T to the interval [0, 1] has

12

the e¬ect of deleting the “middle third” open interval ( 3 , 3 ). Applying T once

more gives

1 21 27 8

A2 = T 2 [0, 1] = [0, ] ∪ [ , ] ∪ [ , ] ∪ [ , 1].

9 93 39 9

In other words, A2 is obtained from A1 by deleting the middle thirds of each

of the two intervals of A1 and so on. This was Cantor™s original construction.

Since An+1 ‚ An for this choice of initial set, the Hausdor¬ limit coincides with

the intersection.

But of course Hutchinson™s theorem (and the proof of the contractions ¬xed

point theorem) says that we can start with any non-empty closed set as our

initial “seed” and then keep applying T . For example, suppose we start with

the one point set B0 = {0}. Then B1 = T B0 is the two point set

2

B1 = {0, },

3

B2 consists of the four point set

228

B2 = {0, , , }

939