## August 2, 2014

### Wrestling with Tight Spans

#### Posted by Tom Leinster

I’ve been spending some time with Simon Willerton’s paper Tight spans, Isbell completions and semi-tropical modules. In particular, I’ve been trying to understand tight spans.

The tight span of a metric space $A$ is another metric space $T(A)$, in which $A$ naturally embeds. For instance, the tight span of a two-point space is a line segment containing the original two points as its endpoints. Similarly, the tight span of a three-point space is a space shaped like the letter Y, with the original three points at its tips. Because of examples like this, some people like to think of the tight span as a kind of abstract convex hull.

Simon’s paper puts the tight span construction into the context of a categorical construction, Isbell conjugacy. I now understand these things better than I did, but there’s still a lot I don’t get. Here goes.

Simon wrote a blog post summarizing the main points of his paper, but I want to draw attention to slightly different aspects of it than he does. So, much as I recommend that post of his, I’ll make this self-contained.

We begin with Isbell conjugacy. For any small category $A$, there’s an adjunction

$\check{\,\,}: [A^{op}, Set] \leftrightarrows [A, Set]^{op}: \hat{\,\,}$

defined for $F: A^{op} \to Set$ and $b \in A$ by

$\check{F}(b) = Hom(F, A(-, b))$

and for $G: A \to Set$ and $a \in A$ by

$\hat{G}(a) = Hom(G, A(a, -)).$

We call $\check{F}$ the (Isbell) conjugate of $F$, and similarly $\hat{G}$ the (Isbell) conjugate of $G$.

Like any adjunction, it restricts to an equivalence of categories in a canonical way. Specifically, it’s an equivalence between

the full subcategory of $[A^{op}, Set]$ consisting of those objects $F$ such that the canonical map $F \to \hat{\check{F}}$ is an isomorphism

and

the full subcategory of $[A, Set]^{op}$ consisting of those objects $G$ such that the canonical map $G \to \check{\hat{G}}$ is an isomorphism.

I’ll call either of these equivalent categories the reflexive completion $R(A)$ of $A$. (Simon called it the Isbell completion, possibly with my encouragement, but “reflexive completion” is more descriptive and I prefer it now.) So, the reflexive completion of a category consists of all the “reflexive” presheaves on it — those canonically isomorphic to their double conjugate.

All of this categorical stuff generalizes seamlessly to an enriched context, at least if we work over a complete symmetric monoidal closed category.

For example, suppose we take our base category to be the category $Ab$ of abelian groups. Let $k$ be a field, viewed as a one-object $Ab$-category. Both $[k^{op}, Ab]$ and $[k, Ab]$ are the category of $k$-vector spaces, and both $\check{\,\,}$ and $\hat{\,\,}$ are the dual vector space construction. The reflexive completion $R(k)$ of $k$ is the category of $k$-vector spaces $V$ for which the canonical map $V \to V^{\ast\ast}$ is an isomorphism — in other words, the finite-dimensional vector spaces.

But that’s not the example that will matter to us here.

We’ll be thinking primarily about the case where the base category is the poset $([0, \infty], \geq)$ (the reverse of the usual order!) with monoidal structure given by addition. As Lawvere observed long ago, a $[0, \infty]$-category is then a “generalized metric space”: a set $A$ of points together with a distance function

$d: A \times A \to [0, \infty]$

satisfying the triangle inequality $d(a, b) + d(b, c) \geq d(a, c)$ and the equaiton $d(a, a) = 0$. These are looser structures than classical metric spaces, mainly because of the absence of the symmetry axiom $d(a, b) = d(b, a)$.

The enriched functors are distance-decreasing maps between metric spaces: those functions $f: A \to B$ satisfying $d_B(f(a_1), f(a_2)) \leq d_A(a_1, a_2)$. I’ll just call these “maps” of metric spaces.

If you work through the details, you’ll find that Isbell conjugacy for metric spaces works as follows. Let $A$ be a generalized metric space. The conjugate of a map $f: A^{op} \to [0, \infty]$ is the map $\check{f}: A \to [0, \infty]$ defined by

$\check{f}(b) = sup_{a \in A} max \{ d(a, b) - f(a), 0 \}$

and the conjugate of a map $g: A \to [0, \infty]$ is the map $\hat{g}: A^{op} \to [0, \infty]$ defined by

$\hat{g}(a) = sup_{b \in A} max \{ d(a, b) - g(b), 0 \}.$

We always have $f \geq \hat{\check{f}}$, and the reflexive completion $R(A)$ of $A$ consists of all maps $f: A^{op} \to [0, \infty]$ such that $f = \hat{\check{f}}$. (Although you could write out an explicit formula for that, I’m not convinced it’s much help.) The metric on $R(A)$ is the sup metric.

All that comes out of the general categorical machinery.

However, we can say something more that only makes sense because of the particular base category we’re using.

As we all know, symmetric metric spaces — the ones we’re most used to — are particular interesting. For a symmetric metric space $A$, the distinction between covariant and contravariant functors on $A$ vanishes. The two kinds of conjugate, $\hat{\,\,}$ and $\check{\,\,}$, are also the same. I’ll write ${}^\ast$ for them both.

The reflexive completion $R(A)$ consists of the functions $A \to [0, \infty]$ that are equal to their double conjugate. But because there is no distinction between covariant and contravariant, we can also consider the functions $A \to [0, \infty]$ equal to their single conjugate.

The set of such functions is — by definition, if you like — the tight span $T(A)$ of $A$. So

$T(A) = \{ f : A \to [0, \infty] \,|\, f = f^\ast \},$

while

$R(A) = \{ f: A \to [0, \infty] \,|\, f = f^{\ast\ast} \}.$

Both come equipped with the sup metric, and both contain $A$ as a subspace, via the Yoneda embedding $a \mapsto d(-, a)$. So $A \subseteq T(A) \subseteq R(A)$.

Example Let $A$ be the symmetric metric space consisting of two points distance $D$ apart. Its reflexive completion $R(A)$ is the set $[0, D] \times [0, D]$ with metric $d((s_1, s_2), (t_1, t_2)) = max \{ t_1 - s_1, t_2 - s_2, 0 \}.$ The Yoneda embedding identifies the two points of $A$ with the points $(0, D)$ and $(D, 0)$ of $R(A)$. The tight span $T(A)$ is the straight line between these two points of $R(A)$ (a diagonal of the square), which is isometric to the ordinary Euclidean line segment $[0, D]$.

As that example shows, the reflexive completion of a space needn’t be symmetric, even if the original space was symmetric. On the other hand, it’s not too hard to show that the tight span of a space is always symmetric. Simon’s Theorem 4.1.1 slots everything into place:

Theorem (Willerton) Let $A$ be a symmetric metric space. Then the tight span $T(A)$ is the largest symmetric subspace of $R(A)$ containing $A$.

Here “largest” means that if $B$ is another symmetric subspace of $R(A)$ containing $A$ then $B \subseteq T(A)$. It’s not even obvious that there is a largest one. For instance, given any non-symmetric metric space $C$, what’s the largest symmetric subspace of $C$? There isn’t one, just because every singleton subset of $C$ is symmetric.

Simon’s told the following story before, but I can’t resist telling it again. Tight spans have been discovered independently many times over. The first time they were discovered, they were called by the less catchy name of “injective envelope” (because $T(A)$ is the smallest injective metric space containing $A$). And the person who made that first discovery? Isbell — who, as far as anyone knows, never noticed that this had anything to do with Isbell conjugacy.

Let me finish with something I don’t quite understand.

Simon’s Theorem 3.1.4 says the following. Let $A$ be a symmetric metric space. (He doesn’t assume symmetry, but I will.) Then for any $a \in A$, $p \in R(A)$ and $\varepsilon \gt 0$, there exists $b \in A$ such that

$d(a, p) + d(p, b) \leq d(a, b) + \varepsilon.$

In other words, $a$, $p$ and $b$ are almost collinear.

A loose paraphrasing of this is that every point in the reflexive completion of $A$ is close to being on a geodesic between points of $A$. The theorem does imply this, but it says a lot more. Look at the quantification. We get to choose one end $a$ of the not-quite-geodesic, as well as the point $p$ in the reflexive completion, and we’re guaranteed that if we continue the not-quite-geodesic from $a$ on through $p$, then we’ll eventually meet another point of $A$ (or nearly).

Let’s get rid of those “not quite”s, and at the same time focus attention on the tight span rather than the reflexive completion. Back in Isbell’s original 1964 paper (cited by Simon, in case you want to look it up), it’s shown that if $A$ is compact then so is its tight span $T(A)$. Of course, Simon’s Theorem 3.1.4 applies in particular when $p \in T(A)$. But then compactness of $T(A)$ means that we can drop the $\varepsilon$.

In other words: let $A$ be a compact symmetric metric space. Then for any $a \in A$ and $p \in T(A)$, there exists $b \in A$ such that

$d(a, p) + d(p, b) = d(a, b).$

So, if you place your pencil at a point of $A$, draw a straight line from it to a point of $T(A)$, and keep going, you’ll eventually meet another point of $A$.

This leaves me wondering what tight spans of common geometric figures actually look like.

For example, take an arc $A$ of a circle — any size arc, as long as it’s not the whole circle. Embed it in the plane and give it the Euclidean metric. I said originally that the tight span is sometimes thought of as a sort of abstract convex hull, and indeed, the introduction to Simon’s paper says that some authors have actually used this name instead of “tight span”. But the result I just stated makes this seem highly misleading. It implies that the tight span of $A$ is not its convex hull, and indeed, can’t be any subspace of the Euclidean plane (unless, perhaps, it’s $A$ itself, which I suspect is not the case). But what is it?

A lot of people who use tight spans are doing so in contexts such as combinatorial optimization and phylogenetic analysis where the metric spaces that they start with are finite. So they don’t treat examples such as arcs, circles, triangles, etc. Has anyone ever computed the tight spans of common geometric shapes?

Posted at August 2, 2014 3:31 AM UTC

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

### Re: Wrestling with Tight Spans

There is a passing resemblance between the formula for the Isbell conjugate and the Legendre transform ($f^*(p) = \sup(p\cdot x - f(x))$). Is there anything more than a passing resemblance? The Legendre transform is a certain tropicalization of the Fourier transform, and Simon has discussed connections between the tight span and tropical geometry, so another way to pose my question is whether any of the players has a more-than-passing resemblance to the Fourier transform.

Posted by: Theo on August 2, 2014 5:04 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Theo, I’ve written about the Legendre transform here and here, and I’m in process of finishing a paper on it. Both the Isbell conjugate and the Legendre-Fenchel transform arise as adjunctions coming from profunctors in the same way (see the links for more details). I haven’t been able to express the Fourier transform in this way. I seem to remember(?!) that the problem is that a need a closed monoidal category to enrich over which had the real (or complex?) numbers as its objects and addition as categorical product.

Posted by: Simon Willerton on August 2, 2014 9:00 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Tom said

the introduction to Simon’s paper says that some authors have actually used this name [“convex hull”] instead of “tight span”

This was Chrobak and Larmore in their paper Generosity Helps or an 11-Competitive Algorithm for Three Servers; they rediscovered the Isbell completion in a computer science context.

Actually the name “hyperconvex hull” would be appropriate. Hyperconvexity is a metric space version of convexity which turns out is the same thing as “injective” in the metric space context. For instance $\mathbb{R}^2$ with the Euclidean metric is not hyperconvex, but with the $L_1$ metric it is. David Eppstein has a nice talk on Hyperconvexity and metric embedding.

Posted by: Simon Willerton on August 2, 2014 10:10 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

The tight span looks like it should make sense for a $V$-category, for any $V$, if it is isomorphic (or equivalent) to its opposite. For instance, a $\dagger$-category or a groupoid. Is it interesting for other enrichments?

Posted by: Mike Shulman on August 2, 2014 8:23 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

I’m not sure it does make sense except when $V$ is a poset (or a preorder). At least, I can’t see how to make it make sense.

We want to define the tight span of a self-dual $V$-category $A$ to be the category of presheaves $F$ on $A$ such that $F$ is “the same as” $F^\ast$. The trouble is, there’s no canonical natural transformation $F \to F^\ast$ or $F^\ast \to F$, so we can’t take “the same as” to mean that this (non-existent) natural transformation is invertible. And it’s probably not going to be fruitful to consider the category of presheaves $F$ for which there is merely some isomorphism between $F$ and $F^\ast$.

When $V$ is a poset, however, we can ask that $F$ and $F^\ast$ are actually equal. So there are two special things about the metric space case: (i) that the base category $V$ is a poset, and (ii) that self-dual $V$-categories are of particular interest. I haven’t been able to think of any other $V$s for which both (i) and (ii) hold.

Posted by: Tom Leinster on August 2, 2014 11:39 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Okay, now I’m no longer convinced that the tight span makes sense even in the posetal case.

I was about to say that while it would certainly be weird to talk about presheaves for which there exists an isomorphism $F\cong F^\ast$, the category of presheaves equipped with an isomorphism $F\cong F^\ast$ seems more natural. But the only way to define morphisms that take account of those isomorphisms isn’t going to reproduce the tight span.

Put differently, what’s going on is that you have an isomorphism $A\cong A^{op}$ yielding an isomorphism $[A^{op},V] \cong [A,V]$, and composition of the conjugate $[A,V] \to [A^{op},V]^{op}$ with this isomorphism yields… a functor $[A,V] \to [A,V]^{op}$. Now you’re trying to talk about “fixed points” of this functor, but it’s not an endofunctor! It just so happens that its domain and codomain have the same set of objects, but looking at the “fixed objects” and arbitrarily considering them as a full subcategory of the domain seems like a strikingly uncategorical thing to do, whether or not $V$ is a poset.

Posted by: Mike Shulman on August 3, 2014 6:51 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

I see what you mean. That’s puzzling. On the one hand, what you say makes the tight span construction seem questionable from a categorical point of view. On the other, there’s social evidence that it’s a natural construction: namely, that it’s been rediscovered several times in several contexts.

As I mentioned in the post, Isbell characterized the tight span $T(A)$ of a (symmetric) metric space $A$ as its “injective envelope”. The precise definitions are as follows.

A metric space $A$ is injective if for any metric space $B$, subspace $C \subseteq B$, and map $f: C \to A$, there exists an extension of $f$ to the whole of $B$. (By “map” I still mean distance-decreasing map.)

An injective envelope of a metric space $A$ is a space $E$ together with a map $i: A \to E$ such that $E$ is injective, $i$ is an isometry, and no injective proper subspace of $E$ contains $i(A)$.

Two injective envelopes $i: A \to E$, $j: A \to F$ are equivalent if there exists an isometry $k: E \to F$ such that $k i = j$.

Isbell proves that every metric space $A$ has an injective envelope, and that any two injective envelopes of $A$ are equivalent. But he doesn’t prove that there’s a unique equivalence between any two injective envelopes of $A$, and I guess that’s false.

As the $n$Lab page points out, this means that the tight span/injective envelope construction isn’t functorial in any sensible way. David also wrote about this back here.

Posted by: Tom Leinster on August 3, 2014 7:28 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Of course, all this brings to mind injective hulls and their nonfunctoriality. See page 156 (and surrounding text) in Abstract and Concrete Categories; this includes many constructions such as algebraic closure, injective envelopes of metric spaces, Dedekind-MacNeille completions, and the like.

This type of thing has caused me to stumble in the past, including for example here, which gives me a guilty feeling every time I think of it.

Posted by: Todd Trimble on August 3, 2014 9:46 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Ah, Todd, yes, my student Jonathan Elliot spent a while thinking about what you wrote there and never quite managed to pin it down. That explains it… I think he learned a lot in the process though.

I gave a different proof of completeness and cocompleteness in the posetal case in my paper, though possibly there are more obvious proofs to the categorical cognoscenti.

Posted by: Simon Willerton on August 4, 2014 9:18 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

What did we learn from that discussion?

Wasn’t it something like that you should take the groupoid of all injective hulls together, e.g., all algebraic completions? Then, forming injective hulls generally sends you out of the category you were considering.

Is it possible that forming the tight span should morally send you to a different category, but that you non-naturally identify this back to the original category?

And, what was Batanin saying here?

Posted by: David Corfield on August 5, 2014 11:00 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Well, returning to that spot, it seems that was the firstish thing that occured to me, and then there was a lot more talk, mirth as much as math.

One suggestion David Roberts makes

but surely the (separable?) algebraic closure $\overline{k}$ of $k$ sits in the topos of $Gal(\overline{k}/k)$-sets?

sounds like the concisest way one can say the same thing, modulo the caveat that the group $Gal(\overline{k}/k)$ depends on the choice of $\overline{k}$ just as much as $\overline{k}$ itself does; one has almost exactly the same story as is found with fundamental groups/basepoints, and for very good reasons, and looking instead at deck transformation groups changes this not at all.

Now-a-days, in a Univalent setting we can say “the Type of algebraic closures is not contractible”.

Posted by: Jesse C. McKeown on August 5, 2014 3:57 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Well, one should consider the groupoid $\Pi_1(Spec(k))$ of fibre functors, rather than the group of automorphisms of a single fibre functor (ie a point of the topos).

Posted by: David Roberts on August 6, 2014 12:12 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Yes.

Posted by: Jesse C. McKeown on August 6, 2014 2:24 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

All of that makes sense for an arbitrary enriching $V$, if you replace “subspace” by “full subcategory” and “isometry” by “fully faithful functor”. Do such gadgets exist, and are they related to the reflexive completion?

Posted by: Mike Shulman on August 6, 2014 6:33 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

The language of ‘tightness’ comes up elsewhere in the context of completions of enriched categories, as in Tightly bounded completions. But do I take it from what’s been said that this is all too ‘natural’ to have a chance to apply to tight spans?

Posted by: David Corfield on August 6, 2014 10:17 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

It’s only just occurred to me, so I’ll say it in case anyone else is confused: there seem to be two different constructions named after Isbell which both have to do with some sort of presheaf-copresheaf duality! Tom’s post / Simon’s paper talk about the Isbell / reflexive completion: the equivalence at the core of the Isbell conjugacy adjunction. Then there’s the Isbell envelope, which looks naively like a much larger completion – at least it requires more data to specify an object (a presheaf, a copresheaf, and a natural transformation). This latter was the subject of Richard Garner’s talk at the CT this year. Are these two constructions at all related?

The naming seems particularly unfortunate to me: if I have an “envelope” and a “completion” lying around, I expect the envelope to be the smaller one, but the situation appears to be more the reverse.

On a side note: I think there’s a typo in the post, just before the example of the two-point space. It should be $A\subseteq T(A) \subseteq R(A)$.

Posted by: Tim Campion on August 3, 2014 5:46 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Actually, I like completed forms to fit in the envelopes I have; it’s tricky to mail them off, otherwise.

Posted by: Jesse C. McKeown on August 3, 2014 2:37 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Thanks for spotting the typo. It’s fixed now.

Yes, the Isbell completion and envelope are related. My student Tom Avery looked into this for a little while, and may if we’re lucky pop up here and explain it to us.

But here’s a quick and simple something. Suppose we have a presheaf $F$ and a copresheaf $G$ on a category $A$. Isbell conjugacy says that natural transformations

$F \to \hat{G}$

are the same as natural transformations

$G \to \check{F}.$

One way to prove that is to show that both things are the same as natural transformations

$F \times G \to Hom_A$

where $F \times G: A^{op} \times A \to Set$ is defined by $(F \times G)(a, b) = F(a) \times G(b)$.

The Isbell envelope of $A$ consists of triples $(F, G, \theta)$ where $F$ is a presheaf, $G$ is a copresheaf, and $\theta$ is a thing of the kind I’ve just described in three ways: a transformation $F \to \hat{G}$, or equivalently a transformation $G \to \check{F}$, or equivalently a transformation $F \times G \to Hom_A$.

Another point is that the Isbell envelope of a small category $A$ contains both $[A^{op}, Set]$ and $[A, Set]^{op}$, whereas the Isbell/reflexive completion is contained in both $[A^{op}, Set]$ and $[A, Set]^{op}$. So as you say, the envelope is much bigger than the completion.

Posted by: Tom Leinster on August 3, 2014 3:17 PM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

To elaborate slightly on what Tom said:

Writing $E(A)$ for the Isbell envelope of a small category $A$ and $R(A)$ for the reflexive completion, the inclusion $[A^{\mathrm{op}},\mathbf{Set}] \to E(A)$ is given by $X \mapsto (X, \check{X})$ with the obvious natural transformation $X \times \check{X} \to A(-,-)$.

The inclusion $[A,\mathbf{Set}]^{\mathrm{op}} \to E(A)$ is similar. In fact these inclusions have a right and left adjoint respectively, given by the obvious forgetful functors. Also the intersection of $[A^{\mathrm{op}},\mathbf{Set}]$ and $[A,\mathbf{Set}]^{\mathrm{op}}$ inside $E(A)$ is precisely $R(A)$.

These are all constructions that work for an arbitrary adjunction: Given $L \dashv R \colon C \rightleftarrows D$, the category $(L \downarrow D) \cong (C \downarrow R)$ contains $C$ as a coreflective subcategory and $D$ as a reflective subcategory, and their intersection is the “invariant part” of the adjunction that Tom mentioned. It’s worth noting that the description of objects of $E(A)$ in terms of natural transformations into $A(-,-)$ is one thing that doesn’t generalise to this context.

Posted by: Tom Avery on August 4, 2014 11:20 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

Interesting. So both the Isbell envelope and the reflexive completion arise from very general constructions that turn an adjunction into a category. What sort of functorality properties do these constructions have?

Both are certain weighted 2-limits: Consider an adjunction $L \dashv R : C \rightleftarrows D$ with unit $\eta$ and counit $\epsilon$. Then the “envelope” of the adjunction is, as Tom says, a comma category in two different ways, $(L \downarrow D) \cong (C \downarrow R)$. On the other hand, the “core” of the adjunction is an inverter in two different ways, $\mathsf{Inv}(\eta) \cong \mathsf{Inv}(\epsilon)$. Both limits are defined over subdiagrams of the adjunction itself, regarded as a 2-functor $\mathbb{A} \to \mathsf{Cat}$, where $\mathbb{A}$ is the free adjunction. So I suspect they can be exhibited as limits of this 2-functor $\mathbb{A} \to \mathsf{Cat}$ with respect to different weights.

So I think these are two 2-functors $[\mathbb{A}, \mathsf{Cat}] \to \mathsf{Cat}$. Which leads to several more questions…

1. What does the 2-category $[\mathbb{A}, \mathsf{Cat}]$ look like? It has adjunctions for objects and some kind of squares between the adjunctions for morphisms, but I’m not clear on what kind of commutativity constraints these must satisfy. How is it related to the double category whose vertical 1-cells are adjunctions and horizontal 1-cells are functors?

2. Are there other situations where two different weights over the same 2-category / enriched category yield isomorphic limits?

3. Is there anything particularly canonical about these two 2-functors? Is either of them adjoint to the functor $\mathsf{Cat} \to [\mathbb{A},\mathsf{Cat}]$ sending a category to the identity adjunction?

Posted by: Tim Campion on August 5, 2014 4:10 AM | Permalink | Reply to this

### Re: Wrestling with Tight Spans

I started an nLab entry nucleus of a profunctor. If anyone has some juicy, unexpected examples, please tell us. I’ve already nabbed Tom’s one about finite-dimensional vector spaces over a field.

Posted by: David Corfield on August 5, 2014 5:41 PM | Permalink | Reply to this

Post a New Comment