18.099: Problem Set 7

Due: Tuesday, November 25.

The problem set this time shows, in particular, that a finite set of contractions on euklidean space determines a unique fractal.

Let (X, d) be a metric space. A map f: X → X is called a contraction if there exists a constant 0 ≤ λ < 1 such that for all x, y ∈ X,

d(f(x), f(y)) ≤ λ · d(x, y).

Show that a contraction f: X → X on a complete metric space has a unique fixed point, that is, a point x ∈ X such that f(x) = x.

We shall apply the result above to the set K of non-empty compact subsets of ℝ^{n} (n ≥ 1 is fixed) equipped with the Hausdorff metric which we proceed to define. We define the distance from a point x ∈ ℝ^{n} to a non-empty compact subset K ⊂ ℝ^{n} to be

d(x, K) = inf{d(x, y) | y ∈ K} = min{d(x, y) | y ∈ K}.

And if ϵ ≥ 0, we define the ϵ-enlargement of a non-empty compact subset K ⊂ ℝ^{n} by

K_{ϵ} = {x ∈ ℝ^{n} | d(x, K) ≤ ϵ}.

Then, the Hausdorff distance between two non-empty compact subsets K, K′ ⊂ ℝ^{n} is defined to be

d(K, K′) = inf{ϵ ≥ 0 | K ⊂ K′_{ϵ} and K′ ⊂ K_{ϵ}}.

Show first that (K, d) is a metric space. Then show that this metric space is complete.

Prove the following result.

Theorem. Let f_{1}, …, f_{N}: ℝ^{n} → ℝ^{n} be a finite family of contractions. Then exists a unique non-empty compact subset K ⊂ ℝ^{n} such that

K = f_{1}(K) ∪ ⋯ ∪ f_{N}(K).