On the Yoneda completion of a quasi-metric space

AbstractSeveral theories aimed at reconciling the partial order and the metric space approaches to Domain Theory have been presented in the literature (e.g. Flagg and Kopperman, Theoret. Comput. Sci. 177 (1) (1997) 111–138; Bonsangue et al., Theoret. Comput. Sci. 193 (1998) 1–51; Symth, Quasi-Uniformities: Reconciling Domains with Metric Spaces, Lectures Notes in Computer Science, vol. 298, Springer, Berlin, 1987, pp. 236–253; Wagner, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh, July 1994, Technical Report CMU-CS-94-159). We focus in this paper on two of these approaches: the Yoneda completion of generalized metric spaces of (Bonsangue et al., Theoret. Comput. Sci 193 (1998) 1–51) which finds its roots in work by Lawvere (Lawvere, Rend. Sem. Mat. Fis. Milano 43 (1973) 135–166; cf. also Wagner, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh, July 1994, Technical Report CMU-CS-94-159) and which is related to early work by Stoltenberg (e.g. Stoltenberg, Proc. London. Math. Soc. (3) 17 (1967) 226–240; Stoltenberg, Proc. Amer. Math. Soc. 18 (1967) 864–867 and Ferrer and Gregori, Proc. London Math. Soc. (3) 49 (1984) 36), and the Smyth completion (Smyth, Quasi-Uniformities: Reconciling Domains with Metric Spaces, Lecture Notes in Computer Science, vol. 298, Springer, Berlin, 1987, pp. 236–253; Smyth, In: G.M. Reed, A.W. Roscoe, R.F. Wachter (Eds.), Topology and Category Theory in Computer Science, Oxford University Press, Oxford, 1991, pp. 207–229; Smyth, J. London Math. Soc. 49 (1994) 385–400; Sünderhauf, In: M. Droste, Y. Gurevich (Eds.), Semantics of Programming Languages and Model Theory, Algebra, Logic and Applications, vol. 5, Gordon and Breach, London, 1993, pp. 189–212; Sünderhauf, Acta Math. Hungar. 69 (1995) 47–54). A net-version of the Yoneda completion, complementing the net-version of the Smyth completion (Sünderhauf, Acta. Math. Hungar. 69 (1995) 47–54), is given and a comparison between the two types of completion is presented. The following open question is raised in Bonsangue et al. (Theoret. Comput. Sci. 193 (1998) 1–51): “An interesting question is to characterize the family of generalized metric spaces for which [the Yoneda] completion is idempotent (it contains at least all ordinary metric spaces)”. We show that the largest class of quasi-metric spaces idempotent under the Yoneda completion is precisely the class of Smyth-completabe spaces. A similar result has been obtained independently by Flagg and Sünderhauf in Flagg and Sünderhauf (preprint, available at: ftp://theory.doc.ic.ac.uk/theory/papers/Sunderhauf/eicqf.ps). 22We are grateful to the authors of Bonsangue et al. (Theoret. Comput. Sci. 193 (1998) 1–51) for pointing out this prior work. We present an entirely new proof of the result via concrete standard techniques and compare this approach with the more abstract categorical machinery of Flagg and Sünderhauf (preprint, available at: ftp://theory.doc.ic.ac.uk/theory/papers/Sunderhauf/eicqf.ps). Our proof is based on a new characterization of Smyth-completability of quasi-metric spaces in terms of sequences, which considerably simplifies prior characterizations for quasi-uniform spaces (e.g. Sünderhauf, In: M. Droste, Y. Gurevich (Eds.), Semantics of Programming Languages and Model Theory, Algebra, Logic and Applications, vol. 5, Gordon and Breach, London, 1993, pp. 189–212; Sunderhauf, Acta Math. Hungar. 69 (1995) 715–720) We also show that the ideal completion, and hence the Yoneda completion and the Smyth completion, are not sequentially adequate in general. The study of the properties of total boundedness, precompactness, hereditary precompactness and compactness is motivated and we analyze the preservation of these properties under the two kinds of completion in the possible absence of idempotency