A **space** is a set; we use the term space when we associate a structure with the set.

A **metric** on a nonempty set X is a function d(.,.) such that, if x and y are elements of X,
*i*) d(x,y)=d(y,x) (symmetry), *ii*) d(x,y)>=0 and d(x,y)=0 iff x=y
(positive definiteness), and *iii*) d(x,y)=<d(x,z)+d(y,z) for any z in X
(triangle inequality). The metric is a notion of distance on X.

Every nonempty set admits a metric; for example, d(x,y)=1 if x and y are distinct, and
d(x,x)=0, is a metric on any nonempty set. The **lp metric** (p>=1) on Rn is the p*th*
root of the sum of (x(i)-y(i))^p, for x and y in Rn; the limiting case (as p tends to infinity)
is the sup metric, max(abs(x(i)-y(i))). The case p=1 is called the **taxicab metric**.

A **metric space** (X,d) is a nonempty set X together with a metric d on X.

A **Cauchy sequence** in a metric space (X,d) is a sequence {x(n)} of points in X such that,
for any eps>0, there is a N>0 such that d(x(n),x(m))<eps for all n,m>N. A
point x in X is the **limit** of a sequence {x(n)} in X if for any eps>0, there is a N>0
such that d(x(n),x)<eps for all n>N; we say that {x(n)} is **convergent** (to x). All
convergent sequences in (X,d) are Cauchy.

If all Cauchy sequences in (X,d) are convergent, then (X,d) is said to be **complete**.

The **epsilon ball** in X, centered at x, is the set B(x,epsilon)={y in X: d(x,y)<epsilon}
(epsilon positive).

A subset S of X is **open** in (X,d) if for every x in S there is an eps>0 such that B(x,eps)
is a subset of S (that is, B(x,eps) is contained entirely in S). A **limit point** (or
**cluster point**)
of S is a point in X such that x is the limit of some sequence {x(n)} lying entirely in S (with x(n) not equal
to x for any n). A
subset S of X is **closed** if it contains all of its limit points. A subset of (X,d) may be
both open and closed; the empty set and X itself are always both open and closed in (X,d).

The **closure** of a subset S of (X,d) is the union of S with its limit points. The set S is closed
(in (X,d)) iff it is equal to its closure. The set S is open iff its complement X\S is closed. If S is equal to
the set of its limit points it is said to be a
**perfect** set.

The **boundary** of S, del S, is the set of all points common to the closure of S and the closure of its complement
X\S. The **interior** of a set S, int S, is the set of all x in S such that B(x,eps) is in S for some eps>0.
The **exterior** of S, ext S, is the complement of the union of the disjoint sets del S and int S. Hence
for any subset S of X, the sets del S, int S, and ext S (any but not all of which may be empty) **partition** X, that is,
X is the union of these pairwise disjoint sets.

An **open cover** of a subset S of (X,d) is a collection of open sets in X such that S is
contained in their union. A **countable** set is one which either has finitely many elements or which is **countably infinite**,
which means that its elements can be put into a one-to-one correspondence with the natural numbers. A **countable open cover** is an open cover consisting of countably many open sets.

A metric space (X,d) is **compact** if any open cover of X contains a finite open cover. A subset S of
(X,d) is compact in X if (S,d) is a compact metric space with respect to the open sets inherited from (X,d), intersected
with S. Equivalently, S is compact iff every infinite sequence {x(n)} in S contains a subsequence which is convergent
in S. In Rn a set is compact iff it is closed and bounded.

A **topological space** (X,T) is a nonempty set X together with a collection T of subsets of X such that
*i*) the empty set and X are in T, *ii*) the union of arbitrarily many sets in T is in T, and *iii*) the intersection
of finitely many sets in T is in T. We refer to T as the **topology** of (or on) the space X, and the sets in T
are by definition the **open sets** in (X,T). Every metric space is a topological space with respect to
the open sets T defined by the metric, but not every topological space admits a metric which is consistent with the
open sets as defined by the topology T.

If (X,T) is a topological space and x and y are in X, we say that x and y are **separated** if there are
open sets A, B in T such that x is in A, y is in B, and A and B are disjoint. If every two distinct points in (X,T)
are separated we say that (X,T) has the **separation property** and that it is a **Hausdorff space**;
every metric space is a Hausdorff space.

A topological space (X,T) is **connected** if the empty set and X are the only subsets of X which are
both open and closed. Equivalently, (X,T) is connected iff it is not possible to partition X into two nonempty disjoint
open subsets of X.

If (X,d1) and (Y,d2) are metric spaces and f:X->Y is a mapping from (X,d1) to (Y,d2), then the **image** of
a subset H of X is the set of all y in Y such that y is equal to f(x) for some x in H; the
**preimage** of a subset G of Y, under f, is the set of all
x in (X,d1) such that f(x) is in G (denoted f^-1(G)). The mapping f is said to be **continuous** if for every
open subset G of (Y,d2) the preimage of G under f is an open subset in (X,d1). Continuity, connectedness, and
compactness are the three fundamental concerns of topology.

If (X,d) is a complete metric space, then the set of all nonempty compact subsets of it, H(X), is the corresponding
**space of fractals** (in the sense of Barnsley). Not every element of H(X) will be a fractal.

We define the **distance from a point to a set**, for x in a complete metric space (X,d) and B in H(X),
by d(x,B)=min{d(x,y): y in B}. This is well-defined. We define the **distance from a set A to a set B** by
s(A,B)=max{d(x,B): x in A} for A, B in H(X). Again, this
is well-defined, but it is not symmetric and hence is not a metric. We define the **Hausdorff metric** on H(X) to be
h(A,B)=max{s(A,B),s(B,A)}; then (H(X),h) is a metric space and is in fact complete.

If S is a subset of X then the **epsilon dilation** (or **epsilon collar** if S is also in H(X)) of S is the set of all y in X such that d(x,y)=<epsilon
for some x in S. If A and B are in H(X) then h(A,B) is at most epsilon iff A is contained in the epsilon dilation of B and B
is contained in the epsilon dilation of A. Hence h(A,B)=inf{epsilon: A is in the epsilon dilation of B and B is in the epsilon
dilation of A}. This is an alternative characterization of the Hausdorff metric.

A **transformation** on (X,d) is a mapping f:X->X which assignes exactly one value f(x) in X to every x in X. A
transformation on X is said to be **onto** (or **surjective**) if f(X)=X; it is said to be **one-to-one**
(or **injective**) if f(x)=f(y) implies x=y. A transformation on X is said to be **bijective** (or a
**bijection**) if it is one-to-one and onto. A continuous bijection is called a **homeomorphism**; in
this case f is invertible, and y=f^-1(x) is also a homeomorphism.

An **affine** map in Rn is a map of the form y=Ax+b where A is a nxn matrix and b is a n-vector. If b=0 the map is
**linear**; otherwise, the affine map may be viewed as a linear map x->Ax followed by a translation by b. If S is a
set in Rn then the transformed set has area equal to the absolute value of the determinant of A times the area of S; we call |A|
the **Jacobian** (or Jacobian determinant) of the map in this context. If A=rI for some scalar r we say that A is a
**scalar** matrix. The **spectral radius** of a matrix is the largest modulus of any element in its **spectrum**,
that is, its set of eigenvalues.

We write f^n for the n-fold composition of f, and define the **forward orbit** of a point x0 to be O^+(x0)={x0,f(x0),f^2(x0),...}.
We define the **backward orbit** of a point x0 to be O^-(x0)={x0,f^-1(x0),f^-2(x0),...}. The **full orbit** of x0, denoted O(x0), is
the union of these sets. The values in O^+(x0) are called the **forward iterates** of x0 under f, and those in
O^-(x0) are called the **backward iterates** of x0 under f.

A **fixed point** of a transformation f is a point x in X such that f(x)=x. An **invariant set** is a subset S
of X such that f(S)=S. The **Fixed Point Theorem** gives conditions under
which a fixed point must exist for a given map and the forward iterates of any point under that map must converge
to that fixed point.

A transformation f on (X,d) is said to be **contractive**, or a **contraction mapping**, if
there is an s in [0,1) such that d(f(x),f(y))=<d(x,y) for all x,y in X, and s is called a **contractivity factor** for f.
The infimum of all such s is also a contractivity factor for f. The **Contraction Mapping Theorem** states that if
f is contractive on a nonempty complete metric space (X,d) then f possesses a unique fixed point in X and the
forward iterates of any x in X converge to that fixed point. Contraction mappings are always continuous.

A **Hutchinson map** W on H(X) is a transformation on H(X) which is the union of
one or more transformations on X. Typically those transformations on X, called the **component** maps of W, are contraction mappings on X.
If so then W is contractive on H(X) and a contractivity factor for it is the maximum of the contractivity factors
of the component maps (on X).

If (X,d1) and (Y,d2) are metric spaces and f:X-Y, then f is said to be an **isometry** if
d(f(x1),f(x2))=d(x1,x2) for all x1,x2 in X. Isometries preserve metric properties as homeomorphisms
preserve topological properties. If (X,d1) and (Y,d2) are metric spaces and f:X-Y, then f is said to be a **similarity** if
there is an r>0 such that d(f(x1),f(x2))=rd(x1,x2) for all x1,x2 in X; r is called the **ratio**
of f.

A **ratio list** is a finite list of positive numbers (r1,...,rn). An **iterated function system** (IFS) realizing a
ratio list is a list of maps (f1,...fn), each of which is a contraction mapping on X with contractivity factor
(r1,...,rn) respectively; a **self-similar IFS** is one for which each of (f1,...,fn) is a
similarity with ratio (r1,...,rn), respectively. The ratio of an IFS is max{r1,...,rn}. We associate the
IFS (f1,...,fn) with the Hutchinson map with components f1,...,fn. If its ratio is less than one then it is contractive
on H(X).

A ratio list is said to be **contracting** (or **hyperbolic**) if each of r1,...,rn is less than
one. The corresponding IFS is then also said to be contracting (or hyperbolic). For a hyperbolic
self-similar IFS we define the **dimension associated with the ratio list** (r1,...,rn) to be
the unique solution d of r1^d+r2^d+...+rn^d=1; d is non-negative, and d=0 iff n=1. Under appropriate conditions,
d is the self-similarity dimension of the attractor of the IFS.

A **condensation transformation** on H(X) is a transformation w0:H(X)->H(X) defined by w0(x)=Y for all x
in H(X), where Y in H(X) is some fixed element of H(X); that is, w0 maps every element of H(X) to Y. (We also
refer to w0 simply as a **condensation**.) A condensation transformation is contractive with
contractivity factor zero. The set Y is called the **condensation set**. If we add a
condensation transformation f0 to a hyperbolic IFS (f1,...,fn) we say that (f0,f1,...,fn) is a
**hyperbolic IFS with condensation**; its ratio is the same as for (f1,...,fn).

The **Collage Theorem** describes how to construct a hyperbolic IFS which has as its unique invariant
set a given element K of H(X); we refer to K as the **target image**.

*Maintainer*: leader@wilbur.rose-hulman.edu.

*Home e-mail*: JeffLeader@MindSpring.com.