# On the Topological and Uniform Structure of Diversities

Authors: Andrew Poelstra
Journal: Journal of Function Spaces and Applications
 (2013)

---

## Abstract

Diversities have recently been developed as multiway metrics admitting clear and useful notions of hyperconvexity and tight span. In this note, we consider the analytical properties of diversities, in particular the generalizations of uniform continuity, uniform convergence, Cauchy
sequences, and completeness to diversities. We develop conformities, a diversity analogue of uniform spaces, which abstract these concepts in the metric case. We show that much of the theory of uniform spaces admits a natural analogue in this new structure; for example, conformities can be defined either axiomatically or in terms of uniformly continuous pseudodiversities. Just as diversities can be restricted to metrics, conformities can be restricted to uniformities. We find that these two notions of restriction, which are functors in the appropriate categories, are related by a natural transformation.


---

## Body

## 1. Introduction

The theory of metric spaces is well-understood and forms the basis of much of, modern analysis. In 1956, Aronszajn and Panitchpakdi developed the notion of hyperconvex metric spaces [1] in order to apply the Hahn-Banach theorem in a more general setting. In fact, every metric space can be embedded isometrically in a minimal hyperconvex space, as discovered by Isbell [2] (as the “hyperconvex hull”) and later by Dress [3] (as the “metric tight span”).These minimal hyperconvex spaces, or tight spans, proved to be powerful tools for the analysis of finite metric spaces. The theory of tight spans, or T-theory, is overviewed in [4]. Its history, as well as applications to phylogeny, are given in [5].In light of these applications of T-theory, Bryant and Tupper developed the theory of diversities alongside an associated tight span theory in [5]. Diversities are multiway metrics mapping finite subsets of a ground space X to the nonnegative reals. The axioms were chosen based on their specific applications to phylogeny (where they had already appeared in special cases) and their ability to admit a tight span theory. This diversity tight span theory contains the metric tight span theory as a special case (using so-called diameter diversities), but it also allows new behavior which may be useful in situations such as microbial phylogeny, where the idea of a historical “phylogenetic tree” does not make sense. Several examples, along with pictures, of this phenomenon are given in [5].A classic paper by Weil [6] developed the theory of uniform spaces, which generalize metric spaces. Uniform spaces admit notions of uniform continuity, uniform convergence, and completeness which coincide with the standard notions when metric spaces are considered as uniform spaces. This theory has been described in Bourbaki's General Topology [7] as well as Kelley's classic text [8]. The metric topology can be derived purely from properties of the uniform space (via the so-called uniform topology), and in this sense uniform spaces lie “between” metric spaces and topologies.In this note, we develop conformities, which generalize diversities in analogy to Weil's uniform space generalization of metrics. We will describe uniform continuity, uniform convergence, Cauchy sequences, and completeness for diversities, and show that these can be characterized in terms of conformities, giving an abstract framework in which to analyze the uniform structure of diversities. This is motivated by the observation that while diversities generalize metric spaces in a straightforward way (in fact they restrict to metric spaces), they can exhibit very nonsmooth behavior with respect to these spaces (cf. Theorem1). Therefore, the existing tools for metric spaces are insufficient to get a handle on the behavior of diversities.


## 2. Preliminaries

Throughout this paper, we will denote the finite power set of a given setX by
(1)𝒫fin(X)={A⊆X:|A|<∞}.We begin with the Bryant-Tupper definition from [5]: a diversity is a pair (X,δ) where X is some set and δ:𝒫fin(X)→ℝ is a function satisfying  (D1)
ifA∈𝒫fin(X), δ(A)≥0 and δ(A)=0 iff |A|≤1,(D2)
ifA,B,C∈𝒫fin(X) with C≠⌀; then
(2)δ(A∪B)≤δ(A∪C)+δ(C∪B).If for some A∈𝒫fin(X), δ(A)=0 but |A|>1, we have the weaker notion of a  pseudodiversity. It is shown in [5] from these axioms that if A⊆B, then δ(A)≤δ(B); that is, (pseudo)diversities are monotonic and that the restriction of a diversity to sets of size 2 forms a pseudometric d(x,y)=δ({x,y}). We call this metric the  induced metric of the diversity.For a metric space(X,d), there are two important diversities on X having d as an induced metric as follows:  (i)
the  diameter diversity(X,diamd) defined by
(3)diamd({x1,…,xn})=supi,jd(xi,xj),
when X=ℝn and d is the Euclidean metric; we refer to this diversity simply by diam.(ii)
The  Steiner tree diversity(X,δ) is defined for each finite set A⊆X as the infimum of the size of the minimum Steiner tree on A.(Recall that a Steiner tree onA is a tree whose vertex set V satisfies A⊆V⊆X, with each edge (x,y) weighted by d(x,y). The size of the tree is the sum of its edge weights.)In fact, these examples are the extremes of diversity behavior relative to their induced metrics, in the sense that for any diversity(X,δ′) which induces a metric d, we have
(4)diamd≤δ′≤δ,
where δ is the Steiner tree diversity on (X,d). This can be shown by a straightforward argument (Bryant and Tupper, upcoming).To demonstrate the difference between the diameter and Steiner tree diversities, consider the Euclidean metric(ℝ3,d). The induced metric of both the diameter and Steiner tree diversity is the Euclidean metric. For any finite set A contained in an ε-ball, diam(A)<ε. To contrast, in any ε-ball, we can find finite sets A for which δ(A) is arbitrarily large.Theorem 1.
The Steiner tree diversity functionδ on ℝ3 is unbounded on every open set of the Euclidean topology.Proof.
Without loss of generality, we show that the result forε-balls is about 0. For each n∈ℕ, define
(5)Gn={(in2,jn2,kn2):0≤i,j,k<n},
which is a grid of points contained in the cube [0,1/n]3. Since there are n3 points, a minimum spanning tree connecting the members of Gn must have n3-1 edges, each of the lengths ≥1/n2, since that is the least distance between two points. Therefore, the size of the minimum spanning tree on Gn is at least (n3-1)/n2, which can be taken as large as we like by taking n large enough. Since the minimal Steiner tree on Gn has a size of at least 0.615 times than that of the minimal spanning tree [9], we have δ(Gn)→∞ as n→∞ even though diam(Gn)→0.A similar construction for the Steiner tree diversity onℝ2 gives sets of diversity (0.615-ε) for every ε>0 in every Euclidean ball. On ℝ, the Steiner tree diversity and diameter diversity are identical. The dramatic difference between the many-point behavior of these two diversities in dimension 2 or higher demonstrates that diversities are not characterized by their induced metrics, even up to a constant.In Section2 and 3, we will define uniform convergence, uniform continuity, and completeness explicitly in terms of an underlying diversity, in Section 4 we will describe conformities, which abstract these properties for diversities. This is in analogy to Weil's uniformities, which abstract the same concepts for metric spaces.With this goal in mind, we start with the following definitions: let(X,δX) and (Y,δY) be diversities. Given x∈X, a sequence {xn}⊂X  converges tox, denoted xn→x, if
(6)limN→∞supi1,i2,…,in≥NδX({x,xi1,xi2,…,xin})=0.
The sequence {xn} is a  Cauchy sequence if
(7)limN→∞supi1,i2,…,in≥NδX({xi1,xi2,…,xin})=0.
From these definitions, and the axioms (D1) and (D2), it can be shown that limits are unique and every convergent sequence is Cauchy. If every Cauchy sequence is convergent, we call the diversity  complete.Finally, iff:X→Y is a function such that for every ε>0, there exists some d>0 such that δX(A)<d⇒δY(f(A))<ε for every A∈𝒫fin(X), we say f is  uniformly continuous.It is not hard to see that for diameter diversities, these definitions coincide exactly with the standard ones on the induced metric.For the second half of the paper, we will work extensively with filters, so we state the definition here: given a ground setX, define a  filter as a collection ℱ of subsets of X satisfying A∩B whenever A, B are in ℱ, and B∈ℱ whenever B⊇A and A∈ℱ. A  filter base becomes a filter when all supersets of its elements are added, in which case we say the base  generates the filter.In this paper, we additionally require that⌀∉ℱ.


## 3. Comparison with Metrics

In this section, we contrast the convergence of sequences with respect to diversities and their induced metrics. In particular, we show that although the Cauchy property for sequences is much stronger for diversities (we demonstrate a sequence which is not Cauchy with respect to a diversity, even though it is Cauchy with respect to the induced metric), completeness of a diversity is equivalent to completeness of its induced metric. This tells us that every diversity which induces a Euclidean metric (e.g., the Steiner tree diversity onℝn) is complete.Since the set of Cauchy sequences in a diversity may be smaller than the set of Cauchy sequences of its induced metric, this may provide a simpler way to determine completeness of metric spaces.At the end of the section, we construct the analogue of completion for diversities.


### 3.1. Completeness in Diversities and Metric Spaces

Theorem 2.
Let(X,δ) be a diversity, and let d be its induced metric. If (X,d) is a complete metric space, then (X,δ) is a complete diversity.Proof.
Suppose that(X,d) is complete. Let {xn} be a Cauchy sequence in (X,δ). Then, it is also Cauchy in (X,d), and therefore converges to some element x. We claim that xn→x, in (X,δ). To this end, let ε>0. Then, there exists N, such that  (i)
d(xn,x)<ε for all n>N (since xn→x in (X,d)),(ii)
δ({xn1,xn2,…,xnm})<ε for all ni>N (since {xn} is Cauchy in (X,δ)).
Therefore, for alln1,…,nm>N,
(8)δ({x,xn1,…,xnm})≤δ({x,xn1})+δ({xn1,…,xnm})=d(x,xn1)+δ({xn1,…,xnm})<2ε,that is,xn→x in (X,δ).As mentioned, the set of Cauchy sequences in a diversity may be strictly smaller than the set of Cauchy sequences in the induced metric. For example, let(X,δ) be the Steiner tree diversity on ℝ3, and consider the sets {Gn}n∈ℕ from Theorem 1.Order each setGn somehow and define the sequence {xi} by concatenating them, that is,
(9){xn}=G1G2G3⋯,
which is Cauchy in the induced metric of (X,δ) (since eventually every pair of points is confined to arbitrarily small cubes [0,ε]3). However, it is not Cauchy in (X,δ), since we saw in the proof of Theorem 1 that δ(Gn) becomes arbitrarily large as n→∞. In other words, every tail of {xn} has arbitrarily large finite sets, so {xn} is not Cauchy.In light of this example, it is interesting to know that every complete diversity has a complete induced metric, which is proved with the following lemma.Lemma 3.
Let(X,δ) be a diversity, and let d be its induced metric. Let {xn} be Cauchy in (X,d). Then, it has a subsequence that is Cauchy in (X,δ).Proof.
Define the subsequence{xni} by
(10)ni=min{n:d(xn,xm)<2-i∀m≥n}.Given ε>0, choose N such that 21-N<ε. Then, for all i1≤i2≤⋯≤im greater than N,
(11)δ({xi1,…,xim})≤δ({xi1,xi2})+⋯+δ({xim-1,xim})<12i1+⋯+12im<∑i=N∞1/2i=21-N<ε.That is, {xni} is Cauchy in (X,δ).Theorem 4.
Let(X,δ) be a diversity, and let d be its induced metric. If (X,δ) is a complete diversity, then (X,d) is a complete metric space.Proof.
Let{xn} be a Cauchy sequence in (X,d). Then, by Lemma 3 it has a subsequence {xin} that is Cauchy in (X,δ), which converges to some element x since the diversity is complete (it converges in both (X,δ) and (X,d)).
Then,xn converges to x in (X,d), since for any ε we have d(xn,x)≤d(xn,xim)+d(xim,x)<2ε for m,n large enough.


### 3.2. Completion

In light of the equivalence between metric completeness and diversity completeness, it is perhaps not so surprising that every diversity can be completed in a canonical way. To do so, we require two more definitions from [5]: an  embedding  π:Y1→Y2 is an injective map between diversities (Y1,δ1) and (Y2,δ2) such that δ1(A)=δ2(π(A)) for all A∈𝒫fin(Y1). A  isomorphism is a surjective embedding.Theorem 5.
Every diversity(X,δ) can be embedded in a complete diversity.Proof.
LetX^ be the set of all Cauchy sequences in X. Identify any two sequences {xi}, {yi} which satisfy limn→∞δ({xn,yn})=0 (so X^ is actually a set of equivalence classes). Define the function δ^ from 𝒫fin(X^)→ℝ by
(12)δ^({{xi1},{xi2},…,{xin}})=limN→∞supi1,…,in≥Nδ({xii1,xi22,…,xinn}).
It can then be shown that(X^,δ^) is a complete diversity, and that the map x↦{x,x,x,…} from (X,δ) is an embedding. The proof is an exercise in notation.This completion is dense in the sense that every memberx of X^ has a sequence {xi}⊆X with xi→x in X^ (let {yi} be a representative of x and define xi={y1,y2,…,yi,yi,yi,…}). It also satisfies a universal property analogous to that for metric completion.Theorem 6.
Let(X,δ) be a diversity, and let (X^,δ^) be its completion. Then, for any complete diversity (Y,γ) and any uniformly continuous function f:X→Y, there is a unique uniformly continuous function f^:X^→Y which extends f.Proof.
Let{xi} be a representative sequence of some members of X^, and define f^({xi})=limi→∞f(xi), which is defined and independent of the representative since f is uniformly continuous and Y is complete. To show f^ is uniformly continuous, pick ε>0 and d>0 such that γ(f(A))<ε whenever δ(A)<d for all A∈𝒫fin(X). Then, for all B={{xi1},{xi2},…,{xim}}∈𝒫fin(X^) with δ^(B)<d/2, we have γ(f^(B))=γ({limi→∞f(xin)}n=1m))<ε since for large enough N, δ({f(xNn)}n=1m)<3d/4.
To show uniqueness off^, let g^ be another uniformly continuous function extending f to X^. For all x∈X^, we have {xi}⊂X with xi→x in X^, and by uniform continuity g^(x)=limi→∞f(xi)=f^(x).This is a universal property in the sense that for every complete diversityX^′ extending X and having the property, there is an isomorphism j~:X^′→X^. (Specifically, let j~be the unique uniformly continuous extension of the identity map j:X→X^ to X^′.)


## 3.1. Completeness in Diversities and Metric Spaces

Theorem 2.
Let(X,δ) be a diversity, and let d be its induced metric. If (X,d) is a complete metric space, then (X,δ) is a complete diversity.Proof.
Suppose that(X,d) is complete. Let {xn} be a Cauchy sequence in (X,δ). Then, it is also Cauchy in (X,d), and therefore converges to some element x. We claim that xn→x, in (X,δ). To this end, let ε>0. Then, there exists N, such that  (i)
d(xn,x)<ε for all n>N (since xn→x in (X,d)),(ii)
δ({xn1,xn2,…,xnm})<ε for all ni>N (since {xn} is Cauchy in (X,δ)).
Therefore, for alln1,…,nm>N,
(8)δ({x,xn1,…,xnm})≤δ({x,xn1})+δ({xn1,…,xnm})=d(x,xn1)+δ({xn1,…,xnm})<2ε,that is,xn→x in (X,δ).As mentioned, the set of Cauchy sequences in a diversity may be strictly smaller than the set of Cauchy sequences in the induced metric. For example, let(X,δ) be the Steiner tree diversity on ℝ3, and consider the sets {Gn}n∈ℕ from Theorem 1.Order each setGn somehow and define the sequence {xi} by concatenating them, that is,
(9){xn}=G1G2G3⋯,
which is Cauchy in the induced metric of (X,δ) (since eventually every pair of points is confined to arbitrarily small cubes [0,ε]3). However, it is not Cauchy in (X,δ), since we saw in the proof of Theorem 1 that δ(Gn) becomes arbitrarily large as n→∞. In other words, every tail of {xn} has arbitrarily large finite sets, so {xn} is not Cauchy.In light of this example, it is interesting to know that every complete diversity has a complete induced metric, which is proved with the following lemma.Lemma 3.
Let(X,δ) be a diversity, and let d be its induced metric. Let {xn} be Cauchy in (X,d). Then, it has a subsequence that is Cauchy in (X,δ).Proof.
Define the subsequence{xni} by
(10)ni=min{n:d(xn,xm)<2-i∀m≥n}.Given ε>0, choose N such that 21-N<ε. Then, for all i1≤i2≤⋯≤im greater than N,
(11)δ({xi1,…,xim})≤δ({xi1,xi2})+⋯+δ({xim-1,xim})<12i1+⋯+12im<∑i=N∞1/2i=21-N<ε.That is, {xni} is Cauchy in (X,δ).Theorem 4.
Let(X,δ) be a diversity, and let d be its induced metric. If (X,δ) is a complete diversity, then (X,d) is a complete metric space.Proof.
Let{xn} be a Cauchy sequence in (X,d). Then, by Lemma 3 it has a subsequence {xin} that is Cauchy in (X,δ), which converges to some element x since the diversity is complete (it converges in both (X,δ) and (X,d)).
Then,xn converges to x in (X,d), since for any ε we have d(xn,x)≤d(xn,xim)+d(xim,x)<2ε for m,n large enough.


## 3.2. Completion

In light of the equivalence between metric completeness and diversity completeness, it is perhaps not so surprising that every diversity can be completed in a canonical way. To do so, we require two more definitions from [5]: an  embedding  π:Y1→Y2 is an injective map between diversities (Y1,δ1) and (Y2,δ2) such that δ1(A)=δ2(π(A)) for all A∈𝒫fin(Y1). A  isomorphism is a surjective embedding.Theorem 5.
Every diversity(X,δ) can be embedded in a complete diversity.Proof.
LetX^ be the set of all Cauchy sequences in X. Identify any two sequences {xi}, {yi} which satisfy limn→∞δ({xn,yn})=0 (so X^ is actually a set of equivalence classes). Define the function δ^ from 𝒫fin(X^)→ℝ by
(12)δ^({{xi1},{xi2},…,{xin}})=limN→∞supi1,…,in≥Nδ({xii1,xi22,…,xinn}).
It can then be shown that(X^,δ^) is a complete diversity, and that the map x↦{x,x,x,…} from (X,δ) is an embedding. The proof is an exercise in notation.This completion is dense in the sense that every memberx of X^ has a sequence {xi}⊆X with xi→x in X^ (let {yi} be a representative of x and define xi={y1,y2,…,yi,yi,yi,…}). It also satisfies a universal property analogous to that for metric completion.Theorem 6.
Let(X,δ) be a diversity, and let (X^,δ^) be its completion. Then, for any complete diversity (Y,γ) and any uniformly continuous function f:X→Y, there is a unique uniformly continuous function f^:X^→Y which extends f.Proof.
Let{xi} be a representative sequence of some members of X^, and define f^({xi})=limi→∞f(xi), which is defined and independent of the representative since f is uniformly continuous and Y is complete. To show f^ is uniformly continuous, pick ε>0 and d>0 such that γ(f(A))<ε whenever δ(A)<d for all A∈𝒫fin(X). Then, for all B={{xi1},{xi2},…,{xim}}∈𝒫fin(X^) with δ^(B)<d/2, we have γ(f^(B))=γ({limi→∞f(xin)}n=1m))<ε since for large enough N, δ({f(xNn)}n=1m)<3d/4.
To show uniqueness off^, let g^ be another uniformly continuous function extending f to X^. For all x∈X^, we have {xi}⊂X with xi→x in X^, and by uniform continuity g^(x)=limi→∞f(xi)=f^(x).This is a universal property in the sense that for every complete diversityX^′ extending X and having the property, there is an isomorphism j~:X^′→X^. (Specifically, let j~be the unique uniformly continuous extension of the identity map j:X→X^ to X^′.)


## 4. Conformities

In this section we introduce a generalization of diversities analogous to uniformities, which generalize metric spaces. Uniformities lie between metric spaces and topologies, in the sense that every metric space defines a uniformity, and every uniformity defines a topology (which coincides with the metric topology when the uniformity came from a metric). Uniformities characterize uniform continuity, uniform convergence, and Cauchy sequences, which are not topological concepts.The carry-over from the metric case is natural but nontrivial, since diversities can behave differently on sets of different cardinality. Since this construction is qualitatively different from metric uniformities, it requires a different name. We asked ourselves “what would you call a uniformity that came from a diversity?”, and the answer was clear, a conformity.Throughout this section, we will give the analogous definitions and results for uniformities, using the standard treatment from Kelley [8]. We begin by defining conformities and comparing them to uniformities; we show that just like uniformities, conformities have a countable base if and only if they are generated by some pseudodiversity.We then briefly touch on the problem of completion for conformities.Finally, we define power conformities; from a conformity defined on a setX, we can construct a conformity on 𝒫fin(X) from which pseudodiversities can be considered uniformly continuous functions. We show that every conformity is generated by exactly the set of pseudodiversities which are uniformly continuous from its power conformity to ℝ. This gives an equivalent definition of conformity in terms of pseudodiversities.


### 4.1. Conformities of Diversities

Recall that for(X,d) a metric space, {xn} a sequence in X, that {xn} is Cauchy if and only if for each ε>0 there is some N such that every pair of points (xi,xj) with i>N, j>N has d(xi,xj)<ε.Similarly, letf:X→Y be a function between metric spaces (X,d) and (Y,g). Then, f is uniformly continuous if and only if each ε>0 has a δ>0 such that whenever pairs of points (x,y)∈X×X satisfy d(x,y)<δ, the pairs (f(x),f(y)) satisfy g(f(x),f(y))<ε.A similar characterization of uniform convergence of sequences of functions can be given in terms of pairs of points. From these observations arises the theory of uniformities, which is described in any standard text on analysis (cf. [7, 8]). We briefly describe the theory here. For any set X define a  uniformity on X as a filter 𝒰 on X×X satisfying  (U1)
(x,x)∈U for every x∈X, U∈𝒰.(U2)
IfU∈𝒰, (x,y)∈U, then (y,x)∈U.(U3)
For everyU∈𝒰, there exists some V∈𝒰 with V∘V⊆U, where in general we define
(13)U∘V:={(x,z):(x,y)∈U,(y,z)∈Vforsomey∈X}.In particular, for any pseudometric space(X,d) we can define the  metric uniformity as the filter on X×X defined by
(14)Uε={(x,y):d(x,y)<ε},
for each ε>0. We see from this example that (U1) expresses the requirement that d(x,x)=0 for all x∈X, (U2) expresses symmetry, and (U3) expresses the triangle inequality.Uniform structure can be defined entirely with respect to uniformities. For example, given setsX,Y and uniformities 𝒰,𝒱 on X and Y, respectively, we can call a function f:X→Yuniformly continuous if f-1(V)∈𝒰 for every V∈𝒱. (Here f acts on members of V componentwise.) A sequence {xn}⊂X is  Cauchy if for every U∈𝒰, there is some N such that pairs of elements (xi,xj) of {xn} are in U whenever i,j>N. It is not hard to see that for metric uniformities, these definitions coincide with the ordinary ones for metric spaces.To abstract the uniform structure of diversities, uniformities are clearly insufficient. For one thing, since diversities map finite sets rather than pairs, we should seek a filter on𝒫fin(X) rather than X×X. Then symmetry is no longer required, but now monotonicity is. Finally, it is not meaningful to compose finite sets as in (U3), so we will need a diferent way to express an analogue of the triangle inequality.Putting all this together, we define aconformity𝒞 on X as a filter on 𝒫fin(X) satisfying  (C1)
{x}∈C for every x∈X, C∈𝒞.(C2)
For everyC∈𝒞, whenever A∈C and B⊆A, we have B∈C.(C3)
For everyC∈𝒞, there exists some D∈𝒞 with D∘D⊆C, where in general we define
(15)U∘V:={u∪v:u∈U,v∈Vandu∩v≠⌀}.Often the term conformity is also used to refer to the pair (X,𝒞).An observation that will be necessary later (one which also holds for uniformities) is that for anyD∈𝒞, (D∘D)∘D=D∘(D∘D), so that D∘D∘D is defined unambiguously. To estimate the size of this, we also note that D∘D∘D⊆(D∘D)∘(D∘D).As in the metric case, there is a canonical way to generate a conformity from a diversity; ifδ is a pseudodiversity on X, we have the conformity generated by the sets
(16)Cε={A:δ(A)≤ε}=δ-1[0,ε],
for each ε>0. (This is equivalent to the one using strict inequalities, but typographically nicer.)As in the metric case, uniform structure can be defined on conformities in a way that generalizes that of diversities, let(X,𝒞) and (Y,𝒟) be conformities. Then, a function f is  uniformly continuous from X to Y if for all D∈𝒟, the set {f-1(d):d∈D} is in 𝒞. A sequence {xn} on X is a  Cauchy sequence if for all C∈𝒞, 𝒫fin({xn}n≥N)⊆C for some integer N. For conformities generated from diversities in the above way, these definitions coincide with those given in the previous section.More generally, given a collection of pseudodiversities{δα}α∈𝒜, we can generate a conformity from the sets {δα-1[0,ε]}α∈𝒜,ε>0. We, therefore, seek a characterization of conformities in terms of the diversities which generate them. (In a later section, we will see that all conformities can be described in this way, so that we can define conformities in terms of such sets.) We begin by stating a result from Kelley [8] along with a summary of his proof.Theorem 7.
A uniformity is generated by a single pseudometric if and only if it has a countable base.The standard proof of this theorem goes as follows: it is obvious that any uniformity generated by a pseudometric has a countable base. Conversely, if there exists a countable base for a uniformity onX, there exists a countable base {Un}n∈ℕ for which the following argument holds. Define the function f(x,y)=2-n, where n=sup{i:(x,y)∈Ui}. This generates the uniformity but does not satisfy the triangle inequality, so define
(17)d(x,y)=inf∑i=1m-1‍f(xi,xi+1),
where the infimum is taken over all sequences {xi}i=1m with x1=x and xm=y. This clearly satisfies the triangle inequality, so it just remains to be shown that d generates the uniformity. This is done by proving that d(x,y)≤f(x,y)≤2d(x,y), which follows from technical constraints on {Un}.Given a conformity with a countable base{Cn} on a set X, one might try to translate this proof directly, define a function f(A):𝒫fin(X)→ℝ by f(A)=sup{i:A∈Ci}, then somehow tweak f to (a) satisfy the triangle inequality and (b) generate the same conformity as f. However, it appears that any direct analogue to the “infimum over all paths” strategy used in the metric case (there are several) cannot satisfy both (a) and (b) simultaneously.Nonetheless, the result is true, which is the content of the next theorem.Lemma 8.
Let(X,𝒞) have a countable base. Then, it has a countable base {Cn} satisfyingC0=𝒫fin(X), Ci∘Ci∘Ci⊆Ci-1 for i>0.Proof.
Let{Vn} be a countable base for 𝒞. Define W0=𝒫fin(X), Wn=Vn∩Wn-1. Then, {Wn} is a nested countable base. Finally, choose {Cn} as Ci=Wni, where ni are chosen inductively as n0=0, then (Wni∘Wni)∘(Wni∘Wni)⊆Wni-1.Theorem 9.
Let(X,𝒞) be a conformity. There exists, a pseudodiversity δ which generates 𝒞 if and only if 𝒞 has a countable base.Proof.
Ifδ exists, the sets {C1/n}n∈ℕ are our base.
Conversely, let{Cn}1∞ be a base for 𝒞 satisfying C0=𝒫fin(X) and Ci∘Ci∘Ci⊆Ci-1 for i>0. Define δ′ on 𝒫fin(X) by
(18)δ′(A)={0,A∈Cn∀n,2-k,A∈Cnfor0≤n≤k,butA∉Ck+1.
Notice that for k≥0,
(19)δ′-1([0,2-k])=Ck
and that δ′ is monotonic; by (C2), if A⊆B, then A∈Cn whenever B∈Cn.
Define a  chain as a sequence{Ai}i=1n in 𝒫fin(X) with Ai∩Ai-1≠⌀ for i=2,…,n. Define a  cycle as a chain with A1∩An≠⌀. Write
(20)δ¯(A)=infchainscoveringA∑i=1n‍δ′(Ai),δ(A)=infcyclescoveringA∑i=1n‍δ′(Ai).
Notice thatδ(⌀)=δ¯(⌀)=0.
We claim thatδ is our desired pseudodiversity, since the sets (δ′)-1[0,ε] generate the conformity, and δ≤δ′≤4δ. We prove this in three stages.(S1)
First of all,δ is a pseudodiversity. By (C1), for every x∈X, n∈𝒩, and {x}∈Cn so that δ′({x})=0. Also, {x} is a cycle covering itself, so δ({x})=0.The triangle equality also holds; letε>0, A,C∈𝒫fin(X), and B∈𝒫fin(X) be nonempty. Choose cycles {Ai}1n and {Bi}1m covering A∪B and B∪C, respectively, and for which
(21)∑i=1nδ′(Ai)≤δ(A∪B)+ε,∑i=1mδ′(Bi)≤δ(B∪C)+ε.Then,{Ai}1n∪{Bi}1m forms a cycle (after reordering) covering A∪C, so
(22)δ(A∪C)≤∑i=1nδ′(Ai)+∑i=1mδ′(Bi)≤δ(A∪B)+δ(B∪C)+2ε.(S2)
Next, we notice that
(i)
every cycle is a chain, soδ≤δ¯.(ii)
If{A1,…,An-1,An} is a chain, then {A1,…,An-1,An,An-1,…,A1} is a cycle—and the sum of δ′ over this cycle is less than twice the sum of δ′ over the original chain. We conclude that
(23)δ≤δ¯≤2δ.(S3)
Finally, we claim thatδ¯≤δ′≤2δ¯. This combined with (23) will give the main result.Trivially,δ¯≤δ′. For the other inequality, choose A∈𝒫fin(X). Our strategy is to induct on the greatest integer N such that δ¯(A)<2-N.The caseN=0 is easy, because then δ′≤1≤2δ¯ (this also covers the case δ¯(A)=1, which is not covered by the induction). When N>0, we can choose positive ε less than (2-N-δ¯(A)), and a chain {Ai}1n with
(24)∑i=1nδ′(Ai)<δ¯(A)+ε<2-N.
Ifn=1, we have δ′(A)≤δ′(A1)<2-N<2δ¯(A). Otherwise, there is k<n such that
(25)∑i=1k-1δ′(Ai)≤δ¯(A)2,∑i=k+1nδ′(Ai)≤δ¯(A)2.
Since {Ai}1k-1 and {Ai}k+1n are chains whose sum under δ′ is less than half that of {Ai}1n, the inductive hypothesis applies to them and we may write
(26)δ′(A1∪⋯∪Ak-1)≤2δ¯(A1∪⋯∪Ak-1)inductivehypothesis≤2∑i=1k-1δ′(Ai)definitionofδ¯≤δ¯(A)by(25)<2-N.
Similarly, δ′(Ak+1∪⋯∪An)<2-N, and δ′(Ak)<2-N by (24). So,
(27)(A1∪⋯∪Ak-1)∈CN+1,Ak∈CN+1,(Ak+1∪⋯∪An)∈CN+1.
Our double-composition hypothesis gives
(28)(A1∪⋯∪Ak-1)∪Ak∪(Ak+1∪⋯∪An)∈CN.
And by monotonicity of δ′,
(29)δ′(A)≤δ′(A1∪⋯∪An)≤2-N≤2δ¯(A).This characterizes the conformities generated by single pseudodiversities. Later, we will describe every conformity in terms of the pseudodiversities that generate them.


### 4.2. Induced Uniformities and Completeness

Given a conformity𝒞, we define its  induced uniformity as the uniformity generated by the sets
(30)UC={(x,y):{x,y}∈C},
for every C∈𝒞. It is straightforward to show that this is a uniformity; since every singleton {x} is in every C∈𝒞, we have every pair (x,x) in every generator of the induced uniformity, proving (U1). Since {x,y}={y,x}, we have (U2). Finally, (U3) follows from the observation that whenever {x,y}∈C∈𝒞 and {y,z}∈D∈𝒞, the set D∘D∈𝒞 contains {x,y,z}. Then, {x,z}∈D∘C by (C2). In other words, if C∘D⊆E in the conformity, then UC∘UD⊆UE in the induced uniformity. Thus, (U3) is implied by (C3).Theorem 10.
LetX be a set, {δA}A∈𝒜 be a family of diversities which generate a conformity 𝒞. For each δA, write dA for its induced metric. Then, the uniformity generated by the metrics {dA}A∈𝒜 is exactly the induced uniformity of 𝒞.Proof.
Denote by𝒰d the uniformity generated by {dA}A∈𝒜, and by 𝒰c the uniformity induced by 𝒞. A base for 𝒞 is
(31)Cε,A={F:δA(F)<ε},
where ε ranges over ℝ+ and A ranges over 𝒜. Then, a base for 𝒞 is
(32)UCε,A={(x,y):δA({x,y})<ε}={(x,y):dA(x,y)<ε}.
But this is just the canonical base for 𝒰d!Corollary 11.
Let(X,𝒞) be a conformity. Then, 𝒞 has a countable base if and only if its induced uniformity does.Proof.
By Theorem9,𝒞 has a countable base if and only if it is generated by a single pseudodiversity; by Theorem 10 this occurs if and only if the induced uniformity is generated by a single pseudometric. A standard result [7, 8] shows that uniformities with countable bases are exactly those generated by single pseudometrics.Next, we give some standard definitions. For a uniform space(X,𝒰), the  uniform topology of 𝒰 on X is the smallest topology containing the sets
(33)N(x,U)={y:(x,y)∈U},
for all x∈X, U∈𝒰. Notice that if 𝒰 is generated by a pseudometric, this coincides with the pseudometric topology.With the same space(X,𝒰), we call a filter ℱ on X Cauchy if for every U∈𝒰, there is some F∈ℱ with F×F⊆U. We say that ℱ  converges to some x∈X if every neighborhood of x (in the uniform topology) is in ℱ. We then call a uniformity  complete if every Cauchy filter converges. It can be shown that a metric space is complete if and only if its generated uniformity is, and that every uniformity can be embedded minimally (i.e., satisfying a universal property with respect to uniformly continuous maps) in a complete uniformity [7, 8].The analogous definitions for conformities are as follows.LetF be a filter on X. If for all C∈𝒞, there exists f∈F with 𝒫fin(f)⊆C, then F is a  Cauchy filter. If x∈X and for all C∈𝒞 there exist f∈F with 𝒫fin(f)⊆{A:A∪{x}∈C}, then F  converges to x. Finally, if every Cauchy filter converges to some point in X, we say 𝒞 is  complete.Theorem 12.
A pseudodiversity(X,δ) is complete if and only if its conformity 𝒞 is.Proof.
Suppose(X,δ) is complete and let F be a Cauchy filter on X. Then, for every ε>0, there is some fε∈F so that 𝒫fin(fε)⊆{A:δ(A)<ε}. Take some sequence εn→0, and define the sets gn⊆X by g1=fε1, gn=fεn∩gεn-1 for n>1.
Choosexn∈gn for each n to form a Cauchy sequence {xn}, with some limit x. For any ε>0, find an integer N so that εn<ε and δ({xn,x})<ε for all n≥N. Then, if a∈𝒫fin(fεn), so is a∪{xn}, so that δ(a∪{x})≤δ(a∪{xn})+δ({xn,x})<2ε. We conclude that F converges to x.
Conversely, suppose that every Cauchy filter converges in𝒞, and let {xn} be a Cauchy sequence in (X,δ). Choose the sets FN={xn}N∞. These sets generate a Cauchy filter with some limit x. It is clear that xn→x.For any conformity(X,𝒞) generated by a diversity, the conformity is complete if and only if the diversity is. The diversity is complete if and only if its induced metric is, which in turn is complete if and only if its uniformity is [7, 8]; thus completeness of the conformity is equivalent to completeness of its induced uniformity. In fact, this is true in general, as the next theorem shows.Theorem 13.
Let(X,𝒞) be a conformity with complete induced uniformity 𝒰. Then, 𝒞 is complete.Proof.
Suppose that𝒰 is complete, and let ℱ be a Cauchy filter with respect to 𝒞. Then, ℱ is also Cauchy with respect to 𝒰, since for all C∈𝒞, we have {{x,y}:x,y∈F}⊆𝒫fin(F)⊆C for some F∈ℱ; then F×F⊆UC. Thus, ℱ converges in 𝒰 to some element x, and we claim that it also converges to x in 𝒞. To this end, fix C∈𝒞. Choose D∈𝒞 so that D∘D⊆C and F∈ℱ so that (a) y∈F whenever (x,y)∈UD and (b) 𝒫fin(F)⊆D. Then, for all A∈𝒫fin(F), A∪{x}∈C. (If A=⌀, A∪{x}∈C trivially. Otherwise, pick y∈A, and we will have A∈D and {x,y}∈D, so that A∪{x,y}=A∪{x}∈C.)We end this section with two open questions as follows.(1)
Does the converse to Theorem13 holds; that is, if a conformity (X,𝒞) is complete, must its induced uniformity be?(2)
We saw in Section3.2 that for any diversity (X,δ), it is possible to embed X in a complete diversity which was universal, meaning that any uniformly continuous map from X to a complete diversity is factored through the embedding. It is shown in [8] that every uniformity can be embedded in a complete uniformity. This embedding is also universal.Is there a notion of universal completion for conformities?


### 4.3. Diversities of Conformities

Not every conformity has a countable base. For example, letX be the space of functions f:[0,1]→[0,1], and consider the “pointwise convergence” conformity generated by the sets
(34)Cεx={{f1,…,fn}:diam({f1(x),…,fn(x)})<ε}
for every ε>0, x∈[0,1]. This conformity has no countable base by Corollary 11, since its induced uniformity does not have a countable base [10]. Thus, by Theorem 9 it is not generated by any pseudodiversity.In this section, we will show that every conformity is generated by the collection of pseudodiversities which are uniformly continuous with respect to it, in an appropriate sense. In the case of uniformities, this is done by constructing a so-called product uniformity; given a uniformity on a setX, the product uniformity is constructed on X×X. Then, a given pseudometric d may or may not be uniformly continuous from the product uniformity to the Euclidean uniformity on ℝ. It can be proven [7, 8] that a uniformity 𝒰 is exactly the uniformity generated by all pseudometrics which are uniformly continuous from its product uniformity.Since pseudodiversities are functions on finite sets rather than pairs, given a conformity on a setX we seek a conformity on 𝒫fin(X) from which to judge uniform continuity of pseudodiversities.In fact, such a conformity exists for which we can prove the same result; given a conformity(X,𝒞), define the  power conformity𝒞P as the conformity on 𝒫fin(X) generated by the sets
(35)Cu={{A1,…,An}:n≤1or⋃i=1nAi∈u},
where u ranges over all members of 𝒞.Lemma 14.
A power conformity is a conformity.Proof.
First, theCus form a filter base since Cu∩Cv=Cu∩v∈𝒞P for any Cu, Cv∈𝒞P. For all A∈𝒫fin(X), {A} is in every Cu by definition. It is immediate that whenever {Ai} is in Cu, so is every subset of {Ai}.
Finally, everyCu has a Cv with Cv∘Cv⊆Cu; choose v with v∘v⊆u in 𝒞. If {Ai}i=1n, {Bi}i=1m are in Cv with some Ai equal to some Bj, then (a) m≤1 and n≤1, so their union has at most one element and therefore must lie in Cu, (b) exactly one of m≤1 or n≤1, in which case one of the sets is a subset of the other, so their union lies in v (and therefore u), or (c) m>1 and n>1, so the sets ⋃i=1n‍Ai and ⋃i=1m‍Bi are sets in v with nonempty intersection. Then, since v∘v⊆u, their union lies in u. In every case we have {Ai}i=1n∪{Bi}i=1m∈Cu.Theorem 15.
Let(X,𝒞) be a conformity. A pseudodiversity δ is uniformly continuous from 𝒞P to (ℝ,diam) if and only if the set Vε={A:δ(A)<ε} is in 𝒞 for each ε>0.Proof.
First, suppose that everyVε is in 𝒞. For each ε>0, the set
(36)Cu={{A1,…,An}:n≤1orδ(⋃i=1nAi)<ε}
is in𝒞P (notice that it has the form of (35) with u=Vε). Let {A,B}∈Cε; then δ(A)≤δ(A∪B)<ε and similarly δ(B)<ε. Thus, |δ(A)-δ(B)|<ε, so δ is uniformly continuous.
Conversely, suppose thatδ is uniformly continuous. Then, for any ε>0, there exists some u∈𝒞, such that every {A1,…,An}∈Cu satisfies supi,j|δ(Ai)-δ(Aj)|<ε. Since for any A∈u, the set {A,⌀} lies in Cu, this implies that δ(A)<ε, which in turn implies that u⊆Vε, which finally implies that Vε is in 𝒞.Corollary 16.
Every conformity is generated by the pseudodiversities which are uniformly continuous from its power conformity to(ℝ,diam).Proof.
Let𝒞 be a conformity, 𝒟 be the conformity generated by the pseudodiversities which are uniformly continuous from the power conformity to (ℝ,diam). By Theorem 9, we have 𝒞⊆𝒟, since every member u of 𝒞 is in a countably-based subconformity of 𝒞. (Take u0=u, ui such that ui∘ui⊆ui-1, i>0 as a base.)
Then, by Theorem15, every pseudodiversity which is uniformly continuous generates a subset of 𝒞; that is, 𝒟⊆𝒞.We saw at the beginning of this section that some conformities can be generated by sets of the form{δα-1[0,ε]}α∈𝒜,ε>0, where 𝒜 is some collection of pseudodiversities, ε>0. What we have just shown is that all conformities are generated in this way, so that we may define a conformity as a filter generated in this way by some collection of diversities.


## 4.1. Conformities of Diversities

Recall that for(X,d) a metric space, {xn} a sequence in X, that {xn} is Cauchy if and only if for each ε>0 there is some N such that every pair of points (xi,xj) with i>N, j>N has d(xi,xj)<ε.Similarly, letf:X→Y be a function between metric spaces (X,d) and (Y,g). Then, f is uniformly continuous if and only if each ε>0 has a δ>0 such that whenever pairs of points (x,y)∈X×X satisfy d(x,y)<δ, the pairs (f(x),f(y)) satisfy g(f(x),f(y))<ε.A similar characterization of uniform convergence of sequences of functions can be given in terms of pairs of points. From these observations arises the theory of uniformities, which is described in any standard text on analysis (cf. [7, 8]). We briefly describe the theory here. For any set X define a  uniformity on X as a filter 𝒰 on X×X satisfying  (U1)
(x,x)∈U for every x∈X, U∈𝒰.(U2)
IfU∈𝒰, (x,y)∈U, then (y,x)∈U.(U3)
For everyU∈𝒰, there exists some V∈𝒰 with V∘V⊆U, where in general we define
(13)U∘V:={(x,z):(x,y)∈U,(y,z)∈Vforsomey∈X}.In particular, for any pseudometric space(X,d) we can define the  metric uniformity as the filter on X×X defined by
(14)Uε={(x,y):d(x,y)<ε},
for each ε>0. We see from this example that (U1) expresses the requirement that d(x,x)=0 for all x∈X, (U2) expresses symmetry, and (U3) expresses the triangle inequality.Uniform structure can be defined entirely with respect to uniformities. For example, given setsX,Y and uniformities 𝒰,𝒱 on X and Y, respectively, we can call a function f:X→Yuniformly continuous if f-1(V)∈𝒰 for every V∈𝒱. (Here f acts on members of V componentwise.) A sequence {xn}⊂X is  Cauchy if for every U∈𝒰, there is some N such that pairs of elements (xi,xj) of {xn} are in U whenever i,j>N. It is not hard to see that for metric uniformities, these definitions coincide with the ordinary ones for metric spaces.To abstract the uniform structure of diversities, uniformities are clearly insufficient. For one thing, since diversities map finite sets rather than pairs, we should seek a filter on𝒫fin(X) rather than X×X. Then symmetry is no longer required, but now monotonicity is. Finally, it is not meaningful to compose finite sets as in (U3), so we will need a diferent way to express an analogue of the triangle inequality.Putting all this together, we define aconformity𝒞 on X as a filter on 𝒫fin(X) satisfying  (C1)
{x}∈C for every x∈X, C∈𝒞.(C2)
For everyC∈𝒞, whenever A∈C and B⊆A, we have B∈C.(C3)
For everyC∈𝒞, there exists some D∈𝒞 with D∘D⊆C, where in general we define
(15)U∘V:={u∪v:u∈U,v∈Vandu∩v≠⌀}.Often the term conformity is also used to refer to the pair (X,𝒞).An observation that will be necessary later (one which also holds for uniformities) is that for anyD∈𝒞, (D∘D)∘D=D∘(D∘D), so that D∘D∘D is defined unambiguously. To estimate the size of this, we also note that D∘D∘D⊆(D∘D)∘(D∘D).As in the metric case, there is a canonical way to generate a conformity from a diversity; ifδ is a pseudodiversity on X, we have the conformity generated by the sets
(16)Cε={A:δ(A)≤ε}=δ-1[0,ε],
for each ε>0. (This is equivalent to the one using strict inequalities, but typographically nicer.)As in the metric case, uniform structure can be defined on conformities in a way that generalizes that of diversities, let(X,𝒞) and (Y,𝒟) be conformities. Then, a function f is  uniformly continuous from X to Y if for all D∈𝒟, the set {f-1(d):d∈D} is in 𝒞. A sequence {xn} on X is a  Cauchy sequence if for all C∈𝒞, 𝒫fin({xn}n≥N)⊆C for some integer N. For conformities generated from diversities in the above way, these definitions coincide with those given in the previous section.More generally, given a collection of pseudodiversities{δα}α∈𝒜, we can generate a conformity from the sets {δα-1[0,ε]}α∈𝒜,ε>0. We, therefore, seek a characterization of conformities in terms of the diversities which generate them. (In a later section, we will see that all conformities can be described in this way, so that we can define conformities in terms of such sets.) We begin by stating a result from Kelley [8] along with a summary of his proof.Theorem 7.
A uniformity is generated by a single pseudometric if and only if it has a countable base.The standard proof of this theorem goes as follows: it is obvious that any uniformity generated by a pseudometric has a countable base. Conversely, if there exists a countable base for a uniformity onX, there exists a countable base {Un}n∈ℕ for which the following argument holds. Define the function f(x,y)=2-n, where n=sup{i:(x,y)∈Ui}. This generates the uniformity but does not satisfy the triangle inequality, so define
(17)d(x,y)=inf∑i=1m-1‍f(xi,xi+1),
where the infimum is taken over all sequences {xi}i=1m with x1=x and xm=y. This clearly satisfies the triangle inequality, so it just remains to be shown that d generates the uniformity. This is done by proving that d(x,y)≤f(x,y)≤2d(x,y), which follows from technical constraints on {Un}.Given a conformity with a countable base{Cn} on a set X, one might try to translate this proof directly, define a function f(A):𝒫fin(X)→ℝ by f(A)=sup{i:A∈Ci}, then somehow tweak f to (a) satisfy the triangle inequality and (b) generate the same conformity as f. However, it appears that any direct analogue to the “infimum over all paths” strategy used in the metric case (there are several) cannot satisfy both (a) and (b) simultaneously.Nonetheless, the result is true, which is the content of the next theorem.Lemma 8.
Let(X,𝒞) have a countable base. Then, it has a countable base {Cn} satisfyingC0=𝒫fin(X), Ci∘Ci∘Ci⊆Ci-1 for i>0.Proof.
Let{Vn} be a countable base for 𝒞. Define W0=𝒫fin(X), Wn=Vn∩Wn-1. Then, {Wn} is a nested countable base. Finally, choose {Cn} as Ci=Wni, where ni are chosen inductively as n0=0, then (Wni∘Wni)∘(Wni∘Wni)⊆Wni-1.Theorem 9.
Let(X,𝒞) be a conformity. There exists, a pseudodiversity δ which generates 𝒞 if and only if 𝒞 has a countable base.Proof.
Ifδ exists, the sets {C1/n}n∈ℕ are our base.
Conversely, let{Cn}1∞ be a base for 𝒞 satisfying C0=𝒫fin(X) and Ci∘Ci∘Ci⊆Ci-1 for i>0. Define δ′ on 𝒫fin(X) by
(18)δ′(A)={0,A∈Cn∀n,2-k,A∈Cnfor0≤n≤k,butA∉Ck+1.
Notice that for k≥0,
(19)δ′-1([0,2-k])=Ck
and that δ′ is monotonic; by (C2), if A⊆B, then A∈Cn whenever B∈Cn.
Define a  chain as a sequence{Ai}i=1n in 𝒫fin(X) with Ai∩Ai-1≠⌀ for i=2,…,n. Define a  cycle as a chain with A1∩An≠⌀. Write
(20)δ¯(A)=infchainscoveringA∑i=1n‍δ′(Ai),δ(A)=infcyclescoveringA∑i=1n‍δ′(Ai).
Notice thatδ(⌀)=δ¯(⌀)=0.
We claim thatδ is our desired pseudodiversity, since the sets (δ′)-1[0,ε] generate the conformity, and δ≤δ′≤4δ. We prove this in three stages.(S1)
First of all,δ is a pseudodiversity. By (C1), for every x∈X, n∈𝒩, and {x}∈Cn so that δ′({x})=0. Also, {x} is a cycle covering itself, so δ({x})=0.The triangle equality also holds; letε>0, A,C∈𝒫fin(X), and B∈𝒫fin(X) be nonempty. Choose cycles {Ai}1n and {Bi}1m covering A∪B and B∪C, respectively, and for which
(21)∑i=1nδ′(Ai)≤δ(A∪B)+ε,∑i=1mδ′(Bi)≤δ(B∪C)+ε.Then,{Ai}1n∪{Bi}1m forms a cycle (after reordering) covering A∪C, so
(22)δ(A∪C)≤∑i=1nδ′(Ai)+∑i=1mδ′(Bi)≤δ(A∪B)+δ(B∪C)+2ε.(S2)
Next, we notice that
(i)
every cycle is a chain, soδ≤δ¯.(ii)
If{A1,…,An-1,An} is a chain, then {A1,…,An-1,An,An-1,…,A1} is a cycle—and the sum of δ′ over this cycle is less than twice the sum of δ′ over the original chain. We conclude that
(23)δ≤δ¯≤2δ.(S3)
Finally, we claim thatδ¯≤δ′≤2δ¯. This combined with (23) will give the main result.Trivially,δ¯≤δ′. For the other inequality, choose A∈𝒫fin(X). Our strategy is to induct on the greatest integer N such that δ¯(A)<2-N.The caseN=0 is easy, because then δ′≤1≤2δ¯ (this also covers the case δ¯(A)=1, which is not covered by the induction). When N>0, we can choose positive ε less than (2-N-δ¯(A)), and a chain {Ai}1n with
(24)∑i=1nδ′(Ai)<δ¯(A)+ε<2-N.
Ifn=1, we have δ′(A)≤δ′(A1)<2-N<2δ¯(A). Otherwise, there is k<n such that
(25)∑i=1k-1δ′(Ai)≤δ¯(A)2,∑i=k+1nδ′(Ai)≤δ¯(A)2.
Since {Ai}1k-1 and {Ai}k+1n are chains whose sum under δ′ is less than half that of {Ai}1n, the inductive hypothesis applies to them and we may write
(26)δ′(A1∪⋯∪Ak-1)≤2δ¯(A1∪⋯∪Ak-1)inductivehypothesis≤2∑i=1k-1δ′(Ai)definitionofδ¯≤δ¯(A)by(25)<2-N.
Similarly, δ′(Ak+1∪⋯∪An)<2-N, and δ′(Ak)<2-N by (24). So,
(27)(A1∪⋯∪Ak-1)∈CN+1,Ak∈CN+1,(Ak+1∪⋯∪An)∈CN+1.
Our double-composition hypothesis gives
(28)(A1∪⋯∪Ak-1)∪Ak∪(Ak+1∪⋯∪An)∈CN.
And by monotonicity of δ′,
(29)δ′(A)≤δ′(A1∪⋯∪An)≤2-N≤2δ¯(A).This characterizes the conformities generated by single pseudodiversities. Later, we will describe every conformity in terms of the pseudodiversities that generate them.


## 4.2. Induced Uniformities and Completeness

Given a conformity𝒞, we define its  induced uniformity as the uniformity generated by the sets
(30)UC={(x,y):{x,y}∈C},
for every C∈𝒞. It is straightforward to show that this is a uniformity; since every singleton {x} is in every C∈𝒞, we have every pair (x,x) in every generator of the induced uniformity, proving (U1). Since {x,y}={y,x}, we have (U2). Finally, (U3) follows from the observation that whenever {x,y}∈C∈𝒞 and {y,z}∈D∈𝒞, the set D∘D∈𝒞 contains {x,y,z}. Then, {x,z}∈D∘C by (C2). In other words, if C∘D⊆E in the conformity, then UC∘UD⊆UE in the induced uniformity. Thus, (U3) is implied by (C3).Theorem 10.
LetX be a set, {δA}A∈𝒜 be a family of diversities which generate a conformity 𝒞. For each δA, write dA for its induced metric. Then, the uniformity generated by the metrics {dA}A∈𝒜 is exactly the induced uniformity of 𝒞.Proof.
Denote by𝒰d the uniformity generated by {dA}A∈𝒜, and by 𝒰c the uniformity induced by 𝒞. A base for 𝒞 is
(31)Cε,A={F:δA(F)<ε},
where ε ranges over ℝ+ and A ranges over 𝒜. Then, a base for 𝒞 is
(32)UCε,A={(x,y):δA({x,y})<ε}={(x,y):dA(x,y)<ε}.
But this is just the canonical base for 𝒰d!Corollary 11.
Let(X,𝒞) be a conformity. Then, 𝒞 has a countable base if and only if its induced uniformity does.Proof.
By Theorem9,𝒞 has a countable base if and only if it is generated by a single pseudodiversity; by Theorem 10 this occurs if and only if the induced uniformity is generated by a single pseudometric. A standard result [7, 8] shows that uniformities with countable bases are exactly those generated by single pseudometrics.Next, we give some standard definitions. For a uniform space(X,𝒰), the  uniform topology of 𝒰 on X is the smallest topology containing the sets
(33)N(x,U)={y:(x,y)∈U},
for all x∈X, U∈𝒰. Notice that if 𝒰 is generated by a pseudometric, this coincides with the pseudometric topology.With the same space(X,𝒰), we call a filter ℱ on X Cauchy if for every U∈𝒰, there is some F∈ℱ with F×F⊆U. We say that ℱ  converges to some x∈X if every neighborhood of x (in the uniform topology) is in ℱ. We then call a uniformity  complete if every Cauchy filter converges. It can be shown that a metric space is complete if and only if its generated uniformity is, and that every uniformity can be embedded minimally (i.e., satisfying a universal property with respect to uniformly continuous maps) in a complete uniformity [7, 8].The analogous definitions for conformities are as follows.LetF be a filter on X. If for all C∈𝒞, there exists f∈F with 𝒫fin(f)⊆C, then F is a  Cauchy filter. If x∈X and for all C∈𝒞 there exist f∈F with 𝒫fin(f)⊆{A:A∪{x}∈C}, then F  converges to x. Finally, if every Cauchy filter converges to some point in X, we say 𝒞 is  complete.Theorem 12.
A pseudodiversity(X,δ) is complete if and only if its conformity 𝒞 is.Proof.
Suppose(X,δ) is complete and let F be a Cauchy filter on X. Then, for every ε>0, there is some fε∈F so that 𝒫fin(fε)⊆{A:δ(A)<ε}. Take some sequence εn→0, and define the sets gn⊆X by g1=fε1, gn=fεn∩gεn-1 for n>1.
Choosexn∈gn for each n to form a Cauchy sequence {xn}, with some limit x. For any ε>0, find an integer N so that εn<ε and δ({xn,x})<ε for all n≥N. Then, if a∈𝒫fin(fεn), so is a∪{xn}, so that δ(a∪{x})≤δ(a∪{xn})+δ({xn,x})<2ε. We conclude that F converges to x.
Conversely, suppose that every Cauchy filter converges in𝒞, and let {xn} be a Cauchy sequence in (X,δ). Choose the sets FN={xn}N∞. These sets generate a Cauchy filter with some limit x. It is clear that xn→x.For any conformity(X,𝒞) generated by a diversity, the conformity is complete if and only if the diversity is. The diversity is complete if and only if its induced metric is, which in turn is complete if and only if its uniformity is [7, 8]; thus completeness of the conformity is equivalent to completeness of its induced uniformity. In fact, this is true in general, as the next theorem shows.Theorem 13.
Let(X,𝒞) be a conformity with complete induced uniformity 𝒰. Then, 𝒞 is complete.Proof.
Suppose that𝒰 is complete, and let ℱ be a Cauchy filter with respect to 𝒞. Then, ℱ is also Cauchy with respect to 𝒰, since for all C∈𝒞, we have {{x,y}:x,y∈F}⊆𝒫fin(F)⊆C for some F∈ℱ; then F×F⊆UC. Thus, ℱ converges in 𝒰 to some element x, and we claim that it also converges to x in 𝒞. To this end, fix C∈𝒞. Choose D∈𝒞 so that D∘D⊆C and F∈ℱ so that (a) y∈F whenever (x,y)∈UD and (b) 𝒫fin(F)⊆D. Then, for all A∈𝒫fin(F), A∪{x}∈C. (If A=⌀, A∪{x}∈C trivially. Otherwise, pick y∈A, and we will have A∈D and {x,y}∈D, so that A∪{x,y}=A∪{x}∈C.)We end this section with two open questions as follows.(1)
Does the converse to Theorem13 holds; that is, if a conformity (X,𝒞) is complete, must its induced uniformity be?(2)
We saw in Section3.2 that for any diversity (X,δ), it is possible to embed X in a complete diversity which was universal, meaning that any uniformly continuous map from X to a complete diversity is factored through the embedding. It is shown in [8] that every uniformity can be embedded in a complete uniformity. This embedding is also universal.Is there a notion of universal completion for conformities?


## 4.3. Diversities of Conformities

Not every conformity has a countable base. For example, letX be the space of functions f:[0,1]→[0,1], and consider the “pointwise convergence” conformity generated by the sets
(34)Cεx={{f1,…,fn}:diam({f1(x),…,fn(x)})<ε}
for every ε>0, x∈[0,1]. This conformity has no countable base by Corollary 11, since its induced uniformity does not have a countable base [10]. Thus, by Theorem 9 it is not generated by any pseudodiversity.In this section, we will show that every conformity is generated by the collection of pseudodiversities which are uniformly continuous with respect to it, in an appropriate sense. In the case of uniformities, this is done by constructing a so-called product uniformity; given a uniformity on a setX, the product uniformity is constructed on X×X. Then, a given pseudometric d may or may not be uniformly continuous from the product uniformity to the Euclidean uniformity on ℝ. It can be proven [7, 8] that a uniformity 𝒰 is exactly the uniformity generated by all pseudometrics which are uniformly continuous from its product uniformity.Since pseudodiversities are functions on finite sets rather than pairs, given a conformity on a setX we seek a conformity on 𝒫fin(X) from which to judge uniform continuity of pseudodiversities.In fact, such a conformity exists for which we can prove the same result; given a conformity(X,𝒞), define the  power conformity𝒞P as the conformity on 𝒫fin(X) generated by the sets
(35)Cu={{A1,…,An}:n≤1or⋃i=1nAi∈u},
where u ranges over all members of 𝒞.Lemma 14.
A power conformity is a conformity.Proof.
First, theCus form a filter base since Cu∩Cv=Cu∩v∈𝒞P for any Cu, Cv∈𝒞P. For all A∈𝒫fin(X), {A} is in every Cu by definition. It is immediate that whenever {Ai} is in Cu, so is every subset of {Ai}.
Finally, everyCu has a Cv with Cv∘Cv⊆Cu; choose v with v∘v⊆u in 𝒞. If {Ai}i=1n, {Bi}i=1m are in Cv with some Ai equal to some Bj, then (a) m≤1 and n≤1, so their union has at most one element and therefore must lie in Cu, (b) exactly one of m≤1 or n≤1, in which case one of the sets is a subset of the other, so their union lies in v (and therefore u), or (c) m>1 and n>1, so the sets ⋃i=1n‍Ai and ⋃i=1m‍Bi are sets in v with nonempty intersection. Then, since v∘v⊆u, their union lies in u. In every case we have {Ai}i=1n∪{Bi}i=1m∈Cu.Theorem 15.
Let(X,𝒞) be a conformity. A pseudodiversity δ is uniformly continuous from 𝒞P to (ℝ,diam) if and only if the set Vε={A:δ(A)<ε} is in 𝒞 for each ε>0.Proof.
First, suppose that everyVε is in 𝒞. For each ε>0, the set
(36)Cu={{A1,…,An}:n≤1orδ(⋃i=1nAi)<ε}
is in𝒞P (notice that it has the form of (35) with u=Vε). Let {A,B}∈Cε; then δ(A)≤δ(A∪B)<ε and similarly δ(B)<ε. Thus, |δ(A)-δ(B)|<ε, so δ is uniformly continuous.
Conversely, suppose thatδ is uniformly continuous. Then, for any ε>0, there exists some u∈𝒞, such that every {A1,…,An}∈Cu satisfies supi,j|δ(Ai)-δ(Aj)|<ε. Since for any A∈u, the set {A,⌀} lies in Cu, this implies that δ(A)<ε, which in turn implies that u⊆Vε, which finally implies that Vε is in 𝒞.Corollary 16.
Every conformity is generated by the pseudodiversities which are uniformly continuous from its power conformity to(ℝ,diam).Proof.
Let𝒞 be a conformity, 𝒟 be the conformity generated by the pseudodiversities which are uniformly continuous from the power conformity to (ℝ,diam). By Theorem 9, we have 𝒞⊆𝒟, since every member u of 𝒞 is in a countably-based subconformity of 𝒞. (Take u0=u, ui such that ui∘ui⊆ui-1, i>0 as a base.)
Then, by Theorem15, every pseudodiversity which is uniformly continuous generates a subset of 𝒞; that is, 𝒟⊆𝒞.We saw at the beginning of this section that some conformities can be generated by sets of the form{δα-1[0,ε]}α∈𝒜,ε>0, where 𝒜 is some collection of pseudodiversities, ε>0. What we have just shown is that all conformities are generated in this way, so that we may define a conformity as a filter generated in this way by some collection of diversities.


## 5. Category Theory

In [5], Bryant and Tupper introduced the category Dvy whose objects are diversities and morphisms nonexpansive maps (functions f between diversities (X,δ) and (Y,ρ) such that ρ(f(A))≤δ(A) for all finite A⊆X). This compares with Met [11], whose objects are metric spaces and morphisms nonexpansive maps (functions f between metric spaces (X,d) and (Y,p) such that p(f(x),f(y))≤d(x,y) for all x,y∈X).It is not hard to see that for both metric spaces and diversities, nonexpansive maps are uniformly continuous. In the metric case, they are also continuous.We introduce the category Conf, whose objects are conformities and morphisms uniformly continuous functions. This compares with Unif [11], whose objects are uniformities and morphisms uniformly continuous functions.We also recall Top, whose objects are topological spaces and morphisms continuous maps, and CAT, whose objects are categories and morphisms are functors (maps between categories which preserve composition).With these categories in hand, we can summarize the relationships between diversities, conformities and metric spaces by observing that the maps in the following diagram in CAT are functors, and that the diagram as a whole commutes(37)
where(i)
rδ maps conformities to their induced uniform spaces;(ii)
rd maps diversities to their induced metric spaces;(iii)
uδ maps diversities to the conformities that they generate;(iv)
ud maps metric spaces to the uniform spaces that they generate;(v)
tm maps metric spaces to their metric topologies;(vi)
andum maps uniform spaces to their uniform topologies.Notice that each functor leaves the underlying sets unchanged for example,ud maps a metric space (X,d) to a uniform space (X,𝒰). The morphisms are also unchanged as functions; for example, a nonexpansive map f:X→Y in Met is considered a continuous map in Top under tm and a uniformly continous map in Unif under ud, but it is the same function from the set X to the set Y in all cases.



---

*Source: 675057-2013-10-28.xml*