10
$\begingroup$

Introduction

I'll describe a way of taking a monad on a category $\mathcal{E}$ with pullbacks, and obtaining a monad on each slice category. I'll show that this construction is always lax-natural in $\mathcal{E}$. However, for many monads on $\mathbf{Set}$ this construction is actually strongly natural, most interestingly in the case of the powerset monad and the probability distributions monad. For others, it's not natural, e.g. for the free abelian group monad $\mathbb{Z}[-]$. The condition seems to characterize monads with a certain sort of ``zerosumfreeness'' condition, e.g. $\mathbb{Z}[-]$ fails because zero can arise as the result of non-trivial linear combinations.

The zerosumfree monads $M$ admit a certain strengthening of the usual notion of ``lax monoidality'' for the cartesian product monoidal structure: the products in the usual coherence maps $M(X_1)\times M(X_2)\to M(X_1\times X_2)$ can be replaced by fiber products $$M(X_1)\times_{M(X)}\; M(X_2)\to M(X_1\times_X X_2).$$

For example, for any functions $X_1\xrightarrow{f_1} X\xleftarrow{f_2} X_2$ in $\mathbf{Set}$, there is a natural map \begin{align*} \mathsf{Dist}(X_1)\times_{\mathsf{Dist}(X)}\;\mathsf{Dist}(X_2)&\to \mathsf{Dist}(X_1\times_X X_2)\\ (p_1,_pp_2)&\mapsto (x_1,_x x_2)\mapsto \frac{p_1(x_1)\cdot p_2(x_2)}{p(x)} \end{align*} where $\mathsf{Dist}(f_1)(p_1)=p=\mathsf{Dist}(f_2)(p_2)$ is the distribution on $X$ induced by $p_1$ and $p_2$, and $f_1(x_1)=x=f_2(x_2)$.

Questions: Where else do these "zerosumfree" monads arise and have they been studied? Have these ``stronger lax monoidal conditions" for categories with pullbacks been studied?

(Edit: what I'm now calling "zerosumfree" was called "non-cancellative" in my original post; I'm now following the naming suggested by Tobias Fritz in his answer below.)

Slicing a monad in a category with pullbacks

Suppose $\mathcal{E}$ is a category with pullbacks and we're given an adjunction $L:\mathcal{E}\rightleftarrows\mathcal{E}':R$. Then for any object $e\in\mathcal{E}$, there is an induced adjunction between slice categories $$L_e:\mathcal{E}/e\rightleftarrows\mathcal{E}'/L(e):R_e$$ Indeed the left adjoint sends $x\to e$ to $Lx\to Le$, and the right adjoint sends $y\to L(e)$ to the pullback $$ \begin{array}{ccc} R_e(y) & \to & Ry\\ \downarrow & & \downarrow\\ e & \underset{\eta_e}{\to}& RLe \end{array} $$

In particular, if $(M,\eta,\mu)$ is a monad on $\mathcal{E}$, we can consider the canonical adjunction with the Eilenberg-Moore category $\mathcal{E}^M$ of $M$-algebras: $$ \hat{M}\colon\mathcal{E}\rightleftarrows\mathcal{E}^M:U $$ Here $\hat{M}(e)$ is the free algebra on $e$, and $U$ is the forgetful functor. Then for every object $e\in\mathcal{E}$ the above construction gives us an adjunction $(\hat{M}_e\vdash U_e)$, and hence a monad on the slice $\mathcal{E}/e$. We denote the underlying functor of this sliced monad by $$ M_e\colon\mathcal{E}/e\to\mathcal{E}/e $$

Example: Take $\mathcal{E}:=\mathbf{Set}$ and $M:=\mathsf{Dist}$ the finite probability distributions monad. Then for any function $g\colon x\to e$, the map $\mathsf{Dist}_e(g):\mathsf{Dist}_e(x)\to e$ is given by the pullback $$ \begin{array}{ccc} \mathsf{Dist}_e(x) & \to & \mathsf{Dist}(x)\\ \downarrow & & \downarrow\\ e & \underset{\eta_e}{\to} & \mathsf{Dist}(e) \end{array} $$ In other words, the sliced monad $\mathsf{Dist}_e(x)$ is the set of fiberwise distributions on $x$: an element consists of an element of $e$ and a distribution on the fiber of $x$ over it.

Naturality

All of the above is natural in $e\in\mathcal{E}$. Indeed, for any morphism $f\colon d\to e$ there is an adjunction between slice categories: $$f_!\colon\mathcal{E}/d\rightleftarrows\mathcal{E}/e:f^*$$ and it is easy to check that the both the following diagram of left adjoints (shown) and that of right adjoints commutes: $$ \begin{array}{ccc} \mathcal{E}/d & \overset{L_d}{\rightleftarrows} & \mathcal{E}'/Ld\\ \scriptsize f_!\normalsize \downarrow\uparrow~~~ & & \scriptsize (Lf)_!\normalsize\downarrow \uparrow~~~~\\ \mathcal{E}/e & \overset{L_e}{\rightleftarrows} & \mathcal{E}'/Le \end{array} $$ Thus there is an induced "mate" natural transformation $L_d\circ f^*\Rightarrow (Lf)^*\circ L_e$. In the case of monads, where $L$ is the free monad functor to the Eilenberg-Moore category, the Beck-Chevalley condition seems to rarely hold. However, something interesting happens when we compose with the right adjoints $R_d$ and $R_e$.

"Zerosumfree monads"?

Composing the above mate natural transformation with $R_d$ and using the commutativity of the right adjoint square above, we obtain: $$ R_d\circ L_d\circ f^*\Rightarrow R_d\circ (Lf)^*\circ L_e\cong f^*\circ R_e\circ L_e $$ Returning to the monad case, we take $L_d:=U_d$ and $R_d:=\hat{M}_d$ to be the adjoint functors $\mathcal{E}/d\leftrightarrows\mathcal{E}^M/Md$ to which $M_d=R_d\circ L_d$ is the associated monad, and we obtain a natural transformation $$f^M\colon M_d\circ f^*\Rightarrow f^*\circ M_e.$$ This is a kind of lax naturality condition for the sliced monads.

Claim: Let $\mathcal{E}=\mathbf{Set}$ and $f\colon d\to e$ any function. For the following examples of monads, the lax naturality map $f^M$ is—or is not—an isomorphism as indicated $$ \begin{array}{l | l} \text{Monad } M&f^M\text{ is always iso?}\\\hline \text{identity}&\text{Yes}\\ \mathsf{Dist}&\text{Yes}\\ \mathsf{P},\text{ powerset}&\text{Yes}\\ \mathsf{P}^{\mathsf{fin}},\text{ finite powerset}&\text{Yes}\\ \mathsf{P}_+,\text{ nonempty powerset}&\text{Yes}\\ \mathsf{P}_+^{\mathsf{fin}}&\text{Yes}\\ -^S,\text{any set $S$}&\text{Yes}\\ (-\times S)^S,\text{any set $S$}&\text{Yes, but reduces to $-^S$}\\ \mathsf{List},\text{free monoid}&\text{Yes, but reduces to identity}\\ -\times G,\text{ $G$ a monoid}&\text{Yes, but reduces to identity}\\ \mathbb{N}[-],\text{free comm. monoid}&\text{Yes, but reduces to identity}\\ \mathbb{R}_+[-],\text{free semi-module over nonneg. reals}&\text{Yes, but reduces to identity}\\ \mathbb{Z}[-],\text{free abelian group}&\text{No!}\\ k[-],\text{free vector space}&\text{No!} \end{array} $$ The reason that $\mathbb{Z}[-]$ and $k[-]$ fail is roughly that there are expressions in the free algebra that "sum to zero" and are thus "locally indetectable".

Question: Has this phenomenon been studied before?

Strengthening lax monoidality of monad

In the case that the above-mentioned maps $f^M$ are invertible, we have natural transformations $$ (f^M)^{-1}\colon f^*\circ M_e\Rightarrow M_d\circ f^* $$ But stepping back a bit, these maps actually arise by composing other natural transformations with $U_d$ and $U_e$ as above. That is, there is a natural transformation as shown: $$ \begin{array}{ccccc} \mathcal{E}/d && \overset{\hat{M}_d}{\rightarrow} && \mathcal{E}^M/Md\\\\ f^*\uparrow & &\Uparrow & & \uparrow\scriptsize (Mf)^*\\\\ \mathcal{E}/e && \overset{\hat{M}_e}{\rightarrow} && \mathcal{E}^M/Me \end{array} $$ The above maps $(f^M)^{-1}$ arise—though not a priori as inverses to $f^M$—by composing the map $(Mf)^*\circ\hat{M}_e\Rightarrow \hat{M}_d\circ f^*$ with the functor $U_d\colon\mathcal{E}^M/Md\to\mathcal{E}/d$ adjoint to $\hat{M}_d$.

Anyway, what this says is that for any maps $d\to e\leftarrow y$, there is a natural map $$\varphi_{d,_ey}: M(d)\times_{M(e)}M(y)\to M(d\times_ey).$$ (This will automatically be a section of the universal map going the other way.) I have not checked that these maps satisfy the axioms for being lax monoidal coherence maps in the case that $e=1$ is a terminal object, but it seems likely.

Question: Has this phenomenon been studied before? Are there any cases you know of where the maps $\varphi_{d,_ey}\;$ exist but do not lead to $f^M$ being an isomorphism?

$\endgroup$
  • $\begingroup$ For the state monad in your table, what precisely do you mean by "it reduces to ${-}^S$? $\endgroup$ – Andrej Bauer Aug 25 at 21:24
  • 2
    $\begingroup$ I'll have to think harder before I feel confident giving an answer, but I suspect many examples are given by weakly cartesian monads, for example analytic monads coming from operads, and the ultrafilter monad. $\endgroup$ – Todd Trimble Aug 26 at 0:22
  • 1
    $\begingroup$ @AndrejBauer, suppose S is a set, M denotes the S-state monad, and N represents the monad -^S on Set. I'm saying that for any set e, the monads M_e and N_e on the slice Set/e are identical. To see this, consider the example above, but in the case of the state monad: take a set x, a function g: x-->e, and consider the pullback of Mg along the unit eta_e: e-->Me. $\endgroup$ – David Spivak Aug 26 at 12:39
  • $\begingroup$ Your notion of noncancellative monad might be related to a question I asked on MSE regarding dimension of free $T$-algebras : a "solution" to your question could be a solution to mine $\endgroup$ – Max Aug 27 at 16:47
4
$\begingroup$

Here are some remarks and pointers to the literature which are too long for a comment.

The map $$ \mathsf{Dist}(X_1) \times_{\mathsf{Dist}(X)} \mathsf{Dist}(X_2) \longrightarrow \mathsf{Dist}(X_1 \times_X X_2) $$ is a well-known construction called conditional product. While this has been rediscovered many times over, the first axiomatics that I am aware of were proposed in a paper by Dawid and Studený. More recently, one categorical axiomatization based on the resemblance with sheaf-theoretic gluing was given in this paper. Another categorical axiomatization has been given by Simpson in this paper, where conditional products are called local independent products. Note that the first two references only consider conditional products of the special type $\eqref{laxproduct_special}$ below, but I believe this to be only a minor restriction.

An important caveat is that although the conditional product is natural in the left and right arguments, it is not natural in the middle one. This plays a prominent role in such categorical axiomatizations.

A general construction of conditional products for suitable monads can be extracted from my latest paper. As described in Section 3, the Kleisli category of any symmetric monoidal affine monad $M$ on a category with finite products is a Markov category. If this Markov category has conditionals in the sense of Definition 11.1, then Definition 12.8 shows that one can form conditional products in the special form $$\tag{1}\label{laxproduct_special} M(A \times B) \times_{M(B)} M(B \times C) \longrightarrow M(A \times B \times C), $$ and I suspect that one can arrive at the general form as in the OP with a bit more fiddling. However, I do not know how to translate the assumption for the Kleisli category to have conditionals into an assumption on the monad, and this may end up being related to your $f^M$. I also do not know whether the existence of conditionals is related to any sort of "noncancellativity"; I have investigated one such condition in Definition 11.19 and after, but it does not seem to play any role in the context of conditional products. (By the way, what is called "noncancellativity" in the OP should arguably be called positivity or zerosumfreeness, since cancellativity usually means more something like $a + c = b + c \: \Rightarrow \: a = b$.)

Finally, I agree with Todd Trimble that the question also triggers strong associations with weakly cartesian monads. Replacing the title of the second column by "has weakly cartesian underlying functor and weakly cartesian multiplication" indeed gives the exact same yes/no answers. This can be seen by applying the results of this paper by Clementino, Hofmann and Janelidze, where this property is called condition (BC). Properties like zerosumfreeness—i.e. what the OP calls "noncancellativity"—indeed play a major role in characterizing monads on $\mathsf{Set}$ which satisfy condition (BC).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.