next up previous
Next: Cluster Trees Up: Order of Magnitude Comparisons Previous: Examples

  
Order-of-magnitude spaces

An order-of-magnitude space, or om-space, is a space of geometric points. Any two points are separated by a distance. Two distances d and e are compared by the relation d << e, meaning ``Distance d is infinitesimal compared to e'' or, more loosely, ``Distance d is much smaller than e.''

For example, let R* be the non-standard real line with infinitesimals. Let R*m be the corresponding m-dimensional space. Then we can let a point of the om-space be a point in R*m. The distance between two points a,b is the Euclidean distance, which is a non-negative value in R*. The relation d << e holds for two distances d,e, if d/e is infinitesimal.

The distance operator and the comparator are related by a number of axioms, specified below. The most interesting of these is called the om-triangle inequality: If ab and bc are both much smaller than xy, then ac is much smaller than xy. This combines the ordinary triangle inequality ``The distance ac is less than or equal to distance ab plus distance bc'' together with the rule from order-of-magnitude algebra, ``If p << r and q << r then p+q << r.''

It will simplify the exposition below if, rather than talking about distances, we talk about orders of magnitude. These are defined as follows. We say that two distances d and e have the same order of magnitude if neither d << e nor e << d. In R*this is the condition that d/e is finite: neither infinitesimal nor infinite. (Raiman, 1990 uses the notation ``d Co e'' for this relation.) By the rules of the order-of-magnitude calculus, this is an equivalence relation. Hence we can define an order of magnitude to be an equivalence class of distances under the relation ``same order of magnitude''. For two points a,b, we define the function od(a,b) to be the order of magnitude of the distance from a to b. For two orders of magnitude p,q, we define p << q if, for any representatives d in p and e in q, d << e. By the rules of the order-of-magnitude calculus, if this holds for any representatives, it holds for all representatives. The advantage of using orders-of-magnitude and the function ``od'', rather than distances and the distance function, is that it allows us to deal with logical equality rather than the equivalence relation ``same order of magnitude''.

For example, in the non-standard real line, let d be a positive infinitesimal value. Then values such as { 1,100,2-50d+100d2...}, are all of the same order of magnitude, o1. The values { d,1.001d,3d+e-1/d...} are of a different order of magnitude o2 << o1. The values { 1/d,10/d+d5...} are of a third order of magnitude o3 >> o1.

Definition 1: An order-of-magnitude space (om-space) O consists of:

satisfying the following axioms:
A.1
For any orders of magnitude d,e in D, exactly one of the following holds: d << e, e << d, d = e.
A.2
For d,e,f in D, if d << e and e << f then d << f.
(Transitivity. Together with A.1, this means that << is a total ordering on orders of magnitude.)
A.3
For any d in D, not d << 0.
(0 is the minimal order of magnitude.)
A.4
For points a,b in P, od(a,b) = 0 if and only if a=b.
(The function od is positive definite.)
A.5
For points a,b in P, od(a,b) = od(b,a).
(The function od is symmetric.)
A.6
For points a,b,c in P, and order of magnitude d in D,
if od(a,b) << d and od(b,c) << d then od(a,c) << d.
(The om-triangle inequality.)
A.7
There are infinitely many different orders of magnitude.
A.8
For any point a1 in P and order of magnitude d in D, there exists an infinite set a2, a3 ... such that od( ai,aj) = d for all i <> j.

The example we have given above of an om-space, non-standard Euclidean space, is wild and woolly and hard to conceptualize. Here are two simpler examples of om-spaces:

I. Let d be an infinitesimal value. We define a point to be a polynomial in d with integer coefficients, such as 3 + 5d - 8 d5. We define an order-of-magnitude to be a power of d. We define dm << dn if m > n; for example, d6 << d4. We define od(a,b) to be the smallest power of d in a-b. For example, od(1+d2-3d3, 1-5d2+4d4) = d2.

II. Let N be an infinite value. We define a point to be a polynomial in N with integer coefficients. We define an order of magnitude to be a power of N. We define Np << Nq if p < q; for example, N4 << N6. We define od(a,b) to be the largest power of N in a-b. For example, od( 1+N2-3N3, 1-5N2+4N4) = N4.

It can be shown that any om-space either contains a subset isomorphic to (I) or a subset isomorphic to (II). (This is just a special case of the general rule that any infinite total ordering contains either an infinite descending chain or an infinite ascending chain.)

We will use the notation ``d <<= e'' as an abbreviation for ``d << e or d = e''.


next up previous
Next: Cluster Trees Up: Order of Magnitude Comparisons Previous: Examples