陳金鑫

(四川大學數(shù)學學院， 成都 610064)

1 Introduction

By a generalized metric on a setXwe mean a mapd:X×X→[0,∞] such thatd(x,x)=0 for allx∈Xandd(x,y)+d(y,z)≥d(x,z) for allx,y,z∈X. The pair (X,d) is called a generalized metric space. Such a space is also called a quasi-pseudo-metric[1]or a hemi-metric[2]. In 1973, Lawvere[3]observed that a generalized metric space is precisely a category enriched over the symmetric monoidal closed category ([0,∞]op,+,0). In this note, following Lawvere, such a space is called a metric space instead of a generalized metric space.

Metric spaces can be thought of as real-valued (precisely,[0,∞]-valued) ordered sets. Yoneda complete metric spaces are then a metric analogy of directed complete partially ordered sets, so, they are the core subject of Quantitative Domain Theory[1-2,4]. Quantitative domain theory is a new branch of domain theory and has undergone active research in the past three decades. The field concerns both the semantics of programming languages and the mathematical field of topology. A basic result in domain theory is that the category dcpo of directed complete partially ordered sets is both complete and cocomplete[5]. It is natural to ask whether this is still true for Yoneda complete metric spaces. The fact that there exist different choices of morphisms for Yoneda complete metric spaces makes the problem more complicated. In this paper, we investigate the completeness and cocompleteness of the following categories:

·[0,∞]-dcpo: the category of Yoneda complete and separated metric spaces and Yoneda continuous non-expansive maps;

·YcMet: the category of Yoneda complete and separated metric spaces and Yoneda continuous maps;

·LipYcMet: the category of Yoneda complete and separated metric spaces and Yoneda continuous Lipschitz maps;

·[0,∞]-CL: the category of [0,∞]-valued continuous lattices and Yoneda continuous right adjoints.

It is shown that the categories[0,∞]-dcpo and YcMet are both complete and cocomplete; the category LipYcMet is finitely complete and cocomplete, but neither complete nor cocomplete; the category [0,∞]-CL is complete. These results are helpful in the development of quantitative domain theory.

2 Preliminaries

A metric on a setXis a mapd:X×X→[0,∞] such thatd(x,x)=0 for allx∈Xandd(x,y)+d(y,z)≥d(x,z) for allx,y,z∈X. The pair (X,d) is called a metric space. In this note, in order to simplify notations, we writeXfor the pair (X,d) and writeX(x,y) ford(x,y). A metric spaceXis separated if for allx,y∈X,X(x,y)=X(y,x)=0 implies thatx=y.

Example2.1For allr,s∈[0,∞], let

dL(r,s)=max{s-r,0},dR(r,s)=max{r-s,0}.

Then both([0,∞],dL) and ([0,∞],dR) are separated metric spaces.

Given a metricspaceX, the underlying order ofXis the order ≤ defined byx≤yifX(x,y)=0. We writeX0for the setXequipped with the underlying order.

Letf:X→Ybe a map between metric spaces. We sayf:X→Yis non-expansive ifX(x,y)≥Y(f(x),f(y)) for allx,y∈X,f:X→Yis Lipschitz if there is somec>0 such thatcX(x,y)≥Y(f(x),f(y)) for allx,y∈X. It is clear that a non-expansive map is precisely a 1-Lipschitz map.

Letf:X→Yandg:Y→Xbe non-expansive maps. We say thatfis left adjoint tog, orgis right adjoint tof[6], ifY(f(x),y)=X(x,g(y)) for allx∈Xandy∈Y.

The argument of Ref.[7, Proposition 3.1] gives a proof of the following useful conclusion.

Proposition2.2Letf:X→Yandg:Y→Xbe non-expansive maps. Thenfis left adjoint togif and only if, as order-preserving maps,f:X0→Y0is left adjoint tog:Y0→X0.

LetXbe a metric space. A weight (a.k.a. a left module)[3]ofXis a functionφ:X→[0,∞] such thatφ(x)≤φ(y)+X(x,y) for allx,y∈X. A coweight ofXis a functionψ:X→[0,∞] such thatψ(y)≤ψ(x)+X(x,y) for allx,y∈X.

The weights ofXcan be thought of as lower fuzzy sets whenXis viewed as a real-valued ordered set. Dually, coweights can be thought as an upper fuzzy sets[8-9].

The set of all weights of a metric spaceXis denoted byPX. For anyφ,ψ∈PX, let

ThenPXbecomes a metric space.

The set of all coweights is denoted byP?X. For anyφ,ψ∈P?X, let

ThenP?Xbecomes metric space.

Definition2.3[4,10]Given a metric spaceXand a weightφofX, a colimit ofφis an element colimφ∈Xsuch that for allx∈X,

X(colimφ,x)=PX(φ,X(-,x)).

Dually, by a limit of a coweightψofXwe mean an element limψ∈Xsuch that for allx∈X,

X(x,limψ)=P?X(X(x,-),ψ).

A metric spaceXis said to be cocomplete if and only if each weight ofXhas a colimit.Xis said to be complete if and only if each coweight ofXhas a limit. It is known thatXis complete if and only if it is cocomplete and the underlying order of a complete metric space is complete[11].

Definition2.4[4,12]A net {xi}i∈Iin a metric spaceXis forward Cauchy if

An elementx∈Xis a Yoneda limit of a forward Cauchy net {xi}i∈Iif for ally∈X,

A metric space is Yoneda complete if every forward Cauchy net has a Yoneda limit.

It is known that the underlying order of a Yoneda complete metric space is directed complete, see Ref.[13, Proposition 4.5].

Corollary2.6A metric spaceXis Yoneda complete if and only if the map

y:X→FX,xX(-,x)

has a left adjoint, denoted by colim:FX→X.

The mapy:X→FXis known as the Yoneda embedding.

Example2.7[2]Both of the metric spaces ([0,∞],dL) and ([0,∞],dR) in Example 2.1 are Yoneda complete.

Yoneda complete metric spaces are a metric version of directed complete partially ordered sets. In this note we are concerned with the completeness and cocompleteness of some categories of such spaces with different kinds of morphisms.

Definition2.8A mapf:X→Ybetween metric spaces is Yoneda continuous if for each forward Cauchy net {xi}i∈IinXand each Yoneda limitxof {xi}i∈I, {f(xi)}i∈Iis a forward Cauchy net inYwithf(x) as a Yoneda limit.

It is trivial that each Lipschitz mapf:X→Ymaps a forward Cauchy net inXto a forward Cauchy net inY.

3 Main results

Proposition3.1The category [0,∞]-dcpo of Yoneda complete and separated metric spaces and Yoneda continuous non-expansive maps is complete.

ProofIt suffices to check that [0,∞]-dcpo has products and equalizers.

ThenXis Yoneda complete and Yoneda limits inXare computed componentwise by Ref.[2, Lemma 7.4.13]. It is clear thatXis a product of (Xj)j∈Jin [0,∞]-dcpo, hence [0,∞]-dcpo has products.

E={x∈X∣f(x)=g(x)}

ofXwith the embedding mapi:E→Xis easily verified to be an equalizer offandg. So [0,∞]-dcpo has equalizers.

Proposition3.2The category [0,∞]-dcpo is cocomplete.

ProofSince [0,∞]-dcpo is complete, then by Ref.[16,Theorem 23.14], it is sufficient to show that [0,∞]-dcpo is well-powered and has a coseparator.

First, we show that [0,∞]-dcpo is well-powered. It suffices to show that every monomorphismf:X→Yin [0,∞]-dcpo is injective. Suppose thatf(a)=f(b). Let * be a singleton metric space andg,h:*→Xbe given byg(*)=aandh(*)=b. Sincefg(*)=fh(*), it follows thata=g(*)=h(*)=b, which shows thatfis injective.

Without loss of generality, we assume thatY(f(x),g(x))≠0. Defineh:Y→[0,∞] byh(y)=Y(y,g(x)). Thenhf(x)≠hg(x). It remains to show thathis non-expansive and Yoneda continuous. For ally1,y2∈Y,

dR(h(y1),h(y2))=

Y(y1,g(x))?Y(y2,g(x))≤Y(y1,y2),

dR(h(y),r)=Y(y,g(x))?r=

Sohis Yoneda continuous.

Remark1The requirement that the metric spaces being separated is not essential in the above proposition. A very minor improvement of the argument shows that the category of Yoneda complete maps is both complete and cocomplete. This remark also applies to other conclusions in this note.

Proposition3.3The category YcMet of Yoneda complete and separated metric spaces and Yoneda continuous maps is complete and cocomplete.

The proof is similar to that of Proposition 3.1 and Proposition 3.2, so it is omitted here.

Proposition3.4The category LipYcMet of Yoneda complete and separated metric spaces and Yoneda continuous Lipschitz maps is both finitely complete and finitely cocomplete.

ProofSince the singleton metric space is a terminal object and the empty space is an initial object in LipYcMet, it suffices to check that LipYcMet has binary products, equalizers, binary coproducts and coequalizers. That LipYcMet has binary products and equalizers can be verified in a way similar to that of Proposition 3.1.

LetA,Bbe two Yoneda complete metric spaces. EquipC=AB(the disjoint union ofAandB) with the metric

Then,Cis a Yoneda complete metric space by Ref.[2，Lemma 7.4.12]. It is easy to see thatCis a coproduct ofAandB.

,

Sinceh:(Y,dY/c)→(A,dA/cc3) is non-expansive and Yoneda continuous, there exists a unique non-expansive and Yoneda continuous maps:(C,dC)→(A,dA/cc3) such thath=sπ. It is trivial thats:(C,dC)→(A,dA) is the unique Lipschitz and Yoneda continuous map satisfying thath=sπ.

Proposition3.5The category LipYcMet is neither complete nor cocomplete.

ProofLetXn=([0,∞],dL) for eachn∈N. We show that the family (Xn)n∈Ndoes not have a product in LipYcMet, hence LipYcMet is not complete.

kcn=kcnXn(a,b)≥kC(fn(a),fn(b))≥

dL(hfn(a),hfn(b))=

dL(gn(a),gn(b))=ncn,

which shows thatk=∞, a contradiction.

Finally, we discuss the completeness of a subcategory of [0,∞]-dcpo. This subcategory is a metric version of that of continuous lattices. Before introducing this subcategory, we need some preparation.

By Corollary 2.6, a metric spaceXis Yoneda complete if and only if the Yoneda embeddingy:X→FXhas a left adjoint.

Definition3.6[17]A metric spaceXis said to be a [0,∞]-domain (or real-valued domain) if it is Yoneda complete and is continuous in the sense that the left adjoint colim:FX→Xof the Yoneda embeddingy:X→FXhas a left adjoint, which will be denoted by:X→FX.

Proposition3.7[18]Every retract of a [0,∞]-domain in [0,∞]-dcpo is a [0,∞]-domain.

A separated and complete[0,∞]-domain is said to be a real-valued continuous lattice (or, a [0,∞]-continuous lattice). Write [0,∞]-CL for the category having real-valued continuous lattices as objects and Yoneda continuous right adjoints as morphisms. It is clear that [0,∞]-CL is the counterpart of the category CL[19]of continuous lattices in the metric setting.

Proposition3.8[20]Real-valued continuous lattices are exactly retracts of powers of the metric space ([0,∞],dL) in the category [0,∞]-dcpo.

Proposition3.9The category [0,∞]-CL is complete.

E={x∈X∣f(x)=g(x)}

ofXwith the embedding mapi:E→Xis an equalizer off,g. Since bothfandgare right adjoints, they preserve limits[11]. So the subspaceEis closed inXwith respect to limits. Hence it is complete.

Since the embeddingi:E→Xpreserves limits andEis complete,ihas a left adjoint Ref.[11, Proposition 6.8], say,h:X→E. Then.

·iis Yoneda continuous, since bothfandgare Yoneda continuous, henceEis closed with respect to Yoneda limits;

·his Yoneda continuous, since every left adjoint is Yoneda continuous;

·hi=idE, sinceh:X0→E0is left adjoint toi:E0→X0, henceh(x) is the meet of {e∈E∣x≤e} inE0, sohi(e)=efor alle∈E.

ThusEis a retract ofXin [0,∞]-dcpo, hence a [0,∞]-domain by Proposition 3.7. ThereforeEis an equalizer offandgin [0,∞]-CL.