Hutchinson's Theorem (a.k.a. how to draw pretty pictures)
by djmathman, Dec 10, 2016, 4:38 PM
Disclaimer: the things in this blog post are not mine; rather, they are the result of material covered over a span of four lectures in Analysis.
Theorem (Hutchinson, 1981) Let
be a complete metric space, and suppose 
are contractions. Then there exists a unique nonempty compact set 
such that ![\[K = \bigcup_{i=1}^nf_i(K).\]](//latex.artofproblemsolving.com/f/8/9/f89bea14df0e4a9ef52f88a9da6eed001087d1a9.png)
Proof. For closed and bounded subsets
and 
of , define ![\[h(A,B) = \max\left\{\sup_{a\in A}\operatorname{dist}(a,B),\sup_{b\in B}\operatorname{dist}(b,A)\right\}\in[0,\infty)\]](//latex.artofproblemsolving.com/6/2/7/6279907331e75505d0fd139c9a254fa5920b03ff.png)
to be the Hausdorff distance between and . It can be shown through a bit of work that this is actually a metric on the space of closed and bounded sets in . Denote by 
the resulting metric space. Additionally, let 
denote the metric space of all compact subsets of when endowed with 
as a metric.
We first note a few properties of. These were proven over the span of three days in class, and so I'll spare the majority of the details.
With these facts in hand, the proof is actually surprisingly short. Note that complete implies 
complete. Furthermore, remark that if is compact, then 
is also compact, so in particular 
is a finite union of compact sets and is thus also compact.
Define
via 
; by the previous paragraph, we know this function is well-defined. Let 
, 
be in , and for simplicity set 
to be the Lipschitz constant associated to 
for 
(which we know is in the interval 
since each is a contraction). Then 
Note that 
is the maximum of a bunch of real numbers less than 
and thus is itself less than . Thus, 
is also a contraction, and so the Banach fixed-point theorem guarantees the existence of a unique 
satisfying 
. 
Corollary 1. There is a simple way to generate this: start with any set , and repeatedly iterate on it. Since is a contraction, the (Hausdorff) distance between 
and tends to zero as 
.
Corollary 2. We can use this to generate fractals! Here are a few examples. On the left hand side of each picture is a set of contractions (or rather the results of applying these contractions on the unit square![$[0,1]^2$](//latex.artofproblemsolving.com/c/6/2/c6269f99f4a41006391c999d4c5f74b8a493ba63.png)
in 
); on the right hand side we get the result of applying iteratively.
Who ever knew math could be so pretty?
Theorem (Hutchinson, 1981) Let
be a complete metric space, and suppose 
are contractions. Then there exists a unique nonempty compact set 
such that ![\[K = \bigcup_{i=1}^nf_i(K).\]](http://latex.artofproblemsolving.com/f/8/9/f89bea14df0e4a9ef52f88a9da6eed001087d1a9.png)
Proof. For closed and bounded subsets
and 
of , define ![\[h(A,B) = \max\left\{\sup_{a\in A}\operatorname{dist}(a,B),\sup_{b\in B}\operatorname{dist}(b,A)\right\}\in[0,\infty)\]](http://latex.artofproblemsolving.com/6/2/7/6279907331e75505d0fd139c9a254fa5920b03ff.png)
to be the Hausdorff distance between and . It can be shown through a bit of work that this is actually a metric on the space of closed and bounded sets in . Denote by 
the resulting metric space. Additionally, let 
denote the metric space of all compact subsets of when endowed with 
as a metric.We first note a few properties of
. These were proven over the span of three days in class, and so I'll spare the majority of the details.- Suppose
is Lipschitz. Then ![\[h(f(A),f(B))\leq K(f)h(A,B),\]](//latex.artofproblemsolving.com/9/6/b/96b2590e66335fb23474dca0a5580d7799180048.png)
where 
denotes the Lipschitz constant of . - If
and 
are nonempty for some 
, then ![\[h\left(\bigcup_{i=1}^k A_i,\bigcup_{i=1}^k B_i\right)\leq\max_{1\leq i\leq k}h(A_i,B_i).\]](//latex.artofproblemsolving.com/5/d/4/5d4a310a18282ff9c6a0f9da6399f885060e8d86.png)
- If is complete, then is also complete. Similarly, if is totally bounded, then is also totally bounded.
- is closed in . Thus, combining this with the above, we get that complete
complete.
is Lipschitz. Then ![\[h(f(A),f(B))\leq K(f)h(A,B),\]](http://latex.artofproblemsolving.com/9/6/b/96b2590e66335fb23474dca0a5580d7799180048.png)
where 
denotes the 
and 
are nonempty for some 
,![\[h\left(\bigcup_{i=1}^k A_i,\bigcup_{i=1}^k B_i\right)\leq\max_{1\leq i\leq k}h(A_i,B_i).\]](http://latex.artofproblemsolving.com/5/d/4/5d4a310a18282ff9c6a0f9da6399f885060e8d86.png)
With these facts in hand, the proof is actually surprisingly short. Note that
complete implies 
complete. Furthermore, remark that if is compact, then 
is also compact, so in particular 
is a finite union of compact sets and is thus also compact.Define
via 
; by the previous paragraph, we know this function is well-defined. Let 
, 
be in , and for simplicity set 
to be the Lipschitz constant associated to 
for 
(which we know is in the interval 
since each is a contraction). Then 
Note that 
is the maximum of a bunch of real numbers less than 
and thus is itself less than . Thus, 
is also a contraction, and so the Banach fixed-point theorem guarantees the existence of a unique 
satisfying 
. 
Corollary 1. There is a simple way to generate this
: start with any set , and repeatedly iterate on it. Since is a contraction, the (Hausdorff) distance between 
and tends to zero as 
.Corollary 2. We can use this to generate fractals! Here are a few examples. On the left hand side of each picture is a set of contractions (or rather the results of applying these contractions on the unit square
![$[0,1]^2$](http://latex.artofproblemsolving.com/c/6/2/c6269f99f4a41006391c999d4c5f74b8a493ba63.png)
in 
); on the right hand side we get the result of applying iteratively.Who ever knew math could be so pretty?
April 2025
November 2024