Applied General Topology c© Universidad Politécnica de Valencia Volume 3, No. 1, 2002 pp. 65–76 Every finite system of T1 uniformities comes from a single distance structure Jobst Heitzig Abstract. Using the general notion of distance function intro- duced in an earlier paper, a construction of the finest distance structure which induces a given quasi-uniformity is given. Moreover, when the usual defining condition xUε y :⇔ d(y,x) 6 ε of the basic entourages is generalized to nd(y,x) 6 nε (for a fixed positive integer n), it turns out that if the value-monoid of the distance function is commutative, one gets a countably infinite family of quasi-uniformities on the un- derlying set. It is then shown that at least every finite system and every descending sequence of T1 quasi-uniformities which fulfil a weak symmetry condition is included in such a family. This is only possible since, in contrast to real metric spaces, the distance function need not be symmetric. 2000 AMS Classification: Primary 54E15; Secondary 54E35, 54A10, 54E70. Keywords: distance function, free monoid, generalized metric, uniformity. 1. Introduction Since Fréchet’s invention of real metric spaces in [2], many generalizations of this concept have been studied in the literature. Much research has been done on generalized metric spaces, in which the distance functions are replaced by certain set systems (cf. [9]). On the contrary, many authors independently suggested more general types of distance functions, the references [8], [12], [7], [5], [6], [11], [10], and [1] are only a small selection. In [3] and [4], a common framework for most if not all of these general concepts of distance functions has been developed to a certain extent. In this paper, the induction of quasi-uniformities on a distance space (X,d,M,P) will be studied. In such a structure, d : X ×X → M is a general distance function on X, that is, it fulfils the zero-distance condition d(x,x) = 0 and the triangle inequality d(x,y) + d(y,z) > d(x,z), and takes its values in a quasi-ordered monoid (q. o. m.) M = (M, +, 0,6). The set P ⊆ M must be a set of positives (or idempotent zero-filter ) for M, that is, a filter of (M,6) with 66 Jobst Heitzig infimum 0 such that, for every ε ∈ P, there is δ ∈ P with 2δ 6 ε. The triple (d,M,P) is called a distance structure on X. For examples and categorical aspects of distance functions on various mathematical objects, see [3, 4]. Using Kelley’s metrization lemma, one can easily show that every quasi- uniformity is induced by a suitable multi-quasi-pseudo-metric, that is, a “quasi- pseudo-metric” taking values in a real vector space instead of the non-negative reals. There is no doubt that this fact must have been noticed early. In this article however, we will see that also every finite family of T1 uniformities (and many families of T1 quasi-uniformities) on a fixed set X comes from a single distance structure. In Theorem 8, this is proved by constructing the finest such structure. This construction is a combinatorially more complex variant of the construction of a finest distance structure for a given quasi-uniformity, which is given in Theorem 2. In contrast to multi-quasi-pseudo-metric spaces, the “topological” information in the resulting spaces will be mostly contained in the set of positives P rather than in the distance function d itself. For example, each T1 quasi-uniformity on some set X can be induced using one and the same distance function. 2. Preliminaries In generalization of the usual definition of entourages in a metric space, let Un(ε) := { (x,y) ∈ X ×X : nd(y,x) 6 nε } for every ε ∈ P and every positive integer n. As P is a filter, the set En := {Un(ε) : ε ∈ P} is a base for a filter Un of reflexive relations on X for each n. Moreover, when M is commutative, nd(y,x) 6 δ > nd(z,y) implies nd(z,x) 6 n ( d(z,y) + d(y,x) ) 6 2δ, so that, for every ε ∈ P, there is δ ∈ P with Un(δ)2 ⊆ Un(ε), that is, Un is a quasi-uniformity. Of course, there are certain relationships between the Un, and in many cases most of them coincide. Obviously, n = n1 + · · · + nk impliesUn1 (ε) ∩·· ·∩Unk(ε) ⊆ Un(ε). Also, nd(x,y) 6 nmd(x,y) + (m− 1)nd(y,x), so that (2m− 1)nδ 6 nε impliesUm(δ) ∩U−1n (δ) ⊆ Un(ε). For a positive d (that is, when d(x,y) > 0 for all x,y), n 6 m and mδ 6 nε imply Um(δ) ⊆ Un(ε). (†) On the other hand, a symmetric d (that is, one with d(x,y) = d(y,x)) fulfils 2d(x,y) = d(x,y) + d(y,x) > d(x,x) = 0, so that here the implication (†) holds at least when m−n is even. This proves the following Uniformities and distance structures 67 Lemma 2.1. (a) n = n1 + · · ·+ nk implies Un ⊆ Un1 ∨·· ·∨Unk , in particular, the map n 7→ Un is antitone with respect to divisibility. (b) For all n,m, Un ⊆ U−1n ∨ Um. (c) For a positive d, all Un coincide. (d) For a symmetric d and all k > 1, U2k = U2 ⊆ U1 = U2k−1. Note that there are indeed natural distance functions which are neither positive nor symmetric, the most important being perhaps the distance x−1y on groups, introduced by Menger [8]: Example 2.2. Let G := [0, 2π) be the additive group of real numbers modulo 2π, M := (P(G), +,{0},⊆) the power set of G ordered by set inclusion and with the usual element-wise addition, P := { (−δ,δ) : δ ∈ (0, 2π] } . Then d(x,y) := {y − x} defines a skew-symmetric distance function (that is, one with d(x,y) + d(y,x) = 0), and U1 is the usual “Euclidean” uniformity on G, while Un is this uniformity “modulo 2πn ” since xUn(−δ,δ) y ⇐⇒ x−y ∈ ⋃ k∈n(−δ + 2kπ n , 2kπ n + δ). Likewise, for X := C \ {0}, M′ := M ⊗ [0,∞), P ′ := P × (0,∞), and d′(x,y) := ( d′(arg x, arg y), ∣∣|y|−|x|∣∣), the uniformity Un of (d′,M′,P ′) induces the Euclidean topology “modulo multiplication with nth roots of unity”. 3. Finest distance functions Like for other topological structures on a set X, we might compare two distance functions d,d′ resp. distance structures D = (d,M,P) and D′ = (d′,M′,P ′) on X with respect to their fineness. If the implication d(x1,y1) + · · · + d(xn,yn) 6 d(z1,w1) + · · · + d(zm,wm) =⇒ d′(x1,y1) + · · · + d′(xn,yn) 6 d′(z1,w1) + · · · + d′(zm,wm) holds for all xi,yi,zi,wi ∈ X, we say that d is finer than d′. If, additionally, for all ε′ ∈ P ′, there is ε ∈ P such that d(x1,y1) + · · · + d(xn,yn) 6 ε =⇒ d′(x1,y1) + · · · + d′(xn,yn) 6 ε′ for all xi,yi ∈ X, we say that D is finer than D′. For a convenient notation, let me introduce the free monoid F of all words in X that have even length and define d(x1y1 · · ·xnyn) := d(x1,y1) + · · · + d(xn,yn), sRd t :⇔ d(s) 6 d(t) (s,t ∈ F). By definition, (F,◦, 0,Rd) is a q. o. m., where ◦ is concatenation and 0 is the empty word. Given any quasi-order R on F which is compatible to ◦ (that is, whenever (F,◦, 0,R) is a q. o. m.), the following construction leads to a distance function dR if and only if xxR 0 Rxx and xz Rxyyz for all x,y,z ∈ X. (?) 68 Jobst Heitzig Let (MR,⊆) := θ(F,R) be the lower set completion of (F,R), that is, the system of all lower sets RA := {s : sRt for some t ∈ A} of (F,R) with set inclusion as partial order. Define an associative operation +R on MR and its neutral element 0R by RA +R RB := R{s◦ t : s ∈ A and t ∈ B} for all A,B ⊆ F and 0R := R{0}. Then let dR : { X ×X → MR = (MR, +R, 0R,⊆) (x,y) 7→ R{xy}. It was shown in [3] that dRd is equivalent to d, which motivates calling Rd the generating quasi-order of d. Moreover, when R⊥ is the smallest quasi-order on F which fulfils (?) and is compatible with ◦ then d⊥ := dR⊥ is a finest distance function on X. In this relation, the step from s ∈ F to an upper neighbour w. r. t. R⊥ consists of inserting a pair yy at an arbitrary position in s or removing a pair yy after an even number of letters in s, while the step to a lower neighbour is made by removing a pair yy at an arbitrary position or inserting a pair yy after an even number of letters. 4. Induction of a single quasi-uniformity We are now ready for the first main result of this paper: Theorem 4.1. Every quasi-uniformity V admits a finest distance structure (dV,MV,PV) for which V = U1. Proof. Let V be some quasi-uniformity on X and V0 := ⋂ V. We will see that the essential information about V is contained in the set of positives PV which we must construct, while the generating quasi-order RdV is fully determined by the very weak condition that xy RdV zz must hold for any triple x,y,z ∈ X which fulfils y V0 x (otherwise dV(x,y) 66 ε for some ε ∈ PV, in contradiction to V0 ⊆ U1(ε)). Therefore, let R be the smallest quasi-order on F that is compatible with ◦ and fulfils x′y′R 0 Rxx and xz Rxyyz for all x,y,z,x′,y′ ∈ X with y′V0 x′. (?′) If we find a suitable s. o. p. P such that (dR,P) induces V then R must obviously be the smallest relation (and thus dR a finest distance function) with this property. Now observe that each of the resulting entourages U1(ε) has to include some entourage V1 ∈ V, hence every ε ∈ P must include some set {xy ∈ F : y V1 x} with V1 ∈ V. Since 0R = R{xx} is a neutral element, ε must even include the set {xy ∈ F : y V0V1V0 x}⊆ 0R +R {xy ∈ F : y V1 x} +R 0R. The same must be true for any δ ∈ P which fulfils δ +R δ ⊆ ε, so that ε must also include a set {xyx′y′ ∈ F : y V0V2V0 x,y′V0V2V0 x′} ⊆ δ +R δ for some V2 ∈ V. This process of replacing some ε by some 2δ can be continued, and in Uniformities and distance structures 69 order to describe it formally, let us define W to be the smallest set of tuples of positive integers that contains the 1-tuple (1) and fulfils (n1, . . . ,ni−1,ni + 1,ni + 1,ni+1, . . . ,nk) ∈ W whenever (n1, . . . ,nk) ∈ W and 1 6 i 6 k. One can think of the elements of W as coding exactly those terms of the form ‘εn1 +· · ·+εnk’ that can be obtained when we start with the term ‘ε1’ and then successively replace an arbitrary summand ‘εn’ by the term ‘εn+1 + εn+1’. Accordingly, one shows by induction that for each element ε1 of a set of positives P there is a sequence ε2,ε3, . . . in P such that (n1, . . . ,nk) ∈ W implies εn1 + · · · + εnk 6 ε1. In our situation, this observation implies that for each ε ∈ P there must be a sequence S = (V1,V2, . . . ) in V with the property that ε includes the set AS of all words v1w1 · · ·vkwk ∈ F for which there is some (n1, . . . ,nk) ∈ W such that wi V0VniV0 vi for i = 1, . . . ,k. In particular, εS := RAS ⊆ Rε = ε. It turns out that this is the only restraint on the set of positives PV. More precisely, we will see that the system B := {εS : S is a sequence in V} of lower sets of (F,R) is a base for a set of positives of (MR, +R, 0R,⊆), and that the distance structure (dR,P) induces the quasi-uniformity V. It is then clear that P is the largest set of positives with this property, so that (dV,PV) := (dR,P) is a finest distance structure inducing V. Since V is a filter and the map S 7→ εS is isotone in every component of S, B is a filter-base. In order to show that P is a s. o. p., we first observe that (n1, . . . ,nk), (m1, . . . ,ml) ∈ W implies (n1 + 1, . . . ,nk + 1,m1 + 1, . . . ,ml + 1) ∈ W. Indeed, after increasing each index by one, the replacements that produce (n1, . . . ,nk) and (m1, . . . ,ml) from the tuple (1) can be combined to a se- quence of replacements that produce (n1 + 1, . . . ,nk + 1,m1 + 1, . . . ,ml + 1) from the tuple (2, 2). Hence also v1w1 · · ·vkwk,v′1w′1 · · ·v′lw ′ l ∈ ε(V2,V3,V4,... ) implies v1w1 · · ·vkwkv′1w ′ 1 · · ·v ′ lw ′ l ∈ ε(V1,V2,V3,... ) for each sequence (V1,V2, . . . ) in V. Secondly, we must prove that ⋂ B = 0R, which is the harder part. Let s = x1z1 · · ·xmzm ∈ ⋂ B and V1 ∈ V. I will show that zj V0V1V0 xj holds for all j = 1, . . . ,m. Choose a sequence S = (V1,V2, . . . ) in V such that Vi+1V0Vi+1 ⊆ Vi for all i > 1 (such a sequence always exists in a quasi-uniformity). Note that (n1, . . . ,nk) ∈ W then implies V0Vn1V0Vn2V0 · · ·V0VnkV0 ⊆ V0V1V0. Now s ∈ RAS, that is, there exists a word v1w1 · · ·vkwk and a k-tuple (n1, . . . ,nk) ∈ W such that wi V0VniV0 vi for i = 1, . . . ,k and sRv1w1 · · ·vkwk. The latter means that, starting with v1w1 · · ·vkwk, one gets x1z1 · · ·xmzm in finitely many steps in each of which 70 Jobst Heitzig some pair of letters is inserted or removed corresponding to the condition (?′). Now take the k-tuple ψ := (w1 V0Vn1V0 v1, . . . ,wk V0VnkV0 vk) of formulae (which express true propositions about the word v1w1 · · ·vkwk) and modify it, analogously to those finitely many steps, in the following way: (i) if (because of xz Rxyyz) a pair yy is being removed after an odd number of let- ters, replace the two consecutive formulae . . .V0 y,y V0 · · · in ψ by one formula . . .V0 · · · (that is, erase the symbols ‘y,y V0’); (ii) if (because of 0 Rxx) a pair xx is being removed after an even number of letters, remove the corresponding formula x.. .x from ψ; (iii) if (because of x′y′R 0) a pair x′y′ is inserted, insert the formula y′V0 x′ at the respective position in ψ. By definition of R, all these modifications preserve the truth of all formulae in the tuple, and each formula in the resulting tuple (ψ1, . . . ,ψk) expresses a true proposition of the form ψj = zj V0VnaV0Vna+1V0 . . .V0VnbV0 xj with 1 6 a,b 6 k. Since all Vni are reflexive, ψj thus implies zj V0Vn1V0Vn2V0 . . .V0VnkV0 xj, hence zj V0V1V0 xj. Because V1 was chosen arbitrarily, we conclude that zj V0 xj for all j, and therefore x1z1 · · ·xmzm R 0. Finally, we have to show that (dR,P) induces the quasi-uniformity V. For V ∈ V, choose V1 ∈ V such that V0V1V0 ⊆ V , then choose a sequence S as in the preceding paragraph. There we have shown that, in particular, dR(x,z) ⊆ RAS implies (z,x) ∈ V0V1V0 ⊆ V. On the other hand, for each ε ∈ P there is some sequence S = (V1, . . . ) in V such that εS ⊆ ε, and (z,x) ∈ V1 ⊆ V0V1V0 impliesdR(x,z) ⊆ εS ⊆ ε. � A somewhat astonishing consequence of this construction is that one dis- tance function is compatible to all T1 quasi-uniformities on X: Corollary 4.2. The distance function d⊥ is the finest distance function d on X such that for each T1 quasi-uniformity V on X there is a s. o. p. P such that (d⊥,P) induces V (namely P = PV). 5. Induction of systems of quasi-uniformities I will now extend this result to certain systems of quasi-uniformities and show that, in particular, every finite system and every descending sequence of T1 uniformities is part of some system (Un)n∈ω. Some additional notation: Intervals of integers will be designated by [a,b]. A pair of letters xy ∈ F is a syllable of a word s ∈ F if and only if it occurs in s after an even number of letters. Let s̃ ∈ F be the word s after deletion of all syllables of the form xx (x ∈ X). The length of s̃ in letters is designated by Uniformities and distance structures 71 `(s), and sa is the ath letter of s̃ for any position a ∈ [1,`(s)]. The subword of s̃ from position a to b is sa,b. Moreover, let λ(x,s) and σ(xy,s) denote the number of occurrences of the letter x resp. the syllable xy in s̃. Finally, (xy)r = xy · · ·xy is a word consisting of r equal syllables. The next constructions mainly rely on four lemmata. For the moment, let us fix some words s,t ∈ F with sR⊥ t, where t̃ = (v1w1) r1 · · ·(v%w%)r%, vi 6= wi, and all ri are even. Then s̃ can be derived from t̃ by a finite number of successive deletions of pairs of identical letters which are neighbours at the time of deletion. A guiding example: for s = yy xy zz xy uz uz R⊥xy xy zz zuuz uz xxuz = t, the deletion steps could be this: in t̃ = xy xy zuuz uz uz, first delete uu, giving xy xy zz uz uz, then delete zz, giving xy xy uz uz = s̃. We now also fix such a sequence of deletions and let D ⊆ [1,`(t)] be the set of positions in t̃ whose corresponding letters are deleted in one of these steps (in the example: D = [5, 8]). For a ∈ D, let π(a) ∈ [1,`(t)] be that position in t̃ such that ta and tπ(a) build a deleted pair (in the example: π(5) = 8 and π(6) = 7). Finally, we write ayb if and only if a and b− 1 are even numbers in D such that a < π(a) = b− 1 (in the example: 6y8). Note that because tc and tπ(c) must first become neighbours before they can be deleted, ay· · ·yb implies that (i) [a,b−1] ⊆ D, (ii) π(c) ∈ [a,b−1] for all c ∈ [a,b−1], and thus (iii) λ(x,ta,b−1) is even for all x ∈ X. Lemma 5.1. Assume ay· · ·yby· · ·yc, ta = tb−1, and tb = tc−1. Then (a) ta−1 = tb or tb−1 = tc. (b) If ta−1 6= tb then λ(ta, tc,`(t)) is odd. (c) If tb−1 6= tc then λ(tb, t1,a−1) is odd. Proof. Let e,f,e′,f′,e′′,f′′ ∈ [1,`(t)] with e < a 6 f < e′ < b 6 f′ < e′′ < c 6 f′′ such that te,f , te′,f′, and te′′,f′′ are three of the defining subwords (viwi)ri of t̃. Moreover, let x := ta−1, y := ta = tb−1, z := tb = tc−1, and w := tc, and assume x 6= z. The situation and the parity arguments that will follow are sketched in Figure 1. Because of x 6= z, we have λ(x,te′,b−1) = 0. Moreover, λ(x,tf+1,e′−1) is even (since all ri are even), and λ(x,ta,b−1) is even because of (iii), so that also λ(x,ta,f ) is even and λ(y,ta,f ) is odd (since |[a,f]| is odd). As before, λ(y,tf+1,e′−1) and λ(y,ta,b−1) are even, thus λ(y,te′,b−1) is odd. Because all ri are even, λ(y,tb,f′) is also odd. Again, λ(y,tf′+1,e′′−1) and λ(y,tb,c−1) are even, hence λ(y,te′′,c−1) is odd. In particular, y ∈{z,w}, that is, y = w (as yz is a syllable of t̃), and λ(y,tc,f′′) is also odd. Finally, λ(y,tc,`(t)) is odd because λ(y,tf′′,`(t)) is even. This proves (a) and (b), whereas (c) is strictly analogous to (b). � 72 Jobst Heitzig Figure 1. Situation in Lemma 5.1 π π� � ? ?· · · � � ? ? t̃ = · · ·(xy · · ·xy · · ·xy) · · · · · · · · · · · · · · ·(yz · · ·y | | (continued on | the next line) |↑ e ↑ a ↑ f ↑ e′ ↑ b− 1 even } λ(x) even even 0 odd even odd } λ(y) even π π� � ? ?· · · � � ? ?| (conti- | nued) | | z · · ·yz) · · · · · · · · · · · · · · ·(zw · · ·zw · · ·zw) · · · ↑ b ↑ f′ ↑ e′′ ↑ c ↑ f′′ λ(y) { odd even odd odd even even odd Lemma 5.2. (a) Assume that a0 yb0 ya1 yb1 · · ·akybkyc with ta0 = · · · = tak = y, and tb0 = · · · = tbk = z. Then ta0−1 = z or y = tc. (b) Assume that a y · · ·y b with ta = tb−1, and ta−1 6= tb. Then both λ(ta, t1,a−1) and λ(ta, tb,`(t)) are odd. Proof. (a) Define e′′,f′′ as above. Similarly, for each i ∈ [0,k], find positions ei,fi,e ′ i,f ′ i ∈ [1,`(t)] with ei < ai 6 fi < e ′ i < bi 6 f ′ i such that tei,fi and te′i,f′i are two of the defining subwords of t̃. Assuming ta0−1 = x 6= z, one proves that λ(y,tb0,f′0 ) is odd exactly as before. Since, for i ∈ [1,k], all of λ(y,tbi−1,ai−1), λ(y,tai,bi−1), λ(y,tf′i−1+1,ei−1), λ(y,tei,fi), λ(y,tfi+1,e′i−1), and λ(y,te′i,f′i ) are even, and since also λ(y,tbk,c−1) and λ(y,tf′k+1,e′′−1) are even, we conclude that λ(y,te′′,c−1) is odd, hence y = tc. (b) Again as in the previous lemma, one proves that, for y := ta, the number λ(y,tb,f′) is odd, so that the first claim follows because λ(y,tf′,`(t)) is even. The second claim is just the dual. � Lemma 5.3. Assume that se−1se = xz is the syllable of s̃ that remains after all the deletions in a subword ta−1,b of t̃, with a < b, ta−1 = x, and tb = z. Then there is y ∈ X such that λ(y,s) > 0, σ(xy,ta−1,b) > 0, and σ(yz,ta−1,b) > 0. Proof. Although ta and tb−1 may be different, we find k > 2, c1, . . . ,ck ∈ [1,`(t)], and y0,y1, . . . ,yk ∈ X such that a = c1 y· · ·yc2 y· · ·yc3 · · ·ck−1 y· · ·yck 6 b, Uniformities and distance structures 73 tci = tci+1−1 = yi for i ∈ [1,k− 1], y0 = x, yk = z, and yi 6= yj for i 6= j (Start with a =: c′1 yc ′ 2 y · · ·yc′l := b and y ′ i := tc′i. As long as there are indices j > i > 1 with y′i = y ′ j, remove all the indices i + 1, . . . ,j, so that finally all remaining y′i are different. Since y ′ 1 = ta 6= z = y′l, at least k ≥ 2 of the original indices are not removed, including the index 1, and the corresponding c′i build the required positions c1, . . . ,ck). Then k = 2 since otherwise Lemma 5.1 (a) would imply that either y0 = y2 or y1 = y3. With y1 for y and c2 for b, Lemma 5.2 (b) implies that λ(y,t1,a−1) is odd. Now, also λ(y,s1,e−1) is odd, because c ∈ [1,a− 1] ∩D implies π(c) ∈ [1,a − 1] (since the letter x at position a − 1 is not deleted). In particular, λ(y,s1,e−1) > 0. � Lemma 5.4. Assume that k > 2, c0 yc1 · · ·ck−1 yck, ck ∈ D, and π(ck) = c0 − 1, representing a number of deletions of the form � �π � �π · · · · · · · · · · · · � �π� �π ?? tc0 ?? tc1 ? ? tck−1 ?? tck Let t′ := tc0−1tc0tc1−1tc1 · · ·tck−1tck be the word consisting only of the “bound- ary letters”, and i ∈ [0,k]. Then σ(tci−1tci, t′) = σ(tcitci−1, t′). Proof. Put c−1 := ck. Obviously, tci−1 = tci−1 for all i ∈ [1,k], and tck = tc0−1. If also tci−1−1 = tci for all i ∈ [0,k] then k must be odd (since tck 6= tc0 ), and σ(tci−1tci, t ′) = σ(tcitci−1, t ′) = k/2. Otherwise, there are r > 1 positions i(1) < · · · < i(r) in [0,k] with tci(j)−1−1 6= tci(j) . Then i(j + 1) − i(j) is even for all j (otherwise, put a0 := ci(j)−1, b0 := ci(j),. . . , c := ci(j+1)−1 and apply Lemma 5.2 (a)). In case that all i(j) are even, we have tck−1 6= tck = tc0−1 = tc1 = tci for all odd i, so that k must be odd. On the other hand, if all i(j) are odd, we have tck = tc0 − 1 6= tc0 = tci for all even i, so that again k must be odd. This shows that t′ is of one of the following two forms: t′ = (yxxy)m0 (yz1z1y)m1 · · ·(yzr−1zr−1y)mr−1 (yxxy)mr or t′ = xy(yxxy)m0 (yz1z1y)m1 · · ·(yzr−1zr−1y)mr−1 (yxxy)mryx, from which the claim follows immediately. � Now we are ready for the construction. Let pi be the ith odd prime number, and S(A) := {a1 + · · · + ak : k > 1, ai ∈ A} for any set A of integers. In the next theorem, we need the following sets of even numbers: for any positive integer u, let quj = 2pj ∏u i=1 pi for all j ∈ [1,u], Qu := {qu1, . . . ,quu}, and Quj := Qu \ {quj}. It is easy to see that then, for each j ∈ [1,u] and k ∈ S(Quj), k −quj /∈ S(Quj) (since pj divides k but not quj). 74 Jobst Heitzig Theorem 5.5. (a) Let V1, . . . , Vu be a finite system of T1 quasi-uniformities such that, for all i,j ∈ [1,u], Vj ⊆ V−1j ∨ Vi. Then there is a finest s. o. p. P such that, for j ∈ [1,u], Vj = Uquj . (b) Let V1 ⊇ V2 . . . be a descending sequence of T1 quasi-uniformities such that, for all j and all U ∈ Vj, there are V1 ∈ V1,V2 ∈ V2, . . . with V −1j ∩ ⋃ i 6=j Vi ⊆ U. Then there is a finest s. o. p. P such that Vj = U2j for all j. Proof. For part (a), let I := [1,u], while for part (b), let I be the set of natural numbers. In both cases, P is defined quite analogously to the proof of Theorem 4.1: its filter-base is now the system B := {εS : S is a sequence in V} of lower sets εS = R⊥AS of R⊥, where V := ∏ i Vi, and the definition of AS changes to this: for S = ((V11,V12, . . . ), (V21,V22, . . . ), . . . ), AS is now the set of all words (v1w1)r1 (v2w2)r2 · · ·(v%w%)r% ∈ F for which there is some (n1, . . . ,n%) ∈ W and some tuple of indices (i1, . . . , i%) such that, for all a ∈ [1,ρ], wa Vnaia va and either ra = quia (for the proof of (a)) or ra = 2ia (for the proof of (b)). As before, P turns out to be a s. o. p., where the only major change is the proof of ⋂ B = 0R: Let s ∈ ⋂ B, σ(xz,s) > 0, and V = (V11,V12, . . . ) ∈ V. Choose S so that Vk+1,iVk+1,i ⊆ Vki for all i ∈ I and all k, and some t ∈ AS with sR⊥ t. Assume that t̃ = (v1w1)r1 (v2w2)r2 · · ·(vρwρ)rρ. If σ(xz,t) > 0, put yV := x, otherwise choose some yV ∈ X with λ(yV ,s) > 0, σ(xyV , t) > 0, and σ(yV z,t) > 0, according to Lemma 5.3. Since `(s) is finite and V is filtered, there is some y such that, for all V ∈ V, there is V ′ ∈ V with V ′ 6 V and yV ′ = y, where 6 denotes component-wise set inclusion. Consequently, xUV y UV z for all V ∈ V, where UV = ⋃ i V1i. This implies that x,y ∈ ⋂ Vi and x,y ∈ ⋂ Vi′ for some i, i′ ∈ I, hence x = y = z. Since this is a contradiction to x 6= z, we have shown that s̃ is the empty word, that is, s ∈ 0R. Finally, let us show that Vj = Uquj resp. Vj = U2j for each j ∈ I. Fix some j ∈ I and let V0j ∈ Vj. Because of the premises, the following choices can now be made. For part (a), choose for all i ∈ I\{j} some V0i ∈ Vj and V1i ∈ Vi such that (V0i)−1∩V1i ⊆ V0j. Then choose V1j ∈ Vj such that V1j ⊆ V0i for all of the finitely many i ∈ I \{j}. For part (b), choose instead some (V11,V12, . . . ) ∈ V with V1h = V1j ⊆ V0j for all h 6 j and (V1j)−1 ∩ ⋃ i 6=j V1i ⊆ V0j. After that, choose the remaining components of a sequence S = ( (V11,V12, . . . ), (V21,V22, . . . ), . . . ) in V so that Vk+1,iVk+1,i ⊆ Vki for all i ∈ I and all k, and assume that rdR⊥(x,y) 6 εS, that is, s := (xz) r R⊥ t ∈ AS with (a) r = quj resp. (b) r = 2j. We have to show that z V0j x. Uniformities and distance structures 75 By definition of AS, we have t̃ = (v1w1)r1 (v2w2)r2 · · ·(vρwρ)rρ, and there is some corresponding tuple (i1, . . . , iρ). Since the only letters in s̃ are x and z, there are exactly r occurrences of the syllable xz in t̃ which are not deleted (because otherwise Lemma 5.3 would imply the existence of a third letter y in s̃). All other occurrences of xz in t̃ are deleted as part of some set of deletions of the form represented in Lemma 5.4, that is, there are c0,. . . ,ck with properties as in Lemma 5.4 and with tci−1tci = xz for some i ∈ [0,k]. Then the lemma implies that σ(xz,t) = r + σ(zx,t) =: k. For (a): If (vawa)ra = (xz)quj for some a ∈ [1,ρ], then ia = j and (z,x) ∈ Vna,ia ⊆ V1j ⊆ V0j. Otherwise, we know that k ∈ S(Quj), that is, σ(zx,t) = k − quj ∈ S(Qu) \ S(Quj), so that (vawa)ra = (zx)quj and ia = j for some a ∈ [1,ρ]. Also, (vbwb)rb = (xz)qui and ib = i for some b ∈ [1,ρ] and some i ∈ I \{j}, so that (z,x) ∈ (V1j)−1 ∩V1i ⊆ V0j. For (b) instead: If (vawa)ra = (xz)2 i for some a ∈ [1,ρ] and i 6 j, then ia = i and (z,x) ∈ Vna,ia ⊆ V1i ⊆ V0j. Otherwise, k is a multiple of 2j+1 so that σ(zx,t) = k − 2j is not such a multiple. Therefore, (vawa)ra = (zx)2 ia and ia 6 j for some a ∈ [1,ρ]. Also, (vbwb)rb = (xz)2 ib and ib 6= j for some b ∈ [1,ρ], so that again (z,x) ∈ (V1ia)−1 ∩V1ib ⊆ V0j. � Unfortunately, this proof highly depends on the fact that MR⊥ is not com- mutative, so that the conjecture that there is also a suitable distance structure with a commutative value monoid is yet unproved. The most familiar example for a descending sequence of uniformities is per- haps the following. Let X := Cb[0, 1] be the (infinite-dimensional) vector space of bounded, continuous, and real-valued functions on the unit interval [0, 1], and, for positive integers p, let Vp be the uniformity on X induced by the usual p-norm. For a second example, take u different primes p1, . . . ,pu and let Vi be the pi-adic uniformity on the rationals. As these are transitive uniformities with countable bases, we may use a slightly simpler construction. More precisely, a base for Vi is the set of equivalence relations Ui,m := {(x,y) : pmi divides ν(|x−y|)}, where m is a positive integer, and ν(z/n) := z whenever z,n have no common divisor (that is, ν(q) is the nominator of q). Therefore, it suffices to use only those εS where all tuples in S are equal, that is, Vh+1,i = Vhi for all i,h. In this case, the resulting s. o. p. P has a countable base B = {εm : m a positive integer}, where εm := ∞⋃ n=0  n · ⋃ j∈[1,u], (x,y)∈Uj,m qujd⊥(x,y)   . 76 Jobst Heitzig As a concluding remark, I note that with similar methods, one can show that, for each pair of comparable T1 uniformities V2 ⊆ V1, there is some sym- metric distance structure (d,P) such that Ui = Vi, which gives a complete characterization of the symmetric T1 case. References [1] M. M. Bonsangue, F. van Breugel, and J. J. M. M. Rutten, Generalized metric spaces: completion, topology, and powerdomains via the Yoneda embedding, Theoret. Comput. Sci. 193 (1998), no. 1-2, 1–51. [2] Maurice Fréchet, Sur les classes V normales, Trans. Amer. Math. Soc. 14 (1913), 320– 325. [3] Jobst Heitzig, Partially ordered monoids and distance functions, Diploma thesis, Uni- versität Hannover, Germany, July 1998. [4] , Many familiar categories can be interpreted as categories of generalized metric spaces, Appl. Categ. Structures (to appear) (2002). [5] Ralph Kopperman, All topologies come from generalized metrics, Amer. Math. Monthly 95 (1988), no. 2, 89–97. [6] Djuro R. Kurepa, General ecart, Zb. Rad. (1992), no. 6, part 2, 373–379. [7] Boyu Li, Wang Shangzi, and Maurice Pouzet, Topologies and ordered semigroups, Topol- ogy Proc. 12 (1987), 309–325. [8] Karl Menger, Untersuchungen über allgemeine Metrik, Math. Annalen 100 (1928), 75– 163. [9] J. Nagata, A survey of the theory of generalized metric spaces, (1972), 321–331. [10] Maurice Pouzet and Ivo Rosenberg, General metrics and contracting operations, Dis- crete Math. 130 (1994), 103–169. [11] Hans-Christian Reichel, Distance-functions and g-functions as a unifying concept in the theory of generalized metric spaces, Recent developments of general topology and its applications (Berlin, 1992), Akademie-Verlag, Berlin, 1992, p. 279–286. [12] B. Schweizer and A. Sklar, Probabilistic metric spaces, North–Holland, New York, 1983. Received September 2001 Revised January 2002 Jobst Heitzig Institut für Mathematik Universität Hannover Welfengarten 1 D-30167 Hannover Germany E-mail address : heitzig@math.uni-hannover.de