Connected monads weakly preserve products

Abstract

If F is a (not necessarily associative) monad on Set, then the natural transformation $F(A\times B)\rightarrow F(A)\times F(B)$ is surjective if and only if $F(\varvec{1})=\varvec{1}$. Specializing F to $F_{\mathcal {V}}$, the free algebra functor for a variety $\mathcal {V},$ this result generalizes and clarifies an observation by Dent, Kearnes and Szendrei in 2012.

1 Introduction

A key observation in [2] by T. Dent, K. Kearnes, and Á. Szendrei is that for any variety $\mathcal {V}$ with idempotent operations each set theoretic product decomposition

$$\begin{aligned} d:\{x,y,z,u\}\twoheadrightarrow \{a,b\}\times \{a,b\} \end{aligned}$$

extends to a surjective homomorphism

$$\begin{aligned} \delta :F_{\mathcal {V}}(\{x,y,z,u\})\twoheadrightarrow F_{\mathcal {V}}(\{a,b\})\times F_{\mathcal {V}}(\{a,b\}) \end{aligned}$$

(1.1)

from the 4-generated free algebra in $\mathcal {V}$ to the square of the 2-generated one.

This fact has an interesting geometric interpretation, which is relevant in the study of congruence modularity. The shifting lemma from [9], which is concerned with shifting a congruence $\gamma$ from one side of an $\alpha -\beta$-parallelogram to the opposite side modulo $\alpha \wedge \beta$, can be specialized to axis-parallel rectangles inside a product of algebras where $\alpha$ and $\beta$ are in fact kernels of the projections and $\gamma$ a factor congruence.

Surjectivity of the above map implies that the projections on the image commute, and since ${{\,\mathrm{Ker}\,}}\delta =\alpha \wedge \beta$, it follows that $\alpha$ and $\beta$ also commute in the preimage. In particular, therefore, the shifting lemma, which in [9] is the major geometrical tool for studying congruence modularity, is only needed in situations of permuting congruence relations $\alpha$ and $\beta$. The restriction to idempotent varieties in these studies is not severe, since a variety is congruence modular iff its idempotent reduct is congruence modular.

Variations of the shifting lemma (e.g. [1]) and, more recently, categorical generalizations as in [3] suggest to investigate the situation in a more general context. In this note, therefore, rather than exploring further ramifications of the above observation, we explore the abstract reasons behind the surjectivity of $\delta$ in (1.1). It turns out that we can deal with this in a framework which is more abstract than universal algebras and varieties. We are rather considering (not necessarily associative) Set-monads F, of which the functor $F_{\mathcal {V}}$, which associates with a set X the free algebra $F_{\mathcal {V}}(X)$ and with a map $g:X\rightarrow Y$ its unique homomorphic extension $\bar{g}:F_{\mathcal {V}}(X)\rightarrow F_{\mathcal {V}}(Y)$, is just an example.

2 Monads and main result

Monads on a category $\mathcal {C}$ are functors $F:\mathcal {C}\rightarrow \mathcal {C}$ together with two natural transformations $\iota :Id\rightarrow F$ and $\mu :F\circ F\rightarrow F$, satisfying two unit laws and an associative law. Our results will even hold for nonassociative monads, so skipping the associative law, we shall only state the unit laws:

$$\begin{aligned} \mu _{X}\circ \iota _{F(X)}=id_{F(X)}=\mu _{X}\circ F\iota _{X} \end{aligned}$$

(2.1)

Equations (2.1) are usually expressed as a commutative diagram:

Rather easy examples of monads on the category of sets are obtained from collection data types in programming, such as $List\langle X\rangle$, $Set\langle X\rangle$ or $Tree\langle X\rangle ;$ see also [11]. In popular programming languages, $List\langle X\rangle$ denotes the type of lists of elements from a base type X. Given a function $g:X\rightarrow Y$, the function $map(g):List\langle X\rangle \rightarrow List\langle Y\rangle$ which sends $[x_{1},\dots ,x_{n}]\in List\langle X\rangle$ to the list $[g(x_{1}),\dots ,g(x_{n})]\in List\langle Y\rangle$ represents the action of the functor List on maps. In mathematical notation we write (List g) rather than map(g). Obviously, $map(f\circ g)=map(f)\circ map(g)$ and $map(id_{X})=id_{List\langle X\rangle },$ so the pair $List\langle -\rangle$ with map indeed establishes a functor.

For List to be a monad, we need a natural transformation $\iota :Id\rightarrow List$, as well as a “multiplication” $\mu :List\circ List\rightarrow List$. The former can be chosen as the singleton operator with $\iota _{X}:X\rightarrow List\langle X\rangle$ sending any $x\in X$ to the one-element list [x].

The monad multiplication $\mu$ is for each type X defined as

$$\begin{aligned} \mu _{X}:List\langle List\langle X\rangle \rangle \rightarrow List\langle X\rangle , \end{aligned}$$

taking a list of lists $[l_{1},\dots ,l_{n}]$ and appending them into a single list $l_{1}+\dots +l_{n}$. Programmers call this operation “flatten”. The unit laws then state that for each list $l=[x_{1},\dots ,x_{n}]\in List\langle X\rangle$ we should have

$$\begin{aligned} flatten([\,[x_{1},\dots ,x_{n}]\,])=[x_{1},\dots ,x_{n}]=flatten([\,[x_{1}],\dots ,[x_{n}]\,]), \end{aligned}$$

which is obvious. Not all monads arise from collection classes, and other uses of monads have all but revolutionized functional programming, see e.g. [12] or [15].

Relevant for universal algebraists is the fact that for every variety $\mathcal {V}$ the construction of the free algebra $F_{\mathcal {V}}(X)$ over a set X is a monadic functor. In this case, $\iota _{X}:X\rightarrow F_{\mathcal {V}}(X)$ is the inclusion of variables, or rather their interpretations as $\mathcal {V}-$terms.

The defining property of $F_{\mathcal {V}}(X)$ states that each map $g:X\rightarrow A$ for $A\in \mathcal {V}$ has a unique homomorphic extension $\bar{g}:F_{\mathcal {V}}(X)\rightarrow A$.

From a map $f:X\rightarrow Y$, we therefore obtain the homomorphism

$$\begin{aligned} F_{\mathcal {V}}f:F_{\mathcal {V}}(X)\rightarrow F_{\mathcal {V}}(Y) \end{aligned}$$

as the unique homomorphic extension of the composition $\iota _{Y}\circ f:X\rightarrow F_{\mathcal {V}}(Y)$:

The flattening map $\mu :F_{\mathcal {V}}(F_{\mathcal {V}}(X))\rightarrow F_{\mathcal {V}}(X)$ can be considered as term composition: a term $t(t_{1},\dots ,t_{n}),$ whose argument positions have been filled by other terms, is interpreted as an honest $\mathcal {V}$-term. To make this precise, consider the diagram below, in which $F_{\mathcal {V}}(X)$ appears in two roles – in the top row as an algebra and in the bottom row as a set of free variables for $F_{\mathcal {V}}(F_{\mathcal {V}}(X))$.

The left square is obtained by instantiating the previous diagram with $Y:=F_{\mathcal {V}}(X)$ and $f:=\iota _{X}$. The right hand triangle defines $\mu _{X}$ as the homomorphic extension of the identity map $id_{F_{\mathcal {V}}(X)}$ from $F_{\mathcal {V}}(X)$, considered as set of free variables for $F_{\mathcal {V}}(F_{\mathcal {V}}(X))$, to $F_{\mathcal {V}}(X)$ considered as a $\mathcal {V}$-algebra.

The first monad equation immediately follows from the definition of $\mu ,$ and the second equation

$$\begin{aligned} \mu _{X}\circ (F_{\mathcal {V}}\iota _{X})=id_{F_{\mathcal {V}}(X)} \end{aligned}$$

follows from the fact that both the left hand side and the right hand side of this equation are homomorphic extensions of $\iota _{X}:X\rightarrow F_{\mathcal {V}}(X),$ as can be read from the diagram, so they must be equal.

The earlier mentioned examples $Tree\langle X\rangle$, $List\langle X\rangle ,$ and $Set\langle X\rangle ,$ just correspond to the free groupoid, the free semigroup, and the free semilattice over the set X of generators, and are themselves instances of this scheme.

We are now ready to state our main result.

Theorem 2.1

A (not necessarily associative) Set-monad F weakly preserves products if and only if $F(\varvec{1})\cong \varvec{1}$.

It will be easy to see (Lemma 4.6 below) that Fweakly preserves the product$A_{1}\times A_{2}$ if and only if the canonical morphism $\delta =(F\pi _{1},F\pi _{2})$ in the below diagram is epi:

(2.2)

The starting point of our discussion, (1.1) from [2], is therefore seen to represent an instance of this result when setting $A_{1}=A_{2}=\{a,b\}$ and $F=F_{\mathcal {V}}$. But before coming to its proof we need a few preparations.

3 Connected functors

Put $\varvec{1}=\{0\}$ and for any set X denote by $!_{X}$ the unique (terminal) map from X to $\varvec{1}$. A Set-functor F is called connected if $F(\varvec{1})\cong \varvec{1}$. Given a variety $\mathcal {V}$, the functor $F_{\mathcal {V}}$ is connected if and only if $\mathcal {V}$ is idempotent.

It is well known, see [14], that every Set-Functor F can be constructed as a sum of connected functors:

$$\begin{aligned} F=\Sigma _{e\in F(\varvec{1})}F_{e}. \end{aligned}$$

For $e\in F(\varvec{1})$ one simply puts $F_{e}(X)=\{u\in F(X)\mid (F!_{X})(u)=e\}.$ On maps $f:X\rightarrow Y$, each subfunctor $F_{e}$ is just the domain-codomain-restriction of Ff to $F_{e}(X)$.

In the following we denote by $c_{y}^{X}:X\rightarrow Y$ or, if X is clear, simply by $c_{y},$ the constant map with value $y\in Y.$ We shall need the following lemma:

Lemma 3.1

If F is a connected functor, then $Fc_{y}^{X}$ is a constant map. Whenever $\iota :Id\rightarrow F$ is a natural transformation, then $Fc_{y}^{X}=c_{\iota _{Y}(y)}^{F(X)}$.

Proof For $y\in Y,$ denote by $\bar{y}:\varvec{1}\rightarrow Y$ the constant map with value y. Observe, that an arbitrary map f is constant if and only if it factors through $\varvec{1},$ i.e. $c_{y}^{X}=\bar{y}\,\circ \,!_{X}$. Applying F and adding the natural transformation $\iota$ into the picture,

we obtain:

$$\begin{aligned} Fc_{y}^{X}&= F\bar{y}\circ F!_{X}\\&= F\bar{y}\circ \iota _{\varvec{1}}\,\circ \,!_{F(X)}\\&= \iota _{Y}\circ \bar{y}\,\circ \,!_{F(X)}\\&= \overline{\iota _{Y}(y)}\,\circ \,!_{F(X)}\\&= c_{\iota _{Y}(y)}^{F(X)}. \end{aligned}$$

$\square$

In the above, we have seen that connected functors preserve constant maps. It might be interesting to remark that this very property characterizes connected functors:

Corollary 3.2

A functor F is connected if and only if for every constant morphism $c_{y}$ the morphism $Fc_{y}$ is constant, again.

Proof

Suppose that F preserves constant maps. As $id_{\varvec{1}}$ is constant, $F(id_{\varvec{1}})=id_{F(\varvec{1})}$ must also be constant, which implies $F(\varvec{1})\cong \varvec{1}$. $\square$

In general, the elements of $F(\varvec{1})$ correspond uniquely to the natural transformations between the identity functor Id and F. This can be seen by instantiating the Yoneda Lemma

$$\begin{aligned} nat(Hom(A,-),F)\cong F(A) \end{aligned}$$

(3.1)

with $A=\varvec{1}.$ Therefore we note:

Corollary 3.3

A monad $(F,\iota ,\mu )$ is connected if and only if $\iota$ is the only transformation from the identity functor to F.

Definition 3.4

Let $\mathcal {C}_{\varvec{1}}$ be the constant functor with $\mathcal {C}_{\varvec{1}}(X)=\varvec{1}$ for all X and $\mathcal {C}_{\varvec{1}}f=id_{\varvec{1}}$ for all f. We say that a functor Fpossesses a constant, if there is a transformation from $\mathcal {C}_{\varvec{1}}$ to F which is natural, except perhaps at $X=\emptyset$.

Clearly, each element of $F(\emptyset )$ gives rise to a constant, but not conversely, since there is nothing to stop us from changing F only on the empty set $\emptyset$ and on empty maps $\emptyset _{X}:\emptyset \rightarrow X$ by choosing any $U\subseteq F(\emptyset )$ and redefining $F'(\emptyset ):=U$ as well as $F'\emptyset _{X}=F\emptyset _{X}\circ \subseteq _{U}^{X}.$ For that reason we do not require naturality at $\emptyset$ in the above definition.

We shall need the following observation:

Lemma 3.5

A connected functor either possesses a constant or it has the identity functor as a subfunctor.

Proof

By the Yoneda Lemma, there is exactly one natural transformation $\iota :Id\rightarrow F$. Assume that some $\iota _{X}$ is not injective, then there are $x_{1}\ne x_{2}\in X$ with $\iota _{X}(x_{1})=\iota _{X}(x_{2})$. Given an arbitrary Y with $y_{1},y_{2}\in Y,$ consider a map $f:X\rightarrow Y$with $f(x_{1})=y_{1}$ and $f(x_{2})=y_{2}$. By naturality,

$$\begin{aligned} \iota _{Y}(y_{1})=\iota _{Y}(f(x_{1}))=Ff\circ \iota _{X}(x_{1})=Ff\circ \iota _{X}(x_{2})=\iota _{Y}(y_{2}), \end{aligned}$$

hence each $\iota _{Y}$ is constant and therefore factors through $\varvec{1}$. This makes the upper and lower triangle inside the following naturality square commute, too.

The left triangle commutes since $\varvec{1}$ is terminal. If $X\ne \emptyset$, the terminal map $!_{X}:X\rightarrow \varvec{1}$ is epi, from which we now conclude that the right triangle commutes as well, except, possibly, when $X=\emptyset$. Thus F possesses a constant. $\square$

4 Preservation properties

We are concerned with the question, under which conditions the $\delta$ in equation (1.1) is epi. Therefore, we take a look at the canonical map $\delta =(F\pi _{1},F\pi _{2}):F(A_{1}\times A_{2})\rightarrow F(A_{1})\times F(A_{2})$ which arises from the commutative diagram (2.2), where $\pi _{i},$ resp $\eta _{i},$ denote the canonical component projections.

The first thing to observe is:

Lemma 4.1

$\delta =(F\pi _{1},F\pi _{2}):F(A_{1}\times A_{2})\rightarrow FA_{1}\times FA_{2}$ is natural in each component.

Proof Assume $f:A_{1}\rightarrow A_{1}'$ and $g:A_{2}\rightarrow A_{2}'$ are given. We want to show that the following diagram commutes:

We calculate:

$$\begin{aligned} ((Ff\times Fg)\circ (F\pi _{1},F\pi _{2}))(u)&= (Ff\times Fg)((F\pi _{1})(u),(F\pi _{2})(u))\\&= ((Ff\circ F\pi _{1})(u),(Fg\circ F\pi _{2})(u))\\&= (F(f\circ \pi _{1})(u),F(g\circ \pi _{2})(u))\\&= (F(\pi _{1}'\circ f\times g)(u),F(\pi _{2}'\circ f\times g)(u))\\&= ((F\pi _{1}'\circ F(f{\times }g))(u){,}(F\pi _{2}'\circ F(f{\times }g))(u))\\&= (F(\pi _{1}')(F(f{\times }g)(u)){,}F(\pi _{2}')(F(f{\times }g)(u)))\\&= (F\pi _{1}'{,}F\pi _{2}')(F(f{\times }g)(u))\\&= ((F\pi _{1}',F\pi _{2}')\circ F(f\times g))(u). \square \end{aligned}$$

Notice that in order for $\delta$ to be surjective, the functor F must be connected or trivial.

Lemma 4.2

If the canonical decomposition as in Theorem 2.1 is always epi, then either $F(\varvec{1})\cong \varvec{1}$ or F is the trivial functor with constant value $\emptyset$.

Proof

For the projections $\pi _{1},\pi _{2}:\varvec{1}\times \varvec{1}\rightarrow \varvec{1}$ we have $\pi _{1}=\pi _{2},$ since $\varvec{1}$ is a terminal object, hence also $F\pi _{1}=F\pi _{2}$. Let $\eta _{1},\eta _{2}$ be the projections from the product $F(\varvec{1})\times F(\varvec{1})$ to its components. Then

$$\begin{aligned} \eta _{1}\circ (F\pi _{1},F\pi _{2})=F\pi _{1}=F\pi _{2}=\eta _{2}\circ (F\pi _{1},F\pi _{2}). \end{aligned}$$

By assumption, $\delta =(F\pi _{1},F\pi _{2})$ is epi, so $\eta _{1}=\eta _{2}$. For arbitrary $a,b\in F(\varvec{1})$ then $(a,b)\in F(\varvec{1})\times F(\varvec{1}),$ so

$$\begin{aligned} a=\eta _{1}(a,b)=\eta _{2}(a,b)=b. \end{aligned}$$

So $F(\varvec{1})$ either has just one element, or $F(\varvec{1})=\emptyset$. In the latter case, for each set X the map $!_{X}:X\rightarrow \varvec{1}$ should yield a map $F!_{X}:F(X)\rightarrow F(\varvec{1}),$ so $F(\varvec{1})=\emptyset$ implies $F(X)=\emptyset .$$\square$

Next, recall some elementary categorical notions.

Definition 4.3

Given objects $A_{1},A_{2}$ in a category $\mathcal {C}$, a product of$A_{1}$and$A_{2}$ is an object P together with morphisms $p_{i}:P\rightarrow A_{i}$, such that for any “competitor”, i.e. for any object Q with morphisms $q_{i}:Q\rightarrow A_{i}$, there exists a unique morphism $d:Q\rightarrow P$, such that $q_{i}=p_{i}\circ d$ for $i=1,2.$ Products, if they exist, are unique up to isomorphism and are commonly written $A_{1}\times A_{2}$.

Similarly, given morphisms $f_{1}:A_{1}\rightarrow B$ and $f_{2}:A_{2}\rightarrow B$ with common codomain B,  their pullback is defined to be a pair of maps $p_{1}:P\rightarrow A_{1}$ and $p_{2}:P\rightarrow A_{2}$ with common domain P such that

$$\begin{aligned} f_{1}\circ p_{1}=f_{2}\circ p_{2} \end{aligned}$$

and for each “competitor”, i.e. each object Q with morphisms $q_{1}:Q\rightarrow A_{1}$ and $q_{2}:Q\rightarrow A_{2}$ also satisfying $f_{1}\circ q_{1}=f_{2}\circ q_{2}$ there exists a unique morphism $d:Q\rightarrow P$ so that $p_{i}\circ d=q_{i}$ for $i=1,2$ (see Figure 1).

In both definitions, if we drop the uniqueness requirement, we obtain the definition of weak product, resp. weak pullback.

Fig. 1

(Weak) pullback and (weak) product

Notice that in case there exists a terminal object $\varvec{1}$, the product of $A_{1}$ with $A_{2}$ is the same as the pullback of the terminal morphisms $!_{A_{i}}:A_{i}\rightarrow \varvec{1}$.

Weak products (weak pullbacks) arise from right invertible morphisms into products (pullbacks):

Lemma 4.4

If $(P,p_{1},p_{2})$ is a product (resp. pullback), then $(W,w_{1},w_{2})$ is a weak product (resp. weak pullback) if and only if there is a right invertible $w:W\rightarrow P$ such that $w_{i}=p_{i}\circ w$.

Proof

If w has a right inverse e, and $(Q,q_{1},q_{2})$ is a competitor to W,  then it is also a competitor to P,  hence there is a morphism $d:Q\rightarrow P$ with $q_{i}=p_{i}\circ d$. Then $e\circ d$ is the required morphism to W. Indeed,

$$\begin{aligned} w_{i}\circ (e\circ d)=p_{i}\circ w\circ e\circ d=p_{i}\circ d=q_{i}. \end{aligned}$$

Conversely, assume that $(W,w_{1},w_{2})$ is a weak product, then both W and P are competitors to each other, yielding both a morphism $w:W\rightarrow P$ with $w_{i}=p_{i}\circ w$ and a morphism $e:P\rightarrow W$ with $p_{i}=w_{i}\circ e$.

Now $(P,p_{1},p_{2})$ is also a competitor to itself, yet both $p_{i}\circ (w\circ e)=p_{i}$ and $p_{i}\circ id_{P}=p_{i}$ for $i=1,2$. By uniqueness it follows that $w\circ e=id_{P},$ so w is indeed right invertible. (The same proof works for the case of weak pullbacks).

$\square$

Definition 4.5

Let $F:\mathcal {C}\rightarrow \mathcal {D}$ be a functor. We say that Fweakly preserves products (pullbacks) if whenever $(P,p_{1},p_{2})$ is a product (pullback), then its image $(F(P),Fp_{1},Fp_{2})$ is a weak product (weak pullback).

It is well known that a functor weakly preserves a limit L if and only it preserves weak limits, see e.g. [5]. Surjective maps are right invertible, so regarding (1.1) or its more general formulation (2.2), we now arrive at the following relevant observation:

Lemma 4.6

The canonical map $\delta$ in (2.2) is epi if and only if F weakly preserves the product $(A_{1}\times A_{2},\pi _{1},\pi _{2})$.

Whereas the above mentioned result of [2], in which the monad F is the free-algebra-functor $F_{\mathcal {V}},$ served a purely universal algebraic purpose, it also has an interesting coalgebraic interpretation. It is well known that coalgebraic properties of classes of F-coalgebras are to a large degree determined by weak pullback preservation properties of the functor F, which serves as a type or signature for a class $Coalg_{F}$ of coalgebras. Prominent structure theoretic properties can be derived from the assumptions that F weakly preserves pullbacks of preimages, kernel pairs or both, see e.g. [4,5,6,7,8, 13]. Here we add one more property to this list: preservation of pullbacks of constant maps.

Theorem 4.7

Let F be a nontrivial functor. Then the following are equivalent:

• (1) F has no constant and weakly preserves products.

• (2) F is connected and weakly preserves pullbacks of constant maps.

Proof

If F is nontrivial and weakly preserves the product $\varvec{1}\times \varvec{1}\cong \varvec{1}$, then F is connected as a consequence of Lemma 4.2. Since F has no constants, $F(\emptyset )=\emptyset$ and moreover Lemma 3.5 provides Id as a subfunctor of F. Thus we obtain a natural transformation $\iota :Id\rightarrow F$ which is injective in each component.

Let now $c_{y_{i}}^{X_{i}}:X_{i}\rightarrow Y$ for $i=1,2$ be constant maps with $y_{i}\in Y$. Applying F, Lemma 3.1 yields $Fc_{y_{i}}^{X_{i}}=c_{\iota _{Y}(y_{i})}^{F(X_{i})}$ for $i=1,2.$

If $y_{1}=y_{2}$ then the pullback of the $c_{y_{i}}^{X_{i}}$ is simply $(X_{1}\times X_{2},\pi _{1},\pi _{2})$. The $Fc_{y_{i}}^{X_{i}}$ are constant maps with the same target value $\iota _{Y}(y_{1})=\iota _{Y}(y_{2}),$ so their pullback is the product $F(X_{1})\times F(X_{2})$ with canonical projections $\eta _{i}:F(X_{1})\times F(X_{2})\rightarrow F(X_{i})$. By assumption, F weakly preserves products, which gives us a surjective canonical map $\delta :F(X_{1}\times X_{2})\rightarrow F(X_{1})\times F(X_{2})$ with $F\pi _{i}=\eta _{i}\circ \delta$, so Lemma 4.4 ensures that $(F(X_{1}\times X_{2}),F\pi _{1},F\pi _{2})$ is a weak pullback of the $Fc_{y_{i}}^{X_{i}}.$

If $y_{1}\ne y_{2},$ then the pullback of the $c_{y_{i}}^{X_{i}}$ is $(\emptyset ,\emptyset _{X_{1}},\emptyset _{X_{2}})$, the empty set $\emptyset$ with empty mappings $\emptyset _{X_{i}}:\emptyset \rightarrow X_{i}$. Since $\iota _{Y}$ is injective, the $Fc_{y_{1}}$ are constant maps with disjoint images, too, consequently their pullback is $(\emptyset ,\emptyset _{F(X_{1})},\emptyset _{F(X_{2})}).$ This is the same we would obtain by applying F to the pullback of the $c_{y_{i}}$, taking into account that $F(\emptyset )=\emptyset$.

For the reverse direction, suppose that F is connected and weakly preserves pullbacks of constant maps. The product $(X_{1}\times X_{2},\pi _{1},\pi _{2})$ is at the same time the pullback of the terminal maps $!_{X_{i}}:X_{i}\rightarrow \varvec{1}$. Applying F and considering that $F(\varvec{1})\cong \varvec{1}$, we see that the $F!_{X_{i}}$ are also terminal maps, so their pullback is $(F(X_{1})\times F(X_{2}),\eta _{1},\eta _{2})$. Thus, if F weakly preserves the pullback of the $!_{X_{i}},$ then we must have that $(F(X_{1}\times X_{2}),F\pi _{1},F\pi _{2})$ is a weak pullback of the $F!_{X_{i}}$ which by Lemma 4.4 means that there exists a surjective map $\delta :F(X_{1}\times X_{2})\rightarrow F(X_{1})\times F(X_{2})$ with $\eta _{i}\circ \delta =F\pi _{i}$. $\square$

The following example demonstrates that the requirement that F has no constants is essential in Theorem 4.7.

Example 4.8

Consider the functor T with $T(X)=X^{2}/\Delta$ where $\Delta$ is the equivalence relation on $X^{2}$ identifying any two elements in the diagonal of $X^{2}.$ For $x_{1},x_{2}\in X$, we denote the elements of $X^{2}/\Delta$ by $(x_{1},x_{2})$ if $x_{1}\ne x_{2}$ and by $\bot$ otherwise. On maps $f:X\rightarrow Y$ the functor T is defined as $(Tf)(\bot )=\bot$ and

$$\begin{aligned} (Tf)(x_{1},x_{2})={\left\{ \begin{array}{ll} \bot &{} \text {if }f(x_{1})=f(x_{2}),\\ (f(x_{1}),f(x_{2})) &{} \text {else.} \end{array}\right. } \end{aligned}$$

Then T is a functor and the projection $\pi _{\Delta }:X^{2}\rightarrow X^{2}/\Delta$ is a natural transformation. Even though $T(\emptyset )=\emptyset$, the functor does have a constant, $\bot$.

The map $\delta =(T\pi _{1},T\pi _{2}):T(X\times Y)\rightarrow T(X)\times T(Y)$ is surjective: If $X=\emptyset$ or $Y=\emptyset$ this is trivial, otherwise fix some $x\in X$ and $y\in Y$. Then $((x_{1},x_{2}),(y_{1},y_{2}))\in T(X)\times T(Y)$ has preimage $((x_{1},y_{1}),(x_{2},y_{2})).$ Preimages of $((x_{1},x_{2}),\bot )$ and of $(\bot ,(y_{1},y_{2}))$ are $((x_{1},y)(x_{2},y))$ and $((x,y_{1}),(x,y_{2})).$ Finally $(\bot ,\bot )$ has preimage $\bot$. Thus T weakly preserves products.

To see that T does not weakly preserve pullbacks of constant maps, consider $c_{0}^{X},c_{1}^{X}:X\rightarrow \{0,1\}$ whose pullback is $\emptyset$. But $T(c_{0}^{X})=T(c_{1}^{X})=c_{\bot }^{T(X)}$ and their pullback is $T(X)\times T(X).$ Clearly there is no way to find a surjective map from $T(\emptyset )=\emptyset$ to $T(X)\times T(Y)$ as would be required by Lemma 4.4.

5 Proof of the main theorem

We are finally turning to the proof of Theorem 2.1, verifying the surjectivity of $\delta =(F\pi _{1},F\pi _{2})$ when $(F,\iota ,\mu )$ is a monad. Thus given $(p,q)\in F(A_{1})\times F(A_{2}),$ we are required to find an element $t\in F(A_{1}\times A_{2})$ such that $(F\pi _{1})(t)=p$ and $(F\pi _{2})(t)=q.$

For each $a\in A_{1}$ we define a map $\sigma _{a}:A_{2}\rightarrow A_{1}\times A_{2}$ by

$$\begin{aligned} \sigma _{a}(b):=(a,b). \end{aligned}$$

Next we define $\tau :A_{1}\rightarrow F(A_{1}\times A_{2})$ by

$$\begin{aligned} \tau (a):=(F\sigma _{a})(q). \end{aligned}$$

The following picture gives an overview, where the lower squares commute due to the fact that $\mu$ is a natural transformation,

and the commutativities involving the dotted arrows will be established in the following auxiliary lemma:

Lemma 5.1

• (1) $F\pi _{1}\circ \tau =\iota _{A_{1}}$

• (2) $F\pi _{2}\circ \tau =c_{q}^{A_{1}}.$

Proof

From the definition it follows that $\pi _{1}\circ \sigma _{a}=c_{a}^{A_{2}}$ and $\pi _{2}\circ \sigma _{a}=id_{A_{2}}.$ Using these, and Lemma 3.1, we calculate:

$$\begin{aligned} \,\,(F\pi _{1}\circ \tau )(a)&= (F\pi _{1})(\tau (a))\\&= (F\pi _{1})((F\sigma _{a})(q))\\&= ((F\pi _{1})\circ F\sigma _{a})(q)\\&= F(\pi _{1}\circ \sigma _{a})(q)\\&= (Fc_{a}^{A_{2}})(q)\\&= c_{\iota _{A_{1}}(a)}^{F(A_{2})}(q)\\&= \iota _{A_{1}}(a) \end{aligned}$$

and similarly

$$\begin{aligned} (F\pi _{2}\circ \tau )(a)&= F(\pi _{2})((F\sigma _{a})(q))\\&= F(\pi _{2}\circ \sigma _{a})(q)\\&= F(id_{A_{2}})(q)\\&= id_{F(A_{2})}(q)\\&= q \end{aligned}$$

whence $(F\pi _{2}\circ \tau )$ is the constant map $c_{q}^{A_{1}}:A_{1}\rightarrow F(A_{2})$. $\square$

With these lemmas in place, we can finish the proof of Theorem 2.1. We set

$$\begin{aligned} t:=(\mu _{A_{1}\times A_{2}}\circ F\tau )(p) \end{aligned}$$

and claim:

$$\begin{aligned} (F\pi _{1})(t)&= p \end{aligned}$$

(5.1)

$$\begin{aligned} (F\pi _{2})(t)&= q. \end{aligned}$$

(5.2)

In order to show (5.1), we calculate, using naturality of $\mu$, for $i=1,2:$

$$\begin{aligned} (F\pi _{i})(t)&= (F\pi _{i})((\mu _{A_{1}\times A_{2}}\circ F\tau )(p))\\&= (F\pi _{i}\circ \mu _{A_{1}\times A_{2}}\circ F\tau )(p)\\&= (\mu _{A_{i}}\circ FF\pi _{i}\circ F\tau )(p)\\&= (\mu _{A_{i}}\circ F(F\pi _{i}\circ \tau ))(p). \end{aligned}$$

Then for $i=1$ we continue, using Lemma 5.1 and the first monad law:

$$\begin{aligned} (\mu _{A_{1}}\circ F(F\pi _{1}\circ \tau ))(p)&= (\mu _{A_{1}}\circ F\iota _{A_{1}})(p)\\&= id_{F(A_{1})}(p)\\&= p, \end{aligned}$$

whereas for $i=2$ we obtain, using Lemmas 5.1 and 3.1 as well as the second monad law:

$$\begin{aligned} (\mu _{A_{2}}\circ F(F\pi _{2}\circ \tau ))(p)&= (\mu _{A_{2}}\circ F(c_{q}^{A_{1}}))(p)\\&= (\mu _{A_{2}}\circ c_{\iota _{F(A_{2})}(q)}^{F(A_{1})})(p)\\&= \mu _{A_{2}}(\iota _{F(A_{2})}(q))\\&= (\mu _{A_{2}}\circ \iota _{F(A_{2})})(q)\\&= q. \end{aligned}$$

Corollary 5.2

Let $\alpha ={{\,\mathrm{Ker}\,}}\pi _{1}$ and $\beta ={{\,\mathrm{Ker}\,}}\pi _{2},$ then

$$\begin{aligned} F(A\times B)/\alpha \wedge \beta \cong F(A)\times F(B). \end{aligned}$$

6 Conclusion

We have shown that a key observation in the work of Dent, Kearnes and Szendrei [2] results from a weak limit preservation property which results from the free-algebra functor $F_{\mathcal {V}}$ being a (not necessarily associative) monad. Such weak limit preservation properties of $Set-$functors are highly relevant when using such functors as type functors for coalgebras.

Indeed, in a forthcoming paper [10] weak preservation of kernel pairs and preservation of preimages by $F_{\mathcal {V}}$ will be characterized by syntactic criteria for the equations $\Sigma$ defining the variety $\mathcal {V}.$