Classic Iterated Function Systems

Sierpinski Carpet

$$ C_0 \supset C_1 \supset C_2 \supset C_3 \supset \cdots $$

The Sierpinski carpet is \(\displaystyle \bigcap_{n=0}^\infty C_n\), the intersection of all the sets in this sequence, that is, the set of points that remain after this construction is repeated infinitely often. The figures below show the first four iterations. The squares in red denote some of the smaller congruent squares used in the construction.

\[ \begin{align} f_1 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} \\ f_2 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} 0 \\ {1/3} \\ \end{array}} \right] \\ f_3 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} 0 \\ {2/3} \\ \end{array}} \right] \\ f_4 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {1/3} \\ 0 \\ \end{array}} \right] \\ f_5 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {1/3} \\ {2/3} \\ \end{array}} \right] \\ f_6 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {0} \\ \end{array}} \right] \\ f_7 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {1/3} \\ \end{array}} \right] \\ f_8 ({\bf{x}}) &= \left[ {\begin{array}{*{20}c} {1/3} & 0 \\ 0 & {1/3} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}c} {2/3} \\ {2/3} \\ \end{array}} \right] \\ \end{align} \]

The Sierpinski carpet consists of eight self-similar pieces corresponding to the eight functions in the iterated function system.

[Enlarge]

This will produce the Sierpinski carpet rotated by 45°. In addition, there will be lines through the square "holes" (see first animation). If you want to avoid those lines, you can modify the L-system to lift the pen by using

F —> F+F−F−F−UGD+F+F+F−F

where U means the pen goes up and D means the pen goes down. You can see the effect in the second animation.

$$\sum\limits_{k = 1}^8 {{r^d}} = 1\quad \Rightarrow \quad d = \frac{{\log (1/8)}}{{\log (r)}} = \frac{{\log (1/8)}}{{\log (1/3)}} = \frac{{\log (8)}}{{\log (3)}} = 1.89279$$

The Sierpinski carpet is uncountable. [Uncountability Details]

The interior of the Sierpinski carpet is empty. Let \(P = (x,y)\) be a point in the Sierpinski carpet and let \(\varepsilon > 0\). Choose an integer \(k\) satisfying \(\frac{\sqrt{2}}{3^k} \lt \varepsilon\). Write the infinite ternary expansions of \(x\) and \(y\) as $$x = x_1x_2x_3x_4\ldots{}_{\small 3}, \quad y = y_1y_2y_3y_4\ldots{}_{\small 3}$$ where an infinite string of 0's is used if either expansion terminates. Define a new point \(P' = (x',y')\) whose coordinates have the same ternary expansion as \(x\) and \(y\) except that \(x'_k =1\) and \(y'_k=1\). Then \(P \ne P'\) and \(P'\) is not in the Sierpinski carpet.

If \(x_k \ne 1\) and \(y_k \ne 1\), then \(|x-x'| = |y - y'| = \frac{1}{3^k}\). Therefore $$d(P,P') = \sqrt { (x-x')^2 + (y-y')^2} = \frac{\sqrt 2}{3^k}.$$

If either \(x_k = 1\) or \(y_k = 1\) (they both can't equal 1 since \(P\) is in the Sierpinski carpet), then one of \(|x-x'|\) or \(|y-y'|\) is equal to 0 and the other is equal to \(\frac{1}{3^k}\). Therefore $$d(P,P') = \sqrt { (x-x')^2 + (y-y')^2} = \frac{1}{3^k}.$$ In either case, \(d(P,P') \lt \varepsilon\). So no matter how small an open ball you draw around any point in the Sierpinski carpet, that ball will always contain another point that is not in the Sierpinski carpet. This shows that the Sierpinski carpet has an empty interior.

The Sierpinski carpet has area 0. Suppose the area of the original square $C_0$ is equal to 1. To get $C_{k+1}$, we scale $C_k$ by 1/3, which reduces the area by $1/9 = (1/3)^2$. But we make 8 copies of this scaled version to form $C_{k+1}$. Therefore the area of $C_{k+1}$ must be (8/9)th of the area of $C_{k}$. This means that the area of $C_{n}$ is $(8/9)^n$ for all $n$. Notice that these areas go to 0 as $n$ goes to infinity.

Another way to compute the area of the Sierpinski carpet is to compute the area of the holes using self-similarity. Suppose that the initial square covering the carpet has area 1 (as we did with $C_0$ above.) Let \(A\) be the area of the complement of the carpet, that is, all the holes not in the carpet. The area of the square removed at the first iteration is 1/9. The holes remaining in each of the other 8 squares is self-similar to those in the carpet, but scaled by a factor of 1/3. Their total area is therefore scaled by a factor of 1/9. Hence the area of all the holes is \(A = \frac{1}{9}+8\left(\frac{1}{9}A\right)\). Then $$A = \frac{1}{9}+\frac{8}{9}A \Rightarrow \frac{1}{9}A = \frac{1}{9} \Rightarrow A = 1.$$ Thus the holes have the same area as the covering square, whence Sierpinski's carpet has area 0. This means that we have removed "all" of the area of the original square in constructing the Sierpinski carpet. But of course there are many points still left in the carpet since the carpet is uncountable in size. That is one reason why area is not a useful dimension for this set.

Universality. Sierpinski used the carpet to catalogue all compact one-dimensional objects in the plane (from a topological point of view). What this basically means is that the Sierpinski carpet contains a topologically equivalent copy of any compact one-dimensional object in the plane. Thus for any curve contained in the plane, there is a set homeomorphic to the Sierpinski carpet that contains the curve. This is why the carpet is sometimes referred to as the Sierpinski curve. Additional topological characterizations of the Sierpinski carpet/curve can be found in the article by Whyburn [10], the text by Peitgen, Jurgens, and Saupe [8], or the topology text by Engelking and Sieklucki [2].

In an article written in 1916, Sierpinski wrote [1]:

Note that as early as one year ago Mr. Mazurkiewicz found an example of a curve which was simultaneously a Jordan curve and a Cantor curve...Mazurkiewicz forms this curve by dividing the square into nine smaller squares using lines parallel to the sides and removing the interior of the center square, performing the same procedure on each of the remaining eight square, and iterating this procedure ad infinitum.