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 \subseteq {N_r}(B) \text{ and } B \subseteq {N_r}(A)} \right\}\]
where for a set $W$, $N_r(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) \lt \varepsilon \;\text{ if and only if }\; A \subset {N_\varepsilon}(B) \text{ and } B \subset {N_\varepsilon}(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 \(\varepsilon \gt 0\). There is an integer \(k\) such that \(D(B,B_n) \lt \varepsilon/2\) for all \(n \ge k\). Therefore
\[B_n \subset N_{\varepsilon/2}(B) \, \text{ and } \, B \subset N_{\varepsilon/2}(B_n) \, \text{ for } n \ge k.\]
Let \(n \ge k\). Then \(B_{k} \cup \dots \cup B_{n} \subset N_{\varepsilon/2}(B)\). This means that
\[A_{n} = A_{k-1} \cup B_{k} \cup \dots \cup B_{n} \subset N_{\varepsilon/2}(A_{k-1} \cup B).\]
Now \(A_{k-1} \subset A_{n}\) and so \(A_{k-1} \subset N_{\varepsilon/2}(A_{n})\). But we also have \(B \subset N_{\varepsilon/2}(B_n)\) and \(B_n \subset A_{n}\), hence \(B \subset N_{\varepsilon/2}(A_{n})\). Thus
\[A_{k-1} \cup B \subset N_{\varepsilon/2}(A_{n}).\]
This shows that \(D(A_{n},A_{k-1} \cup B) \lt \varepsilon/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) lt \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon.\]
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\).
