# Monotone weak distributive laws over the lifted powerset monad in categories of algebras

Quentin Aristote

► To cite this version:

Quentin Aristote. Monotone weak distributive laws over the lifted powerset monad in categories of algebras. 2024. hal-04712728v5

HAL Id: hal-04712728

https://hal.science/hal-04712728v5

Preprint submitted on 11 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
MONOTONE WEAK DISTRIBUTIVE LAWS OVER THE LIFTED POWERSET MONAD IN CATEGORIES OF ALGEBRAS

QUENTIN ARISTOTE •

Université Paris Cité, CNRS, Inria, IRIF, F-75013, Paris, France
e-mail address: quentin.aristote@irif.fr

**ABSTRACT.** In both the category of sets and the category of compact Hausdorff spaces, there is a monotone weak distributive law that combines two layers of non-determinism. Noticing the similarity between these two laws, we study whether the latter can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras. We then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, on the one hand exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases.

# 1. INTRODUCTION

In the study of the semantics of programming languages, and since the seminal work of Moggi [Mog89], effectful computations are usually modeled with monads: an effectful function of type $X \toLY$ is interpreted as a function of type $X \to TY$, where the monadic structure on $T$ allows for having identities and compositions of such effectful functions. When considering several effects at the same time, a natural question arises: given monads corresponding to two effects, is it possible to construct a monad that corresponds to the combination of these two effects? In particular, combining probabilities and non-determinism has been a very popular subject of study in the topological and (dually) domain-theoretic settings: see for instance the introduction of [KP17] for an extensive bibliography on the topic.

The most straightforward way to combine two monads $S$ and $T$ would be to compose their underlying functors, but unfortunately in general the resulting endofunctor $ST$ may not carry the structure of a monad. For this to hold, a sufficient condition is the existence of a *distributive law* of $T$ over $S$, i.e. a natural transformation $TS \Rightarrow ST$ satisfying four axioms involving the units and multiplications of the two monads [Bec69]. Such a distributive

*Key words and phrases:* Weak distributive law, weak extension, weak lifting, iterated distributive law, Yang-Baxter equation, powerset monad, Vietoris monad, Radon monad, Eilenberg-Moore category, regular category, relational extension.

For sometimes small but always fruitful discussions on topics related to this work, the author thanks Gabriella Böhm, Victor Iwaniack, Jean Goubault-Larrecq, Alexandre Goy, Daniela Petrişan and Sam van Gool.
law makes ST into a monad, and its data is equivalent to the data of a *lifting* of S to the Eilenberg-Moore category **EM**(T) of T-algebras or to the data of an *extension* of T to the Kleisli category **KI**(S) of free S-algebras.

Unfortunately, distributive laws turn out to be not so common: proving that some specific pairs of monads do not admit any distributive law between them has been the focus of several works [KS18, VW06, DN18], culminating in [ZM19] where general techniques for proving the absence of distributive laws between monads on **Set**, so-called “no-go theorems”, are exhibited. Among the culprits are the powerset monad **P** and the probability distributions monad **D**: there is no distributive law **PP** ⇒ **PP** nor **DP** ⇒ **PD**.

A next step in combining monads is thus to weaken the requirements asked for by distributive laws. In [Böh10] a 2-categorical theory of such weakened distributive laws, where the axioms relating to the units of the monads are relaxed, is developed. This theory encompasses two orthogonal kinds of weakened laws, both called weak distributive laws: those of [Str09], extensively studied in [BLS11, BLS12, Böh12], and those more recently put light on in [Gar19] and given further instances of in [GP20, GPA21, BS22]. This work focuses on the latter kind of laws: in the following a *weak distributive law* of T over S will thus be a natural transformation of type TS ⇒ ST (again), where only three of the four axioms of distributive laws are required. Such a weak distributive law need not make ST into a monad, but does so of a retract of it when the category is well-behaved. Weak laws TS ⇒ ST are equivalent to *weak extensions* of T to **KI**(S) – extensions of the semi-monad underlying T, i.e. of its endofunctor and multiplication but not of its unit – or, when the category is well-behaved, *weak liftings* of S to **EM**(T) – liftings of S up to a retraction.

Weak extensions are a precious tool for building weak distributive laws, because *monotone extensions* to **Rel** – the category of sets and relations, which also happens to be the category of free algebras of the powerset monad **P** on **Set** – admit a nice characterization: this makes it possible to find weak distributive laws without having to guess their formulæ anymore, and the monotonicity of the extension is a strong indicator that the resulting law will be semantically interesting. In the context of weak distributive laws, this strategy was first used by Garner [Gar19], who exhibited a law **PP** ⇒ **PP**, but also a law $\beta P \Rightarrow P\beta$, combining the ultrafilter monad $\beta$ and the powerset monad, and whose corresponding weak lifting turned out to be the Vietoris monad **V** of closed subsets on the category **KHaus** of compact Hausdorff spaces (the algebras of $\beta$ [Man69]). The same strategy was then used for instance in [GP20], where a law **DP** ⇒ **PD**, combining probabilities and non-determinisim, is described.

In fact, most non-trivial weak distributive laws in the literature (so-called *trivial* ones are described in [Goy21, §2.2]) are laws of type **TP** ⇒ **PT** built using this strategy. A weak distributive law **VV** ⇒ **VV**, combining two layers of non-determinism in **KHaus**, was similarly built by constructing a monotone weak extension [GPA21]; this law's formula is in particular very close to that of the law **PP** ⇒ **PP** in **Set**. Non-determinism can also be combined with probabilities in **KHaus** and other continuous settings: weak distributive laws for this purpose are constructed by hand in a very recent pre-print [Gou24].

The goal of the present work is to take over the program of finding non-**Set**-based weak distributive laws: we focus here on categories of algebras, which fit in the general framework for monotone weak laws presented in [GPA21]. In particular, we notice in Lemma 3.1 that the law **VV** ⇒ **VV** is not only very similar to the law **PP** ⇒ **PP**, but is also actually some sort of weak lifting of it. We thus study whether there is a general framework for not only weakly lifting monads (as weak distributive laws do), but also weakly lifting weak
distributive laws themselves: this framework should yield or simplify the construction of the law $VV \Rightarrow VV$, and hopefully generalize it to other categories of algebras, in particular $EM(P)$ and $EM(D)$ which have weakly lifted powerset monads thanks to the laws $PP \Rightarrow PP$ and $DP \Rightarrow PD$.

This question is largely related to the problem of composing weak distributive laws, which was investigated in [Goy23] from the point of view of the Yang-Baxter equations – the usual tool for composing and lifting plain distributive laws [Che11]. We end up getting a general “no-go theorem” for monotone weak laws over weakly lifted powerset monads: in that sense this work is also close in spirit to [ZM19], where general no-go theorems for (strict) distributive laws are given. While not restricted to monotone distributive laws, these theorems are unlikely to generalize to our setting because they are based on the correspondence between monads and algebraic theories, which is mostly restricted to **Set** and does not have any obvious generalization to semi-monads – to which weak distributive laws are deeply related.

This article is organized as follows. In Section 2, we recall definitions and notations for and give examples of monads and weak distributive laws, and also recall the framework of [GPA21] for monotone weak distributive laws in regular categories. This culminates in Lemma 3.1, where we notice that the law $VV \Rightarrow VV$ is some sort of weak lifting of the law $PP \Rightarrow PP$. The next sections focus on lifting weak distributive laws: in Section 3 we study the approach of the Yang-Baxter equation, showing it indeed allows for weakly lifting weak laws but does not apply to the examples we consider; while in Sections 4 and 5 we focus on the monotonicity of the laws: in Section 4 we characterize the Kleisli category of weakly lifted powerset monads as subcategories of relations, and in Section 5 we then deduce a simple characterization for the existence of monotone weak laws in categories of algebras and apply it to several examples. We conclude in Section 6.

Our main contributions are the following:

* we show that, while the law $VV \Rightarrow VV$ is a kind of weak lifting of the law $PP \Rightarrow PP$ (Lemma 3.7), this lifting does not come from a Yang-Baxter equation (Corollary 3.5), the usual approach to lifting laws: it is an instance of a general no-go theorem for Yang-Baxter equations involving the law $PP \Rightarrow PP$ (Proposition 3.4);

* we characterize the Kleisli category of the weak lifting $\bar{S}$ of a monad $S$ to the algebras of a monad $T$ as the category of $T$-algebras and $KI(S)$-morphisms between them (Proposition 4.2);

* we give a characterization of the Kleisli categories of weakly lifted powerset monads as subcategories of relations (Theorem 4.8), in which a certain class of *decomposable morphisms* play a central role: it follows that the corresponding categories of algebras have *decomposable subobject classifiers* (Proposition 4.12), and that monads must preserve these decomposable morphisms to have monotone weak distributive laws over weakly lifted powerset monads – this is in fact a sufficient condition for monads that are themselves weak liftings (Corollary 5.2);

* concrete instances of this last result are then easily derived: we recover independently the law combining probabilities and non-determinism in compact Hausdorff spaces and recently exhibited in [Gou24] (Theorem 5.4), but we observe otherwise that monotone weak distributive laws over weakly lifted powerset monads in categories of algebras seem very rare (Table 1).

The present article is an extended version of an article presented at STACS 2025 [Ari25], in which the discussion in Section 4.2 and the proofs were not included.
## 2. PRELIMINARIES

In this section we first recall the theory of weak distributive laws from [Gar19] and the tools that come along, especially the ones developed in [GPA21]. The reader is assumed to be familiar with the basics of category theory, an introduction to which appearing for instance in [Bor94a].

### 2.1. Monads and (Weak) Distributive Laws.

**Definition 2.1 (monad).** A monad on a category $\mathcal{C}$ is the data $(\mathcal{T}, \eta^\mathcal{T}, \mu^\mathcal{T})$, often abbreviated $\mathcal{T}$, of an endofunctor $\mathcal{T}: \mathcal{C} \to \mathcal{C}$ and natural transformations $\eta^\mathcal{T}: \mathbf{Id} \Rightarrow \mathcal{T}$ and $\mu^\mathcal{T}: \mathbf{TT} \Rightarrow \mathcal{T}$ satisfying the axioms $\mu^\mathcal{T} \circ \mathcal{T}\eta^\mathcal{T} = \mathbf{id} = \mu^\mathcal{T} \circ \eta^\mathcal{T}\mathcal{T}$ and $\mu^\mathcal{T} \circ \mathcal{T}\mu^\mathcal{T} = \mu^\mathcal{T} \circ \mu^\mathcal{T}\mathcal{T}$.

**Example 2.2 (monads).** In this work we will be particularly concerned with the following monads on **Set**. Thereafter $X$ and $Y$ are sets, $x$ is an element of $X$ and $f: X \to Y$ is a function.

**The powerset monad P:** $PX = \{\text{subsets of } X\};$ for $e \subseteq X$, $(Pf)(e) = f[e] = \{f(x') | x' \in e\};$ $\eta_X^P(x) = \{x\}$; for $E \subseteq PX$, $\mu_X^P(E) = \bigcup E$.

**The probability distributions monad D:** $DX$ is the set of finitely-supported probability distributions on $X$, i.e. functions $\varphi: X \to [0, 1]$ such that $\varphi^{-1}(0, 1]$ is finite and $\sum_{x \in X} \varphi(x) = 1$; $Df$ is the pushforward along $f$ given by $(Df)(\varphi)(y) = \sum_{x \in f^{-1}(y)} \varphi(x)$ for $\varphi \in DX$ and $y \in Y$; $\eta_X^D(x)$ is the Dirac $\delta_x$ for $x \in X$, i.e. the probability distribution such that $\delta_x(x) = 1$; and $\mu^D$ computes the mean of a distribution of distributions, so that for $\Phi \in DDX$, $\mu^D(\Phi)(x) = \sum_{\varphi \in DX} \Phi(\varphi) \cdot \varphi(x)$.

**The ultrafilter monad $\beta$:** $\beta X$ is the set of maximal filters on $X$, where filters are sets $E \in PPX$ that are non-empty, up-closed (for inclusion), stable under finite intersections and that do not contain the empty set; for an ultrafilter $E \in \beta X$, $(\beta f)(E) = \{e' \supseteq f[e] \mid e \in E\}$; $\eta_X^\beta(x)$ is the principal filter $\{e \in PX \mid x \in e\}$; and, for $\mathfrak{E} \in \beta\beta X$, $\mu_X^\beta(\mathfrak{E}) = \bigcup \{\mathfrak{e} \mid \mathfrak{e} \in \mathfrak{E}\}$.

We will also be concerned with a topological analogue of the powerset monad, defined on the category **KHaus** of compact Hausdorff spaces and continuous functions. Thereafter $X$ and $Y$ are compact Hausdorff spaces, $x$ is an element of $X$, and $f: X \to Y$ is a continuous function.

**The Vietoris monad V:** $ VX$ is the space of closed subsets of $X$ equipped with the topology for which a subbase is given by the sets $\square u = \{c \in VX \mid c \subseteq u\}$ and $\diamond u = \{c \in VX \mid c \cap u \neq \emptyset\}$, where $u$ ranges among all open sets of $X$; $(Vf)(c) = f[c] = \{f(x) \mid x \in c\}$ for $c \in VX$; $\eta_X^V(x) = \{x\}$; and $\mu_X^V(C) = \bigcup C$ for $C \in VVX$.

We also write $\mathbf{P}_*$ and $\mathbf{V}_*$ for the non-empty powerset and Vietoris monads, respectively obtained by removing the empty set from each $\mathbf{P}X$ and $\mathbf{V}X$.

Weak distributive laws are a certain type of natural transformations involving monads.

**Definition 2.3 ((weak) distributive law [Gar19, Definition 9]).** A monad $\mathcal{T}$ *weakly distributes* over a monad $\mathcal{S}$ when there is a *weak distributive law of $\mathcal{T}$ over $\mathcal{S}$*, i.e. a natural transformation $\rho: \mathcal{TS} \Rightarrow \mathcal{ST}$ such that the Diagrams $(\eta^+)$, $(\mu^-)$ and $(\mu^+)$ below commute. A (*strict*) distributive law is a weak distributive law that moreover has the diagram $(\eta^-)$ below
commute.

<figure><img src="image_2.png" /></figure>

If $\rho: TS \Rightarrow ST$ is a distributive law, $ST$, $\eta^{ST} = \eta^S\eta^T$ and $\mu^{ST} = \mu^S\mu^T \circ S\rho T$ form a monad [Bec69]. If it is only a weak distributive law this is not the case anymore: $\mu^{ST} \circ \eta^{ST}ST$ need not be an identity, and can only be proven to be idempotent (its composite with itself is itself). But suppose now it is a split idempotent, i.e. that there is a functor $S \bullet T$ and natural transformations $p: ST \Rightarrow S \bullet T$ and $i: S \bullet T \Rightarrow ST$ such that $p \circ i = \text{id}$ and $i \circ p = \mu^{ST} \circ \eta^{ST}ST$. Then $S \bullet T$ can be made into a monad [Gar19] with unit $\eta^{S \bullet T} = p \circ \eta^S\eta^T$ and multiplication $\mu^{S \bullet T} = p \circ \mu^S\mu^T \circ S\rho T \circ ii$: the monad $S \bullet T$ is called the weak composite of S and T.

**Example 2.4** (weak distributive laws). In this work we will be particularly concerned with the following weak distributive laws:

• in **Set**, the weak distributive law $\lambda^{P/P}: PP \Rightarrow PP$ given by Equation (2.1) below has for weak composite the monad $\mathbf{P} \bullet \mathbf{P}$ of sets of subsets closed under non-empty unions [Gar19];

• in **KHaus**, there is a weak distributive law $\lambda^{V/V}: VV \Rightarrow VV$ given by Equation (2.2) below [GPA21];

• in **Set**, the weak distributive law $\lambda^{D/P}: DP \Rightarrow PD$ given by Equation (2.3) below has for weak composite the monad $\mathbf{P} \bullet \mathbf{D}$ of convex sets of finitely supported probability distributions [GP20].

$$ \lambda_X^{\mathbf{P}/\mathbf{P}}(E) = \{e' \in \mathbf{P}X \mid e' \subseteq \bigcup E \text{ and } \forall e \in E, e \cap e' \neq \emptyset\} \quad (2.1) $$

$$ \lambda_X^{\mathbf{V}/\mathbf{V}}(C) = \{c' \in \mathbf{V}X \mid c' \subseteq \bigcup C \text{ and } \forall c \in C, c \cap c' \neq \emptyset\} \quad (2.2) $$

$$ \lambda_X^{\mathbf{D}/\mathbf{P}}(\Phi) = \{ (\mu_X^{\mathbf{D}} \circ \mathbf{D}f)(\Phi) \mid f: \mathbf{P}X \to \mathbf{D}X \text{ and } \forall e \in \mathbf{P}X, \Phi(e) \neq 0 \Rightarrow f(e) \in \mathbf{D}e \} \quad (2.3) $$

At this point two questions may come to the curious reader: how do we actually find these weak distributive laws – the formulæ in Example 2.4 are not trivial – and where does the monad structure on $S \bullet T$ come from. These two questions will respectively be answered in the next two sections, which give two other equivalent presentations of weak distributive laws.

## 2.2. Regular Categories and Monotone (Weak) Extensions.
Given a monad $S$, one may form its *Kleisli category* $\mathbf{KI}(S)$, which is intuitively the category of $S$-effectful $C$-arrows: its objects are those of $C$, its arrows $X \dasharrow Y$ are those arrows $X \to SY$ in $C$, the identity arrow $X \dasharrow X$ is given by $\eta_X^S: X \to SX$, and the composite of two arrows $f: X \dasharrow Y$ and $g: Y \dasharrow Z$ is given by the composition $X \xrightarrow{f} SY \xrightarrow{Sg} SSZ \xrightarrow{\mu_Z^S} SZ$ in $C$. $\mathbf{KI}(S)$ comes with an adjunction $\mathbf{F}_S: C \rightleftharpoons \mathbf{KI}(S):\mathbf{U}_S$, such that $\mathbf{U}_S\mathbf{F}_S = S$: the left adjoint $\mathbf{F}_S$ sends
objects on themselves and an arrow $f: X \to Y$ to the pure effectful arrow $X \xrightarrow{f} Y \xrightarrow{\eta_Y^S} SY$, while the right adjoint $\mathbf{U}_S$ sends an object $X$ on $SX$ and an effectful arrow $f: X \to SY$ to the arrow $SX \xrightarrow{Sf} SSY \xrightarrow{\mu^S} Y$. The unit of the adjunction is $\eta^S$ and its counit is the natural transformation $\varepsilon^S: \mathbf{F}_S \mathbf{U}_S \Rightarrow \text{id}$ (in $\mathbf{KI}(S)$) with components the effectful arrows $\text{id}_{SX}: SX \to SX$.

An endofunctor $T: C \to C$ extends to $\mathbf{KI}(S)$ if there is an endofunctor $\underline{T}: \mathbf{KI}(S) \to \mathbf{KI}(S)$ such that $\underline{T}\mathbf{F}_S = \mathbf{F}_S\underline{T}$. If $T$ and $T'$ have extensions $\underline{T}$ and $\underline{T}'$, a natural transformation $\alpha: T \Rightarrow T'$ extends to $\mathbf{KI}(S)$ if $\underline{\alpha}$, given by $\underline{\alpha}\mathbf{F}_S = \mathbf{F}_S\underline{\alpha}$, is a natural transformation $\underline{T} \Rightarrow \underline{T}'$.

**Definition 2.5** (extensions of monads). Let $S$ be a monad on $C$. A monad $(T, \eta^T, \mu^T)$ on $C$ weakly extends to $\mathbf{KI}(S)$ when $T$ and $\mu^T$ extend to $\mathbf{KI}(S)$. It extends to $\mathbf{KI}(S)$ when $\eta^T$ also extends to $\mathbf{KI}(S)$.

Giving an extension of a monad $T$ to $\mathbf{KI}(S)$ is equivalent to giving a distributive law $\rho: TS \Rightarrow ST$, just like giving a weak extension thereof is equivalent to giving a weak distributive law of the same type [Gar19]: in both cases, the law $\rho$ induces the extension which sends $f: X \to SY$ to $T X \xrightarrow{Tf} TSY \xrightarrow{\rho} STY$, and is computed from the extension as $\rho = \mathbf{U}_S \underline{T} \varepsilon^S \mathbf{F}_S \circ \eta^S TS$. In particular Example 2.4 also yields examples of weak extensions.

**Monotone extensions.** If $\mathbf{KI}(S)$ carries more structure than just that of a category then it is natural to ask that extensions of functors preserve this additional structure: intuitively, the more structure preserved, the more semantically canonical the resulting law should be. For instance, recall that $\mathbf{KI}(\mathbf{P})$ is the category **Rel** of sets and relations and that relations between two sets are ordered by inclusion. Laws arising from monotone extensions to **Rel** are thus of particular interest.

**Definition 2.6** (monotone (weak) distributive laws and extensions). A (weak) distributive law $TS \Rightarrow ST$ and its (weak) extension $\underline{T}$ to $\mathbf{KI}(S)$ are called *monotone* when the sets of morphisms of $\mathbf{KI}(S)$ admit a canonical order that is preserved by $\underline{T}$.

It turns out that such monotone extensions to relations can be defined and characterized in any *regular category*, as described in [GPA21] and recalled now.

Let $C$ be a finitely complete category. The *kernel pair* of an arrow $f: X \to Y$ is the pullback $p_1, p_2: X \times_Y X \twoheadrightarrow X$ of the cospan $X \xrightarrow{f} Y \xleftarrow{f} X$. Assume $C$ has all the coequalizers of these kernel pairs: these coequalizers are called *regular epimorphisms*. $C$ is then called *regular* if these conditions are satisfied and if the regular epimorphisms are stable under pullbacks<fnref n="1" />. Regular categories enjoy the fact that every arrow $f: X \to Y$ may be factored as a regular epimorphism (denoted with $\twoheadleftarrow$) followed by a monomorphism (denoted with $\twoheadleftarrow$), and this factorization is unique up to unique isomorphism – one should think of it as factoring an arrow through its image. **Set** is a canonical example of a regular category.

Regular categories are useful because they are categories where we can speak of relations: if $C$ is a regular category, a $C$-relation between two objects $X$ and $Y$ is a subobject $r: R \hookrightarrow X \times Y$. Relations are preordered: $r: R \hookrightarrow X \times Y$ is smaller than $s: S \hookrightarrow X \times Y$, written $r \leq s$, when there is a monomorphism $m: R \hookrightarrow S$ such that $s \circ m = r$. One may form the category **Rel**($C$) with objects those of $C$ and arrows $X \leftrightarrowmapsto Y$ the equivalence classes of relations between $X$ and $Y$. The identity on $X$ is the diagonal $\langle \text{id}_X, \text{id}_X \rangle: X \hookrightarrow X \times X$, and composition of

<footnote n="1">¹a class of arrows is stable under pullbacks when for every pullback square $a \circ b = c \circ d$, if $a$ is in the class then so is $d$</footnote>
relations $r = \langle r_X, r_Y \rangle: R \hookrightarrow X \times Y$ and $s = \langle s_Y, s_Z \rangle: S \hookrightarrow Y \times Z$, written $s \cdot r: X \rightsquigarrow Z$, is constructed as in Figure 1a: by considering the pullback $R \times_Y S \to R \times S$ of $R \xrightarrow{r_Y} Y \xleftarrow{s_Y} S$, and taking the monomorphism in the factorization of $R \times_Y S \to R \times S \xrightarrow{r_X \times s_Z} X \times Z$.

<figure><img src="image_3.png" /><figcaption>FIGURE 1. Diagrams involved in the definition of regular categories.</figcaption></figure>

The graph functor **Graph**<sub>C</sub>: C → **Rel**(C) sends objects to themselves and an arrow f: X → Y to the relation ⟨id<sub>X</sub>, f⟩: X ↪→ X × Y. There is also a contravariant transpose functor −†: **Rel**(C) → **Rel**(C) that sends objects on themselves and a relation ⟨r<sub>X</sub>, r<sub>Y</sub>⟩: R ↪→ X × Y to ⟨r<sub>Y</sub>, r<sub>X</sub>⟩: R ↪→ Y × X. All in all, a relation ⟨f, g⟩: R ↪→ X × Y can also be written as the composite **Graph**<sub>C</sub>g · (**Graph**<sub>C</sub>f)†: we will often omit **Graph** and write directly g · f†.

The previous construction of the category of relations of a regular category is in fact 2-functorial, in the sense that certain functors and natural transformations can be extended to categories of relations. The functors and natural transformations that can be extended so are characterized in terms of *near pullbacks*.

A square $g_1 \circ f_1 = g_2 \circ f_2$ is a near pullback when its limiting morphism into the corresponding pullback is a regular epimorphism – as in Figure 1b – or, equivalently, when $g_2^\dagger \cdot g_1 = f_2 \cdot f_1^\dagger$ (it is always true that $g_2^\dagger \cdot g_1 \ge f_2 \cdot f_1^\dagger$). A functor between regular categories is said to be *nearly cartesian* when it sends pullbacks on near pullbacks and preserves<fnref n="2" /> regular epimorphisms, or equivalently when it preserves near pullbacks, while a natural transformation $\alpha: \mathbf{F} \Rightarrow \mathbf{G}$ between nearly cartesian functors is *nearly cartesian* as well when its naturality squares $\alpha \circ \mathbf{F}\mathbf{f} = \mathbf{G}\mathbf{f} \circ \alpha$ are near pullbacks.

**Theorem 2.7** ([GPA21, Theorem 6]). Let F: C → D be a functor between regular categories. F has a relational extension, i.e. an order-preserving functor **Rel**(F): **Rel**(C) → **Rel**(D) such that **Rel**(F) **Graph**<sub>C</sub> = **Graph**<sub>D</sub> F, if and only if F is nearly cartesian. In that case there is only one possible such **Rel**(F), given by **Rel**(F)(g · f<sup>†</sup>) = (Fg) · (Ff)<sup>†</sup>.

Let F, G: C ⇝ D be two such functors and α: F ⇒ G be a natural transformation between them. Then **Rel**(α), given by **Rel**(α) **Graph**<sub>D</sub> = **Graph**<sub>D</sub>α, is a natural transformation **Rel**(F) ⇒ **Rel**(G), called the relational extension of α, if and only if α is nearly cartesian.

Just like we omit to write **Graph**, we will often omit to write the functor **Rel**, and instead write $F(g \cdot f^\dagger)$ for **Rel**(F)(g \cdot f^\dagger) = Fg \cdot (Ff)^\dagger$ and $\alpha$ for **Rel**(α).

<footnote n="2">²throughout this work we will say that a functor preserves a class of diagrams whenever it sends any diagram in that class to a diagram in that class</footnote>
**Theorem 2.7** is particularly useful to build weak distributive laws over monads whose Kleisli categories are subcategories of relations – we call these monads *sub-power-object monads*:

**Definition 2.8** (sub-power-object monad). A monad $(\mathcal{S}, \eta^{\mathcal{S}}, \mu^{\mathcal{S}})$ on a regular category $\mathcal{C}$ is a *sub-power-object monad* when $\mathbf{KI}(\mathcal{S})$ is a wide$^3$ subcategory of $\mathbf{Rel}(\mathcal{C})$ such that **Graph**$_{\mathcal{C}}$ factors as $\mathcal{C} \xrightarrow{\mathbf{F}_{\mathcal{S}}} \mathbf{KI}(\mathcal{S}) \hookrightarrow \mathbf{Rel}(\mathcal{C})$.

If $\mathcal{S}$ is a sub-power-object monad on $\mathcal{C}$, an extension to $\mathbf{KI}(\mathcal{S})$ can be constructed by first finding a monotone extension to $\mathbf{Rel}(\mathcal{C})$ using Theorem 2.7 and then restricting this extension to $\mathbf{KI}(\mathcal{S})$. In fact, most examples of weak distributive laws in the literature are obtained in this way:

**Example 2.9** (monotone extensions). **Set** is a regular category whose regular epimorphisms are the surjections and such that $\mathbf{Rel}(\mathbf{Set}) = \mathbf{Rel} \cong \mathbf{KI}(\mathbf{P})$. The endofunctors and the multiplications of the monads **P** and **D** are nearly cartesian, hence **P** and **D** have monotone weak extensions to $\mathbf{KI}(\mathbf{P})$: this is how the weak distributive laws $\mathbf{PP} \Rightarrow \mathbf{PP}$ and $\mathbf{DP} \Rightarrow \mathbf{PD}$ of Example 2.4 were constructed [Gar19, GP20].

**KHaus** is also a regular category: its regular epimorphisms are the surjective continuous functions and $\mathbf{Rel}(\mathbf{KHaus})$ is the category of compact Hausdorff spaces and closed relations, i.e. closed subsets of $X \times Y$, while $\mathbf{KI}(\mathbf{V})$ is the category of compact Hausdorff spaces and continuous relations, i.e. closed relations $r: X \leftrightarrow Y$ such that $r^{-1}[u]$ is open in $X$ for every open $u$ of $Y$. The endofunctor and multiplication of **V** are nearly cartesian hence they have relational extensions, which restrict to continuous relations: this yields a monotone weak extension of **V** to $\mathbf{KI}(\mathbf{V})$, and this is how the weak distributive law $\mathbf{VV} \Rightarrow \mathbf{VV}$ of Example 2.4 was constructed [GPA21].

**2.3. Weak Liftings.** Let $\mathbf{T}$ be a monad over a category $\mathcal{C}$. Its category of algebras $\mathbf{EM}(\mathbf{T})$ is the category whose objects are pairs $(A, a)$ of a $\mathcal{C}$-object $A$ and a $\mathcal{C}$-arrow $a: \mathbf{T}A \to A$ such that $a \circ \eta_A^\mathbf{T} = \mathrm{id}_A$ and $a \circ \mathbf{T}a = a \circ \mu^\mathbf{T}a$, and whose arrows $(A, a) \to (B, b)$ are those $\mathcal{C}$-arrows $A \to B$ such that $f \circ a = b \circ \mathbf{T}f$ – the identity morphism is the one with the identity as its underlying $\mathcal{C}$-arrow, and composition of morphisms is done by composing the underlying $\mathcal{C}$-arrows. Just like for $\mathbf{KI}(\mathbf{T})$, there is an adjunction $\mathbf{F}^\mathbf{T}: \mathcal{C} \hookrightarrow \mathbf{EM}(\mathbf{T}): \mathbf{U}^\mathbf{T}$ such that $\mathbf{U}^\mathbf{T}\mathbf{F}^\mathbf{T} = \mathbf{T}$: the left adjoint $\mathbf{F}^\mathbf{T}$ sends an algebra $(A, a)$ to its carrier object $A$ and a morphism $(A, a) \to (B, b)$ to the underlying arrow $A \to B$, while $\mathbf{U}^\mathbf{T}$ sends an object $X$ to the free $\mathbf{T}$-algebra on $X$, given by the pair $(\mathbf{T}X, \mu_X^\mathbf{T})$, and an arrow $f: X \to Y$ to the morphism $(\mathbf{T}X, \mu_X^\mathbf{T}) \to (\mathbf{T}Y, \mu_Y^\mathbf{T})$ with underlying $\mathcal{C}$-arrow $\mathbf{T}f: \mathbf{T}X \to \mathbf{T}Y$. The unit of the adjunction is $\eta^\mathbf{T}$ and its counit is the natural transformation $\varepsilon^\mathbf{T}: \mathbf{F}^\mathbf{T}\mathbf{U}^\mathbf{T} \Rightarrow \mathrm{id}$ (in $\mathbf{EM}(\mathbf{T}))$ given by $\mathbf{U}^\mathbf{T}\varepsilon_{(A,a)}^\mathbf{T} = a: \mathbf{T}A \to A$.

**Definition 2.10** (weak liftings [Böh10, Definitions 4.1 and 4.2]). A *weak lifting* of an endofunctor $\mathcal{S}: \mathcal{C} \to \mathcal{C}$ to $\mathbf{EM}(\mathbf{T})$ is the data of an endofunctor $\bar{\mathcal{S}}: \mathbf{EM}(\mathbf{T}) \to \mathbf{EM}(\mathbf{T})$ along with natural transformations $\pi_{\mathcal{S}}^\mathbf{T}: \mathbf{SU}^\mathbf{T} \Rightarrow \mathbf{U}^\mathbf{T}\bar{\mathcal{S}}$ and $\iota_{\mathcal{S}}^\mathbf{T}: \mathbf{U}^\mathbf{T}\bar{\mathcal{S}} \Rightarrow \mathbf{SU}^\mathbf{T}$ – also written $\pi_{\mathcal{S}}$ and $\iota_{\mathcal{S}}$ when not ambiguous – such that $\pi_{\mathcal{S}}^\mathbf{T} \circ \iota_{\mathcal{S}}^\mathbf{T} = \mathrm{id}$. The composite $\iota_{\mathcal{S}}^\mathbf{T} \circ \pi_{\mathcal{S}}^\mathbf{T}$ is then written $\kappa_{\mathcal{S}}^\mathbf{T}$.

Let $\alpha: \mathcal{S} \Rightarrow \mathbb{R}$ be a natural transformation between two $\mathcal{C}$-endofunctors with weak liftings $(\bar{\mathcal{S}}, \pi_{\mathcal{S}}, \iota_{\mathcal{S}})$ and $(\bar{\mathcal{R}}, \pi_{\mathcal{R}}, \iota_{\mathcal{R}})$. If a natural transformation $\bar{\alpha}: \bar{\mathcal{S}} \Rightarrow \bar{\mathcal{R}}$ has Diagram $(\pi)$,

<footnote>$^3$A wide subcategory is a subcategory that contains all objects of the bigger category</footnote>
Diagram (ι) or both Diagrams (π) and (ι) below commute, it is respectively a weak π-, weak ι- or a weak lifting of α.

<figure><img src="image_4.png" /></figure>

As discussed in [Böh10], weak π- and weak ι-liftings are necessarily unique and given by $\mathbf{U}^T\bar{\alpha} = \pi_R^T \circ \alpha \circ \iota_S^T$ when they exist. The existence of weak liftings is moreover fully characterized:

**Theorem 2.11** ([Böh10, Proposition 4.3 and Theorem 4.4]). Suppose idempotents split in C. Then idempotents also split in $\mathbf{EM}(T)$, and having a weak lifting of S: $C \to C$ to $\mathbf{EM}(T)$ is equivalent to having a law $\rho$: $TS \Rightarrow ST$ that has Diagram $(\mu^+)$ commute.

Fix now liftings $\bar{S}$ and $\bar{R}$ of S and R given by laws $\rho$: $TS \Rightarrow ST$ and $\sigma$: $TR \Rightarrow RT$. Then, $\alpha$: $S \Rightarrow R$ respectively has a weak $\pi-$, weak $\iota-$ or weak lifting if and only if it makes Diagram (7), Diagram (8) or both Diagrams (7) and (8) below commute. The latter case also holds if and only if $\sigma \circ T\alpha = \alpha T \circ \rho$.

<figure><img src="image_5.png" /></figure>

Weakly lifting is functorial: the composition of the weak (resp. weak $\pi-$, weak $\iota-$) liftings of two functors (resp. natural transformations) is a weak (resp. weak $\pi-$, weak $\iota-$) lifting of their composite.

In [Gar19], Garner instantiates Theorem 2.11 to give another presentation of weak distributive laws: if idempotents split in C, a weak distributive law $TS \Rightarrow ST$ is equivalently given by a weak lifting of $(S, \eta^S, \mu^S)$ to $\mathbf{EM}(T)$, i.e. by weak liftings of S, $\eta^S$ and $\mu^S$, respectively coming from Diagrams $(\mu^-)$, $(\eta^+)$ and $(\mu^+)$. That these two natural transformations weakly lift respectively means that Diagrams $(\pi \circ \eta)$ and $(\iota \circ \eta)$ and Diagrams $(\pi \circ \mu)$ and $(\iota \circ \mu)$ below commute. When Diagram $(\eta^-)$ also commutes, $\rho$ is a (strict) distributive law and this weak lifting is a (strict) lifting: $\pi_S$ and $\iota_S$ are both the identity.

<figure><img src="image_6.png" /></figure>
The weak composite monad $S \bullet T$ corresponding to a weak distributive law $TS \Rightarrow ST$ can be retrieved from the weak lifting of $S$ to $\mathbf{EM}(T)$ by setting $S \bullet T = \mathbf{U}^T \bar{S} \mathbf{F}^T$, $\eta^{S\bullet T} = \mathbf{U}^T \eta \bar{S} \mathbf{F}^T \circ \eta^T$ and $\mu^{S\bullet T} = \mathbf{U}^T \mu \bar{S} \mathbf{F}^T \circ \mathbf{U}^T \bar{S} \varepsilon^T \bar{S} \mathbf{F}^T$. $\kappa_S^T \mathbf{F}^T$ is moreover the idempotent $\mu^{ST} \circ \eta^{ST} \mathbf{ST}: ST \Rightarrow ST$, and its splitting is thus given by $\pi_S^T \mathbf{F}^T: ST \Rightarrow S \bullet T$ and $\iota_S^T \mathbf{F}^T: S \bullet T \Rightarrow ST$.

**Example 2.12** (weak liftings). All idempotents split in **Set** (they factor through their image). The algebras of **P** are the *complete join-semilattices* (we write **EM**(**P**) ≅ **JSL**): the weak lifting corresponding to the law **PP** ⇒ **PP** is the monad of *subsets closed under non-empty joins* [GPA21]. The algebras of **D** are the *barycentric algebras*, also called *convex spaces* (we write **EM**(**D**) ≅ **Conv**): the weak lifting corresponding to the law **DP** ⇒ **PD** is the monad of *convex-closed subsets* [GP20]. Finally, there is also a weak distributive law **βP** ⇒ **Pβ**. Assuming the axiom of choice, the algebras of **β** are the compact Hausdorff spaces [Man69] (we write **EM**(**β**) ≅ **KHaus**): the corresponding weak lifting is the Vietoris monad **V**. In that case $\pi_{\mathbf{P}}$ computes the topological closure of a subset, while $\iota_{\mathbf{P}}$ embeds the set of closed sets into the set of all subsets.

## 2.4. Semi-algebras.
This last preliminary subsection recalls how weak liftings are constructed [Gar19, §3.2]. This will only be used in some specific proofs, and may thus be skipped on a first read.

Call a *semi-monad* on a category $C$ the data $(\mathbf{T}, \mu^\mathbf{T})$ of an endofunctor $\mathbf{T}: C \to C$ and a natural transformation $\mu^\mathbf{T}: \mathbf{TT} \to \mathbf{T}$ such that $\mu^\mathbf{T} \circ \mathbf{T}\mu^\mathbf{T} = \mu^\mathbf{T} \circ \mu^\mathbf{T}\mathbf{T}$. In particular, any monad has an underlying semi-monad, weak distributive laws are really distributive laws between a monad and a semi-monad, and weak extensions of monads are just extensions of the underlying semi-monads.

Given a semi-monad $\mathbf{T}$, one may form the category $\mathbf{EM}_s(\mathbf{T})$ of its *semi-algebras*: a semi-$\mathbf{T}$-algebra is a pair $(A, a)$ of an object $A$ of $C$ and of an arrow $a: \mathbf{T}A \to A$ such that $a \circ \mu_A^\mathbf{T} = a \circ \mathbf{T}a$, and a semi-$\mathbf{T}$-algebra morphism $(A, a) \to (B, b)$ is an arrow $f: A \to B$ in $C$ such that $f \circ a = b \circ \mathbf{T}f$ — the identity morphism is the one with the identity as its underlying $C$-arrow, and composition of morphisms is done by composing the underlying $C$-arrows. Just like for $\mathbf{EM}(\mathbf{T})$, there are functors $\mathbf{F}_s^\mathbf{T}: C \to \mathbf{EM}_s(\mathbf{T}): \mathbf{U}_s^\mathbf{T}$ such that $\mathbf{U}_s^\mathbf{T} \mathbf{F}_s^\mathbf{T} = \mathbf{T}: \mathbf{U}_s^\mathbf{T}$ sends a semi-algebra $(A, a)$ to its carrier object $A$ and a morphism $(A, a) \to (B, b)$ to the underlying arrow $A \to B$, while $\mathbf{F}_s^\mathbf{T}$ sends an object $X$ to the free $\mathbf{T}$-algebra on $X$, given by the pair $(\mathbf{T}X, \mu_X^\mathbf{T})$, and an arrow $f: X \to Y$ to the morphism $(\mathbf{T}X, \mu_Y^\mathbf{T}) \to (\mathbf{T}Y, \mu_Y^\mathbf{T})$ with underlying $C$-arrow $\mathbf{T}f: \mathbf{T}X \to \mathbf{T}Y$. There is a natural transformation $\varepsilon^\mathbf{T}: \mathbf{F}_s^\mathbf{T} \mathbf{U}_s^\mathbf{T} \Rightarrow \mathbf{Id}$ (in $\mathbf{EM}_s(\mathbf{T})$) given by $\mathbf{U}_s^\mathbf{T} \varepsilon_{(A,a)}^\mathbf{T} = a: \mathbf{T}A \to A$.

If $\mathbf{T}$ is also a monad, $\mathbf{EM}(\mathbf{T})$ is a full subcategory of $\mathbf{EM}_s(\mathbf{T})$. We write $\mathbf{I}^\mathbf{T}$ for the inclusion $\mathbf{EM}(\mathbf{T}) \to \mathbf{EM}_s(\mathbf{T})$, and $\mathbf{F}^\mathbf{T}$ and $\mathbf{U}^\mathbf{T}$ are the restrictions of $\mathbf{F}_s^\mathbf{T}$ and $\mathbf{U}_s^\mathbf{T}$ to $\mathbf{EM}(\mathbf{T})$.

In general if $U: D \to C$ is a functor, a *lifting* of an endofunctor $F: C \to C$ along $U$ is an endofunctor $\bar{F}: D \to D$ such that $U\bar{F} = FU$, while a lifting of a natural transformation $\alpha: F \to G$ between endofunctors with liftings $\bar{F}$ and $\bar{G}$ is a natural transformation $\bar{\alpha}$ such that $U\bar{\alpha} = \alpha U$.

**Definition 2.13** (lifting to algebras). Let $\mathbf{T}$ be a monad on $C$. A monad $(S, \eta^S, \mu^S)$ on $C$ *semi-lifts* to $\mathbf{EM}_s(\mathbf{T})$ when $\mathbf{T}$, $\eta^\mathbf{T}$ and $\mu^\mathbf{T}$ lift along $\mathbf{U}_s^\mathbf{T}$. It *lifts* to $\mathbf{EM}(\mathbf{T})$ when it has a semi-lifting to $\mathbf{EM}_s(\mathbf{T})$ that restricts to $\mathbf{EM}(\mathbf{T})$.
*Proof.* Recall from [Gar19] that, if $X$ is a compact Hausdorff space that we see as a $\beta$-algebra, the $X$-component of $\pi_P$ is the function $PX \to VX$ that takes a subset of a compact Hausdorff space and outputs its closure, while the $X$-component of $\iota_P$ is the function $VX \to PX$ that embeds closed subsets in the set of all subsets. Hence for $C$ a closed set of closed sets,

$$ \begin{aligned} \left( \mathbf{P}\pi_{\mathbf{P}} \circ \lambda^{\mathbf{P}/\mathbf{P}} \mathbf{U}^{\beta} \circ \mathbf{P}_{\iota_{\mathbf{P}}} \circ \iota_{\mathbf{P}} \mathbf{V} \right)_X (C) &= \{ \bar{e} \mid e \subseteq \bigcup C \text{ and } \forall c \in C, c \cap e \neq \emptyset \} \\ &= \{ c \in \mathbf{V}X \mid c \subseteq \bigcup C \text{ and } \forall c' \in C, c \cap c' \neq \emptyset \} \\ &= \left( \iota_{\mathbf{P}} \mathbf{V} \circ \mathbf{U}^{\beta} \lambda^{\mathbf{V}/\mathbf{V}} \right)_X (C) \end{aligned} $$

(where $\bar{e}$ denotes the closure of $e$). Indeed if $e \subseteq \bigcup C$ then $\bar{e} \subseteq \bigcup C$ because $\bigcup C = \mu^{\mathbf{V}}(C)$ is closed, and if $e \cap c \neq \emptyset$ then $\bar{e} \cap c \neq \emptyset$.

Because $\pi_P \circ \iota_P = \text{id}$, $\mathbf{U}^{\beta} \lambda^{\mathbf{V}/\mathbf{V}} = \pi_P \mathbf{V} \circ \mathbf{P}\pi_P \circ \lambda^{\mathbf{P}/\mathbf{P}} \mathbf{U}^{\beta} \circ \mathbf{P}_{\iota_P} \circ \iota_{\mathbf{P}} \mathbf{V}$.

<figure><img src="image_7.png" /></figure>

Is this just a coincidence, or is this an instance of Theorem 2.11? And in the latter case, can the weak distributivity of $\lambda^{\mathbf{V}/\mathbf{V}}$ be automatically derived from that of $\lambda^{\mathbf{P}/\mathbf{P}}$? Does this law $\mathbf{PP} \Rightarrow \mathbf{PP}$ also weakly lift to laws on other categories of algebras where the powerset monad weakly lifts, say $\mathbf{EM}(\mathbf{P})$ and $\mathbf{EM}(\mathbf{D})$?

In this section we thus consider three monads $(\mathbf{T}, \eta^\mathbf{T}, \mu^\mathbf{T})$, $(\mathbf{S}, \eta^\mathbf{S}, \mu^\mathbf{S})$ and $(\mathbf{R}, \eta^\mathbf{R}, \mu^\mathbf{R})$ on a category $\mathbf{C}$, and three weak distributive laws $\rho$: $\mathbf{TS} \Rightarrow \mathbf{ST}$, $\sigma$: $\mathbf{TR} \Rightarrow \mathbf{RT}$ and $\tau$: $\mathbf{SR} \Rightarrow \mathbf{RS}$ (a mnemonic for which is which is that $\rho$ does not involve $\mathbf{R}$, $\sigma$ does not involve $\mathbf{S}$ and $\tau$ does not involve $\mathbf{T}$), and study when $\tau$: $\mathbf{SR} \Rightarrow \mathbf{RS}$ weakly lifts to $\mathbf{EM}(\mathbf{T})$. We assume that idempotents split in $\mathbf{C}$, so that the corresponding weak composite and weak liftings all exist.

**3.1. The Yang-Baxter Equation for Weak Distributive Laws.** The standard way to lift (strict) distributive laws is to use the so-called Yang-Baxter equation. The Yang-Baxter equation for the three laws $\rho$, $\sigma$ and $\tau$ holds when diagram (YB) below commutes.

<figure><img src="image_8.png" /></figure>

If these laws are strict distributive laws, then it is well-known since [Che11] that the Yang-Baxter equation is enough to show that $R\rho \circ \sigma S$: $\mathbf{TRS} \Rightarrow \mathbf{RST}$ is a distributive law of $\mathbf{T}$ over $\mathbf{RS}$, and that the distributive law $\tau$: $\mathbf{SR} \Rightarrow \mathbf{RS}$ lifts to a distributive law $\bar{\tau}$: $\overline{\mathbf{SR}} \Rightarrow \overline{\mathbf{RS}}$ in $\mathbf{EM}(\mathbf{T})$. The composition of weak distributive laws using the Yang-Baxter equation was investigated in [Goy23]. A notable result is the following:

**Proposition 3.2** ([Goy23, Theorem 4.3]). If the weak distributive laws $\rho$: $\mathbf{TS} \Rightarrow \mathbf{ST}$, $\sigma$: $\mathbf{TR} \Rightarrow \mathbf{RT}$ and $\tau$: $\mathbf{SR} \Rightarrow \mathbf{RS}$ have Diagram (YB) commute, then $\pi_R^S \mathbf{F}^S \mathbf{T} \circ R\rho \circ \sigma S \circ T\iota_R^S \mathbf{F}^S$ is a weak distributive law $\mathbf{T}(R \bullet S) \Rightarrow (R \bullet S)\mathbf{T}$.

The Yang-Baxter equation thus allows for weakly lifting $R \bullet S$ to $\mathbf{EM}(\mathbf{T})$. More importantly for our purpose, we show it also allows for weakly lifting the weak distributive law $\mathbf{SR} \Rightarrow \mathbf{RS}$:
**Theorem 3.3.** *Weak distributive laws $\rho: TS \Rightarrow ST$, $\sigma: TR \Rightarrow RT$ and $\tau: SR \Rightarrow RS$ satisfy the Yang-Baxter equation if and only if $\tau: SR \Rightarrow RS$ weakly lifts to EM(T), i.e. if there is a natural transformation $\bar{\tau}: \bar{SR} \Rightarrow \bar{RS}$ such that Diagrams (15) and (16) commute.*

<figure><img src="image_9.png" /></figure>

*If this holds, $\bar{\tau}$ is a weak distributive law, and the weak composite $\bar{R} \bullet \bar{S}$ and the weak lifting $\bar{R} \bullet \bar{S}$ (recall that $R \bullet S$ weakly lifts to EM(T) by Proposition 3.2) can be chosen to be equal (as monads).*

*Proof.* We apply Theorem 2.11: recall that SR and RS have weak liftings $\bar{SR}$ and $\bar{RS}$ thanks to the laws $S\sigma \circ \rho R$ and $R\rho \circ \sigma S$. Then $\tau: SR \Rightarrow RS$ weakly lifts to EM(T) as $\bar{\tau}: \bar{SR} \Rightarrow \bar{RS}$ if and only if $R\rho \circ \sigma S \circ T\tau = \tau T \circ S\sigma \circ \rho R$: this is exactly the Yang-Baxter equation. Because weakly lifting is functorial (Theorem 2.11), it preserves any equation satisfied by $\tau$, $\eta^S$, $\eta^R$, $\mu^S$ and $\mu^R$ (they all weakly lift to EM(T)): since $\tau$ is a weak distributive law, so is $\bar{\tau}$.

We now prove that $\pi_R^S F^S: RS \Rightarrow R \bullet S$ and $\iota_R^S F^S: R \bullet S \Rightarrow RS$ also weakly lift to EM(T) as natural transformations $\bar{RS} \Rightarrow \bar{R} \bullet \bar{S}$ and $\bar{R} \bullet \bar{S} \Rightarrow \bar{S} \bar{R}$. It will then follow, again by functoriality, that these two liftings form a splitting of the idempotent $\bar{RS} \Rightarrow \bar{RS}$ and that $\bar{R} \bullet \bar{S}$ can thus be chosen as the weak composite monad $\bar{R} \bullet \bar{S}$.

We apply Theorem 2.11 again: RS and $R \bullet S$ have weak liftings $\bar{RS}$ and $\bar{R} \bullet \bar{S}$ thanks to the laws $R\rho \circ \sigma S$ and $\pi_R^S F^S T \circ R\rho \circ \sigma S \circ T\iota_R^S F^S$ (see Proposition 3.2 for the latter). Thus $\pi_R^S$ weakly lifts to EM(T) if and only if

$$\pi_R^S F^S T \circ R\rho \circ \sigma S \circ T\kappa_R^S F^S = \pi_R^S F^S T \circ R\rho \circ \sigma S$$

Similarly, $\iota_R^S$ weakly lifts to EM(T) if and only if

$$R\rho \circ \sigma ST \circ \iota_R^S F^S = \iota_R^S F^S T \circ \pi_R^S F^S T \circ R\rho \circ \sigma S \circ T\iota_R^S F^S$$

These two results are an immediate consequence of [Goy23, Lemma 4.2] which states that $\kappa_R^S F^S T \circ R\rho \circ \sigma S = R\rho \circ \sigma S \circ T\kappa_R^S F^S$.

Note that it is also possible but much more tedious to prove this result by hand, by checking that $\bar{\tau}$ as given by Diagrams (15) and (16) is indeed a weak distributive law. $\square$

When Theorem 3.3 holds it immediately follows that $U\bar{\tau} = \pi_R \bar{S} \circ R\pi_S \circ \tau U^T \circ S\iota_R \circ \iota_S \bar{R}$, which is exactly the result we got in Lemma 3.1 for $\bar{\tau} = \lambda^{V/V}: VV \Rightarrow VV$ and $\tau = \lambda^{P/P}: PP \Rightarrow PP$. It would thus be a reasonable conjecture that $\lambda^{\beta/P}: \beta P \Rightarrow P\beta$, $\lambda^{\beta/P}: \beta P \Rightarrow P\beta$ and $\lambda^{P/P}: PP \Rightarrow PP$ satisfy the Yang-Baxter equation, from which we would immediately retrieve the weak distributivity of $\lambda^{V/V}: VV \Rightarrow VV$ but also learn that the weak composite $V \bullet V$ is a weak lifting of $P \bullet P$. Unfortunately, the Yang-Baxter equation does not hold in that case. A rather simple way to see this is to notice that $\lambda^{V/V}$ does not make Diagram (16) commute, i.e. it is not a $\iota$-lifting of $\lambda^{P/P}$. More generally, we show the following no-go theorem for weak $\iota$-liftings:

**Proposition 3.4.** Let $\lambda^{T/P}: TP \Rightarrow PT$ be a weak distributive law with corresponding weak lifting $\bar{P}$, and write $\bar{PP}A = (P\iota_P \circ \iota_P \bar{P}) [U^T \bar{P} \bar{P}(A, a)]$ when $(A, a)$ is a T-algebra. If there
is an $(A, a)$ such that $\{A\} \in \overline{\mathbb{P}}\overline{\mathbb{P}}A$ and $\mathbf{P}_*A \notin \overline{\mathbb{P}}\overline{\mathbb{P}}A$, then $\lambda^{\mathbf{P}/\mathbf{P}}: \mathbf{P}\mathbf{P} \Rightarrow \mathbf{PP}$ does not have a weak $\iota$-lifting to $\mathbf{EM}(\mathbf{T})$.

*Proof.* Suppose there is such an algebra, and consider any $\lambda^{\mathbf{P}/\mathbf{P}}: \overline{\mathbb{P}}\overline{\mathbb{P}} \Rightarrow \overline{\mathbb{P}}\overline{\mathbb{P}}$. Let $E \in \mathbf{U}^{\mathbf{T}}\overline{\mathbb{P}}\overline{\mathbb{P}}(A, a)$ be such that $(\mathbf{P}_{\iota\mathbf{P}} \circ \iota_{\mathbf{P}}\overline{\mathbb{P}})(E) = \{A\}$. Then, by Equation (2.1),

$$ (\lambda^{\mathbf{P}/\mathbf{P}} \circ \mathbf{P}_{\iota\mathbf{P}} \circ \iota_{\mathbf{P}}\overline{\mathbb{P}})(E) = \lambda^{\mathbf{P}/\mathbf{P}}(\{A\}) = \mathbf{P}_*A $$

But $\mathbf{P}_*A \notin \overline{\mathbb{P}}\overline{\mathbb{P}}A$, hence necessarily $(\mathbf{P}_{\iota\mathbf{P}} \circ \iota_{\mathbf{P}}\overline{\mathbb{P}} \circ \mathbf{U}^{\mathbf{T}}\lambda^{\mathbf{P}/\mathbf{P}})(E) \in \overline{\mathbb{P}}\overline{\mathbb{P}}A$ must be different from $(\lambda^{\mathbf{P}/\mathbf{P}} \circ \mathbf{P}_{\iota\mathbf{P}} \circ \iota_{\mathbf{P}}\overline{\mathbb{P}})(E)$: Diagram (16) does not commute. $\square$

**Corollary 3.5.** There is no weak $\iota$-lifting (let alone weak liftings) of $\lambda^{\mathbf{P}/\mathbf{P}}$ to $KHaus$, $JSL$ or $Conv$.

*Proof.*

* Given a compact Hausdorff space seen as a $\beta$-algebra $(A, a)$, $\overline{\mathbb{P}}\overline{\mathbb{P}}A$ is the set of all closed sets (in the Vietoris topology) of closed sets of $(A, a)$. $\{A\}$ is such a closed set of closed sets (all singletons and the whole set are always closed in a compact Hausdorff space) but $\mathbf{P}_*A$ is not in general because it contains all non-empty sets, in particular non-closed sets if there are any (which is the case of the unit interval, for instance).

* Consider a $\mathbf{P}$-algebra $(A, a)$, i.e. a complete join-semilattice where $a: \mathbf{P}A \to A$ computes the join of a subset. Then $\overline{\mathbb{P}}\overline{\mathbb{P}}A$ is the set of all non-empty-joins-closed sets of non-empty-joins-closed subsets of $A$. $\{A\}$ is such a non-empty-joins-closed set of non-empty-joins-closed subsets, but $\mathbf{P}_*A$ is not in general because it contains all non-empty sets, in particular non-join-closed subsets if there are any (which is the case of $(\mathbf{P}2, \cup)$ for instance).

* Consider a $\mathbf{D}$-algebra $(A, a)$, i.e. a barycentric algebra where $a: \mathbf{D}A \to A$ computes convex combinations of elements. Then $\overline{\mathbb{P}}\overline{\mathbb{P}}A$ is the set of all convex sets of convex subsets of $A$. $\{A\}$ is such a convex set of convex subsets, but $\mathbf{P}_*A$ is not in general because it contains all non-empty sets, in particular non-convex subsets if there are any (which is the case of $\mathbf{D}2$ for instance). $\square$

**Remark 3.6.** It is not hard to show that the Yang-Baxter equation holding for $\rho: \mathbf{TS} \Rightarrow \mathbf{ST}$, $\sigma: \mathbf{TR} \Rightarrow \mathbf{RT}$ and $\tau: \mathbf{SR} \Rightarrow \mathbf{RS}$ is also equivalent to $\rho: \mathbf{TS} \Rightarrow \mathbf{ST}$ having an extension $\rho: \underline{\mathbf{TS}} \Rightarrow \underline{\mathbf{ST}}$ to $\mathbf{KI}(\mathbf{R})$. In the case of $\lambda^{\beta/\mathbf{P}}: \beta\mathbf{P} \Rightarrow \mathbf{P}\beta$, $\beta$ is in fact a lax monad on $\mathbf{Rel}$ whose algebras are the topological spaces [Bar70]. Unfortunately, we have just shown that the Yang-Baxter equation does not hold for $\lambda^{\beta/\mathbf{P}}: \beta\mathbf{P} \Rightarrow \mathbf{P}\beta$, $\lambda^{\mathbf{P}/\mathbf{P}}: \mathbf{PP} \Rightarrow \mathbf{PP}$ and $\lambda^{\mathbf{P}/\mathbf{P}}: \mathbf{PP} \Rightarrow \mathbf{PP}$, and so do not get a way to weakly lift $\underline{\mathbf{P}}$ to topological spaces for free.

Theorem 3.3 does have some concrete instances: in [Goy23], Goy gives a substantial number of examples of triples of weak distributive laws for which the Yang-Baxter equation holds, although these examples all involve at least one strictly distributive law out of the three.

**3.2. The $\pi$-Yang-Baxter Equation.** We still do not have an explanation for why $\lambda^{\mathbf{V}/\mathbf{V}}$ looks so much like $\lambda^{\mathbf{P}/\mathbf{P}}$. But $\lambda^{\mathbf{V}/\mathbf{V}}$ being a weak lifting of $\lambda^{\mathbf{P}/\mathbf{P}}$ is not a necessary condition for retrieving Lemma 3.1: in fact, $\lambda^{\mathbf{V}/\mathbf{V}}$ being only a weak $\iota$- or $\pi$-lifting of $\lambda^{\mathbf{P}/\mathbf{P}}$ would be enough. We saw in Corollary 3.5 that the weak $\iota$-lifting hypothesis was a dead-end: how about $\lambda^{\mathbf{V}/\mathbf{V}}$ being a weak $\pi$-lifting of $\lambda^{\mathbf{P}/\mathbf{P}}$? This turns out to be true, although the proof is of course more involved than that of the weaker Lemma 3.1.
**Lemma 3.7.** $\lambda^{V/V}:VV \Rightarrow VV$ is a weak $\pi$-lifting of $\lambda^{P/P}:PP \Rightarrow PP$.

*Proof.* We want to show that Diagram (15) commutes, i.e. that for any compact Hausdorff space $X$ and $E \in \mathbf{PPU}^{\beta}X$ we have that the two sets

$$ \{\bar{e} \mid e \subseteq \bigcup E \text{ and } \forall e' \in E, e \cap e' \neq \emptyset\} \qquad (3.1) $$

and

$$ \{c \in \mathbf{V}X \mid c \subseteq \bigcup \overline{\{\bar{e} \mid e \in E\}} \text{ and } \forall c' \in \overline{\{\bar{e} \mid e \in E\}}, c \cap c' \neq \emptyset\} \qquad (3.2) $$

are equal.

Notice first that, since $\mu^V$ is a weak $\pi$-lifting of $\mu^P$, we have that $\bigcup \overline{\{\bar{e} \mid e \in E\}} = \bigcup E$.

(3.1) $\subseteq$ (3.2): Consider some $e \subseteq \bigcup E$ such that for every $e' \in E$, $e \cap e' \neq \emptyset$. Then $\bar{e} \subseteq \bigcup E = \bigcup \overline{\{\bar{e} \mid e \in E\}}$. Consider now some $c \in \overline{\{\bar{e} \mid e \in E\}}$. If $c \cap \bar{e} = \emptyset$, then $c$ is in the open $\square \bar{e}^c$. Hence there must be some $\bar{e}'$ with $e' \in E$ in this open as well, i.e. such that $e' \cap \bar{e} = \emptyset$ and thus $e' \cap e = \emptyset$. Such an $e'$ does not exist by assumption, hence $\bar{e} \cap c \neq \emptyset$.

Hence every element of $\{\bar{e} \mid e \subseteq \bigcup E \text{ and } \forall e' \in E, e \cap e' \neq \emptyset\}$ is contained in (3.2). Because this latter set is closed in $\mathbf{V}VX$, it follows that (3.1) $\subseteq$ (3.2).

(3.2) $\subseteq$ (3.1): Consider some $c \in (3.2)$, i.e. some $c \in \mathbf{V}X$ such that $c \subseteq \bigcup E$ and such that for every $c' \in \overline{\{\bar{e} \mid e \in E\}}$, $c \cap c' \neq \emptyset$. Let $\square u_0 \cap \bigcap_{i=1}^n \Diamond u_i$ be a basic open set of $\mathbf{V}X$ that contains $c$.

Then $c \subseteq u_0$, so by regularity (see for instance [GPA21, Lemma 21]) and compactness of $X$ there is an open set $u'_0$ of $X$ such that $c \subseteq u'_0$ and $\overline{u'_0} \subseteq u_0$. Consider the set $e = \bigcup E \cap u'_0$. Then $e \subseteq u_0$, and for every $e' \in E$, $c \cap \overline{e'} \neq \emptyset$ hence $u'_0 \cap \overline{e'} \neq \emptyset$ and thus $u'_0 \cap e' \neq \emptyset$ (because $u'_0$ is open). And of course since $e' \subseteq \bigcup E$, $u'_0 \cap e' \subseteq e \cap e' \neq \emptyset$.

Moreover for every $1 \le i \le n$, $u_i \cap c \neq \emptyset$ and $c \subseteq u'_0$ hence $(u_i \cap u'_0) \cap c \neq \emptyset$. Since $c \subseteq \bigcup E$, $(u_i \cap u'_0) \cap \bigcup E \neq \emptyset$ and thus $(u_i \cap u'_0) \cap \bigcup E \neq \emptyset$ ($u_i \cap u'_0$ is open). We have just showed that $e \cap u_i \neq \emptyset$ so that $\bar{e} \cap u_i \neq \emptyset$, and of course $\bar{e} \subseteq \overline{u'_0} \subseteq u_0$: $\bar{e} \in \square u_0 \cap \bigcap_{i=1}^n \Diamond u_i$.

This shows that $c$ is in the closure of $\{\bar{e} \mid e \subseteq \bigcup E \text{ and } \forall e' \in E, e \cap e' \neq \emptyset\}$, hence in (3.1). $\square$

Theorem 3.3 adapts to weak $\pi$-liftings, hence we immediately retrieve as a consequence of Lemma 3.7 that $\lambda^{V/V}:VV \Rightarrow VV$ is a weak distributive law.

**Proposition 3.8.** *Weak distributive laws $\rho$: TS $\Rightarrow$ ST, $\sigma$: TR $\Rightarrow$ RT and $\tau$: SR $\Rightarrow$ RS satisfy the $\pi$-Yang-Baxter equation, given by Diagram $(\pi$-YB), if and only if $\tau$: SR $\Rightarrow$ RS weakly $\pi$-lifts to $\mathbf{EM}(\mathbb{T})$, i.e. if there is a natural transformation $\bar{\tau}: \overline{\mathbf{SR}} \Rightarrow \overline{\mathbf{RS}}$ such that Diagram (15) commutes.*

<figure><img src="image_10.png" /></figure>

If this holds, $\bar{\tau}$ is a weak distributive law.
*Proof.* The proof is almost a copy-paste of that of Theorem 3.3.

We apply Theorem 2.11: recall that SR and RS have weak liftings $\overline{SR}$ and $\overline{RS}$ thanks to the laws $S\sigma \circ \rho R$ and $R\rho \circ \sigma S$. Then $\tau: SR \Rightarrow RS$ weakly $\pi$-lifts to $\mathbf{EM}(T)$ as $\tau: \overline{SR} \Rightarrow \overline{RS}$ if and only if the corresponding instance of Diagram (7) commutes: this is exactly Diagram $(\pi$-YB) (up to commuting of natural transformations). Because the correspondence is functorial, it preserves any equation satisfied by $\tau$, $\eta^S$, $\eta^R$, $\mu^S$ and $\mu^R$ (they all weakly $\pi$-lift to $\mathbf{EM}(T))$: since $\tau$ is a weak distributive law, so is $\tau$. $\square$

We also retrieve that $\lambda^{\mathbf{V}/\mathbf{V}}$ is a monotone weak distributive law:

**Proposition 3.9.** Consider a monotone weak distributive law $\lambda^{S/P}: \mathbf{SP} \Rightarrow \mathbf{PS}$ in Set that has a weak $\pi$-lifting to $\mathbf{EM}(T)$. If the components of $\kappa_{\mathbf{P}}: \mathbf{PU}^\mathbf{T} \Rightarrow \mathbf{PU}^\mathbf{T}$ are monotone functions (they preserve inclusion of subsets) then $\lambda^{S/P}: \overline{\mathbf{SP}} \Rightarrow \overline{\mathbf{PS}}$ is also a monotone weak distributive law.

*Proof.* Recall that morphisms $X \dashrightarrow Y$ in $\mathbf{KI}(\mathbf{P})$ correspond to functions $X \to \mathbf{PY}$, so that $f,g: X \to \mathbf{PY}$ are such that $f \leq g$ if and only if $f(x) \subseteq g(x)$ for every $x \in X$. The extension of the functor $S$ to $\mathbf{KI}(\mathbf{P})$ then sends a morphism $X \dashrightarrow Y$ given by the function $f: X \to \mathbf{PY}$ to the morphism $SX \dashrightarrow SY$ given by the composite $SX \xrightarrow{Sf} SPY \xrightarrow{\lambda^{S/P}} \mathbf{PSY}$. That $\lambda^{S/P}$ is a monotone law means that this extension is monotone, i.e. that if $f \leq g$ then $\lambda^{S/P} \circ Sf \leq \lambda^{S/P} \circ Sg$.

Similarly, morphisms $X \dashrightarrow Y$ in $\mathbf{KI}(\overline{\mathbf{P}})$ correspond to $\mathbf{T}$-algebra morphisms $f: X \to \overline{\mathbf{PY}}$, and the morphisms $X \dashrightarrow Y$ can be ordered by saying that $f \leq g: X \to \overline{\mathbf{PY}}$ if and only if $(\iota_{\mathbf{P}})_Y \circ \mathbf{U}^{\mathbf{T}} f \leq (\iota_{\mathbf{P}})_Y \circ \mathbf{U}^{\mathbf{T}} g$. The extension of the functor $\overline{S}$ to $\mathbf{KI}(\overline{\mathbf{P}})$ sends a morphism $X \dashrightarrow Y$ given by a $\mathbf{T}$-algebra morphism $f: X \to \overline{\mathbf{PY}}$ to the morphism $\overline{SX} \dashrightarrow \overline{SY}$ given by the composite $\overline{SX} \xrightarrow{\overline{Sf}} \overline{\mathbf{SPY}} \xrightarrow{\overline{\lambda^{S/P}}} \overline{\mathbf{PSY}}$.

We now show that this extension is monotone. Consider $f,g: X \to \overline{\mathbf{PY}}$ in $\mathbf{EM}(T)$ such that $((\iota_{\mathbf{P}})_Y \circ \mathbf{U}^{\mathbf{T}} f)(x) \subseteq ((\iota_{\mathbf{P}})_Y \circ \mathbf{U}^{\mathbf{T}} g)(x)$ for every $x \in \mathbf{U}^{\mathbf{T}}X$. Then by monotonicity of $\lambda^{S/P}$,

$$ (\lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} f) (E') \subseteq (\lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} g) (E') $$

for every $E' \in \mathbf{U}^{\mathbf{T}}\overline{\mathbf{P}}X$. It follows that

$$ (\mathbf{P}(\pi_S)_Y \circ \lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} f \circ (\iota_{\mathbf{P}})_X) (E) \subseteq (\mathbf{P}(\pi_S)_Y \circ \lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} g \circ (\iota_{\mathbf{P}})_X) (E) $$

for every $E \in \mathbf{PU}^{\mathbf{T}}X$, and finally by monotonicity of $\kappa_{\mathbf{P}}S$ that

$$ (\kappa_{\mathbf{P}})_{\overline{S}Y} \circ \mathbf{P}(\pi_S)_Y \circ \lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} f \circ (\iota_{\mathbf{P}})_X \leq (\kappa_{\mathbf{P}})_{\overline{S}Y} \circ \mathbf{P}(\pi_S)_Y \circ \lambda^{S/P} \circ S(\iota_{\mathbf{P}})_Y \circ \mathbf{SU}^{\mathbf{T}} g \circ (\iota_{\mathbf{P}})_X $$

Because $\iota_{\mathbf{P}}$ is a natural transformation and because $\overline{\lambda^{S/P}}$ is a weak $\pi$-lifting of $\lambda^{S/P}$, this inequality can be rewritten as

$$ (\iota_{\mathbf{P}})_{\overline{S}Y} \circ \mathbf{U}^{\mathbf{T}} (\overline{\lambda^{S/P}} \circ \overline{S}f) \leq (\iota_{\mathbf{P}})_{\overline{S}Y} \circ \mathbf{U}^{\mathbf{T}} (\overline{\lambda^{S/P}} \circ \overline{S}f) $$

so that the extension of $\overline{S}$ to $\mathbf{KI}(\overline{\mathbf{P}})$ is monotone. $\square$

Of course the point of Propositions 3.8 and 3.9 is that they make it easier to exhibit weak distributive laws in categories of algebras. Still, working with Diagram $(\pi$-YB) may be quite tedious, as it involves up to four composed layers of functors. In fact in Lemma 3.7 we did not use this $\pi$-Yang-Baxter equation at all, instead we directly proved that $\lambda^{\mathbf{V}/\mathbf{V}}$ was a
weak $\pi$-lifting because we were already able to take for granted that its components were morphisms of $\beta$-algebras, i.e. continuous functions. Another problem with Proposition 3.8 is that even if we manage to disprove its prerequisites for some examples, we only get that there is no weak $\pi$-lifting of the weak distributive law, but we do not learn anything about other possible meaningful weak distributive laws in the category of algebras.

For all of these reasons we do not try to apply Proposition 3.8 to weakly $\pi$-lift $\lambda^{\mathbf{P}/\mathbf{P}}: \mathbf{P}\mathbf{P} \Rightarrow \mathbf{P}\mathbf{P}$ to $\mathbf{EM}(\mathbf{P})$ and $\mathbf{EM}(\mathbf{D})$, and immediately turn towards another approach in Sections 4 and 5 instead: we try to weakly lift the conditions for the existence of monotone weak distributive laws (described in Section 2.2). This is a reasonable strategy because monotone laws are easier to reason about (all non-trivial weak distributive laws described in the literature are monotone) and are closer to being fully characterized, meaning we should hopefully be able to prove no-go theorems for monotone weak distributive laws. In fact we will prove that there is no such law $\overline{\mathbf{P}\mathbf{P}} \Rightarrow \overline{\mathbf{P}\mathbf{P}}$ in $\mathbf{EM}(\mathbf{P})$ or $\mathbf{EM}(\mathbf{D})$, so that by Proposition 3.9 $\lambda^{\mathbf{P}/\mathbf{P}}$ cannot weakly $\pi$-lift to $\mathbf{EM}(\mathbf{P})$ nor to $\mathbf{EM}(\mathbf{D})$.

### 4. KLEISLI CATEGORIES OF WEAKLY LIFTED MONADS

Let $\mathbf{T}$ be a monad on a regular category $\mathbf{C}$. It is folklore that, under mild conditions, $\mathbf{EM}(\mathbf{T})$ is regular as well. For instance on **Set**, all finitary monads, and even all monads if the axiom of choice is assumed to be true, have regular categories of algebras [Bor94b, Theorems 3.5.4 and 4.3.5]. Here we will assume that $\mathbf{T}$ is a nearly cartesian functor, but the following result also holds for monads that preserve reflexive coequalizers.

**Theorem 4.1** (categories of algebras are regular). Let $(\mathbf{T}, \eta^\mathbf{T}, \mu^\mathbf{T})$ be a monad on a regular category $\mathbf{C}$ such that $\mathbf{T}$ is nearly cartesian. Then $\mathbf{EM}_s(\mathbf{T})$ and $\mathbf{EM}(\mathbf{T})$ are regular, and $\mathbf{U}_s^\mathbf{T}$ and $\mathbf{U}^\mathbf{T}$ create finite limits, regular epimorphisms and near pullbacks$^4$.

*Proof*. We prove the result for $\mathbf{EM}(\mathbf{T})$ and $\mathbf{U}^\mathbf{T}$. The proof for $\mathbf{EM}_s(\mathbf{T})$ and $\mathbf{U}_s^\mathbf{T}$ is the same, with the only difference that we only need to show that (co)limits of semi-algebras are semi-algebras. This works because proving associativity for a (co)limit of a diagram $\mathbf{D}$ only relies on associativity of the algebras in $\mathbf{D}$, not on their unit axiom.

By [ML78, Exercise V.2.2] $\mathbf{U}^\mathbf{T}$ creates the limits that $\mathbf{C}$ has.

We now prove that $\mathbf{EM}(\mathbf{T})$ has coequalizers of kernel pairs. Consider the kernel pair $u, v: (P, p) \to (X, x)$ of a $\mathbf{T}$-algebra morphism $f: (X, x) \to (Y, y)$. Because $\mathbf{U}^\mathbf{T}$ preserves pullbacks, $\mathbf{U}^\mathbf{T}u, \mathbf{U}^\mathbf{T}v: P \to X$ is the kernel pair of $\mathbf{U}^\mathbf{T}f$: let $e: X \to Q$ be its coequalizer.

**Te is the coequalizer of Tu, Tv: TP $\Rightarrow$ TX:** Because $e \circ u = e \circ v$ is a pullback, the square $Te \circ Tu = Te \circ Tv$ is nearly cartesian: writing $u', v': P' \to TX$ for the kernel pair of $Te$, there is a regular epimorphism $e': TP \to P'$ such that $u' \circ e' = Tu$ and $v' \circ e' = Tv$. Suppose now $g: TX \to TZ$ is such that $g \circ Tu = g \circ Tv$. Then because $e'$ is an epimorphism, $g \circ u' = g \circ v'$ and $g$ factors uniquely through the coequalizer of $(u', v')$, i.e. Te because Te is a regular epimorphism hence the coequalizer of its kernel pair.

**The algebra structure on Q:** Consider now the composite $TX \xrightarrow{x} X \xrightarrow{e} Q$. It satisfies $e \circ x \circ Tu = e \circ u \circ p = e \circ v \circ p = e \circ x \circ Tv$, so it factors through the coequalizer $Te$ of

<footnote>$^4$meaning a cone (resp. arrow, resp. square) is limiting (resp. a regular epimorphism, resp. a near pullback) if and only if its image by $\mathbf{U}_s^\mathbf{T}$ or $\mathbf{U}^\mathbf{T}$ is.</footnote>
Tu and Tv. We let $q: TQ \to Q$ be the corresponding colimiting arrow, which satisfies $q \circ Te = e \circ x$ by definition. Now $(Q, q)$ is in fact an algebra:

$$ 
\begin{align*}
q \circ \eta_Q^T \circ e &= q \circ Te \circ \eta_X^T & q \circ \mu_Q^T \circ TTe &= q \circ Te \circ \mu_X^T \\
&= e \circ x \circ \eta_X^T & &= e \circ x \circ \mu_X^T \\
&= e & &= e \circ x \circ Tx \\
& & &= q \circ Te \circ Tx \\
& & &= q \circ Tq \circ TTe
\end{align*}
$$

hence $q \circ \eta_Q^T = \mathrm{id}_Q$ and $q \circ \mu_Q^T = q \circ Tq$ because $e$ and $TTe$ are epimorphisms.

e is a morphism of algebras: By construction, $q \circ Te = e \circ x$.

e: $(X, x) \to (Q, q)$ is the coequalizer of $u, v: (P, p) \to (X, x)$ in EM(T): Consider some morphism of T-algebras $g: (X, x) \to (A, a)$ such that $g \circ u = g \circ v$. Then $U^T g \circ U^T u = U^T g \circ U^T v$ in C, hence $U^T g$ factors as $h \circ e$ for some $h: Q \to A$. We now show that $h$ is in fact a T-algebra morphism $(Q, q) \to (A, a)$:

$$ h \circ q \circ Te = h \circ e \circ x = g \circ x = a \circ Tg = a \circ Th \circ Te $$

Because $Te$ is an epimorphism, $h \circ q = a \circ Th$.

By construction, e is a regular epimorphism in EM(T) if and only if $U^Te$ is so in C, hence $U^T$ creates regular epimorphisms. The creation of pullbacks and regular epimorphisms implies the creation of near pullbacks. $\square$

Consider weak distributive laws $\rho$: TS $\Rightarrow$ ST, $\sigma$: TR $\Rightarrow$ RT and $\tau$: SR $\Rightarrow$ RS on C. Note that because C is a regular category, idempotents split in C by way of the factorization into regular epimorphisms followed by monomorphisms: in particular, all the weak composites and weak liftings corresponding to these weak distributive laws exist. When $\tau$: SR $\Rightarrow$ RS is a monotone weak distributive law thanks to the framework of [GPA21], it is now natural to ask when there is also a monotone weak distributive law $\overline{SR} \Rightarrow \overline{RS}$ in EM(T) arising in the same way: it is for instance the case for $T = \beta$ and $S = R = P$.

To apply the framework for monotone weak distributive laws of [GPA21] to monads $\overline{S}$ and $\overline{R}$, we need to characterize $KI(\overline{R})$ as a subcategory of relations – we do this in Section 4.1, and focus on the example of $R = P$ in Set in Section 4.2 – and then characterize when functors and natural transformations extend to these subcategories of relations – we do this in Section 4.3. We will then apply our results in Section 5.

Because we strive to be as general as possible, in the following the assumptions that we use vary from result to result. In the propositions and theorems we thus recall every time all the assumptions that are necessary.

**4.1. Kleisli Categories of Weakly Lifted Monads.** Let us forget about regular categories and internal relations for an instant and first describe the Kleisli categories of a weakly lifted monad $\overline{R}$ in terms of the Kleisli category of $R$ itself.

**Proposition 4.2.** Let $\sigma$: TR $\Rightarrow$ RT be a weak distributive law in a category C where idempotents split, so that $R$ has a weak lifting $\overline{R}$ to EM(T) and T a weak extension T to KI(R). Then KI($\overline{R}$)-arrows $(A, a) \dashv\dashv (B, b)$ are in one-to-one correspondence with
KI(R)-arrows $f: A \to B$ such that $f \circ F_R a = F_R b \circ \mathbb{T} f$:

<figure><img src="image_11.png" /></figure>

*Proof.* Let us first prove that the Kleisli category of the semi-lifted monad $\bar{\mathbb{R}}$ on $\mathbf{EM}_s(T)$ is described as:

* its objects are semi-T-algebras $(A, a)$, i.e. objects of $\mathbf{EM}_s(T)$;

* its arrows $(A, a) \to (B, b)$ are $KI(R)$-arrows $f: A \to B$ such that $f \circ F_R a = F_R b \circ \mathbb{T} f$.

Call directly the category described above $KI(\bar{\mathbb{R}})$. We will build the adjunction $\mathbf{EM}_s(T): \mathbb{F}_{\bar{\mathbb{R}}} \leftrightarrow \mathbb{U}_{\bar{\mathbb{R}}}:KI(\bar{\mathbb{R}})$, and, since $\mathbb{F}_{\bar{\mathbb{R}}}$ will be bijective on objects, it will immediately follow that $KI(\bar{\mathbb{R}})$ is indeed the Kleisli category of $\bar{\mathbb{R}}$.

We let $\mathbb{F}_{\bar{\mathbb{R}}}: \mathbf{EM}_s(T) \to KI(\bar{\mathbb{R}})$ be the functor that sends semi-T-algebras on themselves and semi-T-algebra morphisms $f: (A, a) \to (B, b)$ to the $KI(R)$-arrow $\mathbb{F}_R U_s^T f: A \to B$. We indeed have that $\mathbb{F}_R U_s^T f \circ \mathbb{F}_R a = \mathbb{F}_R b \circ \mathbb{T} \mathbb{F}_R U_s^T f$ because $\mathbb{T}$ is an extension of the endofunctor $\mathbb{T}$ ($\mathbb{T} \mathbb{F}_R = \mathbb{F}_R \mathbb{T}$), $f$ is a semi-T-algebra morphism and $\mathbb{F}_R$ is a functor.

We let $\mathbb{U}_{\bar{\mathbb{R}}}: KI(\bar{\mathbb{R}}) \to \mathbf{EM}_s(T)$ be the functor that sends a semi-T-algebra $(A, a)$ to the semi-T-algebra $\bar{\mathbb{R}}(A, a) = (\mathrm{RA}, \mathrm{Ra} \circ \sigma_A)$, and a $KI(\bar{\mathbb{R}})$-arrow $(A, a) \to (B, b)$ with underlying $KI(R)$-arrow $f: A \to B$ to the semi-T-algebra morphism $\bar{\mathbb{R}}(A, a) \to \bar{\mathbb{R}}(B, b)$ with underlying C-arrow $\mathbb{U}_R f: \mathrm{RA} \to \mathrm{RB}$. To prove that this is indeed a morphism of semi-T-algebras, apply $\mathbb{U}_R$ to the equality $f \circ \mathbb{F}_R a = \mathbb{F}_R b \circ \mathbb{T} f$, recall that $\sigma = \mathbb{U}_R \mathbb{T} \varepsilon^R \mathbb{F}_R \circ \eta^R \mathrm{TR}$, and use the naturality of $\varepsilon^R$: $\mathbb{F}_R \mathbb{U}_R \Rightarrow \mathrm{Id}$ and $\eta^R: \mathrm{Id} \Rightarrow \mathrm{R}$:

$$ \begin{align*} \mathbb{U}_R f \circ \mathrm{Ra} \circ \sigma_A &= \mathrm{Rb} \circ \mathbb{U}_R \mathbb{T} f \circ \sigma_A \\ &= \mathrm{Rb} \circ \mathbb{U}_R \mathbb{T} f \circ \mathbb{U}_R \mathbb{T} \varepsilon^R_{\mathbb{F}_R A} \circ \eta^R_{\mathrm{TRA}} \\ &= \mathrm{Rb} \circ \mathbb{U}_R \mathbb{T} \varepsilon^R_{\mathbb{F}_R B} \circ \mathbb{U}_R \mathbb{T} \mathbb{F}_R \mathbb{U}_R f \circ \eta^R_{\mathrm{TRA}} \\ &= \mathrm{Rb} \circ \mathbb{U}_R \mathbb{T} \varepsilon^R_{\mathbb{F}_R B} \circ \mathrm{RT} \mathbb{U}_R f \circ \eta^R_{\mathrm{TRA}} \\ &= \mathrm{Rb} \circ \mathbb{U}_R \mathbb{T} \varepsilon^R_{\mathbb{F}_R B} \circ \eta^R_{\mathrm{TRB}} \circ \mathbb{T} \mathbb{U}_R f \\ &= \mathrm{Rb} \circ \sigma_B \circ \mathbb{T} \mathbb{U}_R f \end{align*} $$

Notice that $\mathbb{U}_{\bar{\mathbb{R}}} \mathbb{F}_{\bar{\mathbb{R}}} = \bar{\mathbb{R}}$. For the unit of the adjunction, we of course take the unit $\eta^{\bar{\mathbb{R}}}$ of the monad $\bar{\mathbb{R}}$. We define the counit $\varepsilon^{\bar{\mathbb{R}}}: \mathbb{F}_{\bar{\mathbb{R}}} \mathbb{U}_{\bar{\mathbb{R}}} \Rightarrow \mathrm{Id}$ by letting $\varepsilon^{\bar{\mathbb{R}}}_{\mathbb{F}_{\bar{\mathbb{R}}}(A,a)}: (\mathrm{RA}, \mathrm{Ra} \circ \sigma_A) \to (A, a)$ be the $KI(\bar{\mathbb{R}})$-arrow with underlying $KI(R)$-arrow $\varepsilon^R_{\mathbb{F}_R A}: \mathbb{F}_R \mathrm{RA} \to \mathbb{F}_R A$: using the naturality of $\varepsilon^R$, that $\sigma = \mathbb{U}_R \mathbb{T} \varepsilon^R \mathbb{F}_R \circ \eta^R \mathrm{TR}$ and that $\mathbb{F}_R \dashv \mathbb{U}_R$ is an adjunction, we get

$$ \begin{align*} \varepsilon^R_{\mathbb{F}_R A} \circ \mathbb{F}_R Ra \circ \mathbb{F}_R \sigma_A &= \mathbb{F}_R a \circ \varepsilon^R_{\mathbb{T} \mathbb{F}_R A} \circ \mathbb{F}_R \sigma_A \\ &= \mathbb{F}_R a \circ \varepsilon^R_{\mathbb{T} \mathbb{F}_R A} \circ \mathbb{F}_R \mathbb{U}_R \mathbb{T} \varepsilon^R_{\mathbb{F}_R A} \circ \mathbb{F}_R \eta^R_{\mathrm{TRA}} \\ &= \mathbb{F}_R a \circ \mathbb{T} \varepsilon^R_{\mathbb{F}_R A} \circ \varepsilon^R_{\mathbb{F}_R \mathrm{TRA}} \circ \mathbb{F}_R \eta^R_{\mathrm{TRA}} \\ &= \mathbb{F}_R a \circ \mathbb{T} \varepsilon^R_{\mathbb{F}_R A} \end{align*} $$
The obvious forgetful functor $U_s^T: \text{KI}(\ddot{\mathbb{R}}) \to \text{KI}(\mathbb{R})$ is such that $U_s^T \varepsilon^{\ddot{\mathbb{R}}} = \varepsilon^R U_s^T$ and it is
faithful, hence $\varepsilon^{\ddot{\mathbb{R}}}$ is indeed natural because $\varepsilon^R$ is. In fact we get the four equalities

$$
U_s^T \mathbf{F}_{\mathbb{R}} = \mathbf{F}_R U_s^T \qquad U_s^T \mathbf{U}_{\mathbb{R}} = \mathbf{U}_R U_s^T \qquad U_s^T \varepsilon^{\mathbb{R}} = \varepsilon^R U_s^T \qquad U_s^T \eta^{\mathbb{R}} = \eta^R U_s^T
$$

so by faithfulness of $U_s^T$ and $U_s^T$ again we immediately get that $U_{\mathbb{R}} \varepsilon^{\mathbb{R}} \circ \eta^{\mathbb{R}} U_{\mathbb{R}} = \text{id}$ and
$\varepsilon^{\mathbb{R}} \mathbf{F}_{\mathbb{R}} \circ \mathbf{F}_{\mathbb{R}} \circ \eta^{\mathbb{R}} = \text{id}$ from the corresponding equalities for $\eta^R$ and $\varepsilon^R$: $(\mathbf{F}_{\mathbb{R}}, \mathbf{U}_{\mathbb{R}}, \eta^{\mathbb{R}}, \varepsilon^{\mathbb{R}})$ is
indeed an adjunction, and $(U_s^T, U_s^T)$ in fact form a morphism of adjunctions. Another way
to see this is that not only does the monad $\mathbb{R}$ semi-lift to $\mathbf{EM}_s(\mathbb{T})$, but its Kleisli adjunction
does as well.

We similarly deduce that the monad arising from this semi-lifted Kleisli adjunction is
indeed (R̄, η̄R, μ̄R), and so because F_R̄ is bijective on objects, we have indeed just described
the Kleisli category of R̄.

Finally, recall that we get the weakly lifted monad $\bar{\mathbb{R}}$ by composing the adjunction
$I^T \to K^T$ with any adjunction for the monad $\bar{\mathbb{R}}$. We can in particular use the Kleisli adjunction
for $\bar{\mathbb{R}}$: the adjunction $\mathbf{F}_{\bar{\mathbb{R}}} I^T: \mathbf{EM}(\bar{\mathbb{R}}) \hookrightarrow \mathbf{KI}(\bar{\mathbb{R}}): K^T \mathbf{U}_{\bar{\mathbb{R}}}$ has for corresponding monad $\bar{\mathbb{R}}$. In
particular, we now retrieve the Kleisli category of $\bar{\mathbb{R}}$ as the full subcategory of $\mathbf{KI}(\bar{\mathbb{R}})$ on
objects which are images by the left adjoint of objects of $\mathbf{EM}(\bar{\mathbb{T}})$: this is exactly the category
described in the statement of Proposition 4.2.
□

Assume now that the framework of [GPA21] applies:

• $\mathbb{R}$ is a sub-power-object monad on $\mathbb{C}$; (Definition 2.8)

• T and μ^T are nearly cartesian;

* the weak extension of (T, η^T, μ^T) to KI(R) is the restriction of the relational extension of
T and μ^T to Rel(C).

It then follows from Proposition 4.2 that $\mathrm{KI}(\bar{\mathbb{R}})$ has certain $\mathbb{C}$-relations for morphisms: $\mathrm{KI}(\bar{\mathbb{R}})$-morphisms $(A, a) \dashv\dashv\dashv (B, b)$ correspond to $\mathbb{C}$-relations $\psi: A \rightsquigarrow B$ that are in $\mathrm{KI}(\mathbb{R})$ and such that $\psi \cdot a = b \cdot T\psi$:

$$
\begin{tikzcd}
TA \arrow[r, "T^\psi"] \arrow[d, "a"] & TB \arrow[d, "b"'] \\
A \arrow[r, "\psi"] & B
\end{tikzcd}
$$

Moreover, by Theorems 2.7 and 4.1, $\mathbf{U}^T$ has a relational extension $\mathbf{Rel}(\mathbf{U}^T): \mathbf{Rel}(\mathbf{EM}(\mathbb{T})) \to \mathbf{Rel}(\mathbf{C})$, and $\mathbf{EM}(\mathbb{T})$-relations also correspond to certain $\mathbb{C}$-relations:

**Lemma 4.3.** When the endofunctor $\mathbb{T}$ is nearly cartesian, a $\mathbb{C}$-relation $\psi: A \rightsquigarrow B$ is the image of an $\mathbf{EM}(\mathbb{T})$-relation $(A, a) \rightsquigarrow (B, b)$ by the faithful functor $\mathbf{Rel}(\mathbf{U}^T): \mathbf{Rel}(\mathbf{EM}(\mathbb{T})) \to \mathbf{Rel}(\mathbf{C})$ if and only if $\psi \cdot a \ge b \cdot T\psi$:

$$
\begin{tikzcd}
TA \arrow[r, "T^\psi"] \arrow[d, "a"] & TB \arrow[d, "b"'] \\
A \arrow[r, "\psi"] & B
\end{tikzcd}
$$

*Proof.* Recall [CKW91, Proposition 1.8]: consider $\mathbb{C}$-arrows $f: C \to A$ and $g: D \to B$ and $\mathbb{C}$-relations $\phi: C \rightsquigarrow D$ and $\psi: A \rightsquigarrow B$ respectively given by the jointly monic spans
⟨φ_C, φ_D⟩: S ↪ C × D and ⟨ψ_A, ψ_B⟩: R ↪ A × B. Then, g · φ ≤ ψ · f if and only if there is a
necessarily unique t: S → R such that ψ_A ∘ t = f ∘ φ_C and ψ_B ∘ t = g ∘ φ_D:

<figure><img src="image_12.png" /></figure>

Consider now an **EM(T)**-relation $\psi: (A, a) \rightsquigarrow (B, b)$, given by a jointly monic span $\langle \psi_{(A,a)}, \psi_{(B,b)} \rangle: (R, r) \hookrightarrow (A, a) \times (B, b)$. Then, because **U**$^T$ preserves monomorphisms and products (it preserves all limits), $\langle \mathbf{U}^T\psi_{(A,a)}, \mathbf{U}^T\psi_{(B,b)} \rangle: R \hookrightarrow A \times B$ is a jointly monic span for the C-relation $\mathbf{U}^T\psi$. Factor $\langle \mathbf{TU}^T\psi_{(A,a)}, \mathbf{TU}^T\psi_{(B,b)} \rangle: \mathbf{TR} \hookrightarrow \mathbf{TA} \times \mathbf{TB}$ as $\mathbf{TR} \twoheadrightarrow S \hookrightarrow \mathbf{TA} \times \mathbf{TB}$, and call $e: \mathbf{TR} \twoheadrightarrow S$ the regular epimorphism in this factorization. Then $r$ factors through $e$ as well (in a regular category, regular epimorphisms are strong [CKW91, §1.3]), and because $e$ is an epimorphism, Diagrams (18) and (19) below commute.

<figure><img src="image_13.png" /></figure>

By [CKW91, Proposition 1.8], we get that $\mathbf{U}^T\psi \cdot a \geq b \cdot \mathbf{TU}^T\psi$.

Conversely, consider a C-relation $\psi: A \rightsquigarrow B$ given by a jointly monic span $\langle \psi_A, \psi_B \rangle: R \hookrightarrow A \times B$ and such that $\psi \cdot a \geq b \cdot \tau\psi$. Factor $\langle \tau\psi_A, \tau\psi_B \rangle: \tau R \to \tau A \times \tau B$ as $\tau A \twoheadrightarrow S \hookrightarrow \tau A \times \tau B$, and call $e: \tau A \twoheadrightarrow S$ and $\phi = \langle \phi_{\tau A}, \phi_{\tau B} \rangle: S \hookrightarrow \tau A \times \tau B$ the regular epimorphism and monomorphism in this factorization. We then have the inequality:

<figure><img src="image_14.png" /></figure>
By [CKW91, Proposition 1.8], we get a C-arrow $t: S \to R$ such that $\psi_A \circ t = a \circ \phi_{TA}$ and $\psi_B \circ t = b \circ \phi_{TB}$. Let $r = t \circ e: TR \to R$. We now show that $(R, r)$ is a T-algebra, so that $\psi_A$ and $\psi_B$ are actually jointly monic T-algebra morphisms and $\psi$ is an EM(T)-relation:

$$ \begin{aligned} \psi \circ r \circ \eta_R^T &= \langle a \circ T\psi_A, b \circ T\psi_B \rangle \circ \eta_R^T && \psi \circ r \circ \mu_R^T = \langle a \circ T\psi_A, b \circ T\psi_B \rangle \circ \mu_R^T \\ &= \langle a \circ \eta_A^T \circ \psi_A, b \circ \eta_B^T \circ \psi_B \rangle &&= \langle a \circ \mu_A \circ TT\psi_A, b \circ \mu_B^T \circ TT\psi_B \rangle \\ &= \psi &&= \langle a \circ Ta \circ TT\psi_A, b \circ Tb \circ TT\psi_B \rangle \\ &= \langle a \circ T\psi_A \circ Tr, b \circ T\psi_B \circ Tr \rangle &&= \psi \circ r \circ Tr \end{aligned} $$

$(R, r)$ is thus indeed a T-algebra because $\psi$ is a monomorphism.

The correspondence between EM(T)- and C-relations we have just described is bijective because $U^T$ is faithful. $\square$

$\bar{R}$ is thus itself a sub-power-object monad on EM(T): an EM(T)-relation $(A, a) \rightsquigarrow (B, b)$, seen as a C-relation $\psi: A \rightsquigarrow B$ such that $\psi \cdot a \ge b \cdot T\psi$, is a $KI(\bar{R})$-morphism $(A, a) \dashrightarrow (B, b)$ if and only if this inequality is an equality.

We now describe in more concrete terms which EM(T)-relations are arrows in $KI(\bar{R})$. Decomposable T-algebra morphisms play a central role in this description:

**Definition 4.4** (decomposable morphisms of algebra). Let $T$ be a monad on a category $C$ such that EM(T) is regular. A T-algebra morphism $f: X \to Y$ is called decomposable when the square $f \circ \varepsilon_X^T = \varepsilon_Y^T \circ F^T U^T f$ is a near pullback:

$$ \begin{array}{ccc} F^T U^T X & \xrightarrow{F^T U^T f} & F^T U^T Y \\ \varepsilon_X^T & \underset{X}{\longleftarrow} & \underset{f}{\longleftarrow} \\ \varepsilon_Y^T & \underset{Y}{\longrightarrow} & \varepsilon_X^T \end{array} $$

Given a jointly monic span $\langle \psi_X, \psi_Y \rangle$ in EM(T), the corresponding relation $\psi = \psi_Y \cdot \psi_X^\dagger$ is called decomposable when $\psi_X$ is so.

Decomposable morphisms have been studied in [CCT14, Definition 3.1.1] in the setting of *monoidal topology*. There, these morphisms are called *open* as they generalize open maps between compact Hausdorff spaces, as the next example shows. We prefer the term “decomposable” here as we focus on other examples that feel more algebraic than topological:

**Example 4.5** (decomposable morphisms and relations in categories of algebras over Set).

(1) In EM(β) ≅ KHaus, a continuous map is decomposable if and only if it is open (it preserves open sets), and decomposable relations are the continuous ones, i.e. those relations $\psi: X \rightsquigarrow Y$ such that $\psi^{-1}[u]$ is open in X for every open subset u of Y.

(2) In EM(P) ≅ JSL, $\psi: X \rightsquigarrow Y$ is decomposable if and only if for every family $(x_i)_{i \in I}$ of elements of X and every $y \in Y$ such that $(\bigvee_{i \in I} x_i, y) \in \psi$, there is a family $(y_i)_{i \in I}$ of elements of Y such that $(x_i, y_i) \in \psi$ for all $i \in I$ and $\bigvee_{i \in I} y_i = y$.

(3) In EM(D) ≅ Conv, $\psi: X \rightsquigarrow Y$ is decomposable if and only if for every $x \in X$, every disintegration of x as a barycenter $x = \sum_{i=1}^n \lambda_i x_i$ and every $y \in Y$ such that $(x, y) \in \psi$, y disintegrates as a barycenter $y = \sum_{i=1}^n \lambda_i y_i$ such that $(x_i, y_i) \in \psi$ for all $i \in I$.

The following lemma helps to see why the characterizations of Example 4.5 hold:
**Lemma 4.6.** If $\mathbf{U}^\top$ creates near pullbacks, a $\mathbf{T}$-morphism $f: (A, a) \to (B, b)$ is decomposable if and only if $\mathbf{U}^\top f \circ a = b \circ \mathbf{U}^\top f$ is a near pullback in $\mathbf{C}$:

$$ \begin{array}{ccc} \mathbf{T}A & \xrightarrow{\mathbf{T}f} & \mathbf{T}B \\ \bigdownarrow_a & & \bigdownarrow_b \\ A & \xrightarrow{f} & B \end{array} $$

In particular if $\mathbf{T}$ is a monad on $\mathbf{Set}$, this holds if and only if for every $x \in A$ and $u \in \mathbf{T}B$ such that $f(x) = b(u)$, there is some $t \in \mathbf{T}A$ such that $(\mathbf{T}f)(t) = u$ and $a(t) = x$.

*Proof.* $\mathbf{U}^\top$ creates near pullbacks hence $\mathbf{U}^\top f \circ \mathbf{U}^\top \varepsilon_{(A,a)}^\top = \mathbf{U}^\top \varepsilon_{(B,b)}^\top \circ \mathbf{U}^\top \mathbf{F}^\top \mathbf{U}^\top f$ is a near pullback in $\mathbf{C}$ if and only if $f \circ \varepsilon_{(A,a)}^\top = \varepsilon_{(B,b)}^\top \circ \mathbf{F}^\top \mathbf{U}^\top f$ is a near pullback in $\mathbf{EM}(\mathbf{T})$.

In $\mathbf{Set}$, regular epimorphisms are surjections hence $f \circ a = b \circ \mathbf{T}f$ is a near pullback if and only if the limiting function from $\mathbf{T}A$ to the pullback $A \times_B \mathbf{T}B$ is surjective, which translates to what is stated above. $\square$

*Proof of Example 4.5.* For decomposable relations, we use the characterization of decomposable relations from Theorem 4.8 below.

(1) This immediately follows from Theorem 4.8 and the description of $\mathbf{KI}(\mathbf{V})$ given in [GPA21]. But we can also recover this result by hand: by Lemma 4.6 above, a continuous map $f: X \to Y$ is a decomposable $\beta$-algebra morphism if and only if for every ultrafilter $E$ on $Y$ converging to $y \in Y$, and every $x \in f^{-1}(Y)$, there is an ultrafilter $E'$ on $X$ converging to $x$ and such that $E = \{e \supseteq f(e') \mid e' \in E'\}$.

* Suppose $f$ is decomposable and consider some $x \in X$ and some neighborhood $N$ of $x$: $N$ belongs to every ultrafilter converging to $x$. Consider some ultrafilter $E$ on $Y$ converging to $f(x)$. Then there is an ultrafilter $E'$ on $X$ converging to $x$ and such that $E = \{e \supseteq f(e') \mid e' \in E'\}$. By definition $N \in E'$, hence $f(N) \in E$. $f(N)$ is thus a neighborhood of $y$, and $f$ is open.

* Conversely, suppose that $f$ is open, so that if $N$ is a neighborhood of $x \in X$ then $f(N)$ is a neighborhood of $f(x)$. Fix $y \in Y$, $E$ converging to $y$ and $x \in f^{-1}(y)$. Let $F = \{e' \supseteq f^{-1}(e) \cap N \mid e \in E, N \in N(x)\}$ where $N(x)$ is the filter of neighborhoods of $x$. Then $F$ is a filter: it is non-empty because $X$ is a neighborhood of $x$ hence $F$ contains $X = f^{-1}(Y)$; it is stable under finite intersections because $E$ and $N(x)$ are; it is upwards-closed by definition; and it does not contain the empty set because every neighborhood $N$ of $x$ is such that $f(N)$ is a neighborhood of $f(x)$, i.e. $f(N) \in E$ and $f(N)$ intersects every $e \in E$.

Let $E'$ be any ultrafilter containing $F$. Then $E'$ converges to $x$ because it contains $N(x)$. Moreover $f^{-1}(e) \in E'$ for every $e \in E$, and conversely if $f^{-1}(e) \in E'$ then $f^{-1}(e^c) = f^{-1}(e)^c$ is not in $E'$ so that $e^c$ is not in $E$: because $E$ is an ultrafilter, either $e \in E$ or $e^c \in E$, so the former holds.

In other words, $E = (\beta f)(E')$ and $f$ is decomposable.

We could prove similarly by hand that decomposable relations are indeed the continuous ones.

(2) A relation $(A, \vee^A) \rightsquigarrow (B, \vee^B)$ in $\mathbf{JSL}$ given by some $\psi: A \rightsquigarrow B$ in $\mathbf{Set}$ is decomposable if and only if for every $a \in A$, $E \in \mathbf{PA}$ such that $a = \bigvee^A E$ and $b \in B$ such that $(a, b) \in \psi$, there is an $F \in \mathbf{PB}$ such that

$$ \forall a' \in E, \exists b' \in F, (a', b') \in \psi \text{ and } \forall b' \in F, \exists a' \in E, (a', b') \in \psi $$
and $\bigvee^B F = b$.

Consider some $E = \{a_i \mid i \in I\}$ so that $a = \bigvee_{i \in I} a_i$ and some $b \in B$ such that $(a, b) \in \psi$. Then if $\psi$ is decomposable, consider the corresponding $F \in \mathbf{PB}$ and write $F_i = \{b' \in F \mid (a_i, b') \in \psi\}$ and $b_i = \bigvee^B F_i$. By definition of $F$, every $F_i$ is non-empty and $\bigcup_{i \in I} F_i = F$, so that $\bigvee_{i \in I} b_i = \bigvee^B F = b$. Moreover $\psi \subseteq A \times B$ is a relation of join-semilattices and $(a_i, b') \in \psi$ for every $b' \in F_i$, hence $(a_i, b_i) = \bigvee_{b' \in F_i}^{A \times B} (a_i, b') \in \psi$ as well.

Conversely, if $\psi$ satisfies the stated property then if $\bigvee^A E = a$ and $(a, b) \in \psi$, $\bigvee_{e \in E}^A e = a$ so there is a family $(b_e)_{e \in E}$ of elements of $B$ such that $(e, b_e) \in \psi$ and $\bigvee_{e \in E}^B b_e = b$. Taking $F = \{b_e \mid e \in E\}$, we see that $\psi$ is decomposable.

(3) A relation $A \rightsquigarrow B$ in **Conv** given by some $\psi: A \rightsquigarrow B$ in **Set** is decomposable if and only if for every $a \in A$ given as $a = \sum_{i=1}^n \lambda_i a_i$ with $\sum_{i=1}^n \lambda_i = 1$, $\lambda_i \neq 0$ and $a_i \in A$ for every $1 \le i \le n$, and $b \in B$ such that $(a, b) \in \psi$, there are for every $1 \le i \le n$ some $m_i \ge 1$, $(\mu_{i,j})_{1 \le j \le m_i}$ such that $\sum_{j=1}^{m_i} \mu_{ij} = \lambda_i$ and $(b_{ij})_{1 \le j \le m_i}$ such that $(a_i, b_{ij}) \in \psi$ for all $1 \le j \le m_i$ and $\sum_{i=1}^n \sum_{j=1}^{m_i} \mu_{ij} b_{ij} = b$.

Suppose this holds. For every $1 \le i \le n$, let $b_i = \frac{1}{\lambda_i} \sum_{j=1}^{m_i} \mu_{ij} b_{ij}$. Then $\sum_{i=1}^n \lambda_i b_i = \sum_{i=1}^n \sum_{j=1}^{m_i} \mu_{ij} b_{ij} = b$, and for every $1 \le i \le n$, $(a_i, b_i) = \frac{1}{\lambda_i} \sum_{i=j}^{m_i} \mu_{ij} (a_i, b_{ij}) \in \psi$ because $\psi \subseteq A \times B$ is a relation of barycentric algebras.

Conversely, consider some $a = \sum_{i=1}^n \lambda_i a_i$ and $b$ such that $(a, b) \in \psi$ as above. If there is always some $(b_i)_{1 \le i \le n}$ such that $\sum_{i=1}^n \lambda_i b_i = b$ and $(a_i, b_i) \in \psi$, then taking $m_i = 1$, $\mu_{i1} = \lambda_i$ and $b_{i1} = b_i$ for every $1 \le i \le n$ shows that $\psi$ is decomposable. $\square$

A more general example of decomposable morphism is the following:

**Lemma 4.7.** When $\mathbf{U}^\mathbf{T}$ creates near pullbacks, $\mu^\mathbf{T}$ is nearly cartesian if and only if every free algebra morphism $\mathbf{F}^\mathbf{T}f: (\mathbf{T}X, \mu_X^\mathbf{T}) \to (\mathbf{T}Y, \mu_Y^\mathbf{T})$ with $f: X \to Y$ is decomposable.

*Proof.* $\mu^\mathbf{T}$ is nearly cartesian if and only if for every $f: X \to Y$ in $\mathbf{C}$, $\mu_Y^\mathbf{T} \circ \mathbf{T}Tf = \mathbf{T}f \circ \mu_X^\mathbf{T}$ is a near pullback. But $\mu^\mathbf{T} = \mathbf{U}^\mathbf{T}\varepsilon^\mathbf{T}\mathbf{F}^\mathbf{T}$, hence this holds if and only if for every such $f$, $\mathbf{U}^\mathbf{T}\varepsilon^\mathbf{T}_{\mathbf{F}^\mathbf{T}Y} \circ \mathbf{U}^\mathbf{T}\mathbf{F}^\mathbf{T}\mathbf{U}^\mathbf{T}\mathbf{F}^\mathbf{T}f = \mathbf{U}^\mathbf{T}\mathbf{F}^\mathbf{T}f \circ \mathbf{U}^\mathbf{T}\varepsilon^\mathbf{T}_{\mathbf{F}^\mathbf{T}X}$ is a near pullback, i.e. if and only if every such $\mathbf{F}^\mathbf{T}f$ is decomposable since $\mathbf{U}^\mathbf{T}$ creates near pullbacks. $\square$

We are now able to state the main result of this section. We first state it in full generality (Theorem 4.8), but in practice we will be especially concerned with the case $\mathbf{R} = \mathbf{P}$ on $\mathbf{C} = \mathbf{Set}$ (Corollary 4.9 in Section 4.2).

**Theorem 4.8.** Let $(\mathbf{T}, \eta^\mathbf{T}, \mu^\mathbf{T})$ be a monad on a regular category $\mathbf{C}$. When the endofunctor $\mathbf{T}$ is nearly cartesian, an $\mathbf{EM}(\mathbf{T})$-relation $\psi: (A, a) \rightsquigarrow (B, b)$ is decomposable if and only if $\mathbf{U}^\mathbf{T}\psi \cdot a = b \cdot \mathbf{U}\mathbf{U}^\mathbf{T}\psi$.

If $\mathbf{R}$ is a sub-power-object monad on $\mathbf{C}$ and $\mu^\mathbf{T}$ extends to $\mathbf{KI}(\mathbf{R})$ (for instance if $\mu^\mathbf{T}$ is also nearly cartesian), then the corresponding weakly lifted monad $\bar{\mathbf{R}}$ on $\mathbf{EM}(\mathbf{T})$ is a sub-power-object monad and its Kleisli category $\mathbf{KI}(\bar{\mathbf{R}})$ has for arrows $(A, a) \dashrightarrow (B, b)$ the decomposable relations $\psi: (A, a) \rightsquigarrow (B, b)$ in $\mathbf{EM}(\mathbf{T})$ such that $\mathbf{U}^\mathbf{T}\psi$ is in $\mathbf{KI}(\mathbf{R})$.

*Proof.* Consider some $\mathbf{EM}(\mathbf{T})$-relation $\psi: (A, a) \rightsquigarrow (B, b)$. By Lemma 4.3, it corresponds to the $\mathbf{C}$-relation $\mathbf{U}^\mathbf{T}\psi: A \rightsquigarrow B$, which satisfies $\mathbf{U}^\mathbf{T}\psi \cdot a \ge b \cdot \mathbf{U}\mathbf{U}^\mathbf{T}\psi$. By Proposition 4.2, $\psi$ is in $\mathbf{KI}(\bar{\mathbf{R}})$ if and only if we have moreover that $\mathbf{U}^\mathbf{T}\psi$ is in $\mathbf{KI}(\mathbf{R})$ and $\mathbf{U}^\mathbf{T}\psi \cdot a = b \cdot \mathbf{U}\mathbf{U}^\mathbf{T}\psi$. We now show that this last condition is equivalent to $\psi$ being decomposable.
If $\psi$ is decomposable, it is given by a jointly monic span $\langle\psi_{(A,a)}, \psi_{(B,b)}\rangle: (R, r) \hookrightarrow (A, a) \times (B, b)$ such that $\psi_{(A,a)}$ is a decomposable morphism. Writing $\psi_A = \mathbf{U}^\mathrm{T}\psi_{(A,a)}$ and $\psi_B = \mathbf{U}^\mathrm{T}\psi_{(B,b)}$, this means that $\psi_A \circ r = a \circ \mathrm{T}\psi_A$ is a near pullback in $\mathbf{C}$, or equivalently that $\psi_A^\dagger \cdot a = r \cdot (\mathrm{T}\psi_A)^\dagger$. But because $\psi_{(B,b)}$ is a morphism of $\mathrm{T}$-algebras, we also have that $\psi_B \cdot r = b \cdot \mathrm{T}\psi_B$, and so

$$ \begin{aligned} \mathbf{U}^{\mathrm{T}}\psi \cdot a &= \psi_B \cdot \psi_A^{\dagger} \cdot a \\ &= \psi_B \cdot r \cdot (\mathrm{T}\psi_A)^{\dagger} \\ &= b \cdot \mathrm{T}\psi_B \cdot (\mathrm{T}\psi_A)^{\dagger} \\ &= b \cdot \mathrm{T}\mathbf{U}^{\mathrm{T}}\psi \end{aligned} $$

Conversely, suppose that $\psi: (A, a) \rightsquigarrow (B, b)$ given by $\langle\psi_{(A,a)}, \psi_{(B,b)}\rangle: (R, r) \hookrightarrow (A, a) \times (B, b)$ is such that $\mathbf{U}^{\mathrm{T}}\psi \cdot a = b \cdot \mathrm{T}\mathbf{U}^{\mathrm{T}}\psi$. We now show that $\psi_A = \mathbf{U}^{\mathrm{T}}\psi_{(A,a)}$ is decomposable: consider the pullback

<figure><img src="image_15.png" /></figure>

To prove that $\psi_A$ is decomposable, we need to prove that $e: \mathrm{T}R \to P$ in the diagram above is a regular epimorphism. By definition of the composition of relations, $\psi_A^\dagger \cdot a = p_R \cdot p_{\mathrm{T}A}^\dagger$, so that $b \cdot \mathrm{T}\mathbf{U}^{\mathrm{T}}\psi = \mathbf{U}^{\mathrm{T}}\psi \cdot a = \psi_B \cdot p_R \cdot p_{\mathrm{T}A}^\dagger$. Factor $\langle p_{\mathrm{T}A}, \psi_B \circ p_R \rangle: P \to \mathrm{T}A \times B$ into the regular epimorphism $e': P \to P'$ and the jointly monic span $\langle p'_{\mathrm{T}A}, p'_B \rangle: P' \hookrightarrow \mathrm{T}A \times B$. Then $p'_B \cdot (p'_{\mathrm{T}A})^\dagger = \psi_B \cdot p_R \cdot p_{\mathrm{T}A}^\dagger = b \cdot \mathrm{T}\mathbf{U}^{\mathrm{T}}\psi = \psi_B \cdot r \cdot (\mathrm{T}\psi_A)^\dagger$, therefore $e' \circ e: \mathrm{T}R \to P'$, as in the diagram below, must be a regular epimorphism.

<figure><img src="image_16.png" /></figure>

We will now show that $e'$ is a monomorphism and thus an isomorphism, and it will follow that $e$ must be a regular epimorphism as well. We have the commuting diagram

$$ \begin{array}{ccc} P & \xrightarrow{e'} & P' \\ \langle p_{\mathrm{T}A}, p_R \rangle \Big\downarrow & & \langle p'_{\mathrm{T}A}, p'_B \rangle \Big\downarrow \\ \mathrm{T}A \times R & \xrightarrow{\mathrm{id}_{\mathrm{T}A} \times \langle \psi_A, \psi_B \rangle} & \mathrm{T}A \times A \times B \end{array} $$

where all the arrows except $e$ are monomorphisms: $e$ is also a monomorphism. $\square$

<figure><img src="image_17.png" /></figure>
**4.2. Decomposable Subobject Classifiers.** The foremost example of a sub-power-object monad is the powerset monad **P** on **Set**, for which **KI**(**P**) ≅ **Rel**. We may thus take **C** = **Set** and **R** = **P** in Theorem 4.8 above, and get:

**Corollary 4.9.** If T has a monotone weak distributive law over P in Set, the Kleisli category of the lifted powerset monad P on EM(T) is the category of T-algebras and decomposable relations between them.

More generally, this holds in any *elementary topos*. Recall that an elementary topos is a regular category *E* such that **Graph**<sub>*E*</sub>: *E* → **Rel**(*E*) has a right adjoint [FS90, §1.911]. The monad induced by this adjunction, also written **P**, is called the *power-object monad*, and is trivially a sub-power-object monad since **Graph**<sub>*E*</sub> factors as *E* <sup>*F*<sub>*P*</sub></sup>→ **KI**(**P**) ≅ **Rel**(*E*). The fact that **KI**(**P**) ≅ **Rel** in **Set** makes the latter an elementary topos.

In Theorem 4.8, we may thus take $\mathcal{C}$ to be an elementary topos and $\mathbb{R}$ to be its power-object monad, and, just as in Corollary 4.9, get:

**Corollary 4.10.** If T has a monotone weak distributive law over P in an elementary topos, the Kleisli category of the lifted power-object monad P on EM(T) is the category of T-algebras and decomposable relations between them.

Elementary topoï turn out to have a lot of structure: an elementary topos has finite limits, is cartesian-closed [FS90, 1.92] and has a *subobject classifier* [FS90, 1.912] – an object classifying all monomorphisms:

**Definition 4.11** (M-subobject classfier [Wyl91, Definition 14.1]). Let $\mathcal{C}$ be a regular category and $M \subseteq \mathbf{Mono}$ be a class of monomorphisms in $\mathcal{C}$. An M-subobject classifier is an object $\Omega$ that classifies M-subobjects: for every object $A$, M-monomorphisms $m: A' \hookrightarrow A$ are in one-to-one correspondance with morphisms $\chi: A \to \Omega$, the former being obtained by pulling back $\tau: 1 \to \Omega$ along the latter.

<figure><img src="image_18.png" /></figure>

Intuitively, $\Omega$ is an object of truth values and an *M*-subobject $A' \to A$ is the pre-image of $1 \to \Omega$ by the corresponding morphism $A \to \Omega$. The rich structure of elementary topoï allows for interpreting higher-order logic within them [FS90, B.315].

Let $\mathcal{T}$ be a monad on **Set**. Its category of algebras **EM**(T) is often regular (as discussed above Theorem 4.1), but it is seldom an elementary topos because **Graph**<sub>**EM**(T)</sub> need not have a right adjoint, and in particular it seldom has a subobject classifier. But if T and $\mu^T$ are nearly cartesian, **EM**(T) is not devoid of additional structure: Corollary 4.10 tells us that **Graph**<sub>**EM**(T)</sub> has a right adjoint when co-restricted to the category of decomposable relations. In particular, this entails the existence of a *decomposable subobject classifier* in **EM**(T):

**Proposition 4.12** (decomposable subobject classifiers). In an elementary topos *E*, let T be a monad that has a monotone weak distributive law over **P**. Then **P**1 classifies decomposable subobjects.
*Proof.* Let $\bar{\mathbf{P}}$ be the weak lifting of $\mathbf{P}$ to $\mathbf{EM}(\mathbf{T})$. The Kleisli adjunction for $\bar{\mathbf{P}}$ yields a bijection between $\mathbf{T}$-algebra morphisms $\chi: A \to \bar{\mathbf{P}}1$ and $\mathbf{KI}(\bar{\mathbf{P}})$-arrows $m: A \dashrightarrow 1$, by means of $\chi \mapsto \varepsilon_1^{\bar{\mathbf{P}}} \circ \mathbf{F}_{\bar{\mathbf{P}}}\chi$.

Recall from Corollary 4.10 that $\mathbf{KI}(\bar{\mathbf{P}})$ is the category of decomposable relations. In particular, the bijection above says that $\mathbf{EM}(\mathbf{T})$-morphisms $\chi: A \to \bar{\mathbf{P}}1$ are in one-to-one correspondence with decomposable relations $A \rightsquigarrow 1$. The latter are given by jointly monic spans $\langle m, !_{A'} \rangle: A' \hookrightarrow A \times 1$ such that $m$ is decomposable, or equivalently by decomposable monomorphisms $m: A' \hookrightarrow A$.

$\langle m, !_{A'} \rangle$ is obtained from $\chi$ by writing $\varepsilon_1^{\bar{\mathbf{P}}}$ as a jointly monic span $\langle \top, !_1 \rangle: R \hookrightarrow \bar{\mathbf{P}}1 \times 1$ and pulling $\top: R \hookrightarrow \bar{\mathbf{P}}1$ back along $\chi: A \to \Omega$:

<figure><img src="image_19.png" /></figure>

$(m$ must then already be a monomorphism because $\top$ is one and pullbacks preserve monomorphisms, hence $\langle m, !_{A'} \rangle$ is indeed a jointly monic span). It follows from [Wyl91, Proposition 14.2] that $R \cong 1$. $\square$

We end this subsection with some examples on **Set** that follow from Corollary 4.10. A first consequence of this corollary is that if all $\mathbf{T}$-algebra morphisms are decomposable, then **Graph**<sub>EM(T)</sub>: **EM**(T) → **Rel**(EM(T)) has a right adjoint and **EM**(T) is therefore an elementary topos.

Note that all $\mathbf{T}$-algebra morphisms being decomposable is not a necessary condition for $\mathbf{EM}(\mathbf{T})$ to be an elementary topos, as the next example shows. We still retrieve a classic example of elementary topoï, namely the categories of group actions.

**Example 4.13.** Let $(M, \cdot, 1)$ be a monoid. $M \times -$ is a monad with unit $\eta_X: x \mapsto (1_M, x)$ and multiplication $\mu_X: (m, (n, x)) \mapsto (m \cdot n, x)$. The endofunctor, multiplication and unit of this monad are cartesian, hence nearly cartesian. Its algebras are $M$-sets, i.e. sets equipped with a left-action of $M$.

By Lemma 4.6, a morphism $f: X \to Y$ of $M$-sets is decomposable if and only if for every $x \in X$, $y \in Y$ and $m \in M$ such that $f(x) = m \cdot y$, there is an $x' \in X$ such that $f(x') = y$ and $m \cdot x' = x$. In particular, every morphism of $M$-set is decomposable if and only if every element of $m$ is invertible (take $x' = m^{-1} \cdot x$ in one direction, and consider the morphism of $M$-sets $m \cdot -: M \to M$ for some non-invertible $M$ in the other direction).

By Corollary 4.10, $\mathbf{EM}(M \times -)$ is therefore an elementary topos as soon as $M$ is a group. It is in fact well known that $\mathbf{EM}(M \times -)$ is always an elementary topos, no matter whether $M$ is a group or not [Wyl91, §27.3].

For our running examples **KHaus**, **JSL** and **Conv**, Proposition 4.12 and the characterization of decomposable morphisms in Example 4.5 yield:

**Example 4.14.**

(1) In **KHaus**, clopen subspaces are classified by **V1**, i.e. the set 2 equipped with the discrete topology (for which all subsets are open).

(2) In **JSL**, $\bar{\mathbf{P}}1 = (2, \max)$ classifies downwards-closed sets.
(3) In **Conv**, $\bar{\mathbf{P}}1$ has carrier set $2 = \{\perp, \top\}$ and barycenters $\lambda \cdot \perp + (1-\lambda) \cdot \top = \perp$ for $\lambda \in [0,1)$. It classifies walls, i.e. subsets $E$ of convex sets $C$ such that if $e \in E$ and $e = \lambda \cdot c + (1-\lambda) \cdot c'$ for $\lambda \in (0,1)$ and $c, c' \in C$, then $c, c' \in E$ as well. Walls appear for instance in the structure theorem for convex algebras, which state that every convex algebra is a subalgebra of the *Płonka sum* of its walls [RS90, Theorem 4.5].

**4.3. Monotone Extensions to Subcategories of Relations.** We saw in Corollaries 4.9 and 4.10 that the Kleisli morphisms $X \dashrightarrow Y$ for a weak lifting of the power-object monad could be described as relations $X \leftarrow \cdot \rightarrow Y$ where the left branch of the span belongs to a certain subclass of morphisms – the class of decomposable morphisms.

More generally, if $\mathbb{R}$ is a sub-power-object monad whose Kleisli morphisms $X \dashrightarrow Y$ are relations $X \leftarrow \cdot \rightarrow Y$ where the left branch of the span belongs to a class $\Gamma$ of morphisms, then by Theorem 4.8 the Kleisli morphisms $X \dashrightarrow Y$ of its weak lifting to some $\mathbf{EM}(\mathbb{T})$ will correspond to relations $X \leftarrow \cdot \rightarrow Y$ where the left branch of the span belongs to a class $\Gamma'$ of morphisms, given as follows: a morphism $f$ belongs to $\Gamma'$ if and only if $f$ is decomposable and if $\mathbf{U}^\top f$ belongs to $\Gamma$.

We formalize the subcategories of relations of this specific shape as follows.

**Definition 4.15.** Let $\Gamma$ be a class of morphims of a regular category $\mathbb{C}$ that is stable under pre-composition with isomorphisms. We define

* $\mathbb{C} \cdot \Gamma^\dagger$ to be the class of $\mathbb{C}$-relations $\psi: X \rightsquigarrow Y$ given by jointly monic spans $\langle \psi_X, \psi_Y \rangle$ such that $\psi_X$ is a $\Gamma$-arrow;

* $\mathbf{Graph}_\mathbb{C}: \mathbb{C} \rightarrow \mathbb{C} \cdot \Gamma^\dagger$ as restriction of $\mathbf{Graph}_\mathbb{C}: \mathbb{C} \rightarrow \mathbf{Rel}(\mathbb{C})$ to $\mathbb{C} \cdot \Gamma^\dagger$;

* $\Gamma^\dagger \cdot \mathbb{C}$-squares to be squares $a \circ b = c \circ d$ such that $a$ or $c$ is a $\Gamma$-arrow.

**Lemma 4.16.** $\mathbb{C} \cdot \Gamma^\dagger$ is a wide subcategory of $\mathbf{Rel}(\mathbb{C})$ if and only if $\Gamma$ is a wide subcategory of $\mathbb{C}$ such that

* $\Gamma$-arrows are stable under pullbacks (in $\mathbb{C}$);

* if $f \circ e$ is a $\Gamma$-arrow and $e$ is a regular epimorphism (in $\mathbb{C}$), $f$ is a $\Gamma$-arrow.

*Proof.* Suppose that $\Gamma$ is a wide subcategory of $\mathbb{C}$ satisfying these conditions. Then $\mathbb{C} \cdot \Gamma^\dagger$ contains all the identities of $\mathbf{Rel}(\mathbb{C})$ because both $\mathbb{C}$ and $\Gamma$ contain all the identities of $\mathbb{C}$. Consider jointly monic spans $\langle f_1, g_1 \rangle: R_1 \hookrightarrow X \times Y$ and $\langle f_2, g_2 \rangle: R_2 \hookrightarrow Y \times Z$ such that $f_1$ and $f_2$ are in $\Gamma$, and let $\langle f', g' \rangle: S \hookrightarrow R_1 \times R_2$ be the pullback of $g_1: R_1 \rightarrow Y$ and $f_2: R_2 \rightarrow X$. Then by the first property of $\Gamma$, $f'$ and thus $f_1 \circ f'$ ($\Gamma$ is a category hence stable under composition) are in $\Gamma$. Factor $\langle f_1 \circ f', g_2 \circ g' \rangle$ into a regular epimorphism followed by a jointly monic span: by the second property of $\Gamma$, the resulting jointly monic span is also in $\mathbb{C} \cdot \Gamma^\dagger$.

Conversely, suppose that $\mathbb{C} \cdot \Gamma^\dagger$ is a wide subcategory of $\mathbf{Rel}(\mathbb{C})$. $\mathbb{C} \cdot \Gamma^\dagger$ contains all identities, hence so does $\Gamma$. Given $f: X \to Y$ and $g: Y \to Z$ in $\Gamma$, $f^\dagger \cdot g^\dagger$ is in $\mathbb{C} \cdot \Gamma^\dagger$ (as the composite of two relations therein) hence $g \circ f$ is in $\Gamma$. If $g: Y \to Z$ is in $\Gamma$, then for any $f: X \to Z$ in $\mathbb{C}$, $g^\dagger \cdot f$ is in $\mathbb{C} \cdot \Gamma^\dagger$ (as the composite of two relations therein) hence the pullback of $g$ along $f$ must be in $\Gamma$. Finally, if $e: X \to Y$ and $f: Y \to Z$ are such that $f \circ e$ is in $\Gamma$, then $e \cdot (f \circ e)^\dagger = f^\dagger$ is in $\mathbb{C} \cdot \Gamma^\dagger$ and $f$ itself must be in $\Gamma$. $\square$

Because we are interested in building extensions to Kleisli categories of monads in order to build weak distributive laws, it is in particular useful to characterize when monotone extensions to these subcategories of relations exist, in the spirit of Theorem 2.7.
**Definition 4.17.** Let $C$ and $D$ be two regular categories with respective wide subcategories $\Gamma$ and $\Delta$ as in Lemma 4.16. Let $F$ be a functor $C \to D$. A $(\Gamma, \Delta)$-relational extension of $F$ is an order-preserving functor $\mathbb{F}_{\Gamma, \Delta}: C \cdot \Gamma^\dagger \to D \cdot \Delta^\dagger$ such that $\mathbb{F}_{\Gamma, \Delta} \mathbf{Graph}_\Gamma = \mathbf{Graph}_\Delta \mathbb{F}_{\Gamma, \Delta}$. If $\alpha: F \Rightarrow G$ is a natural transformation between functors $C \to D$ with $(\Gamma, \Delta)$-relational extensions $\mathbb{F}_{\Gamma, \Delta}$ and $\mathbb{G}_{\Gamma, \Delta}$, a $(\Gamma, \Delta)$-relational extension is a (necessarily unique) natural transformation $\alpha_{\Gamma, \Delta}: \mathbb{F}_{\Gamma, \Delta} \Rightarrow \mathbb{G}_{\Gamma, \Delta}$ such that $\alpha_{\Gamma, \Delta} \mathbf{Graph}_\Gamma = \mathbf{Graph}_\Delta \alpha_{\Gamma, \Delta}$.

**Theorem 4.18.** Let $C$, $D$, $\Gamma$, $\Delta$ and $F: C \to D$ be as in Definition 4.17. $F$ has a $(\Gamma, \Delta)$-relational extension if and only if the following two conditions hold:

* $F$ restricts to a functor $\Gamma \to \Delta$;

* $F$ sends near pullback $\Gamma^\dagger \cdot C$-squares on near pullback (necessarily $\Delta^\dagger \cdot D$-) squares (this is always true when $F$ is nearly cartesian).

Such a $(\Gamma, \Delta)$-relational extension, if it exists, is necessarily unique and given by $\mathbb{F}_{\Gamma, \Delta}(g \cdot f)^\dagger = Fg \cdot (Ff)^\dagger$.

Let $\alpha: F \Rightarrow G$ be a natural transformation between two functors $C \to D$ having such $(\Gamma, \Delta)$-relational extensions. $\alpha$ has a (necessarily unique) $(\Gamma, \Delta)$-relational extension if and only if it has near pullbacks for its naturality squares along $\Gamma$-morphisms (this is always true when $\alpha$ is nearly cartesian).

*Proof.* We adapt the proof of [Goy21, Theorem 5.6], itself taken from [de 92, §5.3.11].

First note that a $C$-relation is in $C \cdot \Gamma^\dagger$ as soon as it can be written $g \cdot f^\dagger$ with $f$ in $\Gamma$, without $f$ and $g$ necessarily being jointly monic (and similarly for $D$ and $\Delta$): if $\langle f, g \rangle = \langle f', g' \rangle \circ e$ with $e$ a regular epimorphism and $f'$ and $g'$ jointly monic, $f' \circ e = f$ and $f'$ is thus also in $\Gamma$. Moreover a $C$-arrow $f$ is in $\Gamma$ if and only if $f^\dagger$ is in $C \cdot \Gamma$ (and, again, similarly for $D$ and $\Delta$): $f^\dagger$ is given by the jointly monic span $\langle f, \mathrm{id} \rangle$.

Recall that for every arrow $f: X \to Y$ in a regular category, $f^\dagger: Y \leftrightarrow X$ is the unique relation such that $\mathrm{id}_X \le f^\dagger \cdot f$ and $f \cdot f^\dagger \le \mathrm{id}_Y$ [CKW91, §1.2 and §1.7]. If $H: C \cdot \Gamma^\dagger \to \mathrm{Rel}(D)$ is monotone, then for every $\Gamma$-arrow $f: X \to Y$,

$$Hf \cdot H(f^\dagger) = H(f \cdot f^\dagger) \le H(\mathrm{id}_Y) = \mathrm{id}_{HY}$$

and

$$\mathrm{id}_{HX} = H(\mathrm{id}_X) \le H(f^\dagger \cdot f) = H(f^\dagger) \cdot Hf$$

and therefore $H(f^\dagger) = (Hf)^\dagger$.

In particular if we take $H$ to be a $(\Gamma, \Delta)$-relational extension of $F$ followed by the inclusion $D \cdot \Delta^\dagger \to \mathrm{Rel}(D)$, we get that $(Ff)^\dagger$ is in $D \cdot \Delta^\dagger$, and thus $Ff$ is in $\Delta$: $F$ restricts to a functor $\Gamma \to \Delta$. This forces $H$ to be given on $C \cdot \Gamma^\dagger$-relations by $H(g \cdot f^\dagger) = Fg \cdot (Ff)^\dagger$ (for $f$ in $\Gamma$). Consider now a near pullback $\Gamma^\dagger \cdot C$-square $f \circ g' = g \circ f'$, so that $f^\dagger \cdot g = g' \cdot (f')^\dagger$. Applying $H$, we get $(Ff)^\dagger \cdot Fg = Fg' \cdot (Ff')^\dagger$, hence $Ff \circ Fg' = Fg \circ Ff'$ is a nearly cartesian $\Delta^\dagger \cdot D$-square.

Conversely, suppose $F$ satisfies the two properties above, and define $\mathbb{F}_{\Gamma, \Delta}: C \cdot \Gamma^\dagger \to D \cdot \Delta^\dagger$ by $\mathbb{F}_{\Gamma, \Delta}(g \cdot f^\dagger) = Fg \cdot Ff^\dagger$ for jointly monic $f$ and $g$: because $F$ restricts as a functor $\Gamma \to \Delta$, the result is indeed in $D \cdot \Delta^\dagger$. $\mathbb{F}_{\Gamma, \Delta}$ moreover preserves the identity: $\mathbb{F}_{\Gamma, \Delta} (\mathrm{id}_X \cdot \mathrm{id}_X^\dagger) = \mathrm{Fid}_X \cdot (\mathrm{Fid}_X)^\dagger = \mathrm{id}_{FX} \cdot \mathrm{id}_{FX}^\dagger$. Finally, $\mathbb{F}_{\Gamma, \Delta}$ preserves composition:

* Given $f: R \to X$ and $g: R \to Y$ (not necessarily jointly monic), write $\langle f, g \rangle = \langle f', g' \rangle \circ e$ with $e$ a regular epimorphism and $\langle f', g' \rangle$ a monomorphism, so that $g \cdot f^\dagger = g' \cdot (f')^\dagger$
and $\mathbb{E}_{\Gamma, \Delta} (g \cdot f^{\dagger}) = \mathbb{F}g' \cdot (\mathbb{F}f')^{\dagger}$ by definition. Since $\mathbb{F}$ preserves regular epimorphisms (the square id $\circ e = \text{id} \circ e$ is a near pullback $\Gamma^{\dagger} \cdot \text{C-square}$ hence $\text{id} \circ \mathbb{F}e = \text{id} \circ \mathbb{F}e$ is a near pullback as well), we get that $\mathbb{E}_{\Gamma, \Delta} (g \cdot f^{\dagger}) = \mathbb{F}g' \cdot (\mathbb{F}f')^{\dagger} = \mathbb{F}g \cdot (\mathbb{F}f)^{\dagger}$.

* Given $f: Y \to R$ and $g: X \to R$, write $p_X: P \to X$ and $p_Y: P \to Y$ for their pullback: $f^{\dagger} \cdot g = p_Y \cdot p_X^{\dagger}$ and $\mathbb{E}_{\Gamma, \Delta} (f^{\dagger} \cdot g) = \mathbb{F}p_Y \cdot (\mathbb{F}p_X)^{\dagger}$ by definition. The $\Gamma^{\dagger} \cdot \text{C-square}$ $f \circ p_Y = g \circ p_X$ is a near pullback, hence so is $\mathbb{F}f \circ \mathbb{F}p_Y = \mathbb{F}g \circ \mathbb{F}p_X: \mathbb{E}_{\Gamma, \Delta} (f^{\dagger} \cdot g) = \mathbb{F}p_Y \cdot (\mathbb{F}p_X)^{\dagger} = (\mathbb{F}f)^{\dagger} \cdot \mathbb{F}g$.

Consider now some $\alpha: \mathbb{F} \Rightarrow \mathbb{G}$ as above. $\underline{\alpha}_{\Gamma, \Delta}: \mathbb{E}_{\Gamma, \Delta} \Rightarrow \underline{\mathbb{G}}_{\Gamma, \Delta}$ is as a natural transformation if and only if for every $\langle f, g \rangle: R \hookrightarrow X \times Y$ in $\mathbb{C} \cdot \Gamma^{\dagger}$, i.e. with $f$ in $\Gamma$, $\alpha_Y \cdot \mathbb{F}g \cdot (\mathbb{F}f)^{\dagger} = \mathbb{G}g \cdot (\mathbb{G}f)^{\dagger} \cdot \alpha_X$. Of course $\alpha_Y \cdot \mathbb{F}g = \mathbb{G}g \cdot \alpha_R$ because $\alpha$ is a natural transformation $\mathbb{F} \Rightarrow \mathbb{G}$, hence this is true if and only if $\alpha_R \cdot (\mathbb{F}f)^{\dagger} = (\mathbb{G}f)^{\dagger} \cdot \alpha_X$ (consider the case $g = \text{id}_R$), i.e. if and only if the naturality square $\alpha_X \circ \mathbb{F}f = \mathbb{G}f \circ \alpha_R$ is a near pullback. $\square$

As an example, a first corollary of Theorem 4.18 is the following:

**Corollary 4.19.** In Set, a monad $(\mathbf{T}, \eta^{\mathbf{T}}, \mu^{\mathbf{T}})$ whose endofunctor and multiplication are nearly cartesian also has a (necessarily unique) monotone weak distributive law over the monad $\mathbf{P}_*$ of non-empty subsets, and has one over the monad $\mathbf{P}_f$ of finite subsets if and only if $\mathbf{T}$ preserves functions with finite pre-images of elements.

*Proof.* Recall that a monotone weak distributive law $\mathbf{TS} \Rightarrow \mathbf{ST}$ is equivalently given by a weak extension $(\mathbf{T}, \mu^{\mathbf{T}})$ of $\mathbf{T}$ to $\mathbf{KI}(\mathbf{S})$ with $\mathbf{T}$ monotone.

A $\mathbf{KI}(\mathbf{P}_*)$ morphism is a function $X \to \mathbf{P}_*Y$, i.e. a relation such that every element of $X$ is related to at least one element of $Y$. When seen as jointly monic spans $\langle \psi_X, \psi_Y \rangle$, these relations are exactly those such that $\psi_X$ is surjective. Surjections satisfy the two conditions of Lemma 4.16 because they are the same thing as regular epimorphisms and **Set** is regular, and so we may apply Theorem 4.18 as nearly cartesian endofunctors preserve in particular regular epimorphisms.

A $\mathbf{KI}(\mathbf{P}_f)$ morphism is a function $X \to \mathbf{P}_f Y$, i.e. a relation such that every element of $X$ is related to a finite number of elements of $Y$. When seen as jointly monic spans $\langle \psi_X, \psi_Y \rangle$, these relations are exactly those such that $\psi_X$ has finite pre-images of elements. These functions with finite pre-images of elements are easily seen to satisfy the two conditions of Lemma 4.16, and so we may apply Theorem 4.18. $\square$

We could more generally characterize the existence of monotone weak distributive laws over these powerset monads for any monad on **Set**. Still, Corollary 4.19 is already enough to prove that **P** has monotone weak distributive laws over $\mathbf{P}_f$ and $\mathbf{P}_*$, that **D** has a monotone weak distributive law over $\mathbf{P}_*$ but not over $\mathbf{P}_f$, and that $\beta$ has a monotone weak distributive law over $\mathbf{P}_*$.

## 5. MONOTONE WEAK DISTRIBUTIVE LAWS IN CATEGORIES OF ALGEBRAS

In Section 4, we described the Kleisli categories of weakly lifted sub-power-object monads, and characterized the existence of monotone extensions of functors and natural transformations to these Kleisli categories. We now apply these results to build monotone weak distributive laws in categories of algebras, or conversely show that monotone weak distributive laws between certain monads cannot exist.

In Section 5.1, we start with a generic argument that will make studying concrete examples easier. In Section 5.2, we show how the results from Section 4 may be used
to exhibit monotone weak distributive laws in **KHaus**. Finally, in Section 5.3, we show conversely that in other categories of algebras, e.g. **JSL** and **Conv**, some monotone weak distributive laws involving the weakly lifted powerset monad cannot exist.

**5.1. Weakly Lifting Preserves Near Cartesianness.** In this subsection, assume again (as in Section 4) that $\mathcal{C}$ is a regular category, that $\mathbb{R}$ is a sub-power-object monad on $\mathcal{C}$, and that $\mathbb{T}$ is a monad on $\mathcal{C}$ with nearly cartesian endofunctor and multiplication, whose relational extension $\mathbb{I}$ restricts to $\mathbf{KI}(\mathbb{R})$.

For a monad $S'$ on $\mathbf{EM}(\mathbb{T})$ to have a monotone weak extension to $\mathbf{KI}(\overline{\mathbb{R}})$ (equivalently a monotone weak distributive law over $\overline{\mathbb{R}}$), Theorems 4.8 and 4.18 tell us in particular that the endofunctor $S'$ should preserve a certain subclass $\Gamma$ of morphisms as well as preserve near pullbacks involving $\Gamma$-morphisms, and the multiplication $\mu^{S'}$ should have near pullbacks for its naturality squares along morphisms in $\Gamma$.

Recall now that our motivating examples were possible monotone weak distributive laws $\overline{\mathbb{P}}\mathbb{P} \Rightarrow \overline{\mathbb{P}}\mathbb{P}$ in **JSL** or **Conv**: in these cases, $S' = \overline{\mathbb{P}}$ is itself the weak lifting of a monad whose endofunctor and multiplication are nearly cartesian. It turns out this is enough for $S'$ itself to have nearly cartesian endofunctor and multiplication:

**Lemma 5.1.** Let $\mathcal{C}$ be a regular category, and suppose $\mathbb{T}$ is nearly cartesian. If $\mathbb{F}: \mathcal{C} \to \mathcal{C}$ is nearly cartesian and weakly lifts to $\mathbf{EM}(\mathbb{T})$, then its weak lifting is nearly cartesian. If $\alpha: \mathbb{F} \Rightarrow \mathbb{G}$ between two such functors is nearly cartesian and weakly lifts to $\mathbf{EM}(\mathbb{T})$, then its weak lifting is nearly cartesian as well.

*Proof.* Suppose $\mathbb{F}$ is nearly cartesian, i.e. preserves near pullbacks, and that it has a weak lifting $\overline{\mathbb{F}}$ to $\mathbf{EM}(\mathbb{T})$. Then it also has a semi-lifting $\mathbb{F}$ to $\mathbf{EM}_s(\mathbb{T})$, and $\mathbb{F}U_s^\mathbb{T} = U_s^\mathbb{T}\overline{\mathbb{F}}$ is nearly cartesian as well. Since $U_s^\mathbb{T}$ creates near pullbacks by Theorem 4.1, $\mathbb{F}$ is nearly cartesian. Now $\overline{\mathbb{F}} \cong \mathbf{K}^\mathbb{T}\overline{\mathbb{F}}\mathbf{I}^\mathbb{T}$, but $\mathbf{K}^\mathbb{T}$ and $\mathbf{I}^\mathbb{T}$ are both left and right adjoints, hence they preserve both limits and colimits, and thus near pullbacks (regular epimorphisms are preserved as coequalizers of their kernel pairs). It follows that $\overline{\mathbb{F}}$ preserves near pullbacks.

Suppose $\alpha: \mathbb{F} \Rightarrow \mathbb{G}$ is a nearly cartesian natural transformation between two such functors that has a weak lifting $\overline{\alpha}: \overline{\mathbb{F}} \Rightarrow \overline{\mathbb{G}}$ to $\mathbf{EM}(\mathbb{T})$. Then it also has a semi-lifting $\alpha$ to $\mathbf{EM}_s(\mathbb{T})$, and $\alpha U_s^\mathbb{T} = U_s^\mathbb{T}\alpha$ is nearly cartesian. Since $U_s^\mathbb{T}$ creates near pullbacks, $\alpha$ is nearly cartesian. Now $\overline{\alpha} \cong \mathbf{K}^\mathbb{T}\overline{\alpha}\mathbf{I}^\mathbb{T}$, hence since $\mathbf{K}^\mathbb{T}$ and $\mathbf{I}^\mathbb{T}$ preserve near pullbacks $\overline{\alpha}$ is also nearly cartesian. $\square$

In other words, if $S$ has nearly cartesian endofunctor and multiplication, then this is also the case of $S' = \overline{S}: \overline{S}$ and $\mu^{\overline{S}}$ have relational extensions, and $\overline{S}$ admits a monotone weak distributive law over $\overline{\mathbb{R}}$ if and only if $\mathbf{Rel}(\overline{S})$ restricts to $\mathbf{KI}(\overline{\mathbb{R}})$. If $\mathcal{C} = \mathbf{Set}$, this means for instance:

**Corollary 5.2.** Let $\mathbb{T}$ be a monad on **Set** equipped with a monotone weak distributive law $\mathbb{T}\mathbb{P} \Rightarrow \mathbb{T}\mathbb{P}$, and let $S'$ be a monad on $\mathbf{EM}(\mathbb{T})$. If there is a monotone weak distributive law $S'\overline{\mathbb{P}} \Rightarrow \overline{\mathbb{P}}S'$ (resp. $S'\overline{\mathbb{P}}_* \Rightarrow \overline{\mathbb{P}}_*S'$), $S'$ preserves decomposable (resp. decomposable surjective) $\mathbb{T}$-algebra morphisms. Moreover if $S'$ is itself the weak lifting of a monad on **Set** that has a monotone weak distributive law over $\mathbb{P}$, then the previous condition is not only necessary, but also sufficient.

*Proof.* By Corollary 4.9, decomposable $\mathbf{EM}(\mathbb{T})$-relations form a wide subcategory of all $\mathbf{EM}(\mathbb{T})$-relations, hence the conditions in Lemma 4.16 hold for the class $\Gamma$ of decomposable morphisms and we may thus apply Theorem 4.18 to characterize monotone extensions to
KI($\overline{\mathbf{P}}$). In particular if S is the weak lifting of a monad on Set whose underlying endofunctor and multiplication are nearly cartesian, then this is also true of S itself by Lemma 5.1: the monotone weak distributive law $\overline{\mathcal{S}\mathbf{P}} \Rightarrow \overline{\mathcal{P}\mathcal{S}}$ exists if and only if $\overline{\mathcal{S}}$ preserves decomposable morphisms.

By Theorem 4.8, the Kleisli category of $\overline{\mathbf{P}}_*$ has for arrows $X \dashrightarrow Y$ the T-relations given as jointly monic spans $\langle\psi_X, \psi_Y\rangle: R \hookrightarrow X \times Y$ such that $\psi_X$ is decomposable and $\mathbf{U}^\mathrm{T}\psi_X$ is surjective. $KI(\overline{\mathbf{P}}_*)$ is a category, so these relations form a wide subcategory of all $\mathbf{EM}(\mathrm{T})$-relations, hence the conditions of Lemma 4.16 hold and we may thus apply Theorem 4.18 to characterize monotone extensions to $KI(\overline{\mathbf{P}}_*)$. $\square$

Corollary 5.2 makes it much simpler to check whether $S'$ has a monotone weak distributive law over $\overline{\mathbf{P}}$ or $\overline{\mathbf{P}}_*$: there is no need to check that some squares are nearly cartesian anymore.

**5.2. Monotone Weak Distributive Laws in KHaus.** A first use of Corollary 5.2 lies in retrieving the monotone weak distributive law $VV \Rightarrow VV$: it is exhibited in [GPA21] by showing that $V$ and $\mu^V$ are nearly cartesian, and that $Rel(V)$ preserves continuous relations, but our proof is much simpler.

**Theorem 5.3** (Vietoris weakly distributes over itself [GPA21, Theorem 24]). There are monotone weak distributive laws $VV \Rightarrow VV$ and $VV_* \Rightarrow V_*V$.

*Proof.* First note that $V_*$ is easily seen to be the weak lifting of $P_*$ to $KHaus \cong \mathbf{EM}(\beta)$. By Theorem 4.8, $KI(V_*)$ is the category of relations which, when seen as jointly monic spans $\langle\psi_X, \psi_Y\rangle$, are such that $\psi_X$ is both decomposable (i.e. open) and surjective.

$V$ is a weak lifting of $P$ to $\mathbf{EM}(\beta) \cong KHaus$, hence by Corollary 5.2 we only need to show that $V$ preserves decomposable $\beta$-algebra morphisms (for the law $VV \Rightarrow VV$), i.e. open maps by Example 4.5, and open surjections (for the law $VV_* \Rightarrow V_*V$).

$V$ preserves surjections because it is the weak lifting of a nearly cartesian endofunctor, hence it is nearly cartesian itself.

That $V$ preserves open maps is easily seen to be true. Consider indeed some open map $f: X \to Y$, and some open subset $u$ of $X$. Then $\square u = \{c \in VX \mid c \subseteq u\}$ is open in $VX$, and $(Vf)[\square u] = \{f[c] \mid c \in \square u\} = \square f[u]$ is open in $VY$. Similarly $\diamond u = \{c \in VX \mid c \cap u \neq \emptyset\}$ is open in $VX$, and $(Vf)[\diamond u] = \{f[c] \mid c \in \diamond u\} = \diamond f[u] \cap \square f[X]$ is open in $VY$. Because the sets $\square u$ and $\diamond u$ form a subbasis of the topology of $VX$ when $u$ ranges among all open sets of $X$, this proves that $Vf$ is open. $\square$

We are also able to answer quite easily [Goy21, Conjecture 7.31] on the weak distributivity of the Radon monad – the monad of Radon probability measures on a compact Hausdorff space – over the Vietoris monad:

**Theorem 5.4.** The Radon monad $\mathbf{R}$ does not have a monotone weak distributive law over the Vietoris monad $V$, but it has (a unique) one over the non-empty Vietoris monad $V_*$.

Before giving the proof, let us first recall how the Radon monad is defined. Given a compact Hausdorff space $X$, let $C(X)$ denote the Banach space of continuous functions $X \to \mathbb{C}$ equipped with the uniform norm ($||f|| = \sup_{x \in X} |f(x)|$). A continuous function $C(X) \to \mathbb{C}$ is called a *functional*, and it is called *positive* when its sends functions with positive real domains to positive real numbers. The space of functionals $C(X) \to \mathbb{C}$ is equipped with the *operator norm*, defined by $||\varphi|| = \sup_{||f||=1} |\varphi(f)|$.
R sends a compact Haudorff space X on the space RX of Radon probability measures on X, or equivalently by the Riesz-Markov-Kakutani theorem [Rud87, Theorem 2.14] to the space of positive linear functionals $C(X) \to \mathbb{C}$ with operator norm 1: for every such functional $\varphi$ there is thus a Radon measure m on X such that $\varphi(f) = \int_X u dm$ for any $f \in C(X)$, and conversely integrating along a measure defines an operator with the aforementioned properties. RX (seen as the space of functionals) is equipped with the vague topology, i.e. the weakest topology that makes each $ev_f: RX \to \mathbb{C}$ continuous, where $f$ ranges in $C(X)$ and $ev_f$ is the function that evaluates an operator at $f$.

Given $f: X \to Y$ in KHaus, $\varphi \in RX$ and $g \in C(Y)$, $(Rf)(\varphi)(g) = \varphi(g \circ f)$. $\eta^R(x) \in RX$ is the operator that evaluates a continuous function at $x \in X$, and for $\Phi \in RRX$ and $f \in C(X)$, $\mu^R(\Phi)(f) = \Phi(ev_f)$.

Proof.

**Radon over Vietoris:** Consider the inclusion $f: 1 \to 2$. 1 and 2 are sets equipped with the discrete topology, so that $f$ is an open continuous function. But $R1 = 1$ and $R2$ is the unit interval: a point is never open in the unit interval, hence $Rf$ cannot be open. **R** does not preserve open maps, hence by Corollary 5.2 it does not have a monotone weak distributive law over **V**.

**Radon over non-empty Vietoris:** We use again that $KI(\mathbf{V}_*)$ is the category of relations, which, when seen as jointly monic spans $\langle\psi_X, \psi_Y\rangle$, are such that $\psi_X$ is both open and surjective. Because $KI(\mathbf{V}_*)$ is a category, these relations form a wide subcategory of the relations in KHaus, hence the conditions in Lemma 4.16 hold and Theorem 4.18 applies: **R** is a nearly cartesian endofunctor – it preserves regular epimorphisms [Goy21, Propositions 7.26] and sends pullbacks on near pullbacks [Goy21, Proposition 7.28] – and it preserves open surjections [DE72, Theorem 4.4], therefore it has a monotone extension to $KI(\mathbf{V}_*)$.

We now show that the naturality squares $\mu_Y^R \circ \mathbf{R}Rf = \mathbf{R}f \circ \mu_X^R$ of $\mu^R$ along surjections $f: X \to Y$ are near pullbacks, so that $\mu^R$ also extends to $KI(\mathbf{V}_*)$ and we get a weak distributive law $\mathbf{R}V_* \Rightarrow \mathbf{V}_*\mathbf{R}$.

Consider thus a continuous surjection $f: X \to Y$ in KHaus, and recall that $Rf$ is also surjective [Goy21, Proposition 7.26] (in fact we will simply adapt the proof of preservation of surjectivity to show our result). Consider some $\Phi \in RRY$ and $\psi \in RX$ such that $\mu_Y^R(\Phi) = (Rf)(\psi)$, i.e. $\Phi(ev_g) = \psi(g \circ f)$ for every $g \in C(Y)$.

Consider a first subspace $V_1$ of $C(RX)$ consisting of continuous functions of the shape $g \circ Rf$ for $g \in C(RY)$: $g \circ Rf \mapsto \Phi(g)$ defines a linear functional $\Psi_1$ of norm 1 on $V_1$ (the definition does not depend on the choice of $g$ because there is only one such choice as $Rf$ is surjective).

Similarly, consider a second subspace $V_2$ of $C(RX)$ consisting of continuous functions of the shape $ev_g$ for some $g \in C(X)$: then $ev_g \mapsto \psi(g)$ defines a linear functional $\Psi_2$ of norm 1 on $V_2$.

If a continuous function in $C(RX)$ is in $V_1 \cap V_2$, it is of the shape $ev_{g \circ f} = ev_g \circ Rf$ for some $g \in C(Y)$, and $\Phi(ev_g) = \psi(g \circ f)$ by assumption: $\Psi_1$ and $\Psi_2$ agree on $V_1 \cap V_2$. This defines a linear functional of operator norm 1 on $V_1+V_2$, which extends to a linear functional $\Psi$ of operator norm 1 on $C(RX)$ by the Hahn-Banach theorem [Rud87, Theorem 5.16]. A linear functional of operator norm 1 is positive if and only if it sends the constant function 1 to 1 $\in \mathbb{C}$ (as argued for instance in [Rud87, §5.22]), hence
$ev_1 = 1$ on $RX$ and thus $\Psi(1) = \Psi(ev_1) = \psi(1) = 1$: this implies in turn that $\Psi$ is positive.

We thus found some $\Psi \in RRX$ such that $(RRf)(\Psi) = \Phi$ and $\mu_X^R(\Psi) = \psi$. Because $U^\beta$ creates near pullbacks, this proves that the commuting square $\mathbf{R}f \circ \mu_X^R = \mu_Y^R \circ \mathbf{R}Rf$ is a near pullback. $\square$

Let us stress the importance of this new weak distributive law: the question of how to combine probability and non-determinism has been the topic of numerous works (again, see the introduction of [KP17]), and this law provides an answer in **KHaus** that is derived from a generic construction and thus comes with generic tools, e.g. generalized determinization and up-to techniques [GP20, Goy21]. In a very recent pre-print [Gou24], Goubault-Larrecq also constructs this law $RV_* \Rightarrow V_*R$ as an instance of weak distributive laws between monads of continuous valuations and non-deterministic choice in more general categories of topological spaces: our result is more restricted, but we derive the law from generic categorical principles instead of building it by hand, exhibit its canonicity (it comes from a relational extension), and show why the non-empty version of the Vietoris monad is needed.

**5.3. No-go Theorems for Monotone Weak Distributive Laws in Categories of Algebras.** A second use of Corollary 5.2 is in proving the absence of monotone weak distributive laws. In Section 3 we were able to prove that the law $\mathbf{PP} \Rightarrow \mathbf{PP}$ does not weakly lift to $\mathbf{EM}(\mathbf{P})$ nor $\mathbf{EM}(\mathbf{D})$, but we were not able to say anything about the existence of other monotone weak distributive laws $\overline{\mathbf{P}}\overline{\mathbf{P}} \Rightarrow \overline{\mathbf{P}}\overline{\mathbf{P}}$. Now, thanks to the framework developed above, we are able to prove that such laws cannot exist. We start with $\mathbf{EM}(\mathbf{P})$:

**Example 5.5.** In $\mathbf{EM}(\mathbf{P}) \cong \mathbf{JSL}$, let $\overline{\mathbf{P}}$ be the monad of subsets closed under non-empty joins: the join of a family $(E_i)_{i \in I}$ of non-empty-joins-closed subsets of $X$ is the non-empty-joins-closed subset $\{\bigcup_{i \in I} x_i \mid x_i \in E_i\}$. Let $f: 4 \to 2$ (where $2 = \{0, 1\}$ and $4 = \{0, 1, 2, 3\}$) be the function given by $f(0) = f(2) = 0$ and $f(1) = f(3) = 1$. Then $\mathbf{F}^p f$ is decomposable (by Lemma 4.7), but $\overline{\mathbf{P}}\overline{\mathbf{F}}^p f$ is not.

*Proof*. Indeed, let $A \in \overline{\mathbf{P}}\mathbf{F}^4$ and $B, B_1, B_2 \in \overline{\mathbf{P}}\mathbf{F}^2$ be as depicted in Figure 2a (page 35): $(\overline{\mathbf{P}}\mathbf{F}^p f)(A) = B = B_1 \lor B_2$ but there are no $A_1, A_2 \in \overline{\mathbf{P}}\mathbf{F}^4$ such that $A = A_1 \lor A_2$ and $(\overline{\mathbf{P}}\mathbf{F}^p f)(A_1) = B_1$ as well as $(\overline{\mathbf{P}}\mathbf{F}^p f)(A_2) = B_2$.

Suppose indeed there are such $A_1$ and $A_2$. Then $A_1, A_2 \subseteq A$ and thus $\{0, 1, 2, 3\} \in A_1 \cup A_2$ ($\{0, 1, 2, 3\}$ is join-irreducible in $A$). This would imply $\{0, 1\} \in B_1 \cup B_2$, which does not hold. $\square$

$\overline{\mathbf{P}}$ does not preserve decomposable $\mathbf{P}$-algebra morphisms, and thus there is no monotone weak distributive law $\overline{\mathbf{P}}\overline{\mathbf{P}} \Rightarrow \overline{\mathbf{P}}\overline{\mathbf{P}}$. In fact because the counter-example decomposable morphism is surjective and has finite pre-images, this also proves that there are no monotone weak distributive laws $\overline{\mathbf{P}}\overline{P}_* \Rightarrow \overline{P}_*\overline{\mathbf{P}}$ or $\overline{\mathbf{P}}\overline{P}_f \Rightarrow \overline{P}_f\overline{\mathbf{P}}$ in $\mathbf{EM}(\mathbf{P})$.

Because there is a morphism of monads $\mathbf{D} \Rightarrow \mathbf{P}$ (that sends a probability distribution to its support), there is a functor $\mathbf{EM}(\mathbf{P}) \to \mathbf{EM}(\mathbf{D})$ which allows us to transfer Example 5.5 to $\mathbf{EM}(\mathbf{D})$: there are no monotone weak distributive laws $\mathbf{PP} \Rightarrow \mathbf{PP}$ or $\overline{\mathbf{P}}\overline{P}_* \Rightarrow \overline{P}_*\overline{\mathbf{P}}$ in $\mathbf{EM}(\mathbf{D})$. But this argument is not entirely satisfying, as the resulting example is that of a morphism
<figure><img src="image_20.png" /><figcaption>FIGURE 2. Counterexamples to preservation of decomposability</figcaption></figure>

of convex algebras with very unnatural structures, namely that of complete join-semilattices: one could imagine restricting to a full subcategory of **EM(D)** that does not contain these semilattices, and perhaps $\bar{P}$ would preserve decomposable morphisms there. As shown by the following example, due to Harald Woracek and Ana Sokolova (private communication), this cannot be the case as soon as free convex algebras come in the picture.

**Example 5.6 ([WS24]).** In **EM(D)** $\cong$ **Conv**, let $\bar{P}$ be the monad of convex subsets: a convex combination of some convex subsets of $X$ is the convex set of the corresponding convex combinations of their points (in $X$). Let $f: \{A, B, C\} \to \{B, C\}$ be the function given by $f(A) = f(B) = B$ and $f(C) = C$. Then $\mathbf{F}^D f$ is decomposable (by Lemma 4.7) but $\bar{P} \mathbf{F}^D f$ is not.

*Proof.* Indeed, depicting $\mathbf{F}^D\{A, B, C\}$ as the triangle depicted in Figure 2b (page 35), $\mathbf{F}^D\{B, C\}$ is the line segment $[BC]$ and $\mathbf{F}^D f$ is the vertical projection. Now $\frac{1}{2}\{B\} + \frac{1}{2}[FC] = [DE] = (\bar{P}\mathbf{F}^D f) ([GD])$, but $[GD]$ itself cannot be disintegrated as the mean of two convex subsets of $ABC$, one above $B$ and the other above $[FC]:$ if such a disintegration existed, then the convex subset above $B$ would contain both $B$ (because $D \in [DG]$) and $A$ (because $G \in [DG]$), hence would be $[AB]$. The subset above $[FC]$ would contain at least one point, and hence the mean of these two subsets would have to contain a non-trivial vertical line segment, which is not the case of $[DG]$. $\square$

Using similar arguments, we are able to prove the existence or absence of monotone weak distributive laws over lifted powerset monads in several categories of algebras: these results are gathered in Table 1. All the negative results in this table come from the non-preservation of decomposable morphisms, and thus the absence of monotone extensions of the endofunctors themselves. The topmost row indicates in which category we work. A monad in the second topmost row has a monotone weak distributive law over a monad in the left column if the corresponding cell is filled with $\check{\text{✓}}$, otherwise it is filled with $\text{X}$. In **Set**, $\bar{P}$ and $\bar{P}_*$ are the usual powerset monads **P** and $\mathbf{P}_*$. **L** is the monad of lists, **M** that of multisets and $\mathbf{M}_S$ that of modules for a semiring $S$ satisfying the conditions of [BS22, Theorem 3.1]. **Mon** $\cong$ **EM(L)** is the category of monoids and $\mathbf{CMon} \cong$ **EM(M)** that of commutative monoids. Linear theories distribute over commutative monads [MM07], hence
<table><caption>TABLE 1. Existence or absence of monotone weak distributed laws over weakly lifted powerset monads in categories of algebras.</caption><thead><tr><th rowspan="2"></th><th colspan="5">Set</th><th colspan="2">KHaus</th><th>JSL</th><th>Conv</th><th colspan="3">Mon</th><th colspan="3">CMon</th></tr><tr><th>L</th><th>M</th><th>D</th><th>P</th><th>β</th><th>M<sub>S</sub></th><th>V</th><th>R</th><th>P&#773;</th><th>P&#773;</th><th>M&#773;</th><th>D&#773;</th><th>P&#773;</th><th>M&#773;<sub>S</sub></th><th>M&#773;</th><th>D&#773;</th><th>P&#773;</th></tr></thead><tbody><tr><th>P&#773;</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>P&#773;<sub>*</sub></th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

L and M distribute over M, P, D and M<sub>S</sub> when S is commutative, and so these four monads have liftings (in particular weak liftings) to Mon and CMon.

*Proof of Table 1.* The cases of KHaus, JSL and Conv have already been treated in Theorem 5.4 and Examples 5.5 and 5.6

**In Mon:** By Lemma 4.6, a morphism of monoids $f: A \to B$ is decomposable if and only if for every $f(a) = b_1 \cdots b_n$ with $a \in A$ and $b_i \in B$, there are some $a_1, \dots, a_n \in A$ such that $f(a_i) = b_i$ and $a = a_1 \cdots a_n$.

**PP ⇒ PP:** Here $P = \bar{P}$ is the monad of subsets of monoids: if $A$ is a monoid with unit $e$, PA is a monoid with unit $\{e\}$ and multiplication $\alpha_1\alpha_2 = \{a_1a_2 \mid a_i \in \alpha_i\}$. Consider the constant function $f: \{a, b\} \to \{a\}$. It extends to a monoid morphism $f^*: \{a, b\}^* \to \{a\}^*$. Let $\beta = \{aa\}$, $\beta_1 = \beta_2 = \{a\}$ and $\alpha = \{ab, ba\}$: $\beta = \beta_1\beta_2$ and $\beta = f^*[\alpha]$. Suppose $\alpha_1, \alpha_2 \in \bar{P}(\{a, b\}^*)$ are such that $f^*[\alpha_i] = \beta_i$. Then all the words in $\alpha_i$ must have length 1. Hence if $\alpha_1\alpha_2 \supseteq \alpha$, $\alpha_1$ and $\alpha_2$ must both contain $a$ and $b$, which implies that $\{aa, bb\} \subset \alpha_1\alpha_2 \neq \alpha$.

**M<sub>S</sub>P ⇒ PM<sub>S</sub>:** Let $S$ be a commutative (unital) semiring. Here $M_S$ is the monad of $S$-linear combinations: if $A$ is a monoid with unit $e$, $M_S A$ is a monoid with unit $1 \cdot e$ and multiplication $(\sum_i \alpha_i \cdot a_i) (\sum_j \beta_j \cdot b_j) = \sum_{i,j} \alpha_i \beta_j \cdot a_i b_j$. The counter-example for $P$ can be adapted: $(1 \cdot a)((1+1) \cdot a) = (1+1) \cdot aa = f(1 \cdot ab+1 \cdot ba)$. If there are $\alpha_1, \alpha_2 \in M_S(\{a, b\}^*)$ such that $(M_S f^*)(\alpha_1) = 1 \cdot a$, $(M_S f^*)(\alpha_2) = (1+1) \cdot a$ and $\alpha_1\alpha_2 = 1 \cdot ab+1 \cdot ba$, then $\alpha_1 = w \cdot a + x \cdot b$ and $\alpha_2 = y \cdot a + z \cdot b$ where $w, x, y, z \in S$ are such that $w+x=1$, $y+z=1+1$, $wy=0$, $wz=1$, $xy=1$ and $xz=0$. This implies that $z = (w+x)z = wz+xz=1$ and similarly $y = (w+x)y = wy+xy=1$, hence that $w=0$ and $x=0$ and thus $1=w+x=0$: $S$ is the trivial semiring and $M_S$ is the constant monad $\{0\}$.

**MP ⇒ PM:** This is the instance $S = \mathbb{N}$ of the case $M_S P \Rightarrow PM_S$.

**DP ⇒ PD:** Here $D = \bar{D}$ is the monad of finitely supported probability distributions on a monoid: if $A$ is a monoid with unit $e$, DA is a monoid with unit $\delta_e$ and multiplication $(\alpha_1\alpha_2)(a) = \sum_{a_1a_2=a} \alpha(a_1)\beta(a_2)$. The counter-example for $P$ can be adapted:

$$\delta_{aa} = \delta_a \delta_a = (\mathbf{D}f)(\delta_{ab}/2 + \delta_{ba}/2)$$
**In CMon:** By Lemma 4.6, a morphism of commutative monoids $f: A \to B$ is decomposable if and only if for every $f(a) = m_1b_1 + \cdots + m_nb_n$ with $a \in A, b_i \in B$ and $m_i \in \mathbb{N}$, there are some $a_1, \dots, a_n \in A$ such that $f(a_i) = b_i$ and $a = m_1a_1 + \cdots + m_nb_n$.

**PP $\Rightarrow$ PP:** Here $\mathbf{P} = \bar{\mathbf{P}}$ is the monad of subsets of monoids: if $A$ is a commutative monoid with unit 0, $\mathbf{P}A$ is a monoid with unit $\{e\}$ and addition $\alpha_1 + \alpha_2 = \{a_1 + a_2 \mid a_i \in \alpha_i\}$.

Consider the constant function $f: \{a, b\} \to \{a\}$. It extends to a commutative monoid morphism $f^{\otimes}: \{a, b\}^{\otimes} \to \mathbb{N}$ (where $\Sigma^{\otimes}$ is the free commutative monoid on $\Sigma$). Let $\beta = \{2a\}, \beta_1 = \beta_2 = \{a\}$ and $\alpha = \{2a, 2b\}$: $\beta = \beta_1 + \beta_2$ and $\beta = f^{\otimes}[\alpha]$. Suppose $\alpha_1, \alpha_2$ are such that $f^{\otimes}[\alpha_i] = \beta_i$. Then all the words in $\alpha_i$ must have length 1. Hence if $\alpha_1 + \alpha_2 = \alpha$, both of them must contain $a$ and $b$: then $a + b \in \alpha_1 + \alpha_2$ and $\alpha_1 + \alpha_2 \neq \alpha$.

**MP $\Rightarrow$ PM:** Here $\mathbf{M} = \bar{\mathbf{M}}$ is the monad of (finite) multisets, also written as finite $\mathbb{N}$-linear combinations: if $A$ is a commutative monoid with unit 0 and addition $\oplus$, $\mathbf{M}A$ is a commutative monoid with unit $1 \cdot 0$ and addition $(\sum_i \alpha_i \cdot a_i) \oplus (\sum_j \beta_j \cdot b_j) = \sum_{i,j} \alpha_i \beta_j \cdot (a_i \oplus b_j)$.

The counter-example for $\mathbf{P}$ can be adapted: $(1 \cdot a) \oplus (2 \cdot a) = 2 \cdot (a \oplus a) = (\mathbf{M}f^{\otimes})(1 \cdot (a \oplus a) + 1 \cdot (b \oplus b))$. If there are $\alpha_1, \alpha_2 \in \mathbf{M}\{a, b\}^{\otimes}$ such that $(\mathbf{M}f^{\otimes})(\alpha_1) = 1 \cdot a, (\mathbf{M}f^{\otimes})(\alpha_2) = 2 \cdot a$ and $\alpha_1 \oplus \alpha_2 = 1 \cdot (a \oplus a) + 1 \cdot (b \oplus b)$, then $\alpha_1 = x_a \cdot a + x_b \cdot b$ and $\alpha_2 = y_a \cdot a + y_b \cdot b$ where $x_a, x_b, y_a, y_b \in S$ are such that $x_a + x_b = 1, y_a + y_b = 1 + 1, x_a y_a = x_b y_b = 1$ and $x_a y_b + x_b y_a = 0$. These equations do not have common solutions in $\mathbb{N}$, and so such $\alpha_1$ and $\alpha_2$ cannot exist.

**DP $\Rightarrow$ PD:** Here $\mathbf{D} = \bar{\mathbf{D}}$ is the monad of finitely-supported probability distributions on a monoid: if $A$ is a commutative monoid with unit 0, $\mathbf{D}A$ is a commutative monoid with unit $\delta_0$ and addition $(\alpha_1 + \alpha_2)(a) = \sum_{a_1+a_2=a} \alpha(a_1)\beta(a_2)$. The counter-example for $\mathbf{P}$ can be adapted:

$$ \delta_{2a} = \delta_a + \delta_a = (\mathbf{D}f)(\delta_{2a}/2 + \delta_{2b}/2) \quad \square $$

## 6. CONCLUSION

Noticing the similarity between the laws $\mathbf{VV} \Rightarrow \mathbf{VV}$ and $\mathbf{PP} \Rightarrow \mathbf{PP}$, we developed the theory for weakly lifting weak distributive laws and showed that it only applied partially in this case. We then focused on the monotonicity of the laws, and gave full characterizations for the existence of monotone weak distributive laws over weakly lifted powerset monads in categories of algebras, by characterizing the Kleisli categories of the latters – a key notion appearing then being that of decomposable morphisms. We finally applied this result to exhibit a new law $\mathbf{RV}_* \Rightarrow \mathbf{V}_*\mathbf{R}$ for combining probability and non-determinism in $\mathbf{KHaus}$, but also to show that in general these monotone weak distributive laws seem to be quite rare.

We leave for further work the development of a full 2-categorical theory for iterating weak distributive laws (in the vein of [Che11, Böh12]), which would complete Section 3 but would likely be scarce in new examples. With monotone laws over powerset-like monads fully characterized, another natural question is now whether this can be done in other settings, e.g. in Pos-regular categories [KV17] or over other monads: the multiset monad for instance is a good candidate as its Kleisli category can also be described through spans. Finally, the
author believes it would be interesting to tranpose the results of Section 5 in the setting of monoidal topology [HST14], where categories of algebras for nearly cartesian monads generalize the category of compact Hausdorff spaces in a formal sense: perhaps for instance the weakly lifted powerset monads we study are a generalization of the Vietoris monads of topological spaces.

## REFERENCES

[Ari25] Quentin Aristote. Monotone Weak Distributive Laws over the Lifted Powerset Monad in Categories of Algebras. In Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng, editors, *42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)*, volume 327 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 10:1–10:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.10, doi:10.4230/LIPIcs.STACS.2025.10.

[Bar70] Michael Barr. Relational algebras. In S. MacLane, editor, *Reports of the Midwest Category Seminar IV*, volume 137 of *Lecture Notes in Mathematics*, pages 39–55, Berlin, Heidelberg, 1970. Springer Berlin Heidelberg. URL: https://link.springer.com/chapter/10.1007/BFb0060439, doi:10.1007/BFb0060439.

[Bec69] Jon Beck. Distributive laws. In B. Eckmann, editor, *Seminar on Triples and Categorical Homology Theory*, volume 80 of *Lecture Notes in Mathematics*, pages 119–140, Berlin, Heidelberg, 1969. Springer. URL: https://link.springer.com/chapter/10.1007/BFb0083084, doi:10.1007/BFb0083084.

[BLS11] Gabriella Böhm, Stephen Lack, and Ross Street. On the 2-Categories of Weak Distributive Laws. *Communications in Algebra*, 39(12):4567–4583, December 2011. doi:10.1080/00927872.2011.616436.

[BLS12] Gabriella Böhm, Stephen Lack, and Ross Street. Idempotent splittings, colimit completion, and weak aspects of the theory of monads. *Journal of Pure and Applied Algebra*, 216(2):385–403, February 2012. URL: https://www.sciencedirect.com/science/article/pii/S0022404911001678, doi:10.1016/j.jpaa.2011.07.003.

[Böh10] Gabriella Böhm. The weak theory of monads. *Advances in Mathematics*, 225(1):1–32, September 2010. URL: https://www.sciencedirect.com/science/article/pii/S0001870810000794, doi:10.1016/j.aim.2010.02.015.

[Böh12] Gabriella Böhm. On the iteration of weak wreath products. *Theory and Applications of Categories*, 26(2):30–59, 2012. URL: http://www.tac.mta.ca/tac/volumes/26/2/26-02abs.html.

[Bor94a] Francis Borceux. *Handbook of Categorical Algebra: Volume 1: Basic Category Theory*, volume 1 of *Encyclopedia of Mathematics and Its Applications*. Cambridge University Press, Cambridge, 1994. URL: https://www.cambridge.org/core/books/handbook-of-categorical-algebra/A0B8285BBA900AFE85EED8C971E0DE14, doi:10.1017/CB09780511525858.

[Bor94b] Francis Borceux. *Handbook of Categorical Algebra: Volume 2: Categories and Structures*, volume 2 of *Encyclopedia of Mathematics and Its Applications*. Cambridge University Press, Cambridge, 1994. URL: https://www.cambridge.org/core/books/handbook-of-categorical-algebra/EF86DCA2B6B7BBA10CE255ABC572601B, doi:10.1017/CB09780511525865.

[BS22] Filippo Bonchi and Alessio Santamaria. Convexity via Weak Distributive Laws. *Logical Methods in Computer Science*, Volume 18(4), November 2022. URL: https://lmcs.episciences.org/10356, doi:10.46298/lmcs-18(4):8, 2022.

[CCT14] Maria Manuel Clementino, Eva Colebunders, and Walter Tholen. Lax algebras as spaces. In Dirk Hofmann, Gavin J. Seal, and Walter Tholen, editors, *Monoidal Topology: A Categorical Approach to Order, Metric, and Topology*, Encyclopedia of Mathematics and Its Applications, pages 375–466. Cambridge University Press, Cambridge, 2014. URL: https://www.cambridge.org/core/books/monoidal-topology/lax-algebras-as-spaces/BF54776571213BBC8013FCF1C8C5284F, doi:10.1017/CB09781107517288.007.

[Che11] Eugenia Cheng. Iterated distributive laws. *Mathematical Proceedings of the Cambridge Philosophical Society*, 150(3):459–487, May 2011. URL: https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/
article/abs/iterated-distributive-laws/298823170C90C7FB9606C61E49E9A9B7,
doi: 10.1017/S0305004110000599.

[CKW91] A. Carboni, G. M. Kelly, and R. J. Wood. A 2-categorical approach to change of base and geometric morphisms I. *Cahiers de Topologie et Géométrie Différentielle Catégoriques*, 32(1):47–95, 1991. URL: http://www.numdam.org/item/?id=CTGDC_1991__32_1_47_0.

[de 92] Oege de Moor. *Categories, Relations and Dynamic Programming*. PhD thesis, University of Oxford, 1992. URL: https://www.cs.ox.ac.uk/files/3427/PRG98.pdf.

[DE72] Seymour Z. Ditor and Larry Q. Eifler. Some Open Mapping Theorems for Measures. *Transactions of the American Mathematical Society*, 164:287–293, 1972. URL: https://www.jstor.org/stable/1995975, arXiv:1995975, doi:10.2307/1995975.

[DN18] Fredrik Dahlqvist and Renato Neves. Compositional semantics for new paradigms: Probabilistic, hybrid and beyond, April 2018. URL: http://arxiv.org/abs/1804.04145, arXiv:1804.04145, doi:10.48550/arXiv.1804.04145.

[FS90] Peter John Freyd and Andre Scedrov. *Categories, Allegories*. Number 39 in North-Holland Mathematical Library. Elsevier Science Publishers, Amsterdam, January 1990. URL: https://www.sciencedirect.com/bookseries/north-holland-mathematical-library/vol/39/suppl/C.

[Gar19] Richard Garner. The Vietoris Monad and Weak Distributive Laws. *Applied Categorical Structures*, 28(2):339–354, 2019. doi:10.1007/s10485-019-09582-w.

[Gou24] Jean Goubault-Larrecq. Weak Distributive Laws between Monads of Continuous Valuations and of Non-Deterministic Choice, August 2024. URL: http://arxiv.org/abs/2408.15977, arXiv:2408.15977, doi:10.48550/arXiv.2408.15977.

[Goy21] Alexandre Goy. *On the Compositionality of Monads via Weak Distributive Laws*. PhD thesis, Université Paris-Saclay, October 2021. URL: https://theses.hal.science/tel-03426949.

[Goy23] Alexandre Goy. Weakening and Iterating Laws using String Diagrams. *Electronic Notes in Theoretical Informatics and Computer Science*, Volume 1(Proceedings of MFPS XXXVIII), February 2023. URL: https://entics.episciences.org/10482, doi:10.46298/entics.10482.

[GP20] Alexandre Goy and Daniela Petrişan. Combining probabilistic and non-deterministic choice via weak distributive laws. In *Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science*, LICS '20, pages 454–464, New York, NY, USA, July 2020. Association for Computing Machinery. URL: https://dl.acm.org/doi/10.1145/3373718.3394795, doi:10.1145/3373718.3394795.

[GPA21] Alexandre Goy, Daniela Petrişan, and Marc Aiguier. Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, *48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)*, volume 198 of Leibniz International Proceedings in Informatics (Lipics), pages 132:1–132:14, Dagstuhl, Germany, 2021. Schloss-Dagstuhl - Leibniz Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.132, doi:10.4230/LIPIcs.ICALP.2021.132.

[HST14] Dirk Hofmann, Gavin J. Seal, and Walter Tholen, editors. *Monoidal Topology: A Categorical Approach to Order, Metric, and Topology*. Number 153 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 2014. URL: https://www.cambridge.org/core/books/monoidal-topology/8E35730B51B8292860787A842965090B, doi: 10.1017/CBO9781107517288.

[KP17] Klaus Keimel and Gordon D. Plotkin. Mixed powerdomains for probability and nondeterminism. *Logistical Methods in Computer Science*, Volume 13(1), January 2017. URL: https://lmcs.episciences.org/2665, doi:10.23638/LMCS-13(1:2)2017.

[KS18] Bartek Klin and Julian Salamanca. Iterated Covariant Powerset is not a Monad. *Electronic Notes in Theoretical Computer Science*, 341(Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV)):261–276, December 2018. URL: https://www.sciencedirect.com/science/article/pii/S157106611830094X, doi:10.1016/j.entcs.2018.11.013.

[KV17] Alexander Kurz and Jiří Velebil. Quasivarieties and varieties of ordered algebras: Regularity and exactness. *Mathematical Structures in Computer Science*, 27(7):1153–1194, October 2017. URL: https://www.cambridge.org/core/journals/mathematical-structures-in-computer-science/
article/quasivarieties-and-varieties-of-ordered-algebras-regularity-and-exactness/FFF6C18FD1D7BAF8712AC60F757A3546, doi:10.1017/S096012951500050X.

[Man69] Ernest Manes. A triple theoretic construction of compact algebras. In H. Appelgate, M. Barr, J. Beck, F. W. Lawvere, F. E. J. Linton, E. Manes, M. Tierney, F. Ulmer, and B. Eckmann, editors, *Seminar on Triples and Categorical Homology Theory*, pages 91–118, Berlin, Heidelberg, 1969. Springer Berlin Heidelberg.

[ML78] Saunders Mac Lane. *Categories for the Working Mathematician*. Number 5 in Graduate Texts in Mathematics. Springer Science+Business Media, New York, NY, 2 edition, 1978. doi:10.1007/978-1-4757-4721-8.

[MM07] Ernie Manes and Philip Mulry. Monad compositions I: General constructions and recursive distributive laws. *Theory and Applications of Categories*, 18:172–208, 2007. URL: https://eudml.org/doc/128434.

[Mog89] E. Moggi. Computational lambda-calculus and monads. In *Proceedings. Fourth Annual Symposium on Logic in Computer Science*, pages 14–23. IEEE, June 1989. URL: https://ieeexplore.ieee.org/document/39155, doi:10.1109/LICS.1989.39155.

[PS21] Daniela Petrisan and Ralph Sarkis. Semialgebras and Weak Distributive Laws. In *Proceedings 37th Conference on Mathematical Foundations of Programming Semantics*, volume 351 of *Electronic Proceedings in Theoretical Computer Science*, pages 218–241. Open Publishing Association, 2021. doi:10.4204/EPTCS.351.14.

[RS90] Anna B. Romanowska and Jonathan D. H. Smith. On the Structure of Barycentric Algebras. *Houston Journal of Mathematics*, 16(3):431–448, 1990. URL: https://www.math.uh.edu/~hjm/restricted/archive/v016n3/0431ROMANOWSKA.pdf.

[Rud87] Walter Rudin. *Real and Complex Analysis*. McGraw-Hill, Singapore, 3 edition, 1987.

[Str09] Ross Street. Weak distributive laws. *Theory and Applications of Categories*, 22(12):313–320, 2009. URL: http://www.tac.mta.ca/tac/volumes/22/12/22-12abs.html.

[VW06] Daniele Varacca and Glynn Winskel. Distributing probability over non-determinism. *Mathematical Structures in Computer Science*, 16(1):87–113, February 2006. URL: https://www.cambridge.org/core/journals/mathematical-structures-in-computer-science/article/distributing-probability-over-nondeterminism/195D12D2F23B89E37DA8E70C4C56CBF6, doi:10.1017/S0960129505005074.

[WS24] Harald Woracek and Ana Sokolova. Re: Decomposing convex subsets of simplices along free morphisms, June 2024.

[Wyl91] Oswald Wyler. *Lecture Notes on Topoi and Quasitopoi*. World Scientific, 1991. URL: https://www.worldscientific.com/worldscibooks/10.1142/1047, doi:10.1142/1047.

[ZM19] Maaike Zwart and Dan Marsden. No-Go Theorems for Distributive Laws. In *2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)*, pages 1–13. IEEE, June 2019. URL: https://ieeexplore.ieee.org/document/8785707, doi:10.1109/LICS.2019.8785707.