# Free-Algebra Functors from a Coalgebraic Perspective

H. Peter Gumm

► To cite this version:

H. Peter Gumm. Free-Algebra Functors from a Coalgebraic Perspective. 15th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2020, Dublin, Ireland. pp.55-67, 10.1007/978-3-030-57201-3_4. hal-03232349

HAL Id: hal-03232349

https://inria.hal.science/hal-03232349

Submitted on 21 May 2021

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
# Free-Algebra Functors from a Coalgebraic Perspective

H. Peter Gumm

Philipps-Universität Marburg, Germany

gumm@mathematik.uni-marburg.de

**Abstract.** We continue our study of free-algebra functors from a coalgebraic perspective as begun in [8]. Given a set $\Sigma$ of equations and a set $X$ of variables, let $F_{\Sigma}(X)$ be the free $\Sigma$-algebra over $X$ and $\mathcal{V}(\Sigma)$ the variety of all algebras satisfying $\Sigma$. We consider the question, under which conditions the Set-functor $F_{\Sigma}$ weakly preserves pullbacks, kernel pairs, or preimages [9].

We first generalize a joint result with our former student Ch. Henkel, asserting that an arbitrary *Set*-endofunctor *F* weakly preserves kernel pairs if and only if it weakly preserves pullbacks of epis.

By slightly extending the notion of derivative $\Sigma'$ of a set of equations $\Sigma$ as defined by Dent, Kearnes and Szendrei in [3], we show that a functor $F_{\Sigma}$ (weakly) preserves preimages if and only if $\Sigma$ implies its own derivative, i.e. $\Sigma \vdash \Sigma'$, which amounts to saying that weak independence implies independence for each variable occurrence in a term of $\mathcal{V}(\Sigma)$. As a corollary, we obtain that the free-algebra functor will never preserve preimages when $\mathcal{V}(\Sigma)$ is congruence modular.

Regarding preservation of kernel pairs, we show that for *n*-permutable varieties $\mathcal{V}(\Sigma)$, the functor $F_{\Sigma}$ weakly preserves kernel pairs if and only if $\mathcal{V}(\Sigma)$ is a Mal'cev variety, i.e. 2-permutable.

# 1 Introduction

In his groundbreaking monograph "Universal Coalgebra – a theory of systems" [15] Jan Rutten demonstrated how all sorts of state based systems could be unified under the roof of one abstract concept, that of a coalgebra. Concrete system types – automata, transition systems, nondeterministic, weighted, probabilistic or second order systems – can be modeled by choosing an appropriate functor $F: \mathcal{Set} \to \mathcal{Set}$ which provides a *type* for the concrete coalgebras just as, on a less abstract level, signatures describe types of algebras.

The (co)algebraic properties of the category $Set_F$ of all $F$-coalgebras are very much dependent on certain preservation properties of the functor $F$. A particular property of $F$, which has been considered relevant from the beginning was the preservation of certain weak limits. In Rutten’s original treatise [16], lemmas and theorems were marked with an asterisk, if they used the additional assumption that $F$ *weakly preserves pullbacks*, that is $F$ transforms pullback diagrams in *Set* into weak pullback diagrams.
In our lecture notes [6], we were able to remove a large number of asterisks from Rutten's original presentation, and in joint work with T. Schröder [9], we managed to split the mentioned preservation condition into two separate conditions, weak preservation of kernel pairs and preservation of preimages. These properties were then studied separately with an eye on their structure theoretic significance.

It is therefore relevant and interesting to classify Set functors according to the mentioned preservation properties.

We start this paper by showing that for arbitrary Set functors weak preservation of kernel pairs is equivalent to weak preservation of pullbacks of epis, a result, which was obtained jointly with our former master student Ch. Henkel.

Subsequently, we investigate Set functors $F_Σ$ which associate to a set $X$ the free $Σ$-algebra over $X$. It turns out that (weak) preservation of preimages by $F_Σ$ can be characterized utilizing the *derivative* $Σ'$ of $Σ$, which has been studied a few years ago by Dent, Kearnes, and Szendrei [3]. For arbitrary sets of *idempotent* equations $Σ$, they show that the variety $V(Σ)$ is congruence modular if and only if $Σ ∪ Σ'$ is inconsistent. Below, we extend their notion of derivative to arbitrary sets of equations (not necessarily idempotent) and are able to show that $F_Σ$ weakly preserves preimages if and only if $Σ ⊢ Σ'$.

Regarding preservation of kernel pairs, we exhibit an algebraic condition, which to our knowledge has not been studied before and which appears to be interesting in its own right. If $F_Σ$ weakly preserves kernel pairs, that is if $F_Σ$ weakly preserves pullbacks of epis, then for any pair $p, q$ of ternary terms satisfying

$$p(x, x, y) \approx q(x, y, y)$$

there exists a quaternary term $s$ such that

$$p(x, y, z) \approx s(x, y, z, z)$$

$$q(x, y, z) \approx s(x, x, y, z).$$

Applying this to the description of $n$-permutable varieties given by Hage- mann and Mitschke [10], we find that for an $n$-permutable variety $V(Σ)$, the functor $F_Σ$ weakly preserves kernel pairs if and only if $V(Σ)$ is a Mal'cev variety, i.e. there exists a term $m(x, y, z)$ such that the equations

$$m(x, y, y) \approx x$$

$$m(x, x, y) \approx y$$

are satisfied.

## 2 Preliminaries

For the remainder of this work we shall denote function application by juxtaposition, associating to the right, i.e. $fx$ denotes $f(x)$ and $fgx$ denotes $f(g(x))$.
If $F$ is a functor, we denote by $F(X)$ the application of $F$ to an object $X$ and by $Ff$ the application of $F$ to a morphism $f$.

Given a *Set*-functor $F$, an $F$-coalgebra is simply a map $\alpha : A \to F(A)$, where $A$ is called the *base set* and $\alpha$ the *structure map* of the coalgebra $\mathcal{A} = (A, \alpha)$. A *homomorphism* between coalgebras $\mathcal{A} = (A, \alpha)$ and $\mathcal{B} = (B, \beta)$ is a map $\varphi : A \to B$ satisfying

$$ \beta \circ \varphi = F\varphi \circ \alpha. $$

The functor $F$ is called the *type* of the coalgebra. The class of all coalgebras of type $F$ together with their homomorphisms forms a category $\mathcal{Set}_F$. The structure of this category is known to depend heavily on several pullback preservation properties of the functor $F$.

A pullback diagram

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

is called a *kernel pair*, if $f_1 = f_2$ and it is called a *preimage* if $f_1$ or $f_2$ is mono.

A functor $F$ is said to *weakly preserve pullbacks* if $F$ transforms each pullback diagram into a weak pullback diagram. $F$ weakly preserving kernel pairs, resp. preimages are defined likewise.

In order to check whether in the category $\mathcal{Set}$ a diagram as above is a weak pullback, we may argue elementwise: $(P, p_1, p_2)$ is a weak pullback, if for each pair $(a_1, a_2)$ with $a_i \in A_i$ and $f_1 a_1 = f_2 a_2$ there exists some $a \in P$ such that $p_1 a = a_1$ and $p_2 a = a_2$.

Hence, to see that a *Set*-functor $F$ weakly preserves a pullback $(P, p_1, p_2)$, we must check that for any pair $(u_1, u_2)$ with $u_i \in F(A_i)$ and $(Ff_1)u_1 = (Ff_2)u_2$ we can find some $w \in F(P)$ such that $(Fp_1)w = u_1$ and $(Fp_2)w = u_2$.

One easily checks that a *weak preimage* is automatically a *preimage*. Hence, if $F$ preserves monos, then $F$ preserves preimages if and only if $F$ *weakly preserves* preimages.

Assuming the axiom of choice, all epis in the category $\mathcal{Set}$ are right invertible, hence $F$ preserves epis. Monos are left-invertible, except for the empty mappings $\emptyset_X : \emptyset \to X$ when $X \neq \emptyset$. Hence $F$ surely preserves monos with nonempty domain.

Most *Set*-functors also preserve monos with empty domain. This will, in particular, be the case for the free-algebra functor $F_\Sigma$, which we shall study in the later parts of this work.

For *Set*-functors $F$ which fail to preserve monos with empty domain, there is an easy fix, modifying $F$ solely on the empty set $\emptyset$ and on the empty mappings $\emptyset_X : \emptyset \to X$, so that the resulting functor $F^*$ preserves all monos. The details can be found in [1] or in [7]. This modification is irrelevant as far as coalgebras are concerned, since it affects only the empty coalgebra. Yet it allows us to assume from now on, that $F$ preserves all monos and all epis.
If $f_1$ and $f_2$ are both injective, then their pullback is called an intersection. It is well known from [18] that a set functor automatically preserves nonempty intersections, and, after possibly modifying it at $\emptyset$ as indicated above, preserves all finite intersections.

### 3 Weak preservation of epi pullbacks

The following lemma from [9] shows that weak pullback preservation can be split into two separate preservation requirements.

**Lemma 1** For a Set-functor $F$ the following are equivalent:

1. $F$ weakly preserves pullbacks.

2. $F$ weakly preserves kernels and preimages.

A special case of a preimage is obtained if we consider a subset $U \subseteq A$ as the preimage of $\{1\}$ along its characteristic function $\chi_U : A \to \{0, 1\}$.

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

Such preimages are called *classifying*, and we shall later make use of the following lemma from [9]:

**Lemma 2** A Set-functor $F$ preserves preimages if and only if it preserves classifying preimages.

In the following section we need to consider the action of a functor on pullback diagrams where both $f_1$ and $f_2$ are surjective. Before stating this, we shall prove a useful lemma, which is true in every category:

**Lemma 3** Let morphisms $f: A \to C$ and $f_i: A_i \to C$, for $i = 1, 2$ be given, as well as $e_i: A_i \to A$ with left inverses $h_i: A \to A_i$ such that the diagram below commutes. If $(K, \pi_1, \pi_2)$ is a weak kernel of $f$ then $(K, h_1 \circ \pi_1, h_2 \circ \pi_2)$ is a weak pullback of $f_1$ and $f_2$.

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

*Proof.* Assuming $(K, \pi_1, \pi_2)$ is a weak kernel of $f$, then setting $k_i := h_i \circ \pi_i$ we obtain

$$f_1 \circ k_1 = f_1 \circ h_1 \circ \pi_1 = f \circ \pi_1 = f \circ \pi_2 = f_2 \circ h_2 \circ \pi_2 = f_2 \circ k_2.$$
This shows that $(K, k_1, k_2)$ is a candidate for a pullback of $f_1$ with $f_2$. Let $(Q, q_1, q_2)$ be another candidate, i.e.

$$f_1 \circ q_1 = f_2 \circ q_2,$$

then we obtain

$$f \circ e_1 \circ q_1 = f_1 \circ q_1 = f_2 \circ q_2 = f \circ e_2 \circ q_2,$$

which demonstrates that $(Q, e_1 \circ q_1, e_2 \circ q_2)$ is a competitor to $(K, \pi_1, \pi_2)$ for being a weak kernel of $f$. This yields a morphism $q : Q \to K$ with

$$\pi_i \circ q = e_i \circ q_i.$$

From this we obtain

$$k_i \circ q = h_i \circ \pi_i \circ q = h_i \circ e_i \circ q_i = q_i$$

as required.

**Theorem 4** Let $C$ be a category with finite sums and kernel pairs. If a functor $F : C \to C$ weakly preserves kernel pairs, then it weakly preserves pullbacks of retractions.

*Proof.* Given the pullback $(P, p_1, p_2)$ of retractions $f_i : A_i \to C$, we need to show that $(F(P), Fp_1, Fp_2)$ is a weak pullback. For that reason we shall relate it to the kernel pair of $f := [f_1, f_2] : A_1 + A_2 \to C$.

Since the $f_i$ are retractions, i.e. right invertible, we can choose $g_i : C \to A_i$ with

$$f_i \circ g_i = \mathrm{id}_C.$$

Let $e_i : A_i \to A_1 + A_2$ be the canonical inclusions, then

$$f \circ e_i = [f_1, f_2] \circ e_i = f_i.$$

Define $h_1 := [id_{A_1}, g_1 \circ f_2]$ and $h_2 := [g_2 \circ f_1, id_{A_2}]$, then $h_i : A_1 + A_2 \to A_i$ satisfy

$$h_i \circ e_i = \mathrm{id}_{A_i}$$

as well as

$$f_1 \circ h_1 = [f_1 \circ id_{A_1}, f_1 \circ g_1 \circ f_2] = [f_1, f_2] = f_2 \circ h_2.$$

Thus we have established commutativity of the right half of the following diagram.

<figure><img src="image_5.png" /></figure>
We add the kernel pair $(K, \pi_1, \pi_2)$ of $f := [f_1, f_2]$ and the pullback $(P, p_1, p_2)$ of $f_1$ and $f_2$. Now, the previous lemma asserts that $(K, k_1, k_2)$ is a weak pullback of $f_1$ and $f_2$, therefore we obtain a morphism $p : P \to K$ with $k_i \circ p = p_i$.

On the other hand, $(P, p_1, p_2)$ being the real pullback, earns us a unique morphism $k : K \to P$ with $p_i \circ k = k_i$ and $k \circ p = \text{id}_P$ by uniqueness.

Next, we apply the functor $F$ to the above diagram. The requirements of Lemma 3 remain intact for the image diagram, and assuming that $F$ weakly preserves the kernel $(K, \pi_1, \pi_2)$, we obtain that $(F(K), Fk_1, Fk_2)$ is a weak pullback of $Ff_1$ with $Ff_2$. Since furthermore $F(P)$ remains being a retract of $F(K)$ by means of $Fk \circ Fp = \text{Fid}_P = \text{id}_{F(P)}$, we see that $(F(P), Fp_1, Fp_2)$, too, is a weak pullback of $Ff_1$ and $Ff_2$, as required.

From this we can obtain our mentioned joint result with Ch. Henkel. With an elementwise proof this appears in his master thesis, which has been completed under our guidance [11]:

**Corollary 5** For a Set-endofunctor $F$ the following are equivalent:

1. $F$ weakly preserves kernel pairs.

2. $F$ weakly preserves pullbacks of epis.

*Proof.* In *Set*, each map $f$ can be factored as $f = \iota \circ e$ where $e$ is epi and $\iota$ is mono. Therefore, the kernel of $f$ is the same as the kernel of $e$. This takes care of the direction $(2 \to 1)$. For the other direction, the axiom of choice asserts that in *Set* epis are right invertible, so the conditions of Theorem 4 are met.

# 4 Free-algebra functors and Mal'cev conditions

Given a finitary algebraic signature $S = (\mathfrak{f}, n_i)_{i \in I}$, fixing a family of function symbols $\mathfrak{f}_i$, each of arity $n_i$, and given a set $\Sigma$ of equations, let $\mathcal{V}(\Sigma)$ be the variety defined by $\Sigma$, i.e. the class of all algebras $\mathfrak{A} = (A, (f_i^{\mathfrak{A}})_{i \in I})$ satisfying all equations from $\Sigma$.

The forgetful functor, sending an algebra $\mathfrak{A}$ from $\mathcal{V}(\Sigma)$ to its base set $A$, has a left adjoint $F_\Sigma$, which assigns to each set $X$, considered as set of variables, the free $\Sigma$-algebra over $X$. $F_\Sigma(X)$ consists of equivalence classes of terms $p$, which arise by syntactically composing basic operations named in the signature, using only variables from $X$.

Two terms $p$ and $q$ are identified if the equality $p \approx q$ is a consequence of the equations in $\Sigma$. This is the same as saying that $p$ and $q$ induce the same operation $p^{\mathfrak{A}} = q^{\mathfrak{A}}$ on each algebra $\mathfrak{A} \in \mathcal{V}(\Sigma)$. Instead of $p$ we often write $p(x_1, ..., x_n)$ to mark all occurrences $x_1, ..., x_n$ of variables in the term $p$.

$F_\Sigma$ is clearly a functor (in fact a monad), and its action on maps $\varphi : X \to Y$ can be described as variable substitution, sending $p(x_1, ..., x_n) \in F_\Sigma(X)$ to $p(\varphi x_1, ..., \varphi x_n) \in F_\Sigma(Y)$.

$\Sigma$ is called *idempotent* if for every function symbol $f$ appearing in $\Sigma$ we have $\Sigma \vdash f(x, ..., x) \approx x$. As a consequence, all term operations satisfy the
corresponding equations, so $\Sigma$ is idempotent iff $F_\Sigma(\{x\}) = \{x\}$. In this case, we also call the variety $\mathcal{V}(\Sigma)$ idempotent. As an example, the variety of all lattices is idempotent, whereas the variety of groups is not.

In [8] we have recently shown that for an idempotent set $\Sigma$ of equations $F_\Sigma$ weakly preserves products.

In 1954, A.I. Mal'cev [13,14] discovered that a variety has *permutable congruences*, i.e. $\Theta \circ \Psi = \Psi \circ \Theta$ holds for all congruences $\Theta$ and $\Psi$ in each algebra of $\mathcal{V}(\Sigma)$, if and only if there exists a ternary term $m(x, y, z)$ satisfying the equations

$$x \approx m(x, y, y) \text{ and } m(x, x, y) \approx y.$$

Permutability of congruences $\Theta$ and $\Psi$ can be generalized to $n$-permutability, requiring that the $n$-fold relational compositions agree:

$$\Theta \circ \Psi \circ \Theta \circ \dots = \Psi \circ \Theta \circ \Psi \circ \dots.$$

Here each side is meant to be the relational composition of $n$ factors.

J. Hagemann and A. Mitschke [10], generalizing the original Mal'cev result, showed that a variety $\mathcal{V}$ is $n$-permutable if and only if there are ternary terms $p_1, \dots, p_{n-1}$ such the following series of equations is satisfied:

$$x \approx p_1(x, y, y) \qquad (1)$$

$$p_i(x, x, y) \approx p_{i+1}(x, y, y) \text{ for all } 0 < i < n-1$$

$$p_{n-1}(x, x, y) \approx y.$$

Ever since Mal'cev's mentioned result, such conditions, postulating the existence of derived operations satisfying a (possibly $n$-indexed) series of equations have been called *Mal'cev conditions*, and these have played an eminent role in the development of universal algebra. They may generally be of the form

$$\exists n \in \mathbb{N}. \exists p_1, \dots, p_n. \Gamma$$

where $p_1, \dots, p_n$ are terms and $\Gamma$ is a set of equations involving the terms $p_1, \dots, p_n$. Such a condition is supposed to hold in a variety $\mathcal{V}$ of universal algebras if for some $n \in \mathbb{N}$ there exist terms $p_1, \dots, p_n$ in the operations of $\mathcal{V}$ satisfying the equations in $\Gamma$.

B. Jónsson [12] gave a Mal'cev condition characterizing *congruence distributive* varieties, i.e. varieties $\mathcal{V}$ in which the lattice of congruences of each algebra $\mathfrak{A} \in \mathcal{V}$ is distributive. A Mal'cev condition characterizing *congruence modular* varieties and involving quaternary terms was found by A. Day [2]. In 1981, employing commutator theory, we showed in [5], how to compose Jónsson's terms for congruence distributivity with the original Mal'cev term $m(x, y, z)$ from above in order to characterize congruence modular varieties, while at the same time obtaining ternary terms.

Notice, that all Mal'cev conditions mentioned above are idempotent, i.e. $\Gamma \vdash p_i(x, \dots, x) \approx x$ for each of their terms $p_i$.
# 5 Preservation of preimages

A few years ago, Dent, Kearnes, and Szendrei [3] invented a syntactic operation on idempotent sets of equations $\Sigma$, called the *derivative* $\Sigma'$, and they showed that an idempotent variety $\mathcal{V}(\Sigma)$ is congruence modular if and only if $\Sigma \cup \Sigma'$ is inconsistent.

Subsequently, Freese [4] was able to give a similar characterization for $n$-permutable varieties, using an *order derivative*, which was based on the fact that a variety is $n$-permutable if and only if its algebras are not orderable, an insight, said to have been observed already by Hagemann (unpublished), but which first appears in P. Selinger's PhD-thesis [17].

It will turn out below, after generalizing the relevant definitions from [3] to non-idempotent varieties, that the derivative also serves us to characterize free-algebra functors preserving preimages.

We start by slightly modifying the definition of weak independence from [3]:

**Definition 6** A term $p$ is weakly independent of a variable occurrence $x$, if there exists a term $q$ such that $\Sigma \vdash p(x, v_1, ..., v_n) \approx q(y)$ where $x \neq y$ and $v_1, ..., v_n$ are variables. $p$ is independent of $x$, if $\Sigma \models p(x, z_1, ..., z_n) \approx p(y, z_1, ..., z_n)$ where $x, y$, and all variables $z_1, ..., z_n$ are distinct.

As an example, consider the variety of groups. The term $m(x, y, z) := xy^{-1}z$ is weakly independent of its first argument, since $m(x, x, y) = xx^{-1}y \approx y$ holds, but it is not independent of the same argument, since $m(x, z_1, z_2) = xz_1^{-1}z_2 \not\approx yz_1^{-1}z_2 = m(y, z_1, z_2)$. The term $p(x, y) := xyx^{-1}$ is *independent* of its first argument in the variety of abelian groups, but not in the variety of all groups, since $p(x, z) = xzx^{-1} \not\approx yzy^{-1} = p(y, z)$. More generally, any Mal'cev term $m(x, y, z)$ is *weakly independent* of each of its arguments, but cannot be independent of either of them.

Clearly, if $p$ is independent of $x$ then it is also weakly independent of $x$, since $p(x, z_1, ..., z_n) \approx p(y, z_1, ..., z_n)$ entails $p(x, y, ..., y) \approx p(y, y, ..., y) =: q(y)$.

We now define the *derivative* $\Sigma'$ of $\Sigma$ as the set of all equations asserting that a term which is weakly independent of a variable occurrence $x$ should also be independent of that variable:

$$ \Sigma' := \{p(x, \vec{z}) \approx p(y, \vec{z}) \mid p(x, \vec{w}) \text{ weakly independent of } x\}. $$

We are now ready to state the main theorem of this section:

**Theorem 7** $F_{\Sigma}$ (weakly) preserves preimages if and only if $\Sigma \vdash \Sigma'$.

*Proof.* Consider a term $p$ which is weakly independent of a variable occurrence $x$, i.e. there exists a term $q$ such that $\Sigma \vdash p(x, w_1, ..., w_n) \approx q(y)$ where $x, y, w_1, ..., w_n$ are occurrences of not necessarily distinct variables, but $x \neq y$.

We must show that $p(x, z_1, ..., z_n) \approx p(y, z_1, ..., z_n)$ for $x, y, z_1, ..., z_n$ mutually distinct variables.

Consider the map $\varphi : \{x, y, z_1, ..., z_n\} \to \{x, y, w_1, ..., w_n\}$ which fixes $x$ and $y$ and sends each $z_i$ to $w_i$. Then
$$ 
\begin{align*}
(F_{\Sigma}\varphi)(p(x, z_1, \dots, z_n)) &= p(\varphi x, \varphi z_1, \dots, \varphi z_n) \\
&= p(x, w_1, \dots, w_n) \\
&\approx q(y) \in F_{\Sigma}(\{y\}),
\end{align*}
$$

so $p(x, z_1, \dots, z_n)$ is in the preimage of $F_{\Sigma}(\{y\})$ under $F_{\Sigma}\varphi$.

The preimage of $\{y\} \subseteq \{x, y, w_1, \dots, w_n\}$ under $\varphi$ does not contain $x$, so $\varphi^{-1}(\{y\}) \subseteq \{y, z_1, \dots, z_n\}$. Assuming that $F_{\Sigma}$ preserves preimages, we obtain

$$ p(x, z_1, \dots, z_n) \in F_{\Sigma}(\{y, z_1, \dots, z_n\}), $$

so there exists a term $r$ with

$$ p(x, z_1, \dots, z_n) \approx r(y, z_1, \dots, z_n). $$

Since $x, y \notin \{z_1, \dots, z_n\}$, by substituting $y$ for $x$ in this equation, we also find $p(y, z_1, \dots, z_n) \approx r(y, z_1, \dots, z_n)$, so

$$ p(x, z_1, \dots, z_n) \approx p(y, z_1, \dots, z_n) $$

by transitivity.

Conversely, assume that $\Sigma \vdash \Sigma'$, then we need to verify that $F_{\Sigma}$ preserves preimages. According to Lemma 2, we need only verify that $F_{\Sigma}$ preserves classifying preimages. Let $X$ and $Y$ be disjoint sets and let $\varphi : X \cup Y \to \{x, y\}$ be given, sending elements from $X$ to $x$ and elements from $Y$ to $y$. Then $Y \subseteq X \cup Y$ is the preimage of $\{y\}$ under $\varphi$. We must show that the following is a preimage diagram:

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

Given an element $p \in F_{\Sigma}(X \cup Y)$ with $(F_{\Sigma}\varphi)p \in F_{\Sigma}(\{y\})$ we must show that $p \in F_{\Sigma}(Y)$.

Let $x_1, \dots, x_n, y_1, \dots, y_m$ be all variables occurring in $p$ where $x_i \in X$ and $y_i \in Y$. The assumption yields

$$ p(\varphi x_1, \dots, \varphi x_n, \varphi y_1, \dots, \varphi y_m) = p(x, \dots, x, y, \dots, y) \in F_{\Sigma}(y), $$

i.e. $p(x, \dots, x, y, \dots, y) \approx q(y)$ for some term $q \in F_{\Sigma}(\{y\})$. This means that $p$ is weakly independent of each of its occurrences of $x$, so our assumption $\Sigma \vdash \Sigma'$ says that $\mathcal{V}$ also satisfies the equations

$$ 
\begin{align*}
p(x_1, x_2, \dots, x_n, y_1, \dots, y_m) &\approx p(z_1, x_2, \dots, x_n, y_1, \dots, y_m) \\
&\approx p(z_1, z_2, \dots, x_n, y_1, \dots, y_m) \\
&\approx \dots \\
&\approx p(z_1, z_2, \dots, z_n, y_1, \dots, y_m)
\end{align*}
$$
In particular, by choosing $y$ arbitrarily from $\{y_1, \dots, y_m\}$, we obtain

$$p = p(x_1, \dots, x_n, y_1, \dots, y_m) \approx p(y, \dots, y, y_1, \dots, y_n) \in F_{\Sigma}(Y)$$

as required.

Whereas Dent, Kearnes and Szendrei have shown that congruence modular varieties are characterized by the fact that adding the derivative of their defining equations yields an inconsistent theory, we have just seen that $F_{\Sigma}$ preserving preimages delineates the other extreme, $\Sigma \vdash \Sigma'$. Clearly, therefore, for modular varieties $\mathcal{V}(\Sigma)$, the variety functor $F_{\Sigma}$ does not preserve preimages.

# 6 Preservation of kernel pairs

We begin this section with a positive result:

**Theorem 8** If $\mathcal{V}(\Sigma)$ is a Mal'cev variety, then $F_{\Sigma}$ weakly preserves pullbacks of epis.

*Proof.* According to Corollary 5, it suffices to check that $F_{\Sigma}$ weakly preserves kernel pairs of a surjective map $f : X \to Y$. The kernel of $f$ is

$$K = \{(x, x') | f(x) = f(x')\}$$

with the cartesian projections $\pi_1$ and $\pi_2$.

Given $p := p(x_1, \dots, x_m) \in F_{\Sigma}(X)$ and $q := q(x'_1, \dots, x'_n) \in F_{\Sigma}(X)$, and $r := r(y_1, \dots, y_k) \in F_{\Sigma}(Y)$ with

$$(F_{\Sigma}f)p = r = (F_{\Sigma}f)q,$$

we need to find some $\bar{m} \in F_{\Sigma}(K)$ such that $(F_{\Sigma}\pi_1)\bar{m} = p$ and $(F_{\Sigma}\pi_2)\bar{m} = q$.

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

Choose $g$ as right inverse to $f$, i.e. $f \circ g = \mathrm{id}_Y$, and define:

$$\bar{p} := p((x_1, g f x_1), \dots, (x_m, g f x_m)),$$

$$\bar{r} := r((g y_1, g y_1), \dots, (g y_k, g y_k)),$$

$$\bar{q} := q((g f x'_1, x'_1), \dots, (g f x'_n, x'_n)),$$

then it is easy to check that $\bar{p}$, $\bar{r}$, and $\bar{q}$ are elements of $F_{\Sigma}(K)$, hence the same is true for $\bar{m} := m(\bar{p}, \bar{r}, \bar{q})$, where $m(x, y, z)$ is the Mal'cev term. Moreover,
$$
\begin{align*}
(F_{\Sigma}\pi_1)\bar{m} &= (F_{\Sigma}\pi_1)m(\bar{p}, \bar{r}, \bar{q}) \\
&= m((F_{\Sigma}\pi_1)\bar{p}, (F_{\Sigma}\pi_1)\bar{r}, (F_{\Sigma}\pi_1)\bar{q}) \\
&= m(p(x_1, \dots, x_m), r(gy_1, \dots, gy_k), q(gfx'_1, \dots, gfx'_n)) \\
&= m(p, (F_{\Sigma}g)r(y_1, \dots, y_k), (F_{\Sigma}g)(F_{\Sigma}f)q(x'_1, \dots, x'_n)) \\
&= m(p, (F_{\Sigma}g)r, (F_{\Sigma}g)r) \\
&= p,
\end{align*}
$$

and similarly, $(F_{\Sigma}\pi_2)\bar{m} = q$.

Preservation of kernel pairs for the functor $F_{\Sigma}$ leads to some interesting syntactic condition on terms, which might be worth of further study:

**Lemma 9** If $F_{\Sigma}$ weakly preserves kernel pairs, then for any terms $p, q$ we have:

$$p(x, x, y) \approx q(x, y, y)$$

if and only if there exists a quaternary term $s$ such that

$$p(x, y, z) \approx s(x, y, z, z)$$

$$q(x, y, z) \approx s(x, x, y, z).$$

*Proof.* The if-direction of the claim is obvious. For the other direction consider $\varphi, \psi : \{x, y, z\} \to \{x, z\}$ with $\varphi x = \varphi y = \psi x = x$, and $\varphi z = \psi y = \psi z = z$. Their pullback is

$$P = \{(x, x), (y, x), (z, y), (z, z)\}.$$

Since $\varphi$ and $\psi$ are epi, according to Theorem 4, their pullback should be weakly preserved, too. Now, given $p$ and $q$ with $p(x, x, y) \approx q(x, y, y)$, then $(F_{\Sigma}\varphi)p = (F_{\Sigma}\psi)q$. Therefore, there must be some $s \in F_{\Sigma}(P)$, with $(F_{\Sigma}\pi_1)s = p$ and $(F_{\Sigma}\pi_2)s = q$. We obtain:

$$p(x, y, z) \approx (F_{\Sigma}\pi_1)s((x, x), (y, x), (z, y), (z, z)) = s(x, y, z, z), \text{ and}$$

$$q(x, y, z) \approx (F_{\Sigma}\pi_2)s((x, x), (y, x), (z, y), (z, z)) = s(x, x, y, z).$$

Using the criterion of this Lemma, we now determine, which $n$-permutable varieties give rise to a functor weakly preserving kernel pairs:

**Theorem 10** If $\mathcal{V}(\Sigma)$ is $n$-permutable, then $F_{\Sigma}$ weakly preserves kernel pairs if and only if $\mathcal{V}(\Sigma)$ is a Mal'cev variety, i.e. 2-permutable.

*Proof.* Assuming that $\mathcal{V}(\Sigma)$ is $n$-permutable for $n > 2$, we shall show that it is already $(n-1)$-permutable.

Let $p_1, \dots, p_{n-1}$ be the terms from the Mal'cev condition for $n$-permutability, with the equations 1.
According to Lemma 9, we find some term $s(x, y, z, u)$ such that $s(x, y, z, z) \approx p_1(x, y, z)$ and $s(x, x, y, z) \approx p_2(x, y, z)$. We now define a new term

$$m(x, y, z) := s(x, y, y, z),$$

and calculate:

$$m(x, y, y) \approx s(x, y, y, y) \approx p_1(x, y, y) \approx x$$

as well as

$$m(x, x, y) \approx s(x, x, x, y) \approx p_2(x, x, y) \approx p_3(x, y, y).$$

From this we obtain a shorter chain of equations, discarding $p_1$ and $p_2$ and replacing them by $m$:

$$\begin{align*}
x &\approx m(x, y, y) \\
m(x, x, y) &\approx p_3(x, y, y) \\
p_i(x, x, y) &\approx p_{i+1}(x, y, y) \text{ for all } 2 < i < n-1 \\
p_{n-1}(x, x, y) &\approx y.
\end{align*}$$

# 7 Conclusion and further work

We have shown that variety functors $F_\Sigma$ preserve preimages if and only if $\Sigma \vdash \Sigma'$ where $\Sigma'$ is the derivative of the set of equations $\Sigma$.

For each Mal'cev variety, $F_\Sigma$ weakly preserves kernel pairs. For the other direction, if $F_\Sigma$ weakly preserves kernel pairs, then every equation of the shape $p(x, x, y) \approx q(x, y, y)$ ensures the existence of a term $s(x, y, z, u)$, such that $p(x, y, z) \approx s(x, y, z, z)$ and $q(x, y, y) \approx s(x, x, y, z)$.

This intriguing algebraic condition appears to be new and certainly deserves further study from a universal algebraic perspective. Adding it to Freese's characterization of n-permutable varieties by means of his "order-derivative", allows to distinguish between the cases $n = 2$ (Mal'cev varieties) and $n > 2$, which cannot be achieved using his order derivative, alone.

It would be desirable to see if this consequence of weak kernel preservation can be turned into a concise if-and-only-if statement.

# References

1. Barr, M.: Terminal coalgebras in well-founded set theory. Theoretical Computer Science 114(2), 299–315 (1993). https://doi.org/10.1016/0304-3975(93)90076-6

2. Day, A.: A characterization of modularity for congruence lattices of algebras. Canadian Mathematical Bulletin 12(2), 167–173 (1969). https://doi.org/10.4153/CMB-1969-016-6
3. Dent, T., Kearnes, K.A., Szendrei, Á.: An easy test for congruence modularity. Algebra universalis **67**(4), 375–392 (2012). https://doi.org/10.1007/s00012-012-0186-z

4. Freese, R.: Equations implying congruence n-permutability and semidistributivity. Algebra universalis **70**(4), 347–357 (2013). https://doi.org/10.1007/s00012-013-0256-x

5. Gumm, H.P.: Congruence modularity is permutability composed with distributivity. Arch. Math **36**, 569–576 (1981). https://doi.org/10.1007/BF01223741

6. Gumm, H.P.: Elements of the general theory of coalgebras. In: LUATCS 99. Rand Afrikaans University, Johannesburg, South Africa (1999), https://www.mathematik.uni-marburg.de/~gumm/Papers/Luatcs.pdf

7. Gumm, H.P.: From T-coalgebras to filter structures and transition systems. In: Fiadeiro, J.L., Harman, N., Roggenbach, M., Rutten, J. (eds.) Algebra and Coalgebra in Computer Science. pp. 194–212. Springer Berlin Heidelberg (2005). https://doi.org/10.1007/11548133

8. Gumm, H.P.: Connected monads weakly preserve products. arXiv e-prints arXiv:1909.02259 (Sep 2019), https://arxiv.org/abs/1909.02259, to appear in Algebra universalis

9. Gumm, H.P., Schröder, T.: Types and coalgebraic structure. Algebra Universalis **53**, 229–252 (2005). https://doi.org/10.1007/s00012-005-1888-2

10. Hagemann, J., Mitschke, A.: On n-permutable congruences. Algebra universalis **3**(1), 8–12 (1973). https://doi.org/10.1007/BF02945100

11. Henkel, C.: Klassifikation Coalgebraischer Typfunktoren. (2010), Diplomarbeit, Universität Marburg

12. Jónsson, B.: Algebras whose congruence lattices are distributive. Math. Scand. **21**, 110–121 (1967). https://doi.org/10.7146/math.scand.a-10850

13. Mal'cev, A.I.: On the general theory of algebraic systems. (russian). Mat. Sb. (N.S.) **35**(77), 3–20 (1954)

14. Mal'tsev, A.I.: On the general theory of algebraic systems. Transl., Ser. 2, Am. Math. Soc. **27**, 125–142 (1963)

15. Rutten, J.: Universal coalgebra: A theory of systems. Theoretical Computer Science **249**, 3–80 (10 2000). https://doi.org/10.1016/S0304-3975(00)00056-6

16. Rutten, J.: Universal coalgebra: A theory of systems. Tech. rep., CWI, Amsterdam (1996), CS-R9652

17. Selinger, P.: Functionality, polymorphism, and concurrency: a mathematical investigation of programming paradigms. Tech. Rep. IRCS 97-17, Univ. Pennsylvania (1997), https://repository.upenn.edu/ircs_reports/88/

18. Trnková, V.: On descriptive classification of set-functors. I. Comm. Math. Univ. Carolinae **12**, 143–174 (1971), https://eudml.org/doc/16419