Proof of lemma 2

Lemma 2:  If T is a cluster tree and O is an om-space, then instantiate(T,O) returns an instantiation of T.

Proof: Let d₀ = 0. For any node N, if i=N.label, we define d(N) = d_i. The proof then proceeds in the following steps:

i.

For any nodes M,N, if M is a descendant of N in T then od(G[M],G[N]) <<= d(N). Proof: If M is a child of N, then this is immediate from the construction of x₂ ... x_p in instantiate1. Else, let N=N₁, N₂ ... N_q=M be the path from N to M through T. By the definition of a cluster tree, it follows that N_i.label < N.label, for i > 1 and therefore d(N_i) << d(N). Thus od(G[M],G[N]) <<= (by the o.m.-triangle inequality) max_{i=1 ... q-1}(od( G[N_i+1],G[N_i])) <<= max_{i=1 ... q-1}(d(N_i)) (since N_i+1 is the child of N_i) <<= d(N).

ii.

Let N be a node in T; let C₁ and C₂ be two distinct children of N; and let M₁ and M₂ be descendants of C₁ and C₂ respectively. Then od( G[M₁], G[M₂]) = d(N). Proof: By the construction of x₂ ... x_p in instantiate1(N), od( G[C₁],G[C₂]) = d(N). By part (i.), od( G[M₁],G[C₁]) <<= d(C₁) << d(N) and likewise od( G[M₂],G[C₂]) << d(N). Hence, by axiom A.6, od( G[M₁], G[M₂]) = d(N).

iii.

Let a and b be any two leaves in T, and let N be the least common ancestor in T of a and b. Then od( G[a], G[b]) = d(N). Proof: Immediate from (ii).

iv.

For any node N, odiam(Z(N)) = d(N). Proof: From (iii), any two leaves descending from different children of N are at a distance of order d(N), and no two leaves of N are at a distance of order greater than d(N).

v.

For any node N, Z(N) is a cluster of Z(T). Proof: Let a and b be leaves of N, and let c be a leaf of T - N. Let I be the common ancestor of a and b in T and let J be the common ancestor of a and c. Then I is either N or a descendant of N and J is a proper ancestor of N. Therefore by part (i), d(I) << d(J). But by (iii), od( Z(a), Z(b)) = d(I) << d(J) = od(Z(a),Z(c)).

vi.

For any internal nodes N,M if M.label < N.label then odiam(Z(M)) << odiam(Z(N)). Proof: Immediate from (iv) and the construction of d.

vii.

If C is a cluster of Z(T) then there is a node N in T such that C=Z(N).
Proof: Let S be the set of symbols corresponding to C and let N be the least common ancestor of all of S. Let a and b be two symbols in S that are in different subtrees of S. Then by (iii), od(G[a], G[b]) = d(N}. Let x be any symbol in N.symbols. Then by (iii) od(G[a], G[x]) <<= d(N). Hence G[x] in C.