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.

January 20, 2013

Tight spans, Isbell completions and semi-tropical modules

Posted by Simon Willerton

Some time ago, in a response to a comment on a post (?!) I said that I wanted to understand if the tight span construction for metric spaces could be thought of in enriched category theory terms. Tom suggested that it might have something to do with what he calls the Isbell completion construction. Elsewhere, in a response to a post on Equipments I was wondering about connections between metric spaces as enriched categories and tropical mathematics. I have finally got round to writing up a paper on these things. The draft can be found in the following place.

Tight spans, Isbell completions and semi-tropical modules

The paper was written to be accessible to people (such as metric geometers or tropical algebraists) with essentially no background in category theory, but to show how categorical methods apply. Consequently, parts of the paper on cocompletion might be seen as a bit pedestrian by some of the categorical cognoscenti. I would be interested to hear thoughts that people have. I will give an overview below the fold.

Generalized metric spaces

Recall that there is a notion due to Lawvere of a generalized metric space. The essential difference from the notion of classical metric spaces is that for a generalized metric space we don’t impose symmetry, so that in general d(x,y)d(y,x)d(x,y)\ne d(y,x); however, we do impose the triangle inequality and zero self-distance d(x,x)=0d(x,x)=0. A generalized metric space is actually defined to be a category enriched over the extended non-negative real numbers [0,][0,\infty], and this idea creates a bridge between enriched category theory and metric space theory.

Tight span

For classical metric spaces the idea of tight span has cropped up in many places independently over the years and has many applications, it was first discovered by Isbell in 1964. For a classical metric space MM the tight span T(M)T(M) can be thought of as a minimal contractible classical metric space in which MM embeds isometrically.

For generic three- and four-point metric spaces here are pictures of the tight span.

Some tight spans

One reason that the tight span is of interest is that MM embeds in a tree if and only if the tight span T(M)T(M) is a tree, this underlies some of the applications to phylogenetic analysis, i.e. recreating evolutionary trees of species from genetic data. There are also applications to multicommodity flows on networks, server positioning and group cohomology.

Isbell completion

The Isbell completion I(X)I(X) for an generalized metric space XX is a certain generalized metric space in which XX embeds isometrically. There are appropriate notions of categorical completeness and cocompleteness of a metric space (see below for ways of thinking of these) which are not to be confused with the usual notion of metric space completeness. The Isbell completion is complete and cocomplete, moreover the embedding XI(X)X\to I(X) is continuous and cocontinuous.

The Isbell completion is defined is defined in terms of “presheaves” and “copresheaves” on the space XX. Presheaves and copresheaves are certain kinds of functions X[0,]X\to [0,\infty], for example, for a fixed point xXx\in X the function d(,x)d(-,x) is a presheaf and the function d(x,)d(x,-) is a copresheaf. Each point pp in the Isbell completion is a pair (f,g)(f,g) where ff is a presheaf and gg is a copresheaf, with the interpretation that for any xXx\in X you have f(x)f(x) is the distance to pp from xx and g(x)g(x) is the distance from pp to xx.

For example, the Isbell completion of a generalized metric space with two points is a rectangle (pictured further down this post), the Isbell completion of a classical metric space with three points can be pictured as the union of four polygons in three-space like so.

Isbell completion

The metric here is an asymmetric version of the L L_\infty-metric on 3\mathbb{R}^3, so d((x,y,z),(x,y,z))max(0,xx,yy,zz)d((x,y,z),(x',y',z'))\coloneqq max(0, x'-x, y'-y,z'-z).

In categorical language, the Isbell completion of a generalized metric space is defined to be the “invariant part” of the “Isbell adjunction” between the space of presheaves and space of op-co-presheaves:

L:[0,] X op([0,] X) op:RL: [0,\infty]^{X^{op}} \leftrightarrow ([0,\infty]^X)^{op}:R

with L(f)(y)sup xX(d(x,y)f(x))L(f)(y)\coloneqq \sup_{x\in X}(d(x,y)-f(x)) and similarly for RR. So a point is the Isbell completion is a pair (f,g)(f,g) with L(f)=gL(f)=g and R(g)=fR(g)=f.

Tight span and Isbell completion

The connection between the tight span and the Isbell completion is that for a classical metric space MM the tight span T(M)T(M) is the maximal classical space containing MM inside the Isbell completion I(M)I(M). For example it is drawn in blue in the above picture of the Isbell completion of a three-point classical metric space. This means that the Isbell completion can be thought of as generalized metric space analogue of the tight span.

Directed tight span

After having figured all of this out I discovered that a couple of Japanese mathematicians, Hirai and Koichi, had defined an analogue of the tight span for what they called “directed metric spaces” which are not quite as general as generalized metric spaces but are the same in that they don’t impose the symmetry of the metric.

H. Hirai and S. Koichi, On tight spans and tropical polytopes for directed distances

They were motivated by applications to multicommodity flow on directed networks. It transpires that their directed tight span is basically the Isbell completion.

Semi-tropical algebra

Tropical mathematics is a broad an active area of mathematics being studied for many reasons, but has at its heart the so-called tropical semi-ring T\mathbf{T}. (Here the term “semi-ring” means a ring without additive inverses, such a thing is also called a “rig”.) Actually there are a few minor variants of “the” tropical semi-ring but we can take T\mathbf{T} to be the extended real numbers (,](-\infty,\infty] with “min” as the addition – written \oplus – and “usual ++” as the multiplication – written \odot. Then \infty is the additive unit and 00 is the multiplicative unit. For example,

73=3,73=10.7\oplus 3 =3, \qquad 7\odot 3= 10.

The tropical semi-ring is actually a semi-field as all of the non-\infty elements have multiplicative inverses, e.g. 77=07\odot -7 =0 . We are not interested at this point in the negative reals and will consider the semi-ring ([0,],,)([0,\infty],\oplus, \odot). As this is half of the tropical semi-ring I have named it the semi-tropical semi-ring, and we can denote it S\mathbf{S}.

Modules over the tropical semi-ring are of much interest; a module over a semi-ring is a commutative monoid (C,)(C,\oplus) with an action \odot, in the usual sense, of the semi-ring on it. As the tropical semi-ring T\mathbf{T} is a semi-field, modules over it are free, in particular a module over T\mathbf{T} comes with a flow, i.e. an action of the extended reals (,](-\infty,\infty] on it.

Develin and Sturmfels thought that they were able to show that the classical tight span was a tropical module (modulo the flow), but found an error in their proof. This is the use of the word tropical in Hirai and Koichi’s paper above.

Modules over the semi-tropical semi-ring S\mathbf{S} are a bit more mysterious at this point, but in particular they only have a semi-flow, so points can be moved forward in time, if you will, but cannot be moved backwards in time.

Completeness, cocompleteness and semi-tropical modules

We can now go back to completeness and cocompleteness of generalized metric spaces. It transpires that a generalized metric space is cocomplete if and only if it can be given a semi-tropical module structure in a way compatible with the metric. (I should be careful and say that the generalized metric space has to be skeletal there.) Similarly being complete corresponds to being a semi-tropical module in a way differently compatible with the metric. The point here is that generalized metric spaces are enriched over [0,][0,\infty] and it is this that naturally acts.

As the Isbell completion is both complete and cocomplete, it can be given two different semi-tropical modules structures. In the very simple case of an asymmetric generalized metric space with two points, the two semi-tropical module structures (I(X),,)\left(I(X),\oplus, \odot\right) and (I(X),,)\left(I(X),\boxplus, \boxdot\right) are pictured as follows, where τ[0,]\tau\in [0,\infty].

Isbell completion

The semi-tropical action on the Isbell completion of three points pictured further up is going to be more complicated.

Anyway, to sum up, from the categorical point of view, gives you various structures that are of interest. In particular, we get these semi-tropical structures naturally occurring on Hirai and Koichi’s tight span which they had not looked at. It seems people were looking for tropical actions.

Postscript: Formal concept analysis

In the last week Dusko Pavlovic pointed me to his paper

D. Pavlovic, Quantitative concept analysis

In this paper he also defines what I’ve termed the Isbell completion for what are essentially generalized metric spaces (but he uses the equivalent context of “proxets”). His motivation and notation are rather different however. He goes on to define a generalization of the Isbell completion for any profunctor Φ:XY\Phi\colon X\to Y between generalized metric spaces, he calls this generalized metric space the “nucleus” of Φ\Phi and it consists of pairs (f,g)(f,g) where ff is a presheaf on XX and gg is a copresheaf on YY. I have some ideas about this, but haven’t thought too much about it yet.

Posted at January 20, 2013 10:42 PM UTC

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

13 Comments & 0 Trackbacks

Re: Tight spans, Isbell completions and semi-tropical modules

I don’t quite understand the details, but this looks quite neat! Is the Isbell who first defined the tight span the same Isbell that the Isbell completion is named after? Was he aware of a relationship between the two? I see that the tight span was defined a decade or so before Lawvere wrote about metric spaces as enriched categories; when was the Isbell completion first defined?

Posted by: Mike Shulman on January 22, 2013 3:56 PM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Yes, it’s the same Isbell! I should have made that point a bit clearer.

I’m not very clear on the history, but as far as I can tell Isbell made no mention of the connection.

I’m not sure when the Isbell completion was defined, however in Adequate subcategories (1960) there is certainly some allusion to something like the Isbell completion, but I’ve only really skimmed the paper so I can’t tell you too much.

The tight span was defined by Isbell in Six theorems about injective metric spaces (1964/65).

Lawvere made his observation about metric spaces being enriched categories in 1967 at the earliest, according to the foreword of the TAC reprint of Metric spaces, generalized logic and closed categories.

Isbell conjugation for metric spaces is mentioned by Lawvere in Taking categories seriously (1986), but he doesn’t mention the invariant part, ie the Isbell completion.

So, as far as I can tell, no explicit connection has previously been made between these two constructions of Isbell.

Posted by: Simon Willerton on January 22, 2013 11:24 PM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Simon, please read carefully the early papers about the metric injective hull, first by Isbell, then by me (Włodzimierz Holsztyński). You are attributing some of my work to Isbell. I hope that you will post the correct information, correcting what you have written already (it’s not too easy since Isbell’s writing was not, hm, too tidy).

Regards,

wlod (Włodzimierz Holsztyński)

Posted by: Wlodzimierz Holsztynski (wlod) on January 23, 2013 3:20 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Wlod, I’m very happy to correct things, but it might be easier if you give an account of where I’ve misattributed things! I have certainly based some of the things I’ve said on secondary sources.

Simon.

Posted by: Simon Willerton on January 23, 2013 7:13 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Tom, it depends on your understanding of the idea of working in parallel. Dress discovered it independently, but twenty years later.

In Dress’ 1984 paper, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups, where he first defines the tight span, there’s a “Note added in proof” which says that after writing up his work he learned of Isbell’s 1964 paper on the injective envelope.

Posted by: Simon Willerton on January 23, 2013 4:04 PM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Wlod, I’d also be interested in hearing details (e.g. the titles of the relevant papers of yours). I may have told Simon some muddled, patchy version of the history of this, and I’d like to get it right.

My understanding was that some work had been done in parallel: Isbell came up with the idea of injective envelope/hull, and someone else (Wikipedia says Andreas Dress) independently came up with the same idea and called it “tight span”. I don’t know how far it went before it was realized that they were the same thing, or when the two streams of work were united. Do you?

Posted by: Tom Leinster on January 23, 2013 12:06 PM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

That’s pretty amusing, if Isbell defined these two things unrelatedly, and then a few years later Lawvere described a context in which they can be related to each other, but it took another half century for anyone to notice it!

Posted by: Mike Shulman on January 23, 2013 1:19 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Might it be worth asking Lawvere directly? My general impression is that there are many things that he and his collaborators notice, that never quite see the light of publication.

Posted by: Todd Trimble on January 23, 2013 2:39 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

This could be a stupid question, but I’m not understanding why the tight span of that 4-element set should be 2-dimensional (with the prominent blue rectangle in the middle). Could you walk me through that? Are you using the ordinary Euclidean metric?

Posted by: Todd Trimble on January 23, 2013 12:36 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

I don’t think that it’s at all obvious that the tight span of a generic four-point metric space has a two-dimensional cell in it. It took me a while to realise when I was learning this stuff that the rectangle is given the L 1L_1 metric and not the Euclidean metric. As you undoubtably know, the Euclidean metric on R n\R^n does not crop up very naturally in the Lawverian world of generalized metric spaces.

I’ll see if I can come up with an easy argument for you today. I can certainly direct you to proofs in the literature, but it will be more fun to write it down. In the meantime I will mention the theorem of Dress which says that for a finite metric space with nn points, the tight span is a finite cell complex of dimension at most n/2n/2.

Posted by: Simon Willerton on January 23, 2013 10:02 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Todd, you asked me to convince you about the rectangle in the tight span of the four-point metric space: it’s taken me a bit longer than I expected…

Let’s start with the definition of the tight span.

Suppose that (X,d)(X,d) is a metric space. Define the tight span T(X)T(X) to be the set of functions ff from XX to \mathbb{R} such that the following hold.

  1. For any x,yXx,y\in X, f(x)+f(y)d(x,y)f(x)+f(y)\ge d(x,y).
  2. For each xXx\in X, there exists yXy\in X such that f(x)+f(y)=d(x,y)f(x)+f(y)=d(x,y).

I need to convince you that a generic four-point metric space {a,b,c,d}\{a,b,c,d\} has a two-dimensional part to its tight span.

To be concrete, a point in the tight span is a function f:{a,b,c,d}f\colon \{a,b,c,d\}\to \mathbb{R} which satisfies the following six inequalities subject to the requirement that some of them are actually equalities, as per the second condition of the definition.

f(a)+f(c) d(a,c); f(b)+f(d) d(b,d); f(a)+f(b) d(a,b); f(b)+f(c) d(b,c); f(a)+f(d) d(a,d); f(c)+f(d) d(c,d); f(a) 0; f(b) 0; f(c) 0; f(d) 0. \begin{array}{rlcrl} f(a)+f(c)&\ge d(a,c); &\quad\quad& f(b)+f(d)&\ge d(b,d);\\ f(a)+f(b)&\ge d(a,b);&& f(b)+f(c)&\ge d(b,c);\\ f(a)+f(d)&\ge d(a,d);&& f(c)+f(d)&\ge d(c,d);\\ f(a)&\ge 0;&& f(b)&\ge 0;\\ f(c)&\ge 0;&& f(d)&\ge 0. \end{array}

In solving these it makes sense to break them up into different cases where the weak inequalities become either equalities or strict inequalities. We can enumerate the different cases combinatorially using graphs.

For each point fT(X)f\in T(X) in the tight span there is an associated graph E(f)E(f) that encodes which of the inequalities above are strict. The vertices of the graph E(f)E(f) are the points of the metric space XX and there is an edge between xx and yy in E(f)E(f) if f(x)+f(y)=d(x,y)f(x)+f(y)=d(x,y). The second condition in the definition of the tight span means that every vertex has an edge attached to it.

For instance in our four-point metric space if we have an ff with E(f)E(f) being the X graph,

Cell labelling of tight span

then ff satisfies the following equalities and inequalities.

f(a)+f(c) =d(a,c); f(b)+f(d) =d(b,d); f(a)+f(b) >d(a,b); f(b)+f(c) >d(b,c); f(a)+f(d) >d(a,d); f(c)+f(d) >d(c,d); f(a) >0; f(b) >0; f(c) >0; f(d) >0. \begin{array}{rlcrl} f(a)+f(c)&=d(a,c); &\quad\quad& f(b)+f(d)&=d(b,d);\\ f(a)+f(b)&\gt d(a,b);&& f(b)+f(c)&\gt d(b,c);\\ f(a)+f(d)&\gt d(a,d);&& f(c)+f(d)&\gt d(c,d);\\ f(a)&\gt 0;&& f(b)&\gt 0;\\ f(c)&\gt 0;&& f(d)&\gt 0. \end{array}

If we take ϵ\epsilon and δ\delta sufficiently small then we can define a function ff' by

f(a)f(a)+ϵ; f(c)f(c)ϵ; f(b)f(b)+δ; f(d)f(d)δ. \begin{array}{rclcrcl} f'(a)\coloneqq f(a)+\epsilon; &\quad\quad& f'(c)\coloneqq f(c)-\epsilon;\\ f'(b)\coloneqq f(b)+\delta; &\quad\quad& f'(d)\coloneqq f(d)-\delta. \end{array}

Then ff' will satisfy the same inequalities and equalities as ff, so fT(X)f'\in T(X) and E(f)E(f') is the same X shaped graph as E(f)E(f). This means that the points in the tight span with this associated graph form a (possibly empty) two-dimensional subspace of the space of functions.

Now consider a function gg which has the following graph associated to it.

Cell labelling of tight span

If it exists then such a function will satisfy the following.

g(a)+g(c) =d(a,c); g(b)+g(d) =d(b,d); g(a)+g(b) =d(a,b); g(b)+g(c) =d(b,c); g(a)+g(d) >d(a,d); g(c)+g(d) >d(c,d); g(a) >0; g(b) >0; g(c) >0; g(d) >0. \begin{array}{rlcrl} g(a)+g(c)&=d(a,c); &\quad\quad& g(b)+g(d)&=d(b,d);\\ g(a)+g(b)&= d(a,b);&& g(b)+g(c)&= d(b,c);\\ g(a)+g(d)&\gt d(a,d);&& g(c)+g(d)&\gt d(c,d);\\ g(a)&\gt 0;&& g(b)&\gt 0;\\ g(c)&\gt 0;&& g(d)&\gt 0. \end{array}

In this case we can’t perturb gg to get another function in the tight span with the same associated graph because if we add a little bit to g(a)g(a) then we need to subtract a bit from both g(b)g(b) and g(c)g(c), but that will lead to it not satisfying the equality g(b)+g(c)=d(b,c)g(b)+g(c)= d(b,c).

In terms of the graph, the obstruction to perturbing the function gg is that the graph has an odd cycle in it – in this case a cycle of length three. If we only had cycles with even lengths then we could alternating adding and subtracting little bits to g(x)g(x) as xx varies around the cycle, and thus obtain a new function in the tight span with the same associated graph.

This means that if we have a function ff with associated graph E(f)E(f) and we wish to perturb ff so that we have the same associated graph then we have one degree of freedom for each component of the graph with only even cycles.

Putting it another way, we see that the part of the tight span consisting of functions with a given graph GG has dimension equal to the number of connected components of GG which have no odd cycles in them. So corresponding to the two graphs pictured above we get a two dimensional and a zero dimensional part of the tight span, where either of these could be empty.

One can then calculate the whole of the tight span of a generic four-point space. Without loss of generality we need to assume that

d(a,c)+d(b,d)>d(a,b)+d(c,d),d(a,d)+d(b,c).d(a,c)+d(b,d)\gt d(a,b)+d(c,d),d(a,d)+d(b,c).

This ensures that there are functions in the tight span corresponding to the X graph pictured above. If that isn’t satisfied then we perturb the space and/or rename the points. The associated tight span then has 8 zero-dimensional cells, 8 one-dimensional cells and 1 two-dimensional cells which fit together as follows.

Cell labelling of tight span

I hope that helps. I’m not sure if that’s the kind of answer you wanted, but I’m happy to say more if you like.

Posted by: Simon Willerton on January 29, 2013 11:00 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

Thanks, Simon. I apologize for not replying earlier.

Your explanation seems rather clear, and the notation (using graphs to label the various cells in the tight span) is reminiscent of other things I’ve seen, e.g., using trees to label cells of an associahedron. For example, as we move from one cell to a codimension 1 cell lying within the boundary, we add an edge to the graph label. Or, roughly, that removing an edge from the graph corresponds to adding a degree of freedom.

One thing I puzzled over a little bit is the scope of the word “generic”. For example, I wasn’t sure what the tight span of the four vertices of a regular tetrahedron would look like – maybe that’s not a generic-enough example? Here we have that the distance between any two distinct points is 1, and the constant function taking all points to 1/2 lies in the tight span. Its graph looks like the complete graph on four vertices (sans loops from a vertex to itself), if I’m not mistaken, which has six edges. Whereas in the example you gave, a graph has a maximum of four edges (0-dimensional cells) and a minimum of two (2-dimensional cells). I am guessing that the tight span of the tetrahedron example might not be connected? In particular, that the constant function at 1/2 is an isolated point?

I didn’t think about this really hard, I’m afraid, and don’t want you to spend time on this unless you really want to – I fear you already spent more time on your kind explanation than you originally bargained for. Anyway, thanks again.

Posted by: Todd Trimble on February 4, 2013 11:32 AM | Permalink | Reply to this

Re: Tight spans, Isbell completions and semi-tropical modules

What I mean by generic should become clear if I put some explicit lengths into the picture.

Suppose our four-point metric space has the following distances.

Distances on the metric space

Then without loss of generality we may assume that

B+E=max(B+E,A+F,C+D)B+E=max(B+E,A+F,C+D)

as we can just rename the points otherwise.

Then the tight span has the following edge lengths.

Distances on the metric space

The ‘non-generic’ cases are when some of these edge lengths are zero, for instance when three points are colinear or when the above mentioned maximum is also attained by either A+FA+F or C+DC+D. In the latter case, the tight span is a tree.

[You are right in that I spent a lot more time answering your last question than I intended, but I learnt a vast amount in doing so. It also caused me to write to some maple code to calculate the cell decomposition of the tight span and the Isbell completion for given spaces with three or four points. There remains truth in the old adage that if you want to understand something then you should try to explain it.]

Posted by: Simon Willerton on February 5, 2013 6:47 PM | Permalink | Reply to this

Post a New Comment