A Categorical Approach to L-Convexity

Soichiro Fujii

Bachelor’s Thesis
February, 2014
Mathematical Information Engineering Course
Department of Mathematical Engineering and Information Physics
Faculty of Engineering, The University of Tokyo

## Abstract

We investigate an enriched-categorical approach to a field of discrete
mathematics. The main result is a duality theorem between a class of enriched
categories (called $\overline{\mathbb{Z}}$\- or
$\overline{\mathbb{R}}$-categories) and that of what we call
($\overline{\mathbb{Z}}$\- or $\overline{\mathbb{R}}$-) extended L-convex
sets. We introduce extended L-convex sets as variants of certain discrete
structures called L-convex sets and L-convex polyhedra, studied in the field
of discrete convex analysis. We also introduce homomorphisms between extended
L-convex sets. The theorem claims that there is a one to one correspondence
(up to isomorphism) between two classes. The thesis also contains an
introductory chapter on enriched categories and no categorical knowledge is
assumed.

###### Contents

  1. 1 Introduction
    1. 1.1 Background and Our Results
    2. 1.2 Chapter Overview
  2. 2 Poset-Enriched Category Theory
    1. 2.1 Enriching Posets
    2. 2.2 Enriched Categories
    3. 2.3 Enriched Functors and Canonical Orderings
    4. 2.4 The Opposites of $\mathcal{V}$-Categories
    5. 2.5 $\mathcal{V}$ as a $\mathcal{V}$-Category
    6. 2.6 Functor Categories and the Yoneda Embedding
  3. 3 $\overline{\mathbb{K}}$-Categories and $\overline{\mathbb{K}}$-Extended L-Convex Sets
    1. 3.1 $\overline{\mathbb{K}}$-Extended L-Convex Sets
    2. 3.2 Homomorphisms of $\overline{\mathbb{K}}$-Extended L-Convex Sets
    3. 3.3 Duality Theorems
  4. 4 Conclusion
    1. 4.1 Summary and Concluding Remarks
    2. 4.2 Further Work
  5. 5 Acknowledgments

## Notation

### Proof Trees

Throughout the thesis, we use a proof-tree-like notation as a visually
intuitive way of reasoning. The tree

$\mathord{P(x,y,\dots)}\mathord{}$ $\mathord{Q(x,y,\dots)}\mathord{}$

where $P$ and $Q$ are formulas possibly with some free variables
($x,y,\dots$), represents the assertion

$P(x,y,\dots)\iff Q(x,y,\dots)$

for all possible values of $x,y,\dots$ in some appropriate domains.

For example, the supremum of a subset $S$ of a complete lattice
$(L,\sqsubseteq)$ is the unique element $a\in L$ with the following property:

$\mathord{s}\ \sqsubseteq\ \mathord{}$$x\quad(\forall s\in S)$ $\mathord{a}\
\sqsubseteq\ \mathord{}$$x$

which is to be read as

$x\text{ is an upper bound of }S\iff a\sqsubseteq x$

for all $x\in L$, or equivalently “$a$ is the least element among upper bounds
of $S$.”

Higher trees also appear:

$\mathord{P(x,y,\dots)}\mathord{}$ $\mathord{Q(x,y,\dots)}\mathord{}$
$\mathord{R(x,y,\dots)}\mathord{}$

Note that any two formulas, especially the top and the bottom ones, are
equivalent in a higher tree as well.

###  $\lambda$-Notation

In order to define maps succinctly without giving a name, we exploit the
$\lambda$-notation borrowed from (typed) lambda calculi. An example of
definitions of maps via the $\lambda$-notation is the following:

$\lambda x\in\mathbb{R}.\,x^{2}+2x.$

This expression denotes a function which takes an element $x$ of $\mathbb{R}$
and returns the value $x^{2}+2x$. Therefore if we pass an argument, say, 3, we
have:

$(\lambda x\in\mathbb{R}.\,x^{2}+2x)(3)=3^{2}+2\cdot 3=15.$

### Conventions

To highlight definitions, terms being defined (either explicitly or
implicitly) are written in the boldface font; the italic font is not used for
this purpose, and is reserved for emphases.

The ends of definitions and examples are marked by $\blacksquare$, and the
ends of proofs by ∎.

##  Chapter 1 Introduction

###  1.1 Background and Our Results

The study presented in this thesis is first motivated and inspired by a recent
paper by Simon Willerton [10]. In this paper, he recognizes that a
construction called directed tight span, introduced independently by [1] and
[4], is an instance of a more general construction known as the Isbell
completion. In fact, the directed tight span is a result within the theory of
metric spaces, whereas the Isbell completion belongs to a discipline called
enriched category theory. Why such a link could exist? This is due to an
influential 1973 paper [5] of William Lawvere; he remarks that, among others,
enriched categories specialize to metric spaces.

Let us be more precise. Enriched categories are abstract entities that
generalize (ordinary) categories studied in category theory. A general
definition of an enriched category involves a parameter $\mathcal{V}$ called
the enriching category, itself a category (with some additional structures).
Therefore, if we restrict our attention to those enriched categories with a
specific enriching category, we obtain a theory to which the theory of
enriched categories specializes. For example, if we let
$\mathcal{V}=\textbf{Set}$, where Set is the category of sets and maps, then
it turns out that enriched categories with the enriching category Set (called
Set-categories) are nothing but categories; thus enriched category theory
specializes to category theory. What Lawvere observed is, if we set
$\mathcal{V}=\overline{\mathbb{R}}_{+}$, a poset of nonnegative real numbers
together with an additional element $\infty$ (for those not familiar with
categories: posets are a special kind of categories), then
$\overline{\mathbb{R}}_{+}$-categories are a little generalized metric spaces
(in a precise statement, every metric space is an
$\overline{\mathbb{R}}_{+}$-category). Therefore he established a link between
the theory of enriched categories and that of metric spaces. Now it is amazing
that many notions of metric spaces, e.g., that of nonexpansive maps, sup-
distances on function spaces, the Fréchet embeddings of metric spaces, and
directed tight spans, already appear quite canonically in enriched category
theory.

The main objective of this thesis is to present an enriched-categorical
approach to another seemingly unrelated field: discrete convex analysis. The
theory of discrete convex analysis (see [8] for details) can be seen as a
discrete (or $\mathbb{Z}$) version of convex analysis (based on $\mathbb{R}$),
transporting various notions of convex analysis to a discrete setting. The
notion of convex sets ($\subseteq\mathbb{R}^{n}$), for example, thus has its
discrete counterparts, notably that of L-convex sets (named after lattices)
and M-convex sets (after matroids), which are certain subsets of
$\mathbb{Z}^{n}$. Our main result concerns L-convex sets; rather, their
variant what we call $\overline{\mathbb{Z}}$-extended L-convex sets. By
$\overline{\mathbb{Z}}$ we mean (among several other things) a poset of
integers together with two additional elements $-\infty$ and $\infty$. We
introduce $\overline{\mathbb{Z}}$-extended L-convex sets roughly as certain
subsets of $\overline{\mathbb{Z}}^{n}$, or more generally, subsets of
$\overline{\mathbb{Z}}^{V}$ where $V$ is some (possibly infinite) set. The
axioms we impose for $\overline{\mathbb{Z}}$-extended L-convex sets are
similar (but definitely not equal) to that for L-convex sets, so we regard
$\overline{\mathbb{Z}}$-extended L-convex sets as analogs of L-convex sets. On
the other hand, the poset $\overline{\mathbb{Z}}$ has a natural structure to
be an enriching category, and we can consider
$\overline{\mathbb{Z}}$-categories and the theory of them. Recall the
observation of Lawvere that $\overline{\mathbb{R}}_{+}$-categories are like
metric spaces. Because the structures of $\overline{\mathbb{R}}_{+}$ and
$\overline{\mathbb{Z}}$ are similar, one can say that
$\overline{\mathbb{Z}}$-categories are like metric spaces as well, although
the analogy is even weaker.

Our main result is a correspondence (or duality) between
$\overline{\mathbb{Z}}$-categories and $\overline{\mathbb{Z}}$-extended
L-convex sets. The correspondence is established at three levels: first for
individual objects, second for maps between objects, and finally for what we
call canonical orderings (usually called natural transformations) between
maps. At the first level, we present a construction that makes a
$\overline{\mathbb{Z}}$-extended L-convex set out of a
$\overline{\mathbb{Z}}$-category, and another one that performs the reverse.
These two constructions are inverses in the sense that if we start from a
$\overline{\mathbb{Z}}$-category and apply the first construction to get a
$\overline{\mathbb{Z}}$-extended L-convex set, and then apply the second to
obtain another $\overline{\mathbb{Z}}$-category, then the resulting one is
isomorphic to the $\overline{\mathbb{Z}}$-category we started from; and
likewise if we start from a $\overline{\mathbb{Z}}$-extended L-convex set.
Such a result is in fact already established for L-convex sets and distance
functions satisfying the triangle inequality, with essentially the same
technical contents; see [8, Section 5.3]. However, our result is new in its
formulation of the constructions. It turns out that the set
$\mathbb{Z}\cup\\{-\infty,\infty\\}$, which is the underlying set of the poset
$\overline{\mathbb{Z}}$, can naturally be seen both as a
$\overline{\mathbb{Z}}$-category and as a $\overline{\mathbb{Z}}$-extended
L-convex set; in either case we denote the resulting entity by
$\overline{\mathbb{Z}}$. Our constructions explicitly involve the function
space constructions with codomain $\overline{\mathbb{Z}}$ (either as a
$\overline{\mathbb{Z}}$-category or as a $\overline{\mathbb{Z}}$-extended
L-convex set) as key steps. Therefore in our formulation, maps play a crucial
role. Let us discuss them next; the discussion also leads to the second level
of the correspondence.

In enriched category theory, there is an established notion of maps between
enriched (say, $\mathcal{V}$-) categories, called $\mathcal{V}$-functors. Thus
we adopt $\overline{\mathbb{Z}}$-functors as the members of the class of maps
between $\overline{\mathbb{Z}}$-categories we consider, which are basically
nonexpansive (distance-nonincreasing) maps. For
$\overline{\mathbb{Z}}$-extended L-convex sets, we adopt what we call
homomorphisms between them as natural maps. The introduction of the notion of
homomorphisms is among the contribution of the thesis. Its definition is
closely tied to our definition of $\overline{\mathbb{Z}}$-extended L-convex
sets and seems to be natural. The duality at the second level states that
there is a bijection between the set of $\overline{\mathbb{Z}}$-functors with
specified domain and codomain $\overline{\mathbb{Z}}$-categories and that of
homomorphisms with the corresponding domain and codomain
$\overline{\mathbb{Z}}$-extended L-convex sets, where the correspondence is
that built in the first level. However, one noteworthy point is that the
directions of maps reverse; that is, what corresponds to the domain
$\overline{\mathbb{Z}}$-extended L-convex set is the codomain
$\overline{\mathbb{Z}}$-category, and the codomain
$\overline{\mathbb{Z}}$-extended L-convex set the domain
$\overline{\mathbb{Z}}$-category. This is the reason why we call the whole
correspondence a duality as well.

The canonical orderings are certain preorder relations on the sets of
$\overline{\mathbb{Z}}$-functors or homomorphisms with specified domain and
codomain. They are specialization of $\mathcal{V}$-natural transformations
between $\mathcal{V}$-functors in enriched category theory (one can interpret
homomorphisms as a special kind of $\overline{\mathbb{Z}}$-functors). We show
that, as a third level of the duality, the correspondence of maps at the
second level respects the canonical orderings.

In fact, there is no difficulty to develop an entirely parallel story by
replacing $\mathbb{Z}$ by $\mathbb{R}$; in this case, what correspond to our
$\overline{\mathbb{R}}$-extended L-convex sets turn out to be L-convex
polyhedra, which are also studied in discrete convex analysis. Therefore in
the later chapters of the thesis, we use the symbol $\mathbb{K}$ to denote
either $\mathbb{Z}$ or $\mathbb{R}$ and discuss
$\overline{\mathbb{K}}$-categories and $\overline{\mathbb{K}}$-extended
L-convex sets, treating both cases simultaneously.

###  1.2 Chapter Overview

In Chapter 2, we develop the theory of enriched categories, in a simplified
form. Although the general theory of enriched categories normally requires
acquaintance with basic (ordinary) category theory (as presented in [7]), we
avoid those points where such knowledge is compulsory by restricting our
interest to the cases where enriching categories are posets. Therefore, the
exposition is intended to be so introductory as to be readable without any
previous categorical experience. One remarkable point of (enriched) category
theory is that many general abstract notions specialize to ones which are
well-known inside some particular branch of mathematics. We hope that, with
preordered sets and (somewhat generalized variants of) metric spaces as
running examples, the chapter serves to convey the reader this fascinating
aspect of categories.

Chapter 3 contains our main contribution. First we introduce the notions of
$\overline{\mathbb{K}}$-extended L-convex sets and homomorphisms between them.
To indicate the underlying categorical viewpoints (in this case, not in the
level of (enriched) $\overline{\mathbb{K}}$-categories, but in that of the
(ordinary, or 2-) category of $\overline{\mathbb{K}}$-categories or the
category of $\overline{\mathbb{K}}$-extended L-convex sets), we occasionally
use the terminology of category theory without giving definitions. However,
all statements are translated into elementary terms and therefore the reader
can entirely skip these parts. We present the duality theorem, first for
individual objects, next for maps between them, and finally for canonical
orderings between maps.

Finally, in Chapter 4 we summarize the results of the thesis and briefly
indicate ways to future research.

##  Chapter 2 Poset-Enriched Category Theory

In this chapter, we develop the theory of enriched categories, under a crucial
assumption that the enriching category is actually a poset. This assumption
entirely removes the burden of checking the commutativity of (usually large)
diagrams in the enriching category, simply because every diagram in a poset
commutes. Since all enriching categories we will encounter in this thesis are
posets, such a simplified theory suffices. The organization of the chapter
roughly follows that of [3], which we also recommend as a text on general
enriched category theory.

###  2.1 Enriching Posets

As one needs the notion of fields to define vector spaces, in order to define
enriched categories, we need the notion of enriching categories, often denoted
by the symbol $\mathcal{V}$. The fertility of the resulting theory of enriched
categories over a particular enriching category $\mathcal{V}$ depends on how
nice $\mathcal{V}$ is, and it turns out that in order to gain a fully fruitful
theory, $\mathcal{V}$ should be a bicomplete symmetric monoidal closed
category. As promised above, we treat only the cases where $\mathcal{V}$ is a
poset; when this is the case, the definition of bicomplete symmetric monoidal
closed categories, rather, bicomplete symmetric monoidal closed posets =
symmetric monoidal closed complete lattices, is given successively as follows:

######  Definition 2.1.

A symmetric monoidal poset (SM-P) $\mathcal{V}$ is a triple
$(\mathcal{V}_{0},\otimes,e)$ where

  * •

$\mathcal{V}_{0}=(\mathcal{V}_{0},\sqsubseteq)$ is a poset called the
underlying poset;

  * •

$\otimes\colon\mathcal{V}_{0}\times\mathcal{V}_{0}\longrightarrow\mathcal{V}_{0}$
is a binary operation on $\mathcal{V}_{0}$ called the tensor product;

  * •

$e$ is an element of $\mathcal{V}_{0}$ called the unit element;

such that the following axioms hold:

(Monotonicity of $\otimes$)

$x\sqsubseteq x^{\prime}$ and $y\sqsubseteq y^{\prime}$ imply $x\otimes
y\sqsubseteq x^{\prime}\otimes y^{\prime}\quad(\forall
x,x^{\prime},y,y^{\prime}\in\mathcal{V}_{0})$;

(Associative law)

$x\otimes(y\otimes z)=(x\otimes y)\otimes z\quad(\forall
x,y,z\in\mathcal{V}_{0})$;

(Unit law for $\otimes$)

$e\otimes x=x=x\otimes e\quad(\forall x\in\mathcal{V}_{0})$;

(Commutative law for $\otimes$)

$x\otimes y=y\otimes x\quad(\forall x,y\in\mathcal{V}_{0})$.

A symmetric monoidal complete lattice (SM-CL) is an SM-P whose underlying
poset $\mathcal{V}_{0}$ is a complete lattice.

Thus, an SM-P is nothing but a partially ordered commutative monoid. The name
of the operation $\otimes$, tensor product, comes from the fact that in some
(non-poset) symmetric monoidal categories, the corresponding operation is
given by the classical tensor product of e.g., modules.

######  Definition 2.2.

A symmetric closed poset (SC-P) $\mathcal{V}$ is a triple
$(\mathcal{V}_{0},[-,-],e)$ where

  * •

$\mathcal{V}_{0}=(\mathcal{V}_{0},\sqsubseteq)$ is a poset called the
underlying poset;

  * •

$[-,-]\colon\mathcal{V}_{0}^{\textup{op}}\times\mathcal{V}_{0}\longrightarrow\mathcal{V}_{0}$
is a binary operation on $\mathcal{V}_{0}$ called the internal-hom;

  * •

$e$ is an element of $\mathcal{V}_{0}$ called the unit element;

such that the following axioms hold:

(Monotonicity of $[-,-]$)

$y\sqsupseteq y^{\prime}$ and $z\sqsubseteq z^{\prime}$ imply
$[y,z]\sqsubseteq[y^{\prime},z^{\prime}]\quad(\forall
y,y^{\prime},z,z^{\prime}\in\mathcal{V}_{0})$;

(Composition law)

$[y,z]\sqsubseteq[[x,y],[x,z]]\quad(\forall x,y,z\in\mathcal{V}_{0})$;

(Unit law for $[-,-]$)

$z=[e,z]\quad(\forall z\in\mathcal{V}_{0})$;

(Commutative law for $[-,-]$)

$x\sqsubseteq[y,z]\iff y\sqsubseteq[x,z]\quad(\forall
x,y,z\in\mathcal{V}_{0})$.

A symmetric closed complete lattice (SC-CL) is an SC-P whose underlying poset
$\mathcal{V}_{0}$ is a complete lattice.

Note the sign of an inequality in the monotonicity axiom: the domain of the
first argument of $[-,-]$ is
$\mathcal{V}_{0}^{\textup{op}}=(\mathcal{V}_{0},\sqsupseteq)$, the poset
obtained by reversing the order $\sqsubseteq$ in $\mathcal{V}_{0}$, thus a
clause in the antecedent of the monotonicity axiom is $y\sqsupseteq
y^{\prime}$, not $y\sqsubseteq y^{\prime}$. We will explain the mysterious
name “internal-hom” later.

######  Definition 2.3.

A symmetric monoidal closed poset (SMC-P) $\mathcal{V}$ is a quadruple
$(\mathcal{V}_{0},\otimes,$ $[-,-],e)$ where

  * •

the triple $(\mathcal{V}_{0},\otimes,e)$ is an SM-P;

  * •

the triple $(\mathcal{V}_{0},[-,-],e)$ is an SC-P;

such that these two structures are related as follows:

(Adjointness relation)

$x\otimes y\sqsubseteq z\iff x\sqsubseteq[y,z]\quad(\forall
x,y,z\in\mathcal{V}_{0})$.

A symmetric monoidal closed complete lattice (SMC-CL) is an SMC-P whose
underlying poset $\mathcal{V}_{0}$ is a complete lattice.

The adjointness relation, in the proof-tree notation

$\mathord{x\otimes y}\ \sqsubseteq\ \mathord{}$$z$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$[y,z]$

is equivalent to the requirement that the unary operations $(-\otimes y)$ and
$[y,-]$, obtained by substituting $y$, form a Galois connection with
$(-\otimes y)$ the left (lower) adjoint and $[y,-]$ the right (upper) adjoint.
One can view the commutative law for $[-,-]$ in a similar way.

Although we presented an SMC-P $\mathcal{V}$ as a quadruple
$(\mathcal{V}_{0},\otimes,$ $[-,-],e)$, in fact the adjointness relation is so
rigid that under which the tensor product $\otimes$ and the internal-hom
$[-,-]$ determine each other uniquely. In particular, when the underlying
poset is a complete lattice, the following holds:

######  Proposition 2.4.

Let $\mathcal{V}_{0}=(\mathcal{V}_{0},\sqsubseteq)$ be a complete lattice.
Then the following are equivalent:

  1. (i)

$(\mathcal{V}_{0},\otimes,[-,-],e)$ is an SMC-CL.

  2. (ii)

$(\mathcal{V}_{0},\otimes,e)$ is an SM-CL and for each $y\in\mathcal{V}_{0}$,
$(-\otimes y)$ preserves suprema.

  3. (iii)

$(\mathcal{V}_{0},[-,-],e)$ is an SC-CL and for each $y\in\mathcal{V}_{0}$,
$[y,-]$ preserves infima.

Moreover, the data in (ii) or (iii) are sufficient to recover the whole data
in (i).

###### Proof.

[(i)$\implies$(ii)

] The adjointness relation implies the following:

$\mathord{(\bigvee x_{i})\otimes y}\ \sqsubseteq\ \mathord{}$$z$
$\mathord{\bigvee x_{i}}\ \sqsubseteq\ \mathord{}$$[y,z]$ $\mathord{x_{i}}\
\sqsubseteq\ \mathord{}$$[y,z]\quad(\forall i)$ $\mathord{x_{i}\otimes y}\
\sqsubseteq\ \mathord{}$$z\phantom{[y,]}\quad(\forall i)$

Thus $(\bigvee x_{i})\otimes y=\bigvee(x_{i}\otimes y)$, as required.

[(ii)$\implies$(i)

] First we claim that in order to make the adjointness relation

$\mathord{x\otimes y}\ \sqsubseteq\ \mathord{}$$z$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$[y,z]$

hold for some binary operation $[-,-]$, the value of $[y,z]$ must be the
supremum of $x$’s satisfying $x\otimes y\sqsubseteq z$, namely,

$\displaystyle[y,z]=\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}.$ (2.1)

Note that the supremum certainly exists since $\mathcal{V}_{0}$ is assumed to
be a complete lattice. Suppose $[-,-]$ is a binary operation on
$\mathcal{V}_{0}$ satisfying the adjointness relation:

[$\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}\sqsubseteq[y,z]$

] For every $x\in\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq z\\}$,
$x\sqsubseteq[y,z]$ holds by the adjointness relation, so

$\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}\sqsubseteq[y,z].$

[$[y,z]\sqsubseteq\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}$

] $[y,z]\sqsubseteq[y,z]$ implies by the adjointness relation that
$[y,z]\otimes y$ $\sqsubseteq z$ and hence $[y,z]\in\\{x\in\mathcal{V}_{0}\mid
x\otimes y\sqsubseteq z\\},$ thus

$[y,z]\sqsubseteq\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}.$

Therefore (2.1) is the only possible definition for the operation $[-,-]$.
Conversely, (2.1) implies the adjointness relation:

[$x\otimes y\sqsubseteq z\implies x\sqsubseteq[y,z]$

] Since $x\otimes y\sqsubseteq z$ implies $x\in\\{x\in\mathcal{V}_{0}\mid
x\otimes y\sqsubseteq z\\}$,

$x\sqsubseteq\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}=[y,z].$

[$x\sqsubseteq[y,z]\implies x\otimes y\sqsubseteq z$

] We first show that $[y,z]\otimes y\sqsubseteq z$:

$\displaystyle[y,z]\otimes y$ $\displaystyle=\bigvee\\{x\in\mathcal{V}_{0}\mid
x\otimes y\sqsubseteq z\\}\otimes y$ $\displaystyle=\bigvee\\{x\otimes y\mid
x\otimes y\sqsubseteq z\\}$ $\displaystyle\sqsubseteq z.$

We used the assumption that $(-\otimes y)$ preserves suprema. Using this fact
and the monotonicity of $\otimes$, we conclude

$x\otimes y\sqsubseteq[y,z]\otimes y\sqsubseteq z.$

We now check that the operation $[-,-]$ defined by (2.1) satisfies the axioms
required for SC-Ps.

[Monotonicity of $[-,-]$

] Suppose $y\sqsupseteq y^{\prime}$ and $z\sqsubseteq z^{\prime}$ hold. Then,

$\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}\subseteq\\{x\in\mathcal{V}_{0}\mid x\otimes y^{\prime}\sqsubseteq
z^{\prime}\\}$

because $x\otimes y\sqsubseteq z$ implies $x\otimes y^{\prime}\sqsubseteq
x\otimes y\sqsubseteq z\sqsubseteq z^{\prime}.$ Therefore

$[y,z]=\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq
z\\}\sqsubseteq\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes
y^{\prime}\sqsubseteq z^{\prime}\\}=[y^{\prime},z^{\prime}],$

as required.

[Composition law

] The claim is $[y,z]\sqsubseteq[[x,y],[x,z]]$, namely,

$\bigvee\\{w\in\mathcal{V}_{0}\mid w\otimes y\sqsubseteq
z\\}\sqsubseteq\bigvee\\{w\in\mathcal{V}_{0}\mid
w\otimes[x,y]\sqsubseteq[x,z]\\}.$

Thus it suffices to show

$\displaystyle\\{w\in\mathcal{V}_{0}\mid w\otimes y\sqsubseteq z\\}$
$\displaystyle\subseteq\\{w\in\mathcal{V}_{0}\mid
w\otimes[x,y]\sqsubseteq[x,z]\\}$ $\displaystyle=\big{\\{}w\mid
w\otimes\bigvee\\{v\mid v\otimes x\sqsubseteq y\\}\sqsubseteq\bigvee\\{v\mid
v\otimes x\sqsubseteq z\\}\big{\\}}$
$\displaystyle=\big{\\{}w\mid\bigvee\\{w\otimes v\mid v\otimes x\sqsubseteq
y\\}\sqsubseteq\bigvee\\{v\mid v\otimes x\sqsubseteq z\\}\big{\\}}$

(here we used the assumption that $(w\otimes-)=(-\otimes w)$ preserves
suprema). So let us suppose $w\otimes y\sqsubseteq z$ and aim to show that

$\\{w\otimes v\mid v\otimes x\sqsubseteq y\\}\subseteq\\{v\mid v\otimes
x\sqsubseteq z\\}.$

This holds because for $v$ with $v\otimes x\sqsubseteq y$,

$(w\otimes v)\otimes x=w\otimes(v\otimes x)\sqsubseteq w\otimes y\sqsubseteq
z$

holds.

[Unit law for $[-,-]$

] The claim is $z=[e,z]$. This reduces to

$\displaystyle z$ $\displaystyle=\bigvee\\{x\in\mathcal{V}_{0}\mid x\otimes
e\sqsubseteq z\\}$ $\displaystyle=\bigvee\\{x\in\mathcal{V}_{0}\mid
x\sqsubseteq z\\},$

a trivial equality.

[Commutative law for $[-,-]$

] The claim is $x\sqsubseteq[y,z]\iff y\sqsubseteq[x,z]$, which follows from
the following proof tree:

$\mathord{x}\ \sqsubseteq\ \mathord{}$$[y,z]$ $\mathord{x\otimes y}\
\sqsubseteq\ \mathord{}$$z$ $\mathord{y\otimes x}\ \sqsubseteq\ \mathord{}$$z$
$\mathord{y}\ \sqsubseteq\ \mathord{}$$[x,z]$

[(i)$\implies$(iii)

] The adjointness relation implies the following:

$\mathord{x}\ \sqsubseteq\ \mathord{}$$[y,\bigwedge z_{i}]$ $\mathord{x\otimes
y}\ \sqsubseteq\ \mathord{}$$\bigwedge z_{i}$ $\mathord{x\otimes y}\
\sqsubseteq\ \mathord{}$$z_{i}\phantom{[y,]}\quad(\forall i)$ $\mathord{x}\
\sqsubseteq\ \mathord{}$$[y,z_{i}]\quad(\forall i)$

Thus $[y,\bigwedge z_{i}]=\bigwedge[y,z_{i}]$, as required.

[(iii)$\implies$(i)

] First we claim that in order to make the adjointness relation

$\mathord{x\otimes y}\ \sqsubseteq\ \mathord{}$$z$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$[y,z]$

hold for some binary operation $\otimes$, the value of $x\otimes y$ must be
the infimum of $z$’s satisfying $x\sqsubseteq[y,z]$, namely,

$\displaystyle x\otimes y=\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}.$ (2.2)

Note that the infimum certainly exists since $\mathcal{V}_{0}$ is assumed to
be a complete lattice. Suppose $\otimes$ is a binary operation on
$\mathcal{V}_{0}$ satisfying the adjointness relation:

[$x\otimes y\sqsubseteq\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}$

] For every $z\in\\{z\in\mathcal{V}_{0}\mid x\sqsubseteq[y,z]\\}$, $x\otimes
y\sqsubseteq z$ holds by the adjointness relation, so

$x\otimes y\sqsubseteq\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}.$

[$\bigwedge\\{z\in\mathcal{V}_{0}\mid x\sqsubseteq[y,z]\\}\sqsubseteq x\otimes
y$

] $x\otimes y\sqsubseteq x\otimes y$ implies by the adjointness relation that
$x\sqsubseteq$ $[y,x\otimes y]$ and hence $x\otimes
y\in\\{z\in\mathcal{V}_{0}\mid x\sqsubseteq[y,z]\\},$ thus

$\bigwedge\\{z\in\mathcal{V}_{0}\mid x\sqsubseteq[y,z]\\}\sqsubseteq x\otimes
y.$

Therefore (2.2) is the only possible definition for the operation $\otimes$.
Conversely, (2.2) implies the adjointness relation:

[$x\sqsubseteq[y,z]\implies x\otimes y\sqsubseteq z$

] Since $x\sqsubseteq[y,z]$ implies $z\in\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}$,

$x\otimes y=\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}\sqsubseteq z.$

[$x\otimes y\sqsubseteq z\implies x\sqsubseteq[y,z]$

] We first show that $x\sqsubseteq[y,x\otimes y]$:

$\displaystyle[y,x\otimes y]$
$\displaystyle=[y,\bigwedge\\{z\in\mathcal{V}_{0}\mid x\sqsubseteq[y,z]\\}]$
$\displaystyle=\bigwedge\\{[y,z]\mid x\sqsubseteq[y,z]\\}$
$\displaystyle\sqsupseteq x.$

We used the assumption that $[y,-]$ preserves infima. Using this fact and the
monotonicity of $[-,-]$, we conclude

$x\sqsubseteq[y,x\otimes y]\sqsubseteq[y,z].$

We now check that the operation $\otimes$ defined by (2.2) satisfies the
axioms required for SM-Ps.

[Monotonicity of $\otimes$

] Suppose $x\sqsubseteq x^{\prime}$ and $y\sqsubseteq y^{\prime}$ hold. Then,

$\\{z\in\mathcal{V}_{0}\mid
x^{\prime}\sqsubseteq[y^{\prime},z]\\}\subseteq\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}$

because $x^{\prime}\sqsubseteq[y^{\prime},z]$ implies $x\sqsubseteq
x^{\prime}\sqsubseteq[y^{\prime},z]\sqsubseteq[y,z].$ Therefore

$x\otimes y=\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[y,z]\\}\sqsubseteq\bigwedge\\{z\in\mathcal{V}_{0}\mid
x^{\prime}\sqsubseteq[y^{\prime},z]\\}=x^{\prime}\otimes y^{\prime},$

as required.

[Associative law

] The claim is $x\otimes(y\otimes z)=(x\otimes y)\otimes z$, namely,

$\bigwedge\\{w\in\mathcal{V}_{0}\mid x\sqsubseteq[y\otimes
z,w]\\}=\bigwedge\\{w\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq[z,w]\\}.$

We prove this by showing $\\{w\in\mathcal{V}_{0}\mid x\sqsubseteq[y\otimes
z,w]\\}=\\{w\in\mathcal{V}_{0}\mid x\otimes y\sqsubseteq[z,w]\\}$, or more
explicitly,

$\displaystyle\big{\\{}w\mid x\sqsubseteq[\bigwedge\\{v\mid
y\sqsubseteq[z,v]\\},w]\big{\\}}=\big{\\{}w\mid\bigwedge\\{v\mid
x\sqsubseteq[y,v]\\}\sqsubseteq[z,w]\big{\\}}.$ (2.3)

Note that by the commutative law for $[-,-]$, (2.3) is equivalent to

$\displaystyle\big{\\{}w\mid\bigwedge\\{v\mid
y\sqsubseteq[z,v]\\}\sqsubseteq[x,w]\big{\\}}=\big{\\{}w\mid
z\sqsubseteq[\bigwedge\\{v\mid x\sqsubseteq[y,v]\\},w]\big{\\}}.$ (2.4)

[(LHS)$\subseteq$(RHS)

] We show this in the form of (2.3). It suffices to show

$\displaystyle x\sqsubseteq[\bigwedge\\{v\mid y\sqsubseteq[z,v]\\},w]\implies$
$\displaystyle[z,w]\in\\{v\mid x\sqsubseteq[y,v]\\}$
$\displaystyle\big{(}\iff$ $\displaystyle x\sqsubseteq[y,[z,w]]\;\,\big{)}$

and this follows from

$\displaystyle[\bigwedge\\{v\mid y\sqsubseteq[z,v]\\},w]$
$\displaystyle\sqsubseteq[[z,\bigwedge\\{v\mid y\sqsubseteq[z,v]\\}],[z,w]]$
$\displaystyle=[\bigwedge\\{[z,v]\mid y\sqsubseteq[z,v]\\},[z,w]]$
$\displaystyle\sqsubseteq[y,[z,w]],$

where the first inequality is an instance of the composition law, the equality
follows from the inf-preserving property of $[z,-]$, and the last inequality
from $\bigwedge\\{[z,v]\mid y\sqsubseteq[z,v]\\}\sqsupseteq y$ and the
monotonicity of $[-,-]$.

[(LHS)$\supseteq$(RHS)

] In this case, we refer to the form (2.4). Now, a sufficient condition is

$\displaystyle z\sqsubseteq[\bigwedge\\{v\mid x\sqsubseteq[y,v]\\},w]\implies$
$\displaystyle[x,w]\in\\{v\mid y\sqsubseteq[z,v]\\}$
$\displaystyle\big{(}\iff$ $\displaystyle y\sqsubseteq[z,[x,w]]$
$\displaystyle\iff$ $\displaystyle z\sqsubseteq[y,[x,w]]\;\,\big{)}$

and this follows from

$\displaystyle[\bigwedge\\{v\mid x\sqsubseteq[y,v]\\},w]$
$\displaystyle\sqsubseteq[[x,\bigwedge\\{v\mid x\sqsubseteq[y,v]\\}],[x,w]]$
$\displaystyle=[\bigwedge\\{[x,v]\mid x\sqsubseteq[y,v]\\},[x,w]]$
$\displaystyle=[\bigwedge\\{[x,v]\mid y\sqsubseteq[x,v]\\},[x,w]]$
$\displaystyle\sqsubseteq[y,[x,w]],$

where the first inequality is an instance of the composition law, the first
equality follows from the inf-preserving property of $[z,-]$, and the last
inequality from $\bigwedge\\{[x,v]\mid y\sqsubseteq[x,v]\\}\sqsupseteq y$ and
the monotonicity of $[-,-]$.

[Unit law for $\otimes$

] The claim is $e\otimes x=x=x\otimes e$. Assuming the commutative law for
$\otimes$ proved below, it suffices to show $x=x\otimes e$, namely,

$\displaystyle x$ $\displaystyle=\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq[e,z]\\}$ $\displaystyle=\bigwedge\\{z\in\mathcal{V}_{0}\mid
x\sqsubseteq z\\},$

which obviously holds.

[Commutative law for $\otimes$

] The claim is $x\otimes y=y\otimes x$, which follows from the following proof
tree:

$\mathord{x\otimes y}\ \sqsubseteq\ \mathord{}$$z$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$[y,z]$ $\mathord{y}\ \sqsubseteq\ \mathord{}$$[x,z]$
$\mathord{y\otimes x}\ \sqsubseteq\ \mathord{}$$z$

where $z$ is an arbitrary element of $\mathcal{V}_{0}$.

∎

By virtue of this proposition, we will usually check only the condition (ii)
to prove that a particular system is an SMC-CL. However, we will not ignore
internal-hom’s, since writing them down explicitly often clarifies the
situation.

We complete the limit-preserving properties of $\otimes$ and $[-,-]$ of SMC-
CLs by the following proposition:

######  Proposition 2.5.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,[-,-],e)$ be an SMC-CL. Then the
following hold:

  1. (i)

For each $x\in\mathcal{V}_{0}$, $(x\otimes-)$ preserves suprema.

  2. (ii)

For each $z\in\mathcal{V}_{0}$, $[-,z]$ turns suprema into infima.

###### Proof.

[(i)

] The commutativity of $\otimes$ and sup-preserving property of $(-\otimes x)$
imply the following:

$\mathord{x\otimes(\bigvee y_{i})}\ \sqsubseteq\ \mathord{}$$z$
$\mathord{(\bigvee y_{i})\otimes x}\ \sqsubseteq\ \mathord{}$$z$
$\mathord{y_{i}\otimes x}\ \sqsubseteq\ \mathord{}$$z\quad\;\;(\forall i)$
$\mathord{x\otimes y_{i}}\ \sqsubseteq\ \mathord{}$$z\quad\;\;(\forall i)$

Thus $x\otimes(\bigvee y_{i})=\bigvee(x\otimes y_{i})$, as required.

[(ii)

] The commutativity of $[-,-]$ implies the following:

$\mathord{x}\ \sqsubseteq\ \mathord{}$$[(\bigvee y_{i}),z]$ $\mathord{\bigvee
y_{i}}\ \sqsubseteq\ \mathord{}$$[x,z]$ $\mathord{y_{i}}\ \sqsubseteq\
\mathord{}$$[x,z]\phantom{y_{i}}\quad(\forall i)$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$[y_{i},z]\phantom{x}\quad(\forall i)$

Thus $[(\bigvee y_{i}),z]=\bigwedge[y_{i},z]$, as required.

∎

Now we proceed to see some examples. We begin with a toy example.

######  Example 2.6 ([5]).

The quadruple
$\textbf{2}=(\\{\textup{true},\textup{false}\\},\&,\supset,\textup{true})$ is
defined as follows:

  * •

$\\{\textup{true},\textup{false}\\}=(\\{\textup{true},\textup{false}\\},\vdash)$
is the two-element poset of truth values ordered by entailment $\vdash$; see
the table below for detail (the symbol $\fullmoon$ denotes that the relation
holds, and $\times$ that the relation does not hold):

$x\vdash y$ | $y$
---|---
true | false
$x$ | true | $\fullmoon$ | $\times$
false | $\fullmoon$ | $\fullmoon$
  * •

$\&$ is the binary operation defined as the usual conjunction, as in the
following table:

$x\,\&\,y$ | $y$
---|---
true | false
$x$ | true | true | false
false | false | false
  * •

$\supset$ is the binary operation defined as the usual implication:

$x\supset y$ | $y$
---|---
true | false
$x$ | true | true | false
false | true | true

One can easily verify that 2 is an SMC-CL.

The current thesis is largely indebted to William Lawvere’s 1973 paper [5]. In
this paper, he observed that metric spaces are a special kind of enriched
categories, using the following category (in fact, poset)
$\overline{\mathbb{R}}_{+}$:

######  Example 2.7.

The quadruple
$\overline{\mathbb{R}}_{+}=(\mathbb{R}_{+}\cup\\{\infty\\},+,\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}},0)$ is defined as follows:

  * •

$\mathbb{R}_{+}\cup\\{\infty\\}=(\mathbb{R}_{+}\cup\\{\infty\\},\geq)$ is the
set of nonnegative real numbers $\mathbb{R}_{+}=\\{x\in\mathbb{R}\mid$ $x\geq
0\\}$ with an additional element $\infty$, ordered by the opposite $\geq$ of
the usual ordering $\leq$ (extended from $\mathbb{R}_{+}$ to
$\mathbb{R}_{+}\cup\\{\infty\\}$ in an obvious way). More explicitly,
supposing $s,t\in\mathbb{R}_{+}$ (thus we already know whether $s\geq t$ holds
or not), the order is given by the following table:

$x\geq y$ | $y$
---|---
$t$ | $\infty$
$x$ | $s$ | $s\geq t$ | $\times$
$\infty$ | $\fullmoon$ | $\fullmoon$
  * •

$+$ is the binary operation defined as the natural extension of the usual
addition:

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

$\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ is the binary
operation called the truncated subtraction. To define this, we first set
$t\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}s=\max\\{t-s,0\\}$ for $s,t\in\mathbb{R}_{+}$.
Then the domain of $\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$ is extended to $\mathbb{R}_{+}\cup\\{\infty\\}$
as follows (note the order of the arguments; we set
$[x,y]=y\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}x$):

$y\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}x$ | $y$
---|---
$t$ | $\infty$
$x$ | $s$ | $t\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}s$ | $\infty$
$\infty$ | $0$ | $0$

Then it turns out that $\overline{\mathbb{R}}_{+}$ is an SMC-CL.

The reader may feel that the definition of the extended operations is somewhat
arbitrary, especially in the case $\infty\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\infty=0$. We first note that, contrary to such a
view, in order $\overline{\mathbb{R}}_{+}$ to be an SMC-CL, the extensions of
$+$ and $\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ are
completely determined as soon as we extend the order $\geq$. To see this,
recall from Propositions 2.4 and 2.5 that necessary conditions for the
quadruple
$\overline{\mathbb{R}}_{+}=(\mathbb{R}_{+}\cup\\{\infty\\},+,\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}},0)$ to be an SMC-CL are that

$\displaystyle x+(-)\text{ preserves suprema for each
}x\in\mathbb{R}_{+}\cup\\{\infty\\};$ (2.5) $\displaystyle(-)+y\text{
preserves suprema for each }y\in\mathbb{R}_{+}\cup\\{\infty\\};$ (2.6)
$\displaystyle(-)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}x\text{ preserves infima for each
}x\in\mathbb{R}_{+}\cup\\{\infty\\};$ (2.9) $\displaystyle
y\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}(-)\text{ turns
suprema into infima for each }y\in\mathbb{R}_{+}\cup\\{\infty\\}.$ (2.12)

Now that we are working with the opposite ordering $\geq$, which means our
supremum $\bigvee$ corresponds to the usual infimum (for which we use a
different symbol $\inf$) and dually, we obtain the following for each
$x,y\in\mathbb{R}_{+}\cup\\{\infty\\}$ and $s\in\mathbb{R}_{+}$:

$\displaystyle
x+\infty=x+\inf\emptyset\overset{\text{(\ref{lim_ten1})}}{=}\inf\emptyset=\infty;$
$\displaystyle\infty+y=\inf\emptyset+y\overset{\text{(\ref{lim_ten2})}}{=}\inf\emptyset=\infty;$
$\displaystyle\infty\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}s=\sup_{t\in\mathbb{R}_{+}}\\{t\\}\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}s\overset{\text{(\ref{lim_hom1})}}{=}\sup_{t\in\mathbb{R}_{+}}\\{t\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}s\\}=\infty;$ $\displaystyle
y\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\infty=y\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\inf\emptyset\overset{\text{(\ref{lim_hom2})}}{=}\sup\emptyset=0.$

These specify the extensions.

We then show that $\overline{\mathbb{R}}_{+}$ is indeed an SMC-CL, following
the condition (ii) of Proposition 2.4.

[$\mathbb{R}_{+}\cup\\{\infty\\}$ is a complete lattice

] A well-known fact.

[Monotonicity of $+$

] Suppose $x\geq x^{\prime}$ and $y\geq y^{\prime}$ hold. If all of
$x,x^{\prime},y,y^{\prime}$ are elements of $\mathbb{R}_{+}$, then $x+y\geq
x^{\prime}+y^{\prime}$ holds. Otherwise, either $x$ or $y$ is $\infty$; thus
$x+y=\infty$ and again $x+y\geq x^{\prime}+y^{\prime}$ holds.

[Associative law

] The claim is $x+(y+z)=(x+y)+z$. If all of $x,y,z$ are elements of
$\mathbb{R}_{+}$, the claim reduces to an elementary fact. Otherwise, one of
$x,y,z$ is $\infty$, and both of $x+(y+z)$ and $(x+y)+z$ are equal to
$\infty$.

[Unit law

] The claim is $0+x=x=x+0$. If $x\in\mathbb{R}_{+}$, it certainly holds; if
not, $0+\infty=\infty=\infty+0$ and again it holds.

[Commutative law

] The claim is $x+y=y+x$. If $x,y\in\mathbb{R}_{+}$, it holds. Otherwise, both
sides are equal to $\infty$.

[$(-)+y$ preserves suprema

] If $y=\infty$, the function $(-)+y$ constantly returns $\infty$, which is
also the least element (the supremum of the empty set). Thus it preserves all
suprema.

Suppose $y\in\mathbb{R}_{+}$ and take an arbitrary family
$x_{i}\in\mathbb{R}_{+}\cup\\{\infty\\}$ $(i\in I)$. We aim to prove

$\displaystyle\inf_{i\in I}\\{x_{i}\\}+y=\inf_{i\in I}\\{x_{i}+y\\}.$ (2.13)

If $\inf_{i\in I}\\{x_{i}\\}=\infty$, then for all $i\in I$, $x_{i}=\infty$.
Therefore for all $i\in I$, $x_{i}+y=\infty$ and both sides of (2.13) evaluate
to $\infty$.

If $\inf_{i\in I}\\{x_{i}\\}\in\mathbb{R}_{+}$, then there exists $i\in I$
with $x_{i}\in\mathbb{R}_{+}$, and we may simply omit those $x_{i}$’s with
$x_{i}=\infty$, obtaining a new family $x_{i}\in\mathbb{R}_{+}$ $(i\in
I\neq\emptyset)$ of nonnegative real numbers. Now (2.13) essentially reduces
to the continuity of $+$.

Finally, we show that $\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$ is indeed the internal-hom, by checking the
adjointness relation.

[$x+y\geq z\implies x\geq z\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y\\!\\!\\!$

] The monotonicity of $\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$ is easily verified. Therefore, $x+y\geq z$
implies $(x+y)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y\geq z\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y$. So it suffices to show
$x\geq(x+y)\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}y$,
which follows from the table below:

$(x+y)\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}y$ | $y$
---|---
$t$ | $\infty$
$\;\,\quad x$ | $s$ | $s$ | $0$
$\infty$ | $\infty$ | $0$
[$x\geq z\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}y\implies
x+y\geq z\\!\\!\\!$

] By the monotonicity of $+$, $x\geq z\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y$ implies
$x+y\geq(z\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}y)+y$.
So it suffices to show $(z\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}y)+y\geq z$, which follows from the table below:

$(z\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}y)+y$ | $z$
---|---
$t$ | $\infty$
$\;\,\quad y$ | $s$ | $\max\\{s,t\\}$ | $\infty$
$\infty$ | $\infty$ | $\infty$

Several variants of $\overline{\mathbb{R}}_{+}$ follow. First we observe that
a similar construction works when $\mathbb{R}$ is replaced by $\mathbb{Z}$.

######  Example 2.8.

The quadruple
$\overline{\mathbb{Z}}_{+}=(\mathbb{Z}_{+}\cup\\{\infty\\},+,\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}},0)$ is defined as follows:

  * •

$\mathbb{Z}_{+}\cup\\{\infty\\}=(\mathbb{Z}_{+}\cup\\{\infty\\},\geq)$ is the
set of nonnegative integers $\mathbb{Z}_{+}=\\{x\in\mathbb{Z}\mid$ $x\geq
0\\}$ with an additional element $\infty$, ordered by $\geq$, the order
relation similar to that on $\mathbb{R}_{+}\cup\\{\infty\\}$. For
$s,t\in\mathbb{Z}_{+}$, it is given as follows:

$x\geq y$ | $y$
---|---
$t$ | $\infty$
$x$ | $s$ | $s\geq t$ | $\times$
$\infty$ | $\fullmoon$ | $\fullmoon$
  * •

$+$ is an extension of the usual addition:

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

$\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ is an extension
of the operation defined as $t\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}s=\max\\{t-s,0\\}$:

$y\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}x$ | $y$
---|---
$t$ | $\infty$
$x$ | $s$ | $t\mathbin{\text{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}s$ | $\infty$
$\infty$ | $0$ | $0$

$\overline{\mathbb{Z}}_{+}$ is an SMC-CL; its proof is obtained by a slight
modification to that for $\overline{\mathbb{R}}_{+}$. Again we have no choice
for extensions of operations $+$ and $\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$.

The reader may notice that the cases for $\mathbb{Z}$ and for $\mathbb{R}$ are
almost completely parallel; such a phenomenon occurs frequently in what
follows. We henceforth let the symbol $\mathbb{K}$ denote either $\mathbb{Z}$
or $\mathbb{R}$ and treat both cases simultaneously whenever convenient. This
convention lasts throughout the thesis.

Next example introduces the most important enriching posets in this thesis.
The definition when $\mathbb{K}=\mathbb{R}$ appears in [6].

######  Example 2.9.

The quadruple
$\overline{\mathbb{K}}=(\mathbb{K}\cup\\{-\infty,\infty\\},+,-,0)$ is defined
as follows:

  * •

$\mathbb{K}\cup\\{-\infty,\infty\\}=(\mathbb{K}\cup\\{-\infty,\infty\\},\geq)$
is the set $\mathbb{K}$ with two additional elements $-\infty$ and $\infty$,
ordered by $\geq$. Supposing $s,t\in\mathbb{K}$, the relation is specified by
the following table:

$x\geq y$ |  | $y$ |
---|---|---|---
$-\infty$ | $t$ | $\infty$
$x$ | $-\infty$ | $\fullmoon$ | $\times$ | $\times$
$s$ | $\fullmoon$ | $s\geq t$ | $\times$
$\infty$ | $\fullmoon$ | $\fullmoon$ | $\fullmoon$
  * •

$+$ is the binary operation defined as an extension of the usual addition:

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

$-$ is the binary operation defined as an extension of the usual subtraction
(the order of the arguments is similar to that of the truncated subtraction,
namely, $[x,y]=y-x$):

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

We claim that $\overline{\mathbb{K}}$ is an SMC-CL.

First we see that the extensions of $+$ and $-$ are automatically derived by a
method similar to one we used in the $\overline{\mathbb{R}}_{+}$-case. Let us
write down the results of Propositions 2.4 and 2.5 concerning necessary
conditions for the quadruple
$\overline{\mathbb{K}}=(\mathbb{K}\cup\\{-\infty,\infty\\},+,-,0)$ to be an
SMC-CL:

$\displaystyle x+(-)\text{ preserves suprema for each
}x\in\mathbb{K}\cup\\{-\infty,\infty\\};$ (2.14) $\displaystyle(-)+y\text{
preserves suprema for each }y\in\mathbb{K}\cup\\{-\infty,\infty\\};$ (2.15)
$\displaystyle(-)-x\text{ preserves infima for each
}x\in\mathbb{K}\cup\\{-\infty,\infty\\};$ (2.16) $\displaystyle y-(-)\text{
turns suprema into infima for each }y\in\mathbb{K}\cup\\{-\infty,\infty\\}.$
(2.17)

Since the ordering $\geq$ is again the reverse of the usual one, we
introduce the notation in which we denote suprema and infima with respect to
$\geq$ by $\bigvee$ and $\bigwedge$, whereas infima and suprema with respect
to the usual ordering $\leq$ by $\inf$ and $\sup$, respectively. We obtain,
for each $x,y\in\mathbb{K}\cup\\{-\infty,\infty\\}$ and $s,t\in\mathbb{K}$,
the following:

$\displaystyle
x+\infty=x+\inf\emptyset\overset{\text{(\ref{zlim_ten1})}}{=}\inf\emptyset=\infty;$
$\displaystyle
s+(-\infty)=s+\inf_{t\in\mathbb{K}}\\{t\\}\overset{\text{(\ref{zlim_ten1})}}{=}\inf_{t\in\mathbb{K}}\\{s+t\\}=-\infty;$
(2.18)
$\displaystyle\infty+y=\inf\emptyset+y\overset{\text{(\ref{zlim_ten2})}}{=}\inf\emptyset=\infty;$
$\displaystyle(-\infty)+t=\inf_{s\in\mathbb{K}}\\{s\\}+t\overset{\text{(\ref{zlim_ten2})}}{=}\inf_{s\in\mathbb{K}}\\{s+t\\}=-\infty;$
$\displaystyle\infty-s=\sup_{t\in\mathbb{K}}\\{t\\}-s\overset{\text{(\ref{zlim_hom1})}}{=}\sup_{t\in\mathbb{K}}\\{t-s\\}=\infty;$
(2.19)
$\displaystyle(-\infty)-x=\sup\emptyset-x\overset{\text{(\ref{zlim_hom1})}}{=}\sup\emptyset=-\infty;$
$\displaystyle
y-\infty=y-\inf\emptyset\overset{\text{(\ref{zlim_hom2})}}{=}\sup\emptyset=-\infty;$
$\displaystyle
t-(-\infty)=t-\inf_{s\in\mathbb{K}}\\{s\\}\overset{\text{(\ref{zlim_hom2})}}{=}\sup_{s\in\mathbb{K}}\\{t-s\\}=\infty.$

Finally, we define two remaining cases:

$\displaystyle(-\infty)+(-\infty)=\inf_{s\in\mathbb{K}}\\{s\\}+(-\infty)\overset{\text{(\ref{zlim_ten2})}}{=}\inf_{s\in\mathbb{K}}\\{s+(-\infty)\\}\overset{\text{(\ref{sPlusMinusInfty})}}{=}\inf_{s\in\mathbb{K}}\\{-\infty\\}=-\infty;$
$\displaystyle\infty-(-\infty)=\infty-\inf_{s\in\mathbb{K}}\\{s\\}\overset{\text{(\ref{zlim_hom2})}}{=}\sup_{s\in\mathbb{K}}\\{\infty-s\\}\overset{\text{(\ref{inftyMinusS})}}{=}\sup_{s\in\mathbb{K}}\\{\infty\\}=\infty.$

Now the extensions have completed.

The proof that $\overline{\mathbb{K}}$ is an SMC-CL is simply a little bigger
version of the case analyses we did in Example 2.7.

The last example below is of a bit different flavor:

######  Example 2.10.

Let $L=(L_{0},\supset)$ be a complete Heyting algebra, that is, a complete
lattice $L_{0}=(L_{0},\sqsubseteq)$ equipped with a binary operation
$\supset\colon L_{0}^{\textup{op}}\times L_{0}\longrightarrow L_{0}$ called
the implication, with the following property:

$\mathord{x\land y}\ \sqsubseteq\ \mathord{}$$z$ $\mathord{x}\ \sqsubseteq\
\mathord{}$$y\supset z$

Then, the quadruple $L=(L_{0},\land,\supset,\top)$, where $\top$ is the
largest element of $L_{0}$, is an SMC-CL. Such SMC-CLs (in which the tensor
product is given by the meet $\land$) are called Cartesian closed complete
lattices, which are nevertheless essentially the same as complete Heyting
algebras.

As a special case, we have the following Cartesian closed complete lattices:
the quadruple
$\overline{\mathbb{K}}_{+}^{\text{Cart}}=(\mathbb{K}_{+}\cup\\{\infty\\},\max,\supset,0)$,
where $\mathbb{K}_{+}\cup\\{\infty\\}$ is ordered by $\geq$, and $\supset$
(the order of arguments is $[x,y]=x\supset y$) is defined as

$x\supset y=\begin{cases}0&(x\geq y)\\\ y&(x<y).\end{cases}$

This appears in [5] when $\mathbb{K}=\mathbb{R}$. Just as
$\overline{\mathbb{K}}_{+}$ will be used to generalize metric spaces, we will
later use $\overline{\mathbb{K}}_{+}^{\text{Cart}}$ to generalize ultrametric
spaces.

###  2.2 Enriched Categories

Every poset-enriched category has a particular enriching poset $\mathcal{V}$
which is used to describe its structure. Although we introduced the notion of
SMC-CLs in the previous section, in the early stages of the theory of poset-
enriched categories, it suffices to require the enriching poset $\mathcal{V}$
to be an SM-P.

######  Definition 2.11.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,e)$ be an SM-P. A
$\mathcal{V}$-category $\mathcal{A}$ is a pair $(\textup{Ob}(\mathcal{A}),$
$\textup{Hom}_{\mathcal{A}})$ where

  * •

$\textup{Ob}(\mathcal{A})$ is the set of objects of $\mathcal{A}$;

  * •

$\textup{Hom}_{\mathcal{A}}$ is a map which assigns for each pair $a,b$ of
objects of $\mathcal{A}$, an element $\textup{Hom}_{\mathcal{A}}(a,b)$ of
$\mathcal{V}_{0}$ called its hom-object;

such that the following axioms hold:

(Composition law)

$\textup{Hom}_{\mathcal{A}}(a,b)\otimes\textup{Hom}_{\mathcal{A}}(b,c)\sqsubseteq\textup{Hom}_{\mathcal{A}}(a,c)\quad(\forall
a,b,c\in\textup{Ob}(\mathcal{A}))$;

(Identity law)

$e\sqsubseteq\textup{Hom}_{\mathcal{A}}(a,a)\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$.

The definition is best explained by the various examples given below. Note the
apparent conflict of the term “composition law”; an axiom in the definition of
SC-Ps also bears the same name. However, we will see later that the
composition law for $\mathcal{V}$ can be seen as an instance of the
composition law for $\mathcal{V}$-categories, thus justifying the terminology.

######  Example 2.12.

A 2-category is nothing but a preordered set. In fact, a 2-category
$\mathcal{A}$ is a pair $(\textup{Ob}(\mathcal{A}),\preceq_{\mathcal{A}})$
where

  * •

$\textup{Ob}(\mathcal{A})$ is a set;

  * •

$\preceq_{\mathcal{A}}$ takes two elements $a,b$ of $\textup{Ob}(\mathcal{A})$
and returns a truth value, which can be interpreted to denote whether the
relation $(a\preceq_{\mathcal{A}}b)$ holds or not;

such that the following axioms hold:

(Composition law)

$(a\preceq_{\mathcal{A}}b)\,\&\,(b\preceq_{\mathcal{A}}c)\vdash(a\preceq_{\mathcal{A}}c)\quad(\forall
a,b,c\in\textup{Ob}(\mathcal{A}))$;

(Identity law)

$\textup{true}\vdash(a\preceq_{\mathcal{A}}a)\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$.

Of course, the composition law requires transitivity of
$\preceq_{\mathcal{A}}$ and the identity law the reflexivity of
$\preceq_{\mathcal{A}}$.

######  Example 2.13.

An $\overline{\mathbb{R}}_{+}$-category, or a Lawvere metric space,
$\mathcal{A}$ is a pair $(\textup{Ob}(\mathcal{A}),$ $d_{\mathcal{A}})$ where

  * •

$\textup{Ob}(\mathcal{A})$ is the set of points of $\mathcal{A}$;

  * •

$d_{\mathcal{A}}$, called the distance function of $\mathcal{A}$, takes two
points $a,b$ of $\mathcal{A}$ and returns a value
$d_{\mathcal{A}}(a,b)\in\mathbb{R}_{+}\cup\\{\infty\\}$;

such that the following axioms hold:

(Composition law)

$d_{\mathcal{A}}(a,b)+d_{\mathcal{A}}(b,c)\geq
d_{\mathcal{A}}(a,c)\quad(\forall a,b,c\in\textup{Ob}(\mathcal{A}))$;

(Identity law)

$0\geq d_{\mathcal{A}}(a,a)\quad(\forall a\in\textup{Ob}(\mathcal{A}))$.

Since $0\geq x$ if and only if $x=0$, the identity law is equivalent to
$d_{\mathcal{A}}(a,a)=0$. Lawvere remarked in [5] that every metric space is
an $\overline{\mathbb{R}}_{+}$-category. In fact, the composition law is
nothing but the triangle inequality, and the identity law is also a usual
requirement for the distance functions of metric spaces.

Note that the notion of Lawvere metric spaces generalizes that of metric
spaces in the following points:

  * •

the distance function $d_{\mathcal{A}}$ is not necessarily symmetric, i.e.,
there may exist points $a,b$ of $\mathcal{A}$ with $d_{\mathcal{A}}(a,b)\neq
d_{\mathcal{A}}(b,a)$;

  * •

the values of distance function can attain $\infty$;

  * •

the points $a,b$ of $\mathcal{A}$ with $d_{\mathcal{A}}(a,b)=0$, or even
$d_{\mathcal{A}}(a,b)=d_{\mathcal{A}}(b,a)=0$, may be distinct.

######  Example 2.14.

$\overline{\mathbb{Z}}_{+}$-categories are defined similarly. One can regard
them as a generalization of $\mathbb{Z}_{+}$-valued (or discrete) metric
spaces.

The following classes of enriched categories will be the main field of our
study:

######  Example 2.15.

A $\overline{\mathbb{K}}$-category $\mathcal{A}$ is a pair
$(\textup{Ob}(\mathcal{A}),$ $d_{\mathcal{A}})$ where

  * •

$\textup{Ob}(\mathcal{A})$ is the set of points of $\mathcal{A}$;

  * •

$d_{\mathcal{A}}$, called the distance function of $\mathcal{A}$, takes two
points $a,b$ of $\mathcal{A}$ and returns a value
$d_{\mathcal{A}}(a,b)\in\mathbb{K}\cup\\{-\infty,\infty\\}$;

such that the following axioms hold:

(Composition law)

$d_{\mathcal{A}}(a,b)+d_{\mathcal{A}}(b,c)\geq
d_{\mathcal{A}}(a,c)\quad(\forall a,b,c\in\textup{Ob}(\mathcal{A}))$;

(Identity law)

$0\geq d_{\mathcal{A}}(a,a)\quad(\forall a\in\textup{Ob}(\mathcal{A}))$.

Note that for each $a\in\textup{Ob}(\mathcal{A})$ the composition law yields

$\displaystyle d_{\mathcal{A}}(a,a)+d_{\mathcal{A}}(a,a)\geq
d_{\mathcal{A}}(a,a);$ (2.20)

we can combine this with the identity law and deduce

$d_{\mathcal{A}}(a,a)=0\text{ or }-\infty,$

because no negative number $d_{\mathcal{A}}(a,a)\in\mathbb{K}$ satisfies
(2.20).

######  Example 2.16.

A $\overline{\mathbb{K}}_{+}^{\text{Cart}}$-category $\mathcal{A}$ is a pair
$(\textup{Ob}(\mathcal{A}),$ $d_{\mathcal{A}})$ where

  * •

$\textup{Ob}(\mathcal{A})$ is the set of points of $\mathcal{A}$;

  * •

$d_{\mathcal{A}}$ takes two points $a,b$ of $\mathcal{A}$ and returns a value
$d_{\mathcal{A}}(a,b)\in\mathbb{K}_{+}\cup\\{\infty\\}$;

such that the following axioms hold:

(Composition law)

$\max\\{d_{\mathcal{A}}(a,b),d_{\mathcal{A}}(b,c)\\}\geq
d_{\mathcal{A}}(a,c)\quad(\forall a,b,c\in\textup{Ob}(\mathcal{A}))$;

(Identity law)

$0\geq d_{\mathcal{A}}(a,a)\quad(\forall a\in\textup{Ob}(\mathcal{A}))$.

Of course, we can rewrite the identity law as $d_{\mathcal{A}}(a,a)=0$. As
observed in [5] (when $\mathbb{K}=\mathbb{R}$),
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-categories generalize (discrete or
ordinary) ultrametric spaces.

###  2.3 Enriched Functors and Canonical Orderings

One can understand the notion of $\mathcal{V}$-functors as structure-
preserving maps between $\mathcal{V}$-categories. In the general enriched
category theory (where the enriching category is not necessarily a poset),
there is a yet higher notion of $\mathcal{V}$-natural transformations, which
are regarded as maps between $\mathcal{V}$-functors. In our theory, however,
the notion of $\mathcal{V}$-natural transformations are largely trivialized,
and it only remains as a certain preorder relation among
$\mathcal{V}$-functors with specified domain and codomain
$\mathcal{V}$-categories.

######  Definition 2.17.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,e)$ be an SM-P, and $\mathcal{A}=$
$(\textup{Ob}(\mathcal{A}),\textup{Hom}_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\textup{Hom}_{\mathcal{B}})$ be
$\mathcal{V}$-categories. A $\mathcal{V}$-functor

$F\colon\mathcal{A}\longrightarrow\mathcal{B}$

from $\mathcal{A}$ to $\mathcal{B}$ is a map

$\textup{Ob}(F)\colon\textup{Ob}(\mathcal{A})\longrightarrow\textup{Ob}(\mathcal{B})$

between the sets of objects with the following property:

(Increasing condition)

$\textup{Hom}_{\mathcal{A}}(a,a^{\prime})\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}\textup{Ob}(F)(a),\textup{Ob}(F)(a^{\prime})\big{)}$
$(\forall a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$.

In case a stronger condition

$\textup{Hom}_{\mathcal{A}}(a,a^{\prime})=\textup{Hom}_{\mathcal{B}}\big{(}\textup{Ob}(F)(a),\textup{Ob}(F)(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$

holds, $F$ is called a fully faithful $\mathcal{V}$-functor.

$\mathcal{A}$ is called the domain of $F$ and $\mathcal{B}$ the codomain of
$F$. We denote the set of all $\mathcal{V}$-functors from $\mathcal{A}$ to
$\mathcal{B}$ by $[\mathcal{A},\mathcal{B}]_{0}$.

For brevity, we often denote the values like $\textup{Ob}(F)(a)$ by $F(a)$.
Clearly, $\mathcal{V}$-functors are closed under composition:

######  Proposition 2.18.

Let $F\colon\mathcal{A}\longrightarrow\mathcal{B}$ and
$G\colon\mathcal{B}\longrightarrow\mathcal{C}$ be $\mathcal{V}$-functors.
Then, the composite map

$\textup{Ob}(G)\circ\textup{Ob}(F)\colon\textup{Ob}(\mathcal{A})\longrightarrow\textup{Ob}(\mathcal{B})\longrightarrow\textup{Ob}(\mathcal{C})$

defines a $\mathcal{V}$-functor $G\circ
F\colon\mathcal{A}\longrightarrow\mathcal{C}$.

###### Proof.

For all $a,a^{\prime}\in\textup{Ob}(\mathcal{A})$, we have

$\textup{Hom}_{\mathcal{A}}(a,a^{\prime})\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}\sqsubseteq\textup{Hom}_{\mathcal{C}}\big{(}G\circ
F(a),G\circ F(a^{\prime})\big{)}.$

∎

Also, for every $\mathcal{V}$-category $\mathcal{A}$, the identity map on
$\textup{Ob}(\mathcal{A})$ defines a $\mathcal{V}$-functor. It is called the
identity $\mathcal{V}$-functor on $\mathcal{A}$ and denoted by
$1_{\mathcal{A}}$.

######  Definition 2.19.

Let $\mathcal{V}$ be an SM-P, and $\mathcal{A}$ and $\mathcal{B}$ be
$\mathcal{V}$-categories. A $\mathcal{V}$-functor

$F\colon\mathcal{A}\longrightarrow\mathcal{B}$

from $\mathcal{A}$ to $\mathcal{B}$ is an isomorphism if there exists a
$\mathcal{V}$-functor (called its inverse)

$G\colon\mathcal{B}\longrightarrow\mathcal{A}$

from $\mathcal{B}$ to $\mathcal{A}$ such that $G\circ F=1_{\mathcal{A}}$ and
$F\circ G=1_{\mathcal{B}}$ hold.

If there is an isomorphism between $\mathcal{A}$ and $\mathcal{B}$, then they
are said to be isomorphic and written as $\mathcal{A}\cong\mathcal{B}$.

######  Proposition 2.20.

A $\mathcal{V}$-functor

$F\colon\mathcal{A}\longrightarrow\mathcal{B}$

is an isomorphism if and only if it is fully faithful, and the map

$\textup{Ob}(F)\colon\textup{Ob}(\mathcal{A})\longrightarrow\textup{Ob}(\mathcal{B})$

between the sets of objects is a bijection.

###### Proof.

If $F$ is an isomorphism, let $G$ be its inverse. Then for each pair
$a,a^{\prime}\in\textup{Ob}(\mathcal{A})$,

$\displaystyle\textup{Hom}_{\mathcal{A}}(a,a^{\prime})$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{A}}\big{(}G\circ F(a),G\circ
F(a^{\prime})\big{)}$ $\displaystyle=\textup{Hom}_{\mathcal{A}}(a,a^{\prime})$

holds and $F$ is fully faithful. Also, $\textup{Ob}(G)$ witnesses that
$\textup{Ob}(F)$ is a bijection as a map.

Suppose then, that $F$ is fully faithful and $\textup{Ob}(F)$ is a bijection.
Let
$\textup{Ob}(G)\colon\textup{Ob}(\mathcal{B})\longrightarrow\textup{Ob}(\mathcal{A})$
be the inverse of $\textup{Ob}(F)$ (as a map). Then, for each pair
$b,b^{\prime}\in\textup{Ob}(\mathcal{B})$,

$\textup{Hom}_{\mathcal{B}}(b,b^{\prime})=\textup{Hom}_{\mathcal{B}}\big{(}F\circ
G(b),F\circ
G(b^{\prime})\big{)}=\textup{Hom}_{\mathcal{A}}\big{(}G(b),G(b^{\prime})\big{)}$

holds, thus $G$ is also a (fully faithful) $\mathcal{V}$-functor. By
construction, it is clear that $G\circ F=1_{\mathcal{A}}$ and $F\circ
G=1_{\mathcal{B}}$ hold. ∎

######  Definition 2.21.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,e)$ be an SM-P, and $\mathcal{A}=$
$(\textup{Ob}(\mathcal{A}),\textup{Hom}_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\textup{Hom}_{\mathcal{B}})$ be
$\mathcal{V}$-categories. The set $[\mathcal{A},\mathcal{B}]_{0}$ of all
$\mathcal{V}$-functors from $\mathcal{A}$ to $\mathcal{B}$ admits a canonical
relation $\Rightarrow$ defined as follows:

$F\Rightarrow G\iff
e\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\quad(\forall
a\in\textup{Ob}(\mathcal{A}));$

where $F,G\colon\mathcal{A}\longrightarrow\mathcal{B}$ are
$\mathcal{V}$-functors. We call $\Rightarrow$ the canonical ordering on
$[\mathcal{A},\mathcal{B}]_{0}$.

######  Proposition 2.22.

The relation $\Rightarrow$ defined on the set $[\mathcal{A},\mathcal{B}]_{0}$
is a preorder relation.

###### Proof.

[Reflexivity

] We wish to prove
$e\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),F(a)\big{)}$, but this is
an instance of the identity law for $\mathcal{B}$.

[Transitivity

] Suppose $F\Rightarrow G$ and $G\Rightarrow H$ for
$F,G,H\colon\mathcal{A}\longrightarrow\mathcal{B}$. Then an application of the
composition law for $\mathcal{B}$ yields

$\displaystyle e$ $\displaystyle=e\otimes e$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\otimes\textup{Hom}_{\mathcal{B}}\big{(}G(a),H(a)\big{)}$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),H(a)\big{)}.$

∎

Also, the relation $\Rightarrow$ is preserved under composition of
$\mathcal{V}$-functors, in the sense of the following proposition:

######  Proposition 2.23.

Let $F,G\colon\mathcal{A}\longrightarrow\mathcal{B}$ and
$H,K\colon\mathcal{B}\longrightarrow\mathcal{C}$ be $\mathcal{V}$-functors
such that $F\Rightarrow G$ and $H\Rightarrow K$ hold. Then, for the composite
$\mathcal{V}$-functors $H\circ F,K\circ
G\colon\mathcal{A}\longrightarrow\mathcal{C}$, $H\circ F\Rightarrow K\circ G$
holds.

###### Proof.

$\displaystyle e$ $\displaystyle=e\otimes e$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),F(a)\big{)}\otimes\textup{Hom}_{\mathcal{B}}\big{(}F(a),G(a)\big{)}$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{C}}\big{(}H\circ F(a),K\circ
F(a)\big{)}\otimes\textup{Hom}_{\mathcal{C}}\big{(}K\circ F(a),K\circ
G(a)\big{)}$ $\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{C}}\big{(}H\circ
F(a),K\circ G(a)\big{)}.$

∎

Below we see examples of $\mathcal{V}$-functors and relation $\Rightarrow$.

######  Example 2.24.

Let us take $\mathcal{V}=\textbf{2}$. We claim that 2-functors between
2-categories are just monotonic maps. Indeed, for 2-categories
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),\preceq_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\preceq_{\mathcal{B}})$, a 2-functor
$F\colon\mathcal{A}\longrightarrow\mathcal{B}$ is a map between the sets of
objects such that

(Increasing condition)

$(a\preceq_{\mathcal{A}}a^{\prime})\vdash\big{(}F(a)\preceq_{\mathcal{B}}F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$

holds. If $F$ is moreover fully faithful,

$(a\preceq_{\mathcal{A}}a^{\prime})=\big{(}F(a)\preceq_{\mathcal{B}}F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$

holds and $F$ is nothing but a usual embedding between preorders. The notion
of isomorphic 2-categories agrees with that of isomorphic preorders.

The relation $\Rightarrow$ turns out to be the usual ordering on the set of
monotonic maps:

$F\Rightarrow
G\iff\textup{true}\vdash\big{(}F(a)\preceq_{\mathcal{B}}G(a)\big{)}\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

######  Example 2.25.

For $\overline{\mathbb{K}}_{+}$-categories, one can think of
$\overline{\mathbb{K}}_{+}$-functors as nonexpansive maps. Let
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}$-categories. A $\overline{\mathbb{K}}_{+}$-functor
$F\colon\mathcal{A}\longrightarrow\mathcal{B}$ is a map between the sets of
points with the following property:

(Increasing condition)

$d_{\mathcal{A}}(a,a^{\prime})\geq
d_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$.

If $F$ is fully faithful,

$d_{\mathcal{A}}(a,a^{\prime})=d_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$

holds; i.e., in the terminology of metric spaces, $F$ is an isometry. The
notion of isomorphic $\overline{\mathbb{K}}_{+}$-categories specializes to
that of isometric metric spaces.

The relation $\Rightarrow$ is defined as follows:

$\displaystyle F\Rightarrow G$ $\displaystyle\iff 0\geq
d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$ $\displaystyle\iff
d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}=0\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

######  Example 2.26.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}$-categories. A $\overline{\mathbb{K}}$-functor
$F\colon\mathcal{A}\longrightarrow\mathcal{B}$ is a map between the sets of
points with the following property:

(Increasing condition)

$d_{\mathcal{A}}(a,a^{\prime})\geq
d_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$.

A fully faithful $\overline{\mathbb{K}}$-functor is an isometry (in an obvious
sense).

The relation $\Rightarrow$ is defined as follows:

$F\Rightarrow G\iff 0\geq d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

######  Example 2.27.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-categories. A
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-functor
$F\colon\mathcal{A}\longrightarrow\mathcal{B}$ is a map between the sets of
points with the following property:

(Increasing condition)

$d_{\mathcal{A}}(a,a^{\prime})\geq
d_{\mathcal{B}}\big{(}F(a),F(a^{\prime})\big{)}\quad(\forall
a,a^{\prime}\in\textup{Ob}(\mathcal{A}))$.

A fully faithful $\overline{\mathbb{K}}_{+}^{\text{Cart}}$-functor is an
isometry.

The relation $\Rightarrow$ is defined as follows:

$\displaystyle F\Rightarrow G$ $\displaystyle\iff 0\geq
d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$ $\displaystyle\iff
d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}=0\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

###  2.4 The Opposites of $\mathcal{V}$-Categories

In this section we present a way to construct new $\mathcal{V}$-categories out
of some already existing $\mathcal{V}$-categories.

######  Proposition 2.28.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,e)$ be an SM-P, and
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),$ $\textup{Hom}_{\mathcal{A}})$ be a
$\mathcal{V}$-category. Then there is a $\mathcal{V}$-category denoted by
$\mathcal{A}^{\textup{op}}=(\textup{Ob}(\mathcal{A}^{\textup{op}}),\textup{Hom}_{\mathcal{A}^{\textup{op}}})$,
where

  * •

$\textup{Ob}(\mathcal{A}^{\textup{op}})=\textup{Ob}(\mathcal{A})$, i.e., the
set of objects for $\mathcal{A}^{\textup{op}}$ is identical with that for
$\mathcal{A}$;

  * •

the hom-object function $\textup{Hom}_{\mathcal{A}^{\textup{op}}}$ is given as

$\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,b)=\textup{Hom}_{\mathcal{A}}(b,a).$

###### Proof.

[Composition law

] The claim is

$\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,b)\otimes\textup{Hom}_{\mathcal{A}^{\textup{op}}}(b,c)\sqsubseteq\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,c).$

It is proved as follows:

$\displaystyle\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,b)\otimes\textup{Hom}_{\mathcal{A}^{\textup{op}}}(b,c)$
$\displaystyle=\textup{Hom}_{\mathcal{A}}(b,a)\otimes\textup{Hom}_{\mathcal{A}}(c,b)$
$\displaystyle=\textup{Hom}_{\mathcal{A}}(c,b)\otimes\textup{Hom}_{\mathcal{A}}(b,a)$
$\displaystyle\sqsubseteq\textup{Hom}_{\mathcal{A}}(c,a)$
$\displaystyle=\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,c).$

[Identity law

] The claim is $e\sqsubseteq\textup{Hom}_{\mathcal{A}^{\textup{op}}}(a,a)$, an
obvious formula.

∎

######  Definition 2.29.

The category $\mathcal{A}^{\textup{op}}$ is called the opposite category of
$\mathcal{A}$.

######  Example 2.30.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),\preceq_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\preceq_{\mathcal{B}})$ be
2-categories. The opposite category
$\mathcal{A}^{\textup{op}}=(\textup{Ob}(\mathcal{A}^{\textup{op}}),\preceq_{\mathcal{A}^{\textup{op}}})$
is the opposite (or dual) of preorder:

  * •

$\textup{Ob}(\mathcal{A}^{\textup{op}})=\textup{Ob}(\mathcal{A})$;

  * •

$(a\preceq_{\mathcal{A}^{\textup{op}}}b)=(b\preceq_{\mathcal{A}}a)$.

######  Example 2.31.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}$-categories. The opposite category
$\mathcal{A^{\textup{op}}}=(\textup{Ob}(\mathcal{A^{\textup{op}}}),d_{\mathcal{A^{\textup{op}}}})$
is defined as follows:

  * •

$\textup{Ob}(\mathcal{A}^{\textup{op}})=\textup{Ob}(\mathcal{A})$;

  * •

$d_{\mathcal{A}^{\textup{op}}}(a,b)=d_{\mathcal{A}}(b,a)$.

Note that since a classical metric space has a symmetric distance function, it
is isometric to its opposite.

######  Example 2.32.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}$-categories. The opposite category
$\mathcal{A^{\textup{op}}}=(\textup{Ob}(\mathcal{A^{\textup{op}}}),d_{\mathcal{A^{\textup{op}}}})$
is defined as follows:

  * •

$\textup{Ob}(\mathcal{A}^{\textup{op}})=\textup{Ob}(\mathcal{A})$;

  * •

$d_{\mathcal{A}^{\textup{op}}}(a,b)=d_{\mathcal{A}}(b,a)$.

######  Example 2.33.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-categories. The opposite category
$\mathcal{A^{\textup{op}}}=(\textup{Ob}(\mathcal{A^{\textup{op}}}),d_{\mathcal{A^{\textup{op}}}})$
is defined as follows:

  * •

$\textup{Ob}(\mathcal{A}^{\textup{op}})=\textup{Ob}(\mathcal{A})$;

  * •

$d_{\mathcal{A}^{\textup{op}}}(a,b)=d_{\mathcal{A}}(b,a)$.

###  2.5 $\mathcal{V}$ as a $\mathcal{V}$-Category

We henceforth assume that the enriching category $\mathcal{V}$ is an SMC-P.
This assumption enables us to endow (the underlying set of) $\mathcal{V}_{0}$
with a canonical $\mathcal{V}$-category structure:

######  Proposition 2.34.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,[-,-],e)$ be an SMC-P. Then there is
a $\mathcal{V}$-category, also denoted by
$\mathcal{V}=(\mathcal{V}_{0},[-,-])$, where

  * •

$\textup{Ob}(\mathcal{V})$ is $\mathcal{V}_{0}$, the underlying set of the
poset $\mathcal{V}_{0}$;

  * •

the hom-object function is the internal-hom operation $[-,-]$.

###### Proof.

[Composition law

] The claim is $[x,y]\otimes[y,z]\sqsubseteq[x,z]$ for all
$x,y,z\in\mathcal{V}_{0}$, but this is equivalent to the composition law for
SC-Ps, which we know to hold:

$\mathord{[x,y]\otimes[y,z]}\ \sqsubseteq\ \mathord{}$$[x,z]$
$\mathord{[y,z]\otimes[x,y]}\ \sqsubseteq\ \mathord{}$$[x,z]$
$\mathord{[y,z]}\ \sqsubseteq\ \mathord{}$$[[x,y],[x,z]]$

Incidentally, this proof tree explains the duplication of the name
“composition law.”

[Identity law

] The claim is $e\sqsubseteq[z,z]$ for all $z\in\mathcal{V}_{0}$. Using the
commutative law for $[-,-]$, it suffices to show $z\sqsubseteq[e,z]$. But the
unit law for $[-,-]$ states $z=[e,z]$, so the proof is done.

∎

Now the name of the operation “internal-hom” is motivated. In a sense, it acts
like Hom, and takes values inside $\mathcal{V}$. As an aside, one can think of
the (external) hom of the poset $\mathcal{V}_{0}$ to be that takes two
elements $x,y$ of $\mathcal{V}_{0}$ and returns the truth value of
$x\sqsubseteq y$, which is a value in 2; thus (unless
$\mathcal{V}=\textbf{2}$) outside $\mathcal{V}$.

Let us take a look at some examples of such canonical
$\mathcal{V}$-categories.

######  Example 2.35.

$\textbf{2}_{0}=\\{\textup{true},\textup{false}\\}$ becomes a 2-category
(i.e., preordered set) in a canonical way. By the way, $\textbf{2}_{0}$ is
defined to be the underlying poset of 2, hence is already a preordered set. In
fact, the 2-category 2 is isomorphic to the underlying poset $\textbf{2}_{0}$
of the SMC-CL 2: one can see this by observing that the tables for $\vdash$
and for $\supset$ in Example 2.6 carry the same pattern.

######  Example 2.36.

The set $\mathbb{K}_{+}\cup\\{\infty\\}$ becomes a
$\overline{\mathbb{K}}_{+}$-category by the following distance function:

$d_{\overline{\mathbb{K}}_{+}}(x,y)=y\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}x.$

Therefore, if $x\leq y$ the distance to climb from $x$ to $y$ is the same as
their the difference, but if $x\geq y$, we descend and the corresponding
distance is $0$.

Note that the $\overline{\mathbb{K}}_{+}$-category $\overline{\mathbb{K}}_{+}$
is not an ordinary (discrete) metric space; among others, its distance
function is highly asymmetric.

######  Example 2.37.

The set $\mathbb{K}\cup\\{-\infty,\infty\\}$ becomes a
$\overline{\mathbb{K}}$-category by the following distance function:

$d_{\overline{\mathbb{K}}}(x,y)=y-x.$

Recall that in any $\overline{\mathbb{K}}$-category $\mathcal{A}$

$d_{\mathcal{A}}(a,a)=0\text{ or }-\infty$

holds. $\overline{\mathbb{K}}$ as a $\overline{\mathbb{K}}$-category indicates
that the distances between the same points may take both $0$ and $-\infty$ in
one $\overline{\mathbb{K}}$-category; in fact, if $s\in\mathbb{K}$,

$\displaystyle d_{\overline{\mathbb{K}}}(s,s)$ $\displaystyle=0\text{, and}$
$\displaystyle
d_{\overline{\mathbb{K}}}(-\infty,-\infty)=d_{\overline{\mathbb{K}}}(\infty,\infty)$
$\displaystyle=-\infty$

hold.

######  Example 2.38.

The set $\mathbb{K}_{+}\cup\\{\infty\\}$ becomes a
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-category by the following distance
function:

$\displaystyle d_{\overline{\mathbb{K}}_{+}^{\text{Cart}}}(x,y)$
$\displaystyle=x\supset y$ $\displaystyle=\begin{cases}0&(x\geq y)\\\
y&(x<y).\end{cases}$

###  2.6 Functor Categories and the Yoneda Embedding

Now the theory has reached the stage where we perform some limiting processes
within $\mathcal{V}_{0}$. Therefore, we finally assume that our enriching
category $\mathcal{V}$ is an SMC-CL. We begin this section with the definition
of a $\mathcal{V}$-category of all $\mathcal{V}$-functors with specified
domain and codomain, which is intuitively seen as an analog of a function
space in some sense.

######  Proposition 2.39.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,[-,-],e)$ be an SMC-CL, and
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),\textup{Hom}_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\textup{Hom}_{\mathcal{B}})$ be
$\mathcal{V}$-categories. Then there is a $\mathcal{V}$-category denoted by
${\textup{Fun}(\mathcal{A},\mathcal{B})}=([\mathcal{A},\mathcal{B}]_{0},\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})})$,
where

  * •

$\textup{Ob}({\textup{Fun}(\mathcal{A},\mathcal{B})})$ is
$[\mathcal{A},\mathcal{B}]_{0}$, the set of all $\mathcal{V}$-functors from
$\mathcal{A}$ to $\mathcal{B}$;

  * •

the hom-object function $\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}$
is given as

$\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)=\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{\textup{Hom}_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\right\\},$

where the infimum is taken in the complete lattice $\mathcal{V}_{0}$.

###### Proof.

[Composition law

] The claim is

$\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)\otimes\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(G,H)\sqsubseteq\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,H).$

For each $a\in\textup{Ob}(\mathcal{A})$, we have

$\displaystyle\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)\otimes\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(G,H)$
$\displaystyle\qquad=\bigwedge_{a^{\prime}\in\textup{Ob}(\mathcal{A})}\left\\{\textup{Hom}_{\mathcal{B}}\big{(}F(a^{\prime}),G(a^{\prime})\big{)}\right\\}\otimes\bigwedge_{a^{\prime}\in\textup{Ob}(\mathcal{A})}\left\\{\textup{Hom}_{\mathcal{B}}\big{(}G(a^{\prime}),H(a^{\prime})\big{)}\right\\}$
$\displaystyle\qquad\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\otimes\textup{Hom}_{\mathcal{B}}\big{(}G(a),H(a)\big{)}$
$\displaystyle\qquad\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),H(a)\big{)}.$

Taking the infimum with respect to $a$, we obtain the required result.

[Identity law

] The claim is
$e\sqsubseteq\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,F)$. The
identity law for $\mathcal{B}$ assures

$e\sqsubseteq\textup{Hom}_{\mathcal{B}}\big{(}F(a),F(a)\big{)},$

and the inequality is preserved after we take the infimum with respect to $a$.

∎

######  Definition 2.40.

The $\mathcal{V}$-category ${\textup{Fun}(\mathcal{A},\mathcal{B})}$ is called
a functor category, $\mathcal{A}$ its domain and $\mathcal{B}$ its codomain.

Given a $\mathcal{V}$-category $\mathcal{A}$, there are many functor
categories associated with $\mathcal{A}$. But two of them are of special
importance; they are called the presheaf category and the op-copresheaf
category of $\mathcal{A}$.

######  Definition 2.41.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,[-,-],e)$ be an SMC-CL, and
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),\textup{Hom}_{\mathcal{A}})$ be a
$\mathcal{V}$-category. A presheaf $P$ on $\mathcal{A}$ is a
$\mathcal{V}$-functor
$P\colon\mathcal{A}^{\textup{op}}\longrightarrow\mathcal{V}$, that is, a map
$\textup{Ob}(P)\colon\textup{Ob}(\mathcal{A})\longrightarrow\mathcal{V}_{0}$
satisfying

$\textup{Hom}_{\mathcal{A}}(a,b)\sqsubseteq[P(b),P(a)]$

for every $a,b\in\textup{Ob}(\mathcal{A})$. A copresheaf $Q$ on $\mathcal{A}$
is a $\mathcal{V}$-functor $Q\colon\mathcal{A}\longrightarrow\mathcal{V}$,
that is, a map
$\textup{Ob}(Q)\colon\textup{Ob}(\mathcal{A})\longrightarrow\mathcal{V}_{0}$
satisfying

$\textup{Hom}_{\mathcal{A}}(a,b)\sqsubseteq[Q(a),Q(b)]$

for every $a,b\in\textup{Ob}(\mathcal{A})$.

We call the functor category
${\textup{Fun}(\mathcal{A}^{\textup{op}},\mathcal{V})}$ the presheaf category
of $\mathcal{A}$, and the category
${\textup{Fun}(\mathcal{A},\mathcal{V})}^{\textup{op}}$ the op-copresheaf
category of $\mathcal{A}$.

Presheaf categories and op-copresheaf categories are important because the
original category embeds into them canonically. This is called the Yoneda
embedding theorem; but before we present and prove it, let us see some
examples of functor categories and presheaf or op-copresheaf categories:

######  Example 2.42.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),\preceq_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),\preceq_{\mathcal{B}})$ be
2-categories. The functor category
${\textup{Fun}(\mathcal{A},\mathcal{B})}=([\mathcal{A},\mathcal{B}]_{0},\preceq_{\textup{Fun}(\mathcal{A},\mathcal{B})})$
is given as follows, noting that $\bigwedge$ in $\textbf{2}_{0}$ corresponds
to “for all”:

  * •

$[\mathcal{A},\mathcal{B}]_{0}$ is the set of all monotonic maps from
$\mathcal{A}$ to $\mathcal{B}$;

  * •

$(F\preceq_{\textup{Fun}(\mathcal{A},\mathcal{B})}G)=\textup{true}\iff\big{(}F(a)\preceq_{\mathcal{B}}G(a)\big{)}=\textup{true}$
for all $a\in\textup{Ob}(\mathcal{A})$.

Thus, as a binary relation on the set $[\mathcal{A},\mathcal{B}]_{0}$,
$\preceq_{\textup{Fun}(\mathcal{A},\mathcal{B})}$ coincides with the canonical
ordering $\Rightarrow$.

A presheaf $P$ on $\mathcal{A}$ is a monotonic map
$P\colon\mathcal{A}^{\textup{op}}\longrightarrow\textbf{2}$, and by taking the
inverse image of $\\{\textup{true}\\}\subseteq\textbf{2}_{0}$, it can be seen
as a lower set of $\mathcal{A}$ (a lower set $S$ of a preorder $(A,\preceq)$
is a subset $S\subseteq A$ such that $a\in S$ and $b\preceq a$ imply $b\in
S$). In fact, presheaves on $\mathcal{A}$ correspond one-to-one with lower
sets of $\mathcal{A}$. Moreover, the ordering
$\preceq_{\textup{Fun}(\mathcal{A}^{\textup{op}},\textbf{2})}$ on the presheaf
category coincides with the inclusion ordering $\subseteq$ on the set of lower
sets: for all presheaves $P_{1},P_{2}$ on $\mathcal{A}$,

$P_{1}\preceq_{\textup{Fun}(\mathcal{A}^{\textup{op}},\textbf{2})}P_{2}\iff\textup{Ob}(P_{1})^{-1}\big{(}\\{\textup{true}\\}\big{)}\subseteq\textup{Ob}(P_{2})^{-1}\big{(}\\{\textup{true}\\}\big{)}$

hold.

A copresheaf $Q$ on $\mathcal{A}$ is a monotonic map
$Q\colon\mathcal{A}\longrightarrow\textbf{2}$. If we take the inverse image of
$\\{\textup{true}\\}\subseteq\textbf{2}_{0}$, we obtain an upper set of
$\mathcal{A}$. Copresheaves on $\mathcal{A}$ correspond one-to-one with upper
sets of $\mathcal{A}$; also, the ordering
$\preceq_{{\textup{Fun}(\mathcal{A},\textbf{2})}^{\textup{op}}}=\succeq_{\textup{Fun}(\mathcal{A},\textbf{2})}$
on the op-copresheaf category coincides with the opposite $\supseteq$ of the
inclusion ordering $\subseteq$ on the set of upper sets: for all copresheaves
$Q_{1},Q_{2}$ on $\mathcal{A}$,

$Q_{1}\preceq_{{\textup{Fun}(\mathcal{A},\textbf{2})}^{\textup{op}}}Q_{2}\iff\textup{Ob}(Q_{1})^{-1}\big{(}\\{\textup{true}\\}\big{)}\supseteq\textup{Ob}(Q_{2})^{-1}\big{(}\\{\textup{true}\\}\big{)}$

hold.

To summarize, the presheaf category
${\textup{Fun}(\mathcal{A}^{\textup{op}},\textbf{2})}$ of $\mathcal{A}$ can
naturally be seen as the preordered set (in fact, poset) of lower sets of
$\mathcal{A}$, and the op-copresheaf category
${\textup{Fun}(\mathcal{A},\textbf{2})}^{\textup{op}}$ as that of upper sets
of $\mathcal{A}$.

######  Example 2.43.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}$-categories. The functor category
${\textup{Fun}(\mathcal{A},\mathcal{B})}=([\mathcal{A},\mathcal{B}]_{0},d_{\textup{Fun}(\mathcal{A},\mathcal{B})})$
is given as follows, noting that $\bigwedge$ in
$\mathbb{K}_{+}\cup\\{\infty\\}$ corresponds to (the usual) $\sup$:

  * •

$[\mathcal{A},\mathcal{B}]_{0}$ is the set of all nonexpansive maps from
$\mathcal{A}$ to $\mathcal{B}$;

  * •

$d_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)=\sup_{a\in\textup{Ob}(\mathcal{A})}\left\\{d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\right\\}$.

Therefore, in the current setting, the natural distance on a function space
turns out to be the sup-distance. Since we adjoined $\infty$ and turned
$\mathbb{K}_{+}$ into a complete lattice, we can get rid of additional
assumptions such as the compactness of $\mathcal{A}$ or the boundedness of
$\mathcal{B}$, the usual requirements when performing the sup-distance
construction in the theory of classical metric spaces.

A presheaf $P$ on $\mathcal{A}$ is a nonexpansive map
$P\colon\mathcal{A}^{\textup{op}}\longrightarrow\overline{\mathbb{K}}_{+}$,
namely, a map $\textup{Ob}(P)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}_{+}\cup\\{\infty\\}$ satisfying

$d_{\mathcal{A}}(a,b)\geq P(a)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(b)$

for all $a,b\in\textup{Ob}(\mathcal{A})$, and can be seen as a scalar-valued
function on $\mathcal{A}$. The distance between two presheaves $P_{1}$ and
$P_{2}$ is given by

$d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+})}(P_{1},P_{2})=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{P_{2}(a)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P_{1}(a)\\}.$

The canonical ordering $\Rightarrow$ is defined as

$\displaystyle P_{1}\Rightarrow P_{2}$ $\displaystyle\iff 0\geq
P_{2}(a)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P_{1}(a)\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$ $\displaystyle\iff
P_{2}(a)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P_{1}(a)=0\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$ $\displaystyle\iff
d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+})}(P_{1},P_{2})=0$
$\displaystyle\iff P_{1}(a)\geq P_{2}(a)\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

A copresheaf $Q$ on $\mathcal{A}$ is a nonexpansive map
$Q\colon\mathcal{A}\longrightarrow\overline{\mathbb{K}}_{+}$, namely, a map
$\textup{Ob}(Q)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}_{+}\cup\\{\infty\\}$ satisfying

$d_{\mathcal{A}}(a,b)\geq Q(b)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}Q(a)$

for all $a,b\in\textup{Ob}(\mathcal{A})$, and forms another natural class of
scalar-valued functions on $\mathcal{A}$. The distance between two
copresheaves $Q_{1}$ and $Q_{2}$ in the op-copresheaf category
${\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+})}^{\textup{op}}$ is given
by

$d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+})}^{\textup{op}}}(Q_{1},Q_{2})=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{Q_{1}(a)\mathbin{\text{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}Q_{2}(a)\\}.$

As $\overline{\mathbb{K}}_{+}$-functors, the canonical ordering $\Rightarrow$
on copresheaves is determined by conditions similar to that for presheaves.

######  Example 2.44.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}$-categories. The functor category
${\textup{Fun}(\mathcal{A},\mathcal{B})}=([\mathcal{A},\mathcal{B}]_{0},d_{\textup{Fun}(\mathcal{A},\mathcal{B})})$
is given as follows:

  * •

$[\mathcal{A},\mathcal{B}]_{0}$ is the set of all nonexpansive maps from
$\mathcal{A}$ to $\mathcal{B}$;

  * •

$d_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)=\sup_{a\in\textup{Ob}(\mathcal{A})}\left\\{d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\right\\}$.

A presheaf $P$ on $\mathcal{A}$ is a nonexpansive map
$P\colon\mathcal{A}^{\textup{op}}\longrightarrow\overline{\mathbb{K}}$,
namely, a map $\textup{Ob}(P)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}\cup\\{-\infty,\infty\\}$ satisfying

$d_{\mathcal{A}}(a,b)\geq P(a)-P(b)$

for all $a,b\in\textup{Ob}(\mathcal{A})$. The distance between two presheaves
$P_{1}$ and $P_{2}$ is given by

$d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}})}(P_{1},P_{2})=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{P_{2}(a)-P_{1}(a)\\}.$

The canonical ordering $\Rightarrow$ is defined as

$\displaystyle P_{1}\Rightarrow P_{2}$ $\displaystyle\iff 0\geq
P_{2}(a)-P_{1}(a)\quad(\forall a\in\textup{Ob}(\mathcal{A}))$
$\displaystyle\iff
d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}})}(P_{1},P_{2})\leq
0$ $\displaystyle\iff P_{1}(a)\geq P_{2}(a)\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

A copresheaf $Q$ on $\mathcal{A}$ is a nonexpansive map
$Q\colon\mathcal{A}\longrightarrow\overline{\mathbb{K}}$, namely, a map
$\textup{Ob}(Q)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}\cup\\{-\infty,\infty\\}$ satisfying

$d_{\mathcal{A}}(a,b)\geq Q(b)-Q(a)$

for all $a,b\in\textup{Ob}(\mathcal{A})$. The distance between two
copresheaves $Q_{1}$ and $Q_{2}$ in the op-copresheaf category
${\textup{Fun}(\mathcal{A},\overline{\mathbb{K}})}^{\textup{op}}$ is given by

$d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}})}^{\textup{op}}}(Q_{1},Q_{2})=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{Q_{1}(a)-Q_{2}(a)\\}.$

######  Example 2.45.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ and
$\mathcal{B}=(\textup{Ob}(\mathcal{B}),d_{\mathcal{B}})$ be
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-categories. The functor category
${\textup{Fun}(\mathcal{A},\mathcal{B})}=([\mathcal{A},\mathcal{B}]_{0},d_{\textup{Fun}(\mathcal{A},\mathcal{B})})$
is given as follows:

  * •

$[\mathcal{A},\mathcal{B}]_{0}$ is the set of all nonexpansive maps from
$\mathcal{A}$ to $\mathcal{B}$;

  * •

$d_{\textup{Fun}(\mathcal{A},\mathcal{B})}(F,G)=\sup_{a\in\textup{Ob}(\mathcal{A})}\left\\{d_{\mathcal{B}}\big{(}F(a),G(a)\big{)}\right\\}$.

A presheaf $P$ on $\mathcal{A}$ is a nonexpansive map
$P\colon\mathcal{A}^{\textup{op}}\longrightarrow\overline{\mathbb{K}}_{+}^{\text{Cart}}$,
namely, a map $\textup{Ob}(P)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}_{+}\cup\\{\infty\\}$ satisfying

$\displaystyle d_{\mathcal{A}}(a,b)$ $\displaystyle\geq P(b)\supset P(a)$
$\displaystyle=\begin{cases}0&(P(b)\geq P(a))\\\ P(a)&(P(b)<P(a)),\end{cases}$

or equivalently,

$P(b)<P(a)\implies d_{\mathcal{A}}(a,b)\geq P(a)$

for all $a,b\in\textup{Ob}(\mathcal{A})$. The distance between two presheaves
$P_{1}$ and $P_{2}$ is given by

$\displaystyle
d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+}^{\text{Cart}})}(P_{1},P_{2})$
$\displaystyle=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{P_{1}(a)\supset
P_{2}(a)\\}$
$\displaystyle=\sup_{\begin{subarray}{c}a\in\textup{Ob}(\mathcal{A})\\\
P_{1}(a)<P_{2}(a)\end{subarray}}\\{P_{2}(a)\\}.$

The canonical ordering $\Rightarrow$ is defined as

$\displaystyle P_{1}\Rightarrow P_{2}$ $\displaystyle\iff 0\geq
P_{1}(a)\supset P_{2}(a)\quad(\forall a\in\textup{Ob}(\mathcal{A}))$
$\displaystyle\iff P_{1}(a)\supset P_{2}(a)=0\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$ $\displaystyle\iff
d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+}^{\text{Cart}})}(P_{1},P_{2})=0$
$\displaystyle\iff P_{1}(a)\geq P_{2}(a)\quad(\forall
a\in\textup{Ob}(\mathcal{A})).$

A copresheaf $Q$ on $\mathcal{A}$ is a nonexpansive map
$Q\colon\mathcal{A}\longrightarrow\overline{\mathbb{K}}_{+}^{\text{Cart}}$,
namely, a map $\textup{Ob}(Q)\colon$
$\textup{Ob}(A)\longrightarrow\mathbb{K}_{+}\cup\\{\infty\\}$ satisfying

$\displaystyle d_{\mathcal{A}}(a,b)$ $\displaystyle\geq Q(a)\supset Q(b)$
$\displaystyle=\begin{cases}0&(Q(a)\geq Q(b))\\\ Q(b)&(Q(a)<Q(b)),\end{cases}$

or equivalently,

$Q(a)<Q(b)\implies d_{\mathcal{A}}(a,b)\geq Q(b)$

for all $a,b\in\textup{Ob}(\mathcal{A})$. The distance between two
copresheaves $Q_{1}$ and $Q_{2}$ in the op-copresheaf category
${\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+}^{\text{Cart}})}^{\textup{op}}$
is given by

$\displaystyle
d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+}^{\text{Cart}})}^{\textup{op}}}(Q_{1},Q_{2})$
$\displaystyle=\sup_{a\in\textup{Ob}(\mathcal{A})}\\{Q_{2}(a)\supset
Q_{1}(a)\\}$
$\displaystyle=\sup_{\begin{subarray}{c}a\in\textup{Ob}(\mathcal{A})\\\
Q_{2}(a)<Q_{1}(a)\end{subarray}}\\{Q_{1}(a)\\}.$

Now we present the Yoneda embedding theorem:

######  Theorem 2.46.

Let $\mathcal{V}=(\mathcal{V}_{0},\otimes,[-,-],e)$ be an SMC-CL, and
$\mathcal{A}=(\textup{Ob}(\mathcal{A}),\textup{Hom}_{\mathcal{A}})$ be a
$\mathcal{V}$-category. Then there are fully faithful $\mathcal{V}$-functors
$Y$ and $\overline{Y}$, defined as follows:

$\displaystyle
Y\colon\mathcal{A}\longrightarrow{\textup{Fun}(\mathcal{A}^{\textup{op}},\mathcal{V})},\qquad$
$\displaystyle\textup{Ob}(Y(b))=\lambda
a\in\textup{Ob}(\mathcal{A}^{\textup{op}}).\,\textup{Hom}_{\mathcal{A}}(a,b)\quad(\forall
b\in\textup{Ob}(\mathcal{A}));$
$\displaystyle\overline{Y}\colon\mathcal{A}\longrightarrow{\textup{Fun}(\mathcal{A},\mathcal{V})}^{\textup{op}},\qquad$
$\displaystyle\textup{Ob}(\overline{Y}(a))=\lambda
b\in\textup{Ob}(\mathcal{A}).\,\textup{Hom}_{\mathcal{A}}(a,b)\quad(\forall
a\in\textup{Ob}(\mathcal{A}^{\textup{op}})).$

###### Proof.

We first show that the values $Y(b)$ and $\overline{Y}(a)$ are indeed a
presheaf or a copresheaf, respectively.

[$Y(b)$ is a presheaf on $\mathcal{A}\\!\\!\\!$

] The claim is

$\displaystyle\textup{Hom}_{\mathcal{A}}(a,a^{\prime})$
$\displaystyle\sqsubseteq[Y(b)(a^{\prime}),Y(b)(a)]$
$\displaystyle=[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)],$

and this is equivalent to an instance of the composition law for
$\mathcal{A}$:

$\mathord{\textup{Hom}_{\mathcal{A}}(a,a^{\prime})}\ \sqsubseteq\
\mathord{}$$[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]$
$\mathord{\textup{Hom}_{\mathcal{A}}(a,a^{\prime})\otimes\textup{Hom}_{\mathcal{A}}(a^{\prime},b)}\
\sqsubseteq\ \mathord{}$$\textup{Hom}_{\mathcal{A}}(a,b)$

[$\overline{Y}(a)$ is a copresheaf on $\mathcal{A}\\!\\!\\!$

] The claim is

$\displaystyle\textup{Hom}_{\mathcal{A}}(b,b^{\prime})$
$\displaystyle\sqsubseteq[\overline{Y}(a)(b),\overline{Y}(a)(b^{\prime})]$
$\displaystyle=[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})],$

and this is equivalent to an instance of the composition law for
$\mathcal{A}$:

$\mathord{\textup{Hom}_{\mathcal{A}}(b,b^{\prime})}\ \sqsubseteq\
\mathord{}$$[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]$
$\mathord{\textup{Hom}_{\mathcal{A}}(b,b^{\prime})\otimes\textup{Hom}_{\mathcal{A}}(a,b)}\
\sqsubseteq\ \mathord{}$$\textup{Hom}_{\mathcal{A}}(a,b^{\prime})$
$\mathord{\textup{Hom}_{\mathcal{A}}(a,b)\otimes\textup{Hom}_{\mathcal{A}}(b,b^{\prime})}\
\sqsubseteq\ \mathord{}$$\textup{Hom}_{\mathcal{A}}(a,b^{\prime})$

Next we show that $Y$ and $\overline{Y}$ are fully faithful
$\mathcal{V}$-functors:

[$Y$ is a fully faithful $\mathcal{V}$-functor

] The claim is

$\displaystyle\textup{Hom}_{\mathcal{A}}(b,b^{\prime})$
$\displaystyle=\textup{Hom}_{\textup{Fun}(\mathcal{A}^{\textup{op}},\mathcal{V})}(Y(b),Y(b^{\prime}))$
$\displaystyle=\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{[Y(b)(a),Y(b^{\prime})(a)]\right\\}$
$\displaystyle=\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]\right\\}.$

We prove this by showing the two inequalities:

[$\textup{Hom}_{\mathcal{A}}(b,b^{\prime})\sqsubseteq\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]\right\\}$

] It is equivalent to

$\textup{Hom}_{\mathcal{A}}(b,b^{\prime})\sqsubseteq[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]\quad(\forall
a\in\textup{Ob}(\mathcal{A}))$

and its proof for some fixed $a\in\textup{Ob}(\mathcal{A})$ is already given
above when we prove that $\overline{Y}(a)$ is a copresheaf on $\mathcal{A}$.

[$\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]\right\\}\sqsubseteq\textup{Hom}_{\mathcal{A}}(b,b^{\prime})$

] First note that

$\bigwedge_{a\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a,b),\textup{Hom}_{\mathcal{A}}(a,b^{\prime})]\right\\}\sqsubseteq[\textup{Hom}_{\mathcal{A}}(b,b),\textup{Hom}_{\mathcal{A}}(b,b^{\prime})]$

holds. Using an instance of the identity law for $\mathcal{A}$,
$e\sqsubseteq\textup{Hom}_{\mathcal{A}}(b,b)$, we have the following:

$\displaystyle[\textup{Hom}_{\mathcal{A}}(b,b),\textup{Hom}_{\mathcal{A}}(b,b^{\prime})]$
$\displaystyle\sqsubseteq[e,\textup{Hom}_{\mathcal{A}}(b,b^{\prime})]$
$\displaystyle=\textup{Hom}_{\mathcal{A}}(b,b^{\prime}).$

Therefore the claim follows.

[$\overline{Y}$ is a fully faithful $\mathcal{V}$-functor

] The claim is

$\displaystyle\textup{Hom}_{\mathcal{A}}(a,a^{\prime})$
$\displaystyle=\textup{Hom}_{\textup{Fun}(\mathcal{A},\mathcal{V})}(\overline{Y}(a^{\prime}),\overline{Y}(a))$
$\displaystyle=\bigwedge_{b\in\textup{Ob}(\mathcal{A})}\left\\{[\overline{Y}(a^{\prime})(b),\overline{Y}(a)(b)]\right\\}$
$\displaystyle=\bigwedge_{b\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]\right\\}.$

We prove this by showing the two inequalities:

[$\textup{Hom}_{\mathcal{A}}(a,a^{\prime})\sqsubseteq\bigwedge_{b\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]\right\\}$

] It is equivalent to

$\textup{Hom}_{\mathcal{A}}(a,a^{\prime})\sqsubseteq[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]\quad(\forall
b\in\textup{Ob}(\mathcal{A}))$

and its proof for some fixed $b\in\textup{Ob}(\mathcal{A})$ is already given
above when we prove that $Y(b)$ is a presheaf on $\mathcal{A}$.

[$\bigwedge_{b\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]\right\\}\sqsubseteq\textup{Hom}_{\mathcal{A}}(a,a^{\prime})$

] First note that

$\bigwedge_{b\in\textup{Ob}(\mathcal{A})}\left\\{[\textup{Hom}_{\mathcal{A}}(a^{\prime},b),\textup{Hom}_{\mathcal{A}}(a,b)]\right\\}\sqsubseteq[\textup{Hom}_{\mathcal{A}}(a^{\prime},a^{\prime}),\textup{Hom}_{\mathcal{A}}(a,a^{\prime})]$

holds. Using an instance of the identity law for $\mathcal{A}$,
$e\sqsubseteq\textup{Hom}_{\mathcal{A}}(a^{\prime},a^{\prime})$, we have the
following:

$\displaystyle[\textup{Hom}_{\mathcal{A}}(a^{\prime},a^{\prime}),\textup{Hom}_{\mathcal{A}}(a,a^{\prime})]$
$\displaystyle\sqsubseteq[e,\textup{Hom}_{\mathcal{A}}(a,a^{\prime})]$
$\displaystyle=\textup{Hom}_{\mathcal{A}}(a,a^{\prime}).$

Therefore the claim follows.

∎

######  Definition 2.47.

The $\mathcal{V}$-functor $Y$ is called the Yoneda embedding, and
$\overline{Y}$ the co-Yoneda embedding.

We see some examples of the (co-)Yoneda embeddings.

######  Example 2.48.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),\preceq_{\mathcal{A}})$ be a
2-category. Under the identification of presheaves on $\mathcal{A}$ and lower
sets of $\mathcal{A}$, the Yoneda embedding turns out to be the well-known
principal ideal operation $\mathord{\downarrow}(-)$:

$\displaystyle\textup{Ob}(Y(b))^{-1}\big{(}\\{\textup{true}\\}\big{)}$
$\displaystyle=\mathord{\downarrow}(b)$
$\displaystyle=\\{a\in\textup{Ob}(\mathcal{A})\mid
a\preceq_{\mathcal{A}}b\\}.$

Dually, the co-Yoneda embedding corresponds to the principal filter operation
$\mathord{\uparrow}(-)$:

$\displaystyle\textup{Ob}(\overline{Y}(a))^{-1}\big{(}\\{\textup{true}\\}\big{)}$
$\displaystyle=\mathord{\uparrow}(a)$
$\displaystyle=\\{b\in\textup{Ob}(\mathcal{A})\mid
a\preceq_{\mathcal{A}}b\\}.$

Therefore, the Yoneda embedding theorem specializes to the statement that
every preordered set embeds into the poset of its lower subsets (ordered by
the inclusion) and the poset of its upper subsets (ordered by the opposite of
the inclusion):

$\displaystyle b\preceq_{\mathcal{A}}b^{\prime}$
$\displaystyle\iff\mathord{\downarrow}(b)\subseteq\mathord{\downarrow}(b^{\prime});$
$\displaystyle a\preceq_{\mathcal{A}}a^{\prime}$
$\displaystyle\iff\mathord{\uparrow}(a)\supseteq\mathord{\uparrow}(a^{\prime}).$

But note that such embeddings are not injective unless the preorder is an
order.

######  Example 2.49.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ be a
$\overline{\mathbb{K}}_{+}$-category. The Yoneda embedding $Y$ sends a point
$b$ of $\mathcal{A}$ to the “distance to $b$” function:

$\textup{Ob}(Y(b))=\lambda
a\in\textup{Ob}(\mathcal{A}^{\textup{op}}).\,d_{\mathcal{A}}(a,b).$

The co-Yoneda embedding $\overline{Y}$ sends a point $a$ of $\mathcal{A}$ to
the “distance from $a$” function:

$\textup{Ob}(\overline{Y}(a))=\lambda
b\in\textup{Ob}(\mathcal{A}).\,d_{\mathcal{A}}(a,b).$

The Yoneda embedding theorem reads:

$\displaystyle d_{\mathcal{A}}(b,b^{\prime})$
$\displaystyle=d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+})}(Y(b),Y(b^{\prime}));$
$\displaystyle d_{\mathcal{A}}(a,a^{\prime})$
$\displaystyle=d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+})}^{\textup{op}}}(\overline{Y}(a),\overline{Y}(a^{\prime})).$

If $\mathcal{A}$ is a classical metric space, then by symmetry $Y$ and
$\overline{Y}$ coincide and turn out to be the so-called Fréchet embedding.

######  Example 2.50.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ be a
$\overline{\mathbb{K}}$-category. We have

$\textup{Ob}(Y(b))=\lambda
a\in\textup{Ob}(\mathcal{A}^{\textup{op}}).\,d_{\mathcal{A}}(a,b),\quad\textup{Ob}(\overline{Y}(a))=\lambda
b\in\textup{Ob}(\mathcal{A}).\,d_{\mathcal{A}}(a,b)$

and

$d_{\mathcal{A}}(b,b^{\prime})=d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}})}(Y(b),Y(b^{\prime})),\quad
d_{\mathcal{A}}(a,a^{\prime})=d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}})}^{\textup{op}}}(\overline{Y}(a),\overline{Y}(a^{\prime})).$

######  Example 2.51.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ be a
$\overline{\mathbb{K}}_{+}^{\text{Cart}}$-category. We have

$\textup{Ob}(Y(b))=\lambda
a\in\textup{Ob}(\mathcal{A}^{\textup{op}}).\,d_{\mathcal{A}}(a,b),\quad\textup{Ob}(\overline{Y}(a))=\lambda
b\in\textup{Ob}(\mathcal{A}).\,d_{\mathcal{A}}(a,b)$

and

$d_{\mathcal{A}}(b,b^{\prime})=d_{\textup{Fun}(\mathcal{A}^{\textup{op}},\overline{\mathbb{K}}_{+}^{\text{Cart}})}(Y(b),Y(b^{\prime})),\quad
d_{\mathcal{A}}(a,a^{\prime})=d_{{\textup{Fun}(\mathcal{A},\overline{\mathbb{K}}_{+}^{\text{Cart}})}^{\textup{op}}}(\overline{Y}(a),\overline{Y}(a^{\prime})).$

##  Chapter 3 $\overline{\mathbb{K}}$-Categories and
$\overline{\mathbb{K}}$-Extended L-Convex Sets

We are now ready to show the main result, a correspondence between
$\overline{\mathbb{K}}$-categories and $\overline{\mathbb{K}}$-extended
L-convex sets, which are variants of L-convex sets or L-convex polyhedra of
discrete convex analysis. A chief difference between
$\overline{\mathbb{K}}$-extended L-convex sets and L-convex sets (corresponds
to the case $\mathbb{K}=\mathbb{Z}$) or L-convex polyhedra
($\mathbb{K}=\mathbb{R}$) is that the former have the ambient sets of the form
$\overline{\mathbb{K}}^{V}$ whereas the latter two $\mathbb{Z}^{V}$ or
$\mathbb{R}^{V}$ ($V$ is some set). In this chapter, we introduce
$\overline{\mathbb{K}}$-extended L-convex sets and homomorphisms between them,
and exploit these to show a duality theorem between
$\overline{\mathbb{K}}$-categories and $\overline{\mathbb{K}}$-extended
L-convex sets. The theorem rests on the fact that the set
$\mathbb{K}\cup\\{-\infty,\infty\\}$ can canonically be seen both as a
$\overline{\mathbb{K}}$-category and as a $\overline{\mathbb{K}}$-extended
L-convex set, and has two faces. Using this fact, both directions of the
constructions in the duality (namely, from $\overline{\mathbb{K}}$-categories
to $\overline{\mathbb{K}}$-extended L-convex sets, and conversely) are
realized as that of forming the function spaces with codomain
$\overline{\mathbb{K}}$ (either as a $\overline{\mathbb{K}}$-category or as a
$\overline{\mathbb{K}}$-extended L-convex set). As a byproduct, we remark that
(the underlying sets of) $\overline{\mathbb{K}}$-extended L-convex sets, seen
as $\overline{\mathbb{K}}$-categories with distance functions the restrictions
of that for $\overline{\mathbb{K}}^{V}$ with sup-distances, are nothing but
$\overline{\mathbb{K}}$-presheaf categories. This result gives rise to a claim
that (variants of) L-convex sets arise canonically in the enriched-categorical
setting, suggesting the possibility of a categorical approach to discrete
convex analysis.

###  3.1 $\overline{\mathbb{K}}$-Extended L-Convex Sets

We begin with the definition of $\overline{\mathbb{K}}$-extended L-convex sets
(recall that $\mathbb{K}$ denotes either $\mathbb{Z}$ or $\mathbb{R}$).

######  Definition 3.1.

A $\overline{\mathbb{K}}$-extended L-convex set $\mathbf{D}$ is a pair
$({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ where

  * •

${\textup{Ind}(\mathbf{D})}$ is a set called the index set of $\mathbf{D}$;

  * •

$\mathbf{D}_{0}$ is a subset of
$\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ called the underlying set
of $\mathbf{D}$;

such that the following axioms hold:

(Order completeness)

$\bigvee_{p\in S}p,\ \bigwedge_{p\in S}p\in\mathbf{D}_{0}\quad(\forall
S\subseteq\mathbf{D}_{0})$;

(Weight completeness)

$p+\alpha\cdot\textbf{1}\in\mathbf{D}_{0}\quad(\forall p\in\mathbf{D}_{0},\
\forall\alpha\in\mathbb{K}\cup\\{-\infty,\infty\\})$.

Let us clarify the notations.
$\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ denotes the set of all maps
from the set ${\textup{Ind}(\mathbf{D})}$ to
$\mathbb{K}\cup\\{-\infty,\infty\\}$. The supremum $\bigvee$ and the infimum
$\bigwedge$ in $\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ are taken
coordinate-wise:

$\big{(}\bigvee_{p\in S}p\big{)}(v)=\bigvee_{p\in
S}\big{(}p(v)\big{)},\quad\big{(}\bigwedge_{p\in S}p\big{)}(v)=\bigwedge_{p\in
S}\big{(}p(v)\big{)}\quad(\forall v\in{\textup{Ind}(\mathbf{D})}),$

where the supremum and the infimum in the right hand sides are taken in the
set $\mathbb{K}\cup\\{-\infty,\infty\\}$ using the order $\geq$ (recall that
since $\geq$ is the opposite of the usual ordering $\leq$, the supremum
$\bigvee$ here corresponds to the usual $\inf$, and the infimum $\bigwedge$
the usual $\sup$; we continue to use our previous notational conventions
$\bigvee=\inf$, $\bigwedge=\sup$). $\alpha\cdot\textbf{1}$ represents an
element of $\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ which is the
“all-$\alpha$ vector” or the constant map with the unique value $\alpha$:

$(\alpha\cdot\textbf{1})(v)=\alpha\quad(\forall
v\in{\textup{Ind}(\mathbf{D})}).$

The operation $+$ on $\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ is
defined coordinate-wise using the extended addition of Example 2.9:

$(p+q)(v)=p(v)+q(v)\quad(\forall v\in{\textup{Ind}(\mathbf{D})}).$

One can define the operation $-$ on
$\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$ in the similar way. The
name “weight completeness” has its origin in the fact that together with the
order completeness, it assures the existence of all weighted limits and
weighted colimits, which are fundamental notions of enriched category theory.

First we check that the $-$ version of the weight completeness condition comes
for free.

######  Proposition 3.2.

Let $\mathbf{D}=({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ be a
$\overline{\mathbb{K}}$-extended L-convex set. Then the following hold:

$\displaystyle p-\alpha\cdot\mathbf{1}\in\mathbf{D}_{0}\quad(\forall
p\in\mathbf{D}_{0},\ \forall\alpha\in\mathbb{K}\cup\\{-\infty,\infty\\}).$
(3.1)

###### Proof.

When $\alpha\in\mathbb{K}$, then clearly

$p-\alpha\cdot\mathbf{1}=p+(-\alpha)\cdot\mathbf{1}.$

If $\alpha=-\infty$, then

$(p-(-\infty)\cdot\mathbf{1})(v)=\begin{cases}-\infty&(p(v)=-\infty)\\\
\infty&(\text{otherwise})\end{cases}\quad(\forall
v\in{\textup{Ind}(\mathbf{D})}),$

and this is realized as

$\bigwedge_{\alpha\in\mathbb{K}}(p+\alpha\cdot\mathbf{1})=\sup_{\alpha\in\mathbb{K}}\\{p+\alpha\cdot\mathbf{1}\\}.$

Finally, if $\alpha=\infty$, then

$(p-\infty\cdot\mathbf{1})(v)=-\infty\quad(\forall
v\in{\textup{Ind}(\mathbf{D})})$

and this is written as

$\bigwedge\emptyset=\sup\emptyset.$

Hence, in either case $(p-\alpha\cdot\mathbf{1})\in\mathbf{D}_{0}$ by the
order and weight completeness of $\mathbf{D}$. ∎

In what follows, we refer to the condition (3.1) also as the weight
completeness of $\mathbf{D}$. The definition of
$\overline{\mathbb{K}}$-extended L-convex sets slightly differs from that of
L-convex sets (when $\mathbb{K}=\mathbb{Z}$) or L-convex polyhedra (when
$\mathbb{K}=\mathbb{R}$). For comparison, below we present the definitions of
them.

######  Definition 3.3 ([8]).

Let $V$ be a finite set. A subset $D\subseteq\mathbb{Z}^{V}$ is an L-convex
set if the following hold:

(Nonemptiness)

$D\neq\emptyset$;

(SBS$[\mathbb{Z}]$)

$p\land q,\ p\lor q\in D\quad(\forall p,q\in D)$;

(TRS$[\mathbb{Z}]$)

$p+\alpha\cdot\textbf{1}\in D\quad(\forall p\in D,\
\forall\alpha\in\mathbb{Z})$.

######  Definition 3.4 ([8]).

Let $V$ be a finite set. A subset $D\subseteq\mathbb{R}^{V}$ is an L-convex
polyhedron if the following hold:

(Nonemptiness)

$D\neq\emptyset$;

(Closedness)

$D$ is a closed subset of $\mathbb{R}^{V}$;

(SBS$[\mathbb{R}]$)

$p\land q,\ p\lor q\in D\quad(\forall p,q\in D)$;

(TRS$[\mathbb{R}]$)

$p+\alpha\cdot\textbf{1}\in D\quad(\forall p\in D,\
\forall\alpha\in\mathbb{R})$.

We note that the order completeness condition entails the nonemptiness
condition; just take $S=\emptyset$. Since we impose on
$\overline{\mathbb{K}}$-extended L-convex sets the order completeness
condition stronger than its binary versions (SBS[$\mathbb{Z}$] or
SBS[$\mathbb{R}$]), the index sets are no longer limited to be finite.
However, we adopt the order completeness condition not just because we can
treat infinite index sets; for our purpose, the binary versions do not work
even when ${\textup{Ind}(\mathbf{D})}$ is finite.

$v$$w$ (a) The whole set $\overline{\mathbb{K}}^{2}$

$v$$w$ (b) A half plane

$v$$w$ (c) A band

Figure 3.1: The underlying sets of $\overline{\mathbb{K}}$-extended L-convex
sets

Let us illustrate the point by observing examples of
$\overline{\mathbb{K}}$-extended L-convex sets and a non-example we wish to
exclude. Fig. 3.1 presents examples of (the underlying sets of) typical
$\overline{\mathbb{K}}$-extended L-convex sets with two-element index sets. We
first explain the intended meaning of the figures using Fig. 3.1(c); let
$\mathbf{D}$ be the $\overline{\mathbb{K}}$-extended L-convex set drawn on it.
Since the ambient set of $\mathbf{D}_{0}$ is
$\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}\cong\overline{\mathbb{K}}^{2}$,
there are points whose coordinates include $-\infty$ or $\infty$; the outer
frame of the figure represents these points. The subset $\mathbf{D}_{0}$ is
represented by the gray region (when $\mathbb{K}=\mathbb{Z}$, the region
should be interpreted as a set of lattice points). The boundaries of
$\mathbf{D}_{0}$ is two “lines of gradient 1”; although they are straight,
they pass the points $(-\infty,-\infty)$ (at the lower left) and
$(\infty,\infty)$ (the upper right), and to indicate this fact we bend the
lines in the margin, where they are also dashed. We place two black dots at
the lower left and the upper right to indicate
$(-\infty,-\infty)\in\mathbf{D}_{0}$ and $(\infty,\infty)\in\mathbf{D}_{0}$,
respectively. In Fig. 3.1(b), parts of the frame, namely the bottom and right
lines, are drawn boldly. This represents that points of the forms respectively
$(s,-\infty)$ and $(\infty,t)$ ($s,t\in\mathbb{K}$), are in the underlying
set. Later we show that $\overline{\mathbb{K}}$-extended L-convex sets with
two-element index sets correspond to $\overline{\mathbb{K}}$-categories with
two points, and as an illustration present the correspondence at the level of
shapes, with a more exhaustive enumeration.

An example of subsets of $\overline{\mathbb{K}}^{2}$ which we want to exclude
from the underlying sets of $\overline{\mathbb{K}}$-extended L-convex sets
with two-element index sets is drawn in Fig. 3.2. This set satisfies the
weight completeness condition and the binary version of the order completeness
condition. These weaker conditions fail to assure e.g., if
$(0,0),(1,0),(2,0),\dots$ are in the set then so is $(\infty,0)$, and for such
entities we cannot establish a nice connection with
$\overline{\mathbb{K}}$-categories.

$v$$w$ Figure 3.2: Fig. 3.1(b) without the bottom and right lines

Another, more concrete example of $\overline{\mathbb{K}}$-extended L-convex
sets is the following. It will play a crucial role in the formulation of the
duality theorems.

######  Example 3.5.

The pair
$\overline{\mathbb{K}}=(\\{\ast\\},\mathbb{K}\cup\\{-\infty,\infty\\})$, where
$\\{\ast\\}$ is a singleton and $\mathbb{K}\cup\\{-\infty,\infty\\}$ is a
(non-proper) subset of $\overline{\mathbb{K}}^{\\{\ast\\}}$, is clearly a
$\overline{\mathbb{K}}$-extended L-convex set.

###  3.2 Homomorphisms of $\overline{\mathbb{K}}$-Extended L-Convex Sets

######  Definition 3.6.

Let $\mathbf{D}=({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ and
$\mathbf{E}=({\textup{Ind}(\mathbf{E})},\mathbf{E}_{0})$ be
$\overline{\mathbb{K}}$-extended L-convex sets. A homomorphism

$\Phi\colon\mathbf{D}\longrightarrow\mathbf{E}$

from $\mathbf{D}$ to $\mathbf{E}$ is a map

${\textup{Ind}(\Phi)}\colon{\textup{Ind}(\mathbf{E})}\longrightarrow{\textup{Ind}(\mathbf{D})}$

from the index set of $\mathbf{E}$ to that of $\mathbf{D}$, such that for all
$p\in\mathbf{D}_{0}$, the element
$\Phi_{0}(p)\in\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{E})}$ given by

$\Phi_{0}(p)=p\circ{\textup{Ind}(\Phi)}\colon{\textup{Ind}(\mathbf{E})}\overset{{\textup{Ind}(\Phi)}}{\longrightarrow}{\textup{Ind}(\mathbf{D})}\overset{p}{\longrightarrow}\mathbb{K}\cup\\{-\infty,\infty\\}$

is an element of $\mathbf{E}_{0}$.

$\mathbf{D}$ is called the domain of $\Phi$ and $\mathbf{E}$ the codomain of
$\Phi$. We denote the set of all homomorphisms from $\mathbf{D}$ to
$\mathbf{E}$ by ${\llbracket\mathbf{D},\mathbf{E}\rrbracket}_{0}$.

The condition for a map
${\textup{Ind}(\Phi)}\colon{\textup{Ind}(\mathbf{E})}\longrightarrow{\textup{Ind}(\mathbf{D})}$
to define a homomorphism of $\overline{\mathbb{K}}$-extended L-convex sets
assures that we can always construct a map (called the underlying map of
$\Phi$)

$\Phi_{0}\colon\mathbf{D}_{0}\longrightarrow\mathbf{E}_{0}$

from the underlying set of $\mathbf{D}$ to that of $\mathbf{E}$ (the same
direction as the homomorphism $\Phi$). Therefore one can intuitively think of
a homomorphism as a map between the underlying sets with a special property,
namely that all it does is to relabel the indices in some fixed manner
(determined by ${\textup{Ind}(\Phi)}$). However, note that the equality
between homomorphisms $\Phi,\Psi\colon\mathbf{D}\longrightarrow\mathbf{E}$ are
defined as that between the maps
${\textup{Ind}(\Phi)},{\textup{Ind}(\Psi)}\colon{\textup{Ind}(\mathbf{E})}\longrightarrow{\textup{Ind}(\mathbf{D})}$
of the index sets and not just between the underlying maps
$\Phi_{0},\Psi_{0}\colon\mathbf{D}_{0}\longrightarrow\mathbf{E}_{0}$ (there do
exist different homomorphisms with a common underlying map). Fig. 3.3
illustrates an example of homomorphisms between
$\overline{\mathbb{K}}$-extended L-convex sets with two-element index sets. In
this example, $\Phi$ is given by
${\textup{Ind}(\Phi)}\colon\\{w,w^{\prime}\\}\longrightarrow\\{v,v^{\prime}\\}$
with ${\textup{Ind}(\Phi)}(w)=v$ and
${\textup{Ind}(\Phi)}(w^{\prime})=v^{\prime}$. Correspondingly, we find that
$\Phi_{0}\colon\mathbf{D}_{0}\longrightarrow\mathbf{E}_{0}$ embeds the “thin
band” $\mathbf{D}_{0}$ into the “thick band” $\mathbf{E}_{0}$ (the dark region
in $\mathbf{E}_{0}$ represents the image of $\mathbf{D}_{0}$ through the map
$\Phi_{0}$). Observe that unlike ${\textup{Ind}(\Phi)}$,
${\textup{Ind}(\Phi)}^{-1}\colon\\{v,v^{\prime}\\}\longrightarrow\\{w,w^{\prime}\\}$
does not define a homomorphism, because $\mathbf{E}_{0}$ does not fit in
$\mathbf{D}_{0}$.

$\mathbf{D}$$\mathbf{E}$$\Phi$${\textup{Ind}(\mathbf{D})}$${\textup{Ind}(\mathbf{E})}$$v$$w$$v^{\prime}$$w^{\prime}$${\textup{Ind}(\Phi)}$$\Phi_{0}$$\mathbf{D}_{0}$$\mathbf{E}_{0}$$v$$v^{\prime}$$w$$w^{\prime}$
Figure 3.3: A homomorphism between $\overline{\mathbb{K}}$-extended L-convex
sets

We note that homomorphisms include identity maps and are closed under
composition (therefore, $\overline{\mathbb{K}}$-extended L-convex sets
together with their homomorphisms, form a category). Using these facts, we
define the notion of isomorphisms between $\overline{\mathbb{K}}$-extended
L-convex sets as follows:

######  Definition 3.7.

Let $\mathbf{D}$ and $\mathbf{E}$ be $\overline{\mathbb{K}}$-extended L-convex
sets. A homomorphism

$\Phi\colon\mathbf{D}\longrightarrow\mathbf{E}$

from $\mathbf{D}$ to $\mathbf{E}$ is an isomorphism if there exists a
homomorphism (called its inverse)

$\Psi\colon\mathbf{E}\longrightarrow\mathbf{D}$

from $\mathbf{E}$ to $\mathbf{D}$ such that $\Psi\circ\Phi=1_{\mathbf{D}}$ and
$\Phi\circ\Psi=1_{\mathbf{E}}$ hold, where $1_{\mathbf{D}}$ and
$1_{\mathbf{E}}$ are the identity homomorphisms on $\mathbf{D}$ and
$\mathbf{E}$, respectively.

If there is an isomorphism between $\mathbf{D}$ and $\mathbf{E}$, then they
are said to be isomorphic and written as $\mathbf{D}\cong\mathbf{E}$.

In other words, $\Psi\colon\mathbf{E}\longrightarrow\mathbf{D}$ is the inverse
of $\Phi\colon\mathbf{D}\longrightarrow\mathbf{E}$ if and only if the map
${\textup{Ind}(\Psi)}\colon{\textup{Ind}(\mathbf{D})}\longrightarrow{\textup{Ind}(\mathbf{E})}$
is the inverse of
${\textup{Ind}(\Phi)}\colon{\textup{Ind}(\mathbf{E})}\longrightarrow{\textup{Ind}(\mathbf{D})}$.

In Definition 2.21 we defined the canonical ordering $\Rightarrow$ on the set
$[\mathcal{A},\mathcal{B}]_{0}$ of all $\mathcal{V}$-functors from a
$\mathcal{V}$-category $\mathcal{A}$ to $\mathcal{B}$, hence also for the
special case of $\mathcal{V}=\overline{\mathbb{K}}$. Now we define a similar
relation (also denoted by $\Rightarrow$) on the set
${\llbracket\mathbf{D},\mathbf{E}\rrbracket}_{0}$ of homomorphisms.

######  Definition 3.8.

Let $\mathbf{D}=({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ and
$\mathbf{E}=({\textup{Ind}(\mathbf{E})},\mathbf{E}_{0})$ be
$\overline{\mathbb{K}}$-extended L-convex sets. The set
${\llbracket\mathbf{D},\mathbf{E}\rrbracket}$ of all homomorphisms from
$\mathbf{D}$ to $\mathbf{E}$ admits a canonical relation $\Rightarrow$ defined
as follows:

$\Phi\Rightarrow\Psi\iff\Phi_{0}(p)\geq\Psi_{0}(p)\quad(\forall
p\in\mathbf{D}_{0}),$

where $\Phi,\Psi\colon\mathbf{D}\longrightarrow\mathbf{E}$ are homomorphisms
and $\geq$ is the coordinate-wise order on $\mathbf{E}_{0}$. We call
$\Rightarrow$ the canonical ordering on
${\llbracket\mathbf{D},\mathbf{E}\rrbracket}_{0}$.

Note that we can equip the underlying set $\mathbf{D}_{0}$ with a distance
function $d_{\mathbf{D}_{0}}$ defined by the restriction of the sup-distance
on $\overline{\mathbb{K}}^{\textup{Ind}(\mathbf{D})}$. Under these distances,
one can show that the underlying map $\Phi_{0}$ of every homomorphism
$\Phi\colon\mathbf{D}\longrightarrow\mathbf{E}$ is nonexpansive, hence defines
a $\overline{\mathbb{K}}$-functor. Therefore, the notion of the canonical
ordering $\Rightarrow$ for $\overline{\mathbb{K}}$-functors restricts to that
for the underlying maps of homomorphisms. The above definition coincides with
the result of this approach. Hence $\Rightarrow$ for homomorphisms is also a
preorder, and is preserved under composition (note that
$(\Psi\circ\Phi)_{0}=\Psi_{0}\circ\Phi_{0}$).

###  3.3 Duality Theorems

In this section we show the main result of the thesis, a duality theorem
between $\overline{\mathbb{K}}$-categories and
$\overline{\mathbb{K}}$-extended L-convex sets. First we establish the duality
at the level of individual objects; the resulting Theorem 3.9 states that
there is a one-to-one correspondence between the isomorphism class of
$\overline{\mathbb{K}}$-categories and that of
$\overline{\mathbb{K}}$-extended L-convex sets. In fact, a similar result for
L-convex sets and L-convex polyhedra is already known via almost parallel
constructions in the context of discrete convex analysis. However, there is an
essentially novel aspect (conceptually, rather than technically) in our
approach; we employ the notions of $\overline{\mathbb{K}}$-functors and
homomorphisms of $\overline{\mathbb{K}}$-extended L-convex sets in the
constructions of the duality, and realize them as the function space
constructions with codomain $\overline{\mathbb{K}}$.

By introducing homomorphisms, we can compare these “structure-preserving maps”
of $\overline{\mathbb{K}}$-extended L-convex sets with
$\overline{\mathbb{K}}$-functors, the equally natural maps between
$\overline{\mathbb{K}}$-categories. We can describe the duality at the level
of maps as well; we obtain Theorem 3.13 as a result. In categorical
terminology, we establish a dual equivalence between the category of
$\overline{\mathbb{K}}$-categories and the category of
$\overline{\mathbb{K}}$-extended L-convex sets.

Finally, we conclude the duality in Theorem 3.16 by showing that there is also
a correspondence between the canonical orderings $\Rightarrow$ on
$\overline{\mathbb{K}}$-functors and on homomorphisms, hence at the level of
canonical orderings. In fact, the categories of
$\overline{\mathbb{K}}$-categories and $\overline{\mathbb{K}}$-extended
L-convex sets are (strict) 2-categories (do not confuse with 2-categories,
which are just preordered sets) by the canonical orderings $\Rightarrow$. What
we show is that our construction gives a (strict) 2-equivalence of
2-categories.

####

If we denote the constructions for objects by $[-,\overline{\mathbb{K}}]$
(from a $\overline{\mathbb{K}}$-category to a $\overline{\mathbb{K}}$-extended
L-convex set) and ${\llbracket-,\overline{\mathbb{K}}\rrbracket}$ (from a
$\overline{\mathbb{K}}$-extended L-convex set to a
$\overline{\mathbb{K}}$-category), the duality at the object-level is
expressed as follows:

######  Theorem 3.9.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ be a
$\overline{\mathbb{K}}$-category and
$\mathbf{D}=({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ be a
$\overline{\mathbb{K}}$-extended L-convex set. Then the following hold:

  1. (i)

$\mathcal{A}\cong{\llbracket[\mathcal{A},\overline{\mathbb{K}}],\overline{\mathbb{K}}\rrbracket}$.

  2. (ii)

$\mathbf{D}\cong[{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket},\overline{\mathbb{K}}]$.

Recall that $\cong$ means “is isomorphic to.” Let us define the constructions
and prove that they certainly work.

######  Lemma 3.10.

Let $\mathcal{A}=(\textup{Ob}(\mathcal{A}),d_{\mathcal{A}})$ be a
$\overline{\mathbb{K}}$-category. Then the pair
$[\mathcal{A},\overline{\mathbb{K}}]=(\textup{Ob}(\mathcal{A}),$
$[\mathcal{A},\overline{\mathbb{K}}]_{0})$, where
$[\mathcal{A},\overline{\mathbb{K}}]_{0}$ is the set of all nonexpansive maps
from $\mathcal{A}$ to $\overline{\mathbb{K}}$ (as a
$\overline{\mathbb{K}}$-category), seen as a subset of
$\overline{\mathbb{K}}^{\textup{Ob}(\mathcal{A})}$, is a
$\overline{\mathbb{K}}$-extended L-convex set.

###### Proof.

[Order completeness

] Let $S$ be a set of nonexpansive maps from $\mathcal{A}$ to
$\overline{\mathbb{K}}$. The claim is that $\bigvee_{p\in S}p$,
$\bigwedge_{p\in S}p$ are again nonexpansive maps from $\mathcal{A}$ to
$\overline{\mathbb{K}}$. In other words, that

$\displaystyle d_{\mathcal{A}}(a,b)$ $\displaystyle\geq
d_{\overline{\mathbb{K}}}\big{(}\bigvee_{p\in S}p(a),\bigvee_{p\in
S}p(b)\big{)}=\inf_{p\in S}\\{p(b)\\}-\inf_{p\in S}\\{p(a)\\},$ (3.2)
$\displaystyle d_{\mathcal{A}}(a,b)$ $\displaystyle\geq
d_{\overline{\mathbb{K}}}\big{(}\bigwedge_{p\in S}p(a),\bigwedge_{p\in
S}p(b)\big{)}=\sup_{p\in S}\\{p(b)\\}-\sup_{p\in S}\\{p(a)\\}$ (3.3)

hold for all $a,b\in\textup{Ob}(\mathcal{A})$.

[(3.2)

] For each fixed $p^{\prime}\in S$, the increasing condition implies

$d_{\mathcal{A}}(a,b)\geq p^{\prime}(b)-p^{\prime}(a)\geq\inf_{p\in
S}\\{p(b)\\}-p^{\prime}(a).$

By taking $\sup$ with respect to $p^{\prime}\in S$, we have

$d_{\mathcal{A}}(a,b)\geq\sup_{p^{\prime}\in S}\left\\{\inf_{p\in
S}\\{p(b)\\}-p^{\prime}(a)\right\\}=\inf_{p\in S}\\{p(b)\\}-\inf_{p\in
S}\\{p(a)\\},$

where the equality follows from an instance of a statement in Proposition 2.5
that

$\inf_{p\in S}\\{p(b)\\}-(-)$

turns suprema ($\inf$’s) into infima ($\sup$’s).

[(3.3)

] For each fixed $p^{\prime}\in S$, the increasing condition implies

$d_{\mathcal{A}}(a,b)\geq p^{\prime}(b)-p^{\prime}(a)\geq
p^{\prime}(b)-\sup_{p\in S}\\{p(a)\\}.$

By taking $\sup$ with respect to $p^{\prime}\in S$, we have

$d_{\mathcal{A}}(a,b)\geq\sup_{p^{\prime}\in
S}\left\\{p^{\prime}(b)-\sup_{p\in S}\\{p(a)\\}\right\\}=\sup_{p\in
S}\\{p(b)\\}-\sup_{p\in S}\\{p(a)\\},$

where the equality follows from an instance of a statement in Proposition 2.4
that

$(-)-\sup_{p\in S}\\{p(a)\\}$

preserves infima ($\sup$’s).

[Weight completeness (for $+$)

] Let $p$ be a nonexpansive map from $\mathcal{A}$ to $\overline{\mathbb{K}}$
and $\alpha\in\mathbb{K}\cup\\{-\infty,\infty\\}$. The claim is that
$p+\alpha\cdot\textbf{1}$ is again a nonexpansive map from $\mathcal{A}$ to
$\overline{\mathbb{K}}$. In other words, that

$\displaystyle d_{\mathcal{A}}(a,b)$ $\displaystyle\geq
d_{\overline{\mathbb{K}}}\big{(}p(a)+\alpha,p(b)+\alpha\big{)}=\big{(}p(b)+\alpha\big{)}-\big{(}p(a)+\alpha\big{)}$

hold for all $a,b\in\textup{Ob}(\mathcal{A})$. We use the increasing condition
for $p$

$d_{\mathcal{A}}(a,b)\geq p(b)-p(a)$

and show

$p(b)-p(a)\geq\big{(}p(b)+\alpha\big{)}-\big{(}p(a)+\alpha\big{)},$

which has an equivalent formula:

$\mathord{p(b)-p(a)}\ \geq\
\mathord{}$$\big{(}p(b)+\alpha\big{)}-\big{(}p(a)+\alpha\big{)}$
$\mathord{\big{(}p(b)-p(a)\big{)}+\big{(}p(a)+\alpha\big{)}}\ \geq\
\mathord{}$$p(b)+\alpha$
$\mathord{\big{(}\big{(}p(b)-p(a)\big{)}+p(a)\big{)}+\alpha}\ \geq\
\mathord{}$$p(b)+\alpha$

Therefore it suffices to prove $\big{(}p(b)-p(a)\big{)}+p(a)\geq p(b)$, as
follows:

$\mathord{\big{(}p(b)-p(a)\big{)}+p(a)}\ \geq\ \mathord{}$$p(b)$
$\mathord{p(b)-p(a)}\ \geq\ \mathord{}$$p(b)-p(a)$

∎

######  Lemma 3.11.

Let $\mathbf{D}=({\textup{Ind}(\mathbf{D})},\mathbf{D}_{0})$ be a
$\overline{\mathbb{K}}$-extended L-convex set. Then the pair
${\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}=\big{(}{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}_{0},d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}\big{)}$,
where ${\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}_{0}$ is the set
of all homomorphisms from $\mathbf{D}$ to $\overline{\mathbb{K}}$ (as a
$\overline{\mathbb{K}}$-extended L-convex set) and
$d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}$ is the distance
function on it defined by the sup-distance between the underlying maps, is a
$\overline{\mathbb{K}}$-category.

###### Proof.

First note that elements of
${\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}_{0}$ can canonically
be identified with that of ${\textup{Ind}(\mathbf{D})}$, via a bijection
$\pi_{\mathbf{D}}$ defined as follows:

$\pi_{\mathbf{D}}\colon{\textup{Ind}(\mathbf{D})}\longrightarrow{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}_{0},\qquad\pi_{\mathbf{D}}(v)=\pi_{v}\quad(\forall
v\in{\textup{Ind}(\mathbf{D})}),$

where

${\textup{Ind}(\pi_{v})}\colon\\{\ast\\}\longrightarrow{\textup{Ind}(\mathbf{D})},\qquad{\textup{Ind}(\pi_{v})}(\ast)=v.$

The underlying maps of $\pi_{v}$’s are given as the “projection maps”:

$(\pi_{v})_{0}\colon\mathbf{D}_{0}\longrightarrow\mathbb{K}\cup\\{-\infty,\infty\\}\subseteq\overline{\mathbb{K}}^{\\{\ast\\}}\qquad(\pi_{v})_{0}(p)=p(v).$

See Fig. 3.4 for an illustration. Thus we may write
${\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}_{0}=\\{\pi_{v}\\}_{v\in{\textup{Ind}(\mathbf{D})}}$.
Also note that

$\displaystyle
d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}(\pi_{v},\pi_{w})$
$\displaystyle=\sup_{p\in\mathbf{D}_{0}}\\{d_{\overline{\mathbb{K}}}((\pi_{v})_{0}(p),(\pi_{w})_{0}(p))\\}$
$\displaystyle=\sup_{p\in\mathbf{D}_{0}}\\{d_{\overline{\mathbb{K}}}(p(v),p(w))\\}$
$\displaystyle=\sup_{p\in\mathbf{D}_{0}}\\{p(w)-p(v)\\}.$ (3.4)

$\mathbf{D}$$\overline{\mathbb{K}}$$\pi_{v}$${\textup{Ind}(\mathbf{D})}$$\\{\ast\\}$$\vdots$$v$$\ast$$\vdots$${\textup{Ind}(\pi_{v})}$$(\pi_{v})_{0}$$\mathbf{D}_{0}$$\mathbb{K}\cup\\{-\infty,\infty\\}$$v$
Figure 3.4: The homomorphism $\pi_{v}$

[Composition law

] The claim is

$d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}(\pi_{u},\pi_{v})+d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}(\pi_{v},\pi_{w})\geq
d_{{\llbracket\mathbf{D},\overline{\mathbb{K}}\rrbracket}}(\pi_{u},\pi_{w}),$