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: learning: questions

Topic: sum, zero, copy, discard

Paolo Perrone (Nov 27 2021 at 10:45):

Hi all. I've come across the following phenomenon, which looks like a sort of duality. Can someone tell me if it is an instance of something known?

Let $X=\{x,y,z\}$ and $A=\{a,b,c\}$ be sets. Consider the function $f:X\to A$ given by $f(x)=a$ and $f(y)=f(z)=b$.
Consider now a (discrete) distribution $p$ on $X$, with values $p(x),p(y),p(z)$. The push-forward distribution $f_*p$ on $A$ is as follows: $f_*p(a)=p(x)$, $f_*p(b)=p(y)+p(z)$, $f_*p(c)=0$. In other words, the pushforward distribution $f_*p$ looks at what happens in the $f$-preimage of a given point of $A$, it sums whatever is in there in case the preimage is not a single point, and it gives zero if the preimage is empty. So the commutative monoid structure of $R$ (where distributions take values) is showing up.

Now consider a function $g:A\to R$, with values $g(a), g(b), g(c)$. We can pull back the function to $X$ by precomposition, that is, forming $f^*g=g\circ f:X\to R$. In this case we have that $f^*g(x)=g(a)$ and $f^*g(y)=f^*g(z)=g(b)$. In other words, the pullback function $f^*g$ looks at what happens in the $f$-image of a given point of $X$, it copies the value to all the elements of the preimage in case there is not a single point, and it discards that value (for example, $g(c)$) in case the preimage is empty. So the commutative comonoid structure of $R$ is showing up.

What kind of duality is this?

Morgan Rogers (he/him) (Nov 27 2021 at 12:05):

If $R$ has both structures and they're compatible (something Hopf algebra-ish, say), you might hope that these operations are adjoint to one another somehow. This construction only really works as stated for functions between finite sets and quite special $R$; both parts can be adapted to infinite situations but the operations become a lot more subtle!

Robin Piedeleu (Nov 29 2021 at 10:45):

I can think of a category in which there is a known duality between the monoid and comonoid structures you point out: if $R$ is a field, swapping addition/zero with copy/discard gives a duality on $R$-linear relations, i.e., those relations $R^n\rightarrow R^m$ that are linear subspaces of $R^{n+m}$. The duality becomes obvious when working with a presentation of this (symmetric monoidal) category, such as the one in this paper, where addition/zero are the white nodes and copy/discard are the black nodes. Then, swapping the two colours defines a (self-)duality! One explanation for why this works is that all the equations involving these two structures are completely symmetric, a somewhat mysterious fact already pointed out by @Pawel Sobocinski in this blog post for example.

Robin Piedeleu (Nov 29 2021 at 10:46):

Now I'm not sure precisely how it is related to what you've pointed out, but there must be a similar underlying explanation hiding somewhere.

Robin Piedeleu (Nov 29 2021 at 10:49):

In fact, all the objects you're working with live in this category - the distributions are just vectors and the set maps are maps between the canonical bases, which are all certainly $R$-linear relations - so it might not be so hard to make sense of what you've noticed in those terms

Robin Piedeleu (Nov 29 2021 at 10:52):

Oh, and isn't the pullback given by the transpose of the relevant map, seen as a matrix? In the associated graphical language, the transpose is realised by colour-swap (followed by taking the converse relation) so that would explain it

Andrea Gentili (Nov 29 2021 at 14:45):

Not quite what you're after in terms of algebraic structures, but if you categorify (in the sense that you see $A$ and $X$ as discrete categories and substitute the monoid $R$ with a category with objects the elements of $R$ and such that the coproduct corresponds to the sum in $R$ and the initial object to 0), then your map $f_\ast p$ is the left Kan extension of $p$ with respect to $f$, so that your two constructions amount to the usual direct and inverse image of presheaves, and the duality is indeed given by an adjunction.

(I'm not sure at all that any monoid can be categorified in this sense, but one can always work with the monoid freely generated by the elements of $R$, through which any $p$ naturally factorizes)