The continuum self-similar tree
Mario Bonk Huy Tran



The continuum self-similar tree





Mario Bonk Department of Mathematics,
University of California, Los Angeles, CA 90095, USA, mbonk@math.ucla.edu
Huy Tran Institut für Mathematik, Technische Universität Berlin,
Sekr. MA 7-1,
Strasse des 17. Juni 136,
10623 Berlin, Germany, tran@math.tu-berlin.de






*
    Mario Bonk and Huy Tran
    Jan 2018
===========================




We introduce the continuum self-similar tree (CSST) as the attractor of an iterated function system in the complex plane. We provide a topological characterization of the CSST and use this to relate the CSST to other metric trees such as the  continuum random tree (CRT) and Julia sets of postcritically-finite polynomials. 

 

Primary: 37C70; Secondary: 37B45.





§ INTRODUCTION


In this expository paper, we study the topological properties of a 
certain subset  of the complex plane . It  is defined as the attractor of an iterated function system. As we will see,  has a self-similar “tree-like" structure with very regular branching behavior. In a sense it is the simplest object of this type. Sets homeomorphic to    appear in various other contexts. Accordingly, we give the set  a special name, and call it the continuum self-similar tree (CSST). 

To give the precise definition of  we consider the following contracting  homeomorphisms  on 
: 

    f_1(z) = 12z-12,     f_2(z) =  12z̅ + 12,     f_3(z) =  i2z̅ + i2.

Then the following statement is true.

 There exists a  unique 
non-empty compact set T  satisfying 

    T=f_1(T)∪ f_2(T)∪ f_3(T).

 

Based on this fact, we make the following definition. 


The continuum self-similar tree (CSST) is the set T 
  as given by Proposition <ref>.

  In other words, T is the attractor of the iterated function system {f_1,f_2,f_3} in the plane.
 Proposition <ref> is a special case of 
 well-known more general results in the literature (see 
<cit.>, <cit.>, or 
 <cit.>, for example). We will recall the argument  that leads to Proposition <ref> in Section <ref>. 
 
 Spaces of a similar topological type as   have appeared in the literature before (among the more recent examples is  the antenna set in <cit.> or  
Hata's tree-like set considered in <cit.>).  For a representation of  see Figure <ref>.









To describe the topological properties of , we introduce the  following concept.

 
A (metric)  tree is a compact, connected, and locally connected  metric space (T,d) containing at least two points such that for all  a,b∈ T
with  a b  there exists a unique arc α T with endpoints a and b.

In other words, any two distinct points a and b in a metric tree  can be joined by a  unique  arc α in T. It is convenient to allow a=b here in which case α={a}={b} and we   consider α as  a degenerate arc.  


In the following, we will usually call 
a metric space 
as in Definition <ref> a tree and drop the word “metric" for simplicity.  It is easy to see that the concept of a tree 
 is essentially the same as   the concept of a dendrite 
that  appears in the literature (see, for example, <cit.>, <cit.>,  <cit.>).  More precisely, a metric space T is a tree if and only if it is a non-degenerate dendrite (the simple proof is recorded in <cit.>).  If one drops the compactness assumption  in Definition <ref>, but requires in addition   
that the space is geodesic (see below for the definition), then one is 
led to the notion of a real tree. They  appear in many areas of mathematics (see <cit.>, for example). 

 The following statement
 is  suggested by Figure <ref>.
  
  The continuum self-similar tree    is a metric tree. 
   

 


  
  If T is a tree,  then for x∈ T we  denote by  ν_T(x)∈∪{∞}   the number of (connected) components of T\{x}. This number ν_T(x) is called the valence  of x. If  ν_T(x) = 1, then x is called a leaf of T. If ν_T(x)≥ 3, then x is a branch point of T. If  ν_T(x)=3, then we also call x  a triple point.

The following statement is again suggested by Figure <ref>.

Each branch point of the tree  is a triple point, and these triple points are dense in . 


The set   has an interesting geometric property,  namely it is a quasi-convex subset of ., i.e., any two points 
in  can be joined by a path whose length is comparable to the distance of the points. 
 

  There exists a constant 
L>0 with the following property: if a,b∈ and α is the unique arc in  joining  a and b, then 

    (α)≤ L |a-b|.
  


Note that a unique (possibly degenerate) arc α joining a and b exists, because  is a 
tree  according to 
 by Proposition <ref>.  
 
 Proposition <ref> implies that  we can define a new metric ϱ on  
by setting 
ϱ(a,b)=(α)
for a,b∈,  
where α is the unique arc in  joining  a and b. 
Then the metric space (, ϱ) is   geodesic, i.e., any two points in (, ϱ) can be joined by a path in  whose length is equal to the distance of the points.  It immediately follows from  Proposition <ref> that metric spaces  (as equipped with the Euclidean metric) and (, ϱ) are bi-Lipschitz equivalent by the identity map. 



A natural  way to construct (,ϱ), at least  as an abstract metric space, is as follows. We start with a  line segment J_0 of length 2. Its  midpoint c subdivides  J_0 into two line segments of length 1. We glue 
to c one of the endpoints of another line segment s of the same length. Then we obtain a set  J_1 consisting of three line segment of length 1. The set J_1 carries the natural  path metric. We now repeat this procedure inductively. At the nth step we obtain a tree J_n consisting of 
3^n line segments of length 2^1-n. To pass to J_n+1, each of these line segments s is subdivided by its midpoint c_s into two line segment of length 2^-n and we glue to c_s one endpoint of another line segment of length 2^-n.  

In this way, we obtain  an ascending sequence J_0 J_1…  of  trees equipped with  a geodesic metric. 
The union J=⋃_n∈_0J_n carries a natural path metric ϱ that agrees with the metric on J_n for each n∈_0. As an abstract space  one can define (,ϱ) as the completion of the metric 
space (J,ϱ).

 If one wants to realize  as a subset of  by this construction, one starts with the initial line segment
J_0=[-1,1], and adds s=[0,i] in the first step
to obtain J_1=[-1,0]∪ [0,1]∪ [0,i]. Now one wants to choose  suitable Euclidean similarities f_1, f_2, f_3 that copy the interval [-1,1] to [-1,0], [0,1], [0,i], respectively.
One  hopes to  realize J_n  as a subset of  using an inductive procedure based on 

    J_n+1=f_1(J_n)∪ f_2(J_n)∪ f_3(J_n),    n∈_0.

In order to  avoid self-intersections and   ensure that each set J_n is indeed a tree, one has to be  careful about the orientations of the maps f_1, f_2, f_3. The somewhat non-obvious choice  of these  maps as in  (<ref>) leads to the desired result.  See Proposition <ref>  and the discussion near the end of Section <ref> 
for a precise statements how to use the maps in (<ref>) to realize the sets J_n as subsets of , and obtain  (as in Definition <ref>) as the closure 
of ⋃_n∈_0 J_n. A representation of J_5 is shown in Figure <ref>.














The conditions in Proposition <ref> actually characterize the CSST topologically.



A metric tree (T,d) is homeomorphic to the continuum self-similar tree    if and only if the following conditions are true:


  (i) For every point x∈ T  we  have 
ν_T(x)∈{1,2,3}. 


  (ii)  The set of triple points {x∈ T: ν_T(x) = 3} is a   dense subset of T.





We will  derive Theorem <ref>  from a slightly more general statement.  For its formulation let 
 m∈N with m≥ 3. We consider the class T_m consisting of all metric trees T such that
 

  (i) for every point x∈ T  we  have 
ν_T(x)∈{1,2,m}, and 


  (ii)  the set of branch  points {x∈ T: ν_T(x)=m } is a   dense subset of T.

Note that by Proposition <ref> the CSST   satisfies the conditions in Theorem <ref> with m=3, and so
 belongs to the class of trees _3. Now the following statement is true which contains Theorem <ref> as a special case. 

  Let m∈ with m≥ 3.  Then all trees in T_m are homeomorphic to each other.


 Theorems <ref> and <ref>  are not new. In a previous version of this paper, we considered Theorem <ref> as a “folklore"  statement,
  but we did not have a reference for a proof. Later, the paper 
<cit.> was brought to our attention which contains a more general result which implies Theorem <ref>, and hence also Theorem <ref>  (see <cit.>; the proof there seems to be incomplete though—the continuity of the map h on the dense subset of X needs more justification). 
Theorem <ref> was explicitly stated in <cit.>, but it  seems that the origins of Theorem <ref> can be traced back much further to <cit.> (see also <cit.>, and <cit.> for more pointers to the relevant older literature about dendrites). 

We will give a complete proof of Theorem <ref>. It  is based on  ideas that are quite different from those in <cit.>, but we consider our method of proof  very natural.  It is also related to some other recent work, in particular <cit.>;  so one can view the present paper as an introduction to these ideas.  We will say more about our motivation below. 




Our proof of Theorem <ref> can be outlined as follows. 
 Fix m as in the statement and consider a tree T in _m. 
 Then we cut T into  m
 subtrees 
 at  a carefully chosen branch point. This process is repeated inductively. One labels the subtrees obtained in this way by finite 
 words consisting of  letters in the   alphabet   𝒜 ={1,2, …, m}. The labels are  chosen so that  if S is another tree in _m and one decomposes S in a similar manner, then  one has the same combinatorics (i.e., intersection and inclusion pattern)  for the subtrees in T and S. The desired homeomorphism 
 between  T and S can then be obtained from a general statement that produces a homeomorphism between two spaces, if they admit matching decompositions  into pieces satisfying suitable conditions
 (see  Proposition <ref>). 
 






The CSST is related to metric trees appearing in other areas of mathematics. One of these objects is the 
 (Brownian) continuum random tree (CRT). This is a random  tree introduced by  Aldous <cit.> when he studied the scaling limits of simplicial trees arising  from the critical Galton-Watson process. One can describe the  CRT as follows. We consider a sample of Brownian excursion (_t)_0≤ t≤ 1 on the interval [0,1]. For s,t∈ [0,1], we set 

    d_(s,t) = (s) + (t) - 2 inf{(r): min(s,t)≤ r ≤max(s,t)}.
 Then d_ is a pseudo-metric on [0,1]. 
We define an equivalence relation on [0,1] by setting s∼ t if d_(s,t) = 0. Then d_ descends to a metric on  the quotient space T_=[0,1]/∼. The metric space 
(T_, d_)
  is almost surely a metric tree (see <cit.>).
Curien <cit.> asked the following question. 



Is the topology of the CRT almost surely constant, that is, are  two independent samples of the CRT  almost surely homeomorphic?


This question was the original motivation  for the present work and  
we found  a positive answer based on the following statement.  

 
A sample T of the  CRT is almost surely homeomorphic to the CSST .



As we discussed, a sample T of the CRT is almost surely a 
metric tree (see <cit.>).
Moreover, for such a sample T 
almost surely for every point x∈ T, the valence ν_T(x)  is either 
1, 2 or 3, and the set {x: ν_T(x)=3} of triple points is  dense in T 
(see <cit.> or <cit.>). 
It follows from Proposition <ref> and 
Theorem <ref> that a sample T of the CRT is almost surely homeomorphic to the CSST .   




Informally, Corollary <ref>  says  that  the topology of the CRT is (almost surely) constant and given by the topology of a deterministic model space, namely the CSST. In particular, almost surely any two independent samples of the CRT are 
homeomorphic. This  answers Curien's question in the positive.   As we found out after we had obtained   proofs for Theorem <ref> and Corollary <ref>, Curien's question had already been answered implicitly in <cit.>. There the authors used the distributional self-similarity property of the CRT and showed that the CRT is isometric to a metric space with a random metric. This space is constructed similarly to the CSST as the attractor of an iterated 
function system with maps  very similar to (<ref>) (they contain an 
additional parameter though  which is unnecessary if  one uses the maps in  (<ref>)).  
 

 


















 


 
An important source of trees is given by  Julia sets of 
postcritically-finite polynomials without  periodic critical points in .  It follows from <cit.> (or see <cit.>) that the Julia sets of such  polynomials are indeed trees. One can show    that the Julia set 𝒥(P) of the polynomial P(z)=z^2+i (see Figure <ref>) satisfies the conditions in Theorem <ref>. Accordingly, 𝒥(P) is homeomorphic to 
the CSST. 








 
 














































There are several directions in which one can pursue these topics  further. For example, one can  study the topology of more general trees than those in the classes T_m.  One  may want to  replace m with  any finite (or even infinite) list  of allowed valences for branch points, including branch points of infinite valence. In an earlier version of our paper, we discussed 
this  in more detail. Since we learned  that 
these results are already contained in <cit.>, we decided 
to skip this in the present version.  

There is one important variant 
of Theorem <ref>  that we like to mention though. Namely, one can consider the (non-empty) class T_∞ of trees T such that ν_T(x)∈{1,2,∞} for all x∈ T and such that the set of branch points of T (i.e., in this case the set 
{x∈ T:ν_T(x)=∞}) is dense in  T. Then all trees in 
T_∞ are homeomorphic to each other (our method of proof  does not directly apply here, but 
one can  use our approach based on a more general version of Proposition <ref>). Moreover, each tree T in T_∞ is universal in the sense that every tree S admits a topological embedding into T. These results are due to Waszewski <cit.> (see <cit.> for a modern exposition of this universality property; see also <cit.> for a discussion of a universality property of the trees in T_m, 
m∈, m≥ 3). 






















 
 Trees in T_∞ are also interesting, because they naturally arise in probabilistic models. More specifically, the so-called stable trees with index α∈ (1,2]  are generalizations of the CRT  (see <cit.> for the definition). For  fixed α∈ (1,2), a  sample T of such a stable tree  belongs to T_∞ almost surely  <cit.>. By the previous discussion this implies  that   two independent samples of stable trees for given   α∈ (1,2) are almost surely homeomorphic.  Note that  the Julia set of a polynomial never belongs to  T_∞. This follows from results due to Kiwi (see  <cit.>).
 
 Another direction for further investigations are questions that are more related to  geometric properties of metric trees, in contrast to purely topological properties. In particular, one can study the quasiconformal geometry of the CSST and other trees (for a survey on the general topic of quasiconformal geometry see <cit.>). 
 
 
 One of the basic notion here is the concept of quasisymmetric equivalence. By definition two metric spaces X and Y are called quasisymmetrically equivalent if there exists a quasisymmetry f  X Y. Roughly speaking,  a quasisymmetry is a homeomorphism with good geometric control: it sends metric balls to “roundish" sets with uniformly controlled eccentricity  (for the precise definition of a quasisymmetry and other basic concepts of quasiconformal geometry see <cit.>). 
Since every quasisymmetry is a homeomorphism, two spaces are homeomorphic if they are quasisymmetrically equivalent.
So this gives a stronger type of equivalence for metric spaces that has a more geometric flavor and goes beyond mere topology. 

A natural problem  in this context is to characterize the CCST  up to quasisymmetric equivalence, similar to 
Proposition <ref> which gives a topological characterization. This problem is solved in <cit.>. 
The precise statement is too technical to be included here, but 
roughly speaking the conditions on a metric tree T to be quasisymmetrically equivalent to  are similar in sprit to 
the conditions in Proposition <ref>, but of a more “quantitative" nature. 


For example, one of the conditions stipulates that 
T be trivalent (i.e., all branch points of T are triple points),
but not only should the  branch points of T form a dense subset of T,
 but  T should be uniformly branching in the sense that every arc α T contains a branch point p of 
 height H_T(p) 
 comparable to the diameter of α. Here the height 
 H_T(p) is the diameter of the third largest branch of p
 (see the discussion around (<ref>) for more details).  
 
In our proof of  Theorem <ref>   we 
first realized that this concept of height of a branch point plays a very important role in understanding the geometry and topology of trees. 
This concept  is also used in  <cit.>.

The present  paper and   <cit.> have another 
 common feature. In all of these works  it is important to have   good decompositions of the spaces studied,  depending on the problem under consideration. This line of thought in the context of quasiconformal geometry can be traced back to 
 <cit.>. More recently, Kigami <cit.> 
 has systematically investigated such decompositions 
 in the general framework  of partitions of a space given by sets  that are labeled by the vertices of a (simplicial) tree. 
This common philosophy with other recent work is the main motivation why we wanted to present the proof of  the known 
Theorem <ref> from our perspective. 
 
 One can use the characterization of the CSST up to quasisymmetric equivalence established in <cit.> to prove the following statement (unpublished work by the authors): if the Julia set 𝒥(P) of a postcritically-finite polynomial P with no  periodic critical points in  is homeomorphic to the CSST, then  𝒥(P) is  quasisymmetrically equivalent to the CSST.

 
   
Finally,  we mention in passing that the geometric properties of the continuum random tree (CRT)  were considered in the recent paper <cit.> by Lin and Rohde. Though
Lin and Rohde 
do not study quasisymmetric equivalence, many  of their considerations still fit   into the general framework of quasiconformal geometry.   

  
 
 








 

 

 
 
 

  

 
 



The present  paper is organized as follows.  In  Section <ref>  we state and prove a  general criterion for two metric spaces to be homeomorphic based on the existence of combinatorially equivalent decompositions of the spaces. 
In Section <ref> we collect some general facts about trees that we use later. The  CSST  is  studied 
in Section <ref>. There we provide proofs of 
Propositions <ref>, <ref>, <ref>, 
and <ref>.   In Section <ref>
 we explain how to decompose  trees in T_m with 
 m∈, m≥ 3. 
 Based on this, we then present  a proof Theorem <ref>.   Theorem <ref> is an immediate consequence.
 
  

§ CONSTRUCTING  HOMEOMORPHISMS BETWEEN SPACES
 
 
Throughout this paper, we use fairly standard metric space notation. If (X,d) is a metric space, then we denote by B(a,r)={x∈ X  d(a,x)<r} the open ball of radius r>0 centered at a∈ X.  
If A,B X, then  (A)=sup{d(x,y):x,y∈ A}  is the diameter of 
A and (A,B)=inf{d(x,y): x∈ A,  y∈ B} the (minimal) distance of  A and B. Similarly, if a∈ X, then (a,B)=
({a},B) denotes the distance of the point a to the set B. Finally, if  is a path in X, then 
() stands for  its length. 

Before we discuss trees in more detail and turn our attention to  the CSST, we will establish the following proposition that is  the key to showing that  two trees are homeomorphic. The statement will also give us some guidance for  the desired properties of tree decompositions that we will discuss in the following sections. 
 The proposition  is inspired by  <cit.>, which provided geometric conditions for the  decomposition of a space that can be used to construct quasisymmetric homeomorphisms.

  Let (X,d_X) and (Y,d_Y) be  compact metric spaces. Suppose that for each n∈, the space  X admits a decomposition   X=⋃_i=1^M_n X_n,i as a finite union of non-empty  compact  subsets X_n,i, i=1, …, M_n∈, with the following 
properties for all n, i, and j: 


  (i) Each set X_n+1,j is the subset of some set X_n, i.


  (ii)  Each set X_n, i is equal to  the union of some of the sets  X_n+1,j.


  (iii)   max_1≤ i≤ M_n (X_n, i) → 0 as n→∞.


Suppose that for n∈ the space Y admits a decomposition Y=⋃_i=1^M_n Y_n,i as a union of non-empty compact  subsets Y_n,i, i=1, …, M_n, with  properties analogous to (i)–(iii) such that 

    X_n+1,j  X_n,i Y_n+1,j Y_n,i

and 
 
    X_n,i∩ X_n,j≠∅ Y_n,i∩ Y_n,j≠∅
  
for all n, i,  j. 


Then there exists a unique homeomorphism f  X Y such that 
f(X_n,i)=Y_n,i for all n and i.  

In particular, under these assumptions the spaces X and Y are homeo­morphic. 


We define a map f  X Y as follows. For each point x∈ X, by (ii) and (iii) there exists a nested sequence of sets X_n,i_n, n∈,  such that
{x } = ⋂_n X_n,i_n.
Then the corresponding sets Y_n,i_n, n∈, are also nested by (<ref>). Since these sets are non-empty and compact,  by condition (iii) for the space  Y this implies  that there exists a unique point y∈⋂_n Y_n,i_n. We define f(x)=y.  

Then f is well-defined. To see this,  suppose  we have  another nested sequence X_n,i'_n, n∈,  such that
{x } = ⋂_n X_n,i_n'. Then there exists a unique point y'∈⋂_n Y_n,i'_n. Now x∈ X_n,i_n∩ X_n,i'_n and so 
Y_n,i_n∩ Y_n,i'_n∅  for all n∈ by (<ref>). By condition (iii)  for Y, this is only possible if y=y'. So f  X Y is indeed well-defined. 


One can define a map g  Y X by a similar procedure. Namely, for 
each y∈ Y we can find a nested sequence Y_n,i_n, n∈,  such that
{y } = ⋂_n Y_n,i_n.
 Then there exists a unique point x∈⋂_n X_n,i_n and if we set g(y)=x, we obtain a well-defined map g  Y X. 
 
 It is obvious from the definitions that the maps f and g are inverse to each other.   Hence they define  bijections between X and Y. 
 
 Conditions (i) and (ii) imply that if X_k,i is a set in one of the decompositions of X and x∈ X_k,i, then there exists a nested sequence 
 X_n,i_n, n∈, with X_k,i_k=X_k,i and {x } = ⋂_n X_n,i_n. This implies that f(x)∈ Y_k,i and so f(X_k,i) Y_k,i.
 Similarly, g(Y_k,i) X_k,i. Since g=f^-1, we have  f(X_k,i)=Y_k,i as desired. It is clear that this last condition together with our assumptions determines f uniquely. 
 
 
 It remains to show that f is a homeomorphism. For this  it suffices to prove  that f and f^-1=g are continuous. Since the roles of f and g are completely symmetric, it is enough  to establish  that f is continuous.
 
 For this,   let   >0 be arbitrary. By (iii) we can choose n∈ such that

    max{ (Y_n, i) : 1≤ i≤ M_n} < /2.

Since the sets X_n,i are compact, there exists δ>0 such that

    (X_n,i, X_n,j) >δ,

whenever i,j∈{1, …, M_n} and  X_n,i∩ X_n,j = ∅.


Now suppose that a,b∈ X are arbitrary points with  d_X(a,b)< δ.
We claim that then  d_Y(f(a),f(b))<. Indeed, we can find i,j∈{1, …, M_n} such that a∈ X_n,i and b∈ X_n,j. Since 
d_X(a,b)< δ, we then necessarily have X_n,i∩  X_m,j∅ by definition of δ.
So   Y_n,i∩  Y_n,j∅ by (<ref>). Moreover, f(a)∈ f(X_n,i)=Y_n,i and f(b)∈ f(X_n,j)=Y_n,j.
Hence  

    d_Y(f(a), f(b)) ≤ (Y_n,i) +  (Y_n,j) < .

The continuity of f follows. 




 

§ TOPOLOGY OF TREES
 
 
  In this section we fix some terminology and collect some general facts about trees. We do not claim any originality of this material. All of it is standard and well-known, but we did not try to track it down    in the literature. Our objective is to make our presentation self-contained, and to have convenient reference points   for future work. For general background on trees or dendrites we refer 
 to <cit.>, <cit.>,  <cit.>), and the literature mentioned there.  
  
  
 
 An arc α in a metric space  is a homeomorphic image of the  unit interval [0,1].  The points corresponding to 0 and 1 are called the endpoints 
 of α. 
 
 Let  T be a tree. Then the last part of Definition <ref> is equivalent to the requirement that for all points a,b∈ T with a b, there 
 exists a unique arc in T  joining a and b, i.e., it has the endpoints 
 a and b. We use the notation [a,b]  for this unique arc. 
 It is convenient to allow a=b here. Then [a,b] denotes the degenerate arc consisting  only of the point a=b. 
 Sometimes we want to remove one or both endpoints from the arc [a,b]. Accordingly, we define
  (a,b)=[a,b]{a,b},  [a,b)=[a,b]{b} and 
  (a,b]=[a,b]{a}.   In Section <ref> we will not use this notation for arcs in a tree. There [a,b] will always denote the Euclidean line segment joining  two points a,b∈.  
  
  A metric space X is called path-connected if any two points a,b∈ X can be joined by a path in X, i.e., there exists a continuous map γ [0,1] X such that γ(0)=a and γ(1)=b. The space X is arc-connected if any two distinct points in X can be joined by an arc in X. The image 
  of  a path joining two distinct points in a metric space always contains an arc joining these points (this  follows from  
the fact that every Peano space is arc-connected; see <cit.>). In particular, 
every path-connected metric space is arc-connected. 
 
  Let (T,d) be a tree. Then for each >0 there exists δ>0 such that for all a,b∈ T with d(a,b)<δ we have ([a,b])<.

 Fix >0. Since T is a compact, connected, and  locally connected  metric space, it is a Peano space. So by the Hahn-Mazurkiewicz theorem there exists a continuous surjective map φ [0,1] T of the unit interval onto T <cit.>. By uniform continuity of φ we can represent [0,1]  as a union [0,1]=I_1∪…∪ I_n of finitely many 
closed intervals I_1, …, I_n [0,1]  with (X_k)</2,
where X_k=  φ(I_k) 
for k=1,… ,n. The sets X_k=φ(I_k) are compact. This implies that  there exists δ>0 such that (X_i, X_j)>δ, whenever i,j∈{1,…, n} and 
X_i∩ X_j=∅. 

Now let a,b∈ T with d(a,b)<δ be arbitrary. We may assume a b. 
Then there exist i,j∈{1,…, n} with a∈ X X_i and b∈ Y X_j. 
By choice of δ we must have X∩ Y∅. As continuous images of intervals,
the sets X and Y are path-connected. Since X∩ Y∅, the union X∪ Y that contains the points a and b is also path-connected. This implies that  X∪ 
Y is arc-connected, and so there exists an arc α X∪ Y with endpoints a and b. 
The unique such arc in the tree T is [a,b], and so [a,b]=α X∪ Y. This implies 

    ([a,b])≤(X)+(Y)<,

as desired. 
 
  
 
 
   Let (T,d) be a tree and p∈ T. Then the following statements are true:
 

  (i)  Each  component U of T{p} is an open and arc-connected subset of T.  


  (ii)  If  U is a component of T{p}, then U=U∪{p} and  ∂ U={p}. 
 


  (iii)   Two points a,b∈ T{p} lie in the same component of T{p} if and only if p∉[a,b]. 
 
  
 
 (i) The set T{p} is open. Since T is locally connected,  each component U of T{p} 
is also open.   

For a,b∈ U we write a∼ b if a and b can be joined by a path in U. Obviously,
this defines an equivalence relation on U. The equivalence classes are open subsets
of T. To see this,  suppose  a,b∈ U can be joined by a path β in U. Then for all points 
x in a sufficiently small neighborhood V U of b we have [b,x] U as follows from  Lemma <ref>. 
So by  concatenating β with (a parametrization of) the arc [b,x], we obtain a
path β' in U that joins a and x∈ V. This shows that every point b in the equivalence class of a has a neighborhood V that also belongs to this equivalence class. 

We see that the equivalence classes of ∼ partition U into open sets. Since U is connected, there can only be one such set. It follows that  U is path-connected and 
hence also arc-connected. 


(ii) Let U be a (non-empty) component of T{p}. We choose  a point a∈ U. 
The set  [a,p) is  connected, contained in T{p}, and meets U in a. Hence [a,p) U. This implies that p∈U. On the other hand, the set 
U∪{p} is closed, because its complement is a union of components of T{p} and hence open by (i). Thus  U=U∪{p}. By (i) no point in U is a boundary point of U, and so ∂ U={p}. 


(iii) If a,b∈ T{p} and p∉[a,b], then [a,b] is a  connected subset of  
T{p}. Hence [a,b] lies in a component U of T{p}. In particular, a,b∈ [a,b] lie in the same component U of T{p}.

Conversely, suppose that a,b∈ T{p} lie in the same component U of 
T{p}. We know by (i) that U is arc-connected. Hence there exists a (possibly degenerate) arc α U with endpoints a and b. But the unique such arc in T is [a,b]. Hence [a,b]=α U T{p}, and so p∉[a,b].  

A subset S of a tree (T,d) is called a subtree of T if S equipped with the restriction of the metric d is also a tree as in Definition <ref>. Every subtree S of T contains 
two points and hence a non-degenerate arc. In particular, every subtree S of T is an infinite, actually uncountable set.


The following statement characterizes 
 subtrees. 


   Let (T,d) be a tree. Then a set  
 S T is a subtree of T if and only if S contains at least two points and is  closed and connected.  
  
 
  
 If S is a subtree of T, then S contains at least two points, and is connected and 
 compact. Hence  it is a closed subset of T. Conversely, suppose that S contains at least two points and is closed and connected. Then S is compact, because T is compact.
 
 Suppose that a,b∈ S, a b, are two distinct points in S. 
 We consider the arc [a,b] T. Suppose there exists a point 
 p∈ [a,b] with  p∉S. Then p a,b, and so by Lemma <ref> (iii), the points a and b lie in different components of T{p}. This is impossible, because the connected set S T{p} must be  contained in exactly one component of T{p}. This shows that [a,b] S and so 
 the points a and b  can be joined by an arc in S. This arc in S is unique, because it is unique in T. 
 
 It remains to show that S is  locally connected, i.e., every point in S has  small connected relative neighborhoods. To see this,   let a∈ S and >0 be . Then by Lemma <ref>
 we can find δ>0 such that [a,x] B(a,) whenever 
 x∈ B(a,δ). Now let M be the union of all arcs [a,x] with x∈ S∩ B(a,δ). These arcs lie in S and so M is a connected set contained in S∩ B(a,). Moreover, 
 S∩ B(a,δ) M and so M is a connected relative 
(not necessarily open) neighborhood of a in S. This shows that S is locally connected. We conclude that S is indeed a subtree of T.      



  Let (T,d) be a tree, p∈ 
T, and U a component of T{p}. Then B=U∪{p} is a subtree of T and p is a leaf of B.   

 It follows from Lemma <ref> (i) and (ii) 
that  the set  U is connected and  that B= U∪{p}=U. This implies that B is  closed and connected. Since U∅ and p∉U, the set B contains at least two points. Hence B is  a subtree of T by Lemma <ref>. Since B{p}=U is connected, p is a leaf of B.    

If the subtree B=U∪{p} is as in the previous lemma, then we call B  a branch of p in T (or just a branch of p if T is understood).  


Let (T,d) be a tree, S T be a subtree of T, and p∈ S.
Then every branch B' of p in S is contained in a unique branch B of p in T. The  
 assignment B'↦ B is an injective map between the  sets of branches of p  in S and in T. If p is an interior point of S, then this map is a bijection. 

In particular, if under the given assumptions ν_T(p) is the valence of p in T and ν_S(p) the valence of p in S, then ν_S(p)≤ν_T(p). Here we have equality if p is an interior point of S. 

If p∈ S is a leaf of T, then T has only one branch B at p, namely B=T. Hence  1≤ν_S(p)≤ν_T(p)≤ 1, and so  ν_S(p)=1. This means that p is also a leaf of S. More informally, we can say that the property of a point 
being a leaf in T is passed to subtrees that contain the point. 


 If B' is a branch of p in S, then B'=U'∪{p}, where U' is a component of S{p}. Then U' is a connected subset of T{p} and so contained in a unique component U of T{p}. Then B=U ∪{p} is a branch of p in T with B' B and it is clear that B is the unique such branch. 


To show injectivity of the map B'↦ B, let   B_1' and B_2' be two distinct branches of p in S. 
Pick points a∈ B_1'{p} and b∈ B_2'{p}. Then a and b lie in different components of S{p} and so p∈ [a,b] by Lemma <ref> (iii) applied to the tree  S. 
Hence a and b lie in different components of T{p}, and so in different branches of p in T. This implies that 
B_1' and B_2' must be contained  in different branches of p in T. This shows that the map B'↦ B is indeed injective. 

Now assume in addition that p is an interior point of S. 
To show surjectivity of the map B'↦ B, we consider a branch B of p in T. Pick a point a∈ B{p}. Then [a,p) B{p}, because B is a subtree of T. Since p is an interior point 
of S, there exists a point x∈ [a,p) close enough to p such that x∈ S{p}. If B' is the unique branch of p in S that contains x, then we have x∈ B'∩ B. This  implies B' B. Hence the map B'↦ B is also surjective, and so a bijection.   


Let (T,d) be a tree, p,a_1,a_2,a_3∈ T with p a_1, a_2, a_3 and suppose that the sets [a_1,p), [a_2,p), [a_3,p)
are pairwise disjoint. 
Then  the points a_1,a_2,a_3 lie in different components of T{p} and p is a branch point of T.  


 The arcs [a_1,p] and [a_2,p]=[p, a_2] have only the point p in common. So   their union  [a_1,p]∪ [p, a_2] 
is an arc and this arc must be equal to [a_1,a_2]. Hence p∈ [a_1,a_2] which by Lemma <ref> (iii) implies that a_1 and a_2 lie in different components of T{p}. A similar argument shows that a_3 must be contained in a component of 
T{p} different from the components containing a_1 and  a_2. In particular, T{p} has at least three components and so p is a branch point of T. The statement follows.   


Let (T,d) be a tree such that the branch points of T are dense in T. If a,b ∈ T with a b, then there exists a branch  point c∈ (a,b).


We pick a point x_0 ∈ (a,b)∅. 
Then x_0 has positive distance to both a and b. This and Lemma <ref> imply that we can find δ>0 such that 
for all x∈ B(x_0, δ) the arc [x,x_0] has uniformly small diameter and so does not contain a or b.   
  
Since branch  points are dense in T, we can find a branch  point p∈ B(x_0,δ). Then a,b∉[p,x_0]. If p∈ (a,b), we are done.

In the other case, we have  p∉(a,b). 
 If we travel from p to x_0∈ (a,b) along [p,x_0], we meet 
 [a,b] in a first point 
c∈ (a,b). Then a,b,p c. Moreover, the sets [a,c), [b,c), [p,c) are pairwise disjoint. Hence c∈ (a,b) is a branch  point of T as follows from 
 Lemma <ref>.   





 Let (X,d) be a compact, connected,  and locally connected metric space, J an index set,
p_i∈ T, and U_i a  component of X{p_i} for 
each i∈ J. Suppose that 

    U_i∩ U_j=∅
 for all i,j∈ J, i j.  Then  J is a countable set. If there exists δ>0 such that 
(U_i)>δ for each i∈ J, then J is finite.   
 

Informally, the space X cannot contain a “comb" with too many long teeth.

 We prove the last statement first. We argue by contradiction and assume that    (U_i)>δ>0 for each i∈ J, where J is an infinite index set.  Then we can choose a point x_i∈ U_i such that d(x_i,p_i)≥δ/2. 
The set A={x_i:i∈ J} is infinite and so it must have a limit point q∈ X, because X is compact.   Since X is locally connected,
there exists a connected neighborhood N of q such that 
N B(q,δ/8). Since q is a limit point of A, the set N contains infinitely many points in A. In particular, we can find 
i,j∈ J with x_i,x_j∈ N and i j. 
Then 

    (p_i, N)≥  d(p_i, x_i)-(N)≥δ/2-δ/4>0,

and so N X{p_i}. Since the  connected set N meets  U_i in the point x_i, this implies that N U_i. Similarly, N U_j. This is impossible, because we have i j and so U_i∩ U_j∅, while ∅ N U_i∩ U_j.  


To prove the first statement, note that (U_i)>0 for each i∈ J. Indeed, otherwise  (U_i)=0 for some i∈ J. Then  U_i consists of only one point a. Since X is locally connected, the component U_i of X{p_i} is an open set. So a is an isolated point of X. This is impossible, because the metric space X is connected and so it does not have isolated points. 

Now we write  J=⋃_n∈J_n, where 
J_n consists of all i∈ J such that (U_i)>1/n. Then each set J_n is finite by the first part of the proof. This implies that J is countable.  



We  can apply the previous lemma to a tree T 
and choose for each p_i a fixed branch point p of T. Then it follows that p can have at most countably many distinct 
complementary components U_i and hence there are only countably many 
distinct branches B_i=U_i∪{p} of  p. Moreover, since (B_i)=(U_i)=(U_i), there can only be  finitely many of these branches whose diameter  exceeds a given positive number δ>0. In particular, we can label the branches of p by numbers n=1,2,3,… so that 

    (B_1)≥(B_2)≥(B_3)≥…  .

 We now set 
 
    H_T(p)=(B_3)
  and call H_T(p)  the height of the branch point p in T. So the height of a branch point p is the diameter of the third largest branch of p.  










  Let (T,d) be a tree and 
δ>0. Then  there are at most  finitely many  branch  points p∈ T with height H_T(p)>δ.
 
 We argue by contradiction and assume that this is not true.
Then the  set E of branch  points p in T with H_T(p)>δ has  infinitely many  
elements. Since T is compact, the set E  has a limit point   q∈ T. 

Claim. There exists a branch Q of q 
 such that  the set E∩ Q is infinite and has  q as a limit point.
  
  Otherwise, q has infinitely many distinct branches  Q_n, n∈, that  contain a point a_n∈  E  ∩ (Q_n{q}). Then a_n is a branch point with H_T(a_n)> δ which implies 
 that a_n has at least three branches whose diameters exceed δ.  At least one of them does not contain q. If we denote such a  branch of a_n by  V_n, then V_n  is a connected subset of  T{q}.  It meets Q_n{q}, because a_n∈ (Q_n{q})∩ V_n. It follows that V_n Q_n and so (Q_n)≥ (V_n)>δ. Since the branches Q_n  of q are all 
 distinct for n∈, this contradicts Lemma <ref> (see the discussion after the proof of this lemma).
 The Claim follows.
 
 We fix a branch Q of q as in the Claim. 
For each n∈ we will now inductively construct branch points  p_n∈ E∩ (Q{q})  together with a branch B_n of  p_n and an auxiliary compact set K_n T. 
They will satisfy the following conditions for each n∈: 


  (i) (B_n)>δ,


  (ii)  the sets B_1, …, B_n are disjoint, 


  (iii)   the set K_n is compact and connected, 
and 
    B_1∪…∪ B_n K_n  Q{q}.
  




We pick  an arbitrary branch  point p_1∈ E∩ (Q\{q}) to start. Then we can choose a branch  B_1 of p_1 that does not contain q and satisfies (B_1)>δ. We set K_1=B_1. Then K_1 is a compact and connected set 
that does not contain q and meets Q, because p_1∈ K_1∩ Q. Hence K_1  Q{q}. 

Suppose for some  n∈, a branch point  p_k∈ E∩ Q, a branch B_k of p_k, and a set 
K_k with the properties (i)–(iii) have been chosen for all 1≤ k≤ n. 

Since q∉K_n, we have (q,K_n)>0, and so we can find  a branch  point p_n+1∈ E∩ (Q{p}) sufficiently close to q such that 
p_n+1∉K_n. This is possible, because q is a limit point of E∩ (Q{q}).  Since the set K_n T{p_n+1} is connected, it must be contained in a branch of p_n+1. Since there are three branches 
of p_n+1 q whose diameters exceed δ, we can pick one of them that contains neither q nor K_n. Let B_n+1 be such a branch of p_n+1. Then (B_n+1)>δ and so (i) is true for n+1.  We have  
B_n+1∩ K_n=∅; so (iii) shows that  B_n+1 is disjoint from the previously chosen disjoint sets B_1,…, B_n. This gives (ii).

Since p_n, p_n+1∈ Q{q}, the arc [p_n,p_n+1] does not contain q (see Lemma <ref> (iii)). We also have  p_n∈ B_n K_n and p_n+1∈ B_n+1, which implies that the  
 set K_n+1 K_n∪ [p_n, p_n+1]∪ B_n+1  Q{q} is compact and connected. We  have  
    B_1∪…∪ B_n∪ B_n+1 K_n ∪ B_n+1 K_n+1
     Q{q},

and so K_n+1 has  property (iii). 

 Continuing with this process, 
 we  obtain  disjoint branches B_n for all n∈ that  satisfy (i). 
The last part of Lemma <ref> implies  that this is impossible and we get a contradiction.  



§ BASIC PROPERTIES OF THE  CONTINUUM SELF-SIMILAR TREE
 

We now  we study the  properties of  the continuum self-similar tree (CSST). Unless otherwise specified, all metric notions in this section refer to the Euclidean metric on the complex plane . In this section, i always denotes the imaginary unit and we do not use this letter for indexing as in the other sections.   If a,b∈ we denote by [a,b] the Euclidean line segment in  joining a and b. We also use the usual notation for open or half-open line segments. 
So [a,b)=[a,b]{b}, etc. 


























 








For the proof of  Proposition <ref> we consider a coding 
procedure of certain points in the complex plane by words in an alphabet. We first fix some terminology related to this. 
We consider a non-empty set 𝒜. Then we call 𝒜 an alphabet and refer to the elements in 𝒜 as the letters  in this alphabet. In this paper 
we will only use alphabets of the form  
𝒜={1,2, … ,m} with m∈, m≥ 3.  
We consider the set 
W(𝒜)𝒜^N of infinite sequences in 𝒜  as the set of infinite words in the alphabet 𝒜 and write the elements w∈	 W(𝒜) in the form w=w_1w_2…, where it is understood that w_k∈𝒜 for k∈. Similarly,  we set 
W_n(𝒜)𝒜^n and consider 
W_n(𝒜) as the set of all words in the alphabet 
𝒜 of length n. We write the elements w∈ W_n(𝒜) in the form w=w_1… w_n with w_k∈𝒜 for k=1, … , n. 
We use the convention that W_0( 𝒜)={∅}
and consider the only element ∅ in W_0( 𝒜) as the empty word of length 0.  Finally, 

    W_*(𝒜)⋃_n∈_0  W_n(𝒜)
 is the set of all words of finite length. 
If u=u_1… u_n is a finite word and v=v_1v_2… is a finite or infinite word in the alphabet 𝒜, then  we denote by uv=u_1… u_nv_1v_2… the word obtained by concatenating u and v. We call u an initial segment and v a tail of the word w=uv.  If the alphabet 𝒜 is understood, then we will simply drop 𝒜 from the notation. So W will denote the set of infinite words in 𝒜, etc. 

For the rest of this section, we use the alphabet 𝒜={1,2,3}. So when we  write  W, W_n, W_* it is understood that 𝒜={1,2,3} is the underlying alphabet. 
There exists a unique metric d on W={1,2,3}^ with the following property. If we have two words u=u_1u_2… and  
v=v_1v_2… in W and u v, then for some  n∈_0 we have  u_1=v_1, …, u_n=v_n,  and u_n+1 v_n+1.  Then d(u,v)=1/2^n. More informally, two elements u,v∈ W are close in this metric precisely if  they share a large 
number of initial letters. The metric space (W, d) is compact and homeomorphic to a Cantor set. 

If n∈_0 and w=w_1w_2… w_n∈ W_n, we define 

    f_w   f_w_1∘ f_w_2∘⋯∘ f_w_n,

 where we use the maps in (<ref>) in the composition.  By convention, 
 f_∅= id_ is the identity map on .
 Note that f_w is a Euclidean similarity on  that scales Euclidean distances by the factor 2^-n. If a,b∈, then 
 f_w([a,b])=[f_w(a),f_w(b)]. We will use this repeatedly in the following.
 
 


Throughout this section we denote by H  the (closed) convex hull of the four points 
1, i, -1, and 12-i/2 (see Figure <ref>). We set H_k=f_k(H) for k=1,2,3. Then 

    H_1∪ H_2 ∪ H_3 =f_1(H)∪ f_2(H) ∪ f_3(H) H.

This implies that 

    f_w(H) H
  for all 
w∈  W_∗.   


 


  There exists a well-defined continuous map 
π  W  given  by
  
    π(w)=lim_n→∞ f_w_1w_2… w_n(z_0)

  for w=w_1w_2…∈ W and z_0∈.
Here the limit exists and is independent of the choice of z_0∈C. 
  
 
The existence of such a map π is standard in similar  contexts 
(see, for example,  <cit.>).
 In the following, π  W will always denote the map provided by this lemma.
 
  Fix z_0∈. Then 
 there exists a constant C≥ 0 such that 
 
    |z_0-f_k(z_0)| ≤ C
 for k=1,2,3.
 If  n∈_0 and u∈ W_n, then 
 
    |f_u(a)-f_u(b)|=1/2^n |a-b|
 for all a,b∈. 
 This implies that if w=w_1w_2…∈ W, n∈,  and u w_1w_2… w_n∈ W_n, then 
 
    |f_w_1w_2… w_n(z_0)-f_w_1w_2… w_n+1(z_0)|   
     =|f_u(z_0) -f_u(f_w_n+1(z_0))|
       =1/2^n | z_0-f_w_n+1(z_0)|≤C/2^n.
 
 It follows  that  {f_w_1w_2… w_n(z_0)}_n∈ is a Cauchy sequence in . Hence this sequence converges and 
 
    π(w)=lim_n→∞ f_w_1w_2… w_n(z_0)

 is well-defined for each w=w_1w_2…∈ W. 
 
 The limit does not depend on the choice of z_0. Indeed, if z'_0∈ is another point, then 
 
    |f_w_1w_2… w_n(z_0)-f_w_1w_2… w_n(z'_0)|
     =1/2^n |z_0-z'_0|,
 which implies that 
  
    lim_n→∞ f_w_1w_2… w_n(z_0)=
      lim_n→∞ f_w_1w_2… w_n(z'_0).

  
  The definition of π shows  that if w=w_1w_2…∈ W and n∈_0, then 
    
    π(w)=π(w_1w_2…)=f_w_1… w_n(π(w_n+1w_n+2…)).

    If we pick z_0∈ H, then (<ref>) and the definition of π imply  that π(W) H.  If we combine this with (<ref>), then we see that if two words u,v∈ W start with the same letters 
    w_1,…,  w_n, then 
    
    |π(u)-π(v)|≤(f_w_1… w_n(H))=1/2^n(H).
 
    The continuity of the map π follows from this and the definition of the metric d on W.  
 We can now establish  the result that is the basis of the definition of 
 the CSST. Again arguments along these lines are completely standard. 
  
Proof of Proposition <ref>.  Let  π  W be  the map provided by  Lem­ma <ref> and  define T=π(W). Since W is compact and π is 
 continuous, the set T is non-empty and compact. The relation (<ref>) immediately follows from (<ref>) for n=1. Note  that (<ref>) implies that
 
    f_w( T)=f_w1( T)∪ f_w2( T)∪ f_w3( T)

for each w∈ W_n, n∈_0.  From this in turn we deduce that 

    ⋃_w∈ W_n f_w( T)=  T

for each n∈_0. 

 
 It remains to show the uniqueness of T. Suppose T is another non-empty compact set satisfying the analog of   (<ref>). Then the analogs of 
 (<ref>) and (<ref>) are also valid for T.  
 This and  the definition of 
 π using  a point z_0∈T imply that T =π(W)T. 
  
  For the converse inclusion, let a∈T be arbitrary. Using the relation 
  (<ref>)  for the set   T, we can inductively  construct an infinite word w_1w_2…∈ W such that 
   a∈ f_w_1w_2… w_n(T)
   for all n∈. Since 
  
    ( f_w_1w_2… w_n(T))=1/2^n( T)→ 0  as n→∞,

   the definition of π (using a point z_0∈T) implies that 
   a=π(w). In particular, a∈π(W)=T, and so TT. The uniqueness of T follows.  
 In the proof of the previous proposition we have seen that 
T =π(W). If p∈ and p=π(w) for some w∈ W, then we say that the word w represents p. 

The following statement provides some  geometric descriptions of T.

 Let I=[-1,1]. 
For n∈_0 define 

    J_n= ⋃_w∈ W_n f_w(I)   and   K_n= ⋃_w∈ W_n f_w(H) .

 Then the sets J_n and K_n are compact and   satisfy  

    J_n⊆ J_n+1T K_n+1 K_n

for n∈_0.
Moreover, we have  

    ⋃_n∈_0J_n=  T=⋂_n∈_0K_n.



As we will discuss more towards the end of this section, the first identity 
in (<ref>) represents  as the closure of a union of 
an ascending  sequence of trees as mentioned in the introduction.
We will not need   the second  identity  
in (<ref>) in the following, but included it to show that 
 can also be obtained as the intersection of a natural decreasing sequence of compacts sets. This is how many other fractals are constructed.  

 It is clear that the sets J_n and K_n as defined in the statement are compact for each n∈_0. Set I_k=f_k(I) for k=1,2,3. Then an elementary geometric consideration shows that 
(see Figure <ref>)

    I I_1∪ I_2∪ I_3  H_1∪ H_2 ∪ H_3
     H.
 This in turn implies that 

    f_w(I)     f_w1(I)∪  f_w2(I)∪  f_w3(I)
        
     f_w1(H)∪  f_w2(H)∪  f_w3(H)  f_w(H)
 
for each w∈ W_n, n∈_0. Taking the union over all w∈ W_n, we obtain 

    J_n J_n+1 K_n+1 K_n

for all n∈_0. 
The set T= ⋃_n∈_0J_n is non-empty, compact, and satisfies

    ⋃_k=1,2,3 f_k(T)   = 
    ⋃_k=1,2,3 f_k( ⋃_n∈_0J_n )=  ⋃_k=1,2,3  f_k( ⋃_n∈_0J_n) 
         =⋃_k=1,2,3   f_k( ⋃_n∈_0J_n)= ⋃_n∈_0⋃_k=1,2,3   f_k(J_n)
        = ⋃_n∈_0 J_n+1 = ⋃_n∈_0 J_n  =T.
 
Hence T=T by the uniqueness statement in Proposition <ref>.  So we have the first equation in (<ref>).

Since 0∈ H, we have f_w(0)∈ f_w(H) K_n for each 
w∈ W_n. Since the sets K_n are compact and nested, this implies that for each w=w_1w_2…∈ W we have 

    π(w)=lim_n→∞ f_w_1… w_n(0)∈⋂_n∈_0
    K_n.
 
It follows that T =π(W)⋂_n∈_0 K_n. 

To show the reverse inclusion, let a∈⋂_n∈_0 K_n
be arbitrary. Then a∈ K_n for each n∈_0, and so there is a word u_n∈ W_n such that a∈ f_u_n(H).
Define z_n= f_u_n(0)∈ J_n T.
Since 0∈ H, we  have z_n∈  f_u_n(H), and so 

    |z_n-a|≤(f_u_n(H))=1/2^n(H).

Hence z_n→ a as n→∞. Since z_n∈T and T is compact, it follows that a∈T.
We see that  ⋂_n∈_0 K_nT.
So the second equation in (<ref>) is also valid.

The inclusions  (<ref>) follow from (<ref>) and
(<ref>).   

For a finite word u∈ W_* we define 

    _u f_u().

Note that _∅=. 
Since =π(W) and f_u(π(v))=π(uv) whenever u∈ W_* and v∈ W (see (<ref>)), the set _u consists precisely of the points  a∈ that can be 
  represented in the form a=π(w) with a word w∈ W that has
  u has an initial segment. This implies that if v∈ W_*   is a finite word  with the initial segment 
  u∈ W_*, then _v_u.  
  
  It follows from  (<ref>)  that 

    _u=_u1∪_u2∪_u3
 for each u∈ W_*
and from (<ref>) that    

    =⋃_u∈ W_n_u

for each n∈_0.  


  
  

Since I=[-1,1]TH (as follows from Proposition <ref>) and (I) =  (H) =2, we have  (T)=2.  If n∈_0 and u∈ W_n, then f_u is a similarity map that scales  distances by the factor 1/2^n. Hence 

    (_u)=2^1-n.


 


We have  0=f_1(1)=f_2(-1)=f_3(-1). This implies 

    0∈_k= f_k() f_k(H)=H_k

for k=1,2,3. 
If k,ℓ∈{1,2,3} and kℓ, then (see Figure <ref>)

    H_k ∩H_ℓ={0},  and so _k ∩_ℓ={0}.







  The next lemma   provides a criterion  when two infinite words in W represent the same point in T under the map π. Here we use the notation 
  k̇ for  the infinite word kkk… for k∈{1,2,3}.
 
      
  
 
  (i) We have 
  π^-1(0)={12̇,21̇, 31̇}.


  (ii)   Let v,w∈ W with v w. Then   
 π(v)=π(w) if and only if  there exists a finite word u∈ W_∗ such that v,w∈{u12̇,u21̇,u31̇}. In this case,
  π(v)=π(w)=f_u(0). 
 
 
Note that if v∈ W and v∈{u12̇,u21̇,u31̇} for some u∈ W_∗, then u is uniquely determined. This and the lemma imply that each point in =π(W) has at most three peimages under the map π. 


   (i) Note that 12̇∈π^-1(0) as follows from 
  
    f_2(1)=1  and  f_1(1)=0.

  Similarly, 21̇, 31̇∈π^-1(0), because   
  
    f_1(-1)=-1, f_2(-1)=0,  and   f_1(-1)=-1,  f_3(-1)=0.
 
  Hence {12̇, 21̇, 31̇}π^-1(0). 
  
  To prove the reverse inclusion, suppose that π(w)=0 for some w = w_1w_2…∈ W. We first consider the case w_1=1. 
   Then 0=f_1(a), where   aπ(w_2w_3…), and so a=1. Since 1∈T_2\ (T_1∪T_3) as follows from (<ref>), we must have w_2=2. Then 
   1=f_2(b), where b w_3w_4…, and so b=1 ∈T_2\ (T_1∪T_3).  This  implies   w_3=2. Repeating the argument, we see that 2=w_2=w_3=…, and so w=12̇.
  
 A  very similar argument shows that if w_1=2, then w=21̇, and  if w_1=3, then w=31̇.
 
 (ii) Suppose that π(v)=π(w) for some u,v∈ W, u v. Let u∈ W_∗ be the longest initial word that v and w have in common. So v=uv_n+1v_n+2… and  
w=uw_n+1w_n+2…, where n∈_0 and v_n+1≠ w_n+1. Since f_u is bijective and
 
    π(v)= f_u(π(v_n+1v_n+2…))=π(w)= f_u(π(w_n+1w_n+2…))  ,
 we have 

    π(v_n+1v_n+2…) = π(w_n+1w_n+2…).

Note that
π(v_n+1v_n+2…)  ∈T_v_n+1 and 
π(w_n+1w_n+2…)  ∈T_w_n+1. Since 
v_n+1 W_n+1, 
by  (<ref>) this is only possible if  π(v_n+1v_n+2…) = π(w_n+1w_n+2…)=0. Hence 

    v_n+1v_n+2…, w_n+1w_n+2…∈{12̇,21̇,31̇}
 by (i).  The  “only if" implication  follows. Our considerations also show that  π(v)=π(w)=f_u(0).
The reverse implication follows from (i). 
 



























































Our next goal is to show that  is indeed a tree. This requires some preparation. 

  
 
   
  
  (i)   For each  p∈ there exists a 
  (possibly degenerate)  arc α in 
 with endpoints -1 and p. 

  
  (ii)   The sets , {1}, and {-1}
   are arc-connected. 
       
 


 (i) Let  p∈. Then  p=π(w) for some w=w_1w_2…∈ W. 

 Let v_n=w_1…  w_n and define a_n=f_v_n(-1)∈ for n∈_0. Then 
a_0=f_∅(-1)=-1.  
   For each n∈_0 we have 

    [a_n, a_n+1)=
    [f_v_n(-1), f_v_n w_n+1(-1))=
    f_v_n (   [-1, f_w_n+1(-1)   )   ).

If w_n+1=1, then f_w_n+1(-1)=f_1(-1)=-1; so a_n=a_n+1 
and 

    [a_n, a_n+1)=∅.
  If w_n+1∈{2,3}, then 
f_w_n+1(-1)=0; so   

    [-1, f_w_n+1(-1))=[-1,0)_1{0},
 and

    [a_n, a_n+1) = f_v_n([-1, 0)) f_v_n(_1{0})_v_n.
 
Moreover,






    ([a_n, a_n+1))=1/2^n([-1, f_w_n+1(-1)))= 
      2^-n    if  w_n+1 = 2,3,
    
      0     if  w_n+1 =1.

Let 
    A_n{p}∪⋃_k≥ n+1 [a_k, a_k+1)

for n∈_0. 
By what we have seen above, 

    [a_k, a_k+1)_v_k_v_n+1
 
for k≥ n+1. Since p=lim_k→∞a_k and _v_n+1 is closed, we also have p∈_v_n+1, and so 

    A_n _v_n+1.
 
This implies that 

    [a_n, a_n+1)∩ A_n=∅

for each  n∈_0. 
Indeed, if w_n+1=1  this is clear, because then [a_n, a_n+1)=∅.

If w_n+1=2, then

    A_n_v_n+1=f_v_n(f_2())=f_v_n(_2),

which  implies that 

    [a_n, a_n+1)∩ A_n  f_v_n(_1{0})∩ f_v_n(_2)= f_v_n( (_1{0})∩_2)=∅.
 
If w_n+1=3, then [a_n, a_n+1)∩ A_n=∅  by the same reasoning.
This shows that the sets 

    [a_0,a_1), [a_1, a_2), [a_2, a_3),…, {p}
 are 
pairwise disjoint. As n→∞,  we have   a_n→ p and also (A_n)→ 0 by (<ref>). 
 Therefore, the union 
  
    α =   [a_0,a_1)∪  [a_1, a_2)∪ [a_2, a_3)∪…∪{p}
 
  is an arc in  joining a_0=-1 and p (if p=-1, this arc is degenerate). We have proved (i). 
  
  
 To prepare the proof of (ii),  we claim that if p 1, then this arc α does not contain
  1.  
Otherwise, we must have 1∈ [a_n, a_n+1)_v_n for some n∈_0.
This shows that 1 can be written in the form 1=π(u),
where u∈ W is an infinite word starting with the finite word v v_n (note that this  and the statements below are trivially true for n=0).
On the other hand, we have f_2(1)=1 which implies that 
1=π(2̇). 
By Lemma <ref> (ii) this is only possible if  all the letters in v are 
2's. Then f_v(1)=1 and it follows that 

    1=f_v(1)∈ [a_n,a_n+1)= f_v([-1, f_w_n+1(-1))).
 Since f_v is a bijection, this implies  that 1∈ [-1, f_w_n+1(-1)). Now 
f_w_n+1(-1)∈{-1, 0}, and we obtain a contradiction. So indeed, 1∉α.

(ii) Let p,q∈ with p q be arbitrary. In order to show 
that  is arc-connected, we have to find   an arc   in
 joining p and q. Now by the construction in (i) we can find arcs α and β in  joining p and q to -1, respectively. 
Then the  desired arc  can be found in the union α∪β  as follows. Starting from p, we travel long α until we first hit  β, say in a point x. Such a  point x exists, because -1∈α∩β∅. Let α' be the (possibly degenerate) subarc of α with endpoints p and x, and β' be the subarc of β with endpoints x and q. Then =α'∪β' is an arc   in  joining p and q. 

The arc-connectedness of {1} is proved by the same argument. Indeed, if p,q∈{1}, then  by the remark in the last part of the proof of (i), the arcs  α and β constructed as in (i)  do not contain 1. Then the arc α∪β does not contain 1 either. 

Finally, to show that  {-1} is arc-connected, we assume that  p,q∈{-1}.
 If x is, as  above, the first point on β as we travel  along α starting from p, then it suffices to show that x -1, because then -1∉. This in turn will follow if we can show that α and β have another point in common besides
  -1.  

To find such a point, we revisit the above construction. 
Pick  w=w_1w_2…∈ W and  u=u_1u_2…∈ W such that p=π(w) and q=π(u). Let α and β be the arcs for p and q, respectively, as constructed in (i). Then  α is as in (<ref>) and we can write the other arc β 
 as 

    β =   [b_0,b_1)∪  [b_1, b_2)∪ [b_2, b_3)∪…∪{q},

where b_n=f_u_1… u_n(-1) for n∈_0. Since p q, we have w u, and so there exists a largest  n∈_0 such that 
v w_1… w_n=u_1… u_n and w_n+1 u_n+1. Then a_n=b_n=f_v(-1)∈α∩β. If a_n= b_n -1, we are done. So we may assume that 
a_n=b_n=f_v(-1)=-1. Then 
a_0=… =a_n=-1, and so w_k=u_k=1 for k=1, …, n.  This shows that  all letters in  v are equal to 1. 


Since the letters w_n+1 and u_n+1 are distinct,
one of them is different from 1. We may assume u_n+1 1.
Then f_u_n+1(-1)=0,
and so 
(b_n, b_n+1]=f_v((-1, 0]) β∖{-1}. 
Here we used that f_v is a homeomorphism with f_v(-1)=-1. 

 Since p=π(w)  -1=π(1̇), we have  w1̇ and so there exists a smallest ℓ∈ such that w_n+ℓ 1.
Then  f_w_n+ℓ(-1)=0 and so a simple computation using 
w_n+1=…= w_n+ℓ-1=1 shows  that

    c f_w_n+1… w_n+ℓ(-1)= 
    f_w_n+1… w_n+ℓ-1(0)= 2^1-ℓ-1∈ (-1, 0].
 
Hence 

    a_n+ℓ=f_v(c)∈ f_v((-1, 0])β∖{-1}.
 
It follows that a_n+ℓ∈α∩β and a_n+ℓ -1 as desired.   






   




























   






























The next lemma will help us to identify the branch points of  once we know that  is a tree.  

  
   
  
  (i) 
The  components of {0} are given by 
the non-empty sets _1{0}, _2{0}, _3{0}. 
 
  (ii)  If u∈ W_*, then {f_u(0)} has exactly three  components. The 
 sets T_u1{f_u(0)},
 T_u2{f_u(0)},
 T_u3{f_u(0)} are each contained  in a different component of T{f_u(0)}. 
 
  
In the proof we will use the following general facts about 
 components of a subset M of   a metric space X. 
Recall that a set A M is relatively closed in M if A=A∩ M, or equivalently, if each limit point of A that belongs to M also belongs to A. Each component A of M is relatively closed in M, because its relative closure A∩ M is a connected subset of M with AA∩ M. Hence A=A∩ M, because A is a  component of M and hence a maximal connected subset of M. 
 
  If A_1, …, A_n M  for some n∈ are non-empty, pairwise disjoint, relatively closed, and connected sets with M=A_1∪…∪ A_n, then these sets are the components of M.  

  


  
(i) Each of the sets T\{1} and 
 T\{-1} is  non-empty,  and connected by 
Lemma <ref> (ii).   Therefore, the sets 

    T_1\{0}=f_1(T\{1}), T_2\{0}=f_2(T\{-1}), T_3\{0}=f_3(T\{-1})
 are non-empty and   connected.
They are also relatively closed in T\{0} and  pairwise disjoint by (<ref>). Since =_1∪_2∪_3 we have 

    {0} = (_1{0})∪ (_2{0}) ∪ (_3{0}).
 This implies that the  sets _k{0}, k=1,2,3,  are the  components of 
T\{0}.  The statement follows. 

(ii) We prove this by induction on the length n∈_0 of the word 
u∈ W_*. If n=0 and so u=∅,  this follows from  statement (i).

Suppose the statement is true for all words of length n-1, where n∈. Let u=u_1… u_n∈ W_n be an arbitrary word of length n. We set ℓ u_1 and u' u_2… u_n. Then u =ℓ u'. To be specific and ease notation, we will assume that ℓ=1. The other cases ℓ=2 or ℓ=3 are completely analogous and we will skip the details.

Note that f_u(0) 0. Indeed, if 

    0=f_u(0)=f_u(π(12̇))=
    π(u12̇),
 then u12̇∈{12̇, 21̇, 31̇} by Lemma <ref> (i). This is only possible u1=1. This is a contradiction, because u has length n≥ 1. Hence f_u(0) 0. Since u_1=ℓ=1, we  have f_u(0)∈_1{0}. 

By induction hypothesis, {f_u'(0)} has exactly three connected components V_1, V_2, V_3, and
we may assume that 
_u'k{f_u'(0)} V_k 
for k=1,2,3. 
It follows that 

    f_ℓ({f_u'(0)})=f_1({f_u'(0)})= _1{f_u(0)}
 
has exactly three connected components U_k=f_1(V_k)_1 with 

    _uk{f_u(0)} =_1u'k{f_1u'(0)} =
     f_1(_u'k{f_u'(0)})  
    f_1( V_k)=U_k

for k=1,2,3. 


Let  k∈{1,2,3}. Then we have  V_k=V_k∩{f_u'(0)}, because  V_k is a component of  
{f_u'(0)} and hence relatively closed in 
{f_u'(0)}.   This implies that 

    U_k   =f_1(V_k)=f_1( V_k∩{f_u'(0)})=
    f_1( V_k)∩_1{f_u(0)}
       =f_1(V_k)∩_1{f_u(0)} = U_k∩_1{f_u(0)}.
   
Since _1 is compact, U_k_1, and so U_k_1,  this shows that every limit point of U_k distinct from f_u(0) belongs to U_k. Hence U_k is relatively closed in {f_u(0)}. 

Exactly one of the components of _1{f_u(0)}, say U_1, contains the point 
0∈_1{f_u(0)}. Then U'_1 U_1∪_2∪_3 is a relatively closed subset of {f_u(0)}. This set is also connected, because the sets U_1, _2=f_2(), _3=f_3()  are connected and have the point 0 in common.  Hence  the connected sets U'_1, U_2, U_3  are pairwise disjoint, relatively closed in 
{f_u(0)}, and 

    {f_u(0)}=  (_1  {f_u(0)})∪_2∪_3=U'_1∪ U_2∪ U_3.
 This implies that 
 {f_u(0)} has exactly the three connected 
 components U'_1, U_2, U_3. 
Moreover,   _u1{f_u(0)}, _u2{f_u(0)}, _u3{f_u(0)} lie in the different components 
U_1', U_2, U_3 of {f_u(0)}, respectively. 
This provides the inductive step, and the statement follows.  
 
 We can now show that  is a metric tree. 
 




  



  
   Proof of Proposition <ref>. We know that  is  compact, contains at least two points, and is 
 arc-connected  by Lemma <ref>.   
 
 Let p∈ and n∈ be arbitrary, and define 
 
    N=⋃{_u: u∈ W_n  and  p∈_u}.
 
Since each of the sets 
   _u=f_u(), u∈ W_*, is a compact and connected
   subset of ,  
 the set  N is  connected. Moreover, since each of the finitely many sets  _u, u∈ W_n, is closed, we can find 
 δ>0 such that 
 
    (p, _u)≥δ
 
 whenever u∈ W_n and  p∉_u. Then we have B(p, δ)∩ N by (<ref>), and so N is a connected relative neighborhood of p in . It follows from  (<ref>) 
 that  (N)≤ 2^2-n. This shows that each point in  has  small connected  neighborhoods in . Hence  is locally connected.
 
 

To complete the proof, it remains to show that the arc joining two given distinct points in   is unique. 
For this we argue by contradiction and assume that there are two distinct arcs in T with the same  endpoints. By considering suitable subarcs of these arcs, we can reduce
 to the following situation: there are arcs α,βT that have the distinct   endpoints a,b ∈T in common, but no other points. 
 
 To see that this leads to a contradiction, we represent the points 
 a and b by words in W; so a=π(v) and
 b=π(w), where v=v_1v_2… and w=w_1w_2… are in W. Since a b and every point in T has at most three such representations by Lemma <ref> (ii), we can find a pair v and w representing a and b with the largest common initial word, say v_1=w_1,…, v_n=w_n, and v_n+1 w_n+1 for some maximal n∈_0.  
 
 Let u=v_1… v_n=w_1… w_n and 
 
    t=f_u(0)=π(u12̇)=π(u21̇)=π(u31̇).
 
 Then t a,b. To see this, assume that t=a, say. We have  
 w_n+1∈{1,2,3}, and so,  say w_n+1=1.
 But then 
 a=t=π(u12̇) and b=π(u1w_n+2…). So a and b 
 are represented by words with the common initial segment u1 that is longer than u. This contradicts the choice of v and w. 
 The cases w_n+1 =2 or w_n+1=3 lead to a contradiction in a similar way. 
 
 
 So indeed t=f_u(0) a,b. Moreover a=π (uv_n+1…)∈T_uv_n+1{t} and similarly 
 b∈T_uw_n+1{t}. Since v_n+1 w_n+1 the points a and b lie in different components of 
 T{t} by Lemma <ref> (ii). So any arc joining a and b must pass through t. Hence t∈α∩β, but t a,b. This contradicts our assumption that the arcs α and β have no other points
 than their endpoints a and b in common.   


If M, then we denote by ∂ M the relative boundary of M in . 

 
Let n∈ and u∈ W_n. Then 

    ∂_u{f_u(-1), f_u(1)}.
 
Moreover, if  p∈∂_u, 
then p=f_w(0) for some word w∈ W_* of length ≤ n-1.


In particular, the set ∂_u contains at most two points. 


 We prove this by induction on n.  First consider n=1. So let u=k∈ W_1={1,2,3}.   
 Then _k{0} is a  component {0}  by Lemma <ref> (i).
 Hence Proposition <ref> and Lemma <ref> (i) imply that 
 _k{0} is a relatively  open set in . So each of its points lies in the relative interior of  _k and cannot lie in ∂_k.  Therefore,  ∂_k{0}. Since 
    0= f_∅(0)=f_1(1)=f_2(-1)=f_3(-1),

 the statement is true for n=1. 

Suppose the statement is true for all words in W_n, where 
n∈. Let  u∈ W_n+1 be arbitrary. Then u=vk, where v∈ W_n and k∈{1,2,3}.  By what we have just seen, the set  _k{0} is open in . Hence 

    f_v( _k{0})=f_u(){f_v(0)}=_u{f_v(0)}
 is a relatively open subset  of f_v()=_v. So if p∈_u is 
not an interior point of _u in , then p=f_v(0) or p is not an interior point of _v in  and hence belongs to the boundary of _v.
This and the induction hypothesis imply that 

    ∂_u{f_v(0)}∪∂_v{f_v(0), f_v(-1), f_v(1)}.
 
From this we conclude that  each point p∈∂_u{f_v(0)}∪∂_v  
can be 
written in the form f_w(0) for an appropriate word w of length ≤ n. This is clear if  p=f_v(0) and follows for p ∈∂_v
 from the induction hypothesis. 

Now _u=f_u() is compact and so closed in . Hence 
∂_u_u. On the other hand, _u contains only two of the points  f_v(0), f_v(-1), f_v(1). Indeed, if 
k=1, then  1∉_1 H_1, and so 
f_v(1)∉f_v(_1)=_u. It follows that ∂_u{ f_v(-1), f_v(0)}.
Note that f_1(-1)=-1 and f_1(1)=0, and so 

    f_v(-1)=f_v(f_1(-1))=f_u(-1)  and 
     f_v(0)=f_v(f_1(1))=f_u(1).
 
Hence 
    ∂_u{ f_u(-1), f_u(1)}.


Very similar considerations show that if k=2, then 

    ∂_u{f_v(0), f_v(1)}={f_u(-1),f_u(1)},
 and if k=3, then 

    ∂_u{f_v(0)}={f_u(-1)}.
 The statement follows. 
  




































































The next lemma shows that all branch points of T are of the form f_u(0) with  u∈ W_∗.

  The branch points of  are exactly the points of the form  t=f_u(0) for   some finite word u∈ W_∗. They are 
triple points of . 


 By Lemma <ref> (ii) we know that each point 
t=f_u(0) with u∈ W_∗ is a triple point of the tree .
We have to show that there are no other branch points of . 
 
 So suppose that t is a branch point of T, but t f_u(0) for each  u∈ W_∗. Then we can find (at least) three distinct components U_1, U_2, U_3 of T{t}.  Pick a point x_k∈ U_k  and  choose  n∈ such that 
|x_k-t|> 2^1-n 
for k=1,2,3. By (<ref>) we can find u∈ W_n such that t∈T_u. 
Then t is distinct from the points in the relative  boundary ∂_u, because they have the form f_w(0) for some w∈ W_∗
 (see Lemma <ref>). Hence t is contained in the relative interior of T_u in T. 
Moreover,  (T_u)=2^1-n, and so x_k∉T_u. For k=1,2,3 let α_k be the arc in  joining x_k and t. As we travel from x_k to t along α_k, there exists a first point y_k ∈T_u. Then y_k∈∂_u and so y_k t. Let   β_k be the subarc of α_k  with endpoints  x_k and y_k. Then β_k is a connected set in  {t}. Since x_k∈β_k, it follows that β_k U_k, and so y_k∈ U_k. 

This shows that  the points y_1, y_2, y_3 are distinct and contained in the relative boundary ∂_u. This is impossible,  because by  Lemma <ref> the set ∂_u consists of at most two points.  




We can now prove Proposition <ref> which shows that 
   satisfies the conditions in Theorem <ref> and  belongs to the class of trees _3. 

Proof of Proposition <ref>.
 By Lemma <ref> each branch point of  is a triple point and each set _u for  u∈ W_n and n∈ contains the triple point t=f_u(0). The sets _u, u∈ W_n, 
cover  and have small diameter for n large. It follows that the triple points are dense in .   


In order to show that   is a quasi-convex subset of 
, we first require a lemma. 


There exists a constant K>0 such that if p∈ and  α is the arc in  joining 0 and p, then  

    (α) ≤ K|p|.



In particular, the arc α is a rectifiable curve. 


 Let p∈ be arbitrary. We may assume that 
p 0. Then p=π(w) for some w=w_1w_2…∈ W. 
For simplicity we assume w_1=3. The other cases, w_1=1 and w_1=2, are very similar and we will only present the details for 
w_1=3.

 Since p 0=π(31̇), we have 
w_2w_3…1̇. Hence there exists a smallest number 
  n∈ such that 
such that w_n+1 1. Let v=w_1… w_n be the initial word of w and w'=w_n+1w_n+2… be the tail of w. The word v has  the form v=31… 1, where the sequence  of  1's could possibly be empty.
Note that qπ(w')∈_w_n+1_2∪_3 H_2∪
H_3. 
Since  

    c_0(-1, H_2∪ H_3)>0
(see Figure <ref>), for the distance of q and -1 we  have 
|q+1|≥ c_0. We also have  f_v(q)=p, and f_v(-1)=0, because 
f_1(-1)=-1 and f_3(-1)=0. It follows that 

    |p|=|f_v(q)-f_v(-1)|=1/2^n  |q+1|≥c_0/2^n.


Now  define a_0=0=f_v(-1) and  a_k= 
f_vw_n+1… w_n+k-1(0) for k∈ (here w_n+1… w_n+k-1=∅ for k=1). Note that then 

    a_1=f_v(0)=f_w_1… w_n(0)=f_31… 1(0)=
    f_3(2^1-n-1)=i/2^n,
 
and so 

    [a_0, a_1]= [f_v(-1), f_v(0)]= [0, i/2^n] [0,i]
    .
 
This also shows that ([a_0, a_1])= 1/2^n. 


For  k∈ we have f_w_n+k(0)∈{-1/2, 1/2, i/2}, and 
[0, f_w_n+k(0)].
This implies that 

    [a_k, a_k+1]= f_vw_n+1… w_n+k-1([0, f_w_n+k(0)])
 and
([a_k, a_k+1])= 1/2^n+k for  k∈. 
Since lim_k→∞a_k=π(w)=p, we can   concatenate the intervals [a_k, a_k+1] for k∈_0, add the endpoint 
p, and obtain  a path  in  that joins 0 and p  with  

    ()= ∑_k=0^∞1/2^n+k=1/2^n-1.
 
The (image of the) path  will contain the unique arc α 
in  joining 0 and p and so
(α)≤ 1/2^n-1. If we combine this with (<ref>),  then inequality (<ref>) follows with K=2/c_0.   








We can now  show  that  is indeed a quasi-convex subset of .



Proof of Proposition <ref>.
Let a,b∈ be arbitrary. We may assume that 
a b. Then there are words u=u_1u_2…∈ W and 
v=v_1v_2…∈ W such that a=π(u) and b=π(v). Since 
a b, we have u v and so there exists a smallest number n∈_0 such that u_1=v_1, …, u_n=v_n and u_n+1 v_n+1. Let w=u_1… u_n=v_1… v_n,  
u'=u_n+1u_n+2…∈ W and v'=v_n+1v_n+2…∈ W. We define a'=π(u') and b'=π(v'). 
Set k= u_n+1 and ℓ=v_n+1. Then kℓ, a'∈_k H_k, and b'∈_ℓ H_ℓ. We now use the following
elementary geometric estimate: there exists a constant c_1>0 such that 

    |x-y| ≥ c_1(|x|+|y|),
 
whenever x∈ H_k, y∈ H_ℓ, k,ℓ∈{1,2,3}, kℓ. 
Essentially, this follows from the fact that the sets H_1, H_2, H_3 are contained in closed sectors in  that are pairwise disjoint except for the common point 0. 

In our situation, this means that 

    |a'-b'|≥ c_1 (|a'|+|b'|).
 
Let σ and τ be the arcs in  joining 0 to a' and b', respectively. 
Then  σ∪τ contains the arc α'  in  joining a' and b'. Then it follows from Lemma <ref> that 

    (α')≤ (σ)+ (τ)≤ K(|a'|+|b'|)
    ≤ L |a'-b'|

with L   K/c_1.  

For the  similarity f_w we have  f_w(a')=a and f_w(b')=b. 
Since f_w(), it follows that α f_w(α') is the unique arc in  joining a and b.
Since f_w scales distances by a fixed factor (namely 1/2^n), 
(<ref>) implies the desired inequality 
(α)≤  L |a-b|.    
 
As we already discussed in the introduction, by Proposition <ref> we can define a new metric ϱ on  
by setting 

    ϱ(a,b)=(α)
 
for a,b∈,  
where α is the unique arc in  joining  a and b. 
Then the metric space (, ϱ) is  geodesic, and we have 

    |a-b|≤ϱ(a,b)≤ L|a-b|

for a,b∈, where L is the constant in Proposition <ref>. This implies that   the metric spaces  (as equipped with the Euclidean metric) and (, ϱ) are bi-Lipschitz equivalent by the identity map. 

We  now want to reconcile Definition <ref> with the construction of the CSST as an abstract metric space  outlined in the introduction.  We require an auxiliary statement.


Let n∈_0. Then the sets 

    f_w({-1}),  w∈ W_n,

are pairwise disjoint and their union is equal to {-1}. 


 This is proved by induction on n∈_0. For n=0 the statement is clear, because then 
f_∅({-1})={-1} is the only set in (<ref>). 

Suppose the statement is true for some n∈. Then for each 
u∈ W_n the sets 

    f_u1({-1})   = f_u(_1{-1}),
    
    f_u2({-1})   = f_u(_2{0}),
    
    f_u3({-1})   = f_u(_3{0})

 provide a decomposition of f_u({-1}) into three pairwise disjoint subsets 
as follows from (<ref>) for n=1, (<ref>),  and (<ref>).
This and the induction hypothesis imply that the sets
f_uk({-1}), u∈ W_n, k∈{1,2,3}, and hence the sets   f_w({-1}), w∈ W_n+1, are
pairwise disjoint, and their union is equal to {-1}.  This is the inductive  step, and the statement follows. 

We now consider the sets J_n, n∈_0, 
as in Proposition <ref>. Here J_0=I=[-1, 1] is a line segment of length 2.  Since (-1,1]{-1}, the previous lemma implies that for each n∈_0, 
the sets f_w((-1,1]), w∈ W_n, are pairwise disjoint half-open line segments of length 2^1-n. The union of the closures 
f_w([-1,1])=f_w(I), w∈ W_n, of these line segments is the set  J_n. In particular, J_n consists of 3^n line segments of length 2^1-n with  pairwise disjoint interiors. 

Note that for w∈ W_n we have  

    f_w1((-1,1])∪  f_w2((-1,1])∪ f_w3((-1,1])    =f_w((-1,0])∪ f_w((0,1])
    ∪ f_w((0,i])
       =  f_w((-1,1])∪  f_w([0,i]).
 
An induction argument based on this   shows that for n∈_0 we have a decomposition 

    J_n{-1} =⋃_w∈ W_n f_w((-1,1])

of J_n{-1} into  the pairwise disjoint sets   f_w((-1,1]), w∈ W_n.

 In the passage from  J_n to J_n+1 we can think of each line segment  f_w(I)=f_w([-1,1])  as being replaced with  

    f_w1(I)∪  f_w2(I) ∪ f_w3(I) =f_w([-1,0])∪ f_w([0,1])
    ∪ f_w([0,i]).

So  f_w([-1,1]) is split into two intervals f_w([-1,0]) and 
f_w([0,1]), and  at its midpoint f_w(0) a  new interval 
f_w([0,i]) is “glued"  to f_w(0). This is exactly the procedure described in the introduction. Note  that Lemma <ref> implies that these new intervals 
f_w([0,i]) f_w({-1}), w∈ W_n, are pairwise disjoint. Moreover, each such interval  f_w([0,i]) meets the set J_n only in the point f_w(0) and in no other point of J_n.   Indeed, by 
(<ref>) and Lemma <ref> we have 

    f_w((0,i])∩ J_n    = f_w3((-1,1])∩ J_n =   
    f_w3((-1,1])∩ J_n{-1}
       =  f_w((0,i])∩⋃_u∈ W_n f_u((-1, 1])
    (f_w((0,i])   ∩  f_w((-1, 1]))∪⋃_u∈ W_n,  u w   f_w({-1})∩ 
     f_u({-1})=∅.
 








 
 
 It is clear that J_n is compact, and one can show by induction based on the replacement procedure just described  that J_n is connected. Hence each J_n is a subtree of  by Lemma <ref>. The  metric ϱ in (<ref>) restricted to  J_n, n∈_0, and to  J⋃_n∈ N_0 J_n  is just  the natural Euclidean path metric on  these sets. In particular, 
ϱ  is a geodesic metric on J. These considerations imply that (J_n, ϱ) for n∈, and hence  (J, ϱ), are isometric to the abstract versions of these spaces defined in the introduction. 

By Proposition <ref> the tree  is the equal 
to  closure J in . Since on J the Euclidean metric and the metric ϱ are comparable, 
the set  =J is homeomorphic to the space obtained from the completion of the geodesic metric metric space (J, ϱ). This is how we described the CSST as an abstract metric space in the introduction. 
 

























 

§ DECOMPOSING  TREES IN _M
 
   
 In the previous   section we have seen that for each n∈ the CSST admits a de­com­position   

    =⋃_u∈ W_n_u
 
into subtrees. We will now consider an  tree in _m, m∈, m≥ 3,  
and find  similar decompositions into subtrees. Our goal is to have decompositions for each level n∈ so that the conditions  
(i)–(iii) in  Proposition <ref> are satisfied. 

Note that each tree  class T_m  is non-empty. 
Namely, for each m∈, m≥ 3, a tree in _m can be obtained by essentially the same method as for the construction of the CSST as an abstract metric space outlined in the introduction. The only difference is that instead of gluing one line segment  of length 2^-n
to the midpoint c_s of a line segment s of length 2^1-n obtained in the nth step, we glue  endpoints of  
m-2 such segments  to c_s.  Since from a purely logical point of view we will not need the fact that
T_m is non-empty for the proof of Theorem <ref>,  
 we will skip further  details. 


We now fix m∈, m≥ 3,  for the rest of this section. We consider the alphabet 𝒜={1,2, …, m}. In the following, words will  contain only letters in this fixed alphabet and we use the simplified notation for the sets of words
W, W_n, W_*  as discussed in Section <ref>.  








 















































































 












 

 


































































Let T be an arbitrary  tree in the class  _m.  We will now  define subtrees T_u of T for all levels n∈ and all u∈ W_n. The boundary ∂ T_u of T_u in T will consist of one or two points that are leaves of T_u and branch points of T. We  consider each point  in  ∂ T_u as a  marked leaf in T_u and will assign to it an appropriate 
sign  - or + so that if there are two marked leaves in T_u, then they carry different  signs.  Accordingly,  we refer to the  points in ∂ T_u as the signed marked leaves of T_u.  The same point may carry different signs in different subtrees.  We write p^- if a marked leaf p of T_u  carries the sign - and p^+ if it 
carries the sign +. To refer to this sign, we also write (p, T_u)=- in the first and (p, T_u)=+ in the second case. 
If  T_u has exactly one marked leaf, we call T_u a  leaf-tile and if there are two marked leaves an arc-tile. 


The reason why we want to use these markings is that it will help us to consistently label the  subtrees so that if another tree S in _m is decomposed by the same  procedure, then we obtain 
decompositions of our trees T and S into  subtrees on all levels n that satisfy the analogs of (<ref>)  and (<ref>) (here u∈ W_n will play the role of the index i on each level n). While
 (<ref>) is fairly straightforward to obtain,   (<ref>) 
 requires a more careful approach and this is where the markings will help us (see Lemma <ref> (ii) and its proof).
   

 For the construction we will use an inductive procedure on n. 
 As in Section <ref> (see  (<ref>) and the discussion before Lemma <ref>), 
 for each branch point p∈ T, we let H_T(p) be its height, i.e.,  the diameter of the third largest  branch of p in T. If δ>0, then by Lemma <ref> there are only finitely many branch points p of 
 T with  height  H_T(p)>δ, and in particular there is one for which this quantity is maximal. 
 
For the first step n=1, we  choose a branch   point c of T  with maximal height H_T(c).  Since T is in the class _m, this branch  point c has m=ν_T(c)  branches in T. So we can enumerate the distinct branches by the letters in our alphabet 
 as    T_k, k∈𝒜.  
 
We choose c as the signed marked leaf in each  T_k,   
 where we set (c, T_1)=+ and (c, T_k)=- for k 1. So the set of signed marked leaves is {c^+} in T_1 and {c^-} in T_k, k 1. 
 Note that ∂ T_k={c} as follows from Lemma <ref> (ii) and that c is indeed a leaf in T_k by  Lemma <ref>  for each k∈𝒜. 

 Suppose that for some n∈ and all u∈ W_n we have constructed 
   subtrees T_u of T such that ∂ T_u consists of one or two signed marked leaves of T_u  that are  branch points of T. We will now construct the subtrees of the (n+1)-th 
   level as follows
 by subdivision of the trees T_u. 
 
 
 Fix  u∈ W_n. To decompose T_u into subtrees, we will 
 use a suitable branch point c of T in T_u∂ T_u. The choice of  c depends on whether ∂ T_u contains one or two elements, that is, whether T_u is a leaf-tile or an arc-tile. We will explain this precisely below, but first record some facts that are true in both cases. 
 
 Since c∈ T_u∂ T_u is an interior point of T_u, 
there is a bijective correspondence between the branches of c in T and in T_u (see Lemma <ref>). So ν_T_u(c)=ν_T(c)=m, and we can label the distinct branches 
 of c in T_u  by T_uk, k∈𝒜. We will 
  choose these labels depending on the signed marked leaves of T_u. Among other things,  if T_u has a marked leaf p^-, then p is passed to 
 T_u1 with the same sign. Similarly, a marked leaf p^+ of T_u
 is passed to T_u2 with the same sign. We will momentarily explain this in more detail (see the Summary below).  
 
  In any case, we   have 

    T_u=⋃_k∈𝒜 T_uk.

Each set T_uk is a subtree of T_u and hence also of T. We call these subtrees the children of T_u and T_u the parent of its children.  Note that two distinct children of T_u have only the point c in common and no other points. 

Before we say more about the precise labelings of the children of T_u and their signed leaves, we first want to identify the boundary of each child;  namely, we want to show that 

    ∂ T_uk=  {c}∪   (∂ T_u∩ T_uk)

for each k∈𝒜. 


To see this, first note that  T_uk is a subtree of T.  Hence 
T_uk  contains all of its boundary points and so ∂ T_uk T_uk.  We have c∈∂ T_uk, because c∈ T_uk and  every neighborhood of c contains points in the complement of T_uk as follows from Lemma <ref> (ii) (here it is important that there are at least two branches of c). If p∈ T_uk T_u and 
p∉{c}∪∂ T_u, then a sufficiently small neighborhood  N of p belongs to T_u. Since T_uk{c} is relatively open in T_u (this follows from Lemma <ref> (i)), we can shrink this neighborhood so that p∈ N T_uk. So no point p  in T_uk can be a boundary point of ∂ T_uk unless it belongs  to {c}∪∂ T_u. It follows that  ∂ T_uk{c}∪ 
(∂ T_u∩ T_uk). 


On the other hand,  we know that c∈∂ T_uk. If p∈∂ T_u ∩ T_uk, then p is  a boundary point of T_uk, because every neighborhood of  p contains elements in the complement of T_u and hence in the complement of T_uk T_u. This gives the other inclusion in (<ref>), and 
(<ref>) follows. 



The identity (<ref>)  implies that each point in  ∂ T_uk is a branch point of T, because c is and  the points in ∂ T_u are also  branch points of T by construction on the previous level n. Moreover, each point p∈∂ T_uk T_uk  is a leaf of T_uk, because if p=c, then p  is a leaf in T_uk by Lemma <ref>. Otherwise, p∈∂ T_u. Then p is a leaf of T_u by construction and hence a leaf of T_uk by the discussion after  Lemma <ref>. 


For the  choice of the branch point c∈ T_u∂ T_u, the precise labeling of the children T_uk, and the choice of the signs of the leaves of T_uk in ∂ T_uk, we now consider two cases for the set ∂ T_u. See Figure <ref> for an illustration. 
 
 Case 1: ∂ T_u contains precisely one element, say ∂ T_u={a}.  Note that 
 T_u is a subtree of T and so an infinite set. So T_u∂ T_u∅. All points in T_u∂ T_u  
 are interior points of  T_u. Since branch points 
 in T are dense (here we use that T belongs to _m), there exist branch points of T in 
 T_u∂ T_u.  We choose a  branch point c∈ T_u∂ T_u with maximal height H_T(c) among all such  branch points.  This is possible by Lemma <ref>.

Since a∈∂ T_u T_u{c}, precisely one of the children of T_u contains a. 
We now consider two subcases  depending on the sign of the marked leaf a.     

If (a,T_u)=-,  then we  choose a labeling of the children  so that a∈ T_u1. 
It then follows from (<ref>) that  ∂ T_u1={a,c} and ∂ T_uk={c}
for k 1. We choose signs so that the set of signed marked leaves is {a^-, c^+} in T_u1 and {c^-} in T_uk, k 1.   
   
 
If (a,T_u)=+,   then we choose a labeling such that 
 a∈ T_u2. Then again by (<ref>) we have ∂ T_u2={a,c} and 
 ∂ T_uk={c} for k 2.  
  We choose signs so that the set of signed marked leaves is 
{c^+} in T_u1, {c^-, a^+} in T_u2, and 
 {c^-} in T_uk, k 1,2.  



Case 2. ∂ T_u contains precisely two  elements, say ∂ T_u ={a^-, b^+}.  Then  we choose a branch point  c∈ (a, b) of T 
 such that it has the maximal  height H_T(c) among all branch  points  that lie on  (a, b). The existence of c is guaranteed by Lemma <ref> and Lemma <ref>.
 Note that (a,b) T_u, because T_u is a subtree of T.
  
The points  a and b lie in different branches of c in T_u as  follows from Lemma <ref> (iii). We choose the labels for the children of T_u  so that  a∈ T_u1 and 
 b∈ T_u2. Then by (<ref>) we have 
 ∂ T_u1={a,c}, ∂ T_u2={c,b}, and 
  ∂ T_uk={c}, k 1,2. We choose  signs  so that   
  the set of marked leaves is 
 {a^-, c^+} in T_u1, {c^-, b^+} in T_u2, and {c^-}, in  T_uk for k 1,2. 
 
 
 
 The most important points of our contruction can be summarized as follows.
 
 Summary: T_uk is a  subtree of T such that ∂ T_uk consists of  one or two points. These  points are branch points of T and leaves of T_uk. Moreover, the signs of the points in each set ∂ T_uk are chosen so that these signs differ if ∂ T_uk
 contains two points. If c is the branch point used to decompose 
 T_u, then c is a marked leaf in all the children of T_u, namely the marked leaf c^+ in T_u1 and c^- in T_uk for k 1. 
 
If T_u has a marked leaf p^-, then p is passed to the child 
 T_u1 with the same sign. Similarly, a marked leaf p^+ of T_u
 is passed to T_u2 with the same sign. So marked leaves are  passed to a unique child and they retain their signs.
 Since Cases 1 and 2 exhaust all possibilities, this  completes the inductive step in the construction of the trees on level n+1 and their marked leaves.  So we obtain subtrees T_u 
 of T for all u∈ W_*. Here it is convenient to set T_∅=T with an empty set of marked leaves.  
 


 
If one  applies our procedure  to choose 
 signs for the points in ∂_u for the subtrees _u 
 of the CSST defined in Section <ref>, then one can recover these signs directly  by a simple rule without going through the recursive process. Namely, by Lemma <ref> we have  
 ∂_u{f_u(-1), f(1)}. Then it is not hard to see that 
 for  
 p∈∂_u, we have  (_u, p)=+ if p=f_u(1) and 
 (_u, p)=- if p=f_u(-1).
 
 We now summarize some facts about the subtrees T_u of T that we just defined.   
 
  
  The following statements are true: 


 

  (i) T=⋃_u∈ W_n T_u 
for each n∈.   


  (ii)   If   n∈, u,v∈ W_n, u v, 
and  T_u∩ T_v∅, then T_u∩ T_v consists of precisely one point p∈ T, which is a marked leaf  in both T_u and T_v.  


  (iii)    For  n∈, u∈ W_n, and v∈ W_n+1, we have T_v T_u if and only if u=vk for some 
k∈𝒜. 


  (iv)     For each u∈ W_* let c_u be the branch point chosen in the decomposition of T_u into children. Then c_u c_v for all u,v∈ W_* with  u v.  

 

 (i) This immediately follows from (<ref>) and induction  on n. 

(ii) We prove this by induction on n. By choice of the subtrees 
T_k for  k∈𝒜=W_1  and their marked leaves this is clear for n=1.

  
Suppose the statement is  true for all distinct words  of 
length n-1, where n≥ 2.  Now consider two words u,v∈ W_n of length n  with u v and T_u∩ T_v∅.   Then u=u'k and v=v'ℓ,  where  u',v'∈ W_n-1 and k,ℓ∈𝒜. 

If  u'=v', then T_u and T_v are two of the branches 
 obtained from T_u' and a suitable branch point  c∈ T_u'. In this case, {c}= T_u∩ T_v and c is a marked leaf in both T_u and T_v. 
 
In the other case,  u' v'. Then 
T_u'∩  T_v'∅, because 
T_u∩  T_v∅,  T_u T_u', and T_v T_v'. By induction hypothesis, 
T_u'∩  T_v' consists of  precisely one point p, which  is  a marked leaf in both T_u' and T_v'. 
Then necessarily T_u∩ T_v={p}.
Moreover, p is a marked leaf in both T_u and 
T_v, because marked leaves are passed to children. 
The  statement follows. 

(iii)  Let n∈ and u∈ W_n. Then we have T_uk T_u for each k∈𝒜 by our construction.  Conversely, suppose T_v T_u, where v=v'k∈ W_n+1 with  v'∈ W_n and k∈𝒜. Then T_v'∩ T_u⊇ T_v contains more than one point. By (iii)
this implies that v'=u. The statement follows. 

(iv) If u∈ W_n, n∈_0, then by construction c_u∈ T_u  does not lie in the set ∂ T_u of marked leaves of T_u. By (ii) this implies that c_u∉T_w for each w∈ W_n, w u. It follows that the points c_u, u∈ W_n, are all distinct, and 
none of them is contained  in the union of sets ∂ T_u, u∈ W_n. By our construction this union is equal to the set of all  points c_v, where   v∈ W_* is a word of length ≤ n-1. This shows that the branch points 
 c_u, u∈ W_n, used to define the subtrees of level n+1 are all distinct and distinct from any of the previously chosen branch points for  levels ≤ n. The statement follows from this.  




  
We have 
lim_n→∞sup{(T_u): u∈ W_n} =0. 

 Let δ_nsup{(T_u): u∈ W_n}
for n∈. It is clear that the sequence 
{δ_n} is non-increasing. To show that δ_n→ 0 as n→∞, we argue by contradiction. Then there exists 
δ>0 such that δ_n≥δ for all n∈. 
This means that for each n∈ there exists u∈ W_n with 

    (T_u)≥δ.

We now use (<ref>) to find an infinite word w=w_1w_2…∈ W such that 

    (T_w_1… w_n)≥δ

  for all n∈. 
The word w is constructed inductively as follows. 
 One of the finitely many letters k∈𝒜  must have the property that there are arbitrarily long words u starting with k such that (<ref>) is true.  

We define w_1=k. Note that then (T_w_1)≥δ. 
T  By choice of w_1,   one of the letters  ℓ∈𝒜  must have the property that 
there are arbitrarily long words u starting with w_1ℓ  
such that (<ref>) is true. We define w_2=ℓ.
Then (T_w_1w_2)≥δ.  Continuing in this manner, we can find w=w_1w_2…∈ W satisfying  (<ref>). 

Obviously, 

    T_w_1⊇ T_w_1w_2⊇ T_w_1w_2w_3⊇…  .
 
So the subtrees K_n=T_w_1… w_n, n∈, of T form a descending family of compact sets with (K_n)≥δ. 
This implies that 

    K=⋂_n∈ K_n
 is a non-empty compact subset of 
T with (K)≥δ.

In particular, we can choose p,q∈ K with p q. Then 
p,q∈ K_n for each n∈. Since K_n is a subtree of T, we then have [p,q] K_n. Moreover, by Lemma <ref> there exists a branch  point x of T contained  in (p,q) K_n. 
By Lemma <ref> (iii) the points p and q lie in different components of  K_n{x}.  In particular, for each n∈ the point x is not a leaf of K_n and hence distinct from the marked leaves of K_n. 
 






 
 By Lemma <ref> there are only  finitely many  branch  points y_1, …, y_s of T distinct   from x with H_T(y_j)≥ H_T(x)>0 for j=1, …, s. This implies that at most s of the trees K_n are leaf-tiles, i.e., have only one marked leaf. Indeed, 
 if K_n  an leaf-tile, then it is decomposed into  branches  by use of a branch point c∈ K_n∂ K_n with the largest height H_T(c). The point c is then a marked leaf in each of the 
 children of K_n and in particular in K_n+1.  
 Since the branch  point x∈ K_n is distinct from the marked leaves of K_n and K_n+1, we have x∈ K_n∂ K_n
 and x c.  So  x was not chosen to decompose K_n, and we must have 
 H_T(c)≥ H_T(x). Since the branch  points c that appear from leaf-tiles at different levels n are all distinct as follows from Lemma <ref> (iv), we can have at most s 
 leaf-tiles in the sequence  K_n, n∈. 
This implies  that there exists N∈ such that K_n for n≥ N is an arc-tile and so has precisely two marked leaves.  
 
 Let a,b∈ K_N with a b be the marked leaves of K_N.
 As we travel from x along [x,a] K_N towards a, there is a first point x' on [a,b]. Then x' a.  Otherwise,  
x'=a. Then 
 [x,a] and [a,b] have only the point a in common, which implies that [x,a]∪ [a,b]  is an arc equal to [x,b]. Then a∈ (x,b), which by Lemma <ref> (iii) implies that x,b∈ K_N lie in different components of K_N{a}. This contradicts  
the fact that a is a leaf of K_N and so K_N{a} has only one component. Similarly, one can show that 
x' b.  

The point x' is a branch  point of T. This is clear if x'=x.
If  x' x, this follows from Lemma <ref>, because a,b,x x' and the arcs 
[a,x'), [b,x'), [x,x') are pairwise disjoint. 

The tree K_N+1 is a branch of K_N obtained from a branch point c∈ (a,b) of T with largest height H_T(c) among all branch  points  on (a,b). We have x' c. Otherwise, x'=c. Then x x', because x'=c is a marked leaf of K_N+1 and 
x is distinct from all the marked leaves 
in any of the sets K_n. This implies that  
the points a,b,x lie in different components  of K_N{x'}
and hence in different branches of x' in K_N.  Since  a and b are the marked leaves of K_N, the  branches containing a and b are arc-tiles and all other branches of x'=c in K_N are leaf-tiles. The unique branch of x' in K_N   containing x, which is equal to K_N+1, must be a leaf-tile by the way we  decomposed  T.  This is impossible by  choice of N  and so indeed x' c. 
Note that this implies  H_T(c)≥ H_T(x'). 

Since x' c, c∈ (a,b), and [x,x')∩ [a,b]=∅, we have 
[x,x'] K_N{c}. So x' lies in the same branch of c in K_N as x, which is K_N+1. Moreover, depending on whether c∈ (a,b) lies on the right  or  left of x'∈ (a,b), we have x'∈ (a,c) or 
x'∈ (c,b). In the first case, [a,c] K_N+1 and a and c are the marked leaves of K_N+1. In the second case,  
[c,b] K_N+1 and c and b are the  marked leaves of K_N+1. So in both cases, if  a' and b' are the marked leaves of K_N+1, then x'∈ (a',b'), [x,x'] K_N+1, and 
[x,x')∩ [a',b']=∅. 

These facts allow us 
to repeat the argument for K_N+1 instead of K_N. 
Again K_N+1 is decomposed into branches by choice of a branch point c'∈ (a',b'). We must have c' x', because otherwise we again obtain a contradiction to the fact that K_N+2 is not a leaf-tile. This implies that H_T(c')≥ H_T(x'). Continuing in this manner, we obtain an infinite sequence of  branch points c,c', …. By construction these branch points are all distinct and have a height ≥ H_T(x'). This is impossible by Lemma <ref>. We obtain a contradiction that establishes the statement.    

The previous argument shows that each branch  point x  of T will eventually be chosen as a branch  point in   the decomposition  of T into the subtrees T_u, u∈ W_*. Indeed, otherwise x is distinct from all the marked leaves of any of the subtrees T_u, u∈ W_*. 
This in turn implies that there exists a unique infinite word 
w=w_1w_2…∈ W such that x∈ K_n T_w_1… w_n for n∈. From this one obtains a contradiction as in the last part of the proof of Lemma <ref>. 


  Let m∈, m≥ 3, and  suppose T and S are trees in T_m. Assume that  subtrees T_u of T and S_u of S with signed marked leaves have been defined for u∈ W_* by the procedure described above. Then the following statements are true:


 

  (i) Let n∈, u∈ W_n, and v∈ W_n+1. Then T_v T_u if and only if S_v S_u. 


  (ii)   For  n∈ and  u,v∈ W_n with u v we have  T_u∩ T_v∅
if and only if 
S_u∩  S_v∅. Moreover, if these intersections are non-empty, then they are singleton sets, say 
{p}=T_u∩ T_v and {p}=S_u∩  S_v.
The point  p is a signed marked leaf in T_u and T_v, the point 
p is a signed marked leaf in S_u and S_v, 
(p, T_u)=(p, S_u),  and (p, T_v)=(p, S_v). 

 

In (ii) we are actually only interested in the statement that 
T_u∩ T_v∅
if and only if 
S_u∩  S_v∅. The additional claim in (ii) will help us to prove this statement by an  induction  argument. 


 (i) This follows from Lemma <ref> (iii) applied to the decompositions of T and S. Indeed, we have 
T_v T_u if and only if v=uk for some k∈𝒜 if and only if S_v S_u. 

(ii)  We prove this  by induction on n∈. The case 
  n=1 is clear by how the decompositions were chosen.   
  
  
  Suppose the claim is  true for  words  of 
length n-1, where n≥ 2.  Now consider two words u,v∈ W_n of length n  with u v.  Then u=u'k and v=v'ℓ∈ W_n,  where  u',v'∈ W_n-1 and k,ℓ∈𝒜. Since the claim is symmetric in T and S, we may assume that T_u∩ T_v∅. 

If  u'=v', then T_u and T_v are two of the branches obtained from T_u' and  a branch  point c∈ T_u'. In this case, 
T_u∩ T_v={c} and c is a marked leaf in both T_u and T_v. 
 Similarly, S_u and S_v are two of the branches obtained from S_u' and  a branch  point c∈ S_u'. We  have S_u∩ S_v={c} and c is a marked leaf in both S_u and S_v.
 Moreover, c  has the same sign in  T_u as c in S_u. Indeed, by the  choice of labeling in the decomposition, this sign is + if k=1 and - otherwise. Similarly, 
 c has the same sign in T_v as c in S_v. 
 This shows that the statement is true in this case.
 
 
In the other case,  u' v'. Then 
T_u'∩  T_v'∅, because
T_u∩  T_v∅,  T_u T_u', and T_v T_v'. Then by induction hypothesis, 
T_u'∩  T_v' consists of precisely one point p that is  a marked leaf in  both T_u' and  T_v'. The set  S_u'∩ S_v' consists of one point p that is a marked leaf in S_u' and S_v'. Moreover, we  have 
(p,T_u')=(p,S_u') and (p,T_v')=( p,S_v'). Since ∅ T_u∩ T_v T_u'∩  T_v'={p}, we then have  T_u∩ T_v={p}.   


If (p,T_u')=(p,S_u')=-, then 
u=u'1, because p∈ T_u. Hence p∈ S_u'1=S_u, because the  marked leaf p of S_u' with (p,S_u')=- is passed to the child S_u'1.   
If (p,T_u')=(p,S_u')=+, 
 then u=u'2 and p∈ S_u'2=S_u.  
 
Similarly, if (p,T_v')=(p,S_v')=-,
then v=v'1 and if (p,T_v')=(p,S_v')=+, then 
v=v'2, because p∈ T_v.  In both cases, p∈ S_v. 

In each of these cases,  p is a marked leaf in T_u and T_v, and p is a marked leaf in  S_u and  S_v.
 In particular, 
{p} S_u∩ S_v S_u'∩ S_v'={p} and so 
S_u∩ S_v={p}.  So both T_u∩ T_v={p} and 
  S_u∩ S_v={p} are singleton sets consisting of marked leaves as claimed.
 Since signed marked leaves are passed to children with the same sign, we have 
 
    (p,T_u)= (p,T_u')=(p ,S_u')=(p,S_u).

 Similarly, we conclude that (p,T_v)= (p,S_v).  The statement  follows.   

We are now ready to prove 
 Theorem <ref>, and  Theorem <ref> as an immediate consequence.   
 



 Proof of Theorem <ref>. Let m be as in the statement, and consider arbitrary trees T and S in the class T_m.  For each n∈ we consider 
the decompositions  T=⋃_u∈ W_n T_u 
and S=⋃_u∈ W_n S_u as defined earlier in this section. 
Here of course, W_n=W_n(𝒜), where 𝒜={1,2,…, m}. 

We want to show that  decompositions of T and S for different levels n∈  have the properties 
in Proposition <ref>. In this proposition the index i for fixed level n corresponds to the words u∈ W_n. 

The spaces T and S are trees and hence compact. The sets T_u and S_u appearing in their decompositions are subtrees and hence non-empty and compact. Conditions (i), (ii), and (iii) in Proposition <ref> follow from  
 Lemma <ref> (iii), (<ref>), and Lemma <ref>, respectively.  
Finally, (<ref>) and (<ref>) follow
from Lemma <ref> (i) and (ii).  

Proposition <ref> implies T and S are homeomorphic as desired.   



Proof of Theorem <ref>. 
 As we have seen in 
Section <ref>, the CSST  is a metric tree with the properties
(i) and (ii) as in the statement (see Proposition <ref>
and  Proposition <ref>). In particular,  belongs to the class _3. 
Since  these properties (i) and (ii) are obviously invariant
under homeomorphisms, every metric tree T homeomorphic to  has these properties. 

Conversely, suppose that T is a metric tree with  properties (i) and (ii). Then T belongs to the class _3. So  Theorem <ref> for  m=3 implies that  T and  are homeomorphic.
  

The method of proof for  Theorem <ref> can be used to a establish a slightly stronger result for m=3. 
 
  Let T and S be trees in 
_3. Suppose p_1,p_2,p_3∈ T are three distinct leaves of  
 T, and q_1,q_2,q_3∈ S  are three distinct leaves of  
 S. Then there exists a homeomorphism f  T S such that 
 f(p_k)=q_k for k=1,2,3. 
 
 Note that -1,1∈ are leaves of  as follows from 
 Lemma <ref> (ii). Moreover, i∈ is also a leaf of , because the set 
 
    ∖{i}=_1∪_2∪(_3∖{i})=
     _1∪_2∪ g_3(∖{1})

 is connected. Hence  , and so by Theorem <ref> every tree in _3, has at least three  leaves (actually infinitely many).
 If we apply Theorem <ref>  to S=, then we see that 
  if T is a tree in _3 with three distinct leaves p_1, p_2, p_3, then there exists a homeomorphism f  T such that 
  f(p_1)=-1, f(p_2)=1, and f(p_3)=i. 
  
  
  Proof of Theorem <ref>. 
We will employ a slight modification of our decomposition and coding procedure. The underlying alphabet corresponds to the case m=3, 
and so 𝒜={1,2, 3}. We describe this  for the tree T. Essentially, one wants to use the leaves p_1, p_2, p_3 of T as additional  marked leaves for any of the inductively defined subtrees T_u for  n∈ and u∈ W_n=W_n(𝒜) if it   contains any of these leaves. Here p_1   carries the sign -, while p_2 and p_3 carry the sign +. 

Instead of starting the decomposition process  with   a branch point c∈ T of maximal height, one chooses a branch point c so that 
the leaves p_1, p_2, p_3 lie in distinct branches 
T_1, T_2, T_3 of c in T, respectively. To find such a branch point, one  
 travels from p_1 along  [p_1,p_2] until one first 
 meets [p_2,p_3] in a point c. Then the sets [p_1, c), 
 [p_2, c), [p_3, c) are pairwise disjoint. For k,ℓ∈𝒜 with  kℓ the set [p_k, c)∪{c}∪ (c,p_ℓ] is an arc with endpoints p_k and p_ℓ, and so it must agree with  [p_k, p_ℓ]. In particular, 
 c∈ [p_k, p_ℓ].  Since each  point p_k is a leaf, it easily follows from Lemma <ref> (iii) that c p_1, p_2, p_3. Indeed, if c=p_1 for example, then c=p_1∈ [p_2, p_3] and so 
 p_2 and p_3 would lie in different components of T∖{p_1}. This is impossible, because p_1 is a leaf of T and so 
 T∖{p_1} is connected.   
 
 We conclude that 
 the connected sets  [p_1, c), 
 [p_2, c), [p_3, c) are non-empty and must lie in different branches T_1, T_2, T_3 of c. In particular, c is a branch point of T. We can choose the labels so that p_k∈ T_k for k=1,2,3. 
 The point c is a marked leaf in each of theses branches with a  sign chosen  as before. With the additional signs for the distinguished leaves, we then have the set of marked leaves
 {p_1^-, c^+} in T_1, {c^-, p_2^+} in T_2, and 
 {c^-, p_3^+} in T_3. 
 
 We now continue inductively 
 as before. If we  have already constructed a subtree 
 T_u for some n∈ and u∈ W_n with one or two signed marked leaves, then we   decompose T_u into three branches labeled 
T_u1, T_u2, T_u3 by using a suitable branch point c∈ T_u.  Namely, if   T_u is a leaf-tile and has one marked leaf  a∈ T_u, we choose a branch point c∈ T_u∖{a} with maximal height H_T(c). If 
T_u is an arc-tile with two marked leaves {a,b} T_u we choose a branch point c∈ T_u of maximal height on (a,b) T_u. 

Marked leaves and their signs are assigned to the children 
T_u1, T_u2, T_u3 of T_u as before. In particular, 
 a marked leaf x^- of  T_u is passed to  T_u1 with the same sign. Similarly, a marked leaf x^+ of T_u
 is passed to T_u2 with the same sign. If we continue in this manner, we obtain subtrees T_u with one or two signed marked leaves for all levels n∈ and u∈ W_n. 


We  apply the same procedure for the tree S and its leaves 
q_1, q_2, q_3. Then Lemma <ref>, Lemma <ref>, and  Lemma <ref> are true (with almost identical proofs) for the decompositions of T 
and S obtained in this way. 
 The argument  in the proof of Theorem <ref>   based on 
Proposition <ref> now guarantees the existence of a  homeomorphism 
f  T S such that 

    f(T_u)=S_u  for all n∈ and u∈ W_n.




In our construction p_1∈ T_1 carries the sign - and is 
hence passed to T_11 with the same sign; so p_1∈ T_11. Repeating this argument, we see the 

    p_1∈ T_1∩ T_11∩ T_111∩….
 
The latter nested intersection of compact sets  cannot contain
 more than one point, because by  Lemma <ref> the diameters of our subtrees T_u,
 u∈ W_n,  approach 0 uniformly as n→∞.
  Thus,  {p_1}= T_1∩ T_11∩ T_111∩… . 
 The same argument shows that 
{q_1}=S_1∩ S_11∩ S_111∩…  , 
 and so 
 (<ref>) implies that f(p_1)=q_1.

 Similarly, the points p_2, p_3, q_2, q_3 carry the sign + in their respective trees. This leads to 

    {p_2}   =T_2∩ T_22∩ T_222∩…,   {q_2}=S_2∩ S_22∩ S_222∩…,  
    {p_3}   =T_3∩ T_32∩ T_322∩…,    {q_3}=S_3∩ S_32∩ S_322∩…,
 
which by (<ref>)  gives  f(p_2)=q_2 and f(p_3)=q_3.

 We have shown the existence of a homeomorphism f T S with the desired normalization.  

 




 








 The authors would like to thank Daniel Meyer for many valuable comments on this paper. The first author was partially supported by NSF grants DMS-1506099 and  DMS-1808856.



























99.


[Al91]AldousI D. Aldous:  The continuum random tree. I. Ann. Probab. 19 (1991), 1–28. 

[Be02]Best M. Bestvina:  -trees in topology, geometry and group theory. In:  Handbook of Geometric Topology, Eds. R.J. Daverman and  R.B. Sher, North-Holland, Amsterdam, 2002, pp. 55–91. 



[BT01]BT01 C.J. Bishop and  J.T. Tyson: Conformal dimension of the antenna set.  Proc.  Amer. Math. Soc. 129 (2001), 3631–3636. 


[Bo06]Bo06 M. Bonk: Quasiconformal geometry of fractals. In: Proc. Internat. Congr. Math. (Madrid 2006), Vol. II,  Eur. Math. Soc., 
Zürich, 2006,   pp. 1349–1373. 

[BM19a]BM19a  M. Bonk and D. Meyer:  Uniformly branching trees. In preparation.  

[BM19b]BM19b  M. Bonk and D. Meyer:  Quasiconformal and geodesic tree. Fund. Math., to appear. 

[BM17]BM  M. Bonk and D. Meyer:  Expanding Thurston maps. Vol. 225 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2017.





[CG93]CG 
L. Carleson and T.W. Gamelin: Complex dynamics,  Springer-Verlag, New York, 1993.

[Ch80]Ch80 J.J. Charatonik: Open mappings of universal dendrites. Bull. Acad. Polon. Sci. Ser. Sci. Math. 28
(1980), 489–494.


[CC98]CC98  J. Charatonik and W.J. Charatonik: 
Dendrites. XXX National Congress of the Mexican Mathematical Society (Aguascalientes, 1997), pp. 227–253,
Aportaciones Mat. Comun., 22, Soc. Mat. Mexicana, México, 1998. 

[CD94]CG94 W.J. Charatonik and A. Dilks: On self-homeomorphic spaces. Topology Appl. 55 (1994),  215–238. 



[CH08]Croydon-Hambly 
D. Croydon and B. Hambly: Self-similarity and spectral asymptotics for the continuum random tree. Stochastic Process. Appl., 118(5):730–754, 2008.

[Cu14]Curien 
N. Curien: Dissecting the circle, at random. In: Journées MAS 2012, volume 44 of ESAIM Proc., pp. 129–139. EDP Sci., Les Ulis, 2014.

[DH84]DH A. Douady and J.H. Hubbard: Étude dynamique des polynômes complexes. Partie I. Vol.  84 of Publications Mathématiques 
d'Orsay. Université de Paris-Sud, Département de Mathématiques, Orsay, 1984.

[Fa03]Fa03  K. Falconer: Fractal Geometry. 2nd ed.
 Wiley,  Hoboken, NJ, 2003. 




[DLG05]Duq-LeGall T. Duquesne and J.-F. Le Gall: Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields, 131 (2005), 553–603. 

[He01]He J. Heinonen. Lectures on Analysis on Metric Spaces.
Springer, New York, 2001.



[HY61]HY  J.G. Hocking and G.S. Young. Topology. Addison-Wesley Publishing
Co., Inc., Reading, Mass.-London, 1961.


[Hu81]Hu81 J.E. Hutchinson: 
Fractals and self-similarity.
Indiana Univ. Math. J. 30 (1981),  713–747. 

[Kig18]Kig18 J. Kigami: Weighted partition of a compact metrizable space, its hyperbolicity and Ahlfors regular conformal dimension, preprint, 2018, arXiv:1806.06558. 

[Kig01]Kigami J. Kigami: Analysis on Fractals. Vol. 143 of Cambridge Tracts in
Mathematics, Cambridge University Press, Cambridge, 2001.

[Kiw02]Kiw02 J. Kiwi: Wandering orbit portraits. Trans. Amer. Math. Soc.
354 (2002), 1473–1485. 

[Ku68]Ku68 K. Kuratowski: Topology. Vol. II.  Academic Press, New York-London; PWN—Polish Scientific Publishers, Warsaw, 1968.

[LR19]LR19 P. Lin and S. Rohde:
Conformal welding of dendrites.
  Preprint, 2019.



[LG06]LeGall J.-F. Le Gall. Random real trees. Ann. Fac. Sci. Toulouse Math.
(6) 15 (2006), 35–62.





[Me32]Me32 K. Menger: Kurventheorie. Teubner, Leipzig, 1932.


 [Na92]Na S.B. Nadler, Jr.:  Continuum Theory.  Monographs and Textbooks in Pure and Appl. Math., 158. Marcel Dekker, New York, 1992. 
 
  [Wa23]Wa23  T. Wazewski: Sur les courbes de Jordan ne renfermant aucune courbe simple fermeé de Jordan. Ann. Soc. Polonaise  Math. 2 (1923), 49–170. 


[Wh63]Wh G.T. Whyburn: Analytic Topology.
   Colloquium. Publ., Vol. 28,  American Mathematical Society, Providence, RI, 1963. 
























