D.i D =odiam( Γ( Q .symbols)). Then apply operation ( 3 ) with N = Q .

D.ii D > odiam(F(Q.symbols)), and Q is not the root. Then apply operation (5)
with C = Q. Set M.label to be the suitable value for D. (It is easily shown that D < odiam( Γ( N .symbols)), where N is the father of Q .)
D.iii D > odiam( Γ( Q.symbols)), and Q is the root. Apply operation ( 6 ).

## 口

Lemma 25: Let A = {a1...ak} be a finite set of points whose diameter has order-ofmagnitude D. Then there exists a point u such that, for i = 1 . . . k, od( u, a i ) = D. Proof: Let b 1 = a 1 . By axiom A.8 there exists an infinite collection of points b 2 , b 3 . . such that od( bj , bj ) = D for i ̸= j . Now, for any value aj there can be at most one value bj such that od( a i , b i ) ≪ D ; if there were two such values b i 1 and b i 2 , then by the om-triangle inequality, od( bj 1, bj 2 ) ≪ D . Hence, all but k different values of bj are at least D from any of the a i .  Let u be any of these values of b i .  Then since od( u, a 1 ) = D and od( a 1 , a i ) ≪ D
for all i, it follows that od( u, aj ) ¶ D for all aj. Thus, since od( u, aj ) ¶ D but not od( u, aj )
« D, it follows that od(u, a;) = D, □
Lemma 26: Let T be a cluster tree; let Γ be a valuation over om-space Ω satisfying T ; and let T ′ be an extension of T by x . If Ω is dense and unbounded above, then there is a value a such that the valuation Γ ∪ { x → a } satisfies T ′ . Proof: For operations (1) and (2) the statement is trivial.

Otherwise, let L be an extending label of T . If L = 0, then set D = 0. If L is in T ,
then let D be the order of magnitude corresponding to L in T under Γ . If L 1 < L < L 2 where L 1 and L 2 are labels of consecutive values in T 1 then let D 1 and D 2 be the orders of magnitude corresponding to L 1 , L 2 in T under Γ . Let D be osen so that D 1 ≪ D ≪ D 2 . If L is greater than any label in the tree, then choose D to be greater than the diameter of the tree under F.

If T ′ is formed from T by operation (3), then using lemma 25 let a be a point such that od( a, Γ( y )) = odiam( N ) for all y in N .symbols.

If T ′ is formed from T by operation (4), then let a be a point such that od( a, Γ( y)) =
D.

If T ′ is formed from T by operation (5), then let a be a point such that od( a, Γ( y )) =
D for all y in C .symbols. (Note that, since M .label < N .label, D < odiam( N .symbols).)
If T ′ is formed from T by operation (6), then let a be a point such that od( a, Γ( y)) =
D for all y in R symbols.

In each of these cases, it is straightforward to verify that Γ ∪ { x → a } satisfies T ′ . □
As we observed in Section 8 regarding lemma 28, the conditions on Ω in lemma 26 are necessary, and the statement is false otherwise. For example, let Ω be the om-space described in example I, Section 3, of polynomials over an infinitesimal δ .  Then Ω is not unbounded above; there is a maximum order-of-magnitude O (1). Let T be the starting tree of Figure 3 (upper-left corner), and let T ′ be the result of applying operation 6 (middle bottom). Let Γ be the valuation { u → δ, ν → 2 δ, w → 1 } . Then Γ satisfies Γ , but it cannot be extended to a valuation that satisfies T ′ , as that would require x to be given a value such that od( v, w ) ≪ od( x, w ), and no such value exists within Ω. The point of the lemma