Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: directional structured cospans?

Tobias Fritz (May 31 2021 at 16:52):

Structured cospans are useful for constructing categories of networks in which there is no distinction between inputs and outputs, such as electrical networks.

Has anyone considered a more general kind of cospan where the two legs would be restricted to two separate subcategories, therefore allowing for the construction of categories of networks for which inputs and outputs do play different roles?

Background: I'm currently working with a summer student on constructing free Markov categories, and it seems to be possible to do so using a construction very similar to structured cospans, and in particular to the construction of free hypergraph categories, modulo this directionality issue (related to the fact that Markov categories are almost never compact closed). It would be very helpful if we could employ an already existing framework for this problem rather than either developing it ourselves first or doing our particular case "by hand".

Cole Comfort (May 31 2021 at 20:09):

Suppose we have a situation with spans of the form $F X \leftarrow A \rightarrow G Y$, for $F: \mathbb X \to \mathbb A$, $G: \mathbb Y \to \mathbb A$. Then in order for composition to be well defined, the objects in $F \mathbb X$ and $G \mathbb Y$ must be the same, so I don't know quite exactly how this would work.

I have worked with some categories of structured cospans where the left legs are monics and the right legs are arbitrary maps, the structure-functor being the inclusion of the full subcategory: such categories being discrete cartesian restriction categories (which are not compact closed). But I don't know if this is what you want. In a sense, the left and right legs are in different subcategories, however, the feet are both in the same subcategory.

Jules Hedges (May 31 2021 at 20:20):

I've also come across spans where the left and right legs have different restrictions on them, probably in a different situation (for symmetric lenses)

John Baez (May 31 2021 at 23:46):

@Tobias Fritz - I have not seen anyone develop a theory of structured cospans that's generalized in the way you describe. So, your student can the pleasure of being the first to do it. It's always fun to learn something while generalizing it.

Tobias Fritz (Jun 01 2021 at 06:38):

Thanks, all, for the useful input!

Cole Comfort said:

I have worked with some categories of structured cospans where the left legs are monics and the right legs are arbitrary maps, the structure-functor being the inclusion of the full subcategory: such categories being discrete cartesian restriction categories (which are not compact closed). But I don't know if this is what you want. In a sense, the left and right legs are in different subcategories, however, the feet are both in the same subcategory.

Yes, that's the sort of thing I have in mind. @Cole Comfort, @Jules Hedges, are those works of yours already out? That could possibly still save us some time, even if nobody has yet worked out the general abstract framework as indicated by John.

Chad Nester (Jun 01 2021 at 07:31):

Cole Comfort said:

I have worked with some categories of structured cospans where the left legs are monics and the right legs are arbitrary maps, the structure-functor being the inclusion of the full subcategory: such categories being discrete cartesian restriction categories (which are not compact closed). But I don't know if this is what you want. In a sense, the left and right legs are in different subcategories, however, the feet are both in the same subcategory.

A small correction: discrete cartesian restriction categories arise as categories of spans with monic left leg.

Morgan Rogers (he/him) (Jun 01 2021 at 08:22):

It might not go in the direction you need, but the dual of the situation you're describing appeared in a paper I finished earlier this year; see Section 2.2 in that preprint: it involves spans where the right leg is arbitrary and the left leg is in a "stable class" of morphisms.

Morgan Rogers (he/him) (Jun 01 2021 at 08:23):

Such spans correspond to (or at least are sufficient data to encode) morphisms in the topos of sheaves on a corresponding site.

Morgan Rogers (he/him) (Jun 01 2021 at 08:29):

There's a bunch of info in that section (certainly more than I ever needed) about the correspondence between such spans and morphisms in the topos. This might be useful to you if you are thinking of your cospans as morphisms up to some notion of equivalence: taking sheaves on the opposite of your category could give a neat way to recover the resulting category.

Cole Comfort (Jun 01 2021 at 08:34):

Chad Nester said:

Cole Comfort said:

I have worked with some categories of structured cospans where the left legs are monics and the right legs are arbitrary maps, the structure-functor being the inclusion of the full subcategory: such categories being discrete cartesian restriction categories (which are not compact closed). But I don't know if this is what you want. In a sense, the left and right legs are in different subcategories, however, the feet are both in the same subcategory.

A small correction: discrete cartesian restriction categories arise as categories of spans with monic left leg.

Yes it works for structured spans. I guess I should have said where the left leg is epic :sweat_smile: .

Cole Comfort (Jun 01 2021 at 08:38):

My work probably isn't very enlightening, but partial map categories are just plain old categories of spans where the left leg is monic and this generalized to the structured span case.

Cole Comfort (Jun 01 2021 at 08:39):

With a stability condition on the pullback of monics.

Cole Comfort (Jun 01 2021 at 08:53):

My motivation is to give complete monoidal theories for these partial map categories, which fail to be props, so I look at a full subcategory thereof instead.

Tobias Fritz (Jun 01 2021 at 08:53):

Morgan Rogers (he/him) said:

It might not go in the direction you need, but the dual of the situation you're describing appeared in a paper I finished earlier this year; see Section 2.2 in that preprint: it involves spans where the right leg is arbitrary and the left leg is in a "stable class" of morphisms.

Thanks, that is nice, and it's interesting to know that this gives a way to describe the hom-sets between objects of the original site in a sheaf topos. But as far as I understand, those spans are unstructured spans, so it isn't quite what we need.

BTW, I'm a bit shocked to learn that the canonical functor $\mathcal{C} \to \mathrm{Sh}(\mathcal{C}, J)$ is neither full nor faithful in general! Taking indicator sheaves on a topological space is clearly fully faithful, right? So this seems to be an issue that distinguishes general sites from topological spaces (and locales I guess).

Zhen Lin Low (Jun 01 2021 at 08:55):

The canonical functor is a fully faithful embedding iff the coverage is subcanonical.

Tobias Fritz (Jun 01 2021 at 08:56):

Oh yes, that makes sense! Then it's clear by Yoneda.

Morgan Rogers (he/him) (Jun 01 2021 at 09:37):

Tobias Fritz said:

Morgan Rogers (he/him) said:

It might not go in the direction you need, but the dual of the situation you're describing appeared in a paper I finished earlier this year; see Section 2.2 in that preprint: it involves spans where the right leg is arbitrary and the left leg is in a "stable class" of morphisms.

Thanks, that is nice, and it's interesting to know that this gives a way to describe the hom-sets between objects of the original site in a sheaf topos. But as far as I understand, those spans are unstructured spans, so it isn't quite what we need.

Ah fair enough, from the request it wasn't clear that you still were leaning on structured things. That said, it could well be possible to translate the (dual of) the structured cospan construction to a topos-theoretic setting via morphisms of sites. I don't have enough insight into the nature of applications of these things to comment on whether that would be a worthwhile endeavour :wink:

Tobias Fritz (Jun 01 2021 at 10:05):

Cole Comfort said:

My work probably isn't very enlightening, but partial map categories are just plain old categories of spans where the left leg is monic and this generalized to the structured span case.

Yep, I suspect that the construction that we're looking for and your particular categories of structured spans would be instances of the same general framework. In any case, that's a very cool paper!

Joachim Kock (Jun 01 2021 at 10:50):

The first study of span categories with legs in distinct classes of maps is probably Quillen's Q-constrcution from 1972 (but it is not unlikely that Bénabou and Yoneda considered this earlier, even if they didn't write about it).

Joachim Kock (Jun 01 2021 at 10:58):

The Feynman category of graphs in the sense of Kaufmann and Ward is actually a category of directional structured cospans. They define it using the Borisov-Manin category of graphs by restricting the objects to be disjoint unions of corollas. This is a bit intricate, mostly because the Borisov-Manin category is very ad hoc.

The point is that in the BM category, every morphism factors as a grafting followed by a compression, so in the KW category, the arrows can be described as being grafting-followed-by-compression, where the end objects are disjoint unions of corollas but the middle object is allowed to be a general graph.

Now by a theorem of mine [Cospan construction of the graph category of Borisov and Manin, https://arxiv.org/abs/1611.10342] the BM category is the category of cospans in the Joyal-Kock category of graphs in which the right leg is active and the left leg is inert (generic and free in the original terminology). Now the BM graftings correspond to JK inert maps, and the BM compressions correspond to JK active maps backwards, and altogether the BM category is the JK category with the active maps 'reversed', so that the grafting-followed-by-compression become inert-active cospans.

In conclusion, the Kaufmann-Ward Feynman category of graphs is the directional structured cospan category obtained from the JK category by taking inert-active cospans and allowing only disjoint-unions-of-corollas as 'feet'. This is an example of structured cospans via the inclusion of disjoint-unions-of-corollas into the category if all graphs. (The notion of structured cospans did not exist at that time (I think), but the example is mentioned in Remark 6.7 of the paper.)

Chad Nester (Jun 01 2021 at 11:00):

What about categories of fractions? NLab points me to an article from 1967 (Gabriel and Zisman).

Chad Nester (Jun 01 2021 at 11:01):

It’s entirely possible that they don’t consider categories of spans — I haven’t read it!

Zhen Lin Low (Jun 01 2021 at 11:59):

I don't think GZ used categories of spans explicitly, but you could certainly use them in a calculus of fractions situation. Jardine calls them "cocycles" in this context.

Cole Comfort (Jun 01 2021 at 12:26):

Tobias Fritz said:

Cole Comfort said:

My work probably isn't very enlightening, but partial map categories are just plain old categories of spans where the left leg is monic and this generalized to the structured span case.

Yep, I suspect that the construction that we're looking for and your particular categories of structured spans would be instances of the same general framework. In any case, that's a very cool paper!

Yes, one thing I have thought about is that there is a certain condition regarding the factorization of monics which allows one to glue a (structured) partial map category with its opposite, up to structured spans of monics in order to obtain the full structured span category.

Mike Shulman (Jun 01 2021 at 14:16):

Is what you want achievable by just constructing the whole bicategory of structured cospans and then restricting to a sub-bicategory consisting of the cospans whose legs live where you want them to?

Jules Hedges (Jun 01 2021 at 15:53):

Tobias Fritz said:

Yes, that's the sort of thing I have in mind. Cole Comfort, Jules Hedges, are those works of yours already out? That could possibly still save us some time, even if nobody has yet worked out the general abstract framework as indicated by John.

It took me a while to figure out what paper I was thinking of - it was https://arxiv.org/abs/1903.03671 by Mike Johnson and Brendan Fong, specifically the main results from around section 5 involve spans in a certain category whose left legs satisfy an extra condition

Tobias Fritz (Jun 01 2021 at 19:28):

Mike Shulman said:

Is what you want achievable by just constructing the whole bicategory of structured cospans and then restricting to a sub-bicategory consisting of the cospans whose legs live where you want them to?

Probably yes, and I'm thinking that this is what we'll most likely end up doing, although it does feel like a bit of a hack. In our case, this amounts to constructing free Markov categories (more precisely, actually free CD categories) as subcategories of the corresponding free hypergraph categories.

Cole Comfort (Jun 01 2021 at 21:32):

I think that there is this menagerie of different subcategories of bicategories of relations whose relationships to each other are relatively unexplored.