Volumen 24, 1999, 465–488

**UPPER SETS AND QUASISYMMETRIC MAPS**

**D.A. Trotsenko**^{1} **and J. V¨ais¨al¨a**

Academy of Sciences, Institute of Mathematics

Universitetskij prospekt 4, 630090 Novosibirsk, Russia; trotsenk@math.nsc.ru University of Helsinki, Department of Mathematics

PL 4, Yliopistonkatu 5, FIN-00014 Helsinki, Finland; jvaisala@cc.helsinki.ﬁ

**Abstract.** The upper set ˜*A* of a metric space *A* is a subset of *A**×*(0,*∞*) , consisting of
all pairs (x,*|**x**−**y**|*) with *x, y* *∈* *A*, *x* = *y*. We consider various properties of ˜*A* and a metric
of ˜*A, called the broken hyperbolic metric. The theory is applied to study basic properties of*
quasisymmetric maps.

**1. Introduction**

1.1. Let *A* be a metric space, where the distance between points *a, b* is written
as *|a−b|*. The *upper set* of *A* is the subset

*A*˜=

(x,*|x−y|*) :*x* *∈A, y* *∈A\ {x}*

of *A×*R+*,* R+ = (0,*∞*) . We assume that *A* contains at least two points in order
that ˜*A* be nonempty. If *A⊂*R* ^{n}*, then ˜

*A*

*⊂*R

^{n+1}_{+}=R

^{n}*×*R+, and we can consider the hyperbolic metric

*h*of R

^{n+1}_{+}in ˜

*A*. However, we ﬁnd it convenient to replace

*by another metric , which is bilipschitz equivalent to*

_{h}*, and which is easy to consider also in the case where*

_{h}*A*is an arbitrary metric space. The precise deﬁnition of is given in 2.2.

For each *λ >* 0 we partition ˜*A* into *λ*-components, where points *z* and
*z** ^{}* belong to the same

*λ*-component if they can be joined by a ﬁnite sequence

*z*=

*z*0

*, . . . , z*

*N*=

*z*

*in ˜*

^{}*A*with

*(z*

*j*

*−*1

*, z*

*j*)

*≤*

*λ*for all

*j*. The family Γ = Γ

*λ*(A) of all

*λ*-components of ˜

*A*is the main object of study in this paper. The case

*λ*

*≥*1 is the most interesting. There is a natural

*ordering*of Γ , which gives Γ a structure of a treelike

*graph.*

If *A* is connected, then also ˜*A* is connected, and Γ is the trivial graph con-
sisting of one vertex. More generally, Γ is trivial if *A* is *c*-uniformly perfect with
*c < e** ^{λ}*; see 4.12 for the deﬁnition of uniform perfectness. In the general case we
can roughly say that the structure of Γ describes in which way

*A*is disconnected.

1991 Mathematics Subject Classiﬁcation: Primary 30C65.

1 The research described in this paper was supported by the Russian Fund for Fundamental Research (project 96-01-01558), by the University of Helsinki, and by the Finnish Academy of Sciences.

In Section 6 we apply the theory of upper sets to quasisymmetric maps. Let
*A* and *B* be metric spaces and let *f*: *A* *→* *B* be *η*-quasisymmetric; see 6.2 for
the deﬁnition of quasisymmetry. It is well known that if *A* is uniformly perfect,
then *η* can be chosen to be of the form *η(t) =* *C(t*^{α}*∨t*^{1/α}) ; see [TV], [AT]. We
show that this is true for all *η*-quasisymmetric maps of *A* *if and only if* there
is *λ* such that Γ* _{λ}*(A) is trivial. This property can also be expressed in terms of
relative connectedness (Theorem 4.9).

The second author wants to make it clear that an early version of the theory of upper sets was created and developed by the ﬁrst author D.A. Trotsenko in the late eighties and considered in the conference proceedings [Tr]. Also the application to quasisymmetric maps was proved by him. The main part of this paper was written during the visits of the ﬁrst author at the University of Helsinki in 1997.

The second author has “polished up” the theory by writing and simplifying details of proofs, introducing some terminology and auxiliary concepts, etc.

1.2. *Notation. Throughout the paper,* *A* will denote a metric space with
distance between points *x, y* written as *|x−y|*. For nonempty sets *E, F* *⊂* *A*,
we let *d(E) and* *d(E, F*) denote the diameter of *E* and the distance between
*E* and *F*. For *r >* 0 , *B(E, r) is the* *r*-neighborhood *{x* : *d(x, E*) *< r}* of *E*.
Moreover, *B(x, r) is the open ball with radius* *r* centered at *x*; the closed ball is
*B(x, r) . We let* R and N denote the set of real numbers and the set of positive
integers, respectively, and we write N_{0} = N*∪ {*0*}*. For real numbers *s, t* we use
the notation

*s∧t*= min(s, t), *s∨t* = max(s, t).

We make the convention that *λ* will always denote a real number with *λ≥*1 .
*Acknowledgement.* We thank Pekka Alestalo for careful reading of the manu-
script and for several valuable comments.

**2. Broken hyperbolic metric**

2.1. *Summary. In this section we introduce the broken hyperbolic metric*
of the space *A×*R+ and prove some properties of it.

2.2. *Deﬁnitions. The ordinary hyperbolic metric* *h* of the half space *R*^{n+1}_{+} =
R^{n}*×*R+ is deﬁned by the element of length

*d**h*(x, r) = (*|dx|*^{2} +*dr*^{2})^{1/2}

*r* *,*

where *x∈*R* ^{n}*,

*r*

*∈*R+,

*n≥*1 . We ﬁnd it convenient to replace

*by the metric deﬁned by the element of length*

_{h}*d(x, r) =* *|dx|*+*|dr|*

*r* *.*

Thus for *z, z*^{}*∈*R^{n+1}_{+} we have

*(z, z** ^{}*) = inf

*γ*

*γ*

*|dx|*+*|dr|*
*r*

over all rectiﬁable arcs *γ* joining *z* and *z** ^{}* in R

^{n+1}_{+}. Since

*d*

*h*

*≤*

*d*

*≤*

*√*2

*d*

*h*, we have

* _{h}*(z, z

*)*

^{}*≤*

*(z, z*

*)*

^{}*≤√*

2* _{h}*(z, z

*)*

^{}for all *z, z*^{}*∈*R^{n+1}_{+} . The metric is the *broken hyperbolic metric* of R^{n+1}_{+} .
More generally, let *A* be an arbitrary metric space, and let *z* = (x, r), z* ^{}* =
(x

^{}*, r*

*) be points in*

^{}*A×*R+. Choose points

*y, y*

^{}*∈*R

*with*

^{n}*|y−y*

^{}*|*=

*|x−x*

^{}*|*. Then the number

*(z, z** ^{}*) =

(y, r),(y^{}*, r** ^{}*)

is independent of the choice of *y* and *y** ^{}*, and it gives the broken hyperbolic metric
of

*A×*R+. Since each triple of

*A*can be isometrically embedded into R

^{2}, we see that indeed is a metric in

*A×*R+.

Alternatively, the broken hyperbolic metric of *A×*R+ can be deﬁned as
follows. Let

*π:* *A×*R+ *→A,* *π*2:*A×*R+ *→*R+

be the projections. By a*step* we mean a pair of points in *A×*R+. A step (z, z* ^{}*) is

*vertical*if

*π(z) =π(z*

*) , and (z, z*

^{}*) is*

^{}*horizontal*if

*π*2(z) =

*π*2(z

*) . The hyperbolic length of a vertical step (z, z*

^{}*) is*

^{}*l**h*(z, z* ^{}*) =log

*π*2(z)

*π*2(z

*)*

^{}*,*
and the hyperbolic length of a horizontal step (z, z* ^{}*) is

*l** _{h}*(z, z

*) =*

^{}*|π(z)−π(z*

*)*

^{}*|*

*π*2(z)

*.*

A *step path* in *A×*R+ is a ﬁnite sequence ¯*z* = (z_{0}*, . . . , z** _{N}*) of points in

*A×*R+

such that the step (z*j**−*1*, z**j*) is either horizontal or vertical for all 1 *≤* *j* *≤* *N*.
The hyperbolic length of ¯*z* is the number

*l**h*(¯*z*) =
*N*

*j=1*

*l**h*(z*j**−*1*, z**j*).

In the special case *A* = R* ^{n}*,

*l*

*h*(¯

*z) is the ordinary hyperbolic length of the path*consisting of the segmental paths [z

*j*

*−*1

*, z*

*j*] , 1

*≤*

*j*

*≤*

*N*. The

*broken hyperbolic*

*distance*between points

*z, z*

^{}*∈*

*A×*R+ is deﬁned as

*(z, z** ^{}*) = inf

¯
*z* *l**h*(¯*z*)

over all step paths ¯*z* from *z* to *z** ^{}*. It is not diﬃcult to show that the two deﬁnitions
for are equivalent. However, in the sequel we shall use the second deﬁnition; the
ﬁrst one was given to illustrate the connection between and

*h*in R

^{n+1}_{+}.

2.3. *Geodesics. Let* *z* = (x, r) and *z** ^{}* = (x

^{}*, r*

*) be points in*

^{}*A×*R+. We want to ﬁnd a geodesic from

*z*to

*z*

*, that is, a step path ¯*

^{}*z*= (z0

*, . . . , z*

*N*) such that

*z*0 =

*z*,

*z*

*N*=

*z*

*, and*

^{}*l*

*h*(¯

*z) =(z, z*

*) .*

^{}Assume that *r* *≤* *r** ^{}* and that ¯

*z*is a step path from

*z*to

*z*

*. Let*

^{}*t*= max

*{π*2(z

*j*) : 0

*≤*

*j*

*≤*

*N}*be the maximal height of ¯

*z*. Then the sum of the hyperbolic lengths of all vertical steps of ¯

*z*is at least log(t/r) + log(t/r

*) . The corresponding sum for the horizontal steps is at least*

^{}*|x−x*

^{}*|/t*. Hence

*l*

*h*(¯

*z*)

*≥*

*l*

*(¯*

_{h}*y) , where ¯y*is the step path (z, y

_{1}

*, y*

_{2}

*, z*

*) with*

^{}*y*

_{1}= (x, t) ,

*y*

_{2}= (x

^{}*, t) . We*have

*l** _{h}*(¯

*y) =*

*|x−x*

^{}*|*

*t* + 2 log*t−*log(rr* ^{}*).

Using elementary calculus we see that the right-hand side attains its minimum at
*t* =*|x−x*^{}*|/2 . We obtain the following result:*

2.4. **Theorem.** *Let* *z* = (x, r) *and* *z** ^{}* = (x

^{}*, r*

*)*

^{}*be points in*

*A×*R+

*with*

*r*

*≤r*

^{}*and*

*|x−x*

^{}*|*=

*s. If*

*r*

^{}*≤s/2, then the geodesic in the metric*

*from*

*z*

*to*

*z*

^{}*is the step path*

*z,*(x, s/2),(x^{}*, s/2), z*^{}*, and*
*(z, z** ^{}*) = 2 + log

*s*

^{2}

4rr^{}*.*
*If* *r*^{}*≥s/2, then the geodesic is the step path*

*z,*(x, r* ^{}*), z

^{}*, and*

*(z, z*

*) =*

^{}*s*

*r** ^{}* + log

*r*

^{}*r.*

*In particular, if* *r*=*r*^{}*≥s/2* *or if* *x*=*x*^{}*, then the geodesic reduces to the single*
*step* (z, z* ^{}*)

*.*

2.5. *Remarks. 1. Observe that the ﬁrst case of Theorem 2.4 can occur only*
if *(z, z** ^{}*)

*>*2 .

2. In the case *A* = R* ^{n}*, the geodesic from

*z*to

*z*

*can be considered as an ordinary arc*

^{}*γ*

*⊂*R

^{n+1}_{+}. This arc consists of one, two or three line segments, and it lies on the boundary of the unique square

*Q*such that

*Q*and a pair of its sides are perpendicular to R

*, and the center of*

^{n}*Q*is in R

*. See Figure 1.*

^{n}Geodesic of the metric in R+*n+1*

*R*^{n}

*z*

*z´ *

*L(x*0)

*x*0

The point *z´ of L(x*0) is closest to z

Figure 1.

2.6. *Notation.* For *x* *∈A* we let *L(x) denote the ray* *{x} ×*R+ =*π*^{−}^{1}*{x} ⊂*
*A×*R+.

2.7. **Lemma.** *Let* *z* = (x, r) *∈A×*R+ *and* *x*_{0} *∈A. If* *|x−x*_{0}*| ≥r, then*

*z, L(x*_{0})

=

*z,*(x_{0}*,|x−x*_{0}*|*)

= 1 + log(*|x−x*_{0}*|/r).*

*If* *|x−x*0*| ≤r, then*

*z, L(x*0)

=

*z,*(x0*, r)*

= *|x−x*0*|/r.*

*Proof.* The lemma follows from 2.4 by elementary calculus. Alternatively, we
can argue as follows. Without loss we may assume that *A* =R and that *x*0 = 0 .
Let *z*^{}*∈L(x*0) be the point closest to *z*. Then*z** ^{}* must lie on the geodesic between

*z*and (

*−x, r) , and the lemma follows from 2.4.*

2.8. *Remark. I f* *A* *⊂*R* ^{n}*, then Lemma 2.7 means that the point

*z*

*of*

^{}*L(x*0) closest to

*z*is such that

*z*lies on the boundary of a square with adjacent vertices (x0

*,*0) and

*z*

*. See Figure 1.*

^{}2.9. **Lemma.** *If* *z* = (x, r), z* ^{}* = (x

^{}*, r*

*)*

^{}*∈A×*R+

*, then*

*|x−x*

^{}*| ≤re*

^{(z,z}

^{}^{)−1}

*.*

*Proof.*Set

*s*=

*|x−x*

^{}*|*. Since 1 + log(s/r)

*≤s/r*, Lemma 2.7 implies that

1 + log*s*
*r* *≤*

*z, L(x** ^{}*)

*≤(z, z** ^{}*),
and the lemma follows.

2.10. *Remark. In a recent manuscript [BS], M. Bonk and O. Schramm con-*
sider a metric * ^{}* in

*A×*R, deﬁned by the explicit formula

^{}

(x, s),(y, t)

= 2 log*|x−y|*+*s∨t*

*√st* *.*

It is not diﬃcult to show that this metric is bilipschitz equivalent to our metric .
I n fact, ^{}*/2≤≤*2*√*

2* ^{}*.

**3. Upper sets and** *λ***-components**

3.1. *Summary. In this section we develop the basic theory of the upper set ˜A*
of a metric space *A*. In particular, we study the properties of the family Γ*λ*(A)
of the *λ*-components of ˜*A*, *λ≥*1 .

3.2. *Deﬁnitions. We recall from the introduction that the* *upper set* of a
metric space *A* is

*A*˜=

(x,*|x−y|*) :*x∈A, y∈A\ {x}*

*⊂A×*R+*.*

Recall also that we always assume that *A* contains at least 2 points, and hence
*A*˜=∅. The broken hyperbolic metric of *A×*R+ deﬁnes a metric in ˜*A*.

Recall from 1.2 that we always assume that *λ* *≥* 1 . By a *λ*-sequence we
mean a ﬁnite sequence ¯*z* = (z_{0}*, . . . , z** _{N}*) in ˜

*A*such that

*(z*

_{j−1}*, z*

*)*

_{j}*≤*

*λ*for all 1

*≤j*

*≤N*. Two points in ˜

*A*belong to the same

*λ*-component of ˜

*A*if they can be joined by a

*λ*-sequence in ˜

*A*. If there is only one

*λ*-component, ˜

*A*is

*λ*-connected.

The family Γ*λ*(A) of all *λ*-components of ˜*A* is a partition of ˜*A*. For brevity, we
shall write Γ* _{λ}*(A) as Γ

*or simply as Γ if there is no danger of misunderstanding.*

_{λ}Recall the notation *π:* *A×*R+ *→A* and *π*2: *A×*R+ *→*R+ for the projections.

We deﬁne a partial ordering in *A×*R+ by setting *z* *≤* *z** ^{}* if

*π(z) =*

*π(z*

*) and*

^{}*π*2(z)

*≤π*2(z

*) .*

^{}We also deﬁne a relation *≤* in Γ by setting *γ* *≤γ** ^{}* if

*π(γ*)

*⊂π(γ*

*) .*

^{}In Theorem 3.4 we collect together several basic properties of Γ . In particular,
we show that the relation *≤* is a partial ordering of Γ and give two alternative
characterizations for this relation. Geometrically, *γ* *≤γ** ^{}* means that

*γ*lies below

*γ*

*in*

^{}*A×*R+.

3.3. *Notation. I f* *x, y* *∈A* and *x* =*y*, we set *x, y*= (x,*|x−y|*) . Then *x, y*
and *y, x* are in ˜*A*, and *(x, y,y, x*) = 1 by 2.4. Hence the points *x, y* and
*y, x* lie in the same *λ*-component. This simple observation is needed in several
arguments, and it is the reason for our convention *λ≥*1 .

3.4. **Theorem.** *Let* *γ, γ*^{}*∈*Γ = Γ*λ*(A)*.*

(1) *If* *γ* = *γ*^{}*,* *z* *∈* *γ,* *z** ^{}* =

*x, y ∈*

*γ*

^{}*, and*

*z < z*

^{}*, then*

*y /∈*

*πγ. Moreover,*

*for each*

*w∈γ*

*we have*

*(z*

^{}*,πw, y*)

*<*1

*≤*

*λ*

*and*

*w <πw, y ∈γ*

^{}*.*

(2) *γ* *≤γ*^{}*if and only if* *z* *≤z*^{}*for some* *z* *∈γ,* *z*^{}*∈γ*^{}*.*

(3) *γ* *≤γ*^{}*if and only if for each* *z* *∈γ* *there is* *z*^{}*∈γ*^{}*with* *z* *≤z*^{}*.*

(4) *If* *γ* =*γ*^{}*, then either* *πγ* *and* *πγ*^{}*are disjoint or one of them is a proper*
*subset of the other.*

(5) *≤* *is a partial ordering of* Γ*.*

(6) *If* *z*1 *≤z*2 *≤z*3 *are points of* *A*˜ *with* *z*1*, z*3 *∈γ, then* *z*2 *∈γ.*
(7) *If* *x, y ∈γ, then* *x, y∈πγ.*

(8) *πγ* =*∪{β* *∈*Γ :*β* *≤γ}.*

(9) *If* *γ* *contains* (x, r) *and* (x^{}*, r** ^{}*)

*, and if*

*r∧r*

^{}*≤ |x−x*

^{}*|, then*

*γ*

*contains*

*x, x*

^{}*and*

*x*

^{}*, x.*

(10) *If* *x*_{0}*, y* *∈πγ* *and* *x∈A* *with* *|x−x*_{0}*| ≤e*^{λ}*|y−x*_{0}*|, then* *x∈πγ.*
(11) *If* *d(πγ) =∞, then* *πγ* =*A, and* *γ* *is the greatest element of* Γ.

(12) *If* *d(πγ)<∞, then* *B*

*πγ,*(e^{λ}*−*1)d(πγ)

=*πγ.*
(13) *If* *γ < γ*^{}*, then* *d(πγ** ^{}*)

*≥*(e

^{λ}*−*1)d(πγ).

(14) *πγ* *is closed and open in* *A.*

(15) *If* *A* *is separable, then* Γ *is countable.*

*Proof.* (1) Write *z* = (x, r) , *z** ^{}* = (x, r

*) , where*

^{}*r*

*=*

^{}*|x−y|*. Suppose that

*w*= (u, t)

*∈*

*γ*. We must show that

*u*=

*y*and that

*w <*

*u, y ∈*

*γ*

*. We may assume that*

^{}*(z, w)*

*≤λ*, since the general case follows from this by induction.

By 2.9 we have *|x−u| ≤re*^{λ}^{−}^{1}, and hence

*r*^{}*−re*^{λ}^{−}^{1} *≤ |u−y| ≤r** ^{}*+

*re*

^{λ}

^{−}^{1}

*.*

Since *λ < (z, z** ^{}*) = log(r

^{}*/r) , we have*

*r*

^{}*> re*

*, and hence*

^{λ}*|u−y| ≥*

*r(e*

^{λ}*−*

*e*

^{λ}

^{−}^{1})

*>*0 . Thus the point

*w*

*=*

^{}*u, y*is in ˜

*A*. Moreover,

*(z*^{}*, w** ^{}*)

*≤*

*|u−x|*

*r** ^{}* + log

*r*

^{}*r*^{}*−re*^{λ−1}*≤e*^{−}^{1} + log *e*

*e−*1 *<*1*≤λ,*
which yields *w*^{}*∈γ** ^{}*.

It remains to show that *w < w** ^{}*, that is,

*t <|u−y|*. Assume that

*t≥ |u−y|*. Since

*(w, w*

*)*

^{}*> λ*, we then have

*t > e*

^{λ}*|u*

*−y|*

*> e*

*(e*

^{λ}

^{λ}*−*

*e*

^{λ}

^{−}^{1})r. On the other hand,

*(z, w)*

*≤*

*λ*implies that

*t*

*≤*

*re*

*, and we get the contradiction 1*

^{λ}*> e*

^{λ}*−e*

^{λ}

^{−}^{1}

*≥e−*1 . Part (1) is proved.

Observe that in the situation of (1) we have *y, x ∈* *γ** ^{}* by 3.3. Hence

*πγ*

*πγ*

*, and parts (2), (3), (4) follow easily. Furthermore, (4) implies (5), and (6) follows from (2) and (5). Part (7) is clear in view of 3.3.*

^{}(8) If *β, γ* *∈* Γ and *z* = *x, y ∈* *β* *≤* *γ*, then *x, y* *∈* *πβ* *⊂* *πγ* by (7), and
hence *x* *∈* *πγ*. Conversely, assume that *x, y* *∈* *πγ*, *x* = *y*. Choose *w* *∈* *γ* with
*x* = *π(w) . Let* *β* *∈* Γ be the *λ*-component of ˜*A* containing *z* = *x, y*. Since
*x∈πβ∩πγ*, we have either *β* *≤γ* or *β > γ* by (4). The latter case is impossible,
since it implies that *w < z* by (2) and then *y /∈πγ* by (1). Hence *β* *≤γ*.

(9) We may assume that *r* *≤ |x−x*^{}*|*. Choose *β* *∈*Γ containing *x, x** ^{}* and

*x*

^{}*, x*. Then

*β*

*≤γ*by (8). Since

*z*

*≤ x, x*

*, we have*

^{}*γ*

*≤β*by (2).

(10) By (8) there is *β* *∈*Γ with *x*0*, y ∈β* *≤γ*. By (3) there is*z* = (x0*, r)∈γ*
with *x*0*, y ≤z*. I f *x*0*, x ≥* *z*, then

*(x*0*, x, z) = log* *|x−x*_{0}*|*
*r* *≤λ,*

and hence *x*0*, x ∈* *γ*, which gives *x* *∈* *πγ* by (7). If *x*0*, x ≤* *z*, then *x*0*, x ∈*
*β* *≤γ* for some *β* *∈*Γ by (2), and hence *x∈πβ* *⊂πγ*.

(11) follows directly from (10).

(12) Observe that *d(πγ)>*0 by (7). Suppose that *x∈B*

*πγ,*(e^{λ}*−*1)d(πγ)
.
We can choose *ε >*0 and points *x*1*, x*0*, y∈πγ* such that

*|x−x*1*| ≤*(e^{λ}*−*1)d(πγ)*−ε,*

*|x*_{0}*−y| ≥d(πγ)−εe*^{−}^{λ}*.*
Then

*|x−x*0*| ≤ |x−x*1*|*+*|x*1*−x*0*| ≤*(e^{λ}*−*1)d(πγ)*−ε*+*d(πγ*)*≤e*^{λ}*|y−x*0*|,*
which yields *x∈πγ* by (10).

(13) and (14) follow from (12).

(15) If *A* is separable, then so is *A×*R+. Since the neighborhoods *B(γ, λ/2)*
of *γ* *∈*Γ are disjoint, Γ is countable.

3.5. *Remark. I f* *A* *⊂* R* ^{n}* is inﬁnite, then ( ˜

*A, ) is unbounded. Indeed,*

*A*contains a sequence (x

*j*) of distinct points converging to a point in R

*or to*

^{n}*∞*. Then

*(z*1

*, z*

*j*)

*→ ∞*, where

*z*

*j*=

*x*

*j*

*, x*

*j+1*in the ﬁrst case, and

*z*

*j*=

*x*1

*, x*

*j+1*in the second case.

This result is not true for arbitrary metric spaces. For example, if *A* is a
space with the discrete metric *|x* *−y|* = 1 for *x* = *y*, then ˜*A* = *A× {*1*}*, and
*(z, z** ^{}*) = 1 for all

*z*=

*z*

*.*

^{}**4. Simple** *λ***-sequences and relative connectedness**

4.1. *Summary. We show that each* *λ*-sequence (z0*, . . . , z**N*) in the upper set ˜*A*
can be embedded into a *λ*-sequence of a special kind, called a*simple* *λ*-sequence.

It turns out that the simple *λ*-sequences of ˜*A* are in one-to-one correspondence
with certain sequences (x_{0}*, . . . , x** _{N}*) of

*A*, called

*M*-relative sequences and char- acterized by the property

*|x**j**−*1 *−x**j**|/M* *≤ |x**j**−x**j+1**| ≤M|x**j**−*1 *−x**j**|,*

*M* = *e** ^{λ}*. These lead to

*relatively connected*metric spaces, which are closely connected with uniformly perfect spaces.

4.2. *Simple sequences. We say that a pair (z, z** ^{}*) of points in the upper set ˜

*A*of a metric space

*A*is

*simple*if

*π*

_{2}(z) =

*π*

_{2}(z

*) =*

^{}*|π(z)−π(z*

*)*

^{}*|*. I n other words, there are

*x, y*

*∈A*such that

*z*=

*x, y*,

*z*

*=*

^{}*y, x*. Recall that (z, z

*) is vertical if*

^{}*π(z) =π(z*

*) . In particular, a pair (z, z) is always vertical (but never simple).*

^{}Observe that *(z, z** ^{}*) = 1 for a simple pair (z, z

*) and that*

^{}*(z, z*

*) =log*

^{}*π*2(z)

*π*2(z* ^{}*)
for a vertical pair.

A ﬁnite sequence ¯*z* = (z0*, . . . , z**N*) in ˜*A* is called *simple* if *N* is odd and if
the step (z*j**−*1*, z**j*) is simple for all odd *j* and (z*j**−*1*, z**j*) is vertical for all even *j*.
We ﬁrst show that every *λ*-sequence in ˜*A* can be *simpliﬁed* to a simple *λ*-
sequence by adding new points.

4.3. **Theorem.** *Every* *λ-sequence* *z*¯= (z_{0}*, . . . , z** _{N}*)

*of*

*A*˜

*can be embedded*

*into a simple*

*λ-sequence*

*u*¯= (u0

*, . . . , u*

*N*

*). This means that*

^{}*u*0=

*z*0

*,*

*u*

*N*

*=*

^{}*z*

*N*

*,*

*and*

*z*¯

*is a subsequence of*

*u*¯

*.*

*Proof.* We ﬁrst remark that if *x, y ∈* *A*˜, then the sequence (*x, y,y, x*,
*y, x,x, y*) is a simple 1 -sequence, called a *trick sequence. It has three steps,*
and it joins *x, y* to itself.

The theorem is proved by induction on *N*. Assume ﬁrst that *N* = 1 . Then

¯

*z* is a pair (z, z* ^{}*) with

*(z, z*

*)*

^{}*≤λ*. Write

*z*=

*x, y*= (x, r) and

*z*

*=*

^{}*x*

^{}*, y*

*= (x*

^{}

^{}*, r*

*) . I f*

^{}*x*=

*x*

*, we can use two trick sequences to embed ¯*

^{}*z*into a simple

*λ*- sequence with 7 steps. We may thus assume that

*|x−x*

^{}*|*=

*t >*0 . By symmetry, we may assume that

*r*

*≥r*

*. We consider two cases.*

^{}*Case* 1. *r* *≤e*^{λ}*t*. Consider the sequence ¯*v* = (z, v1*, v*2*, z** ^{}*) , where

*v*1 =

*x, x*

*,*

^{}*v*2 =

*x*

^{}*, x*. I f

*r*

*≥*

*t*, then

*(z, v*1) = log(r/t)

*≤*

*λ*. I f

*r*

*≤*

*t*, then 2.4 and 2.7 imply that

*(z, v*_{1})*< (z, v*_{1}) +*(v*_{1}*, v*_{2}) =*(z, v*_{2}) =

*z, L(x** ^{}*)

*≤(z, z** ^{}*)

*≤λ.*

A similar argument shows that *(v*2*, z** ^{}*)

*≤λ*. Hence ¯

*v*is a

*λ*-sequence. Extending

¯

*v* by two trick sequences we obtain the desired simple *λ*-sequence ¯*u* from *z* to *z** ^{}*.

*Case*2.

*r*

*≥*

*e*

^{λ}*t*. We show that the sequence ¯

*v*= (z, v1

*, v*2

*, v*3

*, z*

*) with*

^{}*v*1 =

*y, x*,

*v*2 =

*y, x*

*,*

^{}*v*3 =

*x*

^{}*, y*is a

*λ*-sequence.

Since

(4.4) *r−t* *≤ |y−x*^{}*| ≤r*+*t,*

we obtain

*(v*1*, v*2) =log *r*

*|y−x*^{}*|* *≤*log *r*

*r−t* *≤*log *e*

*e−*1 *<*1.

To prove that *(v*3*, z** ^{}*)

*≤λ*we consider two subcases.

*Subcase* 2a. *r*^{}*≤r−t*. By (4.4) and by 2.4 we obtain
*(v*_{3}*, z** ^{}*) = log

*|y−x*

^{}*|*

*r*^{}*≤*log *r*

*r** ^{}* + log 1 +

*t*

*r*

*≤*log *r*
*r** ^{}* +

*t*

*r* =*(z, z** ^{}*)

*≤λ.*

*Subcase* 2b. *r*^{}*≥r−t*. Since *r≥e*^{λ}*t*, it follows from (4.4) that the numbers
*r** ^{}* and

*|y−x*

^{}*|*are between

*r(1−e*

^{−}*) and*

^{λ}*r(1 +e*

^{−}*) . Hence*

^{λ}*(v*3*, z** ^{}*)

*≤*log 1 +

*e*

^{−}

^{λ}1*−e*^{−}^{λ}*≤*log*e*+ 1
*e−*1 *<*1.

We have proved that ¯*v* is a *λ*-sequence. Extending ¯*v* by a trick sequence
from *z** ^{}* to

*z*

*we obtain a simple*

^{}*λ*-sequence from

*z*to

*z*

*.*

^{}Next assume that *p* is a positive integer and that the theorem is true whenever
*N* *≤* *p*. Suppose that *N* = *p*+ 1 . Applying the induction hypothesis to the *λ*-
sequences (z0*, . . . , z**N**−*1) and (z*N**−*1*, z**N*) we embed them into simple *λ*-sequences.

Linking these sequences with the trivial vertical step (z*N**−*1*, z**N**−*1) we obtain the
desired simple *λ*-sequence ¯*u*.

4.5. *Remark. The construction of the proof of 4.3 is not the most economical.*

It gives the bound *N*^{}*≤*10N.

4.6. *Relative connectedness. We say that a ﬁnite sequence ¯x* = (x0*, . . . , x**N*)
in a metric space *A* is *proper* if *N* *≥* 1 and if *x**j**−*1 = *x**j* for all 1 *≤* *j* *≤N*. I n
particular, a pair (x, y) is proper if *x* =*y*. The sequence ¯*x* is called *M*-relative,
*M* *≥*1 , if ¯*x* is proper and if

*|x**j**−*1 *−x**j**|/M* *≤ |x**j* *−x**j+1**| ≤M|x**j**−*1*−x**j**|*

or equivalently,

log *|x**j**−x**j+1**|*

*|x**j**−*1*−x**j**|≤*log*M*

for all 1 *≤* *j* *≤* *N* *−*1 . In the trivial case *N* = 1 , ¯*x* is a pair (x_{0}*, x*_{1}) , and the
condition for *M*-relativity is vacuously true for all *M* *≥*1 .

We say that the sequence ¯*x* = (x_{0}*, . . . , x** _{N}*)

*joins*the pairs (x

_{0}

*, x*

_{1}) and (x

*N*

*−*1

*, x*

*N*) , and that

*A*is

*M*-relatively connected if each pair of proper pairs (x, y) and (x

^{}*, y*

*) in*

^{}*A*can be joined by an

*M*-relative sequence in

*A*. The space

*A*is

*relatively connected*if it is

*M*-relatively connected for some

*M*

*≥*1 .

A connected space is *M*-relatively connected for all *M >*1 , but so are many
other spaces as well, for example, the Cantor middle-third set.

4.7. *Associated sequences. We shall show that the* *e** ^{λ}*-relative sequences of

*A*are in one-to-one correspondence with the simple

*λ*-sequences of the upper set ˜

*A*. Suppose that ¯

*x*= (x0

*, . . . , x*

*N*) is a proper sequence in

*A*. Deﬁne a sequence

¯

*z* = (z_{0}*, . . . , z*_{2N}* _{−1}*) in ˜

*A*by

*z*2j =*x**j**, x**j+1**,* *z*2j+1 =*x**j+1**, x**j*

for 0*≤* *j* *≤N* *−*1 . Thus ¯*z* is the sequence

(*x*_{0}*, x*_{1}*,x*_{1}*, x*_{0}*,x*_{1}*, x*_{2}*,x*_{2}*, x*_{1}*, . . . ,x*_{N}_{−1}*, x*_{N}*,x*_{N}*, x*_{N}* _{−1}*).

Clearly ¯*z* is a simple sequence. Moreover, ¯*z* is a *λ*-sequence if and only if ¯*x* is
*e** ^{λ}*-relative; remember that we always assume that

*λ≥*1 . We write ¯

*z*= As ¯

*x*and say that ¯

*z*is the simple sequence

*associated*with ¯

*x*.

*Q*1

*Q*2

*Q*3

*x*0

*x*1

*x*2 *x*3

*z*0

*z*1

*z*2

*z*3

*z*4 *z*5

*R**n*

Figure 2. ¯*z*= As ¯*x*

Conversely, if ¯*z* = (z0*, . . . , z*2N*−*1) is a simple sequence in ˜*A*, we associate
with ¯*z* the proper sequence ¯*x* = As^{−}^{1}*z*¯= (x0*, . . . , x**N*) , where *x*0 =*π(z*0) , *x**N* =
*π(z*2N*−*1) , and *x**j* = *π(z*2j*−*1) = *π(z*2j) for 1 *≤* *j* *≤* *N* *−*1 . Then As As^{−1}*z*¯= ¯*z*
and As^{−}^{1}As ¯*x*= ¯*x* for all ¯*z* and ¯*x*. We have proved:

4.8. **Theorem.** *The function* *x*¯ *→* As ¯*x* *gives a bijective correspondence*
*between the proper sequences of* *A* *and the simple sequences of* *A*˜*. Moreover,* *x*¯
*is* *e*^{λ}*-relative if and only if* As ¯*x* *is a* *λ-sequence.*

4.9. **Theorem.** *For* *λ* *≥* 1*, a metric space* *A* *is* *e*^{λ}*-relatively connected if*
*and only if* *A*˜ *is* *λ-connected.*

*Proof.* This follows from 4.3 and 4.8.

4.10. *Remark. I n the case* *A⊂*R* ^{n}*, we can ﬁnd As ¯

*x*by erecting on each line segment [x

*j*

*−*1

*, x*

*j*] a square

*Q*

*j*, orthogonal to R

*(identiﬁed with R*

^{n}

^{n}*× {*0

*} ⊂*R

*) . The sequence ¯*

^{n+1}*z*= As ¯

*x*consists of vertices of these squares as shown in Figure 2.

We next give an alternative characterization for relative connectedness.

4.11. **Theorem.** *For a metric space* *A, the following conditions are quanti-*
*tatively equivalent:*

(1) *A* *is* *M-relatively connected.*

(2) *There is* *c≥*1 *such that if* *x* *∈A* *andB(x, r)* =*A, then eitherB(x, r) =*
*{x}* *orB(x, r)\B(x, r/c)*= ∅*.*

*More precisely,* (1) *implies* (2) *with* *c*= 2M + 1*, and* (2) *implies* (1)*with all*
*M > c.*

*Proof.* Assume that *A* is *M*-relatively connected and that (2) is not true for
*c*= 2M + 1*≥* 3 . Then there are *x* and *r* such that *{x} *=*B(x, r)* =*A* and such
that*B(x, r)\B(x, r/c) =*∅. Pick points *y* and *y** ^{}* in

*A*such that

0*<|x−y|< r/ c,* *|x−y*^{}*|> r.*

Since *A* is *M*-relatively connected, there is an *M*-relative sequence (x0*, . . . , x**N*)
joining (x, y) to (x, y* ^{}*) . Let

*k*be the smallest number with

*|x*

*k*

*−x| ≥*

*r*. Then

*k*

*≥*2 , and

*M* *≥* *|x**k**−x**k**−*1*|*

*|x**k**−*1*−x**k**−*2*|* *>* *r−r/c*

2r/c = *c−*1
2 *,*
which gives *c <*2M + 1 , a contradiction.

Conversely, assume that (2) is true, that *M > c*, and that (x, y) and (x^{}*, y** ^{}*)
are proper pairs in

*A*. We show that they can be joined by an

*M*-relative sequence.

We ﬁrst assume that *x*= *x** ^{}*. By symmetry, we may assume that

*|x−y*

^{}*| ≤ |x−*

*y|*. Applying condition (2) inductively, we ﬁnd a sequence of points

*y*=

*y*0

*, . . . , y*

*N*

such that

*|x−y**j**|/M* *≤ |x−y**j+1**| ≤c|x−y**j**|/M*

for 0 *≤j* *≤N−*1 and *|x−y**N**|/M* *≤ |x−y*^{}*| ≤ |x−y**N**|*. Now (x, y0*, x, y*1*, . . . , x, y**N*,
*x, y** ^{}*) is an

*M*-relative sequence from (x, y) to (x

^{}*, y*

*) .*

^{}If *x* = *x** ^{}*, we can join the pairs (x, y) and (x

^{}*, y*

*) to (x, x*

^{}*) and (x*

^{}

^{}*, x) ,*respectively, by

*c*-relative sequences. These can be joined in a natural way to a

*c*-relative sequence from (x, y) to (x

^{}*, y*

*) .*

^{}4.12. *Uniformly perfect spaces. A metric space* *A* is *c*-uniformly perfect if
*B(x, r)* =*A* implies that*B(x, r)\B(x, r/c)*=∅. The concept was introduced by
C. Pommerenke [Po] for closed unbounded sets in R^{2}, and it has turned out to be
useful in various questions in analysis.

A uniformly perfect set containing more than one point has no isolated points.

For example, a ﬁnite metric space containing more than one point is not uniformly perfect although it is relatively connected. The following corollary of 4.11 gives relations between uniform perfectness and relative connectedness.

4.13. **Theorem.** *A* *c-uniformly perfect space is* *M-relatively connected for*
*all* *M > c. If a space* *A* *is* *M-relatively connected and has no isolated points,*
*then* *A* *is* *c-uniformly perfect with* *c*= 2M + 1.

We apply the results of this section to show that if points *z < z** ^{}* can be joined
by a

*λ*-sequence in ˜

*A*, they can be joined by a vertical (λ+ 1) -sequence. Recall the notation

*L(x) ={x} ×*(0,

*∞*) from 2.6.

4.14. **Lemma.** *Suppose that* *z, z*^{}*∈γ* *∈* Γ*λ*(A) *and that* *π(z) =* *π(z** ^{}*) =

*x.*

*Then*

*z*

*and*

*z*

^{}*can be joined by a*(λ+ 1)

*-sequence in*

*γ∩L(x).*

*Proof.* Write *z* = *x, y*, *z** ^{}* =

*x, y*

*, and assume, for example, that*

^{}*z < z*

*. By 4.3 and 4.8, there is an*

^{}*e*

*-relative sequence (x0*

^{λ}*, . . . , x*

*N*) in

*A*joining the pairs (x, y) and (x, y

*) . For 1*

^{}*≤*

*i*

*≤*

*N*we set

*p*

*i*= max

*{|x*

*k*

*−x|*: 1

*≤*

*k*

*≤*

*i}*. Then

*|x*_{i}*−x*_{i−1}*| ≤ |x*_{i}*−x|*+*|x−x*_{i−1}*| ≤*2p_{i}*,*
and hence

*|x**i+1**−x| ≤ |x**i+1**−x**i**|*+*|x**i**−x| ≤*2p*i**e** ^{λ}*+

*p*

*i*

*,*which yields

*p*

*i+1*

*≤*(2e

*+ 1)p*

^{λ}*i*. Consequently,

log *p*_{i+1}

*p**i* *≤*log(2e* ^{λ}*+ 1) =

*λ*+ log(2 +

*e*

^{−}*)*

^{λ}*< λ*+ 1.

For each *i* *∈* [1, N] choose *j*(i) *≤* *i* with *|x*_{j(i)}*−* *x|* = *p** _{i}*, and set

*z*

*=*

_{i}*x, x*

*. Then*

_{j(i)}*z*

*i*

*∈*

*A*˜,

*z*=

*z*1

*≤*

*z*2

*≤ · · · ≤*

*z*

*N*, and

*z*

^{}*≤*

*z*

*N*. Choose

*k*with

*z*

_{k}*≤z*

^{}*≤z*

*. Since*

_{k+1}*(z**i**, z**i+1*) = log*p*_{i+1}

*p*_{i}*< λ*+ 1,

(z1*, . . . , z**k**, z** ^{}*) is a (λ+ 1) -sequence joining

*z*and

*z*

*in ˜*

^{}*A∩L(x) . Since*

*z, z*

^{}*∈γ*, all

*z*

*i*lie in

*γ*by 3.4(6).

We apply 4.14 to prove the following more general result.

4.15. **Theorem.** *If* *z* = (x, r) *and* *z** ^{}* = (x

^{}*, r*

*)*

^{}*are in a*

*λ-component*

*γ,*

*then*

*z*

*and*

*z*

^{}*can be joined by a*(λ+ 1)-sequence in

*γ∩*

*L(x)∪L(x** ^{}*)

*.*

*Proof.* By 4.14 we may assume that *x*=*x** ^{}*. Choose

*β*

*∈*Γ containing

*x, x*

*and*

^{}*x*

^{}*, x*. I f

*β*=

*γ*, then

*β < γ*by 3.4(9). Choose

*y*

*∈*

*A*with

*z*=

*x, y*. Writing

*z*1 =

*x*

^{}*, y*we have

*(z, z*1)

*≤λ*by 3.4(1). Then

*z*1

*∈*

*γ*, and

*z*

*can be joined to*

^{}*z*1 by a (λ+ 1) -sequence in

*γ∩L(x*

*) by 4.14.*

^{}**5. Order properties of** Γ*λ*(A)

5.1. *Summary. We continue the study of the set Γ = Γ**λ*(A) , especially from
the order-theoretic point of view. To this end, we introduce the order-theoretic
concept of a *family tree* and show that Γ has this property.

5.2. *Family trees. We consider an arbitrary partially ordered set (P,≤*) . We
recall that *P* is (upwards) *directed* if for each pair *x, y* *∈P* there is *z* *∈* *P* with
*x* *≤* *z* *≥* *y*. I f *P* is directed, then a maximal element in *P* is also the greatest
element of *P*, written as max*P* if it exists.

We say that *P* is a *family tree* if

(1) *P* is directed,

(2) for each pair *a, b* *∈* *P*, the set [a, b] = *{x* *∈P* :*a* *≤* *x* *≤* *b}* is ﬁnite and
linearly ordered.

Suppose that *P* is a family tree and that *a* *∈* *P*, *a* = max*P*. We show
that the set *P*^{+}(A) = *{x* *∈* *P* : *x > a}* has the least element, written as *p(a) .*
Choosing *b∈* *P* with *b > a* we can write [a, b] = *{x*_{0}*, . . . , x*_{N}*}*, where *a* = *x*_{0} *<*

*x*1 *<* *· · ·* *< x**N* = *b. I f* *y > a*, there is *z* *∈* *P* with *y* *≤* *z* *≥* *x*1. Since [a, z] is
linearly ordered, we have either *x*1 *≤y* or *x*1 *> y*. The second case is impossible,
since [a, x1] =*{a, x*1*}*. Hence *x*1 is the least element of *P*^{+}(a) .

If *b* = *p(a) , we say that* *b* is the *parent* of *a* and *a* is a *child* of *b. An*
element *a* = max*P* has precisely one parent, but each element of *P* may have
several children. Writing *p*^{2}(a) =*p*

*p(a)*

etc., we have
(5.3) *P*^{+}(a) =*{p(a), p*^{2}(a), p^{3}(a), . . .*}.*

The sequence may be inﬁnite or ﬁnite. The latter case occurs if and only if max*P*
exists; then the sequence ends with max*P*. We see that *P*^{+}(a) is always linearly
ordered.

A family tree is obviously a *semilattice, that is, each pair* *a, b* *∈* *P* has the
least upper bound *a∨b.*

We remark that the Hasse diagram of a family tree is a tree in the graph- theoretic sense: it is connected and contains no cycles.

We now return to the family Γ = Γ*λ*(A) of all *λ*-components of the upper
set ˜*A* of a metric space *A*. We recall from 3.2 and from 3.4 the following three
equivalent characterizations for the ordering *γ* *≤γ** ^{}* of elements of Γ :

(1) *πγ* *⊂πγ** ^{}*.

(2) *z* *≤z** ^{}* for some

*z*

*∈γ*and

*z*

^{}*∈γ*

*.*

^{}(3) For each *z* *∈γ* there is *z*^{}*∈γ** ^{}* with

*z*

*≤z*

*. 5.4.*

^{}**Theorem.**Γ

*λ*(A)

*is a family tree.*

*Proof.* To show that Γ is directed, assume that *γ* and *γ** ^{}* are incomparable
elements of Γ . Choose

*x, y ∈γ*and

*x*

^{}*, y*

^{}*∈*

*γ*

*. Then*

^{}*x, y*

*∈πγ*. By 3.4(10), we have

*|x*

*−x*

^{}*| ≥*

*e*

^{λ}*|x*

*−y|*

*>*

*|x*

*−y|*, and hence

*x, y ≤ x, x*

*. Similarly*

^{}*x*

^{}*, y*

^{}*≤ x*

^{}*, x*. Since there is

*γ*

^{}*∈*Γ containing

*x, x*

*and*

^{}*x*

^{}*, x*, Γ is directed.

Next assume that *γ, γ*^{}*∈* Γ with *γ < γ** ^{}*. We can choose points (x, r)

*∈*

*γ*and (x, r

*)*

^{}*∈*

*γ*

*with*

^{}*r < r*

*. I f*

^{}*β*

*∈*Γ with

*γ < β < γ*

*, then*

^{}*β*contains a point (x, s) with

*r < s < r*

*. Hence [γ, γ*

^{}*] is linearly ordered. Moreover, [γ, γ*

^{}*] is ﬁnite, since*

^{}*|*log(s/s

*)*

^{}*|*

*> λ*whenever (x, s) and (x, s

*) belong to diﬀerent*

^{}*λ*-components of ˜

*A*.

5.5. *Remark. It follows from 5.4 that each* *γ* *∈* Γ with *γ* = max Γ has a
parent *p(γ*) . To ﬁnd *p(γ) , choose an arbitrary point (x, r)* *∈* *γ*. Then (x, r* ^{}*)

*∈*

*p(γ*) whenever (x, r* ^{}*)

*∈*

*A*˜ and

*t*

*≤*

*r*

^{}*< te*

*, where*

^{λ}*t*= inf

*{s*:

*r < s,*(x, s)

*∈*

*A*˜

*\γ}*.

In the next result we give an alternative way to ﬁnd *p(γ) . Observe that*
*γ* = max Γ if and only if *πγ* =*A*.

5.6. **Lemma.** *Let* *γ* *∈* Γ*, and let* *x* *∈* *πγ,* *y*^{}*∈* *A* *\πγ* *be such that*

*|x−y*^{}*| ≤ed(πγ, A\πγ). Then* *x, y*^{}* ∈p(γ).*

*Proof.* Choose *y* *∈* *πγ* and *γ*^{}*∈* Γ such that *x, y ∈* *γ* and *x, y*^{}* ∈* *γ** ^{}*.
By 3.4(10) we have

*|x−y*

^{}*|*

*> e*

^{λ}*|x−y|*, and hence

*x, y*

*<x, y*

*. This implies*

^{}*γ < γ*

*, and thus*

^{}*p(γ)≤γ*

*. I f*

^{}*p(γ*)=

*γ*

*, then*

^{}*p(γ) contains a point*

*x, y*

*such that*

^{}*|x−y*^{}*|< e*^{−λ}*|x−y*^{}*| ≤e*^{1−λ}*d(πγ, A\πγ)≤d(πγ, A\πγ*).

By 3.4(1) we have *y*^{}*∈A\πγ*. Since *x∈πγ*, this gives a contradiction.

5.6. **Lemma.** *Let* *γ* *∈*Γ*, and let* *x, y∈πγ,* *z* *∈A\πγ. Then*

*|x−y| ≤e*^{−}^{(γ,p(γ))}*|x−z|.*

*Proof.* Let *β* and *γ** ^{}* be the members of Γ containing

*x, y*and

*x, z*, respectively. By 3.4(8), we have

*β*

*≤*

*γ*. Since

*x*

*∈*

*πγ*

*∩πγ*

*and since*

^{}*z /∈*

*πγ*, we have

*γ < γ*

*by 3.4(4). Hence*

^{}*p(γ)*

*≤*

*γ*

*. By 3.4(3), there is*

^{}*w*

*∈*

*p(γ) with*

*x, y*

*< w≤ x, z*. Consequently,

*γ, p(γ)*

*≤(x, y, w)≤*log *|x−z|*

*|x−y|,*
and the lemma follows.

The following order-theoretic result is needed in Section 6.

5.8. **Lemma.** *Let* (P,*≤*) *be a family tree, and let* *g:* *P* *→* [0,*∞*) *be an*
*unbounded function. Then there is a sequence* (x*j*) *in* *P* *such that* *g(x**j*) *→ ∞*
*and such that one of the following three conditions is satisﬁed:*

(1) *x*1 *> x*2 *>· · ·*;
(2) *x*_{1} *< x*_{2} *<· · ·*;

(3) *x**i* *and* *x**j* *are incomparable for all* *i*=*j.*
*Proof.* For *x∈P* we set

*h(x) = sup{g(y) :y < x} ∈*[0,*∞*]

with the agreement that *h(x) = 0 for all minimal elements* *x* of *P*. We consider
three cases.

*Case* 1. *h(x)<∞* for all *x* *∈P*. Now max*P* does not exist. Fix an arbitrary
*y*1 *∈P* and set *y**n+1* =*p** ^{n}*(y1) for

*n∈*N. Then

*y*

*n*

*< y*

*n+1*and

*h(y*

*n*)

*≤h(y*

*n+1*) for all

*n*. We ﬁrst show that

*h(y*

*n*)

*→ ∞*. Let

*M >*0 , and choose

*x*

*∈*

*P*with

*g(x)> M*. Setting

*y*=

*p(x∨y*

_{1}) we have

*y∈P*

^{+}(y

_{1}) , and hence

*y*=

*y*

*for some*

_{n}*n*by (5.3). Thus

*h(y*

*n*)

*≥g(x)> M*.

I f sup*{g(y** _{n}*) :

*n*

*∈*N

*}*=

*∞*, there is a subsequence (x

*) of (y*

_{n}*) such that*

_{n}*g(x*

*n*)

*→ ∞*and (2) is true. Suppose that sup

*{g(y*

*n*) :

*n*

*∈*N

*}*=

*c <*

*∞*. Since

*h(y*

*)*

_{n}*→ ∞*, there is a sequence

*n*

_{0}

*< n*

_{1}

*< n*

_{2}

*<*

*· · ·*in N such that

*h(y*

_{n}_{0})

*> c*and

*h(y*

*n*

*)*

_{i+1}*> h(y*

*n*

*) for all*

_{i}*i*

*≥*0 . Choose elements

*x*1

*, x*2

*, . . .*in

*P*such that

*x*

_{i+1}*< y*

_{n}*and*

_{i+1}*g(x*

*)*

_{i+1}*> h(y*

_{n}*) for all*

_{i}*i*

*≥*0 . Then

*g(x*

*)*

_{i}*→ ∞*. It suﬃces to show that

*x*

*j*and

*x*

*i+1*are incomparable whenever 1

*≤j*

*≤i*.

If *x**i+1* *≤x**j*, then *x**i+1* *< y**n**j*, and we obtain the contradiction
*h(y*_{n}* _{i}*)

*< g(x*

*)*

_{i+1}*≤h(y*

_{n}*)*

_{j}*≤h(y*

_{n}*).*

_{i}Assume that *x**j* *< x**i+1*. Now *x**i+1* and *y**n** _{j}* are in

*P*

^{+}(x

*j*) . Since this is linearly ordered by (5.3), either

*x*

*i+1*

*< y*

*n*

*j*or

*y*

*n*

*j*

*≤*

*x*

*i+1*. As above, the ﬁrst case is impossible. In the second case,

*x*

*=*

_{i+1}*y*

*for some*

_{k}*k*, and we get the contradiction

*c < h(y**n*_{0})*≤h(y**n** _{i}*)

*< g(x*

*i+1*) =

*g(y*

*k*)

*≤c.*

*Case* 2. There is *y* *∈* *P* such that *h(y) =* *∞* and such that *h(z)* *<* *∞* for
every child *z* of *y*. Let *C* = *p*^{−1}*{y}* be the set of all children of *y*. I f *g* is
unbounded in *C*, we choose a sequence (x*n*) in *C* with *g(x**n*) *→ ∞*; then (x*n*)
satisﬁes (3). If *g* is bounded in *C*, then *h* is unbounded in *C*, and there is a
sequence *z*0*, z*1*, . . .* in *C* such that *h(z**i+1*)*> h(z**i*) and *h(z**i*) *→ ∞*. For *i≥*0 we
choose elements *x*_{i+1}*< z** _{i+1}* with

*g(x*

*)*

_{i+1}*> h(z*

*) . Now*

_{i}*g(x*

*)*

_{i}*→ ∞*. For

*i*=

*j*we have

*x*

*i*

*∨x*

*j*=

*y*, and hence

*x*

*i*and

*x*

*j*are incomparable.

*Case* 3. Cases 1 and 2 do not occur. Then there is a sequence *y*1*, y*2*, . . .* in *P*
such that *h(y**n*) =*∞* and *y**n* =*p(y**n+1*) for all *n∈*N. I f sup*{g(y**n*) :*n∈*N*}*=*∞*,
then (y* _{n}*) has a subsequence (x

*) such that*

_{n}*g(x*

*)*

_{n}*→ ∞*and (1) holds. Suppose that

sup*{g(y**n*) :*n∈*N*}*=*c <∞.*

We deﬁne a sequence *n*_{1} *< n*_{2} *<* *· · ·* in N and elements *x*_{i}*< y*_{n}* _{i}* inductively as
follows. Set

*n*1 = 1 and choose

*x*1

*< y*1 with

*g(x*1)

*> c*. Assume that

*n*

*i*and

*x*

_{i}*< y*

_{n}*have been deﬁned. Since [x*

_{i}

_{i}*, y*

_{n}*] is ﬁnite, there is*

_{i}*n*

_{i+1}*> n*

*such that*

_{i}*x*

*i*is not smaller than

*y*

*n*

*i+1*. Choose

*x*

*i+1*

*< y*

*n*

*i+1*such that

*g(x*

*i+1*)

*> g(x*

*i*) + 1 . Now

*g(x*

*i*)

*→ ∞*, and it suﬃces to show that

*x*

*j*and

*x*

*i+1*are incomparable whenever 1

*≤j*

*≤i*.

If *x*_{j}*≤x** _{i+1}*, then

*x*

_{j}*< y*

_{n}

_{i+1}*≤y*

_{n}*, a contradiction. If*

_{j+1}*x*

_{j}*> x*

*, then*

_{i+1}*x*

*and*

_{j}*y*

*n*

*i+1*are in the linearly ordered set

*P*

^{+}(x

*i+1*) , and hence either

*x*

*j*

*< y*

*n*

*i+1*

or *x**j* *≥y**n**i+1*. In the ﬁrst case we again get the contradiction *x**j* *< y**n**j+1*. I n the
second case, *x**j* *∈* [y*n*_{i+1}*, y*1] , and hence *x**j* = *y**k* for some *k*. This is impossible,
since *g(y** _{k}*)

*≤c < g(x*

*) .*

_{j}