* [CSTZ22] Sitan Chen, Zhao Song, Runzhou Tao, and Ruizhe Zhang.  Symmetric sparse boolean matrix factorization and applications.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, pages 46:1–46:25, 2022.
  * [CW13] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference, STOC, pages 81–90, 2013.
  * [DG17] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * [DHJ+18] Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou.  Low rank approximation of binary matrices: Column subset selection and generalizations.  In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 41:1–41:16, 2018.
  * [DMM06a] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.  Subspace sampling and relative-error matrix approximation: Column-based methods.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX and 10th International Workshop on Randomization and Computation, RANDOM, Proceedings, pages 316–326, 2006.
  * [DMM06b] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.  Subspace sampling and relative-error matrix approximation: Column-row-based methods.  In Algorithms - ESA 2006, 14th Annual European Symposium, Proceedings, pages 304–314, 2006.
  * [FGL+20] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Approximation schemes for low-rank binary matrix approximation problems.  ACM Trans. Algorithms, 16(1):12:1–12:39, 2020.
  * [FJS10] Yinghua Fu, Nianping Jiang, and Hong Sun.  Binary matrix factorization and consensus algorithms.  In 2010 International Conference on Electrical and Control Engineering, pages 4563–4567. IEEE, 2010.
  * [FMPS09] Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider.  Covering graphs with few complete bipartite subgraphs.  Theor. Comput. Sci., 410(21-23):2045–2053, 2009.
  * [FSS20] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering.  SIAM J. Comput., 49(3):601–657, 2020.
  * [GGYT12] Harold W. Gutch, Peter Gruber, Arie Yeredor, and Fabian J. Theis.  ICA over finite fields - separability and algorithms.  Signal Process., 92(8):1796–1808, 2012.
  * [GV18] Nicolas Gillis and Stephen A. Vavasis.  On the complexity of robust PCA and $\ell_{1}$-norm low-rank matrix approximation.  Math. Oper. Res., 43(4):1072–1084, 2018.
  * [JPHY14] Peng Jiang, Jiming Peng, Michael Heath, and Rui Yang.  A clustering approach to constrained binary matrix factorization.  In Data Mining and Knowledge Discovery for Big Data, pages 281–303. Springer, 2014.
  * [KG03] Mehmet Koyutürk and Ananth Grama.  PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 147–156, 2003.
  * [KK03] Qifa Ke and Takeo Kanade.  Robust subspace computation using l1 norm, 2003.
  * [KK05] Qifa Ke and Takeo Kanade.  Robust $l_{1}$ norm factorization in the presence of outliers and missing data by alternative convex programming.  In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pages 739–746, 2005.
  * [KMN+04] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu.  A local search approximation algorithm for k-means clustering.  Comput. Geom., 28(2-3):89–112, 2004.
  * [KPRW19] Ravi Kumar, Rina Panigrahy, Ali Rahimi, and David P. Woodruff.  Faster algorithms for binary matrix factorization.  In Proceedings of the 36th International Conference on Machine Learning, ICML, pages 3551–3559, 2019.
  * [KV09] Ravi Kannan and Santosh S. Vempala.  Spectral algorithms.  Found. Trends Theor. Comput. Sci., 4(3-4):157–288, 2009.
  * [Kwa08] Nojun Kwak.  Principal component analysis based on l1-norm maximization.  IEEE transactions on pattern analysis and machine intelligence, 30(9):1672–1680, 2008.
  * [LSW17] Euiwoong Lee, Melanie Schmidt, and John Wright.  Improved and simplified inapproximability for k-means.  Inf. Process. Lett., 120:40–43, 2017.
  * [LVAH12] Haibing Lu, Jaideep Vaidya, Vijayalakshmi Atluri, and Yuan Hong.  Constraint-aware role mining via extended boolean matrix decomposition.  IEEE Trans. Dependable Secur. Comput., 9(5):655–669, 2012.
  * [Mag10] Malik Magdon-Ismail.  Row sampling for matrix algorithms via a non-commutative bernstein bound.  CoRR, abs/1008.0587, 2010.
  * [Mah11] Michael W. Mahoney.  Randomized algorithms for matrices and data.  Found. Trends Mach. Learn., 3(2):123–224, 2011.
  * [MKP14] Panos P. Markopoulos, George N. Karystinos, and Dimitrios A. Pados.  Optimal algorithms for $l_{1}$-subspace signal processing.  IEEE Trans. Signal Process., 62(19):5046–5058, 2014.
  * [MMG+08] Pauli Miettinen, Taneli Mielikäinen, Aristides Gionis, Gautam Das, and Heikki Mannila.  The discrete basis problem.  IEEE transactions on knowledge and data engineering, 20(10):1348–1362, 2008.
  * [MMM+22] Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou.  Fast regression for structured inputs.  In The Tenth International Conference on Learning Representations, ICLR, 2022.
  * [MMM+23] Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou.  Near-linear sample complexity for $l_{p}$ polynomial regression.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3959–4025, 2023.
  * [MMWY22] Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda.  Active linear regression for $\ell_{p}$ norms and beyond.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 744–753, 2022.
  * [MW21] Arvind V. Mahankali and David P. Woodruff.  Optimal $\ell_{1}$ column subset selection and a fast PTAS for low rank approximation.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 560–578, 2021.
  * [Neu18] Stefan Neumann.  Bipartite stochastic block models with tiny clusters.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, pages 3871–3881, 2018.
  * [Orl77] James Orlin.  Contentment in graph theory: covering graphs with cliques.  Indagationes Mathematicae (Proceedings), 80(5):406–424, 1977.
  * [PK18] Young Woong Park and Diego Klabjan.  Three iteratively reweighted least squares algorithms for $l_{1}$-norm principal component analysis.  Knowledge and Information Systems, 54(3):541–565, 2018.
  * [PPP21] Aditya Parulekar, Advait Parulekar, and Eric Price.  L1 regression with lewis weights subsampling.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 49:1–49:21, 2021.
  * [PRF15] Amichai Painsky, Saharon Rosset, and Meir Feder.  Generalized independent component analysis over finite alphabets.  IEEE Transactions on Information Theory, 62(2):1038–1053, 2015\.
  * [PRF18] Amichai Painsky, Saharon Rosset, and Meir Feder.  Linear independent component analysis over finite fields: Algorithms and bounds.  IEEE Transactions on Signal Processing, 66(22):5875–5886, 2018\.
  * [PVG+11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [RPG16] Siamak Ravanbakhsh, Barnabás Póczos, and Russell Greiner.  Boolean matrix factorization and noisy completion via message passing.  In Proceedings of the 33nd International Conference on Machine Learning, ICML, pages 945–954, 2016.
  * [RSW16] Ilya P. Razenshteyn, Zhao Song, and David P. Woodruff.  Weighted low rank approximations with provable guarantees.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 250–263, 2016.
  * [SBM03] Jouni K. Seppänen, Ella Bingham, and Heikki Mannila.  A simple algorithm for topic identification in 0-1 data.  In Knowledge Discovery in Databases: PKDD 2003, 7th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings, pages 423–434, 2003.
  * [SH06] Tomás Singliar and Milos Hauskrecht.  Noisy-or component analysis and its application to link analysis.  J. Mach. Learn. Res., 7:2189–2213, 2006.
  * [SJY09] Bao-Hong Shen, Shuiwang Ji, and Jieping Ye.  Mining discrete patterns via binary matrix factorization.  In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 757–766, 2009.
  * [SWZ17] Zhao Song, David P. Woodruff, and Peilin Zhong.  Low rank approximation with entrywise $\ell_{1}$-norm error.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 688–701, 2017.
  * [VAG07] Jaideep Vaidya, Vijayalakshmi Atluri, and Qi Guo.  The role mining problem: finding a minimal descriptive set of roles.  In Proceedings of the 12th ACM symposium on Access control models and technologies, pages 175–184, 2007.
  * [Woo14] David P. Woodruff.  Sketching as a tool for numerical linear algebra.  Found. Trends Theor. Comput. Sci., 10(1-2):1–157, 2014.
  * [Yer11] Arie Yeredor.  Independent component analysis over galois fields of prime order.  IEEE Trans. Inf. Theory, 57(8):5342–5359, 2011.
  * [ZLDZ07] Zhongyuan Zhang, Tao Li, Chris Ding, and Xiangsun Zhang.  Binary matrix factorization with applications.  In Seventh IEEE international conference on data mining (ICDM 2007), pages 391–400. IEEE, 2007.
  * [ZLS+12] Yinqiang Zheng, Guangcan Liu, Shigeki Sugimoto, Shuicheng Yan, and Masatoshi Okutomi.  Practical low-rank matrix approximation under robust l1-norm.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 1410–1417, 2012.
  * [ZZ12] Marinka Zitnik and Blaz Zupan.  Nimfa: A python library for nonnegative matrix factorization.  Journal of Machine Learning Research, 13:849–853, 2012.


# Completeness and injectivity

Soichiro Fujii111The author is supported by ERATO HASUO Metamathematics for
Systems Design Project (No. JPMJER1603), JST<EMAIL_ADDRESS>Research
Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan

###### Abstract

We show that for any quantale $\mathcal{Q}$, a $\mathcal{Q}$-category is
skeletal and complete if and only if it is injective with respect to fully
faithful $\mathcal{Q}$-functors. This is a special case of known theorems due
to Hofmann and Stubbe, but we provide a different proof, using the
characterisation of the MacNeille completion of a $\mathcal{Q}$-category as
its injective envelope. For Lawvere metric spaces, our results yield those of
Kemajou, Künzi and Otafudu. We point out that their notion of Isbell convexity
can be seen as a geometric formulation of categorical completeness for Lawvere
metric spaces.

###### keywords:

Enriched category , quantale , injective object , injective envelope ,
MacNeille completion , hyperconvex hull , tight span

###### MSC:

[2020] 18D20 , 06F07 , 54E35

##  1 Introduction

The main purpose of this paper is to present a theorem claiming the
equivalence between _completeness_ and _injectivity_ in the context of
_quantale-enriched categories_. In order to convey the idea of the theorem, we
start with describing two classical theorems in order theory and metric space
theory, and then a variant of the latter for directed metric spaces; the first
and third of them are instances of our theorem (modulo minor modifications).

######  Theorem 1.1 ([3]).

A poset is a complete lattice if and only if it is injective.

Recall that a poset ${\mathcal{E}}$ is a complete lattice if it has all
suprema (or equivalently all infima) of subsets of ${\mathcal{E}}$. On the
other hand, a poset ${\mathcal{E}}$ (whose partial order relation we denote by
$\preceq_{\mathcal{E}}$) is said to be injective if, whenever we have posets
${\mathcal{C}}$ and ${\mathcal{D}}$, a monotone map
$f\colon{\mathcal{C}}\longrightarrow{\mathcal{E}}$ (i.e., a function such that
for all $c,c^{\prime}\in{\mathcal{C}}$, $c\preceq_{\mathcal{C}}c^{\prime}$
implies $f(c)\preceq_{\mathcal{E}}f(c^{\prime})$), and an order embedding
$i\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$ (i.e., a function such that
$c\preceq_{\mathcal{C}}c^{\prime}$ if and only if
$i(c)\preceq_{\mathcal{D}}i(c^{\prime})$), there exists a (not necessarily
unique) monotone map $g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$ making
the diagram

${\mathcal{C}}$${\mathcal{D}}$${\mathcal{E}}$$f$$i$$g$

commute. Notice that the property of being a complete lattice is described
totally in terms of the _internal_ structure of a poset, whereas that of being
injective is formulated solely in terms of its _external_ behaviour among all
posets. The fascination of this theorem due to Banaschewski and Bruns lies in
the fact that it connects an internal property with an external one.

######  Theorem 1.2 ([2]).

A metric space is hyperconvex if and only if it is injective.

A metric space ${\mathcal{E}}$ (whose distance function we denote by
$d_{\mathcal{E}}$) is hyperconvex if, for any (possibly infinite) family
$((e_{i},r_{i}))_{i\in I}$ of pairs of a point $e_{i}\in{\mathcal{E}}$ and a
nonnegative real number $r_{i}$ satisfying $r_{i}+r_{j}\geq
d_{\mathcal{E}}(e_{i},e_{j})$ for all $i,j\in I$, there exists a point
$e\in{\mathcal{E}}$ such that $r_{i}\geq d_{\mathcal{E}}(e_{i},e)$ for all
$i\in I$. Let us elaborate the definition. One can view each pair
$(e_{i},r_{i})$ as the closed ball $B(e_{i},r_{i})$ in ${\mathcal{E}}$ with
centre $e_{i}$ and radius $r_{i}$. Then the condition that $r_{i}+r_{j}\geq
d_{\mathcal{E}}(e_{i},e_{j})$ for all $i,j\in I$ says that any two balls in
the family _potentially intersect_ ; indeed, if
$r_{i}+r_{j}<d_{\mathcal{E}}(e_{i},e_{j})$ then $B(e_{i},r_{i})\cap
B(e_{j},r_{j})=\emptyset$ by the triangle inequality. The existence of a point
$e\in{\mathcal{E}}$ such that $r_{i}\geq d_{\mathcal{E}}(e_{i},e)$ for all
$i\in I$ means that the intersection $\bigcap_{i\in I}B(e_{i},r_{i})$ of _all_
balls in the family is nonempty. For example, $\mathbb{R}^{2}$ with the
Euclidean metric is not hyperconvex, but $\mathbb{R}^{2}$ with the maximum
metric is; the following are some balls in these metric spaces.

The definition of injectivity for metric spaces parallels that for posets. A
metric space ${\mathcal{E}}$ is injective if, whenever we have metric spaces
${\mathcal{C}}$ and ${\mathcal{D}}$, a nonexpansive map
$f\colon{\mathcal{C}}\longrightarrow{\mathcal{E}}$ (i.e., a function such that
$d_{\mathcal{C}}(c,c^{\prime})\geq d_{\mathcal{E}}(f(c),f(c^{\prime}))$), and
an isometric embedding $i\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$
(i.e., a function such that
$d_{\mathcal{C}}(c,c^{\prime})=d_{\mathcal{D}}(i(c),i(c^{\prime}))$), there
exists a (not necessarily unique) nonexpansive map
$g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$ such that $f=g\circ i$.
Again, this theorem of Aronszajn and Panitchpakdi is interesting in that it
relates the internal property of hyperconvexity with the external one of
injectivity.

The following theorem due to Kemajou, Künzi and Otafudu is the directed
variant of Theorem 1.2. By a di-space we mean a possibly nonsymmetric (in the
sense that $d_{\mathcal{C}}(c,c^{\prime})$ may be different from
$d_{\mathcal{C}}(c^{\prime},c)$) generalisation of a metric space.

######  Theorem 1.3 ([16]).

A di-space is Isbell convex if and only if it is injective.

The notion of Isbell convexity is a straightforward adaptation of
hyperconvexity to the nonsymmetric setting. Precisely, a di-space
${\mathcal{E}}$ is Isbell convex if, for any (possibly infinite) family
$((e_{i},x_{i},y_{i}))_{i\in I}$ of _triples_ of a point
$e_{i}\in{\mathcal{E}}$ and nonnegative real numbers $x_{i}$ and $y_{i}$
satisfying $x_{i}+y_{j}\geq d_{\mathcal{E}}(e_{i},e_{j})$ for all $i,j\in I$,
there exists a point $e\in{\mathcal{E}}$ such that $x_{i}\geq
d_{\mathcal{E}}(e_{i},e)$ and $y_{i}\geq d_{\mathcal{E}}(e,e_{i})$ for all
$i\in I$. We shall say more about this notion in Section 7. The definition of
injectivity for di-spaces is completely parallel to that for metric spaces.

Except that a precise relationship between the notions of complete lattice on
the one hand, and of hyperconvex metric space and Isbell convex di-space on
the other, is perhaps not apparent, Theorems 1.1–1.3 look quite similar. These
results look even closer if one notes the fact that in all cases we have
constructions of _injective envelopes_. Informally, an injective envelope of
an object (i.e., poset, metric space or di-space) ${\mathcal{C}}$ is the
smallest injective object $\overline{{\mathcal{C}}}$ to which ${\mathcal{C}}$
embeds; we shall give a precise definition in an abstract setting in Section
5. The injective envelope of a poset, metric space and di-space is also known
as its _MacNeille completion_ [21], _hyperconvex hull_ or _tight span_ [13, 7,
10], and _Isbell hull_ or _directed tight span_ [16, 11], respectively.

In this paper we shall prove a generalisation of Theorems 1.1 and 1.3. (For a
generalisation of Theorem 1.2, see [14].) We unify posets and di-spaces by
_categories enriched over a quantale_. A quantale [22] ${\mathcal{Q}}$ is a
complete lattice $(Q,\preceq_{{\mathcal{Q}}})$ equipped with a compatible
monoid structure $(Q,I_{\mathcal{Q}},\circ_{{\mathcal{Q}}})$. Given any
quantale ${\mathcal{Q}}$, one can consider categories enriched over
${\mathcal{Q}}$, or _${\mathcal{Q}}$ -categories_ [15, 28, 29]. Informally, a
${\mathcal{Q}}$-category ${\mathcal{C}}$ is a set
${\mathrm{ob}({\mathcal{C}})}$ equipped with a ${\mathcal{Q}}$-valued preorder
relation
${\mathcal{C}}(-,-)\colon{\mathrm{ob}({\mathcal{C}})}\times{\mathrm{ob}({\mathcal{C}})}\longrightarrow
Q$. Taking ${\mathcal{Q}}={\mathbf{2}}$, the two-element quantale, we recover
preordered sets as ${\mathbf{2}}$-categories, whereas taking
${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{+}}$, the quantale of extended
nonnegative real numbers with addition as the monoid structure, we obtain a
mild generalisation of di-spaces (called _Lawvere metric spaces_) as
${\overline{\mathbb{R}}^{\geq 0}_{+}}$-categories [19].

Theorems 1.1 and 1.3 can be generalised as follows.

######  Theorem 1.4 ([12, 30]).

Let ${\mathcal{Q}}$ be a quantale. A ${\mathcal{Q}}$-category is skeletal and
complete if and only if it is injective (with respect to fully faithful
${\mathcal{Q}}$-functors).

The terms appearing in the above statement will be introduced in Section 3.
Actually, this theorem is known in much more general settings. In [12, Theorem
2.7] it is proved for $\mathcal{T}$-categories for a topological theory
$\mathcal{T}$, and in [30] it is proved for categories enriched over a
quantaloid, with attribution to Hofmann for private communication. See also
[31, Proposition 5.2] and [25, Theorem 10.1].

The MacNeille completion can be generalised from posets to
${\mathcal{Q}}$-categories; see [8, Definition 7.2] and [24, Definition
5.5.2]. It is also known that the MacNeille completion for
${\overline{\mathbb{R}}^{\geq 0}_{+}}$-categories coincides with the Isbell
hull [32]. We show that the abstract characterisation of the MacNeille
completion of a poset as its injective envelope [3] also extends to
${\mathcal{Q}}$-categories.

######  Theorem 1.5.

Let ${\mathcal{Q}}$ be a quantale. For any ${\mathcal{Q}}$-category
${\mathcal{C}}$, its MacNeille completion $\mathcal{M}{\mathcal{C}}$ is the
injective envelope of ${\mathcal{C}}$.

In fact, we shall prove Theorem 1.4 using Theorem 1.5; our proof of Theorem
1.4 extends the proof of Theorem 1.1 in [3], and is different from those
adopted in [12, 30, 31, 25]. If one assumes enough background on enriched
categories, the latter proofs are arguably shorter, but we believe that our
proof illuminating the role of the MacNeille completion is of independent
interest.

The outline of this paper is as follows. In Sections 2 and 3 we introduce
background materials on quantales and ${\mathcal{Q}}$-categories respectively.
In Section 4 we explain the MacNeille completion for
${\mathcal{Q}}$-categories. Then, after a brief review of a formal theory of
injective envelopes in Section 5, we prove Theorems 1.5 and 1.4 in Section 6.
Finally, in Section 7, we revisit the notion of Isbell convexity of [16], and
point out that it is equivalent to categorical completeness.

### Acknowledgements

I am grateful to the organisers of the Third Pan-Pacific International
Conference on Topology and Applications for giving me an opportunity to
present this material. I would like to thank Lili Shen for funding my visit to
Chengdu, and for providing valuable comments on this work, including the
information on the works of Hofmann, Stubbe, Shen and Tholen.

##  2 Quantales

We first introduce _quantales_ [22], also known as _complete idempotent
semirings_ [6, 20]. They are the enriching (or base) categories in the portion
of enriched category theory we shall be concerned with.

######  Definition 2.1.

A (unital) quantale ${\mathcal{Q}}$ is a complete lattice
$(Q,\preceq_{\mathcal{Q}})$ equipped with a monoid structure
$(Q,I_{\mathcal{Q}},\circ_{\mathcal{Q}})$ such that the multiplication
$\circ_{\mathcal{Q}}$ preserves arbitrary suprema in each variable:
$(\bigvee_{i\in I}y_{i})\circ_{\mathcal{Q}}x=\bigvee_{i\in
I}(y_{i}\circ_{\mathcal{Q}}x)$ and $y\circ_{\mathcal{Q}}(\bigvee_{i\in
I}x_{i})=\bigvee_{i\in I}(y\circ_{\mathcal{Q}}x_{i})$. We often omit the
subscript ${\mathcal{Q}}$ from the data of a quantale, writing it simply as
${\mathcal{Q}}=(Q,\preceq,I,\circ)$.

Notice that in the definition of quantale, we do not assume commutativity of
the multiplication $\circ$ by default; quantales with commutative
multiplication are said to be commutative.

The notion of _adjunction_ is central to category theory. In this paper we
shall only need the particularly simple case of adjunctions between posets,
also known as _Galois connections_. Recall that given posets $(L,\preceq)$ and
$(L^{\prime},\preceq^{\prime})$, two functions $f\colon L\longrightarrow
L^{\prime}$ and $u\colon L^{\prime}\longrightarrow L$ are said to form an
adjunction if, for any $l\in L$ and $l^{\prime}\in L^{\prime}$,

$f(l)\preceq^{\prime}l^{\prime}\iff l\preceq u(l^{\prime})$ (1)

holds. We call $f$ the left adjoint of $u$ and $u$ the right adjoint of $f$,
and write them as $f\dashv u$. The adjointness relation (1) is powerful enough
to determine each of the functions $f$ and $u$ from the other, and force both
of them to be _monotone_ functions [27].

We record the following well-known fact.

######  Proposition 2.2.

Let $(L,\preceq)$ be a complete lattice and $(L^{\prime},\preceq^{\prime})$ be
a poset. A function $f\colon L\longrightarrow L^{\prime}$ preserves arbitrary
suprema if and only if there exists a function $u\colon
L^{\prime}\longrightarrow L$ such that $f\dashv u$.

As the first application of Proposition 2.2, observe that in any quantale
${\mathcal{Q}}=(Q,\preceq,$ $I,\circ)$ there are two _residuation_ operations:
for any $x\in Q$, the function $(-)\circ x\colon Q\longrightarrow Q$ preserves
arbitrary suprema, and hence has a right adjoint $(-)\mathbin{\swarrow}x\colon
Q\longrightarrow Q$ called the right extension along $x$; similarly, for any
$y\in Q$ the function $y\circ(-)$ has a right adjoint
$y\mathbin{\searrow}(-)$, called the right lifting along $y$. Of course, in a
commutative quantale the right extensions and right liftings coincide. The
defining adjointness relations are:

$y\preceq z\mathbin{\swarrow}x\iff y\circ x\preceq z\iff x\preceq
y\mathbin{\searrow}z.$ (2)

Focusing on the leftmost and rightmost formulas of (2), we obtain

$z\mathbin{\swarrow}x\succeq y\iff x\preceq y\mathbin{\searrow}z.$

That is, $z\mathbin{\swarrow}(-)\colon Q\longrightarrow Q$ (regarded as a
function from the poset ${\mathcal{Q}}=(Q,\preceq)$ to its dual
${\mathcal{Q}}^{\mathrm{op}}=(Q,\succeq)$) is the left adjoint of
$(-)\mathbin{\searrow}z\colon Q\longrightarrow{Q}$ (from
${\mathcal{Q}}^{\mathrm{op}}$ to ${\mathcal{Q}}$) for any $z\in Q$. The three
types of adjunctions

${\mathcal{Q}}$${\mathcal{Q}}$$(-)\circ x$$(-)\mathbin{\swarrow}x$$\dashv$
${\mathcal{Q}}$${\mathcal{Q}}$$y\circ(-)$$y\mathbin{\searrow}(-)$$\dashv$
${\mathcal{Q}}$${\mathcal{Q}}^{\mathrm{op}}$$z\mathbin{\swarrow}(-)$$(-)\mathbin{\searrow}z$$\dashv$

are fundamental in the theory of quantales.

We conclude this section with some examples of quantales.

######  Example 2.3 ([19]).

The two-element quantale ${\mathbf{2}}=(\\{\bot,\top\\},\vdash,\top,\wedge)$.
The underlying poset of this quantale consists of $\top$ for “truth” and
$\bot$ for “falsity”, ordered by the entailment relation $\vdash$, so that
$\bot\vdash\top$. The monoid structure is given by conjunction $\wedge$.

######  Example 2.4 ([19]).

The Lawvere quantale ${\overline{\mathbb{R}}^{\geq
0}_{+}}=([0,\infty],\geq,0,+)$. Here, $([0,\infty],\geq)$ is the poset
$([0,\infty),\geq)$ of all nonnegative real numbers ordered by the _opposite_
$\geq$ of the usual order $\leq$, extended with the _least_ element $\infty$.
The $+$ operation is the extension of addition for nonnegative real numbers to
$[0,\infty]$ so that $x+\infty=\infty+x=\infty$ for all $x\in[0,\infty]$.
(This extension is forced by the axioms of quantale.) The right
extension/right lifting is given by an extension of the _truncated subtraction
$\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$_, defined by
$u\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}t=\max\\{u-t,0\\}$ for nonnegative real numbers
$t$ and $u$. Precisely, for $y,z\in[0,\infty]$,

$z\mathbin{\swarrow}y=y\mathbin{\searrow}z=\begin{cases}z\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y&\text{ if }y,z\in[0,\infty)\\\ 0&\text{ if
}y=\infty\\\ \infty&\text{ if }z=\infty\text{ and }y\in[0,\infty).\end{cases}$

This quantale is introduced in [19] for a categorical approach to the theory
of metric spaces.

######  Example 2.5 ([19]).

${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{max}}}=([0,\infty],\geq,0,\max)$.
Its underlying poset $([0,\infty],\geq)$ is the same as that of
${\overline{\mathbb{R}}^{\geq 0}_{+}}$. We take the binary max operation with
respect to the usual ordering $\leq$, namely the binary meet operation with
respect to $\geq$, as the multiplication. The right extension/right lifting is
given by

$z\mathbin{\swarrow}y=y\mathbin{\searrow}z=\begin{cases}0\ \text{ if }y\geq
z\\\ z\ \text{ otherwise.}\end{cases}$

This quantale is related to (a generalisation of) ultrametric spaces.

We remark that more generally, any locale, i.e., a complete lattice in which
the binary meet operation $\wedge$ satisfies the infinitary distributive law
$(\bigvee_{i\in I}y_{i})\wedge x=\bigvee_{i\in I}(y_{i}\wedge x)$, acquires a
quantale structure with $\wedge$ as the multiplication; indeed quantales were
first introduced as a quantum theoretic generalisation of locales [22]. The
poset $([0,\infty],\geq)$, or more generally any totally ordered complete
lattice, is a locale.

######  Example 2.6.

Let ${\mathcal{M}}=(M,e,\cdot)$ be a monoid. The free quantale generated by
${\mathcal{M}}$ is
$\mathcal{P}{\mathcal{M}}=(\mathcal{P}M,{\subseteq},\\{e\\},\cdot)$, where
$\mathcal{P}M$ is the power set of $M$ and the multiplication $\cdot$ on
$\mathcal{P}M$ is the unique supremum-preserving extension of the original
multiplication on $M$, which is given by

$A\cdot B=\\{\,a\cdot b\mid a\in A,b\in B\,\\}$

for all $A,B\in\mathcal{P}M$. Unlike the previous examples, this quantale is
not commutative unless ${\mathcal{M}}$ is.

######  Example 2.7.

Let $A$ be a set. The poset $(\mathcal{P}(A\times A),\subseteq)$ of all binary
relations on $A$ admits a quantale structure $(\mathcal{P}(A\times
A),\subseteq,I_{A},\circ)$, where $I_{A}$ denotes the diagonal relation on $A$
and $\circ$ denotes composition of relations. This quantale is not commutative
in general.

##  3 ${\mathcal{Q}}$-categories

In this section, we introduce ${\mathcal{Q}}$-categories for a quantale
${\mathcal{Q}}$. They are instances of the well-established notion of enriched
category [15]. _Throughout the rest of this paper,
${\mathcal{Q}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{\mathcal{Q}})$
denotes an arbitrary quantale, unless otherwise specified._

######  Definition 3.1.

A ${\mathcal{Q}}$-category ${\mathcal{C}}$ consists of:

(CD1)

a set ${\mathrm{ob}({\mathcal{C}})}$ of objects;

(CD2)

for each $c,c^{\prime}\in{\mathrm{ob}({\mathcal{C}})}$, an element
${\mathcal{C}}(c,c^{\prime})\in{Q}$

satisfying the following axioms:

(CA1)

for each $c\in{\mathrm{ob}({\mathcal{C}})}$,
$I_{\mathcal{Q}}\preceq_{\mathcal{Q}}{\mathcal{C}}(c,c)$;

(CA2)

for each $c,c^{\prime},c^{\prime\prime}\in{\mathrm{ob}({\mathcal{C}})}$,
${\mathcal{C}}(c^{\prime},c^{\prime\prime})\circ_{\mathcal{Q}}{\mathcal{C}}(c,c^{\prime})\preceq_{\mathcal{Q}}{\mathcal{C}}(c,c^{\prime\prime})$.

We also write $c\in{\mathcal{C}}$ for $c\in{\mathrm{ob}({\mathcal{C}})}$.

######  Example 3.2.

In the case ${\mathcal{Q}}={\mathbf{2}}$, we may identify the data of a
${\mathbf{2}}$-category
${\mathcal{C}}=({\mathrm{ob}({\mathcal{C}})},({\mathcal{C}}(c,c^{\prime}))_{c,c^{\prime}\in{\mathrm{ob}({\mathcal{C}})}})$
with a set ${\mathrm{ob}({\mathcal{C}})}$ equipped with a binary relation
$\preceq_{\mathcal{C}}$ on it (defined as the set of all pairs
$(c,c^{\prime})\in{\mathrm{ob}({\mathcal{C}})}\times{\mathrm{ob}({\mathcal{C}})}$
with ${\mathcal{C}}(c,c^{\prime})=\top$). Axioms (CA1) and (CA2) for a
${\mathbf{2}}$-category then translate to reflexivity and transitivity of
$\preceq_{\mathcal{C}}$ respectively, hence a ${\mathbf{2}}$-category is
nothing but a _preordered set_.

######  Example 3.3.

In the case ${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{+}}$, we may
regard ${\overline{\mathbb{R}}^{\geq 0}_{+}}$-categories as generalised metric
spaces [19]. Objects of an ${\overline{\mathbb{R}}^{\geq 0}_{+}}$-category
${\mathcal{C}}$ are thought of as _points_ and the element
${\mathcal{C}}(c,c^{\prime})\in[0,\infty]$ as the _distance from $c$ to
$c^{\prime}$_. Notice that the axioms for ${\overline{\mathbb{R}}^{\geq
0}_{+}}$-category indeed translate to some of the axioms for metric spaces:

(CA1)

for each $c\in{\mathrm{ob}({\mathcal{C}})}$, $0\geq{\mathcal{C}}(c,c)$ (that
is, ${\mathcal{C}}(c,c)=0$); and

(CA2)

for each $c,c^{\prime},c^{\prime\prime}\in{\mathrm{ob}({\mathcal{C}})}$,
${\mathcal{C}}(c^{\prime},c^{\prime\prime})+{\mathcal{C}}(c,c^{\prime})\geq{\mathcal{C}}(c,c^{\prime\prime})$
(the triangle inequality).

We call ${\overline{\mathbb{R}}^{\geq 0}_{+}}$-categories Lawvere metric
spaces. Every metric space is a Lawvere metric space, but not conversely.
Lawvere metric spaces are more general than metric spaces in the following
three aspects:

  * 1.

distance may take $\infty$;

  * 2.

distance is non-symmetric (or _directed_), i.e., ${\mathcal{C}}(c,c^{\prime})$
may be different from ${\mathcal{C}}(c^{\prime},c)$; and

  * 3.

${\mathcal{C}}(c,c^{\prime})={\mathcal{C}}(c^{\prime},c)=0$ does not
necessarily imply $c=c^{\prime}$.

######  Example 3.4.

Similarly, ${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{max}}}$-categories may be
regarded as generalised ultrametric spaces; note that axiom (CA2) now reads:

(CA2)

for each $c,c^{\prime},c^{\prime\prime}\in{\mathrm{ob}({\mathcal{C}})}$,
$\max\\{\,{\mathcal{C}}(c^{\prime},c^{\prime\prime}),{\mathcal{C}}(c,c^{\prime})\,\\}\geq{\mathcal{C}}(c,c^{\prime\prime})$.

######  Example 3.5.

Let ${\mathcal{M}}=(M,e,\cdot)$ be a monoid. A
$\mathcal{P}{\mathcal{M}}$-category ${\mathcal{C}}$ has, for each pair
$c,c^{\prime}\in{\mathrm{ob}({\mathcal{C}})}$, a subset
${\mathcal{C}}(c,c^{\prime})\subseteq M$. These subsets must satisfy:

(CA2)

for each $c\in{\mathrm{ob}({\mathcal{C}})}$, $e\in{\mathcal{C}}(c,c)$; and

(CA2)

for each $c,c^{\prime},c^{\prime\prime}\in{\mathrm{ob}({\mathcal{C}})}$,
$n\in{\mathcal{C}}(c^{\prime},c^{\prime\prime})$ and
$m\in{\mathcal{C}}(c,c^{\prime})$, $n\cdot
m\in{\mathcal{C}}(c,c^{\prime\prime})$.

It follows that a $\mathcal{P}{\mathcal{M}}$-category can be identified with
an ordinary category ${\mathcal{C}}$ equipped with a _faithful_ functor
${\mathcal{C}}\longrightarrow{\mathcal{M}}$, where the monoid ${\mathcal{M}}$
is regarded as a one-object category.

In fact, this example can be vastly generalised. For any (ordinary) _category_
${\mathcal{B}}$, we can construct the free _quantaloid_
$\mathcal{P}{\mathcal{B}}$ over it; quantaloids [23] are a many-object version
of quantales, just like categories can be seen as a many-object version of
monoids. It turns out that a $\mathcal{P}{\mathcal{B}}$-category corresponds
to a category ${\mathcal{C}}$ equipped with a faithful functor
${\mathcal{C}}\longrightarrow{\mathcal{B}}$ [8]. Theorem 1.4 is known to
generalise to quantaloid-enriched categories [30, 31, 25], and (skeletal and)
complete/injective $\mathcal{P}{\mathcal{B}}$-categories correspond to
_topological functors over ${\mathcal{B}}$_; see [8] for a characterisation of
topological functors in terms of completeness, and see [5, 9] for that in
terms of injectivity. In order to keep the paper accessible to a wider
audience, in this paper we shall not pursue quantaloid-enriched categories any
further. On the other hand, although our main examples of base quantales are
commutative, we shall not assume commutativity so that our arguments can be
easily generalised to the case of quantaloids.

Let ${\mathcal{C}}$ be a ${\mathcal{Q}}$-category. We define a preorder
relation $\preceq_{\mathcal{C}}$ on ${\mathcal{C}}$ as

$c\preceq_{\mathcal{C}}c^{\prime}\iff
I_{\mathcal{Q}}\preceq_{\mathcal{Q}}{\mathcal{C}}(c,c^{\prime}).$

(Note that the notation $\preceq_{\mathcal{C}}$ agrees with the one introduced
in Example 3.2.) Two objects $c,c^{\prime}\in{\mathcal{C}}$ are said to be
isomorphic if both $c\preceq_{\mathcal{C}}c^{\prime}$ and
$c^{\prime}\preceq_{\mathcal{C}}c$ hold. Isomorphic objects behave exactly in
the same manner: if $c,c^{\prime}\in{\mathcal{C}}$ are isomorphic then for
every object $d\in{\mathcal{C}}$, we have
${\mathcal{C}}(c,d)={\mathcal{C}}(c^{\prime},d)$ and
${\mathcal{C}}(d,c)={\mathcal{C}}(d,c^{\prime})$. We call ${\mathcal{C}}$
skeletal if isomorphic objects in ${\mathcal{C}}$ are equal, i.e., if the
induced preorder relation $\preceq_{\mathcal{C}}$ on
${\mathrm{ob}({\mathcal{C}})}$ is actually a partial order relation.

A skeletal ${\mathbf{2}}$-category is a poset, and a skeletal
${\overline{\mathbb{R}}^{\geq 0}_{+}}$\- or ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{max}}}$-category ${\mathcal{C}}$ satisfies the condition that for
all $c,c^{\prime}\in{\mathcal{C}}$,
${\mathcal{C}}(c,c^{\prime})={\mathcal{C}}(c^{\prime},c)=0$ implies
$c=c^{\prime}$.

Let us move on to define completeness of ${\mathcal{Q}}$-categories. Given a
${\mathcal{Q}}$-category ${\mathcal{C}}$, an object $c\in{\mathcal{C}}$ and an
element $x\in Q$, an object $c^{\prime}\in{\mathcal{C}}$ is said to be a power
of $c$ by $x$ if for any $d\in{\mathcal{C}}$, the equation

${\mathcal{C}}(d,c^{\prime})=x\mathbin{\searrow}{\mathcal{C}}(d,c)$

holds [15, Section 3.7]. Powers of $c$ by $x$ may or may not exist in
${\mathcal{C}}$, but when they exist they are unique up to isomorphism: if
$c^{\prime}$ is a power of $c$ by $x$, then an object
$c^{\prime\prime}\in{\mathcal{C}}$ is also a power of $c$ by $x$ if and only
if $c^{\prime}$ and $c^{\prime\prime}$ are isomorphic. In particular, in a
skeletal ${\mathcal{Q}}$-category powers are unique. We denote the power of
$c$ by $x$ by $x\pitchfork c$.

There is also a dual notion of copower of $c\in{\mathcal{C}}$ by $x\in Q$,
which is defined as an object $c^{\prime}\in{\mathcal{C}}$ such that for any
$d\in{\mathcal{C}}$, the equation

${\mathcal{C}}(c^{\prime},d)={\mathcal{C}}(c,d)\mathbin{\swarrow}x$

holds. The copower of $c$ by $x$ is denoted by $x\ast c$.

######  Definition 3.6 ([29, Section 2]).

A ${\mathcal{Q}}$-category ${\mathcal{C}}$ is said to be:

  * 1.

powered if for any $c\in{\mathcal{C}}$ and $x\in Q$, the power $x\pitchfork c$
exists in ${\mathcal{C}}$;

  * 2.

copowered if for any $c\in{\mathcal{C}}$ and $x\in Q$, the copower $x\ast c$
exists in ${\mathcal{C}}$;

  * 3.

order-complete if the preordered set
$({\mathrm{ob}({\mathcal{C}})},\preceq_{\mathcal{C}})$ is complete (i.e., if
its poset reflection222The _poset reflection_ of a preordered set
$(P,\preceq)$ is the quotient of it by the equivalence relation
$\preceq\cap\succeq$. is a complete lattice); and

  * 4.

complete if it is powered, copowered and order-complete.

Next we define morphisms between ${\mathcal{Q}}$-categories, called
_${\mathcal{Q}}$ -functors_.

######  Definition 3.7.

Let ${\mathcal{C}}$ and ${\mathcal{D}}$ be ${\mathcal{Q}}$-categories.

  1. 1.

A ${\mathcal{Q}}$-functor $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$
is a function
$f\colon{\mathrm{ob}({\mathcal{C}})}\longrightarrow{\mathrm{ob}({\mathcal{D}})}$
such that for each $c,c^{\prime}\in{\mathcal{C}}$,

${\mathcal{C}}(c,c^{\prime})\preceq_{\mathcal{Q}}{\mathcal{D}}(f(c),f(c^{\prime}))$
(3)

holds.

  2. 2.

A ${\mathcal{Q}}$-functor $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$
is fully faithful if for each $c,c^{\prime}\in{\mathcal{C}}$, (3) is satisfied
with equality. We call fully faithful ${\mathcal{Q}}$-functors embeddings for
short.

For any ${\mathcal{Q}}$-category ${\mathcal{C}}$ we have the identity
${\mathcal{Q}}$-functor
${\mathrm{id}_{{\mathcal{C}}}}\colon{\mathcal{C}}\longrightarrow{\mathcal{C}}$
(given by the identity function on ${\mathrm{ob}({\mathcal{C}})}$), and
${\mathcal{Q}}$-functors are closed under composition. So
${\mathcal{Q}}$-categories and ${\mathcal{Q}}$-functors form an (ordinary)
category ${{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Cat}}$. Note that an
embedding $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$ of
${\mathcal{Q}}$-categories need not be injective as a function
$f\colon{\mathrm{ob}({\mathcal{C}})}\longrightarrow{\mathrm{ob}({\mathcal{D}})}$,
though embeddings out of a skeletal ${\mathcal{C}}$ are injective.

For example, a ${\mathbf{2}}$-functor
$f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$ is a monotone map, and an
${\overline{\mathbb{R}}^{\geq 0}_{+}}$\- or ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{max}}}$-functor $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$
is a nonexpansive map. Embeddings specialise to order embeddings and isometric
embeddings respectively.

We say that a ${\mathcal{Q}}$-category ${\mathcal{E}}$ is injective (with
respect to embeddings) if, whenever we have ${\mathcal{Q}}$-categories
${\mathcal{C}}$ and ${\mathcal{D}}$, a ${\mathcal{Q}}$-functor
$f\colon{\mathcal{C}}\longrightarrow{\mathcal{E}}$, and an embedding
$i\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$, there exists a (not
necessarily unique) ${\mathcal{Q}}$-functor
$g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$ such that $f=g\circ i$.

Thus we have defined all terms appearing in Theorem 1.4. In fact, we can
already prove the easier direction.

######  Lemma 3.8.

A skeletal and complete ${\mathcal{Q}}$-category is injective.

###### Proof.

Let ${\mathcal{E}}$ be a skeletal and complete ${\mathcal{Q}}$-category. Given
a diagram as in

${\mathcal{C}}$${\mathcal{D}}$${\mathcal{E}}$$f$$i$

we may define a ${\mathcal{Q}}$-functor
$g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$ as the (pointwise) left (or
right) Kan extension of $f$ along $i$, namely

$\displaystyle g(d)$
$\displaystyle=\mathrm{Lan}_{i}f(d)=\bigvee_{c\in{\mathcal{C}}}{\mathcal{D}}(i(c),d)\ast
f(c)$ $\displaystyle(\text{or }g(d)$
$\displaystyle=\mathrm{Ran}_{i}f(d)=\bigwedge_{c\in{\mathcal{C}}}{\mathcal{D}}(d,i(c))\pitchfork
f(c)).$

Then, provided that $i$ is an embedding, $f(c)$ and $(g\circ i)(c)$ are
isomorphic for all $c\in{\mathcal{C}}$ [28, Proposition 6.7]; but since
${\mathcal{E}}$ is skeletal, isomorphic objects are necessarily equal, so
$f=g\circ i$. (Incidentally, $\mathrm{Lan}_{i}f$ and $\mathrm{Ran}_{i}f$ are
respectively the least and greatest $g$ such that $f=g\circ i$; that is, a
${\mathcal{Q}}$-functor $g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$
satisfies $f=g\circ i$ if and only if $\mathrm{Lan}_{i}f\preceq
g\preceq\mathrm{Ran}_{i}f$ with respect to the pointwise order $\preceq$
induced from $\preceq_{\mathcal{E}}$.) ∎

##  4 The MacNeille completion of a ${\mathcal{Q}}$-category

In this section we explain the MacNeille completion of a
${\mathcal{Q}}$-category. We start with some preparation.

######  Definition 4.1 (Cf. [28, Proposition 6.1]).

Let ${\mathcal{C}}$ be a ${\mathcal{Q}}$-category. The
${\mathcal{Q}}$-category $\mathcal{P}{\mathcal{C}}$ of presheaves over
${\mathcal{C}}$ is defined as follows.

  * 1.

An object is a presheaf over ${\mathcal{C}}$, that is a family
$P=(Pc)_{c\in{\mathcal{C}}}$ of elements of ${Q}$ satisfying the inequality
$Pc^{\prime}\circ{\mathcal{C}}(c,c^{\prime})\preceq_{\mathcal{Q}}Pc$ for each
$c,c^{\prime}\in{\mathcal{C}}$.

  * 2.

The element $\mathcal{P}{\mathcal{C}}(P,P^{\prime})$ of ${Q}$ is given by
$\bigwedge_{c\in{\mathcal{C}}}P^{\prime}c\mathbin{\swarrow}Pc$.

Dually, the ${\mathcal{Q}}$-category $\mathcal{P}^{\dagger}{\mathcal{C}}$ of
copresheaves over ${\mathcal{C}}$ is defined as follows.

  * 1.

An object is a copresheaf over ${\mathcal{C}}$, that is a family
$R=(Rc)_{c\in{\mathcal{C}}}$ of elements of ${Q}$ satisfying the inequality
${\mathcal{C}}(c,c^{\prime})\circ Rc\preceq_{\mathcal{Q}}Rc^{\prime}$ for each
$c,c^{\prime}\in{\mathcal{C}}$.

  * 2.

The element $\mathcal{P}^{\dagger}{\mathcal{C}}(R,R^{\prime})$ of ${Q}$ is
given by $\bigwedge_{c\in{\mathcal{C}}}R^{\prime}c\mathbin{\searrow}Rc$.

For any ${\mathcal{Q}}$-category ${\mathcal{C}}$, there are well-known
embeddings
$y_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$
and
$y^{\dagger}_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
called the Yoneda and co-Yoneda embeddings respectively; they are defined as
$y_{\mathcal{C}}(c)=({\mathcal{C}}(c^{\prime},c))_{c^{\prime}\in{\mathcal{C}}}$
and
$y^{\dagger}_{\mathcal{C}}(c)=({\mathcal{C}}(c,c^{\prime}))_{c^{\prime}\in{\mathcal{C}}}$.

For example, when ${\mathcal{Q}}={\mathbf{2}}$, $\mathcal{P}{\mathcal{C}}$ can
be understood as the poset of all _lower sets_ of ${\mathcal{C}}$ (i.e.,
subsets $P\subseteq{\mathrm{ob}({\mathcal{C}})}$ such that $c^{\prime}\in P$
and $c\preceq_{\mathcal{C}}c^{\prime}$ imply $c\in P$), ordered by inclusion.
The Yoneda embedding maps an element $c\in{\mathcal{C}}$ to the principal
lower set $\downarrow\\!c=\\{\,c^{\prime}\in{\mathcal{C}}\mid
c^{\prime}\preceq_{\mathcal{C}}c\,\\}$ generated by it. Dually,
$\mathcal{P}^{\dagger}{\mathcal{C}}$ is the poset of all _upper sets_ of
${\mathcal{C}}$ ordered by the _opposite_ of inclusion, and the co-Yoneda
embedding maps $c\in{\mathcal{C}}$ to the principal upper set $\uparrow\\!c$.

There exists a pair of canonical ${\mathcal{Q}}$-functors

${\mathcal{C}}\mathbin{\swarrow}(-)\colon\mathcal{P}{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}\quad\text{
and
}\quad(-)\mathbin{\searrow}{\mathcal{C}}\colon\mathcal{P}^{\dagger}{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}.$
(4)

The functor
${\mathcal{C}}\mathbin{\swarrow}(-)\colon\mathcal{P}{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
maps a presheaf $P=(Pc)_{c\in{\mathcal{C}}}$ to the copresheaf
${\mathcal{C}}\mathbin{\swarrow}P=(({\mathcal{C}}\mathbin{\swarrow}P)c)_{c\in{\mathcal{C}}}$
defined as

$({\mathcal{C}}\mathbin{\swarrow}P)c=\bigwedge_{c^{\prime}\in{\mathcal{C}}}{\mathcal{C}}(c^{\prime},c)\mathbin{\swarrow}Pc^{\prime};$

the functor $(-)\mathbin{\searrow}{\mathcal{C}}$ maps
$R\in\mathcal{P}^{\dagger}{\mathcal{C}}$ to
$R\mathbin{\searrow}{\mathcal{C}}\in\mathcal{P}{\mathcal{C}}$ defined as

$(R\mathbin{\searrow}{\mathcal{C}})c=\bigwedge_{c^{\prime}\in{\mathcal{C}}}Rc^{\prime}\mathbin{\searrow}{\mathcal{C}}(c,c^{\prime}).$

The functors (4) form a _${\mathcal{Q}}$ -adjunction_
${\mathcal{C}}\mathbin{\swarrow}(-)\dashv(-)\mathbin{\searrow}{\mathcal{C}}$,
in the sense that
$\mathcal{P}{\mathcal{C}}(P,R\mathbin{\searrow}{\mathcal{C}})=\mathcal{P}^{\dagger}{\mathcal{C}}({\mathcal{C}}\mathbin{\swarrow}P,R)$
for all $P\in\mathcal{P}{\mathcal{C}}$ and
$R\in\mathcal{P}^{\dagger}{\mathcal{C}}$. This can be checked as follows:

$\displaystyle\mathcal{P}{\mathcal{C}}(P,R\mathbin{\searrow}{\mathcal{C}})$
$\displaystyle=\bigwedge_{c,c^{\prime}\in{\mathcal{C}}}\Big{(}Rc^{\prime}\mathbin{\searrow}{\mathcal{C}}(c,c^{\prime})\Big{)}\mathbin{\swarrow}Pc$
$\displaystyle=\bigwedge_{c,c^{\prime}\in{\mathcal{C}}}Rc^{\prime}\mathbin{\searrow}\Big{(}{\mathcal{C}}(c,c^{\prime})\mathbin{\swarrow}Pc\Big{)}$
$\displaystyle=\mathcal{P}^{\dagger}{\mathcal{C}}({\mathcal{C}}\mathbin{\swarrow}P,R).$

This adjunction is called the Isbell adjunction [26, 8].

The MacNeille completion [8, 24] $\mathcal{M}{\mathcal{C}}$ of ${\mathcal{C}}$
is the ${\mathcal{Q}}$-category defined as follows.

(CD1)

An object is a pair $(P,R)$ of a presheaf $P\in\mathcal{P}{\mathcal{C}}$ and a
copresheaf $R\in\mathcal{P}^{\dagger}{\mathcal{C}}$ such that
$P=R\mathbin{\searrow}{\mathcal{C}}$ and $R={\mathcal{C}}\mathbin{\swarrow}P$
hold.

(CD2)

Given two objects $(P,R)$ and $(P^{\prime},R^{\prime})$, the element

$\mathcal{M}{\mathcal{C}}((P,R),(P^{\prime},R^{\prime}))\in Q$

is defined as $\mathcal{P}{\mathcal{C}}(P,P^{\prime})$, or equivalently as
$\mathcal{P}^{\dagger}{\mathcal{C}}(R,R^{\prime});$ indeed, we have

$\mathcal{P}{\mathcal{C}}(P,P^{\prime})=\mathcal{P}{\mathcal{C}}(P,R^{\prime}\mathbin{\searrow}{\mathcal{C}})=\mathcal{P}^{\dagger}{\mathcal{C}}({\mathcal{C}}\mathbin{\swarrow}P,R^{\prime})=\mathcal{P}^{\dagger}{\mathcal{C}}(R,R^{\prime}).$

Hence we have natural embeddings
$p_{\mathcal{C}}\colon\mathcal{M}{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$
and
$p^{\dagger}_{\mathcal{C}}\colon\mathcal{M}{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
defined by projections. The Yoneda (resp. co-Yoneda) embedding factors through
$p_{\mathcal{C}}$ (resp. $p^{\dagger}_{\mathcal{C}}$), so we have a canonical
embedding
$i_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{M}{\mathcal{C}}$
which maps each $c\in{\mathcal{C}}$ to
$({\mathcal{C}}(-,c),{\mathcal{C}}(c,-))\in\mathcal{M}{\mathcal{C}}$. We
summarise the situation in the diagram below.

$\mathcal{P}{\mathcal{C}}$$\mathcal{P}^{\dagger}{\mathcal{C}}$$\mathcal{M}{\mathcal{C}}$${\mathcal{C}}$${\mathcal{C}}\mathbin{\swarrow}(-)$$(-)\mathbin{\searrow}{\mathcal{C}}$$p_{\mathcal{C}}$$p^{\dagger}_{\mathcal{C}}$$y_{\mathcal{C}}$$y^{\dagger}_{\mathcal{C}}$$i_{\mathcal{C}}$$\dashv$

######  Proposition 4.2 ([24, 8]).

Let ${\mathcal{C}}$ be a ${\mathcal{Q}}$-category. The MacNeille completion
$\mathcal{M}{\mathcal{C}}$ is skeletal and complete.

###### Proof.

This is an immediate consequence of the fact that $\mathcal{P}{\mathcal{C}}$
is skeletal and complete, and that $p_{\mathcal{C}}$ has a left adjoint, thus
making $\mathcal{M}{\mathcal{C}}$ a full reflective subcategory of
$\mathcal{P}{\mathcal{C}}$. See e.g., [8, Proposition 7.6 (a)]. ∎

##  5 A formal theory of injective envelopes

In this section, we recall the notion of injective envelope and its basic
properties [1]. Throughout this section, let ${\mathcal{X}}$ be an (ordinary)
category and ${\mathcal{H}}$ be a class of morphisms in ${\mathcal{X}}$, whose
elements are called embeddings. We make no assumptions on ${\mathcal{X}}$ and
${\mathcal{H}}$, unless otherwise specified. An example to bear in mind is the
case where ${\mathcal{X}}={{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Cat}}$ and
${\mathcal{H}}$ is the class of all fully faithful ${\mathcal{Q}}$-functors.

######  Definition 5.1 ([1, Definitions 2.1]).

  1. 1.

An object $E$ of ${\mathcal{X}}$ is injective if, whenever we have objects $C$
and $D$, a morphism $f\colon C\longrightarrow D$, and an embedding $i\colon
C\longrightarrow D$, there exists a (not necessarily unique) morphism $g\colon
D\longrightarrow E$ such that $f=g\circ i$.

  2. 2.

A morphism $f\colon C\longrightarrow D$ in ${\mathcal{X}}$ is called an
essential embedding if: (i) $f$ is an embedding, and (ii) for any object $E$
and morphism $g\colon D\longrightarrow E$, if $g\circ f$ is an embedding then
so is $g$.

  3. 3.

An injective envelope of an object ${C}$ of ${\mathcal{X}}$ is a pair $(D,f)$
consisting of an injective object $D$ and an essential embedding
$f\colon{C}\longrightarrow{D}$.

Injective envelopes of an object are unique up to isomorphisms.333However,
note that the nature of this “uniqueness” is quite different from that for
usual categorical notions determined by their universal properties. We also
remark that the operation of taking the injective envelopes of objects does
not easily extend to morphisms [1]; cf. [26] and [8, Section 7].

######  Lemma 5.2 ([1, Remarks 2.2 (2)]).

Let $C$ be an object of ${\mathcal{X}}$, and $({D},f)$ and
$({D^{\prime}},f^{\prime})$ be injective envelopes of ${C}$. Then there exists
an isomorphism $g\colon{D}\longrightarrow{D^{\prime}}$ such that $g\circ
f=f^{\prime}$.

###### Proof.

By the injectivity of ${D^{\prime}}$, we obtain a morphism $g$ as in the
following commutative diagram.

${C}$${D}$${D^{\prime}}$$f^{\prime}$$f$$g$

We claim that _any_ morphism $g$ between injective envelopes as above (i.e.,
commuting with the essential embeddings) is an isomorphism. Since $f$ is an
essential embedding and $f^{\prime}=g\circ f$ is an embedding, it follows that
$g$ is also an embedding. Using the injectivity of ${D}$, we obtain a morphism
$h$ as below.

${D}$${D^{\prime}}$${D}$${\mathrm{id}_{{D}}}$$g$$h$

So $g$ is a section (split monomorphism) whereas $h$ is a retraction (split
epimorphism). Precomposing $f$ with the above diagram, we obtain the
following.

${C}$${D^{\prime}}$${D}$$f$$f^{\prime}$$h$

So $h$ is also a morphism between injective envelopes. Iterating the same
argument as above, we see that $h$ is a section; hence $h$ is an isomorphism
and so is its section, $g$. ∎

######  Corollary 5.3.

Suppose that the class ${\mathcal{H}}$ of embeddings contains all identity
morphisms of ${\mathcal{X}}$. Let $C$ be an object of ${\mathcal{X}}$ and
$(D,f)$ be an injective envelope of $C$. Then $C$ is injective if and only if
$f$ is an isomorphism.

###### Proof.

If $C$ is injective, then by the assumption, $(C,{\mathrm{id}_{C}})$ is an
injective envelope of $C$. So by Lemma 5.2 there exists an isomorphism
$g\colon C\longrightarrow D$ such that $g\circ{\mathrm{id}_{C}}=f$. Hence
$g=f$ and $f$ is an isomorphism.

Conversely, the class of all injective objects is clearly closed under
isomorphism. ∎

The injective envelope is defined by the complementary properties of
_essentialness_ of the embedding and _injectivity_ of the codomain. In fact it
is “extremal” with respect to these two properties, in the following sense.

######  Proposition 5.4 (Cf. [3, Proposition 2]).

Let ${C}$ be an object of ${\mathcal{X}}$ and $(E,g)$ be its injective
envelope.

  1. 1.

For any _essential_ embedding $f\colon{C}\longrightarrow{D}$, there exists a
(not necessarily unique) embedding $i\colon{D}\longrightarrow E$ with $i\circ
f=g$.

  2. 2.

For any embedding $h\colon C\longrightarrow{F}$ into an _injective_ ${F}$,
there exists a (not necessarily unique) embedding $k\colon
E\longrightarrow{F}$ with $k\circ g=h$.

${C}$$D$$E$$F$$f$$h$$g$$k$$i$

##  6 The MacNeille completion is the injective envelope

In this section we prove Theorem 1.5 and, using that, Theorem 1.4. Whenever we
use the notions introduced in the previous section, we take
${\mathcal{X}}={{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Cat}}$ and
${\mathcal{H}}$ to be the class of all fully faithful
${\mathcal{Q}}$-functors.

The key step is to give an intrinsic characterisation of essential embeddings.
For each ${\mathcal{Q}}$-functor
$f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$, we have
${\mathcal{Q}}$-functors
$f^{\ast}\colon{\mathcal{D}}\longrightarrow\mathcal{P}{\mathcal{C}}$ and
$f_{\ast}\colon{\mathcal{D}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$,
defined as $f^{\ast}(d)=({\mathcal{D}}(f(c),d))_{c\in{\mathcal{C}}}$ and
$f_{\ast}(d)=({\mathcal{D}}(d,f(c)))_{c\in{\mathcal{C}}}$ respectively. We
call $f$ dense if $f^{\ast}$ is an embedding, and codense if $f_{\ast}$ is an
embedding [15, Chapter 5].

For any ${\mathcal{Q}}$-category ${\mathcal{C}}$, the Yoneda embedding
$y_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$ is
$({\mathrm{id}_{{\mathcal{C}}}})^{\ast}$, whereas the co-Yoneda embedding
$y^{\dagger}_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
is $({\mathrm{id}_{{\mathcal{C}}}})_{\ast}$. In particular,
${\mathrm{id}_{{\mathcal{C}}}}$ is both dense and codense. Moreover,
$(y_{\mathcal{C}})^{\ast}\colon\mathcal{P}{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$
is the identity ${\mathcal{Q}}$-functor
${\mathrm{id}_{\mathcal{P}{\mathcal{C}}}}$ (the Yoneda lemma), so
$y_{\mathcal{C}}$ is dense (but in general not codense). Dually,
$y^{\dagger}_{\mathcal{C}}$ is codense (but in general not dense).
(Incidentally,
$(y_{\mathcal{C}})_{\ast}={\mathcal{C}}\mathbin{\swarrow}(-)\colon\mathcal{P}{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
and
$(y^{\dagger}_{\mathcal{C}})^{\ast}=(-)\mathbin{\searrow}{\mathcal{C}}\colon\mathcal{P}^{\dagger}{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$
[8, Remark 6.7].)

_The canonical embedding
$i_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{M}{\mathcal{C}}$ of
${\mathcal{C}}$ into its MacNeille completion is both dense and codense_ ([26,
Theorem 4.16], [8, Proposition 7.6] and [18, Theorem 6.5]), because
$(i_{\mathcal{C}})^{\ast}\colon\mathcal{M}{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$
and
$(i_{\mathcal{C}})_{\ast}\colon\mathcal{M}{\mathcal{C}}\longrightarrow\mathcal{P}^{\dagger}{\mathcal{C}}$
coincide with the (fully faithful) projections $p_{\mathcal{C}}$ and
$p^{\dagger}_{\mathcal{C}}$ respectively.

######  Proposition 6.1 (Cf. [3, Lemma 3]).

A ${\mathcal{Q}}$-functor is an essential embedding if and only if it is a
dense and codense embedding.

###### Proof.

Suppose that $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$ is an
essential embedding. Then the composite $f^{\ast}\circ
f\colon{\mathcal{C}}\longrightarrow\mathcal{P}{\mathcal{C}}$ maps each
$c\in{\mathcal{C}}$ to
$({\mathcal{D}}(fc^{\prime},fc))_{c^{\prime}\in{\mathcal{C}}}=({\mathcal{C}}(c^{\prime},c))_{c^{\prime}\in{\mathcal{C}}}$,
i.e., it is the Yoneda embedding $y_{\mathcal{C}}$. In particular,
$f^{\ast}\circ f$ is an embedding and hence so is $f^{\ast}$, showing that $f$
is dense. A similar argument shows that $f$ is codense.

Conversely, suppose that $f\colon{\mathcal{C}}\longrightarrow{\mathcal{D}}$ is
a dense and codense embedding. Take any ${\mathcal{Q}}$-functor
$g\colon{\mathcal{D}}\longrightarrow{\mathcal{E}}$ such that $g\circ f$ is an
embedding. We aim to show that $g$ is also an embedding, namely that for each
$d,d^{\prime}\in{\mathcal{D}}$ we have
${\mathcal{D}}(d,d^{\prime})={\mathcal{E}}(gd,gd^{\prime})$. Since $g$ is a
${\mathcal{Q}}$-functor, it suffices to show the inequality

${\mathcal{E}}(gd,gd^{\prime})\preceq_{\mathcal{Q}}{\mathcal{D}}(d,d^{\prime}).$
(5)

Since $f$ is dense, we have

${\mathcal{D}}(d,d^{\prime})=\mathcal{P}{\mathcal{C}}(f^{\ast}d,f^{\ast}d^{\prime})=\bigwedge_{c\in{\mathcal{C}}}{\mathcal{D}}(fc,d^{\prime})\mathbin{\swarrow}{\mathcal{D}}(fc,d).$
(6)

Since $f$ is codense, we have

${\mathcal{D}}(fc,d^{\prime})=\mathcal{P}^{\dagger}{\mathcal{C}}(f_{\ast}fc,f_{\ast}d^{\prime})=\bigwedge_{c^{\prime}\in{\mathcal{C}}}{\mathcal{D}}(d^{\prime},fc^{\prime})\mathbin{\searrow}{\mathcal{D}}(fc,fc^{\prime}).$
(7)

Substituting (7) into (6), we obtain

$\displaystyle{\mathcal{D}}(d,d^{\prime})$
$\displaystyle=\bigwedge_{c\in{\mathcal{C}}}\Big{(}\bigwedge_{c^{\prime}\in{\mathcal{C}}}{\mathcal{D}}(d^{\prime},fc^{\prime})\mathbin{\searrow}{\mathcal{D}}(fc,fc^{\prime})\Big{)}\mathbin{\swarrow}{\mathcal{D}}(fc,d)$
$\displaystyle=\bigwedge_{c,c^{\prime}\in{\mathcal{C}}}\Big{(}{\mathcal{D}}(d^{\prime},fc^{\prime})\mathbin{\searrow}{\mathcal{D}}(fc,fc^{\prime})\Big{)}\mathbin{\swarrow}{\mathcal{D}}(fc,d)$

(cf. [7, Theorem 1]). Hence to show (5) it suffices to show, for each
$c,c^{\prime}\in{\mathcal{C}}$,

${\mathcal{E}}(gd,gd^{\prime})\preceq_{\mathcal{Q}}\Big{(}{\mathcal{D}}(d^{\prime},fc^{\prime})\mathbin{\searrow}{\mathcal{D}}(fc,fc^{\prime})\Big{)}\mathbin{\swarrow}{\mathcal{D}}(fc,d).$

Using the adjointness relation (2) twice, this is equivalent to

${\mathcal{D}}(d^{\prime},fc^{\prime})\circ{\mathcal{E}}(gd,gd^{\prime})\circ{\mathcal{D}}(fc,d)\preceq_{\mathcal{Q}}{\mathcal{D}}(fc,fc^{\prime}),$

which can be checked easily as follows:

$\displaystyle{\mathcal{D}}(d^{\prime},fc^{\prime})\circ{\mathcal{E}}(gd,gd^{\prime})\circ{\mathcal{D}}(fc,d)$
$\displaystyle\preceq_{\mathcal{Q}}{\mathcal{E}}(gd^{\prime},gfc^{\prime})\circ{\mathcal{E}}(gd,gd^{\prime})\circ{\mathcal{E}}(gfc,gd)$
$\displaystyle\preceq_{\mathcal{Q}}{\mathcal{E}}(gfc,gfc^{\prime})$
$\displaystyle=\ \ {\mathcal{C}}(c,c^{\prime})$ $\displaystyle=\ \
{\mathcal{D}}(fc,fc^{\prime}).\qed$

Now we can show Theorem 1.5 claiming that for any ${\mathcal{Q}}$-category
${\mathcal{C}}$, $(\mathcal{M}{\mathcal{C}},i_{\mathcal{C}})$ is its injective
envelope. The ${\mathcal{Q}}$-category $\mathcal{M}{\mathcal{C}}$ is skeletal
and complete by Proposition 4.2, hence injective by Lemma 3.8. Since the
${\mathcal{Q}}$-functor $i_{\mathcal{C}}$ is a dense and codense embedding, it
is an essential embedding by Proposition 6.1.

Theorem 1.4 follows at once. Since all identity ${\mathcal{Q}}$-functors are
essential embeddings, by Corollary 5.3, a ${\mathcal{Q}}$-category
${\mathcal{C}}$ is injective if and only if the embedding
$i_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{M}{\mathcal{C}}$ is
an isomorphism. In particular, if ${\mathcal{C}}$ is injective, then it is
isomorphic to the skeletal and complete $\mathcal{M}{\mathcal{C}}$, so
${\mathcal{C}}$ is also skeletal and complete. The converse has already been
shown in Lemma 3.8.

We remark that, being the injective envelope, the MacNeille completion enjoys
the extremal properties described in Proposition 5.4; cf. [24, Proposition
5.5.5] and [8, Proposition 7.6 (e)].

##  7 Isbell convexity as categorical completeness

Finally, in this section we clarify the relationship of Theorem 1.3 due to
Kemajou, Künzi and Otafudu [16, Theorem 1], and the
${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{+}}$ case of our theorem.

We first work over a general quantale ${\mathcal{Q}}$ and provide an
alternative description of objects of the MacNeille completion. Given
(possibly infinite) sets $A$ and $B$, a ${\mathcal{Q}}$-matrix from $A$ to $B$
is simply a function $X\colon A\times B\longrightarrow{Q}$ [4]. We denote such
a ${\mathcal{Q}}$-matrix as $X\colon
A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}B$. Given
${\mathcal{Q}}$-matrices $X\colon
A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}B$, $Y\colon
B\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}C$ and $Z\colon
A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}C$, define the
${\mathcal{Q}}$-matrices:

  * 1.

$Y\circ X\colon A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}C$ as $(Y\circ
X)(a,c)=\bigvee_{b\in B}Y(b,c)\circ X(a,b)$;

  * 2.

$Z\mathbin{\swarrow}X\colon
B\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}C$ as
$(Z\mathbin{\swarrow}X)(b,c)=\bigwedge_{a\in
A}Z(a,c)\mathbin{\swarrow}X(a,b)$; and

  * 3.

$Y\mathbin{\searrow}Z\colon
A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}B$ as
$(Y\mathbin{\searrow}Z)(a,b)=\bigwedge_{c\in
C}Y(b,c)\mathbin{\searrow}Z(a,c)$.

It is routine to check that these operations on ${\mathcal{Q}}$-matrices
satisfy the adjointness relations analogous to (2), namely

$Y\preceq Z\mathbin{\swarrow}X\iff Y\circ X\preceq Z\iff X\preceq
Y\mathbin{\searrow}Z,$

where we order ${\mathcal{Q}}$-matrices of a fixed domain and codomain by the
pointwise order induced from $\preceq_{\mathcal{Q}}$. Also, for any set $A$ we
have the diagonal ${\mathcal{Q}}$-matrix $I_{A}\colon
A\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}A$ defined as
$I_{A}(a,a)=I_{\mathcal{Q}}$ and $I_{A}(a,a^{\prime})=\bot_{\mathcal{Q}}$ (the
least element of ${\mathcal{Q}}$) whenever $a\neq a^{\prime}$. Note that any
${\mathcal{Q}}$-category ${\mathcal{C}}$ can be seen as a
${\mathcal{Q}}$-matrix
${\mathcal{C}}\colon{\mathrm{ob}({\mathcal{C}})}\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}{\mathrm{ob}({\mathcal{C}})}$
satisfying $I_{{\mathrm{ob}({\mathcal{C}})}}\preceq{\mathcal{C}}$ and
${\mathcal{C}}\circ{\mathcal{C}}\preceq{\mathcal{C}}$. We can view a presheaf
$P$ over ${\mathcal{C}}$ as a ${\mathcal{Q}}$-matrix
$P\colon{\mathrm{ob}({\mathcal{C}})}\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}1$ satisfying
$P\circ{\mathcal{C}}\preceq P$, where $1$ denotes a singleton. Dually, a
copresheaf $R$ over ${\mathcal{C}}$ is a ${\mathcal{Q}}$-matrix $R\colon
1\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}{\mathrm{ob}({\mathcal{C}})}$
satisfying ${\mathcal{C}}\circ R\preceq R$. The notations for the
${\mathcal{Q}}$-functors (4) constituting the Isbell adjunction agree with
those for the above operations on ${\mathcal{Q}}$-matrices.

######  Proposition 7.1.

For a ${\mathcal{Q}}$-category ${\mathcal{C}}$, define the set

$\mathcal{U}_{\mathcal{C}}=\\{\,(X,Y)\mid
X\colon{\mathrm{ob}({\mathcal{C}})}\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}1,Y\colon
1\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}{\mathrm{ob}({\mathcal{C}})}\text{
and }Y\circ X\preceq{\mathcal{C}}\,\\}.$

A pair $(X,Y)$ of ${\mathcal{Q}}$-matrices
$X\colon{\mathrm{ob}({\mathcal{C}})}\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}1$ and $Y\colon
1\mathrel{\mathchoice{\ooalign{$\displaystyle\mapstochar\mkern
5.0mu$\cr$\displaystyle\longrightarrow$\cr}}{\ooalign{$\textstyle\mapstochar\mkern
5.0mu$\cr$\textstyle\longrightarrow$\cr}}{\ooalign{$\scriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptstyle\longrightarrow$\cr}}{\ooalign{$\scriptscriptstyle\mapstochar\mkern
5.0mu$\cr$\scriptscriptstyle\longrightarrow$\cr}}}{\mathrm{ob}({\mathcal{C}})}$
belongs to $\mathcal{M}{\mathcal{C}}$ if and only if it is maximal in
$\mathcal{U}_{\mathcal{C}}$, in the sense that (i)
$(X,Y)\in\mathcal{U}_{\mathcal{C}}$, and (ii) for any pair
$(X^{\prime},Y^{\prime})\in\mathcal{U}_{\mathcal{C}}$, if $X\preceq
X^{\prime}$ and $Y\preceq Y^{\prime}$ then $X=X^{\prime}$ and $Y=Y^{\prime}$.

###### Proof.

Suppose $(P,R)\in\mathcal{M}{\mathcal{C}}$. Then $R\circ
P=({\mathcal{C}}\mathbin{\swarrow}P)\circ P\preceq{\mathcal{C}}$, so
$(P,R)\in\mathcal{U}_{\mathcal{C}}$. Given any
$(X^{\prime},Y^{\prime})\in\mathcal{U}_{\mathcal{C}}$, $P\preceq X^{\prime}$
implies
$Y^{\prime}\preceq{\mathcal{C}}\mathbin{\swarrow}X^{\prime}\preceq{\mathcal{C}}\mathbin{\swarrow}P=R$;
similarly, $R\preceq Y^{\prime}$ implies $X^{\prime}\preceq P$.

Conversely, suppose that $(X,Y)$ satisfies conditions (i) and (ii). Then the
pair $(X,{\mathcal{C}}\mathbin{\swarrow}X)$ satisfies
$({\mathcal{C}}\mathbin{\swarrow}X)\circ X\preceq{\mathcal{C}}$, $X\preceq X$
and, by (i), $Y\preceq{\mathcal{C}}\mathbin{\swarrow}X$. So by (ii) we
conclude $Y={\mathcal{C}}\mathbin{\swarrow}X$. Similarly, using the pair
$(Y\mathbin{\searrow}{\mathcal{C}},Y)$ we see that
$X=Y\mathbin{\searrow}{\mathcal{C}}$. In order to show that $X$ is a presheaf
over ${\mathcal{C}}$, it suffices to show $X\circ{\mathcal{C}}\preceq X$.
Since $X=Y\mathbin{\searrow}{\mathcal{C}}$, it suffices to show
$X\circ{\mathcal{C}}\preceq Y\mathbin{\searrow}{\mathcal{C}}$, which is
equivalent to $Y\circ X\circ{\mathcal{C}}\preceq{\mathcal{C}}$. Using $Y\circ
X\preceq{\mathcal{C}}$ and
${\mathcal{C}}\circ{\mathcal{C}}\preceq{\mathcal{C}}$, we obtain the desired
result. Similarly, $Y$ is a copresheaf over ${\mathcal{C}}$. ∎

######  Proposition 7.2.

Let ${\mathcal{C}}$ be a ${\mathcal{Q}}$-category. For each
$(X,Y)\in\mathcal{U}_{\mathcal{C}}$, there exists
$(P,R)\in\mathcal{M}{\mathcal{C}}$ such that $X\preceq P$ and $Y\preceq R$.

###### Proof.

This is immediate from Zorn’s lemma, but a more explicit proof is also
possible.

We claim that
$(P,R)=(({\mathcal{C}}\mathbin{\swarrow}X)\mathbin{\searrow}{\mathcal{C}},{\mathcal{C}}\mathbin{\swarrow}X)$
has the desired properties.

First, we have $X\preceq P$ and $Y\preceq R$, since the former is equivalent
to $({\mathcal{C}}\mathbin{\swarrow}X)\circ X\preceq{\mathcal{C}}$, which in
turn is equivalent to
${\mathcal{C}}\mathbin{\swarrow}X\preceq{\mathcal{C}}\mathbin{\swarrow}X$,
whereas the latter is equivalent to $Y\circ X\preceq{\mathcal{C}}$.

We show $(P,R)\in\mathcal{M}{\mathcal{C}}$ using Proposition 7.1. $(P,R)$ is
in $\mathcal{U}_{\mathcal{C}}$ because $R\circ
P=({\mathcal{C}}\mathbin{\swarrow}X)\circ(({\mathcal{C}}\mathbin{\swarrow}X)\mathbin{\searrow}{\mathcal{C}})\preceq{\mathcal{C}}$
is equivalent to
$({\mathcal{C}}\mathbin{\swarrow}X)\mathbin{\searrow}{\mathcal{C}}\preceq({\mathcal{C}}\mathbin{\swarrow}X)\mathbin{\searrow}{\mathcal{C}}$.
To show $(P,R)$ is a maximal element in $\mathcal{U}_{\mathcal{C}}$, suppose
we are given any $(X^{\prime},Y^{\prime})\in\mathcal{U}_{\mathcal{C}}$ with
$P\preceq X^{\prime}$ and $R\preceq Y^{\prime}$. $R\preceq Y^{\prime}$ implies
$X^{\prime}\preceq Y^{\prime}\mathbin{\searrow}{\mathcal{C}}\preceq
R\mathbin{\searrow}{\mathcal{C}}=P$; so we have $P=X^{\prime}$. Using
$X\preceq P=X^{\prime}$, we have $Y^{\prime}\circ X\preceq Y^{\prime}\circ
X^{\prime}\preceq{\mathcal{C}}$, which is equivalent to
$Y^{\prime}\preceq{\mathcal{C}}\mathbin{\swarrow}X=R$. So we also have
$R=Y^{\prime}$. ∎

######  Remark 7.3.

Jawhari, Misane and Pouzet define an analogue of the MacNeille completion for
_symmetric_ 444A ${\mathcal{Q}}$-category ${\mathcal{C}}$ over a commutative
${\mathcal{Q}}$ is _symmetric_ if
${\mathcal{C}}(c,c^{\prime})={\mathcal{C}}(c^{\prime},c)$ for all
$c,c^{\prime}\in{\mathcal{C}}$. ${\mathcal{Q}}$-categories over a
_commutative_ (or more generally _involutive_) _integral_ 555A quantale
${\mathcal{Q}}$ is _integral_ if the unit $I_{\mathcal{Q}}$ is the greatest
element in $({Q},\preceq_{\mathcal{Q}})$. quantale ${\mathcal{Q}}$, and show
that it is the injective envelope [14]. Their definition is a variant of the
alternative description of the MacNeille completion given in Proposition 7.1.
As mentioned in Section 1, their result generalises Theorem 1.2.

We can characterise complete ${\mathcal{Q}}$-categories in terms of the
canonical embedding to the MacNeille completion.

######  Proposition 7.4.

A ${\mathcal{Q}}$-category ${\mathcal{C}}$ is complete if and only if the
embedding
$i_{\mathcal{C}}\colon{\mathcal{C}}\longrightarrow\mathcal{M}{\mathcal{C}}$ is
surjective (as a function between the sets of objects).

###### Proof.

Since $i_{\mathcal{C}}$ is always fully faithful and
$\mathcal{M}{\mathcal{C}}$ skeletal, $i_{\mathcal{C}}$ is surjective if and
only if it is an equivalence of ${\mathcal{Q}}$-categories [28, Proposition
4.4]. Since completeness is invariant under equivalence, if $i_{\mathcal{C}}$
is surjective then ${\mathcal{C}}$ is complete. For the converse, see e.g.,
[8, Proposition 7.6]. ∎

######  Corollary 7.5.

A ${\mathcal{Q}}$-category ${\mathcal{C}}$ is complete if and only if, given
any $(X,Y)\in\mathcal{U}_{\mathcal{C}}$, there exists $c\in{\mathcal{C}}$ such
that $X\preceq{\mathcal{C}}(-,c)$ and $Y\preceq{\mathcal{C}}(c,-)$.

Now let us specialise to the case ${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq
0}_{+}}$. Extending the notion of Isbell convexity for di-spaces slightly, let
us say a Lawvere metric space (= ${\overline{\mathbb{R}}^{\geq
0}_{+}}$-category) ${\mathcal{C}}$ is Isbell convex if, for any family
$((c_{i},x_{i},y_{i}))_{i\in I}$ where $c_{i}\in{\mathcal{C}}$ and
$x_{i},y_{i}\in[0,\infty]$, if $x_{i}+y_{j}\geq{\mathcal{C}}(c_{i},c_{j})$
holds for each $i,j\in I$, then there exists $c\in{\mathcal{C}}$ such that
$x_{i}\geq{\mathcal{C}}(c_{i},c)$ and $y_{i}\geq{\mathcal{C}}(c,c_{i})$ for
all $i\in I$.

######  Proposition 7.6.

A Lawvere metric space is Isbell convex if and only if it is complete (in the
sense of Definition 3.6).

The above proposition is immediate from Corollary 7.5. So, modulo the above
discussion (and the difference between Lawvere metric spaces and di-spaces),
our Theorem 1.4 yields Theorem 1.3 when
${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{+}}$. We remark that the proof
of Theorem 1.3 in [16], however, relies heavily on Zorn’s lemma and is quite
different from our proof.

A completely parallel comment applies to the relationship of our theorem when
${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{\mathrm{max}}}$ and Künzi and
Otafudu’s characterisation of injective ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{max}}}$-categories by _q-spherical completeness_ in [17, Theorem
2].

## References

  * [1] Jiří Adámek, Horst Herrlich, Jiří Rosickỳ, and Walter Tholen.  Injective hulls are not natural.  Algebra Universalis, 48(4):379–388, 2002.
  * [2] Nachman Aronszajn and Prom Panitchpakdi.  Extension of uniformly continuous transformations and hyperconvex metric spaces.  Pacific Journal of Mathematics, 6(3):405–439, 1956.
  * [3] Bernhard Banaschewski and Günter Bruns.  Categorical characterization of the MacNeille completion.  Archiv der Mathematik, 18(4):369–377, 1967.
  * [4] Renato Betti, Aurelio Carboni, Ross Street, and Robert Walters.  Variation through enrichment.  Journal of Pure and Applied Algebra, 29(2):109–127, 1983.
  * [5] G.C.L. Brümmer and R.-E. Hoffmann.  An external characterization of topological functors.  In Categorical Topology, pages 136–151. Springer, 1976.
  * [6] Guy Cohen, Stéphane Gaubert, and Jean-Pierre Quadrat.  Duality and separation theorems in idempotent semimodules.  Linear Algebra and its Applications, 379:395–422, 2004.
  * [7] Andreas W.M. Dress.  Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces.  Advances in Mathematics, 53(3):321–402, 1984.
  * [8] Richard Garner.  Topological functors as total categories.  Theory and Applications of Categories, 29(15):406–421, 2014.
  * [9] Horst Herrlich.  Initial completions.  Mathematische Zeitschrift, 150(2):101–110, 1976.
  * [10] Horst Herrlich.  Hyperconvex hulls of metric spaces.  Topology and its Applications, 44(1-3):181–187, 1992.
  * [11] Hiroshi Hirai and Shungo Koichi.  On tight spans for directed distances.  Annals of Combinatorics, 16(3):543–569, 2012.
  * [12] Dirk Hofmann.  Injective spaces via adjunction.  Journal of Pure and Applied Algebra, 215(3):283–302, 2011.
  * [13] John R. Isbell.  Six theorems about injective metric spaces.  Commentarii Mathematici Helvetici, 39(1):65–76, 1964.
  * [14] El Mostapha Jawhari, Driss Misane, and Maurice Pouzet.  Retracts: graphs and ordered sets from the metric point of view.  Contemporary Mathematics, 57:175–226, 1986.
  * [15] G.M. Kelly.  Basic concepts of enriched category theory, volume 64 of London Mathematical Society Lecture Note Series.  Cambridge University Press, 1982.  Also available online in Reprints in Theory and Applications of Categories, No. 10 (2005) pp. 1–136.
  * [16] Elisabeth Kemajou, Hans-Peter A. Künzi, and Olivier Olela Otafudu.  The Isbell-hull of a di-space.  Topology and its Applications, 159(9):2463–2475, 2012.
  * [17] Hans-Peter A. Künzi and Olivier Olela Otafudu.  The ultra-quasi-metrically injective hull of a $T_{0}$-ultra-quasi-metric space.  Applied Categorical Structures, 21(6):651–670, 2013.
  * [18] Hongliang Lai and Lili Shen.  Fixed points of adjoint functors enriched in a quantaloid.  Fuzzy Sets and Systems, 321:1–28, 2017.
  * [19] F. William Lawvere.  Metric spaces, generalized logic, and closed categories.  Rendiconti del seminario matématico e fisico di Milano, XLIII:135–166, 1973.  Also available online in Reprints in Theory and Applications of Categories, No. 1 (2001) pp. 1–37.
  * [20] Grigory L. Litvinov, Victor P. Maslov, and Grigory B. Shpiz.  Idempotent functional analysis: an algebraic approach.  Mathematical Notes, 69(5-6):696–729, 2001.
  * [21] Holbrook Mann MacNeille.  Partially ordered sets.  Transactions of the American Mathematical Society, 42(3):416–460, 1937.
  * [22] Christopher J. Mulvey.  &.  Supplemento ai Rendiconti del Circolo Matemàtico di Palermo. Serie II, 12:99–104, 1986.
  * [23] Kimmo I. Rosenthal.  Quantaloids, enriched categories and automata theory.  Applied Categorical Structures, 3(3):279–301, 1995.
  * [24] Lili Shen.  Adjunctions in Quantaloid-enriched Categories.  PhD thesis, Sichuan University, 2014.
  * [25] Lili Shen and Walter Tholen.  Topological categories, quantaloids and Isbell adjunctions.  Topology and its Applications, 200:212–236, 2016.
  * [26] Lili Shen and Dexue Zhang.  Categories enriched over a quantaloid: Isbell adjunctions and Kan adjunctions.  Theory and Applications of Categories, 28(20):577–615, 2013.
  * [27] Ross Street.  The core of adjoint functors.  Theory and Applications of Categories, 27(4):47–64, 2012.
  * [28] Isar Stubbe.  Categorical structures enriched in a quantaloid: categories, distributors and functors.  Theory and Applications of Categories, 14(1):1–45, 2005.
  * [29] Isar Stubbe.  Categorical structures enriched in a quantaloid: tensored and cotensored categories.  Theory and Applications of Categories, 16(14):283–306, 2006.
  * [30] Isar Stubbe.  Cocomplete $\mathcal{Q}$-categories are precisely the injectives wrt. fully faithful functors, 2006.  Unpublished note available from the author’s website.
  * [31] Isar Stubbe.  The double power monad is the composite power monad.  Fuzzy Sets and Systems, 313:25–42, 2017.
  * [32] Simon Willerton.  Tight spans, Isbell completions and semi-tropical modules.  Theory and Applications of Categories, 28(22):696–732, 2013.