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: Presentation of traced SMC of relations between finite sets

Robin Piedeleu (Jun 17 2021 at 14:26):

I believe it is known that the figure below gives a presentation of the traced monoidal category of relations between finite sets (with the disjoint union as monoidal product). The version without the trace is an instance of the more general presentation of matrices over a semiring, for which I know of several references. I have been looking for a reference for the traced version without success. Do you have any idea who, if anyone, wrote this down?
image.png

Nick Hu (Jun 17 2021 at 14:32):

Did you make that image yourself? In my MSc thesis I studied a right-adjoint pseudomonoid presentation with a tracing axiom (like your B12) which can be interpreted in the bicategory of profunctors to yield traced monoidal categories, but it seems slightly different

Robin Piedeleu (Jun 17 2021 at 14:35):

Yes, it's part of a larger equational theory I have. Relations live within it as a traced monoidal subcategory and I wanted to cite the relevant paper.

Robin Piedeleu (Jun 17 2021 at 14:37):

And I'm not sure what the relationship with your work is, but you could interpret these diagrams in the categoy of profunctors if you wanted: any category (by which I mean object in the category of profunctors) carries the four needed operations (copy, delete and their adjoints) and the cups and caps which come from the op duality. I'm not sure about axioms B7-B12, though.

Guillaume Boisseau (Jun 18 2021 at 10:56):

The result is mentioned here https://arxiv.org/abs/1601.02307 (thm 7.2)

Guillaume Boisseau (Jun 18 2021 at 10:59):

Oh sorry, I missed the trace thing. Don't remember seeing anything like that; it's usually compact closure or nothing

Nick Hu (Jun 18 2021 at 12:20):

Robin Piedeleu said:

And I'm not sure what the relationship with your work is, but you could interpret these diagrams in the categoy of profunctors if you wanted: any category (by which I mean object in the category of profunctors) carries the four needed operations (copy, delete and their adjoints) and the cups and caps which come from the op duality. I'm not sure about axioms B7-B12, though.

The bicategory of profunctors is a compact closed bicategory, i.e. it's not Cartesian, so I'm not sure what you mean by it having copy-delete. B10 looks like the counit of the adjunction $\otimes_* \dashv \otimes^*$ and B11 looks like the unit of the adjunction $I_* \dashv I^*$. However, those 2-morphisms aren't bidirectional in my approach, with B10 only going left-to-right and B11 only going right-to-left. I'm not sure about B7-B9, but my feeling (which you can feel free to take with a grain of salt, as I'm not too familiar with what you're trying to do) is that you're missing equations corresponding to the unit and counit of those adjunctions respectively (unless they are subsumed by B7-B9 in some non-obvious way). The point is that there is a nice embedding theorem from $\mathbf{Cat} \to \mathbf{Prof}$ if you want to study functors: a profunctor is morally the same as a functor exactly when it has a right adjoint; furthermore, every functor can be embedding covariantly and contravariantly as a profunctor (denoted $(=)_*$ and $(-)^*$ respectively - these are sometimes called representable profunctors, and essentially any profunctor isomorphic to a representable one is morally a functor). In this case, the functor you're interested in is $\mathcal{C} \times \mathcal{C} \xrightarrow{\otimes} \mathcal{C}$, and in addition imposing this traced structure on it. The categorical algebra corresponding to (/symmetric) monoidal categories is a right-adjoint (/commutative) pseudomonoid (at least in the context of $\mathbf{Prof}$). Of course, it's possible that I've wholly misinterpreted what you're looking for entirely --- at least for me, it's quite easy to see how your axioms arise from that (barring B7-B9) --- but hopefully some of what I said is remotely useful :sweat_smile:

Nathanael Arkor (Jun 18 2021 at 12:25):

Presumably you mean that the tensor product for the compact structure is not cartesian, because Prof itself is a cartesian bicategory (given by coproduct of categories).

Nick Hu (Jun 18 2021 at 12:26):

Yes, that refines what I said to be a bit more precise, thanks @Nathanael Arkor

Robin Piedeleu (Jun 21 2021 at 09:04):

Prof with the product of categories is a Cartesian bicategory in the sense of Carboni and Walters' paper. This does not mean that it is Cartesian as a 1-category, but that it has a monoidal structure resembling products in a suitably lax sense (this paper only deals with the order-enriched case; the gory details for the fully bicategorical case are in Cartesian bicategories II by the same authors, but I never had the guts to tackle it). The basic idea is that every object carries a given comonoid structure, with a right adjoint monoid structure, and every morphism is a lax (co)monoid homomorphism. A simple example is Rel, the bicategory of sets, relations, and inclusions between them. The monoidal product is (confusingly) the usual Cartesian product of sets and the comonoid structure over a set $X$ given by $\{(x,(x,x))| x\in X\}$ and $\{(x,\bullet)| x\in X\}$ with adjoints the converse relations.

For Prof with the product of categories as monoidal product, the comultiplication of the comonoid structure over a given category/object $\mathcal C$ is the profunctor $X,Y_1,Y_2\mapsto hom_{\mathcal C}(X,Y_1)\times hom_{\mathcal C}(X,Y_2)$ and the counit is the constant profunctor at the terminal category $1$. These are the morphisms I called copy and delete above. Their right adjoints are $X_1,X_2,Y\mapsto hom_{\mathcal C}(X_1,Y)\times hom_{\mathcal C}(X_2,Y)$ and $1$ respectively, giving a monoid structure. Note that these always exist, regardless of whether $\mathcal C$ itself has products or is a monoidal category. They may not satisfy the other axioms of my opening post (I have not given it any thought---it might be interesting to figure out if or when they do).

One final caveat: as I said, this may only makes sense if we consider Prof as a bicategory whose 2-cells are thin (by considering only the existence of natural transformations, maybe with some extra properties, between two profunctors instead of explicitly keeping track of which natural transformations). You can think of the equalities in my initial post as denoting the existence of bijective natural transformations. In the fully general case, we would have pseudo-(co)monoids etc.

Nick Hu (Jun 21 2021 at 12:18):

My interpretation of what you said is that there is copy-delete for the representable profunctors, but it's weaker (?) for non-representable profunctors

Guillaume Boisseau (Jun 21 2021 at 13:06):

Considering Prof as having thin 2-cells sounds like working in Rel

Mike Shulman (Jun 21 2021 at 13:49):

Another way to describe the structure of the cartesian product of categories on Prof, which arguably looks less ad-hoc than a cartesian bicategory and is often simpler to work with, is to say that the double category Prof has finite products, in the natural sense that the diagonal functor $\rm Prof \to Prof\times Prof$ and projection $\rm Prof \to 1$ have right adjoints in the 2-category of double categories. See for instance Aleiferi's Cartesian Double Categories with an Emphasis on Characterizing Spans.

Robin Piedeleu (Jun 22 2021 at 09:16):

Nick Hu said:

My interpretation of what you said is that there is copy-delete for the representable profunctors, but it's weaker (?) for non-representable profunctors

I'm not sure what you mean by "copy-delete for the representable profunctors". Do you mean that the comonoid operations are natural for these? That might be true but they exist regardless, even if all profunctors do not distribute over them (this is analogous to the situation in Rel with the cartesian product).

Robin Piedeleu (Jun 22 2021 at 09:18):

Guillaume Boisseau said:

Considering Prof as having thin 2-cells sounds like working in Rel

Hmm...yes it has a very Rel-like feeling (and, in a sense, this is what I was trying to explain above) but they are different 1-categories.

Robin Piedeleu (Jun 22 2021 at 09:22):

Mike Shulman said:

Another way to describe the structure of the cartesian product of categories on Prof, which arguably looks less ad-hoc than a cartesian bicategory and is often simpler to work with, is to say that the double category Prof has finite products, in the natural sense that the diagonal functor $\rm Prof \to Prof\times Prof$ and projection $\rm Prof \to 1$ have right adjoints in the 2-category of double categories. See for instance Aleiferi's Cartesian Double Categories with an Emphasis on Characterizing Spans.

Oh, I'd like to understand this better. Thanks for the reference!

I'm not sure how ad-hoc the structure of a Cartesian bicategory for profunctors is because I never read Cartesian bicategories II. For Rel (and more broadly, categories of relations constructed in the standard way over a category of maps with sufficient structure), the first paper of Carboni & Walters has a characterisation theorem which exhibits it as canonical in some sense. Anyway, even that does not feel as clean as the property you stated.

Guillaume Boisseau (Jun 22 2021 at 22:57):

Robin Piedeleu said:

Guillaume Boisseau said:

Considering Prof as having thin 2-cells sounds like working in Rel

Hmm...yes it has a very Rel-like feeling (and, in a sense, this is what I was trying to explain above) but they are different 1-categories.

Hm I expected this to match better, because Rel is Bool-enriched Prof and thinning is a nice map from Set to Bool

Dan Marsden (Jun 23 2021 at 07:10):

Isn't Rel a full subcategory of Bool-enriched Prof? The objects of the latter are preorders, and in Rel you restrict to the discrete stuff.

Guillaume Boisseau (Jun 23 2021 at 09:15):

Oops you're right, I forgot the objects had structure too