Agnes Scott College
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.

proof1pictures

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\).

proof2pictures

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\).