Editing Iterated function system (section)

==Properties==
[[File:Chaosgame.gif|thumb|right|250px|Construction of an IFS by the [[chaos game]] (animated)]]
[[File:Ifs-construction.png|thumb|IFS being made with two functions.]]
Hutchinson showed that, for the metric space <math>\mathbb{R}^n</math>, or more generally, for a complete metric space <math>X</math>, such a system of functions has a unique nonempty [[Compact space|compact]] (closed and bounded) fixed set ''S''.<ref name=hutchinson>{{cite journal |last=Hutchinson |first=John E. |title=Fractals and self similarity |journal=Indiana Univ. Math. J. |volume=30 |year=1981 |pages=713–747 |doi=10.1512/iumj.1981.30.30055 |url=https://maths-people.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf |issue=5|doi-access=free }}</ref> One way of constructing a fixed set is to start with an initial nonempty closed and bounded set ''S''<sub>0</sub> and iterate the actions of the ''f''<sub>''i''</sub>, taking ''S''<sub>''n''+1</sub> to be the union of the images of ''S''<sub>''n''</sub> under the ''f''<sub>''i''</sub>; then taking ''S'' to be the [[Closure (topology)|closure]] of the limit <math>\lim_{n \rightarrow \infty} S_n</math>. Symbolically, the unique fixed (nonempty compact) set <math>S\subseteq X</math> has the property
:<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
The set ''S'' is thus the fixed set of the [[Hutchinson operator]] <math>F: 2^X\to 2^X</math> defined for <math>A\subseteq X</math> via
:<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>

The existence and uniqueness of ''S'' is a consequence of the [[contraction mapping principle]], as is the fact that
:<math>\lim_{n\to\infty}F^{n}(A)=S</math>
for any nonempty compact set <math>A</math> in <math>X</math>. (For contractive IFS this convergence takes place even for any nonempty closed bounded set <math>A</math>). Random elements arbitrarily close to ''S'' may be obtained by the "chaos game," described below.

Recently it was shown that the IFSs of non-contractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in ''X'') can yield attractors.
These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>

The collection of functions <math>f_i</math> [[Generating set|generates]] a [[monoid]] under [[Function composition|composition]]. If there are only two such functions, the monoid can be visualized as a [[binary tree]], where, at each node of the tree, one may compose with the one or the other function (''i.e.'' take the left or the right branch). In general, if there are ''k'' functions, then one may visualize the monoid as a full [[k-ary tree|''k''-ary tree]], also known as a [[Cayley tree]].