

![0_image_0.png](0_image_0.png)

Note that the set of any single element of P is trivially a cluster of P . The entire set P
is likewise a cluster of P . The empty set is by definition not a cluster of P .

Lemma 1: If C and D are clusters of P then either C ⊂ D , D ⊂ C , or C and D are disjoint.

Proof: Suppose not. Then let x E C N D, y E C - D, z E D - C. Since C is a cluster, od( x, y ) ≪ od( x, z ).  Since D is a cluster, od( x, z ) ≪ od( x, y ).  Thus we have a contradiction.

口 By virtue of lemma 1, the clusters of a set P form a tree. We now develop a representation of the order of magnitude relations in P by constructing a tree whose nodes correspond to the clusters of P , labelled with an indication of the relative size of each cluster.

Definition 3: A cluster tree is a tree T such that
- Every leaf of T is a distinct symbol.

- Every internal node of T has at least two children.

- Each internal node of T is labelled with a non-negative value. Two or more nodes may be given the same value. (For the purposes of Sections 5-7, labels may be taken to be non-negative integers; in Section 8, it will be useful to allow rational labels.)
- Every leaf of the tree is labelled 0.

- The label of every internal node in the tree is less than the label of its parent.
For any node N of T the field "N symbols" gives the set of symbols in the leaves in the subtree of T rooted at N , and the field "N .label" gives the integer label on node N .