Metric spaces

 

Throughout our discussions, we must fix a space X of points in which to work. The space may be the plane , or genuine three-dimensional space , or for that matter any euclidean space , or then again something quite different. In our study of L-systems and symbolic dynamics, there is an underlying space of symbolic trajectories. Recall that we have an alphabet V of symbols. To that alphabet, we also add a ``space'' character which we will represent by the programmer's convention of . Then a trajectory is an infinite sequence of symbols chosen from V:

The finite words we considered earlier are trajectories which end with an infinite sequence spaces. We say two trajectories and are equal if they agree term-by-term, i.e. for all n. The space of all trajectories is denoted (``code-space'' in Barnsley [Bar93]).

For , here are some examples of trajectories

• a itself, which as a sequence is
• ba, which as a sequence is
• , the limiting sequence in the Fibonacci L-system.

So far, the ``spaces'' we have defined have no structure other than as a set of objects. For the purpose of dynamics, though, we must introduce two further notions: the idea of what it means for two points to be ``close'' to each other and the notion of a well-behaved mapping from the space into itself.

Closeness can be measured in various ways. The crucial element is a distance function d(x,y). We have already discussed the usual notion of distance in given by Pythagoras' formula (see the section on Euclidean similarities). The actual formula for distance is not always of such great importance. What is important are three fundamental properties that all distance functions share. A distance function on a space X is a function d(x,y) on pairs of points which returns a nonnegative real value and which satisfies:

Positivity:

d(x,y)>0 unless x=y in which case d(x,x)=0.

Symmetry:

d(x,y)=d(y,x).

Triangle Inequality:

For all , . (The distance along two sides of a triangle is always at least as far as the distance along the remaining side.)

The technical term for a distance function is a metric, and a space equipped with a metric is called a metric space.

To give an example of an unusual metric, we will define one for the Fibonacci code-space . Intuitively, we might think that two trajectories are close if they agree for many terms. We may turn that notion into a metric as follows. Let and be two trajectories. Suppose , , ..., , and . That means the two trajectories agree for the first N terms. Then we define

The choice of is somewhat arbitrary; we simply need a function of N tending to . If , our formula should be interpreted as . If , we define in accordance with the positivity requirement.

We may quickly prove that with this distance function code-space qualifies as a metric space. First of all, it's all arranged that positivity is satisfied, since is always positive and distance 0 occurs precisely when the two trajectories are the same. Symmetry is true because equality of terms as well as inequality are symmetric relations, that is, if then . Transitivity is the trickiest condition to verify. We must choose three trajectories , , and . Suppose and agree up to the N-th term, and and agree up to the M-th term. This means for , and for . Then and . The terms serve as an intermediary for comparing and ; we can conclude if it's true that and . Thus, and agree for at least the first terms. Then

Since the maximum of two nonnegative numbers is certainly less than or equal to their sum, this inequality is even better than the triangle inequality. It is commonly called the ultrametric inequality.

Once we have a metric it is possible to reproduce many of the concepts that occur in calculus, in particular the central idea of limit. Suppose is a sequence in our metric space. (In code-space, for example, each would itself be a trajectory.) We say the limit of this sequence is if and only if

The above limit is defined in the same way the limit of any sequence of nonnegative numbers is defined.

Limits in euclidean space are fairly familiar. However, we have already encountered more exotic limits in our discussion of L-systems. For example, let be the sequence of generations in the Fibonacci L-system, so that , , , etc. We have seen that these generations satisfy the chain law , and that the length of is , the n-th Fibonacci number. The limit trajectory is defined to agree with up to the length of . Thus, . Since the Fibonacci numbers tend to infinity, we conclude that in accordance with our definition. Whew! Consistency is such a relief.