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 25, 2016

Monoidal Categories with Projections

Posted by Tom Leinster

Monoidal categories are often introduced as an abstraction of categories with products. Instead of having the categorical product ×\times, we have some other product \otimes, and it’s required to behave in a somewhat product-like way.

But you could try to abstract more of the structure of a category with products than monoidal categories do. After all, when a category has products, it also comes with special maps X×YXX \times Y \to X and X×YYX \times Y \to Y for every XX and YY (the projections). Abstracting this leads to the notion of “monoidal category with projections”.

I’m writing this because over at this thread on magnitude homology, we’re making heavy use of semicartesian monoidal categories. These are simply monoidal categories whose unit object is terminal. But the word “semicartesian” is repellently technical, and you’d be forgiven for believing that any mathematics using “semicartesian” anythings is bound to be going about things the wrong way. Name aside, you might simply think it’s rather ad hoc; the nLab article says it initially sounds like centipede mathematics.

I don’t know whether semicartesian monoidal categories are truly necessary to the development of magnitude homology. But I do know that they’re a more reasonable and less ad hoc concept than they might seem, because:

Theorem   A semicartesian monoidal category is the same thing as a monoidal category with projections.

So if you believe that “monoidal category with projections” is a reasonable or natural concept, you’re forced to believe the same about semicartesian monoidal categories.

I’m going to keep this post light and sketchy. A monoidal category with projections is a monoidal category V=(V,,I)V = (V, \otimes, I) together with a distinguished pair of maps

π X,Y 1:XYX,π X,Y 2:XYY \pi^1_{X, Y} \colon X \otimes Y \to X, \qquad \pi^2_{X, Y} \colon X \otimes Y \to Y

for each pair of objects XX and YY. We might call these “projections”. The projections are required to satisfy whatever equations they satisfy when \otimes is categorical product ×\times and the unit object II is terminal. For instance, if you have three objects XX, YY and ZZ, then I can think of two ways to build a “projection” map XYZXX \otimes Y \otimes Z \to X:

  • think of XYZX \otimes Y \otimes Z as X(YZ)X \otimes (Y \otimes Z) and take π X,YZ 1\pi^1_{X, Y \otimes Z}; or

  • think of XYZX \otimes Y \otimes Z as (XY)Z(X \otimes Y) \otimes Z, use π XY,Z 1\pi^1_{X \otimes Y, Z} to project down to XYX \otimes Y, then use π X,Y 1\pi^1_{X, Y} to project from there to XX.

One of the axioms for a monoidal category with projections is that these two maps are equal. You can guess the others.

A monoidal category is said to be cartesian if its monoidal structure is given by the categorical (“cartesian”) product. So, any cartesian monoidal category becomes a monoidal category with projections in an obvious way: take the projections π X,Y i\pi^i_{X, Y} to be the usual product-projections.

That’s the motivating example of a monoidal category with projections, but there are others. For instance, take the ordered set (,)(\mathbb{N}, \geq), and view it as a category in the usual way but with a reversal of direction: there’s one object for each natural number nn, and there’s a map nmn \to m iff nmn \geq m. It’s monoidal under addition, with 00 as the unit. Since m+nmm + n \geq m and m+nnm + n \geq n for all mm and nn, we have maps m+nmm + n \to m and m+nnm + n \to n.

In this way, (,)(\mathbb{N}, \geq) is a monoidal category with projections. But it’s not cartesian, since the categorical product of mm and nn in (,)(\mathbb{N}, \geq) is max{m,n}max\{m, n\}, not m+nm + n.

Now, a monoidal category (V,,I)(V, \otimes, I) is semicartesian if the unit object II is terminal. Again, any cartesian monoidal category gives an example, but this isn’t the only kind of example. And again, the ordered set (,)(\mathbb{N}, \geq) demonstrates this: with the monoidal structure just described, 00 is the unit object, and it’s terminal.

The point of this post is:

Theorem   A semicartesian monoidal category is the same thing as a monoidal category with projections.

I’ll state it no more precisely than that. I don’t know who this result is due to; the nLab page on semicartesian monoidal categories suggests it might be Eilenberg and Kelly, but I learned it from a Part III problem sheet of Peter Johnstone.

The proof goes roughly like this.

Start with a semicartesian monoidal category VV. To build a monoidal category with projections, we have to define, for each XX and YY, a projection map XYXX \otimes Y \to X (and similarly for YY). Now, since II is terminal, we have a unique map YIY \to I. Tensoring with XX gives a map XYYIX \otimes Y \to Y \otimes I. But YIYY \otimes I \cong Y, so we’re done. That is, π X,Y 1\pi^1_{X, Y} is the composite

XYX!XIX. X \otimes Y \stackrel{X \otimes !}{\longrightarrow} X \otimes I \cong X.

After a few checks, we see that this makes VV into a monoidal category with projections.

In the other direction, start with a monoidal category VV with projections. We need to show that VV is semicartesian. In other words, we have to prove that for each object XX, there is exactly one map XIX \to I. There’s at least one, because we have

XXIπ X,I 2I. X \cong X \otimes I \stackrel{\pi^2_{X, I}}{\longrightarrow} I.

I’ll skip the proof that there’s at most one, but it uses the axiom that the projections are natural transformations. (I didn’t mention that axiom, but of course it’s there.)

So we now have a way of turning a semicartesian monoidal category into a monoidal category with projections and vice versa. To finish the proof of the theorem, we have to show that these two processes are mutually inverse. That’s straightforward.

Here’s something funny about all this. A monoidal category with projections appears to be a monoidal category with extra structure, whereas a semicartesian monoidal category is a monoidal category with a certain property. The theorem tells us that in fact, there’s at most one possible way to equip a monoidal category with projections (and there is a way if and only if II is terminal). So having projections turns out to be a property, not structure.

And that is my defence of semicartesian monoidal categories.

Posted at August 25, 2016 9:00 PM UTC

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

46 Comments & 0 Trackbacks

Re: Monoidal Categories with Projections

Typo: “centipede mathematics” links to the nLab page on semicartesian monoidal categories.

Posted by: Itai Bar-Natan on August 25, 2016 10:55 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Thanks! Fixed.

What do you call a typo caused by clicking rather than typing? A clicko, maybe.

I have a friend who likes to use the word “braino” for an analogous purpose.

Posted by: Tom Leinster on August 25, 2016 11:21 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I had heard “thinko” which fits better, if you believe that the type in typo is a verb.

Posted by: Allen Knutson on August 28, 2016 3:49 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

It seems kind of odd to just dismiss these as “centipede mathematics” when there are so many examples.

For instance, there are at least two that come up in programming languages. If you think of domain models for programming languages, then there are three (at least) sorts of products. One is the Cartesian product, where =(,)\bot = (\bot,\bot). One is the smash product where x,y.(x,)==(,y)\forall x,y. (x,\bot) = \bot = (\bot,y). And a third is the lifted product where x,y.(x,y)\forall x,y. \bot \ne (x,y). These all have projections, but only one is actually Cartesian.

Also, I saw something recently that pointed out that for the category of comonads on an appropriate monoidal category (not sure if it requires any more than just monoidal), Day convolution forms a monoidal structure (with the identity as unit). And since the identity is the terminal comonad, it is a monoidal category with projections. But Day convolution isn’t the product of comonads.

There are dual situations, too. You can combine two domains (or monoids, even) into a domain that has injections like the coproduct, but isn’t the coproduct. And the monoidal structure of Day convolution on monoidal functors [C,V][C,V] (for VV-enriched functors CC) has ‘inclusions’ from those monoidal functors (because y(I)y(I) is the initial such functor, if I’m not mistaken), but it is not (always) the coproduct of those monoidal functors.

Posted by: Dan Doel on August 26, 2016 1:20 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

It seems kind of odd to just dismiss these as “centipede mathematics” when there are so many examples.

Exactly what the nLab says: “This a weakening of the concept of cartesian monoidal category, which might seem like pointless centipede mathematics were it not for the existence of interesting examples and applications.”

Posted by: Todd Trimble on August 26, 2016 2:05 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Right — no one is dismissing it as centipede mathematics! As I wrote, the nLab article says it sounds like centipede mathematics — but that’s not its final verdict, as the bit that Todd quotes makes clear.

(I’ve added a word to my post to clarify that the nLab article isn’t calling the concept centipedal.)

Posted by: Tom Leinster on August 26, 2016 2:11 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

If you look back in time on the nLab you’ll see that I’m the one who mentioned centipede mathematics on the page about semicartesian categories. I’m also the one who added the page ‘centipede mathematics’—and the picture, which Andrew Stacey greatly disliked.

However, I’m also the one who added the page ‘semicartesian monoidal category’ and said this concept “would seem like pointless centipede mathematics were it not for the existence of many interesting examples”. The examples, from conversations with James Dolan, were mainly of a geometric nature. For example, the category of Poisson manifolds, or the category of convex sets, or the category of affine spaces. It seems pretty easy, in such geometrical situations, for the unit of the tensor product to be terminal.

Long live semicartesian monoidal categories!

Posted by: John Baez on August 28, 2016 9:57 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Surely it is in one of the unit axioms, but what prevents me from taking a monoidal category with zero, and defining the projections to all be zero? Something like “the projection XIXX \otimes I \to X should be the identity”? Ok, fine, that rules out making all projections vanish. But what if I take a monoidal category 𝒞\mathcal{C} with zero, add a disjoint unit to get “𝒞{I}\mathcal{C} \sqcup \{I\}” (allow the zero map to or from II, and let II have endomorphisms algebra {0,1}\{0,1\}), and declare: “projection is 00 except for projections XIXX \otimes I \to X is the identity”. What goes wrong then?

I am glad you posted this, because it turns out that almost every “nonlinear” category I care about is semicartesian, even though many of them are not cartesian.

Posted by: Theo Johnson-Freyd on August 26, 2016 1:21 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

“the projection XIXX \otimes I \to X should be the identity”?

Yes, that’s true in any monoidal category with projections. The definition is set up so that whenever you have an equation involving the monoidal structure and the projections that’s true in every cartesian monoidal category, it’s also true in every monoidal category with projections. Since the projection X×1XX \times 1 \to X in a cartesian monoidal category is always the identity (or strictly, the unit iso in the monoidal structure), the same is true in monoidal categories with projections.

I just dug out that problem sheet of Peter Johnstone’s that I mentioned (the one I learned this theorem from). This problem implicitly gives a definition of monoidal category with projections, and it appears to be very parsimonious. If I’m translating between notations correctly, it’s simply this:

A monoidal category with projections is a monoidal category VV together with natural transformations (π X,Y 1:XYX) X,Y,(π X,Y 2:XYY) X,Y (\pi^1_{X, Y}\colon X \otimes Y \to X)_{X, Y}, \qquad (\pi^2_{X, Y}\colon X \otimes Y \to Y)_{X, Y} such that π I,I 1\pi^1_{I, I} is the unit isomorphism IIII \otimes I \to I.

Apparently, all the other properties follow from this one! Well, I guess what happens is this. I sketched the proof that every mon cat with projections is semicartesian. That proof only needs the naturality plus this property of π I,I 1\pi^1_{I, I}. But then it’s clear that in a semicartesian monoidal category, the projections satisfy a whole host of other properties, like the one about XYZXX \otimes Y \otimes Z \to X that I mentioned in my post.

I don’t understand your 𝒞⨿{I}\mathcal{C} \amalg \{I\} example. You have a monoidal category 𝒞\mathcal{C}; let’s call its unit object JJ. Then you adjoin a new “unit” II. What’s the tensor product on 𝒞⨿{I}\mathcal{C} \amalg \{I\}? In particular, what’s IJI \otimes J? Or concretely, what monoidal category do you get from your construction if you take 𝒞\mathcal{C} to be the terminal category?

I am glad you posted this, because it turns out that almost every “nonlinear” category I care about is semicartesian

Thanks!

I’ve just (re)learned from Johnstone’s problem sheet that there’s a family of examples that I care about, and that isn’t on the nLab page. For any p[1,]p \in [1, \infty], there’s a pp-norm-ish tensor product × p\times_p on the category of metric spaces. It’s given on point-sets by taking the cartesian product, and on distances by taking a ppth root of a sum of ppth powers. (I guess you know what I mean!) That’s only the cartesian monoidal structure when p=p = \infty, which gives the max of distances. But it’s semicartesian for all pp, since the unit object is always the terminal space {}\{\bullet\}.

Posted by: Tom Leinster on August 26, 2016 3:08 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Oh, that p-norm example is nice! I’ll add it to the nLab sometime soon. (It sounds like something that Toby might have known about, but we seem not to see him at the nLab as much as we used to.)

Posted by: Todd Trimble on August 26, 2016 3:22 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Here’s a minor clarification or correction which elaborates on Theo’s point. Tom wrote:

A monoidal category with projections is a monoidal category VV together with natural transformations (π X,Y 1:XYX) X,Y,(π X,Y 2:XYY) X,Y (\pi^1_{X, Y}\colon X \otimes Y \to X)_{X, Y}, \qquad (\pi^2_{X, Y}\colon X \otimes Y \to Y)_{X, Y} such that π I,I 1\pi^1_{I, I} is the unit isomorphism IIII \otimes I \to I.

It’s true that these conditions imply that the monoidal unit is terminal, so that VV is semicartesian; we don’t actually need π 2\pi^2 in order to conclude that. But these conditions do not necessarily make these morphisms equal to the semicartesian monoidal projections XYXX \otimes Y \to X and XYYX \otimes Y \to Y! This fails already in the cartesian case: for example, consider the category of abelian groups (Ab,)(Ab,\oplus) and replace the usual projections ABAA \oplus B \to A and ABBA \oplus B \to B by any integer multiple thereof, e.g. 00 as Theo seems to have suggested. Or more generally, take any semicartesian monoidal category and compose its monoidal projections with any nontrivial endotransformations of the identity functor.

If one wants to conclude that the π X,Y 1\pi^1_{X, Y} and π X,Y 2\pi^2_{X, Y} are indeed equal to the monoidal projections, then one indeed needs to require the stronger property that all the π X,I 1:XIX,π X,Y 2:IXX \pi^1_{X,I} : X \otimes I \to X, \qquad \pi^2_{X,Y} : I \otimes X \to X must be equal to the monoidal structure isomorphisms. This is spelled out as Theorem 3.5 in this paper of Gerhold, Lachs and Schürmann.

Posted by: Tobias Fritz on October 23, 2019 9:24 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

This equivalence between monoidal categories with projections and those whose unit is terminal is somewhat puzzling to me, because the dual statement is not true.

It’s a somewhat better-known fact that a monoidal category is cartesian as soon as it has “both diagonals and projections” in a suitable sense. And you can also define a “monoidal category with diagonals” — but it’s not the same as a monoidal category whose tensor product is the cartesian product!

In fact, if the tensor product is the cartesian product and the category has a terminal object, then the unit object must also be terminal, since the terminal object is a unit for the cartesian product and a binary operation can have at most one unit. But there are examples of “monoidal categories with diagonals” whose unit is not terminal (and whose tensor product is not cartesian), such as pointed sets with smash product.

I don’t really understand this at any level deeper than “well, 2 is more complicated than 0”.

(The only paper I know of about monoidal categories with diagonals calls them relevance monoidal categories because they are related to “relevance logic” in the same way that cartesian monoidal categories are related to ordinary logic, non-cartesian ones are related to “linear logic”, and semicartesian ones are related to “affine logic”.)

Posted by: Mike Shulman on August 26, 2016 4:10 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

This equivalence between monoidal categories with projections and those whose unit is terminal is somewhat puzzling to me, because the dual statement is not true.

Wait, what? How can this be? (C,,I)(C, \otimes, I) is monoidal if and only if (C op,,I)(C^{op}, \otimes, I) is monoidal; “initial” is dual to “terminal”, and “injections” XXYX \to X \otimes Y are dual to “projections” (assuming I’ve understood the meaning of these terms).

What am I missing?

Posted by: Emily Riehl on August 26, 2016 10:21 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Sorry, I didn’t mean “dual” in the sense of “turning all the arrows around”. I meant more informally that a tensor product is cartesian if it has both projections and diagonals, and the semicartesian case is when there are only projections, so the “dual” is when there are only diagonals.

Posted by: Mike Shulman on August 27, 2016 4:43 AM | Permalink | Reply to this

Re: Foundations of Mathematics

Oh good! I was hoping there wasn’t some secret set-theoretical content packaged into the “cartesian” part of semicartesian monoidal category because I am aware of some dual semicocartesian (?) monoidal categories that may be of interest.

Nathalie Wahl and Oscar Randal-Williams have a very interesting preprint Homological stability for automorphism groups.

In it, they observe that families of groups often assemble into a braided monoidal groupoid (𝒢,,0)(\mathcal{G}, \oplus, 0), with the groups appearing as the automorphism groups for each object and the monoidal product being some sort of “direct sum” operation.

Assuming certain conditions are satisfied, they construct a strict monoidal category (𝒞,,0)(\mathcal{C}, \oplus, 0) that is semicocartesian, with the unit initial. The objects of 𝒞\mathcal{C} are the same as the objects of 𝒢\mathcal{G} with

hom(A,B):=colim 𝒢𝒢(A,B). \hom(A,B) := colim_\mathcal{G} \mathcal{G}(-\oplus A,B).

The initial unit provides canonical injections into monoidal products which are used to state conditions for the monoidal category to be homogeneous.

A functor F:𝒞F \colon \mathcal{C} \to \mathbb{Z}-Mod is referred to as a “coefficient system”. One of their main theorems proves that the homology of automorphism groups constructed from 𝒞\mathcal{C} with coefficients in FF stabilizes provided a certain semi-simplicial set constructed from the data of 𝒞\mathcal{C} is sufficiently connected.

Several classical homological stability theorems can be seen as special cases of their result. New applications prove homological stability of families of groups with “twisted coefficients.”

Posted by: Emily Riehl on August 29, 2016 4:47 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I also just remembered that semicartesian monoidal categories appeared on this blog about 7 years ago. I see that I knew then already that slicing under the unit coreflects monoidal categories into semi-cocartesian ones, but for some reason I failed to dualize it. (Probably because examples of slicing under the unit — “pointed objects” — seemed more common in nature than examples of slicing over the unit — “augmented objects”.) Also interesting to see the colax monoidal functors appearing there too, since they also recently popped up in the magnitude homology thread.

Posted by: Mike Shulman on August 26, 2016 4:19 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Some interesting examples of semicartesian categories also come up in categorical probability theory: our old friends FinProb and FinStoch. Intuitively, what’s going here is that there’s a unique way to throw away a random variable, but there a many ways to pair up two random variables, depending on how they are correlated. In some sense, this is what probability theory is all about!

So when John mentions the category of convex sets as being semicartesian, I guess that this is with respect to the tensor product as monoidal structure. This also makes sense from the point of view of information theory: a convex set can be thought of as the state space of some weird hypothetical system, where the convex combinations represent stochastic mixtures of states. Semicartesian then again describes the above property: there’s a unique way to throw away a system, but the state of a composite system is not uniquely determined by the pair of “reduced states” that one gets by throwing away either part.

For a dual example, take the category of C *C^*-algebras with unital completely positive maps. This is again an example of the same flavour, this time describing quantum physics in the Heisenberg picture, which reverses the arrows.

I’m mentioning all this in the hope that it will provide some more intuition for semicartesian categories and why they may be natural after all. They seem to come in many places where the whole is more than the sum of its parts.

Posted by: Tobias Fritz on August 28, 2016 4:53 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I mentioned your claim that

the category of stochastic matrices is enriched over convex spaces with tensor product

over at the thread that has motivated this one.

The question to ask then is whether there are interesting homology theories to be found in these probabalistic/stochastic cases based on Mike’s recipe.

Posted by: David Corfield on August 29, 2016 7:47 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

What’s a minimal dense subcategory of the category of convex spaces? Perhaps those non-cancellative semi-lattice examples make this a little trickier.

Posted by: David Corfield on August 29, 2016 10:51 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

We don’t actually need a dense subcategory; with the current perspective all we need is a coefficient system defined on some small subcategory that we can extend to the whole category by left Kan extension. One obvious interesting small subcategory of convex spaces that pops to my mind is the category of simplices, which means (if I’m not making a mistake) that any convex-space-enriched category should have homology with coefficients in any cosimplicial abelian group.

However, as I said in the other thread (which is, I suppose, where we actually ought to discuss this), it’s hard for me to see what that homology will actually look like without a more explicit description of the tensor product of convex spaces. Can anyone help? For instance, what is the tensor product of an interval with itself? Or more generally of two simplices?

Posted by: Mike Shulman on August 29, 2016 6:45 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

when John mentions the category of convex sets as being semicartesian…

You link to a paper by the three of you where neither ‘semicartesian’, ‘convex set’, ‘convex space’, nor even ‘product’ is mentioned.

Some other place?

Posted by: David Corfield on August 30, 2016 11:30 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Whoops, sorry! I was going to link to John’s comment above.

I’m travelling these days and don’t have much time to follow the discussion, but let me just quickly sketch the tensor product of convex spaces. It should be exactly what one would expect by the fact that convex spaces are model of a commutative algebraic theory: to construct CDC\otimes D for convex spaces CC and DD, take the free convex space (=simplex) generated by C×DC\times D, and impose the relations (λx+(1λ)y)z=λxz+(1λ)yz,(\lambda x + (1-\lambda)y)\otimes z = \lambda x\otimes z + (1-\lambda) y\otimes z, and similarly for the other tensor factor, where I’m using (somewhat abusive) vector space notation to denote the convex combinations.

For example, the tensor product of the simplex with nn vertices and the simplex with mm vertices is the simplex with nmn\cdot m vertices.

Starting next week, I can try to participate in the discussion a bit more if this turns out to be an interesting direction. A couple of years ago, I’ve been wondering whether there could be a homology theory for polytopes. For example, there’s the canonical convex-linear map from the 3-simplex to the square which takes vertices to vertices. This map does not have a convex-linear section. Is there some homological invariant that could detect this, in a manner similar to how homology in algebraic topology detects that S 1S^1 is not a retract of D 2D^2? A closely related question is this: is there an interesting notion of derived category for modules over the semiring of nonnegative reals?

Posted by: Tobias Fritz on August 30, 2016 5:03 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Yes, the explicit description as a quotient of a free object is obvious, but it doesn’t give me much intuition. In particular, C×DC\times D is generally infinite, so the free convex space it generates is rather large (and it seems a stretch to describe it as a “simplex”).

I guess maybe I see how you are getting the tensor product of simplices though. Since the simplex with nn vertices (usually known as the (n1)(n-1)-simplex) is the free convex space on nn points (the vertices), and the “free convex space” functor takes products to tensor products (I think this is true for any commutative theory), the tensor product of an (n1)(n-1)-simplex and an (m1)(m-1)-simplex should be an (nm1)(n m-1)-simplex.

Can we say anything about the tensor products of the convex spaces that appear as hom-spaces in the convexly-enriched category of stochastic matrices?

Posted by: Mike Shulman on August 30, 2016 6:54 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Yes, your statement about the simplices is exactly right! And I agree that calling a free convex space on infinitely many generators a simplex is a bit of a stretch.

For a better intuition about the tensor product, it may help to think in terms of the homogenization. The homogenization of a convex space is the convex cone (module over the semiring +\mathbb{R}_+) that it generates. The homogenization of a tensor product of convex spaces is just the module tensor product of the individual homogenizations. Is this a more intuitive picture?

In FinStoch, the hom-set nmn\to m is the nn-fold cartesian power of the (m1)(m-1)-simplex. Tensor products of convex spaces of this type give polytopes that are known as Bell polytopes. For example, FinStoch(2,2)FinStoch(2,2)FinStoch(2,2)\otimes FinStoch(2,2) is an 8-dimensional polytope whose facets are well-understood.

I haven’t yet gotten around to looking at Mike’s homology theory in sufficient detail, so I’m not quite sure how to proceed. But if we need to know more e.g. about these Bell polytopes, I can probably help out.

Posted by: Tobias Fritz on August 30, 2016 8:19 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

That seems somewhat promising. That means that if we use simplices as our “test objects” for the homology theory, then the “chains” will be simplices living convexly inside such polytopes. But it seems like probably a lot of computation would need to be done before finding anything interesting.

Posted by: Mike Shulman on August 31, 2016 6:16 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Mike wrote:

In particular, C×DC\times D is generally infinite, so the free convex space it generates is rather large (and it seems a stretch to describe it as a “simplex”).

I actually like to picture the free convex space on an infinite set as an infinite-dimensional simplex. To justify this: since ‘free’ functors preserve colimits, the free convex set on an infinite set should be the colimit of the free convex sets on all its finite subsets, which are finite-dimensonal simplices.

So, for example, I believe the free convex set on a countable set should be simply the union

Δ = n=0 Δ n \Delta^\infty = \bigcup_{n=0}^\infty \Delta^n

where we think of each nn-simplex Δ n\Delta^n as sitting inside the next one as the face containing all vertices except the last. That’s not so hard to visualize, in the usual way where we say “1-dimensional, 2-dimensional, 3-dimensional, … okay, I get it.”

In short, a countable-dimensional simplex Δ \Delta^\infty is no more scary than the topologist’s friend S S^\infty.

But when we’re trying to visualize the tensor product of two convex sets CC and DD, we don’t want to think about the free convex set on the underlying set of C×DC \times D. This approach would make even the tensor product of finite-dimensional vector spaces seem like a terrifying entity. What we do with vector spaces is take the cartesian product of chosen bases, and let the linear combinations fend for themselves.

Of course this is eased by the fact that every vector space is free on some set. That’s not true for convex sets. But we can do stuff like say “every convex polytope in n\mathbb{R}^n is the convex hull of its set of vertices, so to form the tensor product of two convex polytopes I’ll start by taking the cartesian product of their sets of vertices, then form the free convex set on that (a simplex), and then mod out by some relations.”

I’m not saying this is easy: I’ve tried stuff like visualizing the tensor product of two squares, and I can’t claim to reliably do it. But it’s not insanely hard to figure these things out if one allows oneself the use of pencil and paper.

Posted by: John Baez on September 1, 2016 5:58 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

In short, a countable-dimensional simplex Δ \Delta^\infty is no more scary than the topologist’s friend S S^\infty.

Fair enough. Although to be honest, I still find S S^\infty a little scary (as a topological space, that is — as a homotopy type, of course, it’s just contractible). (-:

every convex polytope in n\mathbb{R}^n is the convex hull of its set of vertices, so to form the tensor product of two convex polytopes I’ll start by taking the cartesian product of their sets of vertices, then form the free convex set on that (a simplex), and then mod out by some relations.

Ah, very nice. More abstractly, I guess we’re using the fact that the tensor product “distributes over presentations”, so if we have a presentation of two convex spaces as coequalizers of free ones, then we get a similar presentation of their tensor product.

Posted by: Mike Shulman on September 1, 2016 5:01 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I hadn’t thought to see if you had defined S S^{\infty} as a homotopy type. I see from this exercise-solution file (line 1504) that one can define S S^{\infty} as a colimit of higher inductively defined nn-spheres and then prove contractibility (line 1674).

And you can show it’s the shape of topological S S^{\infty}?

I wonder if anything else about it is of interest, such as that the bundle S CP S^{\infty} \to \mathbf{CP}^{\infty}, or K(,2)K(\mathbb{Z}, 2), is the universal principal U(1)U(1)-bundle.

Posted by: David Corfield on September 2, 2016 8:15 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

And you can show it’s the shape of topological S S^{\infty}?

I assume you’re asking whether we can show in cohesive HoTT that the topological 𝕊 \mathbb{S}^{\infty} has contractible shape (since homotopical S S^\infty is contractible). That’s a good question; I haven’t tried!

Posted by: Mike Shulman on September 2, 2016 10:50 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Can Bruhat-Tits buildings be seen as enriched in a semicartesian category? Todd Trimble wrote some accompanying notes, which mentions

the so-called “local approach” due to Tits is that a building is like a metric space, except that “distances” between points are measured not by real numbers but by elements in Coxeter groups.

He also wrote some comments starting here, including

it’s better to shift perspective from Coxeter groups to “Coxeter monoids” which form certain types of quantales.

What other condition does one need? That the unit object is the top element?

Posted by: David Corfield on September 4, 2016 10:08 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

That’s more or less right. Metric spaces are categories enriched in a semicartesian category ([0,] op,+)([0, \infty]^{op}, +) in which the monoidal unit is terminal (and there may be more axioms to account for, e.g., we may want to include symmetry). Similarly, buildings whose “distances” are measured in a Coxeter group WW may be defined to be certain categories enriched in a semicartesian category (W op,)(W_\infty^{op}, \cdot) in which the monoidal unit is terminal, and there are more axioms to account for. (This W W_\infty, derived from the Coxeter group WW, is something Jim Dolan had playfully dubbed the “Murphy monoid”; there’s a kind of shaggy dog story there having to do with “Murphy’s law”. In my notes I use the more sober name Bruhat monoid. It’s a certain ordered monoid, or to be more precise an ordered *\ast-monoid.)

There’s a certain perspective on enrichment that enters here, which I learned from Jim Dolan. Let’s take the simple case of enrichment in an ordered monoid MM. Then the data of an MM-enriched category is a set XX together with a function d:X×XMd: X \times X \to M, satisfying the usual axioms

d(x,y)d(y,z)d(x,z)d(x, y) \cdot d(y, z) \geq d(x, z)

ed(x,x)e \geq d(x, x)

where the order relation on MM is written \geq and ee is the identity element of MM.

Another way of saying it is this: consider the poset of up-sets of MM, 2 M2^M, equipped with Day convolution coming from M opM^{op}. This is a quantale or monoidal sup-lattice. Consider the set of binary relations on XX, 2 X×X2^{X \times X}. Under relational composition, this is also a monoidal sup-lattice. Then the enrichment axioms on dd can be rephrased as saying that

2 d:2 M2 X×X2^d: 2^M \to 2^{X \times X}

is a lax monoidal functor.

It’s super-easy to get turned around here, so let me check that’s right. Take the case of principal prin(u)prin(u) up-sets in MM (we are writing the order relation as \geq, so actually that’s {mM:um}\{m \in M: u \geq m\}). Then 2 d(prin(u))={(x,y)X×X:ud(x,y)}2^d(prin(u)) = \{(x, y) \in X \times X: u \geq d(x, y)\}. Lax monoidality says (in part) that

2 d(prin(u))2 d(prin(v))2 d(prin(uv))2^d(prin(u)) \circ 2^d(prin(v)) \subseteq 2^d(prin(u v))

(where \circ denotes relational composition) which is just a way of saying that if ud(x,y)u \geq d(x, y) and vd(y,z)v \geq d(y, z), then uvd(x,z)u v \geq d(x, z). This is the triangle inequality in disguise.

This may look like an exercise in pointless abstract nonsense, except that the precise axioms for buildings (which are not just enriched categories of this sort; there are more axioms to account for) can be neatly reformulated in this categorical language. The notes at my nLab page, referred to before, give some details (although the proofs that the categorical description exactly matches the usual Tits definition have not yet been recorded there).

(If there’s interest in this, we can continue the discussion.)

In general, if VV is a small monoidal category, then I think we can similarly say that enrichment in VV amounts to a structure of lax monoidal functor of the form

Set d:Set VSet X×XSet^d: Set^V \to Set^{X \times X}

where the monoidal structure on Set X×XSet^{X \times X} is given by composition of endospans. Basically the lax monoidal structural constraint comes down to a family of functions of the form

V(u,d(x,y))×V(v,d(y,z))V(uv,d(x,z)).V(u, d(x, y)) \times V(v, d(y, z)) \to V(u \otimes v, d(x, z)).

Posted by: Todd Trimble on September 5, 2016 1:28 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Wow, very cool! In the comment thread David linked to, Todd said

as of now, I don’t know what all this might be good for, aside from possible aesthetic appeal to those of a categorical bent.

I guess at the moment, with homology of enriched categories in mind, we can fantasize about a homology and magnitude theory for buildings (which Simon speculated about in that same thread).

The “certain perspective on enrichment” is surprising to me and I don’t really understand it yet. Does it relate directly to some other abstract definition of enrichment without dropping all the way down to the explicit version? Is it at all related to enriched categories as lax functors of bicategories into BV\mathbf{B}V, or the “Categories enriched on two sides” of Kelly-Labella-Schmitt-Street (which I also never really understood)? Does the function dd have to be given as data, or can you express it in terms of a lax monoidal functor Set VSet X×XSet^V \to Set^{X\times X} with properties? Of course a monoid in Set X×XSet^{X\times X} is just an unenriched category, and also the same as a lax monoidal functor out of 11. And Set X×XSet^{X\times X} is also just an endo-hom-category of the bicategory Span(Set)Span(Set). Hmm.

Also, though, do I need to understand this definition of enrichment to think about buildings as enriched categories? In particular, can the additional building axioms be reformulated directly in more ordinary enriched-category language (even if they aren’t as neat)?

And can we work through some concrete small example to see what the resulting “homology of a building” looks like? Maybe the case of projective planes that you sketched here?

Posted by: Mike Shulman on September 5, 2016 5:11 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Mike, thanks for your interest and your questions, as always!

I’ll have to think about them. But let me just say what those additional axioms are that give buildings. (Really, I had better try to reconstruct the proof that these do the job. For now I’m going on memory that they do.)

One bit of low-hanging fruit is accounting for symmetry (as in symmetry for metric spaces). Here we need the notion of *\ast-quantale or *\ast-monoidal category. Of course the *\ast-operator on relations 2 X×X2^{X \times X} is relational opposite (permute the two factors XX). On the Bruhat monoid side, where W (D)W_\infty(D) is presented in terms of a Coxeter diagram or matrix DD, we have generators s is_i satisfying relations of the form s i 2=s is_i^2 = s_i and s is js i=s js is js_i s_j s_i \ldots = s_j s_i s_j \ldots where both sides are alternating words of length m ijm_{i j} (given by DD). We say a word ww is reduced if it cannot be written in shorter form using these relations, and the *\ast-operator on W (D)W_\infty(D) may be described as taking a word ww to its opposite gotten by writing it backwards. This is well-defined.

In general, if d:X×XMd: X \times X \to M gives an enrichment of XX in a *\ast-monoid MM, then we say XX is symmetric if 2 d:2 M2 X×X2^d: 2^M \to 2^{X \times X} commutes with the *\ast-operators on these quantales. Of course if a monoid MM is commutative to begin with (as in the case ([0,],+)([0, \infty], +)), then we can take the *\ast to be the identity, and this leads for example to the symmetry axiom for metric spaces.

(Does a symmetry condition enter somewhere in the description of presheaves/sheaves as categories enriched in a bicategory that is due to Bob Walters? I have a vague memory this is so.)

The other axioms for buildings (which I still don’t have a good understanding of) involve the biclosed structure of 2 M,2 X×X2^M, 2^{X \times X}. At least I can say them quickly, and might as well throw them out there for your consideration.

Definition: Given a Coxeter diagram DD, a DD-building consists of a function d:X×XW (D)d: X \times X \to W_\infty(D) such that the map 2 d:2 W (D)2 X×X2^d: 2^{W_\infty(D)} \to 2^{X \times X} is a strict morphism of biclosed *\ast-monoidal categories (not just lax).

This means that 2 d2^d preserves the residuation operators //, \\backslash on the nose, as well as the tensor product. (One residuation is the *\ast-conjugate of the other, so it suffices that one of the residuations be preserved.)

All this seems to generalize just fine to more general enriched contexts (although we would want preservation of the pseudo kind, not strict), but I don’t recall what it means exactly even for the case of metric spaces, although I recall spending some time thinking about it.

Posted by: Todd Trimble on September 5, 2016 3:15 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Thinking about it for a few minutes, my guess for metric spaces is that preserving the tensor product means that “distances are divisible” in the sense that if d(x,z)=a+bd(x,z) = a+b, then there exists a yy with d(x,y)=ad(x,y)=a and d(y,z)=bd(y,z)=b. Not sure about preserving the residuations.

Posted by: Mike Shulman on September 6, 2016 2:29 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

The condition that “distances are divisible” is closely related to Menger convexity, which I just wrote about here.

Posted by: Tom Leinster on September 6, 2016 5:06 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

It won’t help too much here on the nn-Café, but here’s part of the program for the Australian Category Theory seminar at Macquarie University on Wednesday 21 September 2016:

4:00 pm in C5A 307.
Speaker: James Dolan.
Title: Incidence geometries as enriched categories.

Posted by: John Baez on September 20, 2016 4:11 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

We need to get some spies in Australia.

Posted by: Mike Shulman on September 20, 2016 6:00 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I’ve been talking with James a bit about the buildings as enriched categories, and so I thought I would try to figure out how to take the magnitude of such a building using Tom’s recipe here. The first problem is we need a way of assigning a size to each element of the Bruhat monoid, and I see no obvious (and non-trivial) way to do this. I don’t really understand what’s going on with all this recent progress involving homology; do we still expect to be able to “size” the objects of the category we are enriching over ?

Posted by: Simon Burton on October 15, 2016 8:55 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

No, magnitude homology doesn’t require a size measure. Instead it requires coefficient functors VAbV\to Ab. Are there any interesting ones of those for the Bruhat monoid?

Posted by: Mike Shulman on October 15, 2016 10:01 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

The simplest example is the monoid generated by LL and PP with LPL=PLPLPL=PLP and every element is idempotent. So it has order six, and is non-commutative. The six elements are I,L,P,LP,PLI, L, P, LP, PL and LPL=PLP.LPL=PLP. The Bruhat order makes this monoid into a POSET, and is defined by “word inclusion”, ie. ILLPLPL=PLPI \le L \le LP \le LPL=PLP etc. With this POSET structure we now have a (non-symmetric) monoidal category.

But I don’t think there is any internal hom for this Bruhat monoid that makes it into a closed monoidal category, which is what we need for enrichment to work. So I think I’m stuck for now.

Posted by: Simon Burton on October 16, 2016 4:04 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

My own recollection, now more than 10 years old, is that the Bruhat-Coxeter monoid is biclosed (or residuated), if we follow the analogy with the real numbers being a base of enrichment for metric spaces. That is, we use instead (W,)(W, \geq) (just as we use ([0,],)([0, \infty], \geq)) where the adjunction would take the form

uvwiffuw/vu v \geq w \qquad iff \qquad u \geq w/v

in which case we would have w/v= uvwuw/v = \bigwedge_{u v \geq w} u (taking this conjunction wrt to the order \leq). I do believe it all works out.

Incidentally, there is also a *\ast operator on WW which, when applied to a reduced word ww, writes it in reverse. This is an anti-involution: I *=II^\ast = I and (uv) *=v *u *(u v)^\ast = v^\ast u^\ast. And so it will interchange the left and right internal homs, e.g., v\w=(w */v *) *v \backslash w = (w^\ast/v^\ast)^\ast.

It seemed to me at the time though that this, while nice, was a bit of a side issue, because the more important consideration for buildings used instead the quantale of down-sets of W op=(W,)W^{op} = (W, \geq), or the quantale of up-sets [(W,),2][(W, \leq), \mathbf{2}]. Just having enrichment in (W,)(W, \geq) as monoidal poset amounts to having a lax monoidal functor of the form

[d,2]:[W,2][X×X,2][d, \mathbf{2}]: [W, \mathbf{2}] \to [X \times X, \mathbf{2}]

where on the right we have the standard quantale of relations on the set XX, whereas buildings (over WW) were characterized as just those structures (X,d:X×XW)(X, d: X \times X \to W) such that [d,2][d, \mathbf{2}] was not just lax monoidal, but was strong *\ast-monoidal and preserved the quantalic internal homs strongly. (I had tried to press that latter bit, strong preservation of the homs, to James back in 2005 or 2006, but I don’t think I ever managed to fully convince him.)

Posted by: Todd Trimble on October 16, 2016 11:25 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

If it is of interest, here are a few more details on calculating the biclosed structure of the Bruhat-Coxeter monoid W(D)W(D) (based on a given Coxeter diagram or Coxeter matrix DD).

In the first place, an elementary manipulation with adjunctions shows that for u,v,wW=W(D)u, v, w \in W = W(D), we have (w/u)/v=w/(vu)(w/u)/v = w/(v u). Thus if we write an element vv as a product of generators s 1s 2s ns_1 s_2 \ldots s_n coming from the group/monoid presentation based on DD, we are reduced to determining w/sw/s for a general generator ss.

This involves some of the theory of Coxeter groups and decidability of equality for Coxeter groups, but the general statement IIRC is that if ww can be presented as usu s where both uu and usu s are reduced words, then w/s=uw/s = u (i.e., the evaluation of the word uu as an element of WW); otherwise w/s=ww/s = w. There is a remark here that the set of reduced words for either the Coxeter group or the Bruhat-Coxeter monoid is the same.

Posted by: Todd Trimble on October 17, 2016 10:07 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I don’t think magnitude homology requires the enriching monoidal category to be closed anyway.

Posted by: Mike Shulman on October 18, 2016 8:23 AM | Permalink | Reply to this

Re: Monoidal Categories with Projections

I’ve been hacking on this a bit more. I decided to try to follow the graph magnitude homology as this seems to be close to what is needed for categories enriched over the Bruhat monoid.

The first problem I’m having is reconciling the definition of nn-chains with the differential maps, as in John’s question here. For example, an nn-chain can zigzag between two objects in XX whose distance apart is LL, and since LL is idempotent the total chain will have length LL. Omitting any object from the chain yields a chain with a consecutive repetition and also with length LL. So defining the nn-chains as being tuples without consecutive repetitions doesn’t seem to work here.

Posted by: Simon Burton on October 19, 2016 10:38 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

If you start from the general definition of magnitude homology, then this sort of issue is dealt with automatically. As Tom points out there (end of Step 4 of the long version), for general VV there doesn’t seem to be as simple a formula for the normalized chain complex as there is in the metric-spaces case with the special coefficient systems δ \delta_\ell (which is what gives you the “no consecutive repetitions” rule), but the unnormalized one should work fine.

Posted by: Mike Shulman on October 19, 2016 11:38 PM | Permalink | Reply to this

Re: Monoidal Categories with Projections

Back in 2013, I was lamenting the fact that we were yet to hear more of the work Todd had described in a couple of 2007 posts ‘Concrete Groups and Axiomatic Theories’:

a whole slew of interesting developments, in which we view Jim’s orbi-simplex idea as a geometric description of a general axiomatic theory, which in turn is related to the idea of viewing Tits buildings as “quantized” axiomatic theories, and also perhaps to the theory of classifying toposes and their “Galois theory”.

Maybe now, if we get the right spy.

By the way, I was drawn back to that logical invariance post by the talk given by Steve Awodey that I mentioned. If the ordinary logical connectives arise as invariants under maximal permutation symmetry, perhaps aspects of HoTT arise as invariants under maximal equivalence symmetry.

Hmm, is there a way to make sense of what’s invariant under the action of Aut(G)Aut(G) on G nG^n, for some \infty-groupoid GG, or even some multiple type version?

Posted by: David Corfield on September 20, 2016 9:36 AM | Permalink | Reply to this

Post a New Comment