kopperag.dvi @ Applied General Topology c© Universidad Politécnica de Valencia Volume 5, No. 1, 2004 pp. 115- 127 Partial metrizability in value quantales R. Kopperman∗, S. Matthews and H. Pajoohesh Abstract. Partial metrics are metrics except that the distance from a point to itself need not be 0. These are useful in modelling partially defined information, which often appears in computer science. We generalize this notion to study “partial metrics” whose values lie in a value quantale which may be other than the reals. Then each topology arises from such a generalized metric, and for each continuous poset, there is such a generalized metric whose topology is the Scott topology, and whose dual topology is the lower topology. These are both corollaries to our result that a bitopological space is pairwise completely regular if and only if there is such a generalized metric whose topology is the first topology, and whose dual topology is the second. 2000 AMS Classification: 06B35, 06D10, 06F30, 54E35, 54E55 Keywords: value lattice, partial metric, quasimetric, completely regular bitopological space, value quantale, well above, auxiliary relation 1. Introduction A partial metric [7] is a generalised metric for modelling partially defined information. For example, if a person is told to visit London in the UK they would instantly ask where in London. A more precise instruction might be to visit London’s Hyde Park, yet again they would ask, where in Hyde Park. A sufficiently precise instruction might be to visit the Prince Albert Memorial, or the Serpentine Gallery in Hyde Park. Let the relation L1 ≤ L2 on such ∗This author wishes to acknowledge support for this research from the EPSRC of the United Kingdom (grant GR/S07117/01), and from the City University of New York (PSC- CUNY grant 64472-00 33). 116 R. Kopperman, S. Matthews and H. Pajoohesh locations be defined by L2 is a place in L1. Then this is a partial ordering. For example, London ≤    Hyde Park ≤ { Serpentine Gallery Prince Albert Memorial Trafalgar Square ≤ Nelson′s Column A partial metric is a means of extending the notion of metric, such as the Euclidean distance between the Serpentine Gallery and Nelson’s Column, to posets. To see how and, most importantly, why this is useful a brief discussion of the programming problem in computer science which led to partial metrics is now given. A concurrent program is a computer program consisting of two or more processes to be executed in parallel, and also to communicate with each other in some way. A problem arises when two processes are each waiting upon the other for a communication before each itself can communicate. This is a deadly embrace situation known as deadlock where two processes remain alive yet doing nothing as each waits for a communication that can never arrive. In general it is not decidable whether or not an arbitrary concurrent program may deadlock at some time in its execution. However, in a concurrent program for a safety critical application, such as for use in a hospital’s intensive care unit, it is essential that there be some means of proving that deadlock can never occur. The best that can be done is to consider certain concurrent programs where it can be proven that deadlock can never arise. Deadlock is a problem between two processes which are directly or indirectly connected by some path of communication, and so a consideration of such paths provides an analysis of possible deadlock. A cycle is a set of processes P1, P2, . . . , Pn where each Pi communicates by sending messages to P(i+1) mod n, and so receiving messages from P(i−1) mod n. For each Pi let ci be the largest possible difference at any time between the number of messages sent minus the number received. For example, consider the case for n = 2. Suppose c1 = 5, then at any time P1 has sent at least five more messages than it has received. Suppose also that c2 = −3, then P2 has sent at least −3 more (i.e. at most 3 fewer) messages than it has received. This cycle of two processes cannot deadlock as at any time there is a net surplus of at least c1 +c2 = 5+(−3) = 2 messages being produced by the cycle than being received. If the so-called cycle sum ∑n i=1 ci > 0 then this cycle of processes can never deadlock. To prove that a concurrent program will not deadlock it is thus sufficient to prove that each and every cycle sum is positive. This is the cycle sum theorem [10], later extended to a more sophisticated model of concurrent programming as the cycle contraction mapping theorem [6]. The virtue of these theorems is that they are an extensional treatment of deadlock, one which does not require a detailed understanding of exactly how programs are executed. They prove that a deadlock free computation is necessarily the only possible behaviour for a concurrent program. This is in contrast to the more usual (but more difficult) procedure of constructing the Partial metrizability in value quantales 117 sequence of all intermediate states of an execution, and demonstrating that the limit is a deadlock free computation. The behaviour of a cycle can be studied as the fixed point of a function. The purpose of the cycle sum and cycle contraction mapping theorems is to firstly prove that the fixed point is unique, and secondly that this point is, in a desired sense, totally defined. Being an extensional treatment of deadlock we require not the details of how programs are executed, only the distinction between the so-called total (the word total is used here in place of complete as in [7]) computations (i.e. the desirable deadlock free executions) and the partial, that is, those initial parts of a total computation. To appreciate the distinction between total and partial objects we return to the analogy of a visitor to London. A reference to London is only partially informative, as it does not refer to a more specific place of interest such as Hyde Park or Trafalgar Square. London is thus a partialization of Hyde Park, Trafalgar Square, etc. where the (extent of) totalness of a place can be measured by the area of ground upon which it stands. London is a partial approximation to Hyde Park as the latter stands upon a smaller space and contained within that of London. The cycle sum and cycle contraction mapping theorems are in essence in- ductive results to prove that eventually a total result must follow from the inductive hypothesis that for each step in a computation the next step will steadily increase the (extent of) totalness. To formulate such an hypothesis requires a function to measure the (extent of) totalness of a computation. For example, a tourist might ‘visit’ the partial places London, Trafalgar Square, Nelson’s column. The (extent of) totalness of each partial place, as measured by its area, becomes increasingly precise at each step. In the theorems under discussion the property of deadlock free for programs is partialized precisely to the extent to which it applies to each initial part of a deadlock free com- putation. This is a downward approach in which a partial object is viewed as a partialized total one. This is in contrast to the established Scott-Strachey least fixed point semantics [9] where the behaviour of a program is viewed as the limit of a chain of partial approximations, an upward approach where a total object (if the notion exists) is a completion of partial objects. While the upward view is necessary to define the semantics for an arbitrary program, the downward view is sufficient to reason about well behaved programs such as those which are deadlock free. The general problem arising from these deadlock studies [10, 6] is how to partialize theories. Given a theory of (now to be known as) total objects how can additional (to be known as) partial objects be introduced and the theory extended yet weakened to apply to them? In each of the above deadlock studies the total objects form a metric space of infinite sequences. For a set X let, d : Xω × Xω → ℜ+ be the metric such that d(x,y) = 2−sup{n|∀m 0 Note that a pmetric restricted to the total objects is a metric. For all x,y ∈ X, x < y ⇒ |x| > |y|, and so |·| can be used to measure the (extent of) totalness of each member of X. The Banach contraction mapping theorem can be extended to partial metrics. A contraction is a function f : X → X for which there exists a 0 < c < 1 such that ∀ x,y ∈ X, p(f(x), f(y)) ≤ c × p(x,y). A Cauchy sequence is an x ∈ Xω such that there exists a > 0 such that for each ǫ > 0 there exists k ∈ ω such that for all n,m > k, |p(xn,xm) − a| < ǫ. A sequence x ∈ Xω converges if there exists a ∈ X such that for each ǫ > 0 there exists k > 0 such that for all n > k, p(xn,a) − p(a,a) < ǫ. p is complete if every Cauchy sequence converges. The partial metric contraction mapping theorem [6] is that each contraction for a complete partial metric has a unique fixed point, and this point is total. Although originally developed as a partialized theory for extensional reason- ing about properties of programs such as deadlock, partial metrics have since been developed in computer science as a theory of partiality for studying con- tinuous lattices, using the induced ordering x ≤ y iff p(x,x) = p(x,y). A partial metric p : X × X → ℜ+ generalises the theory of metric spaces by dropping the requirement that self distance always be zero, and in so doing opens up the study of T0 spaces to a symmetric (in contrast to quasimetrics) metric style treatment, which in addition incorporates a weight function | · | : X → ℜ+. The present paper takes the process of generalisation further by replacing the range ℜ+ of a pmetric by a value quantale. 2. P-metrics and qmetrics in value lattices Definition 2.1. A value lattice is a poset (V,≤), whose least element is de- noted 0 and largest is ∞, such that (V,≥) is a continuous lattice; together with an associative, commutative operation + : V × V → V such that 0 is an iden- tity and for each R,S ⊇ V, ( ∧ R) + ( ∧ S) = ∧ {r + s|r ∈ R,s ∈ S}, where Partial metrizability in value quantales 119 ∧ denotes inf. Here are some simple but useful consequences of this infinite distributive law: • (s1) For all p ∈ V , p + ∞ = ∞. • (s2) For all p,q,r,s ∈ V , p ≥ q and r ≥ s implies p + r ≥ q + s. A value lattice V, is Boolean if for each a ∈ V, a + a = a. Like any map preserving arbitrary infima, for each p, the map +p, +p(q) = p + q has a right adjoint (see [4], chap. 0.3), −̇ p defined by −̇ p(q) = ∧ {r ∈ V |p + r ≥ q}(= q −̇ p). The properties of −̇ (see [2]) include for any p,q,r ∈ V, S ⊆ V : • (d1) p + r ≥ q iff r ≥ q −̇ p. • (d2) q −̇ p = 0 iff p ≥ q; • (d3) p + (q −̇ p) ≥ q; The reversal of order above – that is, the requirement that (V,≥), rather than the expected (V,≤) be a continuous lattice – is due our need to maintain the traditional way of writing axioms for metrics, in order to allow easy com- parison between metric spaces and our structures. The reader must be careful when looking at references (except [2]), which use the traditional order. No- tice that products of value lattices are again value lattices, and that with the way-above relation denoted ≫, that in a product ∏ I Vi, a ≫ b if and only if each ai ≫ bi and {i|ai 6= ∞} is finite. When we write ≪, we mean the inverse of ≫. Key examples of value lattices include the extended nonnegative reals, IE = [0,∞], the unit interval II = [0,1], and the two-point set, IB = {0,∞}, together with the usual ≤,+, except that in II we truncate addition, via a+b = min{a+u b,1}, where +u denotes the usual sum. By a qmetric from a set X into a value quantale V, we mean a map q : X × X → V such that for each x,y,z ∈ X, q(x,z) ≤ q(x,y) + q(y,z), and q(x,x) = 0. Definition 2.2. A V-pseudopmetric space is a pair (X,p), consisting of a set X and a function p : X × X → V satisfying the following conditions: P1) For every x,y ∈ X, p(x,y) ≥ p(x,x), P2) For every x,y ∈ X, p(x,y) = p(y,x), P3) For every x,y,z ∈ X, p(x,z) ≤ p(x,y) + (p(y,z) −̇ p(y,y)). Its associated qmetric is qp : X×X → V, defined by qp(x,y) = p(x,y) −̇ p(y,y). The dual of any qmetric is the qmetric defined by q∗(x,y) = q(y,x) (so q∗p(x,y) = p(x,y) −̇ p(x,x)). A V-pmetric is a V-pseudopmetric which also satisfies: P4) For every x,y ∈ X, x = y iff p(x,y) = p(x,x) = p(y,y). Definition 2.3. Given a V-qmetric q : X × X → V, the ball (or closed ball) about x ∈ X of radius r ∈ V for is the set Nr(x) = {y ∈ X|q(x,y) ≤ r}; also, N∗r (x) = {y ∈ X|q ∗(x,y) ≤ r}, and the open ball about x of radius r is Br(x) = {y|q(x,y) ≪ r}. 120 R. Kopperman, S. Matthews and H. Pajoohesh A subset U of X is open in X if for each x ∈ U there is an r ≫ 0 such that Nr(x) ⊆ U. We write τq, for the collection of all open subsets of a V-qmetric space (X,q), τp = τqp and τp∗ = τ(qp)∗ for a V-pseudopmetric space. Theorem 2.4. Let (V,≥,+) be a value lattice. (a) If p : X × X → V is a V-pseudopmetric, then qp is a V-qmetric. (b) For each V-qmetric, τq is a topology. For each x ∈ X, {Br(x)|r ≫ 0} and {Nr(x)|r ≫ 0}, are neighborhood bases for τq at x. For each x ∈ X,r ∈ V, N∗r (x) is a closed set in τq. Also, if r ≫ 0 then Br(x) is an open set in τq, so in particular, the set of all open balls is a base for the topology τq. Proof. (a) Certainly, if p : X × X → V is a V-pseudopmetric and q(x,y) = p(x,y) −̇ p(y,y), then q(x,x) = 0. Next, we show that if V is a value lattice and a,b,c ∈ V then (a+b) −̇ c ≤ (a −̇ c)+b. By definition of −̇ , a ≤ (a −̇ c)+c. Thus for every b ∈ V, a+b ≤ (a −̇ c)+c+b. Therefore (a+b) −̇ c ≤ (a −̇ c)+b. Now by the above for every x,y,z ∈ X, q(x,z) = p(x,z) −̇ p(z,z) ≤ (p(z,y) + (p(x,y) −̇ p(y,y))) −̇ p(z,z) ≤ (p(x,y) −̇ p(y,y)) + (p(y,z) −̇ p(z,z)) = q(x,y) + q(y,z). (b) These proofs are left to the reader. That τq is a topology, is straight- forward (or see [5]). The others use facts about the continuous lattice (V,≥), which generalize those about II: a ≪ r,s iff r ∧ s ≫ a and r,s ≥ a iff r ∧ s ≥ a. ≫ is interpolative, so if r ≫ 0 then for some s, r ≫ s ≫ 0. By Scott continuity of +, if q(x,y) ≪ r then ∧ {q(x,y)+s|s ≫ 0} = q(x,y)+ ∧ {s ≫ 0} = q(x,y) ≪ r so for some s ≫ 0, q(x,y) + s ≪ r, thus if z ∈ Ns(y) then z ∈ Br(x), so Br(x) is open. � Theorem 2.5. In any V-qmetric space, x ∈ cl(y) if and only if q(x,y) = 0. In any V-pseudopmetric space, x ∈ cl(y) if and only if p(x,y) = p(y,y). Proof. By Theorem 2.4, N∗0 (y) is closed, so cl(y) ⊆ N ∗ 0 (y). But if x 6∈ cl(y) then for some open T , x ∈ T and y 6∈ T . By Theorem 2.4, Nǫ(x) ⊆ T for some ǫ ≫ 0, thus in particular, q(x,y) 6≤ ǫ, so q(x,y) 6= 0. This shows the reverse inclusion, N∗0 (y) ⊆ cl(y). The assertion about V-pseudopmetric spaces is seen by noting that by the above, x ∈ cl(y) if and only if qp(x,y) = 0, and certainly this happens if and only if p(y,y) ≥ p(x,y), so they are equal by P1). � Corollary 2.6. For a V-qmetric, τq is T0 if and only if for each x,y ∈ X, q(x,y) = q(y,x) = 0 ⇒ x = y. A V-pseudopmetric p is a V-pmetric if and only if τp is T0. Proof. It is known that a topology is T0 if and only if, for each x,y ∈ X, x ∈ cl(y)&y ∈ cl(x) ⇒ x = y. Thus by Theorem 2.5, τq is T0 if and only if q(x,y) = q(y,x) = 0 ⇒ x = y, and so τp is T0 if and only if p(x,y) = p(y,y) = p(x,x) ⇒ x = y. � Lemma 2.7. p(x,y) = max(x,y) is an II-pmetric on II and is also a IB-pmetric on IB. Also, τp is the Scott (or upper) topology, σ = {(x,1]|x ∈ (0,1)}∪{∅,II}, and τp∗ is the lower topology, ω = {[0,x)|x ∈ (0,1)} ∪ {∅,II}. Partial metrizability in value quantales 121 Proof. Since for every x,y ∈ II, max(y,x) = max(x,y) ≥ max(x,x), p satisfies P1 and P2; also P4 is clear. For P3, if y = max(x,y,z) then p(x,z) ≤ y + p(y,z) − p(y,y) = p(x,y) + p(y,z) − p(y,y); if z = max(x,y,z) then p(x,z) ≤ p(x,y) + z − p(y,y) = p(x,y) + p(y,z) − p(y,y) and the case x = max(x,y,z) is similar. Also if p(x,x) = p(y,y), then x = y. Thus p is a II-pmetric on II. Now we show that τp = σ and τp∗ = ω: Let A ∈ τp. Then for each x ∈ A there exists r > 0 (notice that here r ≫ 0 if and only if r > 0), such that Nr(x) ⊆ A. Thus {y|x − r ≤ y} = Nr(x) ⊆ A, hence ↑ (x − r) ⊆ A. Also, if ∨ D ∈ A and D is directed, then there is some r > 0 such that Nr( ∨ D) ⊆ A, and by properties of ∨ , for some d ∈ D we have ∨ D −̇ r ≤ d, showing A ∈ σ. If x ∈ A ∈ σ, then ↑ x ⊆ A. But x = ∨ (x − 1/n) ∈ A, n ∈ IN and {x− 1/n|n ∈ IN} is a directed set, thus there is m ∈ IN such that x− 1/m ∈ A. So ↑ (x − 1/m) ⊆ A. Therefore N1/m(x) ⊆ A and hence A ∈ τp. Now let A ∈ τp∗; then for every x ∈ A there is r > 0 such that N ∗ r (x) ⊆ A. Thus {y|y < x + r/2} ⊆ {y|y − x ≤ r} = N∗r (x) ⊆ A. So (X− ↑ (x + r/2)) ⊆ A. Therefore A ∈ ω. For the reverse inclusion, assume A ∈ ω. Then for every x ∈ A there is a ∈ X such that x ∈ (X− ↑ a) ⊆ A. Thus x < a and hence r = (a − x)/2 > 0 and x ∈ N∗r (x) ⊆ A. For the assertions about IB, since IB ⊆ II, p is a IB-pmetric on IB. Note that N0(∞) = {∞} and N0(0) = N∞(x) = IB for x ∈ IB, so τp = σ, and a similar proof shows τp∗ = ω. � Lemma 2.8. If f : X → Y and p is a V-pseudopmetric on Y , then pf (x,y) = p(f(x),f(y)) defines a V-pseudopmetric on X. Also, f is continuous from (X,τ) to (Y,τp), if and only if τpf ⊆ τ. Proof. Since p is a V-pseudopmetric on Y , pf is on X. We distinguish open qp- balls in Y from open qpf -balls in X, denoting the former by B Y r (y), the latter by BXr (x). By definition of pf, B X r (x) = {y|p(f(x),f(y)) −̇ p(f(y),f(y)) ≪ r} = f−1[BYr (f(x))]. Of course, f is continuous if and only if the inverse image of each set in the base of open qp-balls is open, that is, if and only if each open qpf -ball is open; the latter occurs if and only if τpf ⊆ τ. � Recall that a bitopological space (X,τ, τ∗) is completely regular if whenever x ∈ T ∈ τ then there is a pairwise continuous f : (X,τ,τ∗) → (II,σ,ω), such that f(x) = 1 and f is 0 off T ; it is zero-dimensional if whenever x ∈ T ∈ τ then there is a pairwise continuous f : (X,τ,τ∗) → (IB,σ,ω) such that f(x) = ∞ and f is 0 off T . A bitopological space (X,τ,τ∗) is said to have a property pairwise, if both (X,τ,τ∗) and its dual, (X,τ∗,τ) have the property. Theorem 2.9. If (X,τ,τ∗) is completely regular then there is a value lat- tice V and a V-pseudopmetric such that τ = τp and τ ∗ ⊇ τp∗ . Further, if (X,τ,τ∗) is pairwise completely regular then there is a value lattice V and a V-pseudopmetric such that τ = τp and τ ∗ = τp∗ . The analogous result holds for zero-dimensionality in place of complete regularity, with Boolean value lattices. 122 R. Kopperman, S. Matthews and H. Pajoohesh Conversely, if there is a value lattice and a V-pseudopmetric such that τ = τp and τ∗ ⊇ τp∗, then (X,τ,τ ∗) is completely regular, and converses also hold in the other three cases. Throughout the above, p is a V-pmetric if and only if τ is T0. Proof. Let PC(X,II) be the collection of all pairwise continuous functions from (X,τ,τ∗) to (II,σ,ω), and define A = IIP C(X,II). With the pointwise order, A is a value lattice and for φ,ψ ∈ A, φ ≫ ψ if and only if φ(f) > ψ(f), for every f ∈ PC(X,II) and {f|φ(f) 6= 1} is finite. Now define p : X ×X → A such that p(x,y)(f) = max{f(x),f(y)} for every f ∈ PC(X,II). A coordinatewise proof then shows that p is an A-pseudopmetric on X. Now we show that τ = τp. Let T ∈ τ. If x ∈ T then there is a pairwise continuous function g : (X,τ,τ∗) → (II,σ,ω) such that g(x) = 1 and g is 0 off T . Now take r ∈ A such that r(g) = 1/2 and r(f) = 1 for f 6= g. Then Nr(x) = {y|g(y) ≥ 1/2} ⊆ T . Thus τ ⊆ τp. Now assume that T ∈ τp. For each x ∈ T , there exists r ≫ 0 such that Nr(x) ⊆ T . Let I = {f ∈ PC(X,II)|r(f) 6= 1}. Then Nr(x) = ⋂ {y|fi(x) − fi(y) ≤ r(fi)}, where i ∈ I. Hence x ∈ ⋂ {y|fi(x)−fi(y) < r(fi)/2} ⊆ Nr(x) ⊆ T , where i ∈ I. Therefore x ∈ ⋂ {y|y ∈ f−1i ((fi(x) − r(fi)/2,1])}. Since every fi is continuous, {y|y ∈ f −1 i ((fi(x) − r(fi)/2,1])} ∈ τ and since I is finite, ⋂ {y|y ∈ f−1i ((fi(x) − r(fi)/2,1])} ∈ τ. Thus T ∈ τ and by the above we now have τ = τp. Similarly τp∗ ⊆ τ ∗. For zero-dimensionality replace A by IBP C(X,IB) and proceed as in the completely regular case. In the “pairwise” cases, the above p satisfies τ = τq and τp∗ = τ ∗. For the converses, consider the relation ⊳p on subsets of X, defined by S ⊳p T ⇔ (∃r ≫ 0)(Nr(S) ⊆ T), where Nr(S) is defined to be ⋃ x∈S Nr(x). Then ⊳p can easily be seen to satisfy the properties (a1)-(a3) of an auxiliary relation given below (where (a3) results from the interpolation property of the way- below relation ≫ in the continuous lattice (V,≥)). Further, it is clear that R,S ⊳p T ⇒ R ∪ S ⊳p T , R ⊳p S,T ⇒ R ⊳p S ∩ T , ∅ ⊳p ∅ and X ⊳p X. These are the defining properties of a quasiproximity (see [3]). Each quasiproximity ⊳ has a dual, ⊳∗, defined by S ⊳∗ T ⇔ X \ T ⊳X \ S, and gives rise to a topology, τ⊳ = {T |x ∈ T ⇒ {x} ⊳ T}. Certainly, τp = τ⊳p and τp∗ = τ⊳∗p. In the reference just mentioned, Urysohn’s lemma is shown for quasiproximities; thus, if S ⊳ T then there is a pairwise continuous function f : (X,τ⊳,τ⊳∗) → ([0,1],σ,ω) such that f[S] = {1}, f[X \ T ] = {0}, and as a result, if x ∈ T ∈ τp then, letting S = {x}, there is a pairwise continuous function f : (X,τp,τp∗ ) → ([0,1],σ,ω) such that f(x) = 1 and f[X \ T ] = {0}; the same then holds for (X,τp∗,τp) using ⊳∗. This yields the results for complete regularity and pairwise complete regularity, and those involving 0-dimensionality are simpler, since in this case, for each x ∈ X, r ≫ 0, the function defined by f(y) = { 1 y ∈ Nr(x) 0 y 6∈ Nr(x) , is pairwise continuous from (X,τp,τp∗) to ({0,1},σ,ω). The last statement is immediate from Corollary 2.6. � If ≤ is a transitive, reflexive relation on X (= a pre-order) then the Alexan- droff topology is α(≤) = {T ⊆ X|x ∈ T & x ≤ y ⇒ y ∈ T}. Partial metrizability in value quantales 123 Theorem 2.10. (a) For any topology τ, (X,τ,α(≥τ )) is pairwise 0-dimensional. Thus there is a Boolean value lattice V and a V-pseudopmetric such that τ = τp. (b) For each continuous bounded dcpo, there is a value lattice V and a V- pmetric such that its Scott topology, σ, is τp and its lower topology, ω, is τp∗ . If the dcpo is algebraic as well, then V can be assumed Boolean. Proof. (a) Notice that U ∈ α(≥τ) if and only if x ∈ U and y ∈ cl({x}) imply that y ∈ U. Now consider x ∈ T ∈ τ then define f : (X,τ,α(≥τ)) → (IB,σ,ω) such that f = ∞ on T and f = 0 on X \T . Since T ∈ τ implies X \T ∈ α(≥τ ), f is pairwise continuous. Now let x ∈ U ∈ α(≥τ ). Since (X \ cl({x})) ∈ τ, cl({x}) ∈ α(≥τ). Define f : (X,α(≥τ),τ) → (IB,σ,ω) by f = ∞ on cl({x}) and f = 0 on X \ cl({x}). By the construction, f is pairwise continuous. (b) For each continuous bounded dcpo, (P,σ,ω) is pairwise completely regu- lar and σ is T0 (see [3]); additionally if P is algebraic, then (P,σ,ω) is pairwise 0-dimensional, using the fact that for compact x, ↑ x =⇑ x, so a base for the open sets in σ is a subbase for the closed sets in ω. � 3. Value quantales First, we recall the definition and a few basic properties of value quantales from [2]. Assume V is a complete lattice. Then V is completely distributive if for any family {xi,j | j ∈ J,k ∈ Kj} of elements of V , ∧ j∈J ∨ k∈Kj xj,k = ∨ f∈M ∧ j∈J xj,f(j), where M = ∏ j∈J Kj. Assume V is a complete lattice and p,q ∈ V . Then q is well above p, denoted by q ≻ p, iff for any subset S ⊆ V , if p ≥ ∧ S, then for some r ∈ S, q ≥ r. Raney ([8]) has shown that a complete lattice is completely distributive if and only if each p = ∧ {q | q ≻ p }. This is the criterion we shall use below. The “way-above” relation ≫ for a continuous lattice (L,≥) and ≻ on a completely distributive lattice (V,≥) differ in that for the former (unlike the latter), the set S must be directed (by ≥). Like ≫, ≻ satisfies most of the axioms for an auxiliary relation, ⊲ on a poset (P,≥): if p,q,r,s ∈ P and S ⊆ P , • (a1) q ⊲ p implies q ≥ p; • (a2) s ≥ q, q ⊲ p and p ≥ r implies s ⊲ r; and • (a3) (Interpolation Property) If q ⊲ p, then for some r, q ⊲ r and r ⊲ p. Property (a3) is more special, and holds for ≫ in any continuous lattice (L,≥) ([4]), and for ≻ in any completely distributive lattice (V,≥) ([8]). The definitions of completely distributive lattice (for ≻) and continuous lattice (for ≫) amount to the statement that the relation is approximating: • (a4) Each p is the inf, ∧ {r|r ⊲ p}. For an arbitrary set in a completely distributive lattice, q ≻ ∧ S iff for some r ∈ S, q ≥ r, and for directed set D in a continuous lattice, that q ≫ ∧ D iff for some r ∈ D, q ≥ r. 124 R. Kopperman, S. Matthews and H. Pajoohesh However, many auxiliary relations, like ≫, are subdirecting : for each x ∈ X, {y|y ⊲ x} is directed by ≥. This need not hold for ≻; for example, in IBF r ≻ 0 if and only if, there is at most one f such that r(f) < ∞, and this collection is clearly not directed. But we need this property for 0: A value distributive lattice is a completely distributive lattice V satisfying the following two conditions: • (v1) ∞ 6= 0. • (v2) If p ≻ 0 and q ≻ 0, then p ∧ q ≻ 0. A value quantale V =< V,≤,+ > consists of a value distributive lattice < V,≤> and an operation + on V satisfying definition 1. We now describe a special case of the construction of value quantale from [2]. Assume (L,≥) is a continuous lattice in which ⊥6= ⊤, and let A = A(L) = {x ∈ L | x ≫ ⊥}, where ≫ denotes the way-above relation on L. Then ⊤ ∈ A and if a,b ∈ A, then a∧b ∈ A. By a round upper set in L, we mean a nonempty I ⊆ A for which: (r1) j ≥ k ∈ I ⇒ j ∈ I, and (r2) (∀j ∈ I) ⇓ j ∩ I 6= ∅. (Note in particular, that we do not require that I be directed by ≥.) Let R = (R[L],⊇) denote the poset of round upper sets in L, with reverse set in- clusion. Since R is an inf-closed subset of (2A,⊇)(∼= (IB A,≥)), R is a complete lattice with ∧ S = ⋃ S ∪ {⊤}. For a ∈ L, define θ(a) = {x ∈ A|x ≫ a}. Then θ(a) ∈ R and for a ∈ A, and I ∈ R, notice that a ∈ I ⇒ θ(a) ≻ I, since if a ∈ I ≥ ∧ S then a ∈ I ⊆ ⋃ S so for some J ∈ S, a ∈ J, showing θ(a) ⊆ J, thus θ(a) ≥ J. Thus I = ⋃ {θ(a)|a ∈ I} ⊆ ⋃ {J ≻ I} ⊆ ⋃ {J ⊆ I} = I, so in particular, each I = ∧ {J ≻ I}, thus R is completely distributive by Raney’s result. Also note that if J ≻ I then for some a ∈ I, J ≥ θ(a), that is, J ⊆ θ(a); this with the previous paragraph shows J ≻ I ⇔ (∃a ∈ I)J ⊆ θ(a). Here are some other properties of θ that we need later: (θ1) θ preserves direct inf: For let D be directed by ≥. Then for x ∈ A, x ∈ θ( ∧ D) ⇔ x ≫ ∧ D ⇔ for some y ∈ L, x ≫ y ≫ ∧ D ⇔ for some z ∈ L there is a d ∈ D such that x ≫ z ≥ d ⇔ there is a d ∈ D such that x ≫ d ⇔ x ∈ ⋃ d∈D θ(d) = ∧ θ[D]. Hence ∧ θ[D] = θ( ∧ D) as required. (θ2) For each a,b ∈ L, a ≥ b ⇔ θ(a) ≥ θ(b): If a ≥ b then b = ∧ {a,b} a directed set, so by θ1, θ(b) = ∧ {θ(a),θ(b)} ≤ θ(a). Conversely, if θ(a) ≥ θ(b), then {x|x ≫ a} ⊆ {x|x ≫ b}, so ∧ {x|x ≫ a} ≥ ∧ {x|x ≫ b}. But since L is a continuous lattice, a = ∧ {x|x ≫ a} and b = ∧ {x|x ≫ b}. Hence a ≥ b. In R, clearly the smallest element, called 0, is A and the largest, ∞, is {⊤}. The two differ, since ⊥6= ⊤, so by (a4), for some a 6= ⊤, a ≫⊥; thus a ∈ A so 0 6= {⊤} = ∞. Note also that if I,J ≻ 0 then for some a,b ∈ A we have I ⊆ θ(a), J ⊆ θ(b) so I,J ⊆ θ(a∧b), and a∧b ∈ A, showing that I,J ≥ θ(a∧b) ≻ 0. Thus {I ≻ 0} is ≥-directed, so that R is a value distributive lattice in the terminology of [2]. Partial metrizability in value quantales 125 Now suppose that ⋆ : L × L → L is a binary operation on L such that (L,⋆,⊥) is a commutative monoid and for any a ∈ L, the function a⋆ : L → L preserves infs and the way above relation; that is, any indexed family {bi}i∈I in L, a⋆ ∧ i∈I bi = ∧ i∈I(a⋆bi), and whenever b ≫ b ′, then a⋆b ≫ a⋆b′. Then ⋆ : A × A → A. For I,J ∈ R, define I + J = {a|(∃x ∈ I,y ∈ J)a ≥ x ⋆ y}. Clearly, + is associative, commutative and monotone. Also 0 is a unit for +, because of the following: If a ∈ I + A then for some x ∈ I and y ∈ A, a ≥ x ⋆ y. Thus a ≥ x ⋆ y ≥ x⋆ ⊥= x, and since I is an upper set, a ∈ I. For the reverse set inclusion, if a ∈ I then by (r2) there is m ∈ I such that a ≫ m. Thus a ≫ m = m⋆ ⊥= m ⋆ ∧ k≫⊥ k = ∧ k≫⊥ m ⋆ k. Thus there is k0 ≫⊥ such that a ≥ m ⋆ k0. Hence a ∈ I + A. Thus I + A = I for every I. Note also that for S ⊆ R and I ∈ R, I + ∧ S = I + ⋃ (S ∪ {⊤}) = {a|(∃x ∈ I,y ∈ J ∈ S ∪ {⊤})(a ≥ x ⋆ y)} = ⋃ J∈S∪{⊤}{a|(∃x ∈ I,y ∈ J)(a ≥ x ⋆ y)} = ⋃ J∈S∪{⊤}(I + J) = ∧ J∈S(I + J), so (R,+) is a value quantale. Further: (θ3) Each θ(a ⋆ b) = θ(a) + θ(b). For if t ∈ θ(a) + θ(b) then (∃x ∈ θ(a),y ∈ θ(b))t ≥ x⋆y thus t ≥ x⋆y ≫ a⋆b, hence t ∈ θ(a⋆b). But if t ∈ θ(a⋆b). Then t ≫ a ⋆ b = ∧ {x ⋆ y|x ≫ a,y ≫ b}. Thus by definition of ≫ there are w ≫ a and v ≫ b such that t ≥ w ⋆ v. Therefore t ∈ θ(a) + θ(b). As a result of this and θ2, we also have: (θ4) For each a,b,c ∈ L, a − ⋆b ≤ c ⇔ θ(a) −̇ θ(b) ≤ θ(c), since a −⋆b ≤ c ⇔ a ≤ b ⋆ c ⇔ θ(a) ≤ θ(b ⋆ c) = θ(b) + θ(c) ⇔ θ(a) −̇ θ(b) ≤ θ(c) We have two special cases in mind: Assume K is a nonempty set and let IF be (II,≤,+) (with truncated addition + as introduced preceding Definition 1) or (IB,≤,+). Let K be any nonempty set. Then as a product of continuous lattices, L = IFK is also a continuous lattice with the pointwise order, and in it, a ≫⊥ if and only if for each i ∈ K, a(i) ≫⊥i and for all but a finite number of i, a(i) = ⊤i. Thus in particular, for IF = IB, A = {r ∈ IB K|r−1[{∞}] is cofinite}, and for IF = II, A = {r ∈ [0,1)K|r−1[{1}] is cofinite}. Let ⋆ be pointwise addition; certainly ⋆ is in both cases an associative, commutative operation preserving ≤ and ≫, for which 0 is the unit, since these all hold coordinatewise. Thus ⋆ obeys the assumptions made of it, so (R[IFK],+) is a value quantale. Following [2], we call the R[IBK] the value quantales of subsets, and denote them by Γ(K), and we call the R[IIK] the value quantales of fuzzy subsets, and denote them by Λ(K). One special property of Γ(K) worth noting is that (r2) is trivial, since for r ∈ A, it is easy to see that r ≫ r; for Λ(K) it is worth noticing for (r2) that for r,s ∈ A, r ≫ s if and only if r(i) > s(i) whenever r(i) 6= 1. Theorem 3.1. In theorem 2.9 and its corollaries, “value lattice” can be im- proved to “value quantale”. Proof. By Theorem 2.9, for K = PC(X,IF) there is a K-pseudopmetric p such that τ = τp and τ ∗ ⊇ τp∗ . Let θ : K → R[IF K] be as defined above. In addition to the properties already established, notice that θ(0) = 0 and θ(∞) = ∞. 126 R. Kopperman, S. Matthews and H. Pajoohesh We finish the proof by showing that for the R[IFK]-pseudopmetric d = θ ◦ p, τd = τp and τd∗ = τp∗ . For suppose T ∈ τp; if x ∈ T then for some r ≫ 0, Nr(x) ⊆ T . But r ∈ A(IFK) so θ(r) ≻ A(IFK), the 0 of R[IFK]. Further, if y ∈ Nθ(r)(x), we have qd(x,y) ≤ θ(r) so θ(p(x,y)) −̇ θ(p(y,y)) ≤ θ(r), thus by (θ4), p(x,y) −̇ p(y,y) = qp(x,y) ≤ r, showing y ∈ T . This shows Nθ(r)(x) ⊆ T , so T ∈ τd. Conversely, suppose T ∈ τd; if x ∈ T then for some s ≻ 0, s ∈ R[IF K], Ns(x) ⊆ T . By the beginning of the discussion of θ there is an r ∈ K, r ≫ 0, so that θ(r) ≤ s. If qp(x,y) ≤ r then p(x,y) −̇ p(y,y) ≤ r, thus θ(p(x,y)) −̇ θ(p(y,y)) ≤ θ(r) ≤ s, so y ∈ T . This shows Nr(x) ⊆ T , so T ∈ τp. The above show that τp = τd, and a similar proof shows that τp∗ = τd∗. This completes the proof that throughout Theorem 2.9, the value lattice IFK and pseudopmetric p can be replaced by the value quantale R[IFK] and pseu- dopmetric d. � References [1] K. Ciesielski, R.C. Flagg, and R.D. Kopperman, Characterizing topologies with bounded complete computational models, Electron. Notes Theor. Comput. Sci. 20 (1999), 11 pages. [2] R.C. Flagg and R.D. Kopperman, Continuity spaces: reconciling domains and metric spaces, Theor. Comput. Sci. 177 (1997), 111-138. [3] R.C. Flagg and R.D. Kopperman, Tychonoff poset structures and auxiliary relations, Ann. New York Acad. Sci. 767 (Andima et. al., eds.) (1995), 45–61. [4] G.K. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M.W. Mislove and D.S. Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin, 1980. [5] R. D. Kopperman, All Topologies Come From Generalized Metrics, Am. Math. Monthly 95 (1988), 89–97. [6] Matthews, S.G., An extensional treatment of lazy data flow deadlock, Theoretical com- puter science, 151, (1995), 195–205. [7] Matthews, S.G., Partial metric topology, Proc. 8th summer conference on topology and its applications, ed S. Andima et al., Annals of the New York Academy of Sciences, New York, 728, (1994) 183–197. [8] G.N. Raney, Completely Distributive Lattices, Proc. Amer. Math. Soc., 3 (1952), 677– 680. [9] Stoy, Joseph E., Denotational semantics: the Scott-Strachey approach to programming language theory, The MIT Press, Cambridge, Massachusetts, and London, England, 1977 [10] Wadge, W.W., An extensional treatment of dataflow deadlock, Theoretical computer science, 13(1), (1981) 3–15. Received March 2003 Accepted June 2003 R. D. Kopperman (rdkcc@cunyvm.cuny.edu) Partial metrizability in value quantales 127 Department of Mathematics, City College, City University of New York, New York, NY 10031, USA. Department of Computer Science, University of Birmingham, UK. S. G. Matthews (sgm@dcs.warwick.ac.uk) Department of Computer Science, University of Warwick Coventry, CV4 7AL, UK. H. Pajoohesh (h pajoohesh@yahoo.com) Department of Mathematics Shahid Beheshti University Teheran 19839, IRAN. BCRI and CEOL, University College Cork, (Unit 2200, Cork Airport Business Park, Kinsale Road, Co. Cork), Ireland Department of Computer Science, University of Birmingham, UK.