Larry Riddle, Agnes Scott College

## Convergence of an IFS that includes the Identity Map

The Hausdorff distance between two compact sets A and B is given by

$D(A,B) = \inf \left\{ {r:A \subset {N_r}(B) \text{ and } B \subset {N_r}(A)} \right\}$

where for a set W, Nr(W) is the r-envelope of W; that is, the set of all points that are within a distance r of some point in W. In particular,

$D(A,B) < \epsilon \;\text{ if and only if }\; A \subset {N_\epsilon}(B) \text{ and } B \subset {N_\epsilon}(A).$

Let $$G$$ be an IFS of contractive maps. Without loss of generality, we can assume that $$G$$ consists of two maps $$f_1$$ and $$f_2$$ (the argument below is the same for any number of contractive maps). Let $$F$$ be the IFS consisting of the functions in $$G$$ along with the identity map $$f(A) = A$$.

Let $$A_0$$ be any initial compact set. Define $$A_n = F(A_{n-1})$$ for $$n \ge 1$$. Let $$B_0 = A_0$$ and define $$B_n = G(B_{n-1})$$ for $$n \ge 1$$. Note that

$B_1 = G(A_0) = f_1(A_0) \cup f_2(A_0).$

and

$A_1 = F(A_0) = f_1(A_0) \cup f_2(A_0) \cup A_0 = B_0 \cup B_1.$

Similarly, we can see that \begin{align} A_2 &= F(A_1) = F(B_0 \cup B_1) \\ \\ &= f_1(B_0) \cup f_2(B_0) \cup B_0 \cup f_1(B_1) \cup f_2(B_1) \cup B_1 \\ \\ &= B_1 \cup B_0 \cup B_2 \cup B_1 \\ \\ &= B_0 \cup B_1 \cup B_2. \end{align}

The illustration below shows these first two iterations using the Pythagorean Tree IFS as an example.

In general, we can show by induction that

$A_n = B_0 \cup B_1 \cup B_2 \cup \dots \cup B_n.$

In particular, this also means that

$A_{n} = A_{k-1} \cup B_{k} \cup \dots \cup B_{n} \; \text{ for } n \ge k.$

Since the iterated function system $$G$$ consists of contractive maps, the sets $$B_n$$ converge in the Hausdorff metric to a unique fixed set $$B$$. Let $$\epsilon > 0$$. There is an integer $$k$$ such that $$D(B,B_n) < \epsilon/2$$ for all $$n \ge k$$. Therefore

$B_n \subset N_{\epsilon/2}(B) \, \text{ and } \, B \subset N_{\epsilon/2}(B_n) \, \text{ for } n \ge k.$

Let $$n \ge k$$. Then $$B_{k} \cup \dots \cup B_{n} \subset N_{\epsilon/2}(B)$$. This means that

$A_{n} = A_{k-1} \cup B_{k} \cup \dots \cup B_{n} \subset N_{\epsilon/2}(A_{k-1} \cup B).$

Now $$A_{k-1} \subset A_{n}$$ and so $$A_{k-1} \subset N_{\epsilon/2}(A_{n})$$. But we also have $$B \subset N_{\epsilon/2}(B_n)$$ and $$B_n \subset A_{n}$$, hence $$B \subset N_{\epsilon/2}(A_{n})$$. Thus

$A_{k-1} \cup B \subset N_{\epsilon/2}(A_{n}).$

This shows that $$D(A_{n},A_{k-1} \cup B) < \epsilon/2$$ for all $$n \ge k$$. So if $$n,m \ge k$$, then

$D(A_n,A_m) \le D(A_n,A_{k-1} \cup B) + D(A_{k-1} \cup B, A_m) < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon.$

Therefore the sequence of sets $$A_n$$ is a Cauchy sequence in the Hausdorff metric and hence the sets converge to a limit.

### Alternative Approach: IFS with Condensation

Start with the IFS of contractive maps $$f_1$$ and $$f_2$$ and the initial set $$A_0$$ as described above. Define the constant map $$f_0$$ by $$f_0(A) = A_0$$ for all compact sets $$A$$. The contractive map $$f_0$$ is called a condensation transformation and $$A_0$$ is the associated condensation set.

We now define a new iterated function system $$H$$ with condensation consisting of the contractions $$\{f_0, f_1, f_2\}$$ so that

$H(A) = f_1(A) \cup f_2(A) \cup A_0$

for all compact sets $$A$$. There is a unique fixed attractor $$C$$ for this IFS (note that the set $$C$$ depends on the choice of the condensation set $$A_0$$). Define $$C_0 = A_0$$ and $$C_{n+1} = H(C_n)$$ for $$n \ge 1$$. Then the sets $$C_n$$ converge to $$C$$.

Let $$F$$ be the IFS given above that includes the maps $$\{f_1, f_2\}$$ and the identity map, so

$F(A) = f_1(A) \cup f_2(A) \cup A.$

Define $$A_n = F(A_{n-1})$$ as in the first section above. We claim that the sets $$A_n$$ also converge to the attractor $$C$$. This is a result of the following claims.

Claim 1: $$C_n \subset C_{n+1}$$ for all n. To see why, first note that

$C_1 = H(C_0) = f_1(C_0) \cup f_2(C_0) \cup A_0 = f_1(C_0) \cup f_2(C_0) \cup C_0 \supset C_0.$

Now assume that $$C_{n-1} \subset C_n$$. Then $$f_k(C_{n-1}) \subset f_k(C_{n})$$ for k = 1 and 2, and so

$C_{n} = f_1(C_{n-1}) \cup f_2(C_{n-1}) \cup A_0 \subset f_1(C_{n}) \cup f_2(C_{n}) \cup A_0 = C_{n+1}.$

The claim now follows from induction.

Claim 2: $$A_n = C_n$$ for all n. This is certainly true for n = 0. Assume the claim is true for all k ≤ n. Then

\begin{align} A_{n+1} &= F(A_n) = f_1(A_n) \cup f_2(A_n) \cup A_n \\ \\ &= f_1(A_n) \cup f_2(A_n) \cup f_1(A_{n-1}) \cup f_2(A_{n-1}) \cup A_{n-1} \\ \\ &= f_1(A_n) \cup f_2(A_n) \cup \dots \cup f_1(A_0) \cup f_2(A_0) \cup A_0\\ \\ &= \bigcup_{k=0}^n \left(f_1(A_k) \cup f_2(A_k) \right) \cup A_0 \\ \\ &= \bigcup_{k=0}^n \left(f_1(C_k) \cup f_2(C_k) \right) \cup A_0 \\ \\ &= \bigcup_{k=0}^n \left(f_1(C_k) \cup f_2(C_k) \cup A_0 \right) \\ \\ &= \bigcup_{k=0}^n C_{k+1} = C_{n+1} \end{align}

with the last equality following from Claim 1. Claim 2 now follows from induction. Since the sets $$C_n$$ converge to $$C$$, so do the sets $$A_n$$.