# Enriched categories and tropical mathematics

Soichiro Fujii  Research Institute for Mathematical Sciences, Kyoto University
Kyoto 606-8502, Japan<EMAIL_ADDRESS>
###### Abstract.

This is a survey paper on the connection of enriched category theory over a
quantale and tropical mathematics. Quantales or complete idempotent semirings,
as well as matrices with coefficients in them, are fundamental objects in both
fields. We first explain standard category-theoretic constructions on
matrices, namely composition, right extension, right lifting and the Isbell
hull. Along the way, we review known reformulations (due to Elliott and
Willerton) of tropical polytopes, directed tight spans and the
Legendre–Fenchel transform by means of these constructions, illustrating their
ubiquity in tropical mathematics and related fields. We then consider complete
semimodules over a quantale ${\mathcal{Q}}$, a tropical analogue of vector
spaces over a field, and mention Stubbe’s result identifying them with
skeletal and complete ${\mathcal{Q}}$-categories. With the aim to bridge a gap
between enriched category theory and tropical mathematics, we assume no
knowledge in either field.

###### Key words and phrases:

Enriched category, tropical mathematics, quantale

###### 2010 Mathematics Subject Classification:

18D20, 06F07, 54E35

##  1\. Introduction

_Tropical mathematics_ (also called idempotent mathematics) is mathematics
over an idempotent semiring, instead of over the fields of real or complex
numbers as in many branches of ordinary mathematics. A prototypical example of
idempotent semirings is the so-called _min-plus semiring_
$([-\infty,\infty],\infty,0,\min,+)$, defined as the set $[-\infty,\infty]$ of
extended real numbers equipped with the minimum operation as (idempotent)
addition and the ordinary addition $+$ as multiplication. Such structures
naturally arise in many branches of mathematical sciences, including
operations research [CG91], formal language theory [Sim94, Pin98],
mathematical physics [LMS01] and algebraic geometry [Vir01].

_Enriched categories_ , on the other hand, are a generalisation of categories
[ML98] defined relative to a _base_. We can choose arbitrary _monoidal
categories_ as the base, of which idempotent semirings are a special case. The
theory works best when the base enjoys certain completeness properties, and in
the case of idempotent semiring, imposing these additional completeness
assumptions results in the notion of (unital) _quantale_ [Mul86]. Preordered
sets, metric spaces and ultrametric spaces are all instances of enriched
categories over a quantale [Law73].

In this paper we take a look at a branch of tropical mathematics, namely
_linear algebra over a quantale_ (cf. [CGQ04]), from the enriched categorical
perspective. We believe that enriched category theory can provide an abstract
framework to tropical mathematics, which would help us to recognise various
easy facts that hold for purely formal reasons, and focus on genuine problems.
On the other hand, tropical mathematics can offer novel interpretation to
category theoretic concepts, which might eventually lead to discovery of
useful categorical notions of tropical origin, along the lines of Lawvere’s
notion of Cauchy completeness generalised from metric spaces to enriched
categories [Law73]. The purpose of this paper is to lay the foundations for a
further fruitful interplay between enriched categories and tropical
mathematics, by collecting basic notions and surveying known results which
suggest various links between the two fields. Accordingly, we have tried to
make this paper mostly self-contained and accessible to both category
theorists and tropical mathematicians.

The outline of this paper is as follows. After reviewing the notion of
quantale (Section 2), we move on to study matrices over a quantale
${\mathcal{Q}}$ (called ${\mathcal{Q}}$-matrices) in Section 3. Matrices over
a quantale admit not only composition, but also the operations of _right
extension_ and _right lifting_ , which may be computed by the formulas dual to
the one for composition. Right extensions and right liftings of
${\mathcal{Q}}$-matrices enable us to define the _Isbell hull_ of a
${\mathcal{Q}}$-matrix (Section 4), which is known to unify such constructions
as directed tight spans of metric spaces [Wil13], lower semicontinuous convex
functions on $\mathbb{R}^{n}$ [Wil15] and tropical polytopes [Ell17]; we also
provide brief expositions of these results.

In Section 5 we study complete semimodules over a quantale (cf. [CGQ04,
BK12]), a tropical analogue of vector spaces over a field. It turns out that
the Isbell hull of a ${\mathcal{Q}}$-matrix naturally admits the structure of
a complete semimodule over ${\mathcal{Q}}$, and conversely, any complete
semimodule over ${\mathcal{Q}}$ can be realised as the Isbell hull of some
${\mathcal{Q}}$-matrix. In Section 6 we introduce categories enriched over a
quantale ${\mathcal{Q}}$ (called ${\mathcal{Q}}$-categories). Any complete
semimodule over ${\mathcal{Q}}$ naturally induces a ${\mathcal{Q}}$-category,
and those ${\mathcal{Q}}$-categories arising from a complete semimodule over
${\mathcal{Q}}$ are characterised by the intrinsic properties of _skeletality_
and _completeness_ [Stu06].

### Acknowledgements

We are grateful to Jonathan Elliott, Masahito Hasegawa and Simon Willerton for
their encouragement and insightful discussion.

We would also like to thank anonymous reviewers who provided helpful comments
on the earlier version of this paper.

##  2\. Quantales

We first introduce _quantales_ , also known as _complete idempotent
semirings_. They are the enriching (or base) categories in the portion of
enriched category theory we shall be concerned with; in tropical mathematics,
elements of a quantale are often considered as _scalars_ , and play the role
similar to that of real or complex numbers in ordinary mathematics.

######  Definition 2.1 ([Mul86]).

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 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)$.

Though we have introduced quantales in an order-theoretic manner, we could
have introduced them in a more algebraic manner. In tropical mathematics, it
is customary to start from the notion of idempotent semiring, namely a
semiring $(Q,\mathbf{0},I,\oplus,\circ)$ with an idempotent addition: $x\oplus
x=x$. Given such an idempotent semiring, its additive part
$(Q,\mathbf{0},\oplus)$ is an idempotent commutative monoid, and thus induces
a partial order $\preceq$ on $Q$ by $x\preceq y$ if and only if $x\oplus y=y$.
The resulting poset $(Q,\preceq)$ is an (upper) semilattice (= poset with all
finite suprema), with the least element $\mathbf{0}$ and the binary supremum
operation $\oplus$. Therefore quantales may also be construed as idempotent
semirings with an additional _completeness_ property.

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. Although many examples of quantales
we shall consider below are in fact commutative, we work within the more
general noncommutative setting in order to underline a certain parallelism
between the structure of a quantale and that of _matrices_ (of arbitrary
dimensions) with coefficients in a quantale (Section 3). For matrices the
multiplication (or composition) is not commutative; indeed, commutativity of
multiplication does not even make sense.

The notion of _adjunction_ between posets is central to our approach (see also
[CGQ04, BK12]). 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 (or _Galois connection_) 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 (see [Str12]).

We record the following well-known fact, to which we shall resort frequently
in the sequel.

######  Proposition 2.2 (See e.g., [DP02, Proposition 7.34]).

Let $(L,\preceq_{L})$ be a complete lattice and $(P,\preceq_{P})$ be a poset.
A function $f\colon L\longrightarrow P$ preserves arbitrary suprema if and
only if there exists a function $u\colon P\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 theory of quantales. In Sections 3 and 5, we shall see that
similar structures arise from matrices with coefficients in a quantale, and
complete semimodules over a quantale, respectively.

We conclude this section with some examples of quantales.

######  Example 2.3.

The max-plus quantale
${\overline{\mathbb{R}}_{\mathrm{max},+}}=([-\infty,\infty],\leq,0,+)$. Here,
$([-\infty,\infty],\leq)$ is the poset $(\mathbb{R},\leq)$ of all real numbers
(with the usual order) extended with the least element $-\infty$ and the
greatest element $\infty$. The multiplication $+$ is the unique supremum-
preserving extension to $[-\infty,\infty]$ of the ordinary addition of real
numbers; the right extension/right lifting is then uniquely determined by the
adjointness relation (2), and is an extension of the ordinary subtraction of
real numbers; see Table 1. These extended addition and subtraction appear in
[Law84]. The term “max-plus”, common in tropical mathematics, derives from the
fact that as an idempotent semiring, the addition and the multiplication in
${\overline{\mathbb{R}}_{\mathrm{max},+}}$ are the max operation and (an
extension of) the ordinary addition respectively.

Sometimes in the literature the _max-plus semifield_
$([-\infty,\infty),-\infty,0,\max,+)$, which is basically
${\overline{\mathbb{R}}_{\mathrm{max},+}}$ without the greatest element
$\infty$, is used [CG91, LMS01]. Part of the reasons to prefer it seems to lie
in the fact that it is a _semifield_ , meaning that every non-zero (i.e.,
$\neq-\infty$; note that the zero in this semiring is $-\infty$) element has a
multiplicative inverse (given by $x\mapsto-x$). However, it is our impression
that quantales are much more convenient mathematical objects to work with than
idempotent semifields. For instance, the underlying poset of an idempotent
semifield cannot be a complete lattice except for trivial cases.

$y+x$ |  | $x$ |
---|---|---|---
$\infty$ | $s$ | $-\infty$
| $\infty$ | $\infty$ | $\infty$ | $-\infty$
$y$ | $t$ | $\infty$ | $t+s$ | $-\infty$
| $-\infty$ | $-\infty$ | $-\infty$ | $-\infty$

$z-y$ |  | $y$ |
---|---|---|---
$\infty$ | $t$ | $-\infty$
| $\infty$ | $\infty$ | $\infty$ | $\infty$
$z$ | $u$ | $-\infty$ | $u-t$ | $\infty$
| $-\infty$ | $-\infty$ | $-\infty$ | $\infty$

Table 1. The operation tables for $y+x\ (=y\circ x)$ and $z-y\
(=z\mathbin{\swarrow}y=y\mathbin{\searrow}z)$ in
${\overline{\mathbb{R}}_{\mathrm{max},+}}$. $s,t$ and $r$ denote real numbers.

######  Example 2.4.

The min-plus quantale
${\overline{\mathbb{R}}_{\mathrm{min},+}}=([-\infty,\infty],\geq,0,+)$. The
underlying poset $([-\infty,\infty],\geq)$ is the poset $(\mathbb{R},\geq)$ of
all real numbers ordered by the _opposite_ of the usual order, extended with
the _greatest_ element $-\infty$ and the _least_ element $\infty$. The
extension of $+$ is again uniquely determined by the requirement that it
should be part of a quantale structure.

In fact, the quantale ${\overline{\mathbb{R}}_{\mathrm{min},+}}$ is isomorphic
to ${\overline{\mathbb{R}}_{\mathrm{max},+}}$ under the mapping $x\mapsto-x$.
So they are just different ways of presenting the same structure. However,
note that this does not mean that the operation tables are the _same_ for
${\overline{\mathbb{R}}_{\mathrm{max},+}}$ and
${\overline{\mathbb{R}}_{\mathrm{min},+}}$; for instance, we have
$-\infty+\infty=-\infty$ in ${\overline{\mathbb{R}}_{\mathrm{max},+}}$, but
have $-\infty+\infty=\infty$ in ${\overline{\mathbb{R}}_{\mathrm{min},+}}$.

######  Example 2.5.

The nonnegative min-plus quantale (also called the _Lawvere quantale_)
${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}=([0,\infty],\geq,0,+)$.
This is ${\overline{\mathbb{R}}_{\mathrm{min},+}}$ restricted to the
nonnegative (i.e., $\geq 0$) part. The $+$ operation is the restriction of $+$
for ${\overline{\mathbb{R}}_{\mathrm{min},+}}$ to $[0,\infty]$, which is
anyway the only sensible extension of the ordinary addition. 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$. This quantale is introduced in [Law73] for a category-theoretic
approach to the theory of metric spaces.

Note that by restricting the isomorphism between
${\overline{\mathbb{R}}_{\mathrm{max},+}}$ and
${\overline{\mathbb{R}}_{\mathrm{min},+}}$, ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{min},+}}$ is isomorphic to the nonpositive max-plus quantale (in
the obvious sense), but it is not isomorphic to “the nonnegative max-plus
quantale”; indeed, there is no quantale that deserves this name. It is
impossible to endow a quantale structure on the poset $([0,\infty],\leq)$ in
such a way that its multiplication is given by an extension of the ordinary
addition $+$, because the quantale axioms would force $0+x=0$ for all
$x\in[0,\infty]$.

######  Example 2.6.

One can also consider the “discrete” variants of the quantales
${\overline{\mathbb{R}}_{\mathrm{max},+}}$
($\cong{\overline{\mathbb{R}}_{\mathrm{min},+}}$) or
${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$, replacing the real
numbers by the integers. The discrete variant of
${\overline{\mathbb{R}}_{\mathrm{min},+}}$ is used in [Fuj14] in connection to
discrete convex analysis [Mur03].

######  Example 2.7.

The nonnegative min-max quantale ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{min,max}}}=([0,\infty],\geq,0,\max)$. Its underlying poset
$([0,\infty],\geq)$ is the same as that of ${\overline{\mathbb{R}}^{\geq
0}_{\mathrm{min},+}}$. We take the binary max operation with respect to the
usual ordering $\leq$, namely the binary infimum 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 infimum 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 [Mul86]. The poset $([0,\infty],\geq)$, or more generally any totally
ordered complete lattice, is a locale.

######  Example 2.8.

The truth value quantale (or 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$. This is also used in [Law73].

######  Example 2.9.

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. It has been used in connection to
formal language theory, both from the categorical side [Ros95] as well as from
the tropical side [Pin98].

######  Example 2.10.

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. In fact, this is obtained from ${\mathbf{2}}$ via a general
construction of _matrix quantale_ ; see the next section.

##  3\. Matrices

In this section we study matrices over a quantale.

######  Definition 3.1.

Let ${\mathcal{Q}}$ be a quantale, and $A$ and $B$ be (possibly infinite)
sets. A ${\mathcal{Q}}$-matrix (or simply a matrix) from $A$ to $B$ is a
$(B\times A)$-indexed family of elements of $Q$. If $X=(X_{b,a})_{b\in B,a\in
A}$ is a ${\mathcal{Q}}$-matrix from $A$ to $B$, we denote it by $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$.

In particular, if $A=\\{\,1,\dots,m\,\\}$ and $B=\\{\,1,\dots,n\,\\}$ for some
natural numbers $m$ and $n$, then a ${\mathcal{Q}}$-matrix $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$ is nothing but an
$(n\times m)$-matrix with coefficients in ${\mathcal{Q}}$, which we may write
as

$X=\left[\begin{tabular}[]{c c c c}$X_{1,1}$&$X_{1,2}$&$\cdots$&$X_{1,m}$\\\
$X_{2,1}$&$X_{2,2}$&$\cdots$&$X_{2,m}$\\\
$\vdots$&$\vdots$&$\ddots$&$\vdots$\\\
$X_{n,1}$&$X_{n,2}$&$\cdots$&$X_{n,m}$\\\ \end{tabular}\right]$ (3)

as usual.

For any set $A$ we have the identity matrix $I_{A}$

$(I_{A})_{a,a^{\prime}}=\begin{cases}I_{\mathcal{Q}}&\text{ if
}a=a^{\prime},\\\ \mathbf{0}_{\mathcal{Q}}&\text{ otherwise,}\end{cases}$

where $\mathbf{0}_{\mathcal{Q}}$ denotes the least element in
$(Q,\preceq_{\mathcal{Q}})$. Given 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$ and $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$, we may define their
composition $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 follows:

$(Y\circ X)_{c,a}=\bigvee_{b\in B}(Y_{c,b}\circ_{\mathcal{Q}}X_{b,a}).$ (4)

Since the supremum $\bigvee$ corresponds to (possibly infinitary) addition in
a quantale, (4) may be seen as the tropical analogue of the usual matrix
multiplication formula. It can be easily checked that the composition
operation satisfies the familiar laws, namely

$X\circ I_{A}=X,\quad I_{B}\circ X=X\quad\text{and}\quad Z\circ(Y\circ
X)=(Z\circ Y)\circ X$ (5)

for all $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
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}}}D$.

We put a partial order $\preceq_{A,B}$ on the set ${{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,B)$ of all ${\mathcal{Q}}$-matrices from $A$ to $B$ in
an entrywise manner, namely $X\preceq_{A,B}X^{\prime}$ if and only if for all
$b\in B$ and $a\in A$, $X_{b,a}\preceq_{\mathcal{Q}}X^{\prime}_{b,a}$. The
poset $({{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(A,B),\preceq_{A,B})$
is isomorphic to the $(B\times A)$-fold product of
$(Q,\preceq_{\mathcal{Q}})$, and hence is again a complete lattice. We
sometimes omit the subscripts $A,B$ in $\preceq_{A,B}$. One easily verifies
that the composition operation preserves arbitrary suprema in each variable:

$(\bigvee_{i\in I}Y_{i})\circ X=\bigvee_{i\in I}(Y_{i}\circ
X)\quad\text{and}\quad Y\circ(\bigvee_{i\in I}X_{i})=\bigvee_{i\in I}(Y\circ
X_{i})$ (6)

for all $X,X_{i}\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$ and $Y,Y_{i}\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$.

Notice the evident parallelism of the structure of a quantale (Definition 2.1)
and that of matrices. We see in particular that for any set $A$, the set of
all matrices of type
$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$ admits a natural
structure of a quantale, forming a matrix quantale (cf. Example 2.10). Indeed,
taking into account the non-square matrices as well, we may summarise
equations (5) and (6) by saying that for any quantale ${\mathcal{Q}}$,
${\mathcal{Q}}$-matrices (of arbitrary dimensions) form a _quantaloid_
${{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}$. We do not need a formal
definition of quantaloid in this paper; informally, it is a “many-object
version” of quantale, just as groupoids are groups with many objects. See
e.g., [Ros95, Stu05, SZ13].

The structural similarity of a quantale and matrices over it suggests the
possibility of extending the constructions in the former, in particular that
of residuation, to the latter. This is indeed the case, and to do so we need
no more than Proposition 2.2. For any ${\mathcal{Q}}$-matrix $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$ and a set $C$, the first
of the equations (6) says that the function

$(-)\circ X\colon{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(B,C)\longrightarrow{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,C)$

preserves arbitrary suprema. Hence we obtain its right adjoint

$(-)\mathbin{\swarrow}X\colon{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,C)\longrightarrow{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(B,C),$

called the right extension along $X$. Similarly, for any
${\mathcal{Q}}$-matrix $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 a set $A$, the
function

$Y\circ(-)\colon{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,B)\longrightarrow{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,C)$

has a right adjoint

$Y\mathbin{\searrow}(-)\colon{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,C)\longrightarrow{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,B),$

called the right lifting along $Y$.

Analogously to (2), the adjointness relation

$Y\preceq_{B,C}Z\mathbin{\swarrow}X\iff Y\circ X\preceq_{A,C}Z\iff
X\preceq_{A,B}Y\mathbin{\searrow}Z$ (7)

holds for any triple of 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$, implying the third type
of adjunction

${{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,B)$${{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(B,C)^{\mathrm{op}}$$Z\mathbin{\swarrow}(-)$$(-)\mathbin{\searrow}Z$$\dashv$
(8)

(sometimes called the _Isbell adjunction_ [SZ13]). Note that, since elements
of $Q$ can be identified with ${\mathcal{Q}}$-matrices of type
$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}}}1$, where $1=\\{\ast\\}$ is
a singleton, (2) may be regarded as a special case of (7) where $A=B=C=1$.

Let us now take a closer look at the operations of right extension and right
lifting of matrices. Given 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$ 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$, the right extension of
$Z$ along $X$ is a matrix $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$. First observe that we
have

$(Z\mathbin{\swarrow}X)\circ X\preceq_{A,C}Z,$ (9)

since by (7) this is equivalent to
$Z\mathbin{\swarrow}X\preceq_{B,C}Z\mathbin{\swarrow}X$, which holds
trivially. In more detail, the adjointness relation (7) says that
$Z\mathbin{\swarrow}X$ is the largest matrix of type
$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$ with this property.
Namely, it is characterised by (9) together with

$\text{for any }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,\ Y\circ
X\preceq_{A,C}Z\text{ implies }Y\preceq_{B,C}Z\mathbin{\swarrow}X.$

Explicitly, the matrix $Z\mathbin{\swarrow}X$ is given by

$(Z\mathbin{\swarrow}X)_{c,b}=\bigwedge_{a\in
A}(Z_{c,a}\mathbin{\swarrow}X_{b,a}).$ (10)

The formula (10) may be verified by showing the adjointness relation (7)
directly. Similarly, the right lifting $Y\mathbin{\searrow}Z$ is abstractly
characterised by the properties

$Y\circ(Y\mathbin{\searrow}Z)\preceq_{A,C}Z$

and

$\text{for any }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\circ
X\preceq_{A,C}Z\text{ implies }X\preceq_{A,B}Y\mathbin{\searrow}Z,$

whereas concretely it is given by the formula

$(Y\mathbin{\searrow}Z)_{b,a}=\bigwedge_{c\in
C}(Y_{c,b}\mathbin{\searrow}Z_{c,a}).$ (11)

We now introduce miscellaneous notions on matrices. For any matrix $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$, its transpose
$X^{\top}\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}}}A$ is defined by
$X^{\top}_{a,b}=X_{b,a}$. Recall that $1=\\{\ast\\}$ is a singleton. As
already mentioned, matrices of type
$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}}}1$ can be identified with
elements of the base quantale ${\mathcal{Q}}$, and thus are also called
scalars. If $X\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}}}1$ is a scalar, then by
abuse of notation we also denote by $X$ its unique entry $X_{\ast,\ast}\in Q$.
For any set $A$, matrices of type
$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}}}A$ are column vectors of
size $A$, and dually those of type
$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}}}1$ are row vectors of size
$A$; cf. (3). Note that a column vector $X\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}}}A$ and a row vector $Y\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}}}1$ of the same size compose,
and give rise to a scalar

$Y\circ X=\bigvee_{a\in A}(Y_{\ast,a}\circ X_{a,\ast}),$

which may be thought of as the _scalar product_ of $Y$ and $X$. For any matrix
$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$ and $a\in A$, the $a$-th
column vector of $X$ is a column vector $X_{-,a}\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}}}B$ of size $B$ defined by
$(X_{-,a})_{b,\ast}=X_{b,a}$; dually, for any $b\in B$ we have the $b$-th row
vector of $X$ $X_{b,-}=((X^{\top})_{-,b})^{\top}$.

######  Example 3.2.

Willerton [Wil15] observes that the Legendre–Fenchel transform (see e.g.,
[Roc70, Section 12]) is an instance of right extension/right lifting of
matrices. Recall that the Legendre–Fenchel transform on a finite-dimensional
real vector space $\mathbb{R}^{n}$ maps any function
$f\colon\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$ to its conjugate, which
is a function $f^{\ast}$ of type
$(\mathbb{R}^{n})^{\ast}\longrightarrow[-\infty,\infty]$, where
$(\mathbb{R}^{n})^{\ast}=\mathbb{R}^{n}$ is the dual vector space of the
original $\mathbb{R}^{n}$. Using the pairing function ${\langle-,-\rangle}$
defined by ${\langle p,v\rangle}=\sum_{i=1}^{n}p_{i}v_{i}$ for each
$p=(p_{1},\dots,p_{n})\in(\mathbb{R}^{n})^{\ast}$ and
$v=(v_{1},\dots,v_{n})\in\mathbb{R}^{n}$, the formula for the conjugate
$f^{\ast}$ is given by

$f^{\ast}(p)=\sup_{v\in\mathbb{R}^{n}}\\{{\langle p,v\rangle}-f(v)\\}$ (12)

for each $p\in(\mathbb{R}^{n})^{\ast}$.

To understand this construction via matrices, we first regard the pairing
function ${\langle-,-\rangle}$ as an
${\overline{\mathbb{R}}_{\mathrm{min},+}}$-matrix
${\langle-,-\rangle}\colon\mathbb{R}^{n}\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}}}(\mathbb{R}^{n})^{\ast}$. A
function $f$ of type $\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$ may be
identified with an ${\overline{\mathbb{R}}_{\mathrm{min},+}}$-matrix
$f\colon\mathbb{R}^{n}\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 likewise a function
$g$ of type $(\mathbb{R}^{n})^{\ast}\longrightarrow[-\infty,\infty]$ with an
${\overline{\mathbb{R}}_{\mathrm{min},+}}$-matrix $g\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}}}(\mathbb{R}^{n})^{\ast}$.
Then we have $f^{\ast}={\langle-,-\rangle}\mathbin{\swarrow}f$; see (10). Note
that infima in ${\overline{\mathbb{R}}_{\mathrm{min},+}}$ (denoted by
$\bigwedge$ in (10)) amount to suprema with respect to the usual order
(denoted by $\sup$ in (12)).

The Legendre–Fenchel transform works in the converse direction as well,
mapping a function
$g\colon(\mathbb{R}^{n})^{\ast}\longrightarrow[-\infty,\infty]$ to its
conjugate $g^{\ast}\colon\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$ given
by essentially the same formula:

$g^{\ast}(v)=\sup_{p\in(\mathbb{R}^{n})^{\ast}}\\{{\langle
p,v\rangle}-g(p)\\}.$

Of course, this can be expressed as
$g^{\ast}=g\mathbin{\searrow}{\langle-,-\rangle}$ using matrices.

The Legendre–Fenchel transform is an important tool in convex analysis. One
reason for this importance is that for any function
$f\colon\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$, $(f^{\ast})^{\ast}$ is
its convex envlope, i.e., the least (with respect to the pointwise order
$\leq$) lower-semicontinuous convex function above $f$. In particular, lower-
semicontinuous convex functions can be characterised as the “fixed points” of
the Legendre–Fenchel transform; we shall revisit this point in the next
section.

##  4\. The Isbell hull of a matrix

In this section we introduce the notion of Isbell hull of a matrix. It
incorporates many important constructions in tropical mathematics and related
fields, such as the tropical polytope generated by a set of points [DS04], the
directed tight span of a (generalised) metric space [HK12, KKO12], and the set
of lower-semicontinuous convex functions on $\mathbb{R}^{n}$.

######  Definition 4.1 ([SZ13, Section 4]).

Let ${\mathcal{Q}}$ be a quantale 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$ be a
${\mathcal{Q}}$-matrix. The Isbell hull of $Z$, denoted by $\mathrm{Isb}(Z)$,
is the set of all pairs $(X,Y)$ of ${\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}}}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}}}C$ such that both
$Y=Z\mathbin{\swarrow}X$ and $X=Y\mathbin{\searrow}Z$ hold.

In this section we treat the Isbell hull of a matrix only as a _set_ of
certain pairs of matrices, but in fact it has rich structure, as we shall see
in Section 5. The term “Isbell hull” is already used in [KKO12] to refer to a
special case of Definition 4.1.

The Isbell hull construction, like many important constructions, may be viewed
from several different angles. The first alternative view is provided by the
following.

######  Proposition 4.2.

Let $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$ be a
${\mathcal{Q}}$-matrix. A pair $(X,Y)\in{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,1)\times{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(1,C)$ belongs to $\mathrm{Isb}(Z)$ if and only if it is
a maximal pair under-approximating $Z$, in the sense that (i) $Y\circ X\preceq
Z$, and (ii) if $(X^{\prime},Y^{\prime})\in{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,1)\times{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(1,C)$ satisfies $Y^{\prime}\circ X^{\prime}\preceq Z$,
$X\preceq X^{\prime}$ and $Y\preceq Y^{\prime}$, then $X=X^{\prime}$ and
$Y=Y^{\prime}$.

###### Proof.

Suppose $(X,Y)\in\mathrm{Isb}(Z)$. Given $(X^{\prime},Y^{\prime})$ with
$Y^{\prime}\circ X^{\prime}\preceq Z$, $X\preceq X^{\prime}$ implies
$Y^{\prime}\preceq Z\mathbin{\swarrow}X^{\prime}\preceq
Z\mathbin{\swarrow}X=Y$; similarly, $Y\preceq Y^{\prime}$ implies
$X^{\prime}\preceq X$.

Conversely, suppose that $(X,Y)$ satisfies conditions (i) and (ii). Then the
pair $(X,Z\mathbin{\swarrow}X)$ satisfies $(Z\mathbin{\swarrow}X)\circ
X\preceq Z$, $X\preceq X$ and, by (i), $Y\preceq Z\mathbin{\swarrow}X$. So by
(ii) we conclude $Y=Z\mathbin{\swarrow}X$. Similarly, using the pair
$(Y\mathbin{\searrow}Z,Y)$ we see that $X=Y\mathbin{\searrow}Z$. ∎

The Isbell hull of a matrix can be seen as an instance of the set of fixed
points of an adjunction. Suppose that

${\mathcal{L}}$${\mathcal{L^{\prime}}}$$f$$u$$\dashv$

is an adjunction between posets ${\mathcal{L}}=(L,\preceq)$ and
${\mathcal{L^{\prime}}}=(L^{\prime},\preceq^{\prime})$. By a fixed point of
the adjunction $f\dashv u$ we mean a pair $(l,l^{\prime})\in L\times
L^{\prime}$ such that $l^{\prime}=f(l)$ and $l=u(l^{\prime})$. The set of all
fixed points of $f\dashv u$ is denoted by $\mathrm{Fix}(f\dashv u)$. For any
matrix $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$, clearly
$\mathrm{Isb}(Z)$ is
$\mathrm{Fix}(Z\mathbin{\swarrow}(-)\dashv(-)\mathbin{\searrow}Z)$ for the
adjunction (8) with $B=1$.

We recall some well-known properties of $\mathrm{Fix}(f\dashv u)$. By
definition, given an element $(l,l^{\prime})\in\mathrm{Fix}(f\dashv u)$, each
of $l$ and $l^{\prime}$ is determined from the other. This means that both
projections $\pi_{1}\colon\mathrm{Fix}(f\dashv u)\longrightarrow L$ and
$\pi_{2}\colon\mathrm{Fix}(f\dashv u)\longrightarrow L^{\prime}$, mapping
$(l,l^{\prime})$ to $l$ and $l^{\prime}$ respectively, are injective. Given
elements $(l_{1},l^{\prime}_{1})$ and $(l_{2},l^{\prime}_{2})$ of
$\mathrm{Fix}(f\dashv u)$, we have $l_{1}\preceq l_{2}$ if and only if
$l^{\prime}_{1}\preceq^{\prime}l^{\prime}_{2}$, because the former is
equivalent to $l_{1}\preceq u(l^{\prime}_{2})$ and the latter to
$f(l_{1})\preceq^{\prime}l^{\prime}_{2}$. Hence we obtain a natural partial
order on $\mathrm{Fix}(f\dashv u)$ induced by either of the projections,
turning it into a poset $\mathcal{F}ix(f\dashv u)$. The projections $\pi_{1}$
and $\pi_{2}$ are monotone by definition and moreover they have adjoints:

${\mathcal{L}}$${\mathcal{L^{\prime}}}$$\mathcal{F}ix(f\dashv
u)$.$f$$u$$\pi_{1}$$g$$v$$\pi_{2}$$\dashv$$\dashv$$\dashv$

Here, the adjoints $g$ and $v$ are given by $g(l)=(uf(l),f(l))$ and
$v(l^{\prime})=(u(l^{\prime}),fu(l^{\prime}))$. Observe in particular that the
image of $\pi_{1}$ (which may be identified with $\mathrm{Fix}(f\dashv u)$ by
injectivity of $\pi_{1}$) coincides with the image of $u$. Infima and suprema
in $\mathcal{F}ix(f\dashv u)$ are easy to describe. Given a family
$((l_{i},l^{\prime}_{i}))_{i\in I}$ of elements of $\mathrm{Fix}(f\dashv u)$,
$\bigwedge_{i\in I}(l_{i},l^{\prime}_{i})\in\mathrm{Fix}(f\dashv u)$ exists if
and only if $\bigwedge_{i\in I}l_{i}\in L$ exists, and in this case we have
$\bigwedge_{i\in I}(l_{i},l^{\prime}_{i})=(\bigwedge_{i\in
I}l_{i},f(\bigwedge_{i\in I}l_{i}))$; similarly, $\bigvee_{i\in
I}(l_{i},l^{\prime}_{i})=(u(\bigvee_{i\in I}l^{\prime}_{i}),\bigvee_{i\in
I}l^{\prime}_{i})$ whenever either side of the equality exists. In particular,
$\mathcal{F}ix(f\dashv u)$ is a complete lattice whenever either
${\mathcal{L}}$ or ${\mathcal{L^{\prime}}}$ is.

######  Corollary 4.3.

Let $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$ be a matrix.

  1. (1)

The Isbell hull $\mathrm{Isb}(Z)$ of $Z$ admits a partial order $\preceq$
defined by $(X,Y)\preceq(X^{\prime},Y^{\prime})$ if and only if
$X\preceq_{A,1}X^{\prime}$, or equivalently if and only if
$Y^{\prime}\preceq_{1,C}Y$. The poset $(\mathrm{Isb}(Z),\preceq)$ is a
complete lattice.

  2. (2)

A row vector $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}}}1$ is in $\mathrm{Isb}(Z)$
(precisely: is in $\pi_{1}(\mathrm{Isb}(Z))$) if and only if there exists some
column vector $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}}}C$ such that
$X=Y\mathbin{\searrow}Z$.

  3. (3)

For any pair $(X^{\prime},Y^{\prime})\in{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,1)\times{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(1,C)$ under-approximating $Z$ (i.e., such that
$Y^{\prime}\circ X^{\prime}\preceq Z$), there exists $(X,Y)\in\mathrm{Isb}(Z)$
with $X^{\prime}\preceq X$ and $Y^{\prime}\preceq Y$.

###### Proof.

We show only the third clause. Given any
$X^{\prime}\in{{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(A,1)$, the pair
$((Z\mathbin{\swarrow}X^{\prime})\mathbin{\searrow}Z,Z\mathbin{\swarrow}X^{\prime})$
is in $\mathrm{Isb}(Z)$ and we have
$X^{\prime}\preceq(Z\mathbin{\swarrow}X^{\prime})\mathbin{\searrow}Z$. If
$Y^{\prime}\in{{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(1,C)$ satisfies
$Y^{\prime}\circ X^{\prime}\preceq Z$, then we also have $Y^{\prime}\preceq
Z\mathbin{\swarrow}X^{\prime}$. ∎

Let us see some examples of the Isbell hull construction. The case of tropical
polytope requires some preparation and will be treated in Section 5.

######  Example 4.4 ([Wil15]).

The set of all lower-semicontinuous convex functions of type
$\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$ may be understood as the
Isbell hull of the ${\overline{\mathbb{R}}_{\mathrm{min},+}}$-matrix
${\langle-,-\rangle}\colon\mathbb{R}^{n}\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}}}(\mathbb{R}^{n})^{\ast}$ in
Example 3.2. In light of that example, this is simply a restatement of the
classical theorem that a function
$f\colon\mathbb{R}^{n}\longrightarrow[-\infty,\infty]$ is lower-semicontinuous
convex if and only if $f=g^{\ast}$ for some
$g\colon(\mathbb{R}^{n})^{\ast}\longrightarrow[-\infty,\infty]$ (if and only
if $f=(f^{\ast})^{\ast}$).

######  Example 4.5.

The trivial-looking case of ${\mathcal{Q}}={\mathbf{2}}$ is in fact a rich
source of instances of naturally occurring Isbell hulls. In this case, a
matrix $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$ may be identified with a
relation $Z\subseteq C\times A$ consisting exactly of those pairs $(c,a)\in
C\times A$ with $Z_{c,a}=\top$. Similarly, a row vector $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}}}1$ and a column vector
$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}}}C$ are identified with
subsets $X\subseteq A$ and $Y\subseteq C$ respectively. Then we have an
adjunction

$\mathcal{P}A$$(\mathcal{P}C)^{\mathrm{op}},$$Z\mathbin{\swarrow}(-)$$(-)\mathbin{\searrow}Z$$\dashv$
(13)

given explicitly by

$Z\mathbin{\swarrow}X=\\{\,c\in C\mid\forall a\in X.\,(c,a)\in Z\,\\}$

and

$Y\mathbin{\searrow}Z=\\{\,a\in A\mid\forall c\in Y.\,(c,a)\in Z\,\\}.$

In fact, every adjunction between the powerset lattices $\mathcal{P}A$ and
$(\mathcal{P}C)^{\mathrm{op}}$ is of the form (13) for some relation
$Z\subseteq A\times C$. (One can reconstruct a relation from such an
adjunction by considering the images of singletons.)

Being a general form of adjunctions (Galois connections) between powerset
lattices, this includes many classical dualities; see e.g., [Wil15, Section
1.1.1]. This is also the framework of _formal concept analysis_ , in which one
is given the data consisting of a set $A$ of _attributes_ , a set $C$ of
_objects_ and a _satisfaction relation_ $Z$ specifying which object satisfies
which attribute, and aims to extract _concepts_ , which are nothing but
elements of $\mathrm{Isb}(Z)$. Pavlovic [Pav12] proposes an enriched
categorical generalisation of formal concept analysis via the _nucleus of a
profunctor_ , which is the same as the Isbell hull of a ${\mathcal{Q}}$-matrix
for a general quantale ${\mathcal{Q}}$.

Another classical instance of this construction is where $A=C$ and $Z$ is a
partial order on $A$. In this case, the poset $\mathcal{I}sb(Z)$ (which is a
complete lattice by Corollary 4.3) is known as the _MacNeille completion_ of
the poset $(A,Z)$.

######  Example 4.6.

Willerton [Wil13] observes that the directed tight span of a generalised
metric space [HK12, KKO12] is an instance of the Isbell hull construction with
${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$. A
generalised metric space $(A,d)$ consists of a set $A$ together with a
function $d\colon A\times A\longrightarrow[0,\infty]$ satisfying $d(a,a)=0$
and $d(a,a^{\prime})+d(a^{\prime}a^{\prime\prime})\geq d(a,a^{\prime\prime})$
(the triangle inequality) for each $a,a^{\prime},a^{\prime\prime}\in A$. Given
a generalised metric space $(A,d)$, its directed tight span is given by the
set of all pairs of functions $(X,Y)$ where $X,Y\colon
A\longrightarrow[0,\infty]$, such that $X$ and $Y$ form a minimal pair
satisfying $Y(a^{\prime})+X(a)\geq d(a,a^{\prime})$ for each $a,a^{\prime}\in
A$. In light of Proposition 4.2, this is clearly the Isbell hull of $d$
regarded as an ${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$-matrix
$d\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$.

The directed tight span of a generalised metric space has a natural
$l_{\infty}$-type metric on it, making it into a generalised metric space as
well. (Indeed, the directed tight span of $(A,d)$ is characterised as the
unique _injective_ and _tight extension_ of $(A,d)$.) As we shall see in
Example 6.3, the notion of generalised metric space coincides with an enriched
categorical notion of _${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$
-categories_. We can also recover the $l_{\infty}$ metric on the directed
tight span from the general theory, since as we shall see in Sections 5 and 6,
the Isbell hull of a ${\mathcal{Q}}$-matrix always acquires a natural
structure of a ${\mathcal{Q}}$-category.

##  5\. Complete semimodules

In this section we study the notion of complete semimodule over a quantale
${\mathcal{Q}}$. It will turn out that the Isbell hull of any
${\mathcal{Q}}$-matrix acquires such structure and conversely, any complete
semimodule is isomorphic to the Isbell hull of itself (regarded as a
${\mathcal{Q}}$-category; see Section 6).

######  Definition 5.1 ([CGQ04, Section 2.2]).

Let
${\mathcal{Q}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{{\mathcal{Q}}})$
be a quantale. A (left) complete semimodule over ${\mathcal{Q}}$ is a complete
lattice ${\mathcal{M}}=(M,\preceq_{{\mathcal{M}}})$ equipped with a left
action $\ast_{{\mathcal{M}}}\colon Q\times M\longrightarrow M$ of the monoid
$(Q,I_{\mathcal{Q}},\circ_{\mathcal{Q}})$ on the set $M$, such that
$\ast_{\mathcal{M}}$ preserves arbitrary suprema in each argument:
$(\bigvee_{i\in I}x_{i})\ast_{\mathcal{M}}m=\bigvee_{i\in
I}(x_{i}\ast_{\mathcal{M}}m)$ and $x\ast_{\mathcal{M}}(\bigvee_{i\in
I}m_{i})=\bigvee_{i\in I}(x\ast_{\mathcal{M}}m_{i})$.

A right complete semimodule over ${\mathcal{Q}}$ is a left complete semimodule
over the quantale
${\mathcal{Q}}^{\mathrm{rev}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ^{\mathrm{rev}}_{\mathcal{Q}})$,
where $x\circ^{\mathrm{rev}}_{\mathcal{Q}}y=y\circ_{\mathcal{Q}}x$.

Analogously to the case of quantale, there is an algebraic variant of the
above order-theoretic definition. In general, a _semimodule over a semiring
${\mathcal{Q}}$_ is a commutative monoid ${\mathcal{M}}$ equipped with an
action of ${\mathcal{Q}}$, which may be succinctly expressed as a semiring
homomorphism from ${\mathcal{Q}}$ to the semiring
$\mathrm{End}({\mathcal{M}})$ of all endomorphisms on ${\mathcal{M}}$. If
${\mathcal{Q}}$ is an idempotent semiring then the underlying commutative
monoid ${\mathcal{M}}$ of any semimodule over it is necessarily idempotent,
since the existence of a semiring homomorphism
${\mathcal{Q}}\longrightarrow\mathrm{End}({\mathcal{M}})$ forces
${\mathrm{id}_{{\mathcal{M}}}}\in\mathrm{End}({\mathcal{M}})$ to be idempotent
(with respect to addition). So a semimodule over an idempotent semiring can be
equivalently given as an (upper) semilattice with an appropriate action, and
Definition 5.1 may be viewed as a _complete_ version of it.

Applying Proposition 2.2, we obtain two residuation operations associated with
a complete semimodule
${\mathcal{M}}=(M,\preceq_{\mathcal{M}},\ast_{\mathcal{M}})$: for each $m\in
M$, the right adjoint $(-)\mathbin{\swarrow}_{\mathcal{M}}m\colon
M\longrightarrow Q$ of $(-)\ast_{\mathcal{M}}m\colon Q\longrightarrow M$, and
for each $x\in Q$, the right adjoint
$x\mathbin{\searrow}_{\mathcal{M}}(-)\colon M\longrightarrow M$ of
$x\ast_{\mathcal{M}}(-)\colon M\longrightarrow M$. We again have the
adjointness relation

$x\preceq_{\mathcal{Q}}n\mathbin{\swarrow}_{\mathcal{M}}m\iff
x\ast_{\mathcal{M}}m\preceq_{\mathcal{M}}n\iff
m\preceq_{\mathcal{M}}x\mathbin{\searrow}_{\mathcal{M}}n$ (14)

for each $x\in Q$ and $m,n\in M$. Adopting terminology from enriched category
theory, we call the function

$\ast_{\mathcal{M}}\colon{\mathcal{Q}}\times{\mathcal{M}}\longrightarrow{\mathcal{M}}$

the copower, the function

$\mathbin{\swarrow}_{{\mathcal{M}}}\colon{\mathcal{M}}\times{\mathcal{M}}^{\mathrm{op}}\longrightarrow{\mathcal{Q}}$

the hom-functor, and the function

$\mathbin{\searrow}_{{\mathcal{M}}}\colon{\mathcal{Q}}^{\mathrm{op}}\times{\mathcal{M}}\longrightarrow{\mathcal{M}}$

the power.

######  Proposition 5.2 (Cf. [CGQ04, Section 2.3] and [Stu05, Proposition
5.10]).

Let
${\mathcal{Q}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{\mathcal{Q}})$
be a quantale and ${\mathcal{M}}=(M,\preceq_{\mathcal{M}},\ast_{\mathcal{M}})$
be a left complete semimodule over ${\mathcal{Q}}$. Then the triple
${\mathcal{M}}^{\mathrm{op}}=(M,\succeq_{\mathcal{M}},\mathbin{\searrow}_{\mathcal{M}})$
is a right complete semimodule over ${\mathcal{Q}}$ (called the dual of
${\mathcal{M}}$). Moreover we have
$({\mathcal{M}}^{\mathrm{op}})^{\mathrm{op}}={\mathcal{M}}$.

###### Proof.

We need to show that $I_{\mathcal{Q}}\mathbin{\searrow}_{\mathcal{M}}m=m$,
$x\mathbin{\searrow}_{\mathcal{M}}(y\mathbin{\searrow}_{\mathcal{M}}m)=(y\circ_{\mathcal{Q}}x)\mathbin{\searrow}_{\mathcal{M}}m$,
$(\bigvee_{i\in I}x_{i})\ast_{{\mathcal{M}}}m=\bigwedge_{i\in
I}(x_{i}\ast_{\mathcal{M}}m)$ and $x\ast_{\mathcal{M}}(\bigwedge_{i\in
I}m_{i})=\bigwedge_{i\in I}(x\ast_{\mathcal{M}}m_{i})$, where $\bigwedge$
denotes infima in the original complete lattice $(M,\preceq_{{\mathcal{M}}})$.
They follow from the adjointness relation (14). ∎

######  Example 5.3.

Here are some immediate examples of (left or right) complete semimodules over
a quantale
${\mathcal{Q}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{\mathcal{Q}})$;
in the following, all complete semimodules are over ${\mathcal{Q}}$ unless
otherwise stated. First, clearly the underlying complete lattice
$(Q,\preceq_{\mathcal{Q}})$ of ${\mathcal{Q}}$ acquires a left complete
semimodule structure via $\circ_{\mathcal{Q}}$; we denote this left complete
semimodule also by ${\mathcal{Q}}$. The dual right complete semimodule
${\mathcal{Q}}^{\mathrm{op}}$ corresponding to it (Proposition 5.2) uses the
right lifting $\mathbin{\searrow}$ as action.

On the other hand, the complete lattice $(Q,\preceq_{{\mathcal{Q}}})$ also
underlies the quantale
${\mathcal{Q}}^{\mathrm{rev}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{\mathcal{Q}}^{\mathrm{rev}})$,
hence via $\circ_{\mathcal{Q}}^{\mathrm{rev}}$ it becomes a left complete
semimodule over ${\mathcal{Q}}^{\mathrm{rev}}$, i.e., a right complete
semimodule (over ${\mathcal{Q}}$). This right complete semimodule is denoted
by ${\mathcal{Q}}^{\mathrm{rev}}$. The dual left complete semimodule
${\mathcal{Q}}^{\mathrm{revop}}=({\mathcal{Q}}^{\mathrm{rev}})^{\mathrm{op}}$
uses the right extension $\mathbin{\swarrow}$ as action.

Because left or right complete semimodules are closed under arbitrary
products, for any pair of sets $A$ and $B$ we obtain a left complete
semimodule ${\mathcal{Q}}^{A}\times({\mathcal{Q}}^{\mathrm{revop}})^{B}$ and a
right complete semimodule
$({\mathcal{Q}}^{\mathrm{op}})^{A}\times({\mathcal{Q}}^{\mathrm{rev}})^{B}$,
which are easily seen to be the dual of each other.

The symmetry of the notions of left and right complete semimodule may leave
one wonder whether it is possible to give the data of a complete semimodule in
an unbiased manner, choosing neither the left action (copower) nor the right
action (power) as a primitive. This is indeed possible, by means of the hom-
functor. The resulting notion is _skeletal and complete
${\mathcal{Q}}$-category_; see Section 6.

######  Definition 5.4.

Let ${\mathcal{Q}}$ be a quantale and
${\mathcal{M}}=(M,\preceq_{{\mathcal{M}}},\ast_{{\mathcal{M}}})$ be a left
complete semimodule over ${\mathcal{Q}}$. A left complete subsemimodule of
${\mathcal{M}}$ is a subset of $M$ closed under arbitrary suprema in
${\mathcal{M}}$ and the copower $x\ast_{\mathcal{M}}(-)$ by an arbitrary
element $x\in Q$. A right complete subsemimodule of ${\mathcal{M}}$ is a
subset of $M$ closed under arbitrary infima in ${\mathcal{M}}$ and the power
$x\mathbin{\searrow}_{\mathcal{M}}(-)$ by an arbitrary element $x\in Q$.

We regard a left (resp. right) complete subsemimodule itself as a left (resp.
right) complete semimodule, by the induced order and operation.

Of course, a right complete subsemimodule of ${\mathcal{M}}$ is nothing but a
left complete subsemimodule of the left complete semimodule
${\mathcal{M}}^{\mathrm{op}}$ over ${\mathcal{Q}}^{\mathrm{rev}}$.

The set of all left complete subsemimodules of a fixed left complete
semimodule ${\mathcal{M}}=(M,\preceq_{\mathcal{M}},\ast_{\mathcal{M}})$ is
closed under arbitrary intersections. Hence for any subset $S\subseteq M$
there exists the least left complete subsemimodule containing $S$, the left
complete subsemimodule generated by $S$. Similarly we have the right complete
subsemimodule generated by $S$.

######  Proposition 5.5 ([BK12, Theorem 3.1], cf. [Ell17, Theorem 3.3.9] ).

Let $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$ be a matrix. The Isbell
hull $\mathrm{Isb}(Z)$, considered as a subset of ${{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,1)$, is the right complete subsemimodule generated by
the set $\\{\,Z_{c,-}\mid c\in C\,\\}\subseteq{{{\mathcal{Q}}}\mathchar
45\relax\mathbf{Mat}}(A,1)$ of all row vectors of $Z$, where
${{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(A,1)$ is regarded as the left
complete semimodule ${\mathcal{Q}}^{A}$. Dually, $\mathrm{Isb}(Z)$ considered
as a subset of ${{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(1,C)$ is the
left complete subsemimodule generated by $\\{\,Z_{-,a}\mid a\in
A\,\\}\subseteq{{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(1,C)$, where
${{{\mathcal{Q}}}\mathchar 45\relax\mathbf{Mat}}(1,C)$ is regarded as the left
complete semimodule $({\mathcal{Q}}^{\mathrm{revop}})^{C}$.

###### Proof.

Let us prove that $\mathrm{Isb}(Z)\subseteq{\mathcal{Q}}^{A}$ is the right
complete subsemimodule generated by $\\{\,Z_{c,-}\mid c\in C\,\\}$. Recall the
second clause of Corollary 4.3, claiming that $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}}}1$ is in $\mathrm{Isb}(Z)$
if and only if it is of the form $X=Y\mathbin{\searrow}Z$ for some $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}}}C$. The key observation is
that the equation $X=Y\mathbin{\searrow}Z$ may be regarded as an expression of
$X$ by a “tropical linear combination (in
$({\mathcal{Q}}^{\mathrm{op}})^{A}$)” of the row vectors $Z_{c,-}$. More
precisely, we read from the formula (11) for right lifting that we have

$X=Y\mathbin{\searrow}Z=\bigwedge_{c\in
C}(Y_{c,\ast}\mathbin{\searrow}Z_{c,-}).$ (15)

Observe that the column vector $Y$ plays the role of “coefficients” of the
above tropical linear combination. Any row vector $X$ as in (15), expressible
as the infimum of powers of $Z_{c,-}$, must lie in any right complete
subsemimodule containing the row vectors $Z_{c,-}$. Also we see that for any
$c\in C$, the row vector $Z_{c,-}$ itself may be expressed as a trivial linear
combination, upon taking $Y$ to be

$Y_{c^{\prime},\ast}=\begin{cases}I_{Q}&\text{if }c=c^{\prime},\\\
\mathbf{0}_{\mathcal{Q}}&\text{otherwise.}\end{cases}$

That the set $\mathrm{Isb}(Z)$ of all row vectors expressible as (15) is
closed under infima and the power $x\mathbin{\searrow}(-)$ by an element $x$
of ${\mathcal{Q}}$ may be checked easily. Precisely, given a family
$X_{i}=Y_{i}\mathbin{\searrow}Z$, we may take new coefficient $\bigvee_{i\in
I}Y_{i}$ to express their infimum: $\bigwedge_{i\in I}X_{i}=(\bigvee_{i\in
I}Y_{i})\mathbin{\searrow}Z$. Given $X=Y\mathbin{\searrow}Z$, we have
$x\mathbin{\searrow}X=(Y\circ x)\mathbin{\searrow}Z$. ∎

As a consequence of this proposition, the Isbell hull of any
${\mathcal{Q}}$-matrix acquires the structure of a left complete
${\mathcal{Q}}$-semimodule.

######  Example 5.6.

By using Proposition 5.5, we can see how tropical polytopes [DS04] are (modulo
some points at infinity) instances of the Isbell hull construction. Let $m$
and $n$ be natural numbers. In [DS04], the tropical polytope generated by $m$
points $Z_{1},\dots,Z_{m}\in\mathbb{R}^{n}$ is defined as the set of all
points $X\in\mathbb{R}^{n}$ which can be expressed as a tropical linear
combination

$X=(Y_{1}\odot Z_{1})\oplus\dots\oplus(Y_{m}\odot Z_{m}),$ (16)

where $Y_{i}\in\mathbb{R}$ and $\oplus$ and $\odot$ denote the coordinate-wise
minimum and the addition ($c\odot(a_{1},\dots,a_{n})=(c+a_{1},\dots,c+a_{n})$)
respectively.111Strictly speaking, Develin and Sturmfels consider an
additional step of projectivisation in the definition, hence our tropical
polytopes are the unprojectivised version of theirs. As observed in [Ell17],
this is the finite part of the Isbell hull of the
${\overline{\mathbb{R}}_{\mathrm{max},+}}$-matrix $Z\colon
n\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}}}m$ (where $n$ (resp. $m$)
denotes an $n$-element (resp. $m$-element) set) obtained from the coordinates
of the points $Z_{1},\dots,Z_{m}$. Indeed, any expression of the form (16) may
be expressed as $X=Y\mathbin{\searrow}Z$ for some
${\overline{\mathbb{R}}_{\mathrm{max},+}}$-matrix $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}}}m$ with finite (i.e.,
$\neq\pm\infty$) entries and vice versa.

In [DS04] the following interesting duality result has been established: there
is a bijective correspondence between (the combinatorial types of) _tropical
polytopes in $\mathbb{R}^{n}$ generated by $m$ points_ and _tropical polytopes
in $\mathbb{R}^{m}$ generated by $n$ points_. From our point of view, this
result can be understood abstractly from the fact that for an
${\overline{\mathbb{R}}_{\mathrm{max},+}}$-matrix $Z$, $\mathrm{Isb}(Z)$ and
$\mathrm{Isb}(Z^{\top})$ are canonically isomorphic; this follows from the
commutativity of the quantale ${\overline{\mathbb{R}}_{\mathrm{max},+}}$.

##  6\. ${\mathcal{Q}}$-categories

In this section, we introduce ${\mathcal{Q}}$-categories for a quantale
${\mathcal{Q}}$. They are instances of the well-studied notion of enriched
category [Kel82].

######  Definition 6.1.

Let
${\mathcal{Q}}=(Q,\preceq_{\mathcal{Q}},I_{\mathcal{Q}},\circ_{\mathcal{Q}})$
be a quantale. 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}})}$.

Note that a ${\mathcal{Q}}$-category ${\mathcal{C}}$ can be identified with 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}})}$
with ${\mathcal{C}}_{c^{\prime},c}={\mathcal{C}}(c,c^{\prime})$. In fact, a
${\mathcal{Q}}$-category may be defined more succinctly as a set $A$
(corresponding to (CD1)) together with a ${\mathcal{Q}}$-matrix $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}}}A$ (CD2) on it such that
$I_{A}\preceq_{A,A}X$ (CA1) and $X\circ X\preceq_{A,A}X$ (CA2) hold [BCSW83].

######  Example 6.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$). The 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 6.3.

In the case ${\mathcal{Q}}={\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$,
we may regard ${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$-categories
as _generalised metric spaces_ [Law73] (cf. Example 4.6); objects of an
${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min},+}}$-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}_{\mathrm{min},+}}$-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).

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

  * •

distance may attain $\infty$;

  * •

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

  * •

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

######  Example 6.4.

Similarly, ${\overline{\mathbb{R}}^{\geq 0}_{\mathrm{min,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})$.

As we have already mentioned, every left complete semimodule over
${\mathcal{Q}}$ gives rise to a ${\mathcal{Q}}$-category. The precise
construction is as follows.

######  Definition 6.5.

Let ${\mathcal{M}}=(M,\preceq_{\mathcal{M}},\ast_{{\mathcal{M}}})$ be a left
complete semimodule over ${\mathcal{Q}}$. The following data defines a
${\mathcal{Q}}$-category, again called ${\mathcal{M}}$:

(CD1):

the set of objects is ${\mathrm{ob}({\mathcal{M}})}=M$; and

(CD2):

for each $m,m^{\prime}\in M$, the element ${\mathcal{M}}(m,m^{\prime})\in Q$
is defined as $m^{\prime}\mathbin{\swarrow}_{\mathcal{M}}m$ (note the order of
the arguments $m$ and $m^{\prime}$).

The axioms can be checked easily by means of the adjointness relations (14).

The structure of a left complete semimodule ${\mathcal{M}}$, namely the order
relation $\preceq_{\mathcal{M}}$ and the action $\ast_{\mathcal{M}}$, can be
recovered from the induced ${\mathcal{Q}}$-category
${\mathcal{M}}=(M,({\mathcal{M}}(m,m^{\prime}))_{m,m^{\prime}\in M})$. To see
this, first note that any ${\mathcal{Q}}$-category
${\mathcal{C}}=({\mathrm{ob}({\mathcal{C}})},({\mathcal{C}}(c,c^{\prime}))_{c,c^{\prime}\in{\mathrm{ob}({\mathcal{C}})}})$
determines a preorder relation $\preceq_{{\mathcal{C}}}$ on
${\mathrm{ob}({\mathcal{C}})}$ by

$c\preceq_{{\mathcal{C}}}c^{\prime}\ \text{ if and only if }\
I_{\mathcal{Q}}\preceq_{\mathcal{Q}}{\mathcal{C}}(c,c^{\prime}).$ (17)

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, namely 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 a
${\mathcal{Q}}$-category ${\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 antisymmetric and
is a partial order relation. Now, if a ${\mathcal{Q}}$-category
${\mathcal{M}}$ is derived from a left complete semimodule ${\mathcal{M}}$ by
the construction of Definition 6.5, then we actually recover the original
order relation on the complete semimodule by (17) (see (14)). The action
$\ast_{\mathcal{M}}$ is then uniquely determined from the hom-functor
${\mathcal{M}}(-,-)$ via the adjunction
$(-)\ast_{\mathcal{M}}m\dashv{\mathcal{M}}(m,-)$.

In fact, it is also possible to define the counterpart of $\ast_{\mathcal{M}}$
for general ${\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 copower of $c$ by $x$ if
for any $d\in{\mathcal{C}}$, the equation

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

holds [Kel82, Section 3.7]. Copowers 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 copower of $c$ by $x$, then an object
$c^{\prime\prime}\in{\mathcal{C}}$ is also a copower of $x$ and $c$ if and
only if $c^{\prime}$ and $c^{\prime\prime}$ are isomorphic. In particular, in
a sketetal ${\mathcal{Q}}$-category copowers are unique.

There is also a dual notion of power 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}}(d,c^{\prime})=x\mathbin{\searrow}{\mathcal{C}}(d,c)$

holds.

######  Definition 6.6 ([Stu06, Section 2]).

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

  * •

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

  * •

powered if for any $x\in Q$ and $c\in{\mathcal{C}}$, a power of $c$ by $x$
exists in ${\mathcal{C}}$;

  * •

order-complete if the preordered set
$({\mathrm{ob}({\mathcal{C}})},\preceq_{\mathcal{C}})$ is complete (i.e., if
it admits suprema of arbitrary subsets);

  * •

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

In fact, the construction in Definition 6.5 provides a one-to-one
correspondence between _left complete semimodules over ${\mathcal{Q}}$_ on the
one hand, and _skeletal and complete ${\mathcal{Q}}$-categories_ on the other
[Stu06, Section 4]. See also [Wil13, Section 5].

Recall that a ${\mathcal{Q}}$-category ${\mathcal{C}}$ may be identified with
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}})}$.
We can then consider its Isbell hull $\mathrm{Isb}({\mathcal{C}})$; by
Proposition 5.5, it is a complete semimodule over ${\mathcal{Q}}$, hence by
and Definition 6.5 we may view $\mathrm{Isb}({\mathcal{C}})$ as a (skeletal
and complete) ${\mathcal{Q}}$-category. A more explicit description of
$\mathrm{Isb}({\mathcal{C}})$ as a ${\mathcal{Q}}$-category is the following.

######  Definition 6.7.

Let ${\mathcal{C}}$ be a ${\mathcal{Q}}$-category. The
${\mathcal{Q}}$-category $\mathrm{Isb}({\mathcal{C}})$ is defined as follows:

(CA1):

its set of objects is $\mathrm{Isb}({\mathcal{C}})$ as in Definition 4.1;

(CA2):

given $(X,Y)$ and $(X^{\prime},Y^{\prime})$ in $\mathrm{Isb}({\mathcal{C}})$,
the element $\mathrm{Isb}({\mathcal{C}})((X,Y),(X^{\prime},Y^{\prime}))\in Q$
is defined as

$\bigwedge_{c\in{\mathcal{C}}}X^{\prime}_{\ast,c}\mathbin{\searrow}X_{\ast,c},$

or equivalently as

$\bigwedge_{c\in{\mathcal{C}}}Y^{\prime}_{c,\ast}\mathbin{\swarrow}Y_{c,\ast}.$

The ${\mathcal{Q}}$-category $\mathrm{Isb}({\mathcal{C}})$ is called the
MacNeille completion of ${\mathcal{C}}$ ([Gar14, Definition 7.2], [She14,
Definition 5.5.2]).

In fact, it is known that for any skeletal and complete ${\mathcal{C}}$,
$\mathrm{Isb}({\mathcal{C}})$ is canonically isomorphic to ${\mathcal{C}}$
(see [She14, Proposition 5.5.5] or [Gar14, Proposition 7.6]). It follows that
any skeletal and complete ${\mathcal{Q}}$-category, or equivalently any left
complete semimodule over ${\mathcal{Q}}$, can be realised the Isbell hull
$\mathrm{Isb}(Z)$ of a certain ${\mathcal{Q}}$-matrix $Z$.

## References

  * [BCSW83] Renato Betti, Aurelio Carboni, Ross Street, and Robert Walters.  Variation through enrichment.  Journal of Pure and Applied Algebra, 29(2):109–127, 1983.
  * [BK12] Radim Belohlavek and Jan Konecny.  Row and column spaces of matrices over residuated lattices.  Fundamenta Informaticae, 115(4):279–295, 2012.
  * [CG91] R. A. Cuninghame-Green.  Minimax algebra and applications.  Fuzzy Sets and Systems, 41(3):251–267, 1991.
  * [CGQ04] 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.
  * [DP02] Brian A. Davey and Hilary A. Priestley.  Introduction to lattices and order.  Cambridge university press, second edition, 2002.
  * [DS04] Mike Develin and Bernd Sturmfels.  Tropical convexity.  Documenta Mathematica, 9:1–27, 2004.
  * [Ell17] Jonathan Elliott.  On the fuzzy concept complex.  PhD thesis, University of Sheffield, 2017.
  * [Fuj14] Soichiro Fujii.  A categorical approach to L-convexity, 2014.  Bachelor’s thesis, The University of Tokyo, arXiv:1904.08413.
  * [Gar14] Richard Garner.  Topological functors as total categories.  Theory and Applications of Categories, 29(15):406–421, 2014.
  * [HK12] Hiroshi Hirai and Shungo Koichi.  On tight spans for directed distances.  Annals of Combinatorics, 16(3):543–569, 2012.
  * [Kel82] 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.
  * [KKO12] 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.
  * [Law73] 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.
  * [Law84] F. William Lawvere.  State categories, closed categories, and the existence of semi-continuous entropy functions.  IMA Preprint Series, 86, 1984.
  * [LMS01] Grigory L. Litvinov, Victor P. Maslov, and Grigory B. Shpiz.  Idempotent functional analysis: an algebraic approach.  Mathematical Notes, 69(5-6):696–729, 2001.
  * [ML98] Saunders Mac Lane.  Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics.  Springer, second edition, 1998.
  * [Mul86] Christopher J. Mulvey.  &.  Supplemento ai Rendiconti del Circolo Matemàtico di Palermo. Serie II, 12:99–104, 1986.
  * [Mur03] Kazuo Murota.  Discrete convex analysis.  SIAM, 2003.
  * [Pav12] Dusko Pavlovic.  Quantitative concept analysis.  In International Conference on Formal Concept Analysis, pages 260–277. Springer, 2012.
  * [Pin98] Jean-Eric Pin.  Tropical semirings.  In Idempotency, pages 50–69, 1998.
  * [Roc70] R. Tyrrell Rockafellar.  Convex Analysis, volume 28 of Princeton Landmarks in Mathematics and Physics.  Princeton University Press, 1970.
  * [Ros95] Kimmo I. Rosenthal.  Quantaloids, enriched categories and automata theory.  Applied Categorical Structures, 3(3):279–301, 1995.
  * [She14] Lili Shen.  Adjunctions in Quantaloid-enriched Categories.  PhD thesis, Sichuan University, 2014.
  * [Sim94] Imre Simon.  On semigroups of matrices over the tropical semiring.  Theoretical Informatics and Applications, 28(3–4):277–294, 1994\.
  * [Str12] Ross Street.  The core of adjoint functors.  Theory and Applications of Categories, 27(4):47–64, 2012.
  * [Stu05] Isar Stubbe.  Categorical structures enriched in a quantaloid: categories, distributors and functors.  Theory and Applications of Categories, 14(1):1–45, 2005.
  * [Stu06] Isar Stubbe.  Categorical structures enriched in a quantaloid: tensored and cotensored categories.  Theory and Applications of Categories, 16(14):283–306, 2006.
  * [SZ13] 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.
  * [Vir01] Oleg Viro.  Dequantization of real algebraic geometry on logarithmic paper.  In European Congress of Mathematics, pages 135–146. Springer, 2001\.
  * [Wil13] Simon Willerton.  Tight spans, Isbell completions and semi-tropical modules.  Theory and Applications of Categories, 28(22):696–732, 2013.
  * [Wil15] Simon Willerton.  The Legendre-Fenchel transform from a category theoretic perspective, 2015.