Show that if $f_i: X \to X$ are contractions on a metric space $X$, then $F(K)=\bigcup_{i=1}^N f_i(K)$ is a contraction on $\mathcal{H}(X)$.

Question

Show that if $f_i: X \to X$ are contractions, then $F: \mathcal{H}(X) \to \mathcal{H}(X)$ defined by $F(K)=\bigcup_{i=1}^N f_i(K)$ is a contraction on $\mathcal{H}(X)$, where $\mathcal{H}(X)$ is the metric space consisting of all nonempty compact sets of $X$ with the Hausdorff distance.

Proof:

Induction on $N$.

Base Case: $N=2$. Suppose $A, B \in \mathcal{H}(X)$, then $F(A)=f_1(A)\cup f_2(A), F(B)=f_1(B)\cup f_2(B)$.

$d_{\mathcal{H}}(F(A), F(B))=\max\{\underset{x \in F(A)}\sup{d(x, F(B))}, \underset{y \in F(B)}\sup{d(y, F(A))}\}$, $d_{\mathcal{H}}(A, B)=\max\{\underset{a \in A}\sup{d(a, B)}, \underset{b \in B}\sup{d(b, A)}\}$. Screeching halt.

Any HINT would be appreciated.

Answer 1

Actually the base case is $N=1$, for which the proof is not difficult. You might be able to work it out on your own.

$\\$

Think about the following: what can you say the Hausdorff distance between $A$ and $B\cup C$, where all three sets $A,B,C$ are compact? We'll try to compare $d_\text{Haus}(A,B\cup C)$ on the one hand, with $d_\text{Haus}(A,B)$ and $d_\text{Haus}(A,C)$ on the other hand.

If you take an arbitrary $a\in A$, is it possible for $d(a,B\cup C)$ to be greater than $d(a,B)$? Of course not. If the set $B$ gets as close as some distance $r$ from the point $a$, then the set $B\cup C$ gets at least as close or possibly closer to the point $a$.

Therefore, $\max_{a\in A}d(a,B\cup C)\leq\max_{a\in A}d(a,B)$.

For the same reason, $\max_{a\in A}d(a,B\cup C)\leq\max_{a\in A}d(a,C)$.

As for $d(x,A)$ where $x\in B\cup C$, we can ask whether this distance is maximised for $x\in B$ or for $x\in C$.

If it is maximised for $x\in B$, then $\max_{x\in B\cup C}d(x,A)\leq \max_{x\in B}d(x,A)$. We could combine this with the above to get $d_\text{Haus}(A,B\cup C)\leq d_\text{Haus}(A\cup B)$.

If instead it is maximised for $x\in C$, then for the same reason, $d_\text{Haus}(A,B\cup C)\leq d_\text{Haus}(A\cup C)$.

The big conclusion at the end of all these computations is that $d_\text{Haus}(A,B\cup C)\leq \max\{d_\text{Haus}(A, B),d_\text{Haus}(A,C)\}$.

Such a lemma will help you prove the inductive step.