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 pth 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.