# Urysohn ultrametric spaces and isometry groups

TABLE OF CONTENTS ACKNOWLEDGEMENTS iii CHAPTER 1. INTRODUCTION 1.1. Motivation 1 1.2. Universality in Separable Ultrametric Spaces 1 1.3. R-Urysohn Metric Spaces 3 1.4. Complexity of The Classi_cation of All Polish Ultrametric Spaces 4 1.5. Isometry Group of Separable Complete Ultrametric Spaces 5 CHAPTER 2. UNIVERSALITY IN POLISH ULTRAMETRIC SPACES 2.1. Admissible Sets of Distance 8 2.2. Tree Constructions 11 2.3. Classi_cation of General R-ultrametric Spaces 17 2.4. Countable R-ultra-Urysohn Space 25 2.5. Some Abstract Conclusions 37 CHAPTER 3. ISOMETRY GROUPS OF POLISH ULTRAMETRIC SPACES 3.1. Isometry Groups of Polish Ultrametric Spaces 44 3.2. Isometry Groups of Finite Ultrametric Spaces 62 3.3. Isometry Groups of Compact Ultrametric Spaces 67 3.4. Isometry Group of R-ultra-Urysohn Space 78 3.5. More About General R-ultrametric Spaces 83 3.6. Open Problems 85 BIBLIOGRAPHY 88

CHAPTER 1 INTRODUCTION 1.1.Motivation In this dissertation we study separable ultrametric spaces.The following are natural and fundamental questions in this area which motivated my research: (1) Do there exist universal spaces for the class of all separable ultrametric spaces?Are there such spaces with the Urysohn property? (2) What is the exact complexity of the classiﬁcation problem of all complete separable ultrametric spaces up to isometry? (3) How do we characterize the isometry groups of separable ultrametric spaces? Each of the above problems also makes sense for subclasses of separable ultrametric spaces,such as compact,locally compact,and so on.Thus,we have a large number of open problems in this interesting area. The following describes our main ﬁndings. 1.2.Universality in Separable Ultrametric Spaces In 1927,Urysohn [12] deﬁned a Polish metric space which turned out to contain all other Polish spaces as closed subspaces. Theorem 1.1 (Urysohn).There exists an unique universal Urysohn Polish space,U. Definition 1.2.A metric space U is said to be universal for a family M of metric spaces if any space from Mis isometrically embeddable in U. 1

Definition 1.3.A metric space M with {d(a,b):a,b ∈ M} = R is called R-Urysohn if for any ﬁnite metric space A with {d(x,y):x,y ∈ A} ⊆ R,and any subspace B ⊆ A,every isometric embedding f:B → i M can be extended to an isometric embedding g:A → i M. Urysohn proved Theorem 1.1 by showing U has the Urysohn property.Since one space has the Urysohn property implies it has the universality,U is universal. In recent years,much interest was devoted to the universal (Urysohn) spaces,and more results were obtained (see [1],[3],[5],[9],[14],[15] and [16]).This is also connected to the study of countable random graphs (See [2],[4] and [7]).People also noticed that:If a collection of spaces has the universality,it is unnecessary for its sub collection to have the universality.For example,there exists a universal Polish space for the collection of all Polish metric spaces,but there does not exist a universal space for the collection of all compact metric spaces. The collection of complete separable ultrametric spaces is a sub-collection of Polish spaces.The existence of a universal Polish ultrametric space is not certain as well.This dissertation is focus on the study of complete separable ultrametric spaces. Definition 1.4.An ultrametric on a set of points X is a metric d:X × X → R,which satisﬁes:d(x,z) ≤ max{d(x,y),d(y,z)},∀x,y,z ∈ X. First,we note that any separable ultrametric space (X,d) realizes only a countable set of distances,i.e.the set R X = {d(x,y):x,y ∈ X} is countable.It follows easily that there does not exist a universal separable ultrametric space. Thus a natural way to continue our study is to consider a ﬁxed countable set R ⊆ R ≥0 of potential distances.We call an ultrametric space X with R X ⊆ R an R-ultrametric space. The question now becomes:For what set R does there exist a universal R-ultrametric space? The answer turns out to be aﬃrmative for any {r i } ∞ i=0 ⊆ R ≥0 with r 0 = 0 as following: 2

Theorem 1.5.For any countable R ⊆ R ≥0 with 0 ∈ R,there exists an unique corresponding universal complete separable R-ultrametric space,and we denote it as U u R . Note that such R can even be a dense subset of R like the set of all rational numbers or with gap like the set:

1 2 + 1 n

∞ n=1 ∪ {0}.We give two diﬀerent proofs for Theorem 1.5 in this dissertation. Way 1:By using the tree construction.Note the tree that we will use in this proof is diﬀerent fromtrees people normally talk about in set theory.The tree that we construct here has the following property:If you pick an arbitrary node u in the tree,then the collection of all nodes that extended by u gives a linear-order.While the property for a tree that people normally use in set theory:If you pick an arbitrary node v in the tree,then the collection of all nodes that extended by v gives a well-order. Way 2:By showing U u R is R-ultra-Urysohn (An R-ultrametric space X is called R- ultra-Urysohn if for any ﬁnite ultrametric space A with {d(x,y):x,y ∈ A} ⊆ R,and any subspace B ⊆ A,every isometric embedding f:B → i X can be extended to an isometric embedding g:A → i X.).This proof is similar as the proof that Urysohn gave to show the existence of Urysohn Polish metric space.But from this proof we will continue to give complete characterization of R-Urysohn space. While for special cases of R we have the following conclusion: Theorem 1.6.(X,d) is a compact R-ultrametric space iﬀ R X = {r i } ∞ i=1 ∪{0} with r i+1 < r i and r i →0.Moreover for any ﬁxed such R,([ω <ω ],d R ) is a universal R-ultrametric space. 1.3.R-Urysohn Metric Spaces We also consider the further question:For which set R does there exist an R-metric space with the R-Urysohn property?It is known that for some R the answer is negative, and we obtain a complete characterization for the sets R for which the answer is positive as following: 3

Theorem 1.7.For countable R ⊆ R TFAE: (1) There exists a countable R-Urysohn space. (2) There exists a R-Urysohn space. (3) R has Basic Amalgamation Property. (4) ∀a,b,c,d ∈ R with [max{|a −c|,|b −d|},min{a +c,b +d}] ∩R = ∅ we have [c −d,a +b]

R = ∅. From the above characterization,we can easily see for a large family of R,there exist corresponding countable R-Urysohn spaces.Moreover,we have the following conclusion for uncountable R: Theorem 1.8 (Joint with Gao and Jackson).For any uncountable R with |R| = ω 1 ;(2), (3) and (4) in Theorem 1.7 are still equivalent. 1.4.Complexity of The Classiﬁcation of All Polish Ultrametric Spaces Note that every dense subset of R-ultra-Urysohn space is R-ultra-Urysohn.Moreover,for every separable complete R-ultra-Urysohn space X,the countable dense subset D is unique up to isometry.Then we deﬁne Basic Amalgamation property as: Definition 1.9.We say a countable R ⊆ R has Basic Amalgamation Property,if for any ﬁnite R-metric space (A,d A ) and any distinct x,y/∈ A,whenever (A

{x},d x ) and (A

{y},d y ) are R-metric spaces,with d x A = d A & d y A = d A ,we can extend (A,d A ) to be a R-metric space (A

{x,y},d) with d (A

{x}) = d x & d (A

{y}) = d y . We show that for any ﬁxed countable R with Basic Amalgamation Property we can give a direct point-by-point construction of the countable R-ultra-Urysohn space.This gives a diﬀerent proof of an earlier theorem of Gao and Kechris [6] by establishing a duality between R-ultrametric spaces with R-trees. In view of the recent results of Louveau and Rosendal [?],we also have the following corollary: 4

Theorem 1.10.For any ﬁxed countable set R of non-negative numbers,including 0;with 0 ∈ R−{0}.The isometric embeddability between separable complete R-ultrametric spaces is an universal Σ 1 1 quasi-order.The isometric biembeddability between separable complete R-ultrametric spaces is a universal Σ 1 1 equivalence relation. 1.5.Isometry Group of Separable Complete Ultrametric Spaces Note the following two theorems about Polish metric spaces,one was proved by Gao and Kechris [6],and the other was proved recently by Melleray [11]: Theorem 1.11 (Gao-Kechris).Up to (topological group) isomorphism the isometry groups of Polish metric spaces are exactly the Polish groups. Theorem 1.12 (Melleray).Up to (topological group) isomorphism the isometry groups of compact metric spaces are exactly the compact metrizable groups. Also note that Gao and Kechris [6] completely characterized the isometry groups of locally compact separable metric spaces.This characterization implies that isometry group of a locally compact separable space is not always a locally compact Polish group. Motivated by the above results in Polish metric spaces,we investigate isometry groups of complete separable ultrametric spaces and try to characterize them. From earlier results we know that the isometry group of any separable complete ultra- metric space is a closed subgroup of S ∞ .So we try to characterize which closed subgroups of S ∞ are isomorphic to such isometry groups.We show that one necessary condition is that involutions in the isometry group generate a dense subset.However,this condition turns out to be insuﬃcient because of some more complex examples constructed. The isometry group of a compact ultrametric space is either ﬁnite or uncountable.Thus, we concentrated on the ﬁnite isometry groups of ultrametric spaces.Also we show that if Iso(X) is a ﬁnite isometry group of an ultrametric space (X,d) and f ∈ Iso(X) such that f = id & f p = id,where p is a prime number.Then,p!must be a factor of |Iso(X)|.By 5

using this necessary condition,we can easily tell some ﬁnite isometry groups,such as ﬁnite cyclic groups,are not isomorphic to any isometry groups of any ultrametric space. On the other hand,since in the section 2.2 & 2.3 of this dissertation we have the result: For any tree T 1 ,T 2 ⊆ ω <ω (ω

Theorem 1.15.If X is a compact orbital ultrametric space,then Iso(X) ∼ = C for some C ∈ C.Where C is the least class of groups such that G ∈ C ⇔G =

n G n where G n = lim ←− m G n,m with f i,j :G n,j →G n,i ,i ≤ j & G n,m ∈ C F . Recall the the following theorem proved by Uspenskij [13]: Theorem 1.16 (Uspenskij).Isometry group of Urysohn Polish space is a universal Polish group. It is natural for us to ask the question:Are isometry groups of the above universal spaces universal?The answer is positive from the following: Theorem 1.17.Every isometry group of R-ultra-Urysohn space is universal for the family of all isometry groups of complete separable R-ultrametric spaces. 7

CHAPTER 2 UNIVERSALITY IN POLISH ULTRAMETRIC SPACES 2.1.Admissible Sets of Distance Definition 2.1.An ultrametric space is a set of points M with a metric d:M ×M →R, where R is the set of real numbers such that for all x,y,z in M,the following hold: (1)d(x,y) ≥ 0. (2)d(x,y) = 0 if and only if x = y. (3)d(x,y) = d(y,x).(symmetry) (4)d(x,z) ≤ max{d(x,y),d(y,z)}.( ultrametric inequality) Fromabove deﬁnition,one can conclude several typical facts of ultrametric spaces (X,d). Fact 2.2.Every triangle is isosceles with possibly a small edge. Proof.Let x,y,z ∈ X.If d(x,y) = d(x,z) = d(y,z) then we have nothing to show.Oth- erwise,without loss of generality suppose d(x,y) > d(y,z).Then we have d(x,z) ≤ d(x,y), since d(x,z) ≤ max{d(x,y),d(y,z)}.Notice that we also have d(x,y) ≤ max{d(x,z), d(y,z)},so d(x,z) ≥ d(x,y).Therefore,d(x,z) = d(x,y). Fact 2.3.For ∀x,y ∈ X,if r = d(x,y),then B r (x)

B r (y) = ∅. Proof.Suppose B r (x)

B r (y) = ∅ and let z ∈ B r (x)

B r (y).Consider the triangle formed by x,y,z.We have d(x,z) < r by our assumption.Since d(x,y) = r,by Fact 2.2, d(x,y) = r = d(z,y).But d(y,z) < r as z ∈ B r (x)

B r (y).Contradiction. Fact 2.4.For ∀x ∈ X and ∀r ∈ R,B r (x) is clopen. 8

Proof.B r (x) is open.To see B r (x) is closed we will show that X −B r (x) is open.Let y ∈ X−B r (x) and suppose d(x,y) = l.By Fact 2.3,we have that B l (x)

B l (y) = ∅.Note that B l (y) is an open set in X containing y.Therefore,B r (x) is closed. Definition 2.5.A topological space X is 0-dimensional if X has a clopen base. Proposition 2.6.Any ultrametric space is 0-dimensional. Fact 2.7.Every point inside a ball is its center,i.e.if d(x,y) < r then B r (x) = B r (y). Proof.Let z ∈ B r (x),then d(x,z) < r.Since d(x,y) < r,by Fact 2.2,we have d(y,z) < r. So z ∈ B r (y).Therefore,B r (x) ⊆ B r (y).Similarly,we can show B r (x) ⊇ B r (y).Hence B r (x) = B r (y). Fact 2.8.Intersecting balls are contained in each other,i.e.if B r (x)

B s (y) = ∅,where x,y ∈ X and r,s ∈ R,then either B r (x) ⊆ B s (y) or B r (x) ⊇ B s (y). Proof.Suppose r < s.Let z ∈ B r (x)

B s (y),then d(x,z) < r and d(z,y) < s.There- fore,B r (x) = B r (z) and B s (y) = B s (z).Note that B s (z) ⊇ B r (z),as r < s;and by Fact 2.7,we have ∀x 0 ∈ B r (x),B r (x 0 ) = B r (x).Hence B r (x) ⊆ B s (y). Similarly,if s < r then B r (x) ⊇ B s (y). Proposition 2.9.If (X,d) is a separable ultrametric space,then {d(x,y):x,y ∈ X} is countable. Proof.Let D be a countable dense subset of X,say D = {x i } i=1 ∞ . Then {d(x i ,x j ):x i ,x j ∈ D} is countable.Want to show ∀x,y ∈ X,∃x i ,x j ∈ D such that d(x i ,x j ) = d(x,y).Let r 1 ,r 2 < d(x,y).Consider B r 1 (x) and B r 2 (y).Since D is countable dense set in X,there exists x i ∈ B r 1 (x)

D.Therefore,d(x,y) = d(x i ,y).Similarly, ∃x j ∈ B r 2

D such that d(x i ,y) = d(x i ,x j ).Hence d(x,y) = d(x i ,x j ). 9

Definition 2.10.A metric space U is said to be universal for a family Mof metric spaces if any space from Mis isometrically embeddable in U. Corollary 2.11.There does not exist a universal separable ultrametric space. Proof.Suppose X is a universal separable ultrametric space,then A = {d(x,y):x,y ∈ X} is countable.Pick arbitrary r ∈ R − A,and let (Y,ρ) be with ∃z 1 ,z 2 ∈ Y such that ρ(z 1 ,z 2 ) = r.Then (Y,ρ) can not be embedded in (X,d). Definition 2.12.A countable R ⊆ R is admissible if there is an ultrametric space (X,d) such that R = {d(x,y):x,y ∈ X}.A countable R ⊆ R is admissible in the sense of compactness if there is a compact ultrametric space (X,d) such that R = {d(x,y):x,y ∈ X}. The objective of this section is to characterize admissible sets. Proposition 2.13.A countable R ⊆ R is admissible in the sense of compactness iﬀ R = {a n } ∞ n=1

{0} with a n+1 < a n and a n →0. Proof.(⇒) Let (X,d) be a compact R-ultrametric space with {d(x,y):x,y ∈ X} = R. Without loss of generality assume R = {a n } ∞ n=1

{0}. Claim:If ∃{a n k } an inﬁnite subsequence of {a n } with {a n k } →c,where c > 0,then R is not admissible in the sense of compactness. (Proof of Claim:) Reenumerate the sequence {a n k } = {b i } ∞ i=1 .Then for each n ∈ N pick x n ,y n ∈ X such that d(x n ,y n ) = b n .Then {x n } ∞ n=1 & {y n } ∞ n=1 are inﬁnite sequences in X.Since X is compact,let {x n k } be a convergent subsequence of {x n } ∞ n=1 ,say x n k →x ∞ . Now {y n k } is an inﬁnite sequence in X,therefore there is a convergent subsequence

y n k j

of {y n k },say y n k j → y ∞ .Then x n k j → x ∞ ,moreover d(x ∞ ,y ∞ ) = c,as a n k → c.Pick y m ∈

y n k j

,with d(y ∞ ,y m ) < c 2 m .Now consider the triangle formed by x ∞ ,y ∞ ,y m . Since X is an ultrametric space,by Fact 2.2,we have d(x ∞ ,y ∞ ) = d(x ∞ ,y m ) = c.Since x n k j → x ∞ ,d(x m ,x ∞ ) arbitrary small,but d(x m ,y m ) = a m ,and d(y m ,x ∞ ) = c.Which 10

means the triangle formed by x ∞ ,x m ,y m is not isosceles,which contradicts that X is an ultrametric space.(End of Proof of Claim) Clearly R does not contain any decreasing subsequence which converges to a nonzero point.Also,R does not contain any inﬁnite increasing sequence.Suppose R contains an inﬁnite increasing sequence {a k } ∞ k=1 .Then by compactness,{a k } ∞ k=1 is bounded above.Let a be the least upper bound of {a k } ∞ k=1 ,then a > 0 and there is a subsequence

a k j

of {a k } ∞ k=1 such that a k j →a.Hence R = {a n } ∞ n=1

{0},with a n+1 < a n and a n →0. (⇐) Suppose R = {a n } ∞ n=1

{0} with a n+1 < a n and a n → 0.Let X = R,and deﬁne metric d on X by:d(x,y) = max{x,y},∀x,y ∈ X.Now we will show (X,d) is an ultrametric space.It suﬃces to show that ultrametric inequality holds for (X,d). Let x,y,z ∈ X,without loss of generality assume d(x,z) ≥ d(y,z).Then y ≤ z and max{x,y} = d(x,y) ≤ d(x,z) = max{x,z}.Hence d(x,y) ≤ max{d(x,z),d(y,z)}.And since a n →0,(X,d) is compact.Therefore,(X,d) is a compact ultrametric space. Remark 2.14.If {b n } ⊆ R with b n →c,where c > 0,then R is not admissible in the sense of compactness. Proposition 2.15.For the general ultrametric space (without compactness),a countable subset R of R is admissible iﬀ 0 ∈ R. Proof.(⇒):Trivial. (⇐):Suppose R = {a n } ∞ n=1

{0}.Let X = R,deﬁne a metric d on X by:d(x,y) = max{x,y},∀x,y ∈ X.Now we will show (X,d) is an ultrametric space.It suﬃces to show that ultrametric inequality holds for (X,d).Let x,y,z ∈ X.Without loss of generality assume d(x,z) ≥ d(y,z).Then y ≤ z and max{x,y} = d(x,y) ≤ d(x,z) = max{x,z}. Hence d(x,y) ≤ max{d(x,z),d(y,z)}. 2.2.Tree Constructions In this section we only consider R is admissible in the sense of compactness. 11

Definition 2.16.Given a set S and n ∈ ω,we regard S n to be the set of all ﬁnite sequences of length n with elements in S.Denote S <ω =

n S n .A tree T on S is a set of ﬁnite sequences from S,closed under subsequences;i.e.,if u ∈ T and v ⊆ u then v ∈ T.Therefore ∀u,v ∈ T, u ⊆ v ⇔ u = v lh(u).In general,T ⊆ S <ω .The empty sequence is always a member of a nonempty tree.A node of a tree is just a sequence in that tree.If u ∗ x ∈ T,then u is a parent of u ∗ x,u ∗ x is a child of u,and x is the immediate successor of u.Let X = S ω be the set of all functions from ω to S.A branch of a tree T is an inﬁnite sequence f ∈ S ω such that for every n,(f(0),...,f(n)) ∈ T.The set of all branches of T is denoted by [T] = {f ∈ S ω :∀n(f(0),· · ·,f(n)) ∈ T}. Example 2.17.Let X be Baire Space,with T = ω <ω . For ∀f,g ∈ [T] deﬁne: d(f,g) = 0,if f = g, 2 −n ,if n is the least such that f (n) = g (n). Let f,g,h ∈ [T].Assume without loss of generality,d(f,h) ≥ d(g,h).Then d(f,g) ≤ d(f,h).Therefore,d(f,g) ≤ max{d(f,h),d(g,h)} and ([T],d) is an ultrametric space.The topology given by this metric is the product topology. Similarly,we can conclude that Cantor Space (T = 2 <ω ) with the same metric is a com- pact ultrametric space. Example 2.18.If (X 1 ,d 1 ) and (X 2 ,d 2 ) are two compact ultrametric spaces. Let {d 1 (x,y):x,y ∈ X 1 } = R 1 = {a n } ∞ n=1

{0} with a n+1 < a n & {d 2 (x,y):x,y ∈ X 2 } = R 2 = {b n } ∞ n=1

{0} with b n+1 < b n .Then X = X 1

X 2 with d(x,y) = d 1 (x,y),if x,y ∈ X 1 , d 2 (x,y),if x,y ∈ X 2 , max{a 1 ,b 1 },if (x ∈ X 1 & y ∈ X 2 ) or (x ∈ X 2 & y ∈ X 1 ). is a compact ultrametric space. 12

Let T be an inﬁnite tree on ω and R = {a n } ∞ n=1

{0},with a n+1 < a n and a n →0. For ∀x,y ∈ [T],let a metric d on [T] be: d(x,y) = 0,if x = y, a n ,if n is the least level such that x(n) = y (n). Denote the space determined by T and R:([T],d) = X T . Definition 2.19.Let T 1 ,T 2 ⊆ ω <ω .Then T 1 → T 2 ,if ∃ϕ:T 1 → T 2 such that for any t,t

∈ T 1 ,the following hold: (1) lh(t) = lh(ϕ(t)). (2) t = t

⇒ϕ(t) = ϕ(t

). (3) t ⊆ t

⇒ϕ(t) ⊆ ϕ(t

). Definition 2.20.Let (X 1 ,d 1 ) & (X 2 ,d 2 ) be metric spaces,then we say ϕ:X 1 →X 2 is an isometry,if ϕ is a distance-preserving isomorphism.We denote X 1 isometrically isomorphic to X 2 as X 1 ∼ = i X 2 . Proposition 2.21.For any tree T 1 ,T 2 ⊆ ω <ω ,we have T 1 → T 2 ⇔ X T 1 → i X T 2 .More- over,T 1 ∼ = T 2 ⇔X T 1 ∼ = i X T 2 . Proof.(⇒) Obvious.(Let ψ:T 1 onto → T 2 be an isomorphism.Deﬁne ϕ:X T 1 → X T 2 by: ϕ(f) =

n ψ(f n).It’s easy to check that ϕ is an isometry.) (⇐) Let ψ:(X T 1 ,d 1 ) → (X T 2 ,d 2 ) be an isometric embedding.Deﬁne ϕ:T 1 → T 2 as following:For any t ∈ T 1 ,let f t be a branch containing t and let ϕ(t) = ψ(f t ) lh(t). Claim:ϕ is well deﬁned. (Proof of Claim:) Let t be an element in T 1 and let f t & f

t be two distinct branches with t ⊆ f t & t ⊆ f

t .Note that d 1 (f t ,f

t ) < a lh(t) .Since ψ is an isometric embedding,we have d 2 (ψ(f t ),ψ(f

t )) = d 1 (f t ,f

t ).Therefore,d 2 (ψ(f t ),ψ(f

t )) < a lh(t) .Hence ψ(f t ) lh(t) = ψ(f

t ) lh(t).(End of Proof of Claim) 13

To see T 1 →T 2 we will show that ϕ satisﬁes the Deﬁnition 2.19. (1) lh(t) = lh(ϕ(t)) by the deﬁnition of ϕ. (2) Let t,t

be distinct elements in T 1 , Case 1:Neither t ⊆ t

nor t ⊇ t

.Let n = min{lh(t),lh(t

)},then ∃k ≤ n such that f t (k) = f t

(k).Therefore,f t = f

t .Since ψ is an isometry,we have ψ(f t ) = ψ(f t

).Especially we have ψ(f t ) (k) = ψ(f t

) (k).Hence ϕ(t) = ψ(f t ) lh(t) = ψ(f t

) lh(t) = ϕ(t

). Case 2:Either t ⊂ t

or t ⊃ t

.Then lh(t) = lh(t

),and by (1),we have ϕ(t) = ϕ(t

). (3) Suppose t ⊆ t

then lh(t) ≤ lh(t

).Therefore,f t lh(t) = f t

lh(t) and hence f t

lh(t) ⊆ f t

lh(t

).So ϕ(t) = ψ(f t ) lh(t) ⊆ ψ(f t