relevant monad – Dan Marsden

Quotients of Commutative, Affine and Relevant Monads

We have seen that nice properties such as being commutative, affine, or relevant can be transferred to strong submonads. A natural question to ask is whether something similar applies to quotients? In fact, we can apply the tricks we’ve already seen to get straight to some answers.

Commutative Monads

As strong monad morphisms commute with double strengths, if

\varphi : (\mathbb{T}, \mathsf{st}) \Rightarrow (\mathbb{Q}, \mathsf{st})

is a strong monad morphism, and $\mathbb{T}$ is commutative, we can immediately show

\mathsf{dst}^{\mathbb{Q}} \cdot \varphi \otimes \varphi = \mathsf{dst}^{\mathbb{Q}’} \cdot \varphi \otimes \varphi

If $\varphi \otimes \varphi$ is component-wise epimorphic, then

\mathsf{dst}^{\mathbb{Q}} = \mathsf{dst}^{\mathbb{Q}’}

and $\mathbb{Q}$ is commutative. Even if we restrict attention to where the monoidal structure is products, this condition is not as straightforward as that for monomorphisms. Fortunately there are many special cases where $\varphi$ being a component-wise epimorphism implies $\varphi \times \varphi$ is. In particular, this works nicely for $\mathsf{Set}$ -monads. As all natural transformation are strong in that case, we have

Quotients of commutative monads are commutative.

Affine, Relevant and Cartesian Monads

\varphi : (\mathbb{T}, \mathsf{st}) \Rightarrow (\mathbb{Q}, \mathsf{st})

is a strong monad morphism, and $\mathbb{T}$ is affine, then using the same calculational properties as we did for submonads, but in reverse, we can conclude

\langle \mathbb{Q}\pi_1, \mathbb{Q}\pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{Q}} \cdot \varphi \times \varphi = \varphi \times \varphi

and so if $\varphi \times \varphi$ is component-wise epimorphic

\langle \mathbb{Q}\pi_1, \mathbb{Q}\pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{Q}} = \mathsf{id}

If we restrict attention to $\mathsf{Set}$ -monads, using the result of the previous section, we can conclude

Quotients of affine monads are affine.

A very similar argument allows us to conclude that for $\mathsf{Set}$ -monads

Quotients of relevant monads are relevant.

Combining both these observations gives

Quotients of Cartesian monads are Cartesian.

Algebraic Interpretation

As usual, it pays to see if we use algebraic intuition to justify our conclusions. If we consider $\mathsf{Set}$ -monads presented by operations and equations, being commutative, affine, relevant or Cartesian requires that certain equations between terms hold. We can think of quotient monads as imposing extra equations between terms, so it is unsurprising quotient monads continue to have these nice properties.

Summary

The conclusions above are less general than for submonads. This is because epimorphisms do not interact as nicely with products as monomorphisms do. In the case of $\mathsf{Set}$ -monads everything was about as well-behaved as we could possibly hope.

Distributive Laws and General Equations

We have seen we can distribute any monad $\mathbb{T}$ presented by linear equations over a commutative monad $\mathbb{S}$ . There is a balance between the assumptions on these two monads that yields a distributive law, but it is not the only choice. This time we look at strengthening our assumptions about the monad $\mathbb{S}$ so that we can weaken the restriction to presentations by linear equations on monad $\mathbb{T}$ and still have a distributive law.

The plan is quite simple. The previous results hinged on closure properties of multilinear extensions. Our approach is to consider classes of monads where we get stronger closure properties of multilinear extensions, so we continue to use uniqueness of multilinear extensions as our proof principle.

Special Classes of Monads

Throughout this post, $\mathbb{S}$ will denote a commutative monad on a category with finite products.

Recall that $\mathbb{S}$ is:

Affine if $\langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle \cdot \mathsf{dst} = \mathsf{id}_{\mathbb{S}(X) \times \mathbb{S}(Y)}$ .
Relevant if $\mathsf{dst} \cdot \langle \mathbb{S}\pi_1, \mathbb{S}\pi_2 \rangle = \mathsf{id}_{\mathbb{S}(X \times Y)}$
Cartesian if it is both affine and linear.

Frustratingly, there are several unrelated notions of Cartesian monad used in the literature, so some caution with this terminology is required.

Multilinear Extensions for Affine Monads

We begin by investigating a special case of when we can delete inputs and still get multilinear extensions.

Assume $\mathbb{S}$ is an affine monad, and

\hat{h} : \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

h : X \rightarrow X

then the composite

\hat{h} \cdot \pi_1 : \mathbb{S}(X) \times \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

h \cdot \pi_1 : X \times X \rightarrow X

Intuitively, we can drop the second input and still get a multilinear extension.

To confirm multilinearity,

\hat{h} \cdot \pi_1 \cdot \mu \times \mu = \hat{h} \cdot \mu \cdot \pi_1 = \mu \cdot \mathbb{S}(\hat{h}) \cdot \pi_1

= \mu \cdot \pi_1 \mathbb{S}(\hat{h}) \cdot \pi_1 \cdot \langle \mathbb{S}\pi_1, \mathbb{S}\pi_2 \rangle \cdot \mathsf{dst} = \mu \cdot \mathbb{S}(\hat{h}) \cdot \mathbb{S}\pi_1 \cdot \mathsf{dst}

where the second step uses the assumed multilinearity of $\hat{h}$ , and the third step uses the assumption $\mathbb{S}$ is affine.

Verifying the extension property is a routine application of naturality.

Generalising from this special case, multilinear extensions of affine monads are closed under deleting variables. Using the same argument as the previous post, affine monads preserve equations that delete but don’t duplicate variables. We will refer to such equations as strictly deleting, and use the term strictly deleting presentation in the obvious way.

Multilinear Extensions for Relevant Monads

We begin by looking at a special case of when we can duplicate inputs and still get a multilinear extension.

Assume $\mathbb{S}$ is a relevant monad, and

\hat{h} : \mathbb{S}(X) \times \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

h : X \times X \rightarrow X

then the composite

\hat{h} \cdot \Delta_{\mathbb{S}(X)} : \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

h \cdot \Delta_{X} : X \rightarrow X

(Here $\Delta$ is the usual diagonal or copying natural transformation.) Intuitively we can duplicate the input and still get a multilinear extension.

To confirm multilinearity,

\hat{h} \cdot \Delta \cdot \mu = \hat{h} \cdot \mu \times \mu \cdot \Delta = \mu \cdot \mathbb{S}(\hat{h}) \cdot \mathsf{dst} \cdot \Delta

= \mu \cdot \mathbb{S}(\hat{h}) \cdot \mathsf{dst} \cdot \langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle \cdot \mathbb{S}(\Delta) = \mu \cdot \mathbb{S}(\hat{h}) \cdot \mathbb{S}(\Delta)

where the second step uses the assumed multilinearity, and the final step uses relevance of $\mathbb{S}$ .

Again, verifying the extension property is straightforward.

Generalising from this special case, multilinear extensions of relevant monads are closed under duplicating variables. Again, using the same argument as the previous post, relevant monads preserve equations that duplicate but don’t delete variables. We will refer to such equations as strictly duplicating, and use the term strictly duplicating presentation in the obvious way.

Consequences

Combining the proof principle of uniqueness of multilinear extensions with the additional closure properties above, we get a range of results. For a commutative monad $\mathbb{T}$ there is a distributive law:

\mathbb{T} \circ \mathbb{S} \Rightarrow \mathbb{S} \circ \mathbb{T}

$\mathbb{T}$ has a linear presentation.
$\mathbb{S}$ is affine and $\mathbb{T}$ has a strictly deleting presentation.
$\mathbb{S}$ is relevant and $\mathbb{T}$ has a strictly duplicating presentation.
$\mathbb{S}$ is Cartesian and $\mathbb{T}$ is any finitary monad.

Summary

The preservation theorems involving affine, relevant and Cartesian monads appear in the PhD thesis of Louis Parlant, although the proof strategy was somewhat different. Continuing Manes emphasis on multilinear maps provides a uniform perspective on all the different results.

Monads with special presentations

Previously, we introduced strong monads, and their associated double strength maps. By considering how a monad interacts with the double strengths, other important classes of monads emerge.

Recall that for a strong monad $\mathbb{T}$ , their are two double strength morphisms:

$\mathsf{dst}, \mathsf{dst'} : \mathbb{T}(X) \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(X \otimes Y)$

which are natural in $X$ and $Y$ . By restricting attention to the case where the monoidal structure is given by categorical products, we then notice that by combining the double strength and product structure, we can form the following composites:

$\mathbb{T}(X) \times \mathbb{T}(Y) \xrightarrow{\mathsf{dst}} \mathbb{T}(X \times Y) \xrightarrow{\langle \mathbb{T}(\pi_1), \mathbb{T}(\pi_2) \rangle} \mathbb{T}(X) \times \mathbb{T}(Y)$ .
$\mathbb{T}(X \times Y) \xrightarrow{\langle \mathbb{T}(\pi_1), \mathbb{T}(\pi_2) \rangle} \mathbb{T}(X) \times \mathbb{T}(Y) \xrightarrow{\mathsf{dst}} \mathbb{T}(X \times Y)$ .

As these composites are both endomorphisms, it is natural to ask when they are equal to the identity morphism of the same type.

Remark: This is a recurring theme, which we have commented on before. When doing category theory, we are often in situations when certain morphisms are assumed to be part of the available structure. It is always worthwhile considering when composites of these morphisms of the same type are actually equal. For example, the axioms of a monoidal category ensure that all such diagrams commute (in a precise technical sense). On the other hand, for a strong monad, exploring when the two double strength maps coincide leads us to the notion of commutative monad.

A monad is said to be:

Affine if $\mathbb{T}(X) \times \mathbb{T}(Y) \xrightarrow{\mathsf{dst}} \mathbb{T}(X \times Y) \xrightarrow{\langle \mathbb{T}(\pi_1), \mathbb{T}(\pi_2) \rangle} \mathbb{T}(X) \times \mathbb{T}(Y) = \mathsf{id}$ .
Relevant if $\mathbb{T}(X \times Y) \xrightarrow{\langle \mathbb{T}(\pi_1), \mathbb{T}(\pi_2) \rangle} \mathbb{T}(X) \times \mathbb{T}(Y) \xrightarrow{\mathsf{dst}} \mathbb{T}(X \times Y) = \mathsf{id}$ .
Cartesian if it is both affine and relevant. That is, when it preserves binary products, up to isomorphism.

We should immediately be a bit suspicious of these definitions. Do we get different notions if we consider interaction with $\mathsf{dst}'$ rather than $\mathsf{dst}$ ? Fortunately, life is simple in this case, and the choice to use $\mathsf{dst}$ or $\mathsf{dst}'$ makes no difference, although it does take a little bit of work to establish this fact.

Affineness algebraically?

As usual, when we encounter new classes of monads, we shall examine them from the point of view of algebra.

A bit of calculation shows that being affine is equivalent to requiring the component of the monad at the terminal object is an isomorphism. Algebraically, $\mathbb{T}(\{ x \})$ consists of equivalence classes of terms:

$[x], [t(x, x)], [t(t'(x, x), x))], \ldots$

The set of these terms is isomorphic to the terminal object if and only if it has a single element. This can only be the case if all these equivalence classes are equal. This is the same as requiring that every term built from operation symbols and a single variable is equal to the variable itself. This will be the case if and only if every operation $o$ satisfies:

$o(x,\ldots,x) = x$

That is, all the operations are idempotent.

Example: The non-empty (finite) powerset monad is affine.

Example: If we consider consider any algebraic presentation such that we can derive $x = y$ , then everything can be proved equal to everything else. Such a presentation is said to be inconsistent. We consider the presented monad $\mathbb{T}$ . There are two cases:

The signature doesn’t contain a constant symbol. In this case $\mathbb{T}(\emptyset) = \emptyset$ , and for every other $X$ , $\mathbb{T}(X) \cong 1$ .
The signature contains a constant symbol. In this case, for all $X$ , $\mathbb{T}(X) \cong 1$ .

So the monads corresponding to inconsistent presentations are affine. These pathological monads, which we shall refer to as inconsistent monads, are a good source of counterexamples for naive conjectures about monads.

Counterexample: For an algebraic presentation $(\Sigma, E)$ which is not inconsistent, if $\Sigma$ contains a constant symbol, then the presented monad is not affine. For example, the ordinary finite powerset monad is not affine.

Relevance algebraically

Unfortunately, the condition for being relevant does have such a convenient simplification. In this case, to understand what is going on algebraically, we shall have to look the the original definition directly, using the algebraic description of $\mathsf{dst}$ discussed previously. For arbitrary element

$[t((x_1,y_1),\ldots,(x_n,y_n))] \in \mathbb{T}(X \times Y)$ ,

the relevance condition becomes:

$[t((x_1,y_1),\ldots,(x_n,y_n))] = [t(t((x_1,y_1),\ldots,(x_1,y_n)),\ldots, t((x_n,y_1),\ldots,(x_n,y_n)))]$

which can only be the case if the following equation is derivable for every term $t$ :

$t((x_1,y_1),\ldots,(x_n,y_n)) = t(t((x_1,y_1),\ldots,(x_1,y_n)),\ldots, t((x_n,y_1),\ldots,(x_n,y_n)))$

Using pairs everywhere is getting hard to read. The previous equation is equivalent to:

$t(x_1,\ldots,x_n) = t(t(x_1,y_{1,2}, \ldots, y_{1,n}),\ldots, t(y_{n,1},\ldots, y_{n,n-1}, x_n))$

Example: If we only have constant elements in our presentation, then the equation above holds trivially. Therefore for any set $E$ , the exception monad $(-) + E$ is relevant.

As the relevance condition is still rather hard to read, we specialise it to a single binary operation $\times$ :

$x_1 \times x_2 = (x_1 \times y_1) \times (y_2 \times x_2)$

The equation should be familiar from our discussion of the reader monad for a binary bit.

Example: The equation above is exactly the condition satisfied by the lookup operation for the binary bit reader monad, and inductively by all terms. The binary bit reader monad is relevant. In fact, any instance of the reader monad is relevant, as can be verified by direct calculation.

Counterexample: To confirm a monad is relevant, it is not sufficient to establish the condition for operation symbols only. For example, if we have two binary operations $s,t$ satisfying the relevance condition above, it is not necessarily the case that the composite $t(s(w,x),s(y,z))$ will.

Example: Unsurprisingly, the inconsistent monads introduced above are also relevant. This is trivially true, as they satisfy every possible equational condition.

Summing Up

By considering the interaction between a strong monad and its double strength maps, we were lead to new classes of monads. In algebraic examples, these conditions have natural interpretations.

We should ask ourselves, are these monads useful for anything? Gladly, the answer is yes. We briefly sketch a couple of examples:

For a commutative monad on a symmetric monoidal category, under tame conditions, the symmetric monoidal structure lifts to the Eilenberg-Moore category. If the monad is affine or relevant, further structure such as projection and diagonal maps also lift to the Eilenberg-Moore category.
Beck’s distributive laws are a vital tool for composing monads. If a monad is commutative monad, there are useful positive results about the existence of distributive laws for combining it with other monads. Recent work has shown that affine and relevant monads imply distributive laws in more general situations.

To discuss either of these topics properly requires more background than we have currently introduced. We may return to them in later posts.

For further background on affine and relevant monads, Jacobs “Semantics of Weakening and Contraction” is an excellent place to start reading (as it is for many other topics in monad theory!). The importance of affine and relevant monads for positive results about distributive laws can be found in the PhD thesis of Louis Parlant.