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: deprecated: algebra & CT

Topic: Algebraic presentations and traced categories


view this post on Zulip Mateo Torres-Ruiz (May 04 2023 at 13:34):

Hi. I've been wondering whether there's any known results giving necessary and sufficient conditions on algebraic presentations of monads such that we can claim that the monad we are looking at is traced.

view this post on Zulip Matteo Capucci (he/him) (May 04 2023 at 19:01):

If someone knows about it that's @Joseph Collins

view this post on Zulip Robin Piedeleu (May 05 2023 at 12:22):

Bumping this thread because I'd also like to know the answer! I'm interested in the compact closed case as well (as in: conditions on the algebraic presentation of a monad that make its Kleisli category compact closed).

view this post on Zulip JS PL (he/him) (May 06 2023 at 07:58):

So you might be interested in my paper with Hassei:
https://arxiv.org/pdf/2208.06529.pdf
where we look at "traced monads" which are monads that lift traced monoidal structure to their Eilenberg-Moore categories.

Here are also some slides on the subject:
https://richardblute.files.wordpress.com/2021/11/lemay-novfest.pdf
and I'll be giving an updated talk about this at CMS2023 in a few weeks.

view this post on Zulip JS PL (he/him) (May 06 2023 at 07:59):

It remains an open question if "Traced monads" can be defined without mentioning the Eilenberg-Moore category. (Hassei has been working on this for 20+ years I believe) We give a solution in certain cases to this using Hopf monads.

view this post on Zulip JS PL (he/him) (May 06 2023 at 08:01):

Monads that lift compact closed structure to their Eilenberg-Moore categories are precisely Hopf monads:
https://arxiv.org/abs/1003.1920
https://arxiv.org/abs/math/0604180
http://www.tac.mta.ca/tac/volumes/33/37/33-37.pdf

view this post on Zulip JS PL (he/him) (May 06 2023 at 08:02):

Robin Piedeleu said:

Bumping this thread because I'd also like to know the answer! I'm interested in the compact closed case as well (as in: conditions on the algebraic presentation of a monad that make its Kleisli category compact closed).

I don't know the answer for Kleisli categories. But Hassei mentioned that he and others (I think he mentioned Paul-André Méliès?) looked at lifting trace to Kleisli categories and could only come up with nasty identities.

view this post on Zulip JS PL (he/him) (May 06 2023 at 08:03):

However I am very much interested in lifting trace/compact closed structure to Kleisli catgories as well.

view this post on Zulip JS PL (he/him) (May 06 2023 at 08:04):

(Donc @Robin Piedeleu si tu veux on peut en discuter plus!)

view this post on Zulip Robin Piedeleu (May 10 2023 at 09:14):

Thanks, @JS PL (he/him)!

I'm also interested in the question of what makes the Kleisli/EM category of a monad (over Set) traced/compact-closed. That is, when the underlying category is not necessarily compact nor traced. All Set-monads I know of whose Kleisli category is compact-closed are of the form XSXX \mapsto S^X for some semiring SS. It's somewhat mysterious to me. Why is that? Is that necessary? Sounds unlikely.

view this post on Zulip Tobias Fritz (May 10 2023 at 09:48):

That's an interesting question! Here's a partial answer on when the Kleisli cat SetT\mathsf{Set}_T of a monad TT on Set\mathsf{Set} is compact closed. First of all, in order for SetT\mathsf{Set}_T to be symmetric monoidal, TT needs to be a commutative monad. This at least makes T1T1 into a commutative monoid (which in the semiring case is the underlying multiplicative monoid; if TT is in addition additive, then T1T1 is even a semiring). Assuming compact closure, we then get natural isomorphisms:

TXSetT(1,X)SetT(X,1)(T1)X.TX \cong \mathsf{Set}_T(1, X) \cong \mathsf{Set}_T(X^*, 1) \cong (T1)^{X^*}.

If one could now argue that XX must be canonically self-dual, then this turns into your TX=SXTX = S^X with S=T1S = T1. But I'm not sure how to complete the argument.

view this post on Zulip Nathanael Arkor (May 10 2023 at 10:05):

As an aside, a 2-dimensional version of this argument implies that the bicategory of distributors/profunctors is compact closed, since the bicategory of distributors is the Kleisli bicategory for the presheaf construction, which is pseudo-commutative, and PC(P1)CSetC\mathcal P \mathbf C \simeq (\mathcal P 1)^{\mathbf C^\circ} \simeq \mathrm{Set}^{\mathbf C^\circ} (cf. Remark 5.9 of Di Liberti–Loregian's On the unicity of formal category theories).

view this post on Zulip Tobias Fritz (May 10 2023 at 10:38):

Conjecture: A Kleisli category SetT\mathsf{Set}_T for a commutative monad TT on Set\mathsf{Set} is compact closed if and only if TT is isomorphic to a monad of the form XQXX \mapsto Q^X, where QQ is a commutative quantale.


Here, the functoriality of such a monad on a function f:XYf : X \to Y is the map QXQYQ^X \to Q^Y given by q(yxf1(y)q(x))q \mapsto \left(y \mapsto \bigvee_{x \in f^{-1}(y)} q(x) \right), and the monad multiplication QQXQXQ^{Q^X} \to Q^X looks like α(xqQXq(x)α(q))\alpha \mapsto \left(x \mapsto \bigvee_{q \in Q^X} q(x) \ast \alpha(q) \right) . This recovers the usual powerset monad for Q={0,1}Q = \{0,1\}.

Note also that the above conjecture really is an equivalence of properties rather than structures, since a monad on Set\mathsf{Set} is commutative in at most one way, and being compact closed is also a mere property of a symmetric mnoidal category.

view this post on Zulip Robin Piedeleu (May 10 2023 at 11:23):

Thanks, that clarifies a lot!

I'm also inclined to believe your conjecture. I think to prove it will require some cardinality argument: for more general semirings, finite sets are always dualisable in the Kleisli category of SXS^X. What seems to make the whole Kleisli category compact-closed is the ability to take arbitrary sums in your semiring (suprema for quantales).

view this post on Zulip JS PL (he/him) (May 10 2023 at 11:49):

Robin Piedeleu said:

That is, when the underlying category is not necessarily compact nor traced.

Ah that is a very interesting question! I'd be interested in the answer too.

view this post on Zulip JS PL (he/him) (May 10 2023 at 11:51):

Tobias Fritz said:

Conjecture: A Kleisli category SetT\mathsf{Set}_T for a commutative monad TT on Set\mathsf{Set} is compact closed if and only if TT is isomorphic to a monad of the form XQXX \mapsto Q^X, where QQ is a commutative quantale.

Yes this seems quite plausible. It seems that neat argument you wrote above seems to point in that direction. And as @Robin Piedeleu says, having infinite sums is needed to define the cap.

view this post on Zulip JS PL (he/him) (May 10 2023 at 11:52):

Tobias Fritz said:

TXSetT(1,X)SetT(X,1)(T1)X.TX \cong \mathsf{Set}_T(1, X) \cong \mathsf{Set}_T(X^*, 1) \cong (T1)^{X^*}.

If one could now argue that XX must be canonically self-dual, then this turns into your TX=SXTX = S^X with S=T1S = T1. But I'm not sure how to complete the argument.

This is very neat! However I also don't see how to argue X=XX^\ast = X. Of course, if you assume the Kleisli category is "self-dual compact closed" then your argument is finished.

view this post on Zulip JS PL (he/him) (May 10 2023 at 11:56):

For the traced story, the Kleisli category of the maybe monad _{}\_ \sqcup \lbrace \ast \rbrace is traced on the coproduct. So there seems to be more possible monads for this side of the story.

view this post on Zulip Nathanael Arkor (May 10 2023 at 12:07):

Tobias Fritz said:

But I'm not sure how to complete the argument.

If the duality in the Kleisli category is induced by an involution on the original category, then you get (T1)X((T1))X(T1)^{X^*} \cong ((T1)^*)^X. (This is the case in the 2-dimensional example, for instance.)

view this post on Zulip Nathanael Arkor (May 10 2023 at 12:09):

Which suggests to me that either the duals in the compact closed structure should always be induced in this way or, in general, the correct expression is SXS^{X^*}, and being able to remove the dual is a special situation.

view this post on Zulip Tom Hirschowitz (May 10 2023 at 14:56):

For traced structure wrt coproduct on the Kleisli category, there is a whole bunch of work by @Sergey Goncharov, Stefan Milius, and others on all sorts of iterative monads, see for example Complete Elgot monads and coalgebraic resumptions.

view this post on Zulip Sergey Goncharov (May 10 2023 at 15:07):

Thanks, @Tom Hirschowitz for popularizing our work! We investigated in depth the case of coCartesian trace on the Kleisli category of a monad. According to Hyland and Hasegawa, such coCartesian trace is the same as a Conway fixpoint operator, i.e. for a monad TT, it has the profile f:XT(Y+X)(f:XTY)f: X\to T(Y+X)\mapsto (f^\dagger: X\to TY), plus the laws of Conway iteration. These are generally known to be too weak, so a standard remedy is to add the so called uniformilty principle w.r.t. pure morphisms. We call the resulting monads Elgot monads. Regarding Cartesian tensor, let alone proper tensor, we did not analyse them in the context of monads.

view this post on Zulip JS PL (he/him) (May 10 2023 at 21:30):

Ah this is super interesting paper @Sergey Goncharov -- definitely on a topic that aligns with some of my current research projects near to my heart.

view this post on Zulip JS PL (he/him) (May 10 2023 at 21:31):

Sergey Goncharov said:

Regarding Cartesian tensor, let alone proper tensor, we did not analyse them in the context of monads.

Well one difficulty with providing a traced Cartesian structure on a Kleisli category is that unlike coproducts which come for free on a Kleisli category, products do not come for free. So there's even more extra structure needed here.

view this post on Zulip JS PL (he/him) (May 10 2023 at 21:32):

Nathanael Arkor said:

Tobias Fritz said:

But I'm not sure how to complete the argument.

If the duality in the Kleisli category is induced by an involution on the original category, then you get (T1)X((T1))X(T1)^{X^*} \cong ((T1)^*)^X. (This is the case in the 2-dimensional example, for instance.)

I was under the impression that there was no involution on the category SETSET?

view this post on Zulip Sergey Goncharov (May 10 2023 at 21:48):

JS PL (he/him) said:

Sergey Goncharov said:

Regarding Cartesian tensor, let alone proper tensor, we did not analyse them in the context of monads.

Well one difficulty with providing a traced Cartesian structure on a Kleisli category is that unlike coproducts which come for free on a Kleisli category, products do not come for free. So there's even more extra structure needed here.

Yes, exactly. From the semantics perspective, Cartesian trace is recursion (f ⁣:Γ×XX)(f ⁣:ΓX)(f\colon \Gamma\times X\to X)\mapsto (f_\dagger\colon\Gamma\to X), and technical aspects aside, Kleisli category is not the best place to interpret it, except for some corner cases, like the lifting monad on dcpo, for which Kleisli and EM coincide. Recursion is dual to iteration. But if we want to dualise iteration on monads, we also should dualize monads and get recursion on co-monads. At least, this is what semantic considerations suggest.

view this post on Zulip JS PL (he/him) (May 10 2023 at 21:59):

Another example is the power set monad on SETSET, whose Kleisli category is RELREL and this has a Cartesian trace, which is the same as the coCartesian trace because RELREL has biproducts. But this is an example where the Kleisli and the EM do not coincide.

view this post on Zulip JS PL (he/him) (May 10 2023 at 22:00):

Sergey Goncharov said:

But if we want to dualise iteration on monads, we also should dualize monads and get recursion on co-monads. At least, this is what semantic considerations suggest.

But yes, it is much more natural to consider Cartesian trace in coKleisli categories.