Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

February 21, 2014

Metric Spaces, Generalized Logic, and Closed Categories

Posted by Emily Riehl

Guest post by Tom Avery

Before getting started, I’d like to thank Emily for organizing the seminar, as well as all the other participants. It’s been a lot of fun so far! I’d also like to thank my supervisor Tom Leinster for some very helpful suggestions when writing this post.

In the fourth instalment of the Kan Extension Seminar we’re looking at Lawvere’s paper “Metric spaces, generalized logic, and closed categories”. This is the paper that introduced the surprising description of metric spaces as categories enriched over a certain monoidal category \mathbb{R}. A lot of people find this very striking when they first see it, and it helps to drive home the point that enriched categories are not just ordinary categories with some extra structure on the hom-sets; in fact the hom-sets don’t have to be sets at all!

Lawvere also intended the paper to serve as an accessible introduction to enriched category theory, so it begins fairly gently with some basic definitions. For the purposes of this post however, I’ll assume the reader has at least seen the definitions of symmetric monoidal closed categories, 𝒱\mathcal{V}-categories, and 𝒱\mathcal{V}-functors. If not, everything you need can be found on the nlab.

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, false\mathrm{false} and true\mathrm{true}, and three morphisms, which we write as entailments: falsefalse\mathrm{false} \vdash \mathrm{false}, falsetrue\mathrm{false} \vdash \mathrm{true} and truetrue\mathrm{true} \vdash \mathrm{true}. The tensor product is given by conjunction, the unit is true\mathrm{true} and the internal hom is implication.

The hom-tensor adjunction gives a correspondence between judgements auva \wedge u \vdash v and u(av)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)X(x,y) as the truth value of the statement xyx \leq y, and the composition and identities give us

(xy)(yz)xzandtruexx. (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 xyx \to y precisely when xyx \geq y. The tensor product is addition with 00 as the unit, and this forces the internal hom to be truncated subtraction:

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

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

X(x,y)+X(y,z)X(x,z)and0X(x,x),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)=0X(x,y) = 0 only when x=yx=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)=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)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 false\mathrm{false} \mapsto \infty and true0\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 𝟚Set\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:XYf \colon X \to Y such that Y(fx,fx)X(x,x)Y(f x,f x') \leq X(x,x') for all xx and xx' in XX. For an arbitrary monoidal category 𝒱\mathcal{V} and 𝒱\mathcal{V}-categories XX and YY the functor 𝒱\mathcal{V}-category [X,Y][X,Y] has as objects the 𝒱\mathcal{V}-functors XYX \to Y, and the hom objects are defined by the end

[X,Y](f,g)= xY(fx,gx).[X,Y](f,g) = \int _x Y(f x,g x).

When 𝒱=Set\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:XYf,g \colon X \to Y is the truth value of the statement x(fxgx)\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)[X,Y](f,g) is given by sup xY(fx,gx)\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 |yx||y-x|. The self-enrichment of 𝒱\mathcal{V} means we can define the presheaf 𝒱\mathcal{V}-category [X op,𝒱][X^{\mathrm{op}}, \mathcal{V}], and that allows us to define the Yoneda embedding X[X op,𝒱]X \to [X^{\mathrm{op}},\mathcal{V}], which sends an object xx to the representable presheaf X(,x)X(-,x). Just as in ordinary category theory, this embedding is full and faithful, which in the case of posets gives:

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

Here we have used the correspondence between downwards closed subsets and order preserving maps X op𝟚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 opX^{\mathrm{op}} \to \mathbb{R}.

Adequacy and density

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

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

of the Yoneda embedding with restriction along ii is full and faithful. We say that ii is dense if we have an isomorphism of bimodules i i 1 Xi_{\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,ix)+Y(ix,y 2)]. 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 l_{\infty} as usually defined because of the non-standard metric on \mathbb{R}.

The comprehension scheme

A(n ordinary) functor p:EBp \colon E \to B is called a discrete opfibration if every morphism p(e)bp(e) \to b is the image under pp of a unique morphism with domain ee. There is a correspondence between discrete opfibrations on BB and functors BSetB \to \mathrm{Set}, and this correspondence is obtained by restricting a certain adjunction Cat/B[B,Set]\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:EBp \colon E \to B between posets, the left adjoint of this adjunction sends pp to ϕ p:B𝟚\phi_p \colon B \to \mathbb{2}, defined by setting ϕ p(b)\phi_p(b) to be the truth value of the statement e(bp(e))\exists e(b \leq p(e)). The right adjoint sends ϕ:B𝒱\phi \colon B \to \mathcal{V} to π:{B|ϕ}B\pi \colon \{B|\phi\} \to B, where {B|ϕ}\{B|\phi\} is the (upwards closed) subset of BB on which ϕ\phi takes the value true\mathrm{true}, and π\pi is the inclusion. If we take BB to be a discrete poset (i.e. a set) then ϕ\phi is just a unary predicate on BB, and

{B|ϕ}={bB|ϕ(b)=true}.\{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:EBp \colon E \to B to the function ϕ p:B\phi_p \colon B \to \mathbb{R} defined by ϕ p(b)=inf eB(p(e),b)\phi_p (b) = \inf_e B(p (e), b), i.e. the distance from the image of pp. The right adjoint sends ϕ:B\phi \colon B \to \mathbb{R} to the inclusion of its vanishing set.

It’s interesting to note that for Set\mathrm{Set} and 𝟚\mathbb{2}, this adjunction restricts to an equivalence between a subcategory of 𝒱-Cat/B\mathcal{V} \text{-} \mathrm{Cat} / B (the discrete opfibrations, and inclusions of upwards closed subsets respectively) and the whole functor category [B,𝒱][B, \mathcal{V}]. For \mathbb{R} however, only those functions BB \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 BB as a distinguished class of subsets.

Bimodules and Kan extensions

For 𝒱\mathcal{V}-categories XX and YY, a bimodule ϕ:XY\phi \colon X \to Y consists of a 𝒱\mathcal{V}-functor ϕ:Y opX𝒱\phi \colon Y^{\mathrm{op}} \otimes X \to \mathcal{V} (the placement of the op\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 XX and YY, with ϕ(y,x)\phi(y,x) as the hom object between an object of YY and an object of XX, 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)ϕ(y,x)ϕ(y,x)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:XYf \colon X \to Y, we define bimodules f :XYf_{\star} \colon X \to Y and f :YXf^{\star} \colon Y \to X by

f (y,x)=Y(y,fx)andf (x,y)=Y(fx,y).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 XYX \rightrightarrows Y is just a 𝒱\mathcal{V}-natural transformation between the corresponding 𝒱\mathcal{V}-functors Y opX𝒱Y^{\mathrm{op}} \otimes X \to \mathcal{V}. Given bimodules ϕ:XY\phi \colon X \to Y and ψ:YZ\psi \colon Y \to Z, we can define the composite bimodule ψϕ:XZ\psi \circ \phi \colon X \to Z by the coend

ψϕ(z,x)= yψ(z,y)ϕ(y,x), \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:XX1_X \colon X \to X given by X(,):X opX𝒱X(-,-) \colon X^{\mathrm{op}} \otimes X \to \mathcal{V} serves as an identity for this composition, and hence there is bicategory 𝒱-Mod\mathcal{V} \text{-} \mathrm{Mod} of 𝒱\mathcal{V}-categories, bimodules and natural transformations.

Let kk be the 𝒱\mathcal{V}-category with a single object and whose only hom object is the unit object of 𝒱\mathcal{V}. Then a bimodule kkk \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 f_{\star} for a 𝒱\mathcal{V}-functor ff, the operation ββf \beta \mapsto \beta \circ f_{\star} also has a left adjoint, which is given by ϕϕf \phi \mapsto \phi \circ f^{\star}, and can also be written explicitly as a coend.

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

Lan fϕ(y)= xY(fx,y)ϕ(x)andRan fϕ(y)= x[Y(y,fx),ϕ(x)] \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 ff 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 XX be a subspace of a metric space YY, and let ϕ\phi be a Lipschitz-1 map from XX to \mathbb{R}. Then ϕ\phi has both maximal and minimal Lipschitz-1 extensions to the whole of YY, given by

Lan fϕ(y)=inf x[ϕ(x)+Y(fx,y)]andRan fϕ(y)=sup x[ϕ(x)Y(y,fx)].\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 XX is the space of simple, non-negative functions on a probability space (i.e. positive linear combinations of indicator functions of measurable sets), and ff is the inclusion into the space of all measurable functions (with the sup metric). If you take ϕ(x)\phi (x) to be the integral of the simple function xx, then the two Kan extensions of ϕ\phi give the upper and lower integrals of a measurable function yy. In particular, yy is integrable if and only if Lan fϕ(y)=Ran fϕ(y)\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

Lan fϕ(y)=x(fxyϕ(x))andRan fϕ(y)=x(yfxϕ(x)). \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 XX and YY are just sets, so that ff is an arbitrary function, this gives

Lan fϕ(y)=(xf 1(y))ϕ(x)andRan fϕ(y)=(xf 1(y))ϕ(x), \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 ff is a product projection W×ZZW \times Z \to Z we have

Lan fϕ(z)=wϕ(w,z)andRan fϕ(z)=wϕ(w,z). \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 XYX \to Y gives rise to an adjunction f :XY:f 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 YY is Cauchy complete if and only if every adjunction of bimodules XYX \rightleftarrows Y is induced by a Lipschitz-1 map XYX \to Y. In particular, the points of the Cauchy completion of YY correspond to bimodule adjunctions 1Y1 \rightleftarrows Y (where 11 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 (Set\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 Ab\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,γ)(X, \gamma) to consist of a set XX of “vertices” and for every pair (x,x)(x,x') of vertices an object γ(x,x)\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:XYf \colon X \to Y and a family of morphisms f x,x:γ(x,x)δ(fx,fx)f_{x,x'} \colon \gamma (x,x') \to \delta (f x, f x'). There is an evident forgetful functor from 𝒱-Cat\mathcal{V} \text{-} \mathrm{Cat} to the category of 𝒱\mathcal{V}-graphs. This has a left adjoint which sends a 𝒱\mathcal{V}-graph (X,γ)(X, \gamma) to the 𝒱\mathcal{V}-category FXF X which has the vertices of XX as objects and hom objects defined by

FX(x,x)= x 1,,x nγ(x,x 1)γ(x 1,x 2)γ(x n,x),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,,x n[γ(x,x 1)+γ(x 1,x 2)++γ(x n,x)]. 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 ii such that i i =1i_{\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?

Posted at February 21, 2014 12:47 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2700

42 Comments & 1 Trackback

Re: Metric Spaces, Generalized Logic, and Closed Categories

In the author commentary to the TAC reprint of this article, Lawvere writes:

While listening to a 1967 lecture of Richard Swan, which included a discussion of the relative codimension of pairs of subvarieties, I noticed the analogy between the triangle inequality and a categorical composition law… This connection is more fruitful than a mere analogy, because it provides a sequence of mathematical theorems, so that enriched category theory can suggest new directions of research in metric space theory and conversely, unusual for two subjects so old (1966 and 1906 respectively).

The converse I certainly believe: see Cauchy complete category. But I’d love to collect explicit examples where category theory influences developments in metric space theory, rather than simply reinterprets known theorems (albeit in a spectacularly elegant way).

Tom, maybe I should specifically direct this question to you? Though I would also be interested in learning about milder influences. For instance, has Lawvere’s suggested relaxation of the axioms for a metric space caught on in any way?

Posted by: Emily Riehl on February 21, 2014 1:05 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

I’m not aware that he was influenced by Lawvere, but Gromov says some strikingly similar things in his remarkable, sprawling, book Metric Structures for Riemannian and non-Riemannian spaces. From the very first page of the introduction:

Besides [the triangle inequality], one insists that the distance function be symmetric, that is, d(x,x)=d(x,x)d(x, x') = d(x', x). (This unpleasantly limits many applications: the effort of climbing up to the top of a mountain, in real life as well as in mathematics, is not at all the same as descending back to the starting point).

Finally, one assumes d(x,x)=0d(x, x) = 0 for all xXx \in X and add the following separation axiom. If xxx \neq x', then d(x,x)=0d(x, x') = 0. This seems to be an innocuous restriction, as one can always pass to the quotient space by identifying xx and xx' whenever d(x,x)=0d(x, x') = 0. But sometimes the separation becomes a central issue, e.g., for Kobayashi and Hofer metrics, where such identification may reduce XX to a single point, for instance.

I thought Gromov also allowed \infty as a distance. I can’t find that in the book right now, but in any case I imagine he’s quite relaxed about it.

I don’t know what Kobayashi and Hofer metrics are.

Posted by: Tom Leinster on February 21, 2014 2:52 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

This probably doesn’t really count as a “development in metric space theory”, but I had fun with it, and it wouldn’t have been possible without Lawvere.

Posted by: Mike Shulman on February 21, 2014 4:42 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

A quick comment: a complete and cocomplete symmetric monoidal closed category is what Bénabou calls a cosmos. A snappy name, I think!

Posted by: Zhen Lin on February 21, 2014 10:30 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

I was surprised by Lawvere’s definition of the Cauchy completion of a small VV-category CC as the category of VV-functors C opSetC^{op} \to Set admitting a right adjoint in the bicategory of VV-profunctors. For V=SetV=Set, I am more familiar with another definition: the Cauchy completion of CC is the full subcategory of C^=[C op,Set]\hat{C} = [C^{op},Set] spanned by retracts of representables.

For the convenience of others in a similar position, let me sketch the proof of the following result, due to Borceux-Dejean:

Proposition. A functor F:C opSetF : C^{op} \to Set is in the Cauchy completion CC if and only if it admits a right adjoint as a profunctor F:1CF \colon 1 \nrightarrow C.

Proof: Suppose G:CSetG \colon C \to Set is a right adjoint. The unit is an element of the functor tensor product G× CFG \times_C F, represented by an element (y,x)Gc×Fc(y,x) \in Gc \times Fc for some cCc \in C. The counit is a natural transformation ϵ:Fa×GbC(a,b)\epsilon \colon Fa \times Gb \to C(a,b).

From these, we define x:C(,c)Fx \colon C(-,c) \to F and ϵ(,c)(y):FC(,c)\epsilon(-,c)(y) \colon F \to C(-,c). From one of the triangle inequalities, you can check that this makes FF a retract of C(,c)C(-,c).

Conversely, if FF is a retract of C(,c)C(-,c), the Yoneda lemma gives an idempotent on cc and hence on C(c,)C(c,-). This idempotent splits in [C,Set][C,Set] and the splitting defines a functor G:CSetG \colon C \to Set that one can check is the right adjoint to FF.

Posted by: Emily Riehl on February 21, 2014 7:11 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

For the statement of the Borceux-Dejean proposition, the Cauchy completion is defined to be the idempotent completion, right? So the proposition is analogous to Lawvere’s identification of Cauchy sequences as \mathbb{R}-presheaves with right adjoints as bimodules.

One thing these characterizations have in common is that they require one to know something about maps into a coend: specifically, we take the unit map of the adjoint bimodules I xG(x)F(x)I \to \int^x G(x) \otimes F(x), and we translate it into something else. In the Set\mathbf{Set} case, we take a representative IG(x)×F(x)I \to G(x) \times F(x); in the \mathbb{R} case, the coend is an infinum, and we take a sequence approaching the inf (which becomes our Cauchy sequence).

At the level of general 𝒱\mathcal{V}-categories, one can’t do this because the coend’s universal property involves maps out, not in. I’ve been trying to verify that the category X˜\tilde{X} of 𝒱\mathcal{V}-presheaves-with-right-adjoints-as-bimodules on a 𝒱\mathcal{V}-category XX actually has the appropriate universal property to be called a “Cauchy completion” of XX, and this inability to understand maps into a coend has been a stumbling block. Is there anywhere I can find this done in the literature, or is it considered trivial?

Posted by: Tim Campion on February 23, 2014 2:42 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

It depends; what do you consider to be the “appropriate” universal property? It’s precisely because these characterizations involve maps into colimits that they depend very much on the specific category in question; the most sensible general definition is that Cauchy completion is the completion with respect to absolute colimits. Relative to this definition, I think the result is more or less in Street’s “Absolute colimits in enriched categories”.

Posted by: Mike Shulman on February 23, 2014 7:08 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

The universal property I have in mind is that X˜\tilde X is Cauchy complete (in Lawvere’s sense) and any functor XYX \to Y for a Cauchy complete YY extends essentially uniquely to a functor X˜Y\tilde X \to Y.

What Street shows is that a left adjoint bimodule is the same thing as an absolute weight. He assumes that the Cauchy completion X˜\tilde X exists and can be described as the category of left adjoint bimodules IXI \nrightarrow X, and observes that a consequence of what he’s shown is that X˜\tilde X consists of the absolute weights. What I’m struggling with is the part that Street assumes. In particular, I don’t know how to show that the category of left adjoint bimodules is actually Cauchy complete in Lawvere’s sense.

That is, I want to show that for any left adjoint bimodule IX˜I \nrightarrow \tilde X is representable. What I’d like to do is to compose with the yoneda embedding X˜X\tilde X \nrightarrow X to yield a left adjoint bimodule 1X1 \nrightarrow X which by definition lies in X˜\tilde X, but unfortunately the adjunctions are in the wrong directions. This would be overcome if I could show the (true, I think) fact that yoneda embedding XX˜X \to \tilde X is an equivalence of at the level of bimodules, since an equivalence is both left and right adjoint. The unit is iso because Yoneda is fully faithful; to say that the counit is iso is to say that the Yoneda embedding is dense in Lawvere’s sense. I don’t think this is true of the whole Yoneda embedding; it has to use the specifics of X˜\tilde X in some essential way.

Actually, this approach circumvents the need to understand maps out of coends, but it’s still got me stuck. It’s such a basic fact that it must be in the literature somewhere, but I haven’t found it.

Posted by: Tim Campion on February 23, 2014 8:03 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Betti&Carboni construct a Cauchy completion in the sense of Lawvere for a bicategory XX in ‘Cauchy-completion and the associated sheaf’ (Cah.top.géom.diff. XXIII 1982 http://www.numdam.org/item?id=CTGDC19822332430 ).

Posted by: thomas holder on February 24, 2014 12:22 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

This is very nice! Their description of X˜\tilde X emphasizes the symmetry between the left and right adjoint, and they seem to have an alternative approach to showing that XX˜X \to \tilde X is an equivalence of bimodules.

One restriction is that they work in the quantaloid setting, where 𝒱\mathcal{V} has been generalized to a bicategory, but is restricted to be locally posetal, so this includes 𝒱=\mathcal{V} = \mathbb{R} and 𝒱=2\mathcal{V} = 2, (and, most importantly for their purposes, 𝒱=\mathcal{V} = a certain bicategory of relations constructed from an arbitrary site) but not 𝒱=Set\mathcal{V} = \mathbf{Set}, 𝒱=Ab\mathcal{V} = \mathbf{Ab}, etc. It does save them checking a lot of coherence conditions!

Posted by: Tim Campion on February 24, 2014 4:07 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Sorry, that these restrictions in the Betti-Carboni paper have escaped my notice!

Isar Stubbe has published a series of papers on categories enriched in quantaloids, the first of which (arXiv:math/0409473 ) deals with Morita theory & Cauchy completion. This is probably the best survey for this material around, but might not be at the generality you are looking for.

Posted by: thomas holder on February 24, 2014 10:49 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Ah, I see. You’re on the right track. Let y:AA˜y:A\to\tilde{A} be the corestricted Yoneda embedding, with induced profunctors A˜(1,y):AA˜\tilde{A}(1,y):A ⇸ \tilde{A} and A˜(y,1):A˜A\tilde{A}(y,1):\tilde{A} ⇸ A. As you say, the unit of the adjunction A˜(1,y)A˜(y,1)\tilde{A}(1,y) \dashv \tilde{A}(y,1) is invertible because yy is fully faithful. But because A˜\tilde{A} consists of left adjoints, A˜(y,1)\tilde{A}(y,1) is actually also a left adjoint. Call its right adjoint M:AA˜M:A ⇸ \tilde{A}. Now we have

1 A˜A˜(y,1)A˜(y,1)A˜(y,1)M. 1_{\tilde{A}} \cong \tilde{A}(y,1)\rhd \tilde{A}(y,1) \cong \tilde{A}(y,1) \odot M.

The first isomorphism is essentially by definition of the homs of A˜\tilde{A}, while the second is a general property relating adjoint 1-morphisms and bicategorical homs (use a Yoneda argument). Thus, the unit of the adjunction A˜(y,1)M\tilde{A}(y,1)\dashv M is also an isomorphism. It then follows easily that MA˜(1,y)M\cong \tilde{A}(1,y) and the adjunction is an equivalence.

I also don’t know where this can be found written down. I was tempted to include it in Enriched indexed categories, which the Kan extension seminar is going to read later, but I decided that paper was already too long.

Posted by: Mike Shulman on February 24, 2014 12:56 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Okay – MM can be defined by M(λ,a)=ρ(a)=A˜(ya,ρ)M(\lambda, a) = \rho(a) = \tilde{A}(ya, \rho) where λρ\lambda \dashv \rho, right?

If this is right, then we eventually get A˜(λ,ya)M(λ,a)A˜(ya,ρ)\tilde{A}(\lambda, ya) \cong M(\lambda, a) \cong \tilde{A}(ya, \rho), which seems like a variation on the hom-set definition of adjoint functors (i.e. if LRL \dashv R, then Hom(Lx,y)Hom(x,Ry)\mathrm{Hom}(Lx, y) \cong \mathrm{Hom}(x, Ry)). It would be nice to understand this better, because right now the only way I know to approach adjoint bimodules is via the unit and counit, which sometimes feels kind of clunky.

Posted by: Tim Campion on February 24, 2014 5:57 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

I don’t understand: if by λρ\lambda\dashv \rho you mean that λ\lambda and ρ\rho are both modules, then they can’t both be objects of A˜\tilde{A}.

Posted by: Mike Shulman on February 25, 2014 7:55 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Ok, yes, that’s a right definition of MM. Now I see what you’re saying. More generally, for any adjoint pair fgf\dashv g in a bicategory, with f:ABf:A\to B and g:BAg:B\to A, there are induced isomorphisms (now writing in classical composition order)

(C,B)(fh,k)(C,A)(h,gk)\mathcal{B}(C,B)(f h, k) \cong \mathcal{B}(C,A)(h,g k)

for any h:CAh:C\to A and k:CBk:C\to B. Similarly, for m:ADm:A\to D and n:BDn:B\to D we have

(B,D)(mg,n)(A,D)(m,nf).\mathcal{B}(B,D)(m g, n) \cong \mathcal{B}(A,D)(m,n f).

These are special cases of the mates correspondence. Conversely, by Yoneda, an adjoint pair in a bicategory can be characterized by such a collection of isomorphisms varying naturally in hh and kk (or dually in mm and nn). Does that look like the isomorphism you have in mind?

Posted by: Mike Shulman on February 26, 2014 4:23 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

(Oops, somehow I clicked on reply-to the wrong comment.)

Posted by: Mike Shulman on February 26, 2014 4:27 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

It’s hard for me to see how to apply this isomorphism directly because the isomorphism I’m looking for compares the hom-categories 𝒱Mod(I,A)\mathcal{V}\mathbf{Mod}(I, A) and 𝒱Mod(A,I)\mathcal{V}\mathbf{Mod}(A,I), whereas in the isomorphism you gave, the hom-categories (C,B)\mathcal{B}(C,B) and (C,A)\mathcal{B}(C,A) have the same domain object CC. As a technical point, I think I’d also need the 𝒱\mathcal{V}-bicategory version, rather than the vanilla bicategory version.

Actually, perhaps it’s less mysterious than I thought: it shouldn’t have anything to do with representable bimodules in particular; the more general equation would just be

(*’) 𝒱 A op(λ,λ)𝒱 A(ρ,ρ)\mathcal{V}^{A^\mathrm{op}}(\lambda, \lambda') \cong \mathcal{V}^A(\rho',\rho)

when λρ\lambda \dashv \rho, λρ\lambda' \dashv \rho', which is essentially the statement that the Cauchy completion A˜\tilde{A} has dual descriptions in terms of left adjoint and right adjoint modules. This still ought to be some manifestation of the mate correspondence, though.

Posted by: Tim Campion on February 27, 2014 1:25 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

It’s just the composite of the two isomorphisms I mentioned:

𝒱 A op(λ,λ)=Prof(I,A)(λ1,λ)=Prof(I,I)(1,ρλ)=Prof(A,I)(1ρ,ρ)=𝒱 A(ρ,ρ). \mathcal{V}^{A^{op}}(\lambda,\lambda') = Prof(I,A)(\lambda 1, \lambda') = Prof(I,I)(1,\rho \lambda') = Prof(A,I)(1\rho',\rho) = \mathcal{V}^A(\rho',\rho).

You didn’t mention that you were looking for an isomorphism of hom-objects in 𝒱\mathcal{V} rather than just a bijection of sets (or did you and I just missed it?) but of course it all works just the same for a locally enriched bicategory.

Posted by: Mike Shulman on February 27, 2014 6:04 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Sorry – that was silly of me. I do mean that λρ\lambda \dashv \rho as bimodules, so where I wrote A˜(ya,ρ)\tilde{A}(ya, \rho), I should have written 𝒱 A(A(a,),ρ)\mathcal{V}^A(A(a, -), \rho). So the equation that struck me is A˜(λ,ya)𝒱 A(A(a,),ρ)\tilde{A}(\lambda, ya) \cong \mathcal{V}^A(A(a, -), \rho), or to be more symmetrical,

(*) 𝒱 A op(λ,A(,a))𝒱 A(A(a,),ρ)\mathcal{V}^{A^{\mathrm{op}}}(\lambda, A(-, a)) \cong \mathcal{V}^A(A(a, -), \rho)

when λρ\lambda \dashv \rho as bimodules. It at least checks out when the adjunction is representable: if λρ=A(,a)A(a,)\lambda \dashv \rho = A(-, a') \dashv A(a',-), then both sides reduce by Yoneda to A(a,a)A(a',a).

Claiming that (*) holds is predicated on my wild guess that M(λ,a)M(\lambda, a) should be defined as ρ(a)=𝒱 A(A(a,),ρ)\rho(a) = \mathcal{V}^A(A(a,-), \rho). The right action would be given by ρ\rho’s right action, and I’ve written down something fairly complicated that I think might work as a left action. Even if this works, it still might not be what you had in mind.

Something that I think might be related to (*) is the fact that the Cauchy completion A˜\tilde{A} should have a dual description as the opposite of the category of right adjoint bimodules AIA \nrightarrow I. And there is a third description given in the Betti-Carboni paper that Thomas Holder linked to: the objects of A˜\tilde{A} are adjoint pairs λρ\lambda \dashv \rho and the homs are A˜(λρ,λρ)=ρλ\tilde{A}(\lambda \dashv \rho, \lambda' \dashv \rho') = \rho' \odot \lambda; units are adjunction units, and composition is by counits.

Posted by: Tim Campion on February 25, 2014 10:18 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Regarding Tom’s third remark, I wondered also how far the analogy of 𝒱\mathcal{V} with “truth-values” can be pushed and how fruitful this idea of a “generalized logic” really is. What makes Lawvere’s point of view seem somewhat mysterious to me is that symmetric closed monoidal categories correspond to a very specific logic, namely multiplicative intuitionistic linear logic (MILL). So the internal logic of all categories considered by Lawvere is the same, namely MILL. This fact makes Lawvere’s notion of “generalized logic” hard to understand. (A snappier, but slightly inaccurate, way to say this, thanks to Zhen: MILL is the internal logic of a cosmos.)

Of course the issue here, really, is what is meant by “logic”. Furthermore, Lawvere is concerned not with 𝒱\mathcal{V} itself but with 𝒱\mathcal{V}-enriched categories. So perhaps the “models” of theories over this generalized logic are to be thought of simply and naively as the 𝒱\mathcal{V}-categories themselves? (That still begs the question of what the “theories” are.)

Posted by: Dimitris on February 23, 2014 12:36 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

It’s not clear how rigidly formalized Lawvere intended the word “logic” to be here, but the idea of isolating monoidal closedness (on top of completeness and cocompleteness) as a general assumption on a category of “truth values” in order to do anything mathematically interesting seems reasonable.

If the cosmos VV is playing the role of “truth values”, then VV-CatCat plays a role more similar to SetSet than to anything else. Or perhaps we should add to that and say VV-ProfProf plays the role of RelRel, and then we locate VV-CatCat (or at least the Cauchy-complete VV-CatCat) inside as having the same objects as VV-ProfProf but with the left adjoint 1-cells as morphisms, just as functions between sets are those arrows in RelRel that are left adjoints. (Nowadays we would probably speak in terms of ‘equipments’, but that would be somewhat anachronistic for the early 70’s when the paper was written.)

A ‘theory’ could then take several forms, with the logically simplest ‘algebraic theory’ being something like a (2-)monad on VV-CatCat if we are pursuing this analogy. James Dolan has been urging consideration of ‘doctrines’ which would be to such VV-CatCat as ordinary theories (or their accessible categories of models) would be to SetSet. For example, one could contemplate a ‘doctrine” of finitely monoidally cocomplete categories relative to AbAb-CatCat, and inside such a doctrine we can pick out some of its objects as ‘theories’ in a more conventional sense, for example a generic finitely monoidally cocomplete additive category equipped with a suitable “line object”. His idea is that fundamental constructions and results in algebraic geometry can be profitably understood in such ‘doctrinal’ terms, and this could simplify the learning of modern algebraic geometry by category theorists. You can find some lectures of his (hopefully the videos are still extant) on his nLab web.

Posted by: Todd Trimble on February 24, 2014 12:20 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

If the cosmos VV is playing the role of “truth values”, then V-CatV \text{-}\mathrm{Cat} plays a role more similar to Set than to anything else.

This is one of the things that struck me as odd about the generalized logic idea. If presheaves on a 𝒱\mathcal{V}-category are meant to correspond to properties of elements of a set, then surely 𝒱-Cat\mathcal{V} \text{-}\mathrm{Cat} should correspond to the category of sets. But in order to recover anything resembling standard logic, you have to not only restrict to 𝒱=𝟚\mathcal{V} = \mathbb{2}, but also restrict to considering discrete 𝟚\mathbb{2}-categories. So perhaps the thing that corresponds to Set\mathrm{Set} is really the category of discrete 𝒱\mathcal{V}-categories (which actually is just Set\mathrm{Set}). But it seems strange to introduce enriched category theory as generalized logic, only to immediately throw away the 𝒱\mathcal{V}-categorical structure except when talking about presheaf categories.

Posted by: Tom Avery on February 24, 2014 9:52 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

If you only care about categories up to equivalence, then a set is just a 𝟚\mathbb{2}-enriched groupoid. (A setoid, if you will.) But I’m not so sure what the correct definition of “𝒱\mathcal{V}-enriched groupoid” is for non-cartesian 𝒱\mathcal{V}.

Posted by: Zhen Lin on February 24, 2014 11:33 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Tom, of course you’re right that SetSet merely occurs as a subcategory of 2\mathbf{2}-CatCat (which is equivalent to PosPos or PreordPreord). So it was inaccurate for me to say that VV-CatCat is analogous more to SetSet than to anything else; it’s obviously more closely analogous to PosPos. The main thing I was trying to get at (in that part of my comment) is that in the spirit of the article, a cosmos VV is being viewed more in terms of generalizing a base category of truth values than of a base category of 00-types like SetSet, which is the more traditional view on enriched category theory. This may be highlighted by the fact that the presiding example is that of a commutative quantale [0,][0, \infty] as the base category for metric spaces.

It’s perhaps an obvious remark for anyone who’s read the paper, but it’s an interesting shift in point of view. Originally I thought it might help address Dimitris’s apparent puzzlement as to why MILL was the internal logic of choice here, but after reading the responses I’m even less sure.

Posted by: Todd Trimble on February 24, 2014 2:54 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

One thing to note about metric spaces is that if you look at the underlying poset of most familiar metric spaces, it will be discrete: the only points which have arrows between them are those which are distance 0 apart.

So there’s at least a possibility that Lawvere intends us to generalize sets / discrete posets to enriched categories whose underlying ordinary categories are discrete. But it does seem like non-discrete posets ought to play some role in the whole scheme.

There definitely are people out there who study categories enriched in quantales / quantaloids – maybe someone like that could help clarify the picture?

Posted by: Tim Campion on February 24, 2014 6:13 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Well, sheaves on a site are a special case of \dagger-categories enriched in a quantaloid. So there are lots of other “set-like” categories that can be obtained in such a way. (I prefer to talk about \dagger-categories than groupoids in this context, although they are the same when 𝒱=2\mathcal{V}=2, because the notion of \dagger-category makes sense for arbitrary enrichment whereas the notion of groupoid is difficult to make sense of for non-cartesian enrichment. For instance, when 𝒱=\mathcal{V}=\mathbb{R}, the \dagger-categories are the symmetric metric spaces.)

One possible answer might be that PosPos is actually more basic than SetSet: we should define PosPos first and then find SetSet inside it as the groupoidal or \dagger objects. (-:

Posted by: Mike Shulman on February 24, 2014 8:29 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

The idea of using \dagger-categories as the appropriate notion of “set-like” 𝒱\mathcal{V}-categories is appealing to me because it also gives an explanation of why symmetric metric spaces are important, which seems to be lacking in the categorical view of metric spaces.

I’m not really sure if the following makes sense, I’m just running with Mike’s “Pos\mathrm{Pos} is more basic the Set\mathrm{Set}” idea: Maybe we should think of the elements of a poset as abstract propositions as in propositional logic, together with some implications between them defining the order relation. An order preserving map is an interpretation of one system of propositions in another, and in particular a map to 𝟚\mathbb{2} is an assignment of truth values. We can interpret a groupoidal poset PP as a set by imagining that each proposition pp is of the form x=p 0x = p_0 where xx should be thought of as a free variable ranging over the set, and p 0p_0 as a constant. Then pp and qq are isomorphic in PP iff the constant symbols p 0p_0 and q 0q_0 represent the same elements of the set.

Transferring this to metric spaces, an arbitrary metric space is a set of propositions with fuzzy implications between them, and a symmetric metric space is a set with a fuzzy (but symmetric) equality relation between its elements. The fact that \mathbb{R}-functors are Lipschitz-1 maps says that functions can’t make elements less equal than they already are.

Posted by: Tom Avery on February 25, 2014 2:32 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

I’ve never thought about it quite like that before, but it makes some sense.

Posted by: Mike Shulman on February 25, 2014 7:55 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Todd, thanks for this. You said:

[T]he idea of isolating monoidal closedness (on top of completeness and cocompleteness) as a general assumption on a category of “truth values” in order to do anything mathematically interesting seems reasonable.

I suppose so, but I see no a priori reasons to think that it is a reasonable constraint other than the fact that it is true of the only intuitive example of a “category of truth values”, namely \square. (Perhaps \mathbb{R} is also an intuitive example of “fuzzy” truth values.) \square is a degenerate example of so many other types of categories that taking it as the sole guiding example for a generalization seems like a big leap. This raises the following interesting question: is there any reason to think that MILL is a good candidate for a “logic of truth values”, i.e. a metalogic over which our generalized logic is “enriched”? If there are such reasons, they would provid good evidence to think that the generalization is a good one.

Your point about doctrines, however, also makes me think that Lawvere is generally more interested in logic in the sense of universal algebra rather than “logic” in the more canonical sense of those syntactic entities for which one proves completeness/internal language theorems. E.g. he is interested in categorical frameworks, like doctrines, which allow you to extend algebraic notions such as “monadic”, rather than, say, study generalized quantifiers. This makes sense given his preference for semantic generalizations, rather than syntactic ones that remain bound to a particular presentation. He makes some striking remarks to that effect in one of his recent talks:

What is this notion of algebraic structure [induced by doctrines]? Refuting the idea that an algebraic theory can only arise syntactically, it simultaneously refutes the idea that algebraic theories constitute a ‘new’ or ‘alternative approach’ or ‘categorical counterpart’ to universal algebra; in fact they constitute an essential feature that was long implicitly present, for example in the study of cohomology operations. Of course it is often helpful if, moreover, a presentation can be found for it.

I suppose this accurately describes his attitude towards “doctrinal algebraic geometry”? Unfortunately, the videos you linked to seem to no longer be up. Would any of the powers that be have the power to resurrect them?

Posted by: Dimitris on February 24, 2014 3:32 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Dimitris wrote:

Unfortunately, the videos you linked to seem to no longer be up. Would any of the powers that be have the power to resurrect them?

I thought I was a power that be.

However, someone at U.C. Riverside moved all the videos without telling me, thus breaking all links to them.

When I discovered this, I fixed the links to Jim’s lectures here on my webpage but forgot to do it on Jim’s.

I am unable to fix them on his page, since someone has made it impossible to edit Jim’s wiki— I think Andrew Stacey said he’d do this sort of thing to inactive ‘personal webs’ to reduce spam. If someone active on the nForum raises this issue, it would be easy for the powers that really be to copy my working links over to Jim’s page.

However, there are lots of other broken links like this, since I’d been videoing my seminars for quite a while, and I’m too lazy to find all the webpages that need to be fixed. Just to remind myself, a broken link of either of these forms:

http://mainstream.ucr.edu/baez_04_28_stream.mov

or

http://mediaserve.ucr.edu/baez/baez_04_28_stream.mov

can be updated to a working link like this:

http://pcast.ucr.edu/qts/baez_04_28_stream.mov

Posted by: John Baezb on March 5, 2014 1:19 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Thanks so much for this.

Posted by: Dimitris on March 6, 2014 7:03 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Sorry to come to the party so late! One generalized logic that is worth mentioning in this context is fuzzy logic, where you generalize your truth values to lie in the interval [0,1][0,1] with 00 corresponding to false and 11 corresponding to true. I think what I want to say about this is likely to grow into a post in its own right, but I’d be interested to hear here if anyone’s thought about this.

There are a few ways you can define a tensor product to make the poset [0,1][0,1] into a cosmos (I’m not sure if I like that term) which the cosmos of ordinary truth values embeds, in particular you can take the tensor product to be mulitplication. In that case it is actually isomorphic to ¯ +\overline{\mathbb{R}}_+ via the exponential map. However, the interpretation of categories enriched over [0,1][0,1] is rather different to that of generalized metric spaces. Given a [0,1][0,1]-category CC you can interpret the hom object C(c,c)[0,1]C(c,c')\in [0,1] as the truth degree of a relation between cc and cc'. So if C(c,c)C(c,c') then ccc\le c' definitely; if C(c,c)=0.5C(c,c')=0.5 then it’s somewhat true that ccc\le c' and if C(c,c)=0C(c,c')=0 then it is definitely not true that ccc\le c'.

Posted by: Simon Willerton on March 1, 2014 5:47 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

There’s a short list of cosmoi (Thanks, Zhen for pointing out this name!) for which I know what Cauchy completion / adjoint bimodules from II / absolute colimit weights amount to.

  • When 𝒱=Set\mathcal{V}= \mathbf{Set}, the Cauchy completion is the idempotent completion.

  • When 𝒱=\mathcal{V} = \mathbb{R}, the Cauchy completion is the completion under Cauchy sequences.

  • When 𝒱=Ab\mathcal{V} = \mathbf{Ab}, the Cauchy completion is the completion under idempotents and finite sums.

  • When 𝒱=\mathcal{V} = a certain locally cocomplete bicategory constructed from a site, a Cauchy complete symmetric 𝒱\mathcal{V}-category is a sheaf.

That last one is pretty sketchy, and involves generalizing to enrichment in 𝒱\mathcal{V} a bicategory.

What other 𝒱\mathcal{V} have nice characterizations of Cauchy completion? What about Cat\mathbf{Cat}? SSet\mathbf{SSet}? Quantales other than \mathbb{R}? “Commutative algebra” categories other than Ab\mathbf{Ab}? I think I’ve read before that there’s some size issue related to Cauchy completion when 𝒱\mathcal{V} is suplattices, but I don’t remember exactly what it was.

Maybe we could create a nice list to add to the nlab page.

Posted by: Tim Campion on February 25, 2014 10:46 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Yes, we should collect a list of these!

For cartesian monoidal enrichment like CatCat and sSetsSet, I think the Cauchy completion is usually just idempotent-splitting. I don’t offhand know a precise theorem along those lines, though.

You’re right about suplattices: the Cauchy completion of a SupSup-enriched category ought to be its completion under idempotent-splitting and arbitrary sums — it’s just like for AbAb, except that now you can “add” (i.e. take the join of) infinitely many things. In particular, no small SupSup-enriched category is Cauchy complete. Whether a large one can be Cauchy complete may depend a little on how you set up the definitions.

Here’s another nice example in the same spirit as your last one: when we enrich in the bicategory of spans in a category SS with pullbacks, then a Cauchy complete enriched category is a locally small SS-indexed category (i.e. a pseudofunctor S opCatS^{op}\to Cat whose “homsets are representable in SS”) with split idempotents. The original paper about this one is called Variation through enrichment. By suitably modifying the bicategory in question when SS is a site, you can also get “stacks with split idempotents”.

This last example suggests that there’s some interest in considering “sub-Cauchy completions”, i.e. completions under some absolute colimits but not all of them. For instance, one can isolate a class Φ\Phi of absolute colimits for which Φ\Phi-cocomplete Span(S)Span(S)-categories are exactly locally small SS-indexed categories (not necessarily with split idempotents). One can also describe stacks, separated presheaves, and prestacks in this way. (Although I would argue that it’s better to consider categories enriched in a double category than enriched in a bicategory, in which case no cocompleteness condition at all is necessary to describe indexed categories, separated presheaves, or prestacks.)

Another example of sub-Cauchy completion comes from categorifying in a different direction, considering bicategories enriched in a monoidal bicategory. The 2-category ColimColim of cocomplete categories is a “2-cosmos”, and there’s a class Φ\Phi of absolute colimits such that the Φ\Phi-cocompletion of a bicategory 𝒲\mathcal{W} is the bicategory Prof(𝒲)Prof(\mathcal{W}) of 𝒲\mathcal{W}-enriched categories.

The last example I can think of off the top of my head right now is in homotopy theory: when we enrich in the (,1)(\infty,1)-cosmos of spectra, then all finite colimits are absolute. Thus, the Cauchy completion is a completion under direct sums, split idempotents, and also cofibers.

Posted by: Mike Shulman on February 26, 2014 9:26 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

The key step in Emily’s proof from Borceux-Dejean showing that the Cauchy completion in Set\mathbf{Set} is the idempotent completion comes in converting the unit η:1 cGc×Fc\eta: 1 \to \int^c Gc \times Fc into a point 1Fc×Gc1 \to Fc \times Gc for some cc (which is then seen to specify a retract of cc). This follows from the fact that Set(1,)\mathbf{Set}(1, -) preserves colimits, i.e. 11 is tiny. So I believe that the Cauchy completion will be the idempotent completion for any cartesian cosmos 𝒱\mathcal{V} such that the unit is tiny. This includes Cat\mathbf{Cat} and sSet\mathbf{sSet}.

Another example of a sub-Cauchy completion that comes to mind is completing from a pre-additive category (= Ab\mathbf{Ab}-enriched category) to an additive category (=Ab\mathbf{Ab}-enriched category with finite sums).

I asked about examples like this in the spirit of a “mathematical tourist”, and as a tourist, the example of spectra is particularly intriguing. If all finite colimits to be absolute (and dually, all finite limits must be absolute, I suppose?), then they must be very nice to work with!

Posted by: Tim Campion on February 28, 2014 11:24 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

If we take our favorite definition of metric space (either Lawvere’s or the standard stupid one) and change the triangle inequality

d(x,z)d(x,y)+d(y,z) d(x,z) \le d(x,y) + d(y,z)

to

d(x,z)max[d(x,y),d(y,z)] d(x,z) \le max \left[ d(x,y), d(y,z) \right]

we get a definition of ultrametric space. Has someone written about ultrametric spaces as categories enriched over [0,][0,\infty] with maxmax rather than ++ as its tensor product?

I can imagine Simon Willerton writing about this and max-plus algebra.

Okay, yes: googling “willerton ultrametric” takes me to his paper Tight spans, Isbell completions and semi-tropical modules, where he writes:

H.-P.A. Künzi and Olela Otafudu [17] define a directed tight span for generalized ultra-metric spaces; generalized ultra-metric spaces can be viewed as categories enriched over [0,][0,\infty] with max the monoidal product: is the directed span the Isbell completion in this context?

Is there anything more than this one sentence?

I’ve gotten interested in this stuff because of the mysterious relation between the space of phylogenetic trees and tropical algebra. It seems ultrametric spaces could explain the link, since a phylogenetic tree gives an ultrametric space and an ultrametric space gives a category enriched over ([0,],max)([0,\infty], max), which in turn is related to the tropical rig. But I don’t see how it all fits together.

Posted by: John Baez on February 27, 2014 10:33 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Has someone written about ultrametric spaces as categories enriched over [0,][0,\infty] with maxmax rather than ++ as its tensor product?

In the context of magnitude, Tom wrote a bit here, I wrote more in a comment, and the content of that comment was written more formally in the last section of this paper. But I don’t know that this sheds any light on phylogenetic trees.

Posted by: Mark Meckes on February 27, 2014 11:48 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Is there anything more than this one sentence?

Probably Lawvere observed in his article that max\max is the cartesian product and [0,][0, \infty] is cartesian closed (if he doesn’t say what the exponential is, it’s a good but easy exercise to work out by hand).

It may be on the obvious side, but one remark is that there is a family of closed monoidal structures on [0,][0, \infty] where the tensor is given by x py=(x p+y p) 1/px \otimes_p y = (x^p + y^p)^{1/p}, and the max\max product is the limit as pp approaches infinity.

The max\max product also has a kind of ‘tropical’ feel to it, and interestingly, David Speyer and Bernd Sturmfels mention phylogenetic trees in their article in Mathematics Magazine.

Posted by: Todd Trimble on February 27, 2014 12:27 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

I used to teach our third and fourth year students about two subjects dear to John’s heart, namely Petri nets and, in particular, timed Petri nets as discrete event systems. The latter are studied by converting the awkward max, min equations that arise in the modelling into neat linear equations over (max,+)(max,+). The theory is very pretty but quite powerful. (It would make a good course for some good students, and a good source for ideas for student projects.) In the course at Bangor, we did not treat the categorical aspects, but that might be a good area to explore.

Posted by: Tim Porter on February 28, 2014 6:44 AM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

John, here’s a few thoughts. [Note that due to my conventions, what I’ve written might need max changed to min or the introduction of some minus signs to make it agree with what Sturmfels writes.]

Firstly, tropical things involve both max\max (or min\min) and ++ so I would suspect that you want to consider enriching over [0,][0,\infty] with ++ as the monoidal product, you will still have max\max as the categorical product. If you enrich using max\max as the monoidal product, where will you get ++ from in the tropical semiring?

If you’re enriching over [0,][0,\infty] then you probably will deal with what I call the semi-tropical semiring, namely ([0,],max,+)([0,\infty],\max,+) so it’s half the usual tropical semiring. For instance, I have a theorem that says that a generalized metric is complete as a ([0,],+)([0,\infty],+)-category precisely when it is a module for the semitropical semi-ring, where the action is appropriately compatible with the metric.

As for the connection between tropical methods and phylogenetic trees, I’ll try to describe what I know.

One way to build a phylogenetic tree is to start with the set of modern-day species you want to build the tree of and find some appropriate distances between the species. This might be some form of genetic distance, for instance. The distance between two species, you hope, should be proportional to the time since they split from a common ancestor.

The problem of finding a phylogenetic tree is then the problem of finding a tree with the species as leaves, where the distance between the species using the tree metric is the same as the metric you had previously measured. To put it another way, you need to find a tree in which your metric space of species embeds isometrically.

There is a particularly nice ‘continuous’ metric space in which a finite metric space canonically embeds, it is called the tight span or the hyperconvex hull and it is a finite dimensional cell complex. Isbell is possibly the first person who wrote it down, but Dress rediscovered it in the 1980s. The important fact here is that a metric space embeds isometrically in a tree if and only if its tight span is a tree. You can view the tight span as the closest you can get to embedding the metric space in a tree. So the tight span is like a best approximation to a phylogenetic tree for the metric you’ve picked on your species.

Here are the tight spans of generic three and four point metric spaces.

Some tight spans

There is classical theorem, due to Buneman in 1972 and Zaretsky in 1965, which gives a condition which is equivalent to your metric space embedding in a tree (or the tight span being a tree if you prefer); this is the four-point condition.

Four point condition For XX a metric space, the four point condition is that for every x,y,z,wXx,y,z,w\in X we have d(x,y)+d(z,w)max{d(x,z)+d(y,w),d(x,w)+d(y,z)}.d(x,y)+d(z,w)\le max\{ d(x,z)+d(y,w),\,\, d(x,w)+d(y,z)\}. This is equivalent to saying that the maximum of the set {d(x,y)+d(z,w),d(x,z)+d(y,w),d(x,w)+d(y,z)}\{d(x,y)+d(z,w),\,\, d(x,z)+d(y,w),\,\, d(x,w)+d(y,z)\} is attained at two of the points.

We want to make some connection between this and the tropical semiring. I know two ways of doing this, but I’m not sure how related they are.

The first is described in the Speyer-Sturmfels paper you mention. Writing \oplus for max\max and \odot for ++ in the tropical fashion, the maximum of the set mentioned in the four point condition becomes the following, where I’ve bracketed for clarity.

(d(x,y)d(z,w))(d(x,z)d(y,w))(d(x,w)d(y,z))(d(x,y)\odot d(z,w)) \oplus (d(x,z)\odot d(y,w)) \oplus (d(x,w)\odot d(y,z))

This is a tropical quadratic polynomial. The roots of a tropical polynomial are taken to be the places where the maximum is attained by at least two of the terms. So the four point condition is that the distances between any four points in the space are roots of this quadratic equation. This is analogous to the quadratic condition satisfied by the image of the Plücker embedding of the Grassmannian, so the above tropical quadratic polynomial is called the tropical Grassmann-Plücker relation.

I do not know, and have not thought about, how to relate this to enriched category theory.

The second way to make some connection between phylogenetic trees and the tropical semiring I do know how to relate to enriched category theory. This goes back to Develin and Sturmfels paper Tropical Convexity. Associated to a finite set of vectors in n\mathbb{R}^n they constructed the tropical convex hull of the set, this is in fact the same as the set of tropical linear combinations of the vectors. If you take a metric space XX then take the set of row (or column) vectors of the matrix of distances, then you can form the associated tropical convex hull. In their paper they ‘prove’ that this tropical convex hull is \mathbb{R} times the tight span of the metric space. This is not true and they had to publish an erratum for this result. It is true when the tight span is a tree though.

How does this relate to enriched category theory? It is a fact that I hope will appear in my student Jonathan Elliott’s PhD thesis, that up to certain mild caveats, the tropical convex hull they associated to a metric space is the ‘Isbell completion’ of the metric space considered as a ([,],+)([-\infty,\infty],+)-category. All you need to know at this point is that the Isbell completion is a categorical construction.

In my paper on Isbell completions I looked at the Isbell completion of metric spaces considered as ([0,],+)([0,\infty],+)-categories. This Isbell completion is a generalized metric space (ie a non-symmetric metric space); the largest submetric space of this which contains the original metric space and which is actually symmetric is nothing other than the tight span.

I’ve gone on rather a lot and hand-waved rather a lot, but can happily expand on bits if needed.

Posted by: Simon Willerton on March 2, 2014 12:51 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Thanks a lot, Simon! All this is very helpful. It will take me a while to digest it and think of something interesting to say. Something nice is clearly at work here.

Posted by: John Baez on March 5, 2014 1:37 PM | Permalink | Reply to this

Re: Metric Spaces, Generalized Logic, and Closed Categories

Todd said

Probably Lawvere observed in his article that max\max is the cartesian product and [0,][0, \infty] is cartesian closed.

Indeed he did. I came across the exponential (ie the internal hom) recently and was really surprised that I hadn’t seen it before, but I went back to Lawvere’s paper, which I’ve read many times, and found that there it was!

Posted by: Simon Willerton on March 2, 2014 12:53 PM | Permalink | Reply to this
Read the post Fuzzy logic and enriching over the category [0,1]
Weblog: The n-Category Café
Excerpt: Watch me try to understand fuzzy logic from an enriched category theory perspective
Tracked: March 15, 2014 6:00 PM

Post a New Comment