The n-Category Café

Lawvere begins by describing some of the philosophy behind the paper. He argues that rather than being abstract nonsense that only appears at the highest level of mathematics, category theory can be found even in the most elementary concepts. He mentions the well known examples of posets and groups as categories, and the aim of the paper is to describe another example of an elementary mathematical structure arising from categorical constructions, namely metric spaces.

We’ll also look at posets as enriched categories that are closely related to metric spaces, and this is where the “generalized logic” of the title comes in. The idea is that objects in a monoidal category $\mathcal{V}$ will be truth values for our generalized logic, morphisms in $\mathcal{V}$ will be entailments between them, certain functors correspond to logical operations, and adjointness relations between these functors correspond to rules of inference.

We will only consider categories enriched in complete and cocomplete symmetric monoidal closed categories (which I’ll just call “monoidal categories”), and we are particularly interested in two examples. The first is $\mathbb{2}$, which has two objects, $\mathrm{false}$ and $\mathrm{true}$, and three morphisms, which we write as entailments: $\mathrm{false} \vdash \mathrm{false}$, $\mathrm{false} \vdash \mathrm{true}$ and $\mathrm{true} \vdash \mathrm{true}$. The tensor product is given by conjunction, the unit is $\mathrm{true}$ and the internal hom is implication.

The hom-tensor adjunction gives a correspondence between judgements $a \wedge u \vdash v$ and $u \vdash (a \Rightarrow v)$, which is just the deduction theorem from logic. Categories enriched in $\mathbb{2}$ are simply posets (well, really preorders); we interpret the hom-object $X(x,y)$ as the truth value of the statement $x \leq y$, and the composition and identities give us

$$(x \leq y) \wedge (y \leq z) \vdash x \leq z \quad \text{and} \quad \mathrm{true} \vdash x \leq x.$$

The category $\mathbb{R}$ has as objects non-negative reals together with $\infty$, and has a single morphism $x \to y$ precisely when $x \geq y$. The tensor product is addition with $0$ as the unit, and this forces the internal hom to be truncated subtraction:

$$[x,y] = \mathrm{max} (y-x, 0),$$

but we’ll just write this as $y-x$. Thus the fact that $x+y \geq z$ if and only if $y \geq z-x$ can be thought of as somehow generalizing the deduction theorem. The composition and identities in an $\mathbb{R}$-category $X$ give us

$$X(x,y) + X(y,z) \geq X(x,z) \quad \text{and} \quad 0 \geq X(x,x),$$

which are familiar as axioms of metric spaces, and this is how we will refer to $\mathbb{R}$-categories. This is a weakening of the usual metric space axioms in three ways:

• We don’t require that $X(x,y) = 0$ only when $x=y$. This condition amounts to requiring that isomorphic objects are equal, which is undesirable from a categorical point of view; this is also the reason for dropping antisymmetry of posets. There are naturally occurring examples that don’t satisfy the non-degeneracy condition; perhaps most notably, it makes sense to regard the distance between two measurable functions that are equal almost everywhere as being zero.

• We allow $X(x,y) = \infty$. Allowing infinite distances is also quite natural, as it’s easy to imagine spaces where it’s impossible to get from one point to another. For example, this is the most sensible way to think of distances in a discrete space.

• We don’t require $X(x,y) = X(y,x)$. Allowing non-symmetry is a more significant shift in what we mean by a metric space, but even so there are natural examples, for example the Hausdorff metric on subsets of a metric space. It’s best to think of the hom-values in a generalized metric space not as representing distances, but representing the least time or effort it takes to get from one point or state to another. When you look at it this way, there’s no reason to assume symmetry (e.g. going up and down a hill are not equally difficult).

There is a monoidal functor $\mathbb{2} \to \mathbb{R}$ sending $\mathrm{false} \mapsto \infty$ and $\mathrm{true} \mapsto 0$, and this induces an inclusion of the category of posets into the category of metric spaces. There is also a monoidal functor $\mathbb{2} \to \mathrm{Set}$, so metric spaces and categories can be seen as generalizing posets in different directions.

Functor categories and Yoneda

A $\mathbb{2}$-functor between posets is precisely an order preserving map, and a $\mathbb{R}$-functor between metric spaces is a Lipschitz map with Lipschitz constant 1, i.e. a function $f \colon X \to Y$ such that $Y(f x,f x') \leq X(x,x')$ for all $x$ and $x'$ in $X$. For an arbitrary monoidal category $\mathcal{V}$ and $\mathcal{V}$-categories $X$ and $Y$ the functor $\mathcal{V}$-category $[X,Y]$ has as objects the $\mathcal{V}$-functors $X \to Y$, and the hom objects are defined by the end

$$[X,Y](f,g) = \int _x Y(f x,g x).$$

When $\mathcal{V} = \mathrm{Set}$, this just gives the ordinary end representation of the set of natural transformations. Since $\mathbb{2}$ and $\mathbb{R}$ are both posets, ends reduce to products, which are conjunctions in $\mathbb{2}$ and suprema in $\mathbb{R}$. So for posets, the object of natural transformations between order preserving maps $f,g \colon X \to Y$ is the truth value of the statement $\forall x (f x \leq g x)$. In other words, order preserving maps are ordered by domination. For metric spaces the hom object $[X,Y](f,g)$ is given by $\sup_x Y(f x,g x)$. So the space of Lipschitz-1 maps between metric spaces is endowed with the sup metric.

The closed structure of the monoidal category $\mathcal{V}$ makes $\mathcal{V}$ itself into a $\mathcal{V}$-category. For $\mathbb{2}$ this gives the obvious interpretation of $\mathbb{2}$ as a poset. However, the metric on $\mathbb{R}$ is given by truncated subtraction, rather than the usual $|y-x|$. The self-enrichment of $\mathcal{V}$ means we can define the presheaf $\mathcal{V}$-category $[X^{\mathrm{op}}, \mathcal{V}]$, and that allows us to define the Yoneda embedding $X \to [X^{\mathrm{op}},\mathcal{V}]$, which sends an object $x$ to the representable presheaf $X(-,x)$. Just as in ordinary category theory, this embedding is full and faithful, which in the case of posets gives:

Proposition. Any poset $X$ can be embedded into the poset of downwards closed subsets of $X$ (ordered by inclusion), by sending an element $x$ to the set of all things $\leq x$.

Here we have used the correspondence between downwards closed subsets and order preserving maps $X^{\mathrm{op}} \to \mathbb{2}$. For metric spaces we have:

Proposition. Any metric space can be isometrically embedded into the space of Lipschitz-1 maps $X^{\mathrm{op}} \to \mathbb{R}$.

Adequacy and density

We say that a $\mathcal{V}$-functor $i \colon X \to Y$ is adequate if the composite

$$Y \to [Y^{\mathrm{op}},\mathcal{V}] \to [X^{\mathrm{op}}, \mathcal{V}]$$

of the Yoneda embedding with restriction along $i$ is full and faithful. We say that $i$ is dense if we have an isomorphism of bimodules $i_{\star} \circ i^{\star} \cong 1_X$. I haven’t yet said what bimodules are, but the important thing is that in the case of metric spaces this becomes the condition that

$$Y(y_1,y_2) = inf_x [Y(y_1,i x) + Y(i x, y_2)].$$

This terminology is slightly unfortunate, because what Lawvere calls an adequate functor is nowadays called a dense functor, and Lawvere’s notion of density doesn’t have a modern name as far as I’m aware. A functor is dense iff it’s image is dense in the usual metric space sense. Lawvere shows that a dense functor is adequate, at least in the case of metric spaces. A metric space is separable if it admits a dense map from the discrete space on the natural numbers, and this result give us

Proposition. Any separable metric space can be isometrically embedded in the space of sequences of reals endowed with the sup metric.

This space of sequences is not quite $l_{\infty}$ as usually defined because of the non-standard metric on $\mathbb{R}$.

The comprehension scheme

A(n ordinary) functor $p \colon E \to B$ is called a discrete opfibration if every morphism $p(e) \to b$ is the image under $p$ of a unique morphism with domain $e$. There is a correspondence between discrete opfibrations on $B$ and functors $B \to \mathrm{Set}$, and this correspondence is obtained by restricting a certain adjunction $\mathrm{Cat}/B \rightleftarrows [B, \mathrm{Set}]$ to an equivalence. This adjunction can be defined for arbitrary $\mathcal{V}$, provided that the unit of $\mathcal{V}$ is in fact terminal (this gives a way of defining projections from a tensor product to each of the factors, which is not generally possible). I won’t go into the details of how it’s defined, but I’ll describe what it gives for $\mathbb{2}$ and $\mathbb{R}$.

Given an order-preserving map $p \colon E \to B$ between posets, the left adjoint of this adjunction sends $p$ to $\phi_p \colon B \to \mathbb{2}$, defined by setting $\phi_p(b)$ to be the truth value of the statement $\exists e(b \leq p(e))$. The right adjoint sends $\phi \colon B \to \mathcal{V}$ to $\pi \colon \{B|\phi\} \to B$, where $\{B|\phi\}$ is the (upwards closed) subset of $B$ on which $\phi$ takes the value $\mathrm{true}$, and $\pi$ is the inclusion. If we take $B$ to be a discrete poset (i.e. a set) then $\phi$ is just a unary predicate on $B$, and

$$\{B|\phi \} = \{b \in B | \phi (b) = \mathrm{true} \}.$$

Lawvere calls the right adjoint of the adjunction the comprehension scheme, and this example shows why.

For metric spaces, the left adjoint sends a Lipschitz-1 map $p \colon E \to B$ to the function $\phi_p \colon B \to \mathbb{R}$ defined by $\phi_p (b) = \inf_e B(p (e), b)$, i.e. the distance from the image of $p$. The right adjoint sends $\phi \colon B \to \mathbb{R}$ to the inclusion of its vanishing set.

It’s interesting to note that for $\mathrm{Set}$ and $\mathbb{2}$, this adjunction restricts to an equivalence between a subcategory of $\mathcal{V} \text{-} \mathrm{Cat} / B$ (the discrete opfibrations, and inclusions of upwards closed subsets respectively) and the whole functor category $[B, \mathcal{V}]$. For $\mathbb{R}$ however, only those functions $B \to \mathbb{R}$ that give the distance from a closed subset are invariant under the adjunction, and these correspond to the inclusion of this closed set. Thus purely categorical considerations naturally give rise to the closed sets in $B$ as a distinguished class of subsets.

Bimodules and Kan extensions

For $\mathcal{V}$-categories $X$ and $Y$, a bimodule $\phi \colon X \to Y$ consists of a $\mathcal{V}$-functor $\phi \colon Y^{\mathrm{op}} \otimes X \to \mathcal{V}$ (the placement of the $\mathrm{op}$ is not completely agreed upon, but I’ll stick with Lawvere’s convention). We can think of a bimodule as a $\mathcal{V}$-category structure on the disjoint union of $X$ and $Y$, with $\phi(y,x)$ as the hom object between an object of $Y$ and an object of $X$, and with all the hom objects in the other direction being the initial object of $\mathcal{V}$. The $\mathcal{V}$-functoriality of $\phi$ means that we have a “composition” operation $Y(y',y)\otimes \phi(y,x) \to \phi(y',x)$, and dually, and that this composition is associative.

There are two special types of bimodule that are particularly important, and they are both induced by $\mathcal{V}$-functors. Given a $\mathcal{V}$-functor $f \colon X \to Y$, we define bimodules $f_{\star} \colon X \to Y$ and $f^{\star} \colon Y \to X$ by

$$f_{\star} (y,x) = Y(y, f x) \quad \text{and} \quad f^{\star} (x,y) = Y(f x,y).$$

A morphism between two bimodules $X \rightrightarrows Y$ is just a $\mathcal{V}$-natural transformation between the corresponding $\mathcal{V}$-functors $Y^{\mathrm{op}} \otimes X \to \mathcal{V}$. Given bimodules $\phi \colon X \to Y$ and $\psi \colon Y \to Z$, we can define the composite bimodule $\psi \circ \phi \colon X \to Z$ by the coend

$$\psi \circ \phi (z,x) = \int^y \psi (z,y) \otimes \phi (y, x),$$

and this composition is associative (up to isomorphism). The bimodule $1_X \colon X \to X$ given by $X(-,-) \colon X^{\mathrm{op}} \otimes X \to \mathcal{V}$ serves as an identity for this composition, and hence there is bicategory $\mathcal{V} \text{-} \mathrm{Mod}$ of $\mathcal{V}$-categories, bimodules and natural transformations.

Let $k$ be the $\mathcal{V}$-category with a single object and whose only hom object is the unit object of $\mathcal{V}$. Then a bimodule $k \to k$ is just an object of $\mathcal{V}$, and composition is just the tensor product in $\mathcal{V}$. So bimodule composition generalizes the tensor product, and it’s natural to ask whether the internal hom of $\mathcal{V}$ also generalizes. Since general bimodule composition is not commutative, there are two composition operations (on the left and the right) that could potentially have right adjoints, and in fact they both do, and these are defined by end formulae. If we restrict our attention to modules of the form $f_{\star}$ for a $\mathcal{V}$-functor $f$, the operation $\beta \mapsto \beta \circ f_{\star}$ also has a left adjoint, which is given by $\phi \mapsto \phi \circ f^{\star}$, and can also be written explicitly as a coend.

Let $f$ be a $\mathcal{V}$-functor $X \to Y$. Bimodules $Y \to k$ are just $\mathcal{V}$-functors $\psi \colon Y \to \mathcal{V}$, and the bimodule composite $\psi \circ f_{\star}$ is the bimodule $X \to k$ corresponding to the $\mathcal{V}$-functor $\psi f \colon X \to \mathcal{V}$. Thus the left and right adjoint to precomposition with $f_{\star}$ in this case give left and right Kan extensions along $f$, and the formulae for these adjoints reduce to the familiar coend and end formulae for left and right Kan extensions:

$$\mathrm{Lan}_f \phi (y) = \int^x Y(f x, y) \otimes \phi (x) \quad \text{and} \quad \mathrm{Ran}_f \phi (y) = \int _x [ Y(y, f x), \phi (x) ]$$

When $f$ is full and faithful, the Kan extensions really are extensions, in other words if you extend and then restrict, you get back what you started with. So specializing all this to the case $\mathcal{V} = \mathbb{R}$ gives:

Proposition. Let $X$ be a subspace of a metric space $Y$, and let $\phi$ be a Lipschitz-1 map from $X$ to $\mathbb{R}$. Then $\phi$ has both maximal and minimal Lipschitz-1 extensions to the whole of $Y$, given by

$$\mathrm{Lan}_f \phi (y) = \inf_x [ \phi(x) + Y(f x,y) ] \quad \text{and} \quad \mathrm{Ran}_f \phi (y) = \sup_x [ \phi(x) - Y(y,f x)].$$

A particularly interesting example is given when $X$ is the space of simple, non-negative functions on a probability space (i.e. positive linear combinations of indicator functions of measurable sets), and $f$ is the inclusion into the space of all measurable functions (with the sup metric). If you take $\phi (x)$ to be the integral of the simple function $x$, then the two Kan extensions of $\phi$ give the upper and lower integrals of a measurable function $y$. In particular, $y$ is integrable if and only if $\mathrm{Lan}_f \phi (y) = \mathrm{Ran}_f \phi (y)$.

If we think of a map from a poset to $\mathbb{2}$ as a unary relation or predicate, then the left and right Kan extensions become

$$\mathrm{Lan}_f \phi (y) = \exists x (f x \leq y \wedge \phi (x) ) \quad \text{and} \quad \mathrm{Ran}_f \phi (y) = \forall x (y \leq f x \Rightarrow \phi (x)).$$

If we restrict to the case when $X$ and $Y$ are just sets, so that $f$ is an arbitrary function, this gives

$$\mathrm{Lan}_f \phi (y) = (\exists x \in f^{-1} (y)) \phi (x) \quad \text{and} \quad \mathrm{Ran}_f \phi (y) = (\forall x \in f^{-1}(y)) \phi (x),$$

and specializing even further to the case when $f$ is a product projection $W \times Z \to Z$ we have

$$\mathrm{Lan}_f \phi (z) = \exists w \phi (w,z) \quad \text{and} \quad \mathrm{Ran}_f \phi (z) = \forall w \phi (w,z).$$

So existential and universal quantification are (very) special cases of Kan extensions. This leads Lawvere to use the phrase “Kan quantification” for Kan extensions.

Every $\mathcal{V}$-functor $X \to Y$ gives rise to an adjunction $f_{\star} \colon X \rightleftarrows Y \colon f^{\star}$ in the bicategory of bimodules, and it’s natural to ask under what conditions does every adjunction arise in this way. Recall that a metric space is (Cauchy) complete if every Cauchy sequence has a limit. A bit of care is needed when making this precise, because the possible non-symmetry of the metric means there are several things it could mean for a sequence to be Cauchy or convergent.

Proposition. A metric space $Y$ is Cauchy complete if and only if every adjunction of bimodules $X \rightleftarrows Y$ is induced by a Lipschitz-1 map $X \to Y$. In particular, the points of the Cauchy completion of $Y$ correspond to bimodule adjunctions $1 \rightleftarrows Y$ (where $1$ is the one point metric space).

This gives a description of Cauchy complete metric spaces that is purely categorical, so it makes sense to talk about Cauchy complete $\mathcal{V}$-categories for arbitrary $\mathcal{V}$. It turns out that an ordinary ($\mathrm{Set}$-enriched) category is Cauchy complete iff all idempotents split, and the Cauchy completion of a ring regarded as a one object category enriched in $\mathrm{Ab}$ is the category of finitely generated projective modules.

These days it’s more common to see Cauchy complete categories defined in terms of absolute colimits. I’m not too sure about the history of the concept, but I think the definition Lawvere gives came first, and Street later gave the characterisation in terms of absolute colimits in “Absolute colimits in enriched categories”.

Free $\mathcal{V}$-categories

Finally, Lawvere defines a $\mathcal{V}$-graph $(X, \gamma)$ to consist of a set $X$ of “vertices” and for every pair $(x,x')$ of vertices an object $\gamma (x,x')$ of $\mathcal{V}$ (i.e. like a $\mathcal{V}$-category but without composition or identities). A morphism of $\mathcal{V}$-graphs is a function $f \colon X \to Y$ and a family of morphisms $f_{x,x'} \colon \gamma (x,x') \to \delta (f x, f x')$. There is an evident forgetful functor from $\mathcal{V} \text{-} \mathrm{Cat}$ to the category of $\mathcal{V}$-graphs. This has a left adjoint which sends a $\mathcal{V}$-graph $(X, \gamma)$ to the $\mathcal{V}$-category $F X$ which has the vertices of $X$ as objects and hom objects defined by

$$FX(x,x') = \sum_{x_1,\ldots , x_n} \gamma (x,x_1) \otimes \gamma (x_1,x_2) \otimes \ldots \otimes \gamma (x_n, x'),$$

where the sum runs over all finite sequences of vertices. In the case of metric spaces, this gives the “least-cost” distance:

$$inf_{x_1, \ldots , x_n} [ \gamma(x, x_1) + \gamma (x_1, x_2) + \ldots + \gamma (x_n, x') ].$$

I’ll finish with a few questions for those more knowledgeable than myself:

• I think the only categorical notion in the paper that I hadn’t at least heard of before is Lawvere’s notion of density (i.e. a functor $i$ such that $i_{\star} \circ i^{\star} = 1$; as noted above this is different from what people usually mean by a dense functor). Does this appear elsewhere in category theory, or is it only interesting for metric spaces?

• A lot of the results about metric spaces are very similar to classical results, but are not quite the same because of the non-standard metric on $\mathbb{R}$. Is there any way of recovering the classical results without too much work?

• The idea of generalized logic is intriguing, but I’m not sure how far you can go with it. Is it possible, for example, to talk about generalized models of a generalized theory?