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.

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 AA is another metric space T(A)T(A), in which AA 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 AA, there’s an adjunction

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

defined for F:A opSetF: A^{op} \to Setand and b \in AbyUnknown character/pUnknown characterUnknown characterpUnknown character by</p> <p>Fˇ(b)=Hom(F,A(,b)) \check{F}(b) = Hom(F, A(-, b)) Unknown character/pUnknown characterUnknown characterpUnknown characterandfor</p> <p>and for G: A \to Setand and a \in AbyUnknown character/pUnknown characterUnknown characterpUnknown character by</p> <p>G^(a)=Hom(G,A(a,)). \hat{G}(a) = Hom(G, A(a, -)). Unknown character/pUnknown characterUnknown characterpUnknown characterWecall</p> <p>We call \check{F}theUnknown characterbUnknown character(Isbell)conjugateUnknown character/bUnknown characterof the <b>(Isbell) conjugate</b> of F,andsimilarly, and similarly \hat{G}the(Isbell)conjugateof the (Isbell) conjugate of G.Unknown character/pUnknown characterUnknown characterpUnknown characterLikeanyadjunction,itrestrictstoanequivalenceofcategoriesinacanonicalway.Specifically,itsanequivalencebetweenUnknown character/pUnknown characterUnknown characterblockquoteUnknown characterUnknown characterpUnknown characterthefullsubcategoryof. </p> <p>Like any adjunction, it restricts to an equivalence of categories in a canonical way. Specifically, it's an equivalence between</p> <blockquote> <p>the full subcategory of [A^{op}, Set]consistingofthoseobjects consisting of those objects Fsuchthatthecanonicalmap such that the canonical map F \to \hat{\check{F}}isanisomorphismUnknown character/pUnknown characterUnknown character/blockquoteUnknown characterUnknown characterpUnknown characterandUnknown character/pUnknown characterUnknown characterblockquoteUnknown characterUnknown characterpUnknown characterthefullsubcategoryof is an isomorphism</p> </blockquote> <p>and</p> <blockquote> <p>the full subcategory of [A, Set]^{op}consistingofthoseobjects consisting of those objects Gsuchthatthecanonicalmap such that the canonical map G \to \check{\hat{G}}isanisomorphism.Unknown character/pUnknown characterUnknown character/blockquoteUnknown characterUnknown characterpUnknown characterIllcalleitheroftheseequivalentcategoriestheUnknown characterbUnknown characterreflexivecompletionUnknown character/bUnknown character is an isomorphism.</p> </blockquote> <p>I'll call either of these equivalent categories the <b>reflexive completion</b> R(A)of of A.(SimoncalledittheIsbellcompletion,possiblywithmyencouragement,butUnknown characterreflexivecompletionUnknown characterismoredescriptiveandIpreferitnow.)So,thereflexivecompletionofacategoryconsistsofalltheUnknown characterreflexiveUnknown characterpresheavesonitthosecanonicallyisomorphictotheirdoubleconjugate.Unknown character/pUnknown characterUnknown characterpUnknown characterAllofthiscategoricalstuffgeneralizesseamlesslytoanenrichedcontext,atleastifweworkoveracompletesymmetricmonoidalclosedcategory.Unknown character/pUnknown characterUnknown characterpUnknown characterForexample,supposewetakeourbasecategorytobethecategory. (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 &mdash; those canonically isomorphic to their double conjugate.</p> <p>All of this categorical stuff generalizes seamlessly to an enriched context, at least if we work over a complete symmetric monoidal closed category. </p> <p>For example, suppose we take our base category to be the category Abofabeliangroups.Let of abelian groups. Let kbeafield,viewedasaoneobject be a field, viewed as a one-object Abcategory.Both-category. Both [k^{op}, Ab]and and [k, Ab]arethecategoryof are the category of kvectorspaces,andboth-vector spaces, and both \check{\,\,}and and \hat{\,\,}arethedualvectorspaceconstruction.Thereflexivecompletion are the dual vector space construction. The reflexive completion R(k)of of kisthecategoryof is the category of kvectorspaces-vector spaces Vforwhichthecanonicalmap for which the canonical map V \to V^{\ast\ast}isanisomorphisminotherwords,thefinitedimensionalvectorspaces.Unknown character/pUnknown characterUnknown characterpUnknown characterButthatsnottheexamplethatwillmattertoushere.Unknown character/pUnknown characterUnknown characterpUnknown characterWellbethinkingprimarilyaboutthecasewherethebasecategoryistheposet is an isomorphism &mdash; in other words, the finite-dimensional vector spaces.</p> <p>But that's not the example that will matter to us here.</p> <p>We'll be thinking primarily about the case where the base category is the poset ([0, \infty], \geq)(thereverseoftheusualorder!)withmonoidalstructuregivenbyaddition.AsLawvereobservedlongago,a (the reverse of the usual order!) with monoidal structure given by addition. As Lawvere observed long ago, a [0, \infty]categoryisthenaUnknown charactergeneralizedmetricspaceUnknown character:aset-category is then a "generalized metric space": a set AofpointstogetherwithadistancefunctionUnknown character/pUnknown characterUnknown characterpUnknown character of points together with a distance function</p> <p>d:A×A[0,] d: A \times A \to [0, \infty] Unknown character/pUnknown characterUnknown characterpUnknown charactersatisfyingthetriangleinequality</p> <p>satisfying the triangle inequality d(a, b) + d(b, c) \geq d(a, c)andtheequaiton and the equaiton d(a, a) = 0.Thesearelooserstructuresthanclassicalmetricspaces,mainlybecauseoftheabsenceofthesymmetryaxiom. These are looser structures than classical metric spaces, mainly because of the absence of the symmetry axiom d(a, b) = d(b, a).Unknown character/pUnknown characterUnknown characterpUnknown characterTheenrichedUnknown characteriUnknown characterfunctorsUnknown character/iUnknown characteraredistancedecreasingmapsbetweenmetricspaces:thosefunctions. </p> <p>The enriched <i>functors</i> are distance-decreasing maps between metric spaces: those functions f: A \to Bsatisfying satisfying d_B(f(a_1), f(a_2)) \leq d_A(a_1, a_2).IlljustcalltheseUnknown charactermapsUnknown characterofmetricspaces.Unknown character/pUnknown characterUnknown characterpUnknown characterIfyouworkthroughthedetails,youllfindthatIsbellconjugacyformetricspacesworksasfollows.Let. I'll just call these "maps" of metric spaces.</p> <p>If you work through the details, you'll find that Isbell conjugacy for metric spaces works as follows. Let Abeageneralizedmetricspace.Theconjugateofamap be a generalized metric space. The conjugate of a map f: A^{op} \to [0, \infty]isthemap is the map \check{f}: A \to [0, \infty]definedbyUnknown character/pUnknown characterUnknown characterpUnknown character defined by</p> <p>fˇ(b)=sup aAmax{d(a,b)f(a),0} \check{f}(b) = sup_{a \in A} max \{ d(a, b) - f(a), 0 \} Unknown character/pUnknown characterUnknown characterpUnknown characterandtheconjugateofamap</p> <p>and the conjugate of a map g: A \to [0, \infty]isthemap is the map \hat{g}: A^{op} \to [0, \infty]definedbyUnknown character/pUnknown characterUnknown characterpUnknown character defined by</p> <p>g^(a)=sup bAmax{d(a,b)g(b),0}. \hat{g}(a) = sup_{b \in A} max \{ d(a, b) - g(b), 0 \}. Unknown character/pUnknown characterUnknown characterpUnknown characterWealwayshave</p> <p>We always have f \geq \hat{\check{f}},andthereflexivecompletion, and the reflexive completion R(A)of of Aconsistsofallmaps consists of all maps f: A^{op} \to [0, \infty]suchthat such that f = \hat{\check{f}}.(Althoughyoucouldwriteoutanexplicitformulaforthat,Imnotconvinceditsmuchhelp.)Themetricon. (Although you could write out an explicit formula for that, I'm not convinced it's much help.) The metric on R(A)isthesupmetric.Unknown character/pUnknown characterUnknown characterpUnknown characterAllthatcomesoutofthegeneralcategoricalmachinery.Unknown character/pUnknown characterUnknown characterpUnknown characterHowever,wecansaysomethingmorethatonlymakessensebecauseoftheparticularbasecategorywereusing.Unknown character/pUnknown characterUnknown characterpUnknown characterAsweallknow,Unknown characteriUnknown charactersymmetricUnknown character/iUnknown charactermetricspacestheonesweremostusedtoareparticularinteresting.Forasymmetricmetricspace is the sup metric.</p> <p>All that comes out of the general categorical machinery. </p> <p>However, we can say something more that only makes sense because of the particular base category we're using. </p> <p>As we all know, <i>symmetric</i> metric spaces &mdash; the ones we're most used to &mdash; are particular interesting. For a symmetric metric space A,thedistinctionbetweencovariantandcontravariantfunctorson, the distinction between covariant and contravariant functors on Avanishes.Thetwokindsofconjugate, vanishes. The two kinds of conjugate, \hat{\,\,}and and \check{\,\,},arealsothesame.Illwrite, are also the same. I'll write {}^\astforthemboth.Unknown character/pUnknown characterUnknown characterpUnknown characterThereflexivecompletion for them both. </p> <p>The reflexive completion R(A)consistsofthefunctions consists of the functions A \to [0, \infty]thatareequaltotheirUnknown characteriUnknown characterdoubleUnknown character/iUnknown characterconjugate.Butbecausethereisnodistinctionbetweencovariantandcontravariant,wecanalsoconsiderthefunctions that are equal to their <i>double</i> conjugate. But because there is no distinction between covariant and contravariant, we can also consider the functions A \to [0, \infty]equaltotheirUnknown characteriUnknown charactersingleUnknown character/iUnknown characterconjugate.Unknown character/pUnknown characterUnknown characterpUnknown characterThesetofsuchfunctionsisbydefinition,ifyouliketheUnknown characterbUnknown charactertightspanUnknown character/bUnknown character equal to their <i>single</i> conjugate.</p> <p>The set of such functions is &mdash; by definition, if you like &mdash; the <b>tight span</b> T(A)of of A.SoUnknown character/pUnknown characterUnknown characterpUnknown character. So </p> <p>T(A)={f:A[0,]|f=f *}, T(A) = \{ f : A \to [0, \infty] \,|\, f = f^\ast \}, Unknown character/pUnknown characterUnknown characterpUnknown characterwhileUnknown character/pUnknown characterUnknown characterpUnknown character</p> <p>while</p> <p>R(A)={f:A[0,]|f=f **}. R(A) = \{ f: A \to [0, \infty] \,|\, f = f^{\ast\ast} \}. Unknown character/pUnknown characterUnknown characterpUnknown characterBothcomeequippedwiththesupmetric,andbothcontain</p> <p>Both come equipped with the sup metric, and both contain Aasasubspace,viatheYonedaembedding as a subspace, via the Yoneda embedding a \mapsto d(-, a).So. So A \subseteq T(A) \subseteq R(A).Unknown character/pUnknown characterUnknown characterblockquoteUnknown characterUnknown characterpUnknown characterUnknown characterbUnknown characterExampleUnknown character/bUnknown characterLet.</p> <blockquote> <p><b>Example</b> Let Abethesymmetricmetricspaceconsistingoftwopointsdistance be the symmetric metric space consisting of two points distance Dapart.Itsreflexivecompletion apart. Its reflexive completion R(A)istheset is the set [0, D] \times [0, D]withmetric with metric d((s 1,s 2),(t 1,t 2))=max{t 1s 1,t 2s 2,0}. d((s_1, s_2), (t_1, t_2)) = max \{ t_1 - s_1, t_2 - s_2, 0 \}. TheYonedaembeddingidentifiesthetwopointsof The Yoneda embedding identifies the two points of Awiththepoints with the points (0, D)and and (D, 0)of of R(A).Thetightspan. The tight span T(A)isthestraightlinebetweenthesetwopointsof is the straight line between these two points of R(A)(adiagonalofthesquare),whichisisometrictotheordinaryEuclideanlinesegment (a diagonal of the square), which is isometric to the ordinary Euclidean line segment [0, D].Unknown character/pUnknown characterUnknown character/blockquoteUnknown characterUnknown characterpUnknown characterAsthatexampleshows,thereflexivecompletionofaspaceneedntbesymmetric,eveniftheoriginalspacewassymmetric.Ontheotherhand,itsnottoohardtoshowthatthetightspanofaspaceUnknown characteriUnknown characterisUnknown character/iUnknown characteralwayssymmetric.SimonsUnknown characterahref=Unknown characterhttp://www.tac.mta.ca/tac/volumes/28/22/2822abs.htmlUnknown characterUnknown characterTheorem4.1.1Unknown character/aUnknown characterslotseverythingintoplace:Unknown character/pUnknown characterUnknown characterblockquoteUnknown characterUnknown characterpUnknown characterUnknown characterbUnknown characterTheoremUnknown character/bUnknown character(Willerton)Let. </p> </blockquote> <p>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 <i>is</i> always symmetric. Simon's <a href="http://www.tac.mta.ca/tac/volumes/28/22/28-22abs.html">Theorem 4.1.1</a> slots everything into place: </p> <blockquote> <p><b>Theorem</b> (Willerton) Let Abeasymmetricmetricspace.Thenthetightspan be a symmetric metric space. Then the tight span T(A)isthelargestsymmetricsubspaceof is the largest symmetric subspace of R(A)containing containing A.Unknown character/pUnknown characterUnknown character/blockquoteUnknown characterUnknown characterpUnknown characterHereUnknown characterlargestUnknown charactermeansthatif. </p> </blockquote> <p>Here "largest" means that if Bisanothersymmetricsubspaceof is another symmetric subspace of R(A)containing containing Athen then B \subseteq T(A).ItsnotevenobviousthatthereUnknown characteriUnknown characterisUnknown character/iUnknown characteralargestone.Forinstance,givenanynonsymmetricmetricspace. It's not even obvious that there <i>is</i> a largest one. For instance, given any non-symmetric metric space C,whatsthelargestsymmetricsubspaceof, what's the largest symmetric subspace of C?Thereisntone,justbecauseeverysingletonsubsetof? There isn't one, just because every singleton subset of Cissymmetric.Unknown character/pUnknown characterUnknown characterpUnknown characterSimonstoldthefollowingstorybefore,butIcantresisttellingitagain.Tightspanshavebeendiscoveredindependentlymanytimesover.Thefirsttimetheywerediscovered,theywerecalledbythelesscatchynameofUnknown characterinjectiveenvelopeUnknown character(because is symmetric. </p> <p>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)isthesmallestinjectivemetricspacecontaining is the smallest injective metric space containing A).Andthepersonwhomadethatfirstdiscovery?Isbellwho,asfarasanyoneknows,nevernoticedthatthishadanythingtodowithIsbellconjugacy.Unknown character/pUnknown characterUnknown characterpUnknown characterLetmefinishwithsomethingIdontquiteunderstand.Unknown character/pUnknown characterUnknown characterpUnknown characterSimonsUnknown characterahref=Unknown characterhttp://www.tac.mta.ca/tac/volumes/28/22/2822abs.htmlUnknown characterUnknown characterTheorem3.1.4Unknown character/aUnknown charactersaysthefollowing.Let). And the person who made that first discovery? Isbell &mdash; who, as far as anyone knows, never noticed that this had anything to do with Isbell conjugacy.</p> <p>Let me finish with something I don't quite understand. </p> <p>Simon's <a href="http://www.tac.mta.ca/tac/volumes/28/22/28-22abs.html">Theorem 3.1.4</a> says the following. Let Abeasymmetricmetricspace.(Hedoesntassumesymmetry,butIwill.)Thenforany be a symmetric metric space. (He doesn't assume symmetry, but I will.) Then for any a \in A,, p \in R(A)and and \varepsilon \gt 0,thereexists, there exists b \in AsuchthatUnknown character/pUnknown characterUnknown characterpUnknown character such that</p> <p>d(a,p)+d(p,b)d(a,b)+ε. d(a, p) + d(p, b) \leq d(a, b) + \varepsilon. Unknown character/pUnknown characterUnknown characterpUnknown characterInotherwords,</p> <p>In other words, a,, pand and barealmostcollinear.Unknown character/pUnknown characterUnknown characterpUnknown characterAUnknown characteriUnknown characterlooseUnknown character/iUnknown characterparaphrasingofthisisthateverypointinthereflexivecompletionof are almost collinear.</p> <p>A <i>loose</i> paraphrasing of this is that every point in the reflexive completion of Aisclosetobeingonageodesicbetweenpointsof is close to being on a geodesic between points of A.Thetheoremdoesimplythis,butitsaysalotmore.Lookatthequantification.WegettoUnknown characteriUnknown characterchooseUnknown character/iUnknown characteroneend. The theorem does imply this, but it says a lot more. Look at the quantification. We get to <i>choose</i> one end aofthenotquitegeodesic,aswellasthepoint of the not-quite-geodesic, as well as the point pinthereflexivecompletion,andwereguaranteedthatifwecontinuethenotquitegeodesicfrom in the reflexive completion, and we're guaranteed that if we continue the not-quite-geodesic from aonthrough on through p,thenwelleventuallymeetanotherpointof, then we'll eventually meet another point of A(ornearly).Unknown character/pUnknown characterUnknown characterpUnknown characterLetsgetridofthoseUnknown characternotquiteUnknown characters,andatthesametimefocusattentiononthetightspanratherthanthereflexivecompletion.BackinIsbellsoriginal1964paper(citedbySimon,incaseyouwanttolookitup),itsshownthatif (or nearly).</p> <p>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 Aiscompactthensoisitstightspan is compact then so is its tight span T(A).Ofcourse,SimonsTheorem3.1.4appliesinparticularwhen. Of course, Simon's Theorem 3.1.4 applies in particular when p \in T(A).Butthencompactnessof. But then compactness of T(A)meansthatwecandropthe means that we can drop the \varepsilon.Unknown character/pUnknown characterUnknown characterpUnknown characterInotherwords:let.</p> <p>In other words: let Abeacompactsymmetricmetricspace.Thenforany be a compact symmetric metric space. Then for any a \in Aand and p \in T(A),thereexists, there exists b \in AsuchthatUnknown character/pUnknown characterUnknown characterpUnknown character such that</p> <p>d(a,p)+d(p,b)=d(a,b). d(a, p) + d(p, b) = d(a, b). Unknown character/pUnknown characterUnknown characterpUnknown characterSo,ifyouplaceyourpencilatapointof</p> <p>So, if you place your pencil at a point of A,drawastraightlinefromittoapointof, draw a straight line from it to a point of T(A),andkeepgoing,youlleventuallymeetanotherpointof, and keep going, you'll eventually meet another point of A.Unknown character/pUnknown characterUnknown characterpUnknown characterThisleavesmewonderingwhattightspansofcommongeometricfiguresactuallylooklike.Unknown character/pUnknown characterUnknown characterpUnknown characterForexample,takeanarc.</p> <p>This leaves me wondering what tight spans of common geometric figures actually look like. </p> <p>For example, take an arc Aofacircleanysizearc,aslongasitsnotthewholecircle.EmbeditintheplaneandgiveittheEuclideanmetric.Isaidoriginallythatthetightspanissometimesthoughtofasasortofabstractconvexhull,andindeed,theintroductiontoSimonspapersaysthatsomeauthorshaveactuallyusedthisnameinsteadofUnknown charactertightspanUnknown character.ButtheresultIjuststatedmakesthisseemhighlymisleading.Itimpliesthatthetightspanof of a circle &mdash; 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 AisUnknown characteriUnknown characternotUnknown character/iUnknown characteritsconvexhull,andindeed,cantbeUnknown characteriUnknown characteranyUnknown character/iUnknown charactersubspaceoftheEuclideanplane(unless,perhaps,its is <i>not</i> its convex hull, and indeed, can't be <i>any</i> 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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2759

21 Comments & 0 Trackbacks

Re: Wrestling with Tight Spans

There is a passing resemblance between the formula for the Isbell conjugate and the Legendre transform (f *(p)=sup(pxf(x))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 2\mathbb{R}^2 with the Euclidean metric is not hyperconvex, but with the L 1L_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 VV-category, for any VV, 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 VV 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 VV-category AA to be the category of presheaves FF on AA such that FF is “the same as” F *F^\ast. The trouble is, there’s no canonical natural transformation FF *F \to F^\ast or F *FF^\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 FF for which there is merely some isomorphism between FF and F *F^\ast.

When VV is a poset, however, we can ask that FF and F *F^\ast are actually equal. So there are two special things about the metric space case: (i) that the base category VV is a poset, and (ii) that self-dual VV-categories are of particular interest. I haven’t been able to think of any other VVs 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 FF *F\cong F^\ast, the category of presheaves equipped with an isomorphism FF *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 AA opA\cong A^{op} yielding an isomorphism [A op,V][A,V][A^{op},V] \cong [A,V], and composition of the conjugate [A,V][A op,V] op[A,V] \to [A^{op},V]^{op} with this isomorphism yields… a functor [A,V][A,V] op[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 VV 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)T(A) of a (symmetric) metric space AA as its “injective envelope”. The precise definitions are as follows.

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

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

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

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

As the nnLab 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 k¯\overline{k} of kk sits in the topos of Gal(k¯/k)Gal(\overline{k}/k)-sets?

sounds like the concisest way one can say the same thing, modulo the caveat that the group Gal(k¯/k)Gal(\overline{k}/k) depends on the choice of k¯\overline{k} just as much as k¯\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 Π 1(Spec(k))\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 VV, 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 AT(A)R(A)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 FF and a copresheaf GG on a category AA. Isbell conjugacy says that natural transformations

FG^ F \to \hat{G}

are the same as natural transformations

GFˇ. G \to \check{F}.

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

F×GHom A F \times G \to Hom_A

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

The Isbell envelope of AA consists of triples (F,G,θ)(F, G, \theta) where FF is a presheaf, GG is a copresheaf, and θ\theta is a thing of the kind I’ve just described in three ways: a transformation FG^F \to \hat{G}, or equivalently a transformation GFˇG \to \check{F}, or equivalently a transformation F×GHom AF \times G \to Hom_A.

Another point is that the Isbell envelope of a small category AA contains both [A op,Set][A^{op}, Set] and [A,Set] op[A, Set]^{op}, whereas the Isbell/reflexive completion is contained in both [A op,Set][A^{op}, Set] and [A,Set] op[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)E(A) for the Isbell envelope of a small category AA and R(A)R(A) for the reflexive completion, the inclusion [A op,Set]E(A) [A^{\mathrm{op}},\mathbf{Set}] \to E(A) is given by X(X,Xˇ)X \mapsto (X, \check{X}) with the obvious natural transformation X×XˇA(,)X \times \check{X} \to A(-,-).

The inclusion [A,Set] opE(A)[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 op,Set][A^{\mathrm{op}},\mathbf{Set}] and [A,Set] op[A,\mathbf{Set}]^{\mathrm{op}} inside E(A)E(A) is precisely R(A)R(A).

These are all constructions that work for an arbitrary adjunction: Given LR:CDL \dashv R \colon C \rightleftarrows D, the category (LD)(CR)(L \downarrow D) \cong (C \downarrow R) contains CC as a coreflective subcategory and DD 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)E(A) in terms of natural transformations into A(,)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 LR:CDL \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, (LD)(CR)(L \downarrow D) \cong (C \downarrow R). On the other hand, the “core” of the adjunction is an inverter in two different ways, Inv(η)Inv(ϵ)\mathsf{Inv}(\eta) \cong \mathsf{Inv}(\epsilon). Both limits are defined over subdiagrams of the adjunction itself, regarded as a 2-functor 𝔸Cat\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 𝔸Cat\mathbb{A} \to \mathsf{Cat} with respect to different weights.

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

  1. What does the 2-category [𝔸,Cat][\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 Cat[𝔸,Cat]\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