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.
Bruno Gavranović (Oct 20 2022 at 18:10):What structure on a monad do we need such that its Kleisli category is cartesian?
I'm noticing that the Kleisli category of the powerset monad has products (given by disjoint union of sets). On the other hand, Kleisli categories of any of the usual probability monads don't have products.
Both of these Kleisli categories describe kinds of nondeterministic processes, and it was my understanding nondeterminism => noncartesianity.
For instance, Markov categories are famously non-deterministic, and the subcategory of their deterministic processes is precisely the cartesian subcategory.
But in the case of the Kleisli category of the powerset monad (i.e. the category of relations) that intuition seems to be violated.
Morgan Rogers (he/him) (Oct 20 2022 at 18:48):The forgetful functor from the Kleisli category for a monad T creates products when T preserves them, so that's a sufficient condition.
Paolo Perrone (Oct 21 2022 at 08:18):Bruno Gavranovic said:
What structure on a monad do we need such that its Kleisli category is cartesian?
I'm noticing that the Kleisli category of the powerset monad has products (given by disjoint union of sets). On the other hand, Kleisli categories of any of the usual probability monads don't have products.
Both of these Kleisli categories describe kinds of nondeterministic processes, and it was my understanding nondeterminism => noncartesianity.
For instance, Markov categories are famously non-deterministic, and the subcategory of their deterministic processes is precisely the cartesian subcategory.But in the case of the Kleisli category of the powerset monad (i.e. the category of relations) that intuition seems to be violated.
Part of the structure of Markov category is a (specified) tensor product.
When you form a Kleisli category (of a commutative monad over a cartesian category ) and consider it a Markov category, you are taking as monoidal product the one induced by the cartesian product of . In the case of the power set monad, that's the one induced by the cartesian product of sets.
If you take another monoidal product on the Kleisli category, for example the disjoint union, then you have a different Markov category, with different structure and interpretation.
Tim Campion (Oct 22 2022 at 16:51):If the Kleisli category is semiadditive, then finite coproducts and finite products coincide. The Kleisli category has finite coproducts so long as the underlying category for the monad has finite coproducts, so in this case it will also have finite products. This gives a large class of examples which includes the powerset monad (if the powerset monad is the one I think it is -- with algebras the complete lattices).
Beyond that, one case where you have products is if every algebra is free (and the underlying category has products). But this doesn't happen too often. The monad on whose algebras are pointed sets is an example. So is the monad on whose algebras are "torsors over a varying division algebra".
dusko (Oct 22 2022 at 20:24):Bruno Gavranovic said:
What structure on a monad do we need such that its Kleisli category is cartesian?
I'm noticing that the Kleisli category of the powerset monad has products (given by disjoint union of sets). On the other hand, Kleisli categories of any of the usual probability monads don't have products.
Both of these Kleisli categories describe kinds of nondeterministic processes, and it was my understanding nondeterminism => noncartesianity.
For instance, Markov categories are famously non-deterministic, and the subcategory of their deterministic processes is precisely the cartesian subcategory.But in the case of the Kleisli category of the powerset monad (i.e. the category of relations) that intuition seems to be violated.
it helps to make the question more precise. first off, the category of all algebras (usually the EM-presentation) inherits the cartesian product from the base category, so one situation to get out of the way is the question when does the inclusion of free algebras into all algebras (ie KL into EM) reflect products. for the product of free algebras to be even just a tensor product the monad must be commutative. that is if and only if. (if it is not commutative but just strong, we get john power's and edmund robinson's premonoidal structure.) now for that monoidal structure to be cartesian, we need the diagonals and the projections (which are always inherited) to be natural. the first obviously boils down to the monad unit being cartesian. the second seems like a separation of the algebraic operations (like the commutativity of the monad is the commutativity of the operations). it must have been spelled out in universal algebra papers from the 70s, gratzer or people like that. maybe even in johnstone's papers about varieties.
but you are asking a more general question: when is the kleisli category itself cartesian, without the requirement that the cartesian product of free algebras is the same as the product of algebras.
since free algebras of course always inherit the coproducts from the base category, if the coproducts happen to be biproducts, there we go. that covers your example of free semilattices, also free abelian monoids (ie the powerset and the multiset monads). the category of free abelian monoids is the free category with biproducts and the category of relations is the free one with biproducts and idempotent scalars. but those examples are of course very special. the general property that there is a free algebra that is universal for pairs of homomorphisms into free algebras seems like an interesting question in universal algebra. it involves the separation property within the signature like above, but maybe it gets complicated down the road. not sure. could be a paper in it.
the idea that "Markov categories are famously nondeterministic" seems wrongheaded to me. take the category of pointed sets, or partial functions (which are the same over decidable sets). this is of course a kleisli category, and it couldn't be more deterministic. take its slice into 1. this is a markov category. it still couldn't be more deterministic, could it? everything in it is single-valued. take the slice into 1 of any kleisli category over a cartesian category -- you get a markov category. nondeterminism is incidental to whatever monad you start from.
it is of course important to always think of examples. but in this case it is interesting how examples can be misleading :)
in any case, you have been asking nice questions recently :)
Tobias Fritz (Oct 23 2022 at 09:22):A silly terminological point: in a Markov category, the monoidal unit is required to be terminal. In other words, every morphism in a Markov category is total. The category of partial functions is therefore not a Markov category (with respect to cartesian product as monoidal structure). What @dusko calls a "Markov category" is known as a gs-monoidal category or CD category.
So @Bruno Gavranovic is right with his statement that Markov categories are all about nondeterminism. To be more precise, a Markov category in which all morphisms are deterministic is the same thing as a cartesian monoidal category, and these are quite boring and degenerate as Markov categories.
Tobias Fritz (Oct 23 2022 at 09:23):I'm not saying that Markov categories are necessarily more interesting than the gs-monoidal categories that Dusko seems to have in mind. I'm just trying to clarify the terminology.
dusko (Oct 23 2022 at 19:16):Tobias Fritz said:
A silly terminological point: in a Markov category, the monoidal unit is required to be terminal. In other words, every morphism in a Markov category is total. The category of partial functions is therefore not a Markov category (with respect to cartesian product as monoidal structure). What dusko calls a "Markov category" is known as a gs-monoidal category or CD category.
So Bruno Gavranovic is right with his statement that Markov categories are all about nondeterminism. To be more precise, a Markov category in which all morphisms are deterministic is the same thing as a cartesian monoidal category, and these are quite boring and degenerate as Markov categories.
if is a monoidal category with tensor unit , then the slice category is a monoidal category whose tensor unit is terminal. for any commutative monad over a cartesian category, the kleisli category is monoidal, and has the identity on as the terminal object. the slice , where is the category of partial functions, has the identity on 1 as the terminal object. it satisfies all axioms of a markov category. ah, i see, the diagonal was natural already in , so now we have a cartesian category. but this is incidental. any commutative monad what.so.ever gives a markov category . are we saying that all commutative monads whatsoever accommodate markov chains and probability theory? last time i mentioned that is a completely nondegenerate example of a markov category. andrey markov introduced the markov chains to study conditional probabilities of words in pushkin's "eveniy oniegin" back in 1906. there are no markov chains in . with all due respect to your otherwise thorough and much appreciated work, it's unfair to markov to distract from his work by attaching his name to a framework where he couldn't count the word frequencies. it distracts from his ideas, used by kolmogorov and shannon and GPT3 and attracts attention to the long-standing tradition of categorical terminological infelicities.
"cartesian monoidal categories" is another example. it seems to suggest that there are cartesian non-monoidal categories. someone said that the qualifier "cartesian monoidal" is justified by the fact that peter freyd used "cartesian" for "finitely complete", and ptj adopted it in the elephants. so "cartesian monoidal" then does not imply "cartesian" anymore.
it would be nice if you would mention somewhere that monoidal categories with a chosen comonoid on every object have been classified to some degree of detail in the "classical and quantum structuralism" paper by bob coecke and eric paquette and me, back in the 2000s (on arxiv i am sure). none of us will mind if we need to call them gs-monoidal or CD, but saying that the categories with comonoids where the counit is terminal characterize probability is a little optimistic.
dusko (Oct 23 2022 at 20:03):PS i was also a little optimistic above. bob and eric and i bob and eric i did characterize stochastic operators in the structuralism paper a bit more tightly --- BUT using the classical (basis) structures, which are not just comonoids but frobenius algebras. so so the question is: can we characterize positive maps without a dagger? that is i guess what already alberti and uhlmann in their book had been struggling with...
Tobias Fritz (Oct 24 2022 at 06:38):Right. Note that I've never claimed that Markov categories characterize probability or that all commutative monads accommodate Markov chains and probability (whatever that means exactly). And as you're rightly intuiting, that's far from true! For example, we've proven de Finetti's theorem in purely categorical terms based on a number of additional axioms, among which the existence of conditionals is the most important. And then there are other Markov categories, in particular versions of Rel, in which de Finetti's theorem can be formulated but ends up being false. Nevertheless, I think that it's a useful intuition to think of a morphism in an arbitrary Markov category as an abstract generalization of a Markov kernel.
Perhaps embarrassingly, I don't know much about Markov's work at all, so maybe you're right that the name "Markov category" is a big stretch relative to that. That being said, there are also other relevant considerations in addition to historical accuracy, in particular how useful and evocative a term is for us in the present and in the future. And in that respect, "Markov category" seems to perform better than the terms "affine CD category" (Cho & Jacobs 2017) and "category of information transformers" (Golubtsov, late 90's, modulo some technical differences).
Perhaps you would have similar reservations about the term "abelian category"? I personally think that it's a perfectly good name, and better than "model category" for sure.
Yes, I'm aware of a lot of other literature that involves Frobenius structures and/or daggers, in particular by Bob and various sets of coauthors. As far as classical probability is concerned, the problem with that is that it cannot accommodate measure-theoretic probability.
Bruno Gavranović (Oct 25 2022 at 12:46):Thanks for all the responses! I think I understand what my confusion was after @Paolo Perrone's answer.
Paolo Perrone said:
Part of the structure of Markov category is a (specified) tensor product.
When you form a Kleisli category (of a commutative monad over a cartesian category ) and consider it a Markov category, you are taking as monoidal product the one induced by the cartesian product of . In the case of the power set monad, that's the one induced by the cartesian product of sets.
If you take another monoidal product on the Kleisli category, for example the disjoint union, then you have a different Markov category, with different structure and interpretation.
Right, I was confused about the fact that the monoidal product I had in mind of the Kleisli category of the powerset monad is cartesian, but I was forgetting that it was induced in a different way than we usually induce the monoidal product of the Kleisli category of the distribution monad. The latter is induced by the cartesian product in the base, whereas in the former I used the coproduct.
So this makes a bit more sense now