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: event: MIT Categories Seminar

Topic: July 16: Tobias Fritz' talk

Paolo Perrone (Jul 14 2020 at 19:40):

Hello all! Here's the official discussion thread for Tobias Fritz' talk, "Probability theory with Markov categories".
When: Thursday, July 16th, 12 noon EDT (Boston time)
Zoom meeting:
https://mit.zoom.us/j/280120646
Meeting ID: 280 120 646

Youtube live stream:
https://youtu.be/wQDufwP84y0

Oliver Shetler (Jul 14 2020 at 19:55):

Will there be a permanent link afterward? I'll be without internet during that time.

Paolo Perrone (Jul 14 2020 at 19:57):

Oliver Shetler said:

Will there be a permanent link afterward? I'll be without internet during that time.

The live stream is available for some hours, after which we'll upload a recording.

Tobias Fritz (Jul 15 2020 at 23:16):

Hi all! My slides are now available here. Looking forward to the discussion tomorrow!

Paolo Perrone (Jul 16 2020 at 15:45):

Hello all. The talk will start in 15 minutes!

Eigil Rischel (Jul 16 2020 at 16:53):

@Tobias Fritz : I meant to ask about this when you mentioned in back during the Categorical Probability and Statistics conference, but never got around to it: can you elaborate on your "information theoretic" example? What's the compatibility between the functions $X^n \to Y^n$? How should I think about that function? What sort of asymptotic equivalence are we quotienting by?

Paolo Perrone (Jul 16 2020 at 17:12):

From JS: “Jets and differential linear logic” by James Wallbridge

Paolo Perrone (Jul 16 2020 at 17:14):

https://gather.town/8u0TXRzLpBsKwHjz/mit-categories-seminar
password: "yonedalemma"

Paolo Perrone (Jul 16 2020 at 19:25):

Video here!
https://youtu.be/xSNqaPTduks

JS PL (he/him) (Jul 29 2020 at 19:34):

Not sure where else to ask this question but: are their any interesting examples of Markov categories where the tensor product is a coproduct? What can we say about Markov categories in this case? (Of course, one example is that any category with finite biproducts is a Markov category)

Tobias Fritz (Jul 30 2020 at 00:13):

That's an oddly interesting question, @JS Pacaud Lemay! I take it as asking whether the monoidal structure in a cocartesian monoidal Markov category is necessarily a biproduct. I don't know! But now I'm also quite curious about this, and perhaps someone else can resolve this based on the following. There's a lot of structure in the problem, so let me describe how far I've gotten.

For starters, the monoidal unit $I$ is terminal as part of the definition of Markov category, initial by assumption, and therefore a zero object. For every object $X$, we have the coproduct inclusions $i_\ell, i_r : X \to X \otimes X$, and we also have the comultiplication $i_\nabla : X \to X \otimes X$. In the other direction, we have the two projections $p_\ell, p_r$ and the codiagonal $p_\nabla : X \otimes X \to X$. So there are three canonical morphisms in either direction! These satisfy a bunch of equations, and in particular the following:

$p_\ell i_\nabla = p_r i_\nabla = 1_X$
$p_\nabla i_\ell = p_\nabla i_r = 1_X$
$p_\ell i_\ell = p_r i_r = 1_X$
$p_r i_\ell = p_\ell i_r = 0_X$

as well as the bialgebra law, which can be derived from the universal property of the coproduct. These conditions all together are nicely self-dual, and of course they hold if $\otimes$ is the biproduct. But do they imply that $\otimes$ is a biproduct? If not, perhaps they could make for an interesting kind of category in their own right? @Martti Karvonen has worked on characterizations of biproducts, so perhaps he will know.

I presume that you're asking this because it has the flavour of linear logic, right? So perhaps @Valeria de Paiva can help out?

JS PL (he/him) (Jul 30 2020 at 06:46):

Thanks for the reply @Tobias Fritz - for a cocartesian monoidal Markov category, the coproduct is not necessarily a biproduct.

JS PL (he/him) (Jul 30 2020 at 06:54):

For example, as you point out in your paper, for any symmetric monoidal category $X$, then categor of a cocommutative comonoids and counit preserving morphisms is a Markov category, call it $C[X]$. Take $X= SET^{op}]$, then $C[SET^{op}$ is the opposite category of the category whose objects are commutative monoids, and whose maps are unit preserving morphisms. Then $C[SET^{op}]$ has coproducts but not products.

The coproduct structure in $C[SET^{op}]$ corresponds to the Cartesian product of sets, with the pointwise monoid structure. The injection maps are the projection maps $M_1 \times M_2 \to M_i$. The copy map in $C[SET^{op}]$ corresponds to the binary operator of a monoid (which I'll write as $+$) $M \times M \to M$, $x,y \mapsto x + y$. But since copy isn't natural (for example $\mathbb{R} \to \mathbb{R}^2$, $x \mapsto x^2$ preserves to unit but not the addition), then it follows that the coproduct in $C[SET^{op}]$ is not a product.

JS PL (he/him) (Jul 30 2020 at 07:08):

Tobias Fritz said:

I presume that you're asking this because it has the flavour of linear logic, right?

Actually, I'm asking because I work with "Cartesian left additive categories". A Cartesian left additive category can be defined as a category with finite products $\times$ and terminal object $\ast$, equipped with two (not necessarily natural) families of maps:
$A \times A \xrightarrow{+_A} A$ and $\ast \xrightarrow{0_A} A$,
such that $(A, +_A, 0)$ is a commutative monoid and also that:
$+_{A \times B} = \langle +_A \circ (p_A \times p_A), +_B \circ (p_B \times p_B) \rangle$ and $0_{A \times B} = \langle 0_A, 0_B \rangle$ (which is the compatibility with the monoidal structure).

Now one can ask for the Cartesian left additive to be reduced, which amounts to asking that $0_A$ be natural, so $f \circ 0_A = 0_C$. And it turns out that the opposite of a reduced Cartesian left additive category is precisely a cocartesian Markov category (and vice-versa of course)

Tobias Fritz said:

If not, perhaps they could make for an interesting kind of category in their own right?

Oh absolutely! There are lots of interesting reduced Cartesian left additive categories, here are two I have in mind:

1) For a commutative ring $R$, let $R[x_1, x_2, ..., x_n]_\ast$ be the non-unital commutative ring of polynomials in $n$ variables whose constant term is zero.
Let $POLY_{red}$ be the category whose objects are $n \in \mathbb{N}$ and where a map $P: n \to m$ is a tuple $P= \langle p_1, ..., p_m \rangle$ where $p_i \in R[x_1, x_2, ..., x_n]_\ast$.

2) For a commutative ring $R$, let $R [[x_1, x_2, ..., x_n]]_\ast$ be the non-unital commutative ring of power series in $n$ variables whose constant term is zero.
Let $POW_{red}$ be the category whose objects are $n \in \mathbb{N}$ and where a map $P: n \to m$ is a tuple $P= \langle p_1, ..., p_m \rangle$ where $p_i \in R[[x_1, x_2, ..., x_n]]_\ast$. That the constant zero term is important here, because we wouldn't be able to compose power series without this assumption.

What I don't know is if the opposite category of a reduced Cartesian left additive category is interesting from a Markov category theory perspective.

JS PL (he/him) (Jul 30 2020 at 07:25):

(I'll also point that those two examples of reduced CLACs are also examples of (reduced) Cartesian differential categories, but maybe that's a story for another time!)

Tobias Fritz (Jul 30 2020 at 12:44):

D'oh, right!

So an essential feature of CLACs like $POLY_{red}$ and $POW_{red}$ is that there's a canonical way to add parallel morphisms, but it's not an enrichment: composition is additive only in the first argument but not in the second, like substitution of polynomials. (BTW is this what your skew enrichment is about?) Then I can see that there will be plenty of examples like this with significance in differential algebra and geometry. In the smooth context, I suppose that $CartSp^{op}$ would be another one; or really any opposite of a category of geometric objects with a linear structure, right?

As a Markov category, $C[Set^{op}]$ has so far mainly been useful as a source of counterexamples. More generally, (opposites of) CLACs are somewhat conceptually orthogonal to categories of Markov kernels, and the latter are the categories around which the theory of Markov categories is being developed at the moment. But one of the theses in my talk was that the breadth of Markov categories is underexplored, and that the landscape is vastly larger and more interesting than one would imagine when having categories of Markov kernels in mind. So far we have little idea of what one gets upon instantiating theorems of probability theory in those categories, such as 0/1-laws, theorems on sufficient statistics, or the BSS theorem on the comparison of statistical experiments. In a dream world, these theorems will turn out to be interesting in those kinds of categories as well, and perhaps even match known results. I'd love to hear from anyone who can say anything about this.

In any case, thank you for sharing those examples! Now that I have some idea of why you're interested in CLACs, perhaps you can say a bit more about what you do with them or point to a reference? Is about developing calculus or aspects of differential geometry synthetically using CLACs (with extra structure/properties)?

blackwell_act.pdf

JS PL (he/him) (Jul 30 2020 at 12:53):

Tobias Fritz said:

perhaps you can say a bit more about what you do with them or point to a reference?

Happy to!
CLACs are the base structure of Cartesian differential categories (http://www.tac.mta.ca/tac/volumes/22/23/22-23.pdf), which provide the categorical semantics of the directional derivative from multivariable calculus. The canonical example of a Cartesian differential category is $CartSp$. But there are lots of other examples, especially those which arise from differential linear logic.

Tobias Fritz said:

BTW is this what your skew enrichment is about?

Absolutely! Richard Garner and I talk about this in (https://arxiv.org/pdf/2002.02554.pdf) - and we give lots of examples of CLACs and CDCs.

Tobias Fritz (Jul 30 2020 at 13:00):

That's really interesting! I'll have to study the Cartesian differential categories paper a bit and will think about possible parallels to probability theory (modulo arrow reversal).

BTW I think you were also the one who had asked about the jet comonad, right? I had thought about that a bit more, and my tentative conclusion was that its co-Kleisli category, meaning the category of differential operators, is cartesian and therefore not interesting as a Markov category. But perhaps I should also have been thinking about its opposite, and using differential operators between vector spaces to get the left additive structure?

JS PL (he/him) (Jul 30 2020 at 13:00):

Tobias Fritz said:

As a Markov category, $C[Set^{op}]$ has so far mainly been useful as a source of counterexamples.

Good to know!

Tobias Fritz said:

In a dream world, these theorems will turn out to be interesting in those kinds of categories as well, and perhaps even match known results. I'd love to hear from anyone who can say anything about this.

It would be cool if some of these theorems have meaning or hold in reduced CLACs. Hopefully CLACs will be of interest to those working with Markov Categories!

JS PL (he/him) (Jul 30 2020 at 13:04):

Tobias Fritz said:

BTW I think you were also the one who had asked about the jet comonad, right? I had thought about that a bit more, and my tentative conclusion was that its co-Kleisli category, meaning the category of differential operators, is cartesian and therefore not interesting as a Markov category. But perhaps I should also have been thinking about its opposite, and using differential operators between vector spaces to get the left additive structure?

I wasn't the one who asked the question but I did give a reference.

Tobias Fritz said:

But perhaps I should also have been thinking about its opposite, and using differential operators between vector spaces to get the left additive structure?

Yes! The coKleisli category of the jet comonad in (https://arxiv.org/pdf/1811.06235.pdf) is a Cartesian differential category, and therefore a CLAC. So taking its subcategory of reduced maps and then taking the dual of that subcategory, gives a Markov category.

Valeria de Paiva (Jul 30 2020 at 14:44):

Tobias Fritz said:

[...]These conditions all together are nicely self-dual, and of course they hold if $\otimes$ is the biproduct. But do they imply that $\otimes$ is a byproduct?

If not, perhaps they could make for an interesting kind of category in their own right? Martti Karvonen has worked on characterizations of biproducts, so perhaps he will know.

I presume that you're asking this because it has the flavour of linear logic, right? So perhaps Valeria de Paiva can help out?

hi @Tobias -- I think the problem is that I spend all my effort trying to make sure that products and coproducts were not the same, as in logic this is a very bad state of affairs: conjunctions should not be the same as disjunctions.
but of course in Algebra this makes sense and perhaps in physics too-- I talked a little to Shahn Majid https://en.wikipedia.org/wiki/Shahn_Majid about objects like you describe with free monoidal and free comonoidal structures, interacting nicely, a long time ago, but never wrote anything about it.

Tobias Fritz (Jul 30 2020 at 14:46):

Oh, I see! That makes perfect sense, thanks :smile:

Martti Karvonen (Jul 30 2020 at 20:16):

Tobias Fritz said:

That's an oddly interesting question, JS Pacaud Lemay! I take it as asking whether the monoidal structure in a cocartesian monoidal Markov category is necessarily a biproduct. I don't know! But now I'm also quite curious about this, and perhaps someone else can resolve this based on the following. There's a lot of structure in the problem, so let me describe how far I've gotten.

For starters, the monoidal unit $I$ is terminal as part of the definition of Markov category, initial by assumption, and therefore a zero object. For every object $X$, we have the coproduct inclusions $i_\ell, i_r : X \to X \otimes X$, and we also have the comultiplication $i_\nabla : X \to X \otimes X$. In the other direction, we have the two projections $p_\ell, p_r$ and the codiagonal $p_\nabla : X \otimes X \to X$. So there are three canonical morphisms in either direction! These satisfy a bunch of equations, and in particular the following:

$p_\ell i_\nabla = p_r i_\nabla = 1_X$
$p_\nabla i_\ell = p_\nabla i_r = 1_X$
$p_\ell i_\ell = p_r i_r = 1_X$
$p_r i_\ell = p_\ell i_r = 0_X$

as well as the bialgebra law, which can be derived from the universal property of the coproduct. These conditions all together are nicely self-dual, and of course they hold if $\otimes$ is the biproduct. But do they imply that $\otimes$ is a biproduct? If not, perhaps they could make for an interesting kind of category in their own right? Martti Karvonen has worked on characterizations of biproducts, so perhaps he will know.

Unless I'm missing something (e.g. your assumptions aren't even enough to imply the existence of binary products/coproducts), I believe the answer is yes and you don't even need all of the assumptions: roughly, you need a monoidal category with monoidally natural projections, inclusions, diagonals and codiagonals satisfying some equations. The equations you need are exactly the triangle equations guaranteeing that the tensor product is an ambiadjoint (simultaneously a left and right adjoint) to the diagonal $C\to C\times C$ + the equations $p_\ell i_\ell = p_r i_r = 1_X$ . In particular, you can drop the equations concerning 0 (and you don't even need assume the existence of zero morphisms as it follows from naturality). This is follows from
Theorem 3.6. Alternatively, as long as $X\otimes Y$ is simultanously a product, coproduct and the equations above (now with 0 included, or with the idempotence formulation from my paper if you prefer) hold, you have finite biproducts. See also Theorem 5, which roughly says that any natural iso between coproducts and products implies having biproducts and Proposition 4.6 which roughly says that in the precence of an initial object and enrichment in commutative monoids, any coproduct is a biproduct.

Tobias Fritz (Jul 30 2020 at 20:28):

Martti, thanks for chiming in! Above, JS has already given a number of examples of such categories (called Cartesian left additive categories or CLACs) in which the relevant monoidal structure is actually not a biproduct!

To match this up with what you say, I guess the resolution is that your statements require the diagonals and codiagonals to be natural, right? (Your "monoidally natural" could mean either just multiplicative with respect to $\otimes$, or it could mean that plus natural. I think you mean the latter, yes?) Now in a CLAC, the diagonals are natural because the monoidal structure is cartesian, but the codiagonals are not (in the interesting cases). I think that the most basic example of such a structure is the category of commutative monoids with merely unital maps as morphisms, the cartesian monoidal structure, and using the monoid multplications to define the codiagonals.

Martti Karvonen (Jul 31 2020 at 02:20):

Yes, I'd want them to be natural + cooperate with $\otimes$. Similarly, for the results I mentioned in the presense of addition, one does need bilinear (commutative) addition, whereas in the cases discussed above one might have something more restricted.