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

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.

Matteo Capucci (he/him) (May 04 2023 at 19:01):

If someone knows about it that's @Joseph Collins

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).

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.

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.

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

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.

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.

JS PL (he/him) (May 06 2023 at 08:04):

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

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 $X \mapsto S^X$ for some semiring $S$. It's somewhat mysterious to me. Why is that? Is that necessary? Sounds unlikely.

Tobias Fritz (May 10 2023 at 09:48):

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

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

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

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 $\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).

Tobias Fritz (May 10 2023 at 10:38):

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

Here, the functoriality of such a monad on a function $f : X \to Y$ is the map $Q^X \to Q^Y$ given by $q \mapsto \left(y \mapsto \bigvee_{x \in f^{-1}(y)} q(x) \right)$, and the monad multiplication $Q^{Q^X} \to Q^X$ looks like $\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\}$.

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

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 $S^X$. What seems to make the whole Kleisli category compact-closed is the ability to take arbitrary sums in your semiring (suprema for quantales).

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.

JS PL (he/him) (May 10 2023 at 11:51):

Tobias Fritz said:

Conjecture: A Kleisli category $\mathsf{Set}_T$ for a commutative monad $T$ on $\mathsf{Set}$ is compact closed if and only if $T$ is isomorphic to a monad of the form $X \mapsto Q^X$, where $Q$ 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.

JS PL (he/him) (May 10 2023 at 11:52):

Tobias Fritz said:

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

If one could now argue that $X$ must be canonically self-dual, then this turns into your $TX = S^X$ with $S = 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^\ast = X$. Of course, if you assume the Kleisli category is "self-dual compact closed" then your argument is finished.

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.

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^*} \cong ((T1)^*)^X$. (This is the case in the 2-dimensional example, for instance.)

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 $S^{X^*}$, and being able to remove the dual is a special situation.

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.

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 $T$, it has the profile $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.

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.

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.

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^*} \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 $SET$?

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\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.

JS PL (he/him) (May 10 2023 at 21:59):

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

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.