# Duality of Equations and Coequations via Contravariant Adjunctions

Julian Salamanca, Marcello Bonsangue, Jurriaan Rot

► To cite this version:

Julian Salamanca, Marcello Bonsangue, Jurriaan Rot. Duality of Equations and Coequations via Contravariant Adjunctions. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. pp.73-93, 10.1007/978-3-319-40370-0_6. hal-01446034

HAL Id: hal-01446034

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

Submitted on 25 Jan 2017

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
Duality of Equations and Coequations
via Contravariant Adjunctions

Julian Salamanca¹,*, Marcello Bonsangue¹,², and Jurriaan Rot³,**

¹ CWI Amsterdam, The Netherlands

² LIACS - Leiden University, The Netherlands

³ LIP, Université de Lyon, CNRS, Ecole Normale Supérieure de Lyon, INRIA, Université Claude-Bernard Lyon 1, France

**Abstract.** In this paper we show duality results between categories of equations and categories of coequations. These dualities are obtained as restrictions of dualities between categories of algebras and coalgebras, which arise by lifting contravariant adjunctions on the base categories. By extending this approach to (co)algebras for (co)monads, we retrieve the duality between equations and coequations for automata proved by Ballester-Bolinches, Cosme-Llópez and Rutten, and generalize it to dynamical systems.

# 1 Introduction

Equations play a fundamental role in (universal) algebra. Their categorical dual in universal coalgebra is the notion of *coequations*. Coequations were studied extensively in the search for a dual of Birkhoff's theorem and the specification of classes of coalgebras (see, e.g., [17, 19, 1, 2, 5, 21, 9, 11, 12, 23, 22]).

The aim of the current paper is a different one: to relate equations to coequations and vice versa. Our starting point is the abstract definition of (co)equations on (co)algebras for an endofunctor. These definitions give rise to categories of equations and coequations; we seek sufficient conditions to obtain dual equiva- lences between such categories.

We start with a more general concept than a duality, namely, a contravari- ant adjunction. Our approach is to lift adjunctions to categories of algebras and coalgebras [13]. In the setting of a contravariant adjunction, and by using preser- vation of limits by adjoints, we have that sets of equations are sent to sets of coequations. To guarantee the converse, i.e., that coequations are also mapped to equations, we assume that the contravariant adjunction is a duality. This gives us a duality result between equations and coequations. We derive known dualities between equations and coequations for automata [7, 24, 25] as a special

<footnote>* The research of this author is funded by the Dutch NWO project 612.001.210.</footnote>

<footnote>** Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).</footnote>
case of this abstract approach, and we generalize the duality shown in [7] to
include (general) dynamical systems.

As a natural next step in this study we include monads and comonads into the
picture and prove a lifting theorem to lift contravariant adjunctions to Eilenberg-
Moore categories. From this lifting theorem we show the following results:

- Dualities between equations and coequations for Eilenberg-Moore categories.

- Lifting of contravariant adjunctions to Eilenberg-Moore categories where, given a contravariant adjunction and a comonad, we define a canonical monad.

- Lifting of dualities to Eilenberg-Moore categories where, given a duality and a monad, we define a canonical comonad.

The paper is organized as follows. Section 2 is a preliminary section in which we introduce some notation we use in the paper. In Section 3 we introduce the abstract definitions of equations and coequations, satisfaction of equations for algebras and satisfaction of coequations for coalgebras. Section 4 introduces the notion of a contravariant adjunction. We state a theorem for lifting contravariant adjunctions (Theorem 3), which is essentially a special case of [13, 2.14. Theorem], and then illustrate this lifting theorem through several examples. In Section 5 we focus on the particular case that the contravariant adjunction is a duality to show a general duality result between equations and coequations. Further, we show how to get a canonical notion of satisfaction of equations for coalgebras. In Section 6 we include monads and comonads in our setting to prove a lifting theorem (Theorem 11) that allows us to lift contravariant adjunctions to a contravariant adjunction between Eilenberg-Moore categories. We show how to construct a comonad from a given monad and vice versa to get respective lifting theorems. Finally, in Section 7 we apply the lifting theorems (to Eilenberg-Moore) to the study of equations and coequations for dynamical systems and deterministic automata.

## 2 Preliminaries

In this section we introduce the notation for categories of algebras and coalgebras that we will use in the paper. We assume that the reader is familiar with basic concepts from category theory and coalgebra, see, e.g., [6, 22].

Given a category $\mathcal{D}$ and an endofunctor $L: \mathcal{D} \to \mathcal{D}$, we denote by $\mathrm{alg}(L)$ the category of $L$-algebras and their homomorphisms, i.e., objects in $\mathrm{alg}(L)$ are pairs $(X, \alpha)$ where $X$ is an object in $\mathcal{D}$ and $\alpha \in \mathcal{D}(LX, X)$, and a homomorphism from an $L$-algebra $(X_1, \alpha_1)$ to an $L$-algebra $(X_2, \alpha_2)$ is a morphism $h \in \mathcal{D}(X_1, X_2)$ such that $h \circ \alpha_1 = \alpha_2 \circ Lh$.

Dually, for a given endofunctor $B: C \to C$ on a category $C$, coalg$(B)$ denotes the category of $B$-coalgebras, i.e., objects in coalg$(B)$ are pairs $(Y, \beta)$ where $Y$ is an object in $C$ and $\beta \in C(Y, BY)$, and a homomorphism from a $B$-coalgebra $(Y_1, \beta_1)$ to a $B$-coalgebra $(Y_2, \beta_2)$ is a morphism $h \in C(Y_1, Y_2)$ such that $\beta_2 \circ h = Bh \circ \beta_1$.
In case that we have a monad $\mathcal{L} = (\mathcal{L}, \eta, \mu)$, we let $\text{Alg}(\mathcal{L})$ denote the category of (Eilenberg-Moore) $\mathcal{L}$-algebras, i.e., algebras for the monad $\mathcal{L}$. Similarly, for a comonad $\mathcal{B} = (\mathcal{B}, \epsilon, \delta)$, the category $\text{Coalg}(\mathcal{B})$ consists of Eilenberg-Moore coalgebras for the comonad $\mathcal{B}$. Notice that we use the notation $\mathcal{L}, \mathcal{B}$ to refer to (co)monads, and $\mathcal{L}, \mathcal{B}$ to refer to the underlying functors.

Each of the categories $\text{alg}(\mathcal{L})$, $\text{Alg}(\mathcal{L})$, $\text{coalg}(\mathcal{B})$, and $\text{Coalg}(\mathcal{B})$ has a canonical forgetful functor into the underlying category. For instance, the forgetful functor for $\text{Alg}(\mathcal{L})$ is the functor $U: \text{Alg}(\mathcal{L}) \to \mathcal{D}$ defined as $U(X, \alpha) = X$ and $Uf = f$ for any $\mathcal{L}$-algebra morphism $f$. We will refer to those forgetful functors without giving them a specific name.

### 3 Equations and coequations

We introduce the abstract definitions of equations and coequations. Let $\mathcal{L}$ be an endofunctor on $\mathcal{D}$ and $\mathcal{S}$ be an object in $\mathcal{D}$. The free $\mathcal{L}$-algebra on $\mathcal{S}$ generators is an algebra $\mathfrak{F}(\mathcal{S}) = (\mathfrak{F}(\mathcal{S}), \tau) \in \text{alg}(\mathcal{L})$ together with a morphism $\eta \in \mathcal{D}(\mathcal{S}, \mathfrak{F}(\mathcal{S}))$, called unit, satisfying the following universal property: for any $\mathcal{L}$-algebra $\mathcal{X} = (\mathcal{X}, \alpha)$ and any morphism $f \in \mathcal{D}(\mathcal{S}, \mathcal{X})$ there is a unique morphism $f^\sharp \in \text{alg}(\mathcal{L})(\mathfrak{F}(\mathcal{S}), \mathcal{X})$ such that $f^\sharp \circ \eta = f$, i.e., the following diagram commutes:

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

We define equations for $\mathcal{L}$ on $\mathcal{S}$ generators as epimorphisms with domain $\mathfrak{F}(\mathcal{S})$, i.e., elements $e_P \in \text{alg}(\mathcal{L})(\mathfrak{F}(\mathcal{S}), \mathcal{P})$ that are epimorphisms for some $\mathcal{P} = (\mathcal{P}, \zeta) \in \text{alg}(\mathcal{L})$. Observe that if $\mathcal{L}$ is a polynomial functor on Set (see, e.g., [22, Section 10]) then equations can be identified with $\mathcal{L}$-congruences $\mathcal{C}$ of $\mathfrak{F}(\mathcal{S})$, since $\mathfrak{F}(\mathcal{S})/\mathcal{C} \cong \mathcal{P}$ for $\mathcal{C} = \text{ker}(e_P)$, and elements in $\mathcal{C}$ are pairs of terms with variables on the set $\mathcal{S}$. This corresponds to the classical definition of equations in universal algebra. Finally, we say that an $\mathcal{L}$-algebra $\mathcal{X} = (\mathcal{X}, \alpha)$ satisfies the equation $e_P$, denoted as $(\mathcal{X}, \alpha) \models e_P$, if for any morphism $f \in \mathcal{D}(\mathcal{S}, \mathcal{X})$ the morphism $f^\sharp$ factors through $e_P$, i.e., there exists $g_f \in \text{alg}(\mathcal{L})(\mathcal{P}, \mathcal{X})$ such that the following diagram commutes:
<figure><img src="image_3.png" /></figure>

Now, assuming that the free $L$-algebra on $S$ generators $\mathfrak{F}(S) = (\mathfrak{F}(S), \tau)$ exists, we can define the category $\text{eq}(L, S)$ of equations for $L$ on $S$ generators as follows:

Objects of $\text{eq}(L, S)$: epimorphisms $e_X \in \text{alg}(L)(\mathfrak{F}(S), X)$ for some
$X = (X, \alpha) \in \text{alg}(L)$.

Arrows of $\text{eq}(L, S)$: for $e_{X_i} \in \text{eq}(L, S), i = 1, 2$, a morphism
$f \in \text{eq}(L, S)(e_{X_1}, e_{X_2})$ is a morphism $f \in \text{alg}(L)(X_1, X_2)$
such that the following diagram commutes:

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

Notice that morphisms in $\text{eq}(L, S)$ are necessarily epimorphisms.

**Example 1.** Consider the Set endofunctor $L$ given by $LX = A \times X$, where $A$ is a fixed set, and the singleton set $S = 1$ of generators. Then an $L$-algebra together with an assignment of the single generator is a *pointed deterministic automaton*, i.e., a triple $(X, \alpha, x)$ consisting of a set of states $X$, a transition function $\alpha: A \times X \to X$ and an element $x \in X$.

The free $L$-algebra on 1 is given by $A^* = (A^*, \tau)$ where $\tau: A \times A^* \to A^*$ is defined by $\tau(a, w) = wa$ and the unit $\eta: 1 \to A^*$ maps the single generator to the empty word $\varepsilon \in A^*$, i.e., $\eta = \varepsilon$. Given a pointed automaton $(X, \alpha, x)$ we obtain a unique homomorphism $r_x: A^* \to X$, given by $r_x(\varepsilon) = x$ and $r_x(wa) = \alpha(a, r_x(w))$. In the sequel we sometimes denote $r_x(w)$ by $w(x)$, the state we reach from the state $x$ by processing the word $w$.

A *right congruence on* $A^*$ is an equivalence relation $C \subseteq A^* \times A^*$ such that for any $a \in A$ and $(u, v) \in C$ we have that $(ua, va) \in C$. Right congruences $C$ correspond to equations as defined above, by letting $A^*/C = (A^*/C, [\tau]) \in \text{alg}(L)$ where $[\tau]$ is given by $[\tau](a, [w]) = [wa]$ and the epimorphism (equation) $e_C \in \text{alg}(L)(A^*, A^*/C)$ maps every word to its equivalence class.
An $L$-algebra $(X, \alpha)$ satisfies the equation $e_C$, i.e., $(X, \alpha) \models C$, if and only if for every $(u, v) \in C$ and any $x \in X$, we have $r_x(u) = r_x(v)$. This coincides with satisfaction of equations as defined in [7].

Notice that the function $\tau': A \times A^* \to A^*$ defined as $\tau'(a, w) = aw$ is such that the algebra $(A^*, \tau')$ is also a free $L$-algebra, which gives us the notion of left congruence as a corresponding notion of equation. $\square$

We dualize the definition of equations to obtain the definition of coequations, e.g., [22, 18, 19]. Let $B$ be an endofunctor on $C$ and $R$ be an object in $C$. The cofree $B$-coalgebra on $R$ colours is a coalgebra $\mathfrak{C}(R) = (\mathfrak{C}(R), v) \in \text{coalg}(B)$ together with a morphism $\epsilon \in \mathcal{C}(\mathfrak{C}(R), R)$, called counit, satisfying the following universal property: for any $B$-coalgebra $Y = (Y, \beta)$ and any morphism (colouring) $f \in \mathcal{C}(Y, R)$ there is a unique morphism $f^b \in \text{coalg}(L)(Y, \mathfrak{C}(R))$ such that $\epsilon \circ f^b = f$, i.e., the following diagram commutes:

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

We define coequations for $B$ on $R$ colours as monomorphisms with codomain $\mathfrak{C}(R)$, i.e., elements $m_Q \in \text{coalg}(B)(Q, \mathfrak{C}(R))$ that are monomorphisms for some $Q = (Q, \delta) \in \text{coalg}(B)$. We say that a $B$-coalgebra $Y = (Y, \beta)$ satisfies the coequation $m_Q$, denoted as $(Y, \beta) \models m_Q$ (notice the difference between the symbols: $\models$ for equations and $\models$ for coequations), if for any morphism (colouring) $f \in \mathcal{C}(Y, R)$ the morphism $f^b$ factors through $m_Q$, i.e., there exists $g_f \in \text{coalg}(B)(Y, Q)$ such that the following diagram commutes:

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

Assuming that the cofree $B$-coalgebra on $R$ colours $\mathfrak{C}(R) = (\mathfrak{C}(R), v)$ exists, define the category coeq$(B, R)$ of coequations for $B$ on $R$ colours whose objects are monomorphisms $m_Y \in \text{coalg}(B)(Y, \mathfrak{C}(R))$ for some $Y = (Y, \beta) \in \text{coalg}(B)$, and, a morphism between two objects $m_{Y_1}$ and $m_{Y_2}$ in coeq$(B, R)$ is a morphism $g \in \text{coalg}(B)(Y_1, Y_2)$ such that $m_{Y_2} \circ g = m_{Y_1}$. Notice that morphisms in coeq$(B, R)$ are necessarily monomorphisms.
*Example 2.* For a given set $A$, consider the Set endofunctor $B$ defined by $BX = X^A$, and consider the two-element set $R = 2$ of colours. Then a $B$-coalgebra together with an assignment of colours to states is a coloured deterministic automaton: a triple $(Y, \beta, f)$ consisting of a set of states $Y$, a transition function $\beta: Y \to Y^A$ and an assignment of final states $f: Y \to 2$.

The cofree $B$-coalgebra on 2 colours is given by $2^{A^*} = (2^{A^*}, v)$ where $v: 2^{A^*} \to (2^{A^*})^A$ is given by right derivative

$$v(L)(a) = L_a = \{w \mid aw \in L\}$$

and the counit $\epsilon: 2^{A^*} \to 2$ is given by $\epsilon(L) = L(\epsilon)$. Given a coloured deterministic automaton $(Y, \beta, f)$, we obtain a unique $B$-coalgebra morphism $l: Y \to 2^{A^*}$ that maps every state to the language it accepts, i.e., $l(x)(\epsilon) = f(x)$ and $l(x)(aw) = l(\beta(x)(a))(w)$.

Coequations for $B$ on $R$ correspond to subsets of $2^{A^*}$ that are closed under right derivatives, i.e., subcoalgebras of $2^{A^*}$. Given any monomorphism (coequation) $m_Q$ with codomain $2^{A^*}$ and a $B$-coalgebra $(Y, \beta)$, we have that $(Y, \beta) \models m_Q$ if and only if for every 2-colouring $f \in \text{Set}(Y, 2)$ the set of those languages accepted by the states of the coloured automaton $(Y, \beta, f)$ is contained in $\text{Im}(m_Q)$. This coincides with satisfaction of coequations as defined in [7].

Similarly to the previous example, the function $v': 2^{A^*} \to (2^{A^*})^A$ given by left derivative

$$v'(L)(a) = aL = \{w \mid wa \in L\}$$

is such that $(2^{A^*}, v')$ is also a cofree $B$-coalgebra for which the corresponding notion of coequations are subsets of $2^{A^*}$ closed under left derivatives. $\square$

# 4 Lifting contravariant adjunctions

In this section we recall the notion of a contravariant adjunction and how to lift it to categories of algebras and coalgebras, according to [13, 14]. We instantiate this abstract approach in examples of constructions on various kinds of automata.

Given two contravariant functors $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ (i.e., $F$ and $G$ reverse the direction of arrows), a contravariant adjunction between $F$ and $G$, denoted by $F \dashv G$, is a bijection

$$\mathcal{D}(X, FY) \cong \mathcal{C}(Y, GX)$$

which is natural in both $X \in \mathcal{D}$ and $Y \in \mathcal{C}$. Observe that both $F$ and $G$ are on the codomain of the Hom-sets. Such a contravariant adjunction can be equivalently defined by two units $\eta^{FG}: \text{Id}_\mathcal{D} \Rightarrow FG$ and $\eta^{GF}: \text{Id}_\mathcal{C} \Rightarrow GF$ that satisfy the triangle identities $G\eta^{FG} \circ \eta_G^{GF} = \text{Id}_\mathcal{G}$ and $F\eta^{GF} \circ \eta_F^{FG} = \text{Id}_\mathcal{F}$. By standard preservation properties, both $F$ and $G$ map colimits to limits, in particular initial objects to final objects and epimorphisms to monomorphisms.

Given a contravariant adjunction as above, if $\eta^{GF}$ and $\eta^{FG}$ are isomorphisms then we say $F, G$ form a duality, and denote it by $F \cong G$. In this case, limits are mapped to colimits and vice versa.
Our basic setting consists of a contravariant adjunction between $F$ and $G$, an endofunctor $B$ on $C$ and an endofunctor $L$ on $D$, depicted in the diagram below. Throughout this paper we depict contravariant functors in diagrams with an ‘×’ at the beginning of the arrow.

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

In this setting, we are interested in lifting the adjunction to a contravariant adjunction between lifted functors $\hat{F}: \text{coalg}(B) \to \text{alg}(L)$ and $\hat{G}: \text{alg}(L) \to \text{coalg}(B)$ of $F$ and $G$, respectively, as in the following picture:

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

where the vertical arrows are forgetful functors. An important consequence of such a lifting is that, if $L$ has an initial algebra, then it is mapped by $\hat{G}$ to a final $B$-coalgebra.

In [13, 2.14. Theorem] it is shown that a sufficient condition for such a lifting is the existence of a natural isomorphism $\gamma: GL \Rightarrow BG$. This is summarized by the theorem below.

**Theorem 3.** Let $F: C \to D$ and $G: D \to C$ be contravariant functors that form a contravariant adjunction. Let $B$ be an endofunctor on $C$ and $L$ be an endofunctor on $D$. If there is a natural isomorphism $\gamma: GL \Rightarrow BG$, then

1. The adjunction $F \dashv G$ lifts to an adjunction as in Diagram (1), i.e., to a contravariant adjunction between functors $\hat{F}: \text{coalg}(B) \to \text{alg}(L)$ and $\hat{G}: \text{alg}(L) \to \text{coalg}(B)$.

2. If $F, G$ form a duality then $\hat{F}, \hat{G}$ form a duality as well.

The functors $\hat{F}: \text{coalg}(B) \to \text{alg}(L)$ and $\hat{G}: \text{alg}(L) \to \text{coalg}(B)$ are defined on objects as:

$$ (Y \xrightarrow{\beta} BY) \stackrel{\hat{F}}{\longmapsto} (LFY \xrightarrow{\rho_Y} FBY \xrightarrow{F\beta} FY) $$

$$ (LX \xrightarrow{\alpha} X) \stackrel{\hat{G}}{\longmapsto} (GX \xrightarrow{G\alpha} GLX \xrightarrow{\gamma_X} BGX) $$
and on morphisms as $\hat{F} = F$ and $\hat{G} = G$. The natural transformation $\rho: LF \Rightarrow FB$ in the definition of $\hat{F}$ is defined as the mate of the inverse $\gamma^{-1}: BG \Rightarrow GL$:

$$ \rho \stackrel{\text{def.}}{=} FB\eta^{GF} \circ F\gamma^{-1}F \circ \eta^{FG}LF, $$

using the units $\eta^{GF}$ and $\eta^{FG}$ of the adjunction. Natural transformations of the form $\rho: LF \Rightarrow FB$ and the definition of $\hat{F}$ form the heart of the approach to coalgebraic modal logic based on contravariant adjunctions/dualities (see, e.g., [16, 15, 20, 8]). There is a one-to-one correspondence between such natural transformations and those of the form $BG \Rightarrow GL$, using the above construction. We are only interested in the case where the natural transformation $BG \Rightarrow GL$ is an isomorphism, to lift adjunctions, as in [17]. For notational convenience, the direction in $\gamma: GL \Rightarrow BG$ is reversed in the current paper.

In the rest of this section we provide examples and applications of Theorem 3 and the setting in Diagram (1).

**Example 4.** [[17, Example 4]] For a fixed set $A$ consider the following situation:

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

Here $L$-algebras are pointed deterministic automata on $A$ (Example 1) and $B$-coalgebras are two-coloured deterministic automata on $A$ (Example 2). The contravariant functors $F$ and $G$ form a contravariant adjunction which, by Theorem 3, can be lifted to an adjunction between $\hat{F}$ and $\hat{G}$. The isomorphism $\gamma: GL \Rightarrow BG$ is defined for any $X$ as the function $\gamma_X: 2^{A \times X+1} \to 2 \times (2^X)^A$ such that $\gamma_X(f) = (f(\cdot), \lambda a. \lambda x.f(a, x))$.

Given a $B$-coalgebra $(Y, \langle c, \beta \rangle)$ we have that $\hat{F}(Y, \langle c, \beta \rangle) = (2^Y, [\alpha, i])$ where $\alpha: A \times 2^Y \to 2^Y$ and $i: 1 \to 2^Y$ are functions defined as follows:

$$ \begin{gathered} i(\cdot) = c^{-1}(\{1\}) = \text{accepting states of } (Y, \langle c, \beta \rangle), \\ \alpha(a, Z) = \{y \in Y \mid \beta(y)(a) \in Z\}. \end{gathered} $$

Given an $L$-algebra $(X, [\alpha, i])$ we have that $\hat{G}(X, [\alpha, i]) = (2^X, \langle c, \beta \rangle)$ where the functions $c: 2^X \to 2$ and $\beta: 2^X \to (2^X)^A$ are defined as:

$$ \begin{gathered} c(Z) = 1 \quad \text{iff} \quad i(\cdot) \in Z \\ \beta(Z)(a) = \{x \in X \mid \alpha(a, x) \in Z\} \end{gathered} $$

Recall from Example 1 that the initial $L$-algebra is given by $(A^*, [\eta, \tau'])$, where $A^*$ is the free monoid with generators $A$ and identity element $\varepsilon$, $\eta: 1 \to A^*$ is the empty word $\varepsilon$ and $\tau': A \times A^* \to A^*$ is the concatenation function given by $\tau'(a, w) = aw$. Because of the contravariant adjunction, the initial $L$-algebra is sent by $\hat{G}$ to the final $B$-coalgebra, given by $\hat{G}(A^*, [\eta, \tau']) = (2^{A^*}, \langle \hat{\varepsilon}, \hat{\tau} \rangle)$ where $\hat{\varepsilon}(L) = L(\varepsilon)$ and $\hat{\tau}(L)(a)(w) = L(aw)$. Note that the final $B$-coalgebra is not sent by $\hat{F}$ to the initial $L$-algebra. $\square$
*Example 5.* Let CABA be the category of complete atomic Boolean algebras whose morphisms are complete Boolean algebra homomorphisms. For a fixed set A consider the following situation:

$$
\begin{array}{ccc}
 & FY = \mathrm{At}(Y) & \\
 B \underset{G}{\overset{F}{\rightleftarrows}} & & \\
 & GX = 2^X & \\
 & LX = (A \times X) + 1 & \\
 & BY = 2 \times Y^A & \\
 & \gamma_X : 2^{A \times X+1} \to 2 \times (2^X)^A &
\end{array}
$$

Here $\mathrm{At}(Y)$ denotes the set of atoms of the object $Y$ in CABA. The contravariant functors $F$ and $G$ form a contravariant adjunction, in fact a duality, which, by Theorem 3, can be lifted to a duality between $\hat{F}$ and $\hat{G}$ if we consider the canonical natural isomorphism $\gamma: GL \Rightarrow BG$ defined for every $X$ as the morphism $\gamma_X: 2^{A \times X+1} \to 2 \times (2^X)^A$ such that $\gamma_X(f) = (f(\cdot), \lambda a. \lambda x.f(a, x))$.

Given a B-coalgebra $(Y, \langle c, \beta \rangle)$, we have that $\hat{F}(Y, \langle c, \beta \rangle) = (\mathrm{At}(Y), [\alpha, i])$
where the functions $\alpha: A \times \mathrm{At}(Y) \to \mathrm{At}(Y)$ and $i: 1 \to \mathrm{At}(Y)$ are defined as
follows:

$$
\begin{array}{l}
i(\cdot) = \text{the unique element } y_0 \in \mathrm{At}(Y) \text{ s.t. } c(y_0) = 1, \\
\alpha(a, y) = \text{the unique element } y' \in \mathrm{At}(Y) \text{ s.t. } \beta(y')(a) \geq y.
\end{array}
$$

In particular, if $P \subseteq 2^{A^*}$ is a *preformation of languages* [7, Definition 11], i.e.,
$P \in \text{CABA}$ and it is closed under left and right derivatives $^1$, then $(P, \langle \hat{\epsilon}, \hat{\tau}' \rangle) \in$
coalg$(B)$ where $\hat{\epsilon}(L) = L(\epsilon)$ and $\hat{\tau}'(L)(a) = {}_a L$. In this case, $\hat{F}(P, \langle \hat{\epsilon}, \hat{\tau}' \rangle) =$
*free*(P) which is the quotient $A^*/C$ where $C$ is the set, in fact congruence, of
all equations satisfied by the automaton $(P, \hat{\tau})$, where $\hat{\tau}(L)(a) = L_a$ (see [7]).

Given an L-algebra $(X, [\alpha, i])$, we have that $\hat{G}(X, [\alpha, i]) = (2^X, \langle c, \beta \rangle)$ where the CABA morphisms $c: 2^X \to 2$ and $\beta: 2^X \to (2^X)^A$ are defined as

$$
\begin{array}{l}
c(Z) = 1 \quad \text{iff} \quad i(\cdot) \in Z \\
\beta(Z)(a) = \{x \in X \mid \alpha(a, x) \in Z\}.
\end{array}
$$

In particular, if $C$ is a congruence of the monoid $A^*$ then $(A^*/C, [[\tau'], [\varepsilon]]) \in$
alg$(L)$ where $[\tau')(a, [w]) = [aw]$. In this case, $\hat{G}(A^*/C, [[\tau'], [\varepsilon]]) \cong \textbf{cofree}(A^*/C)$
which is the minimum set of coequations that the automaton $(A^*/C, [\tau])$ satisfies,
where $[\tau](a, [w]) = [wa]$ (see [7]).

Similarly to the previous example, the initial L-algebra $A^* = (A^*, [\eta, \tau'])$,
where $\eta = \varepsilon$ and $\tau'(a, w) = aw$, is sent by $\hat{G}$ to the final B-coalgebra $2^{A^*} =$
$(2^{A^*}, \langle \hat{\epsilon}, \hat{\tau} \rangle)$, where $\hat{\epsilon}(L) = L(\varepsilon)$ and $\hat{\tau}(L)(a)(w) = L(aw)$. Also, because the
contravariant adjunction is a duality, the final B-coalgebra $2^{A^*}$ is sent by $\hat{F}$ to
the initial L-algebra $A^*$. We will explore this case further in Section 5 to get
dualities between sets of equations and sets of coequations.
$\square$

<footnote n="1">¹ $P \subseteq 2^{A^*}$ is closed under right (left) derivatives if for every $L \in P$ and $a \in A$, $L_a \in P$ ($_a L \in P$). Here $L_a(w) = L(aw)$, and ${}_a L(w) = L(wa)$, $w \in A^*$.</footnote>
*Example 6.* For a fixed field $K$, let $\mathrm{Vec}_K$ be the category of vector spaces over $K$ with linear maps. Let $A$ be a fixed set and consider the following situation:

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

$$FX = GX = X^{\partial}$$

$$LX = K + (A \times X)$$

$$BY = K \times Y^A$$

$$\gamma_X : (K + A \times X)^{\partial} \to K \times (X^{\partial})^A$$

Here $X^{\partial} = \mathrm{Vec}_K(X, K)$, the dual space of $X$, and $A \times X := \coprod_{a \in A} X$. We have that the contravariant functors $F$ and $G$ form a contravariant adjunction which, by Theorem 3, can be lifted to a contravariant adjunction between $\hat{F}$ and $\hat{G}$ if we consider the canonical natural isomorphism $\gamma: GL \Rightarrow BG$ defined for every $X$ as the map $\gamma_X : (K + A \times X)^{\partial} \to K \times (X^{\partial})^A$ such that $\gamma_X(\varphi) = (\varphi(1), \lambda a. \lambda x. \varphi(a, x))$.

Given a $B$-coalgebra $(Y, \langle c, \beta \rangle)$, we have that $\hat{F}(Y, \langle c, \beta \rangle) = (Y^{\partial}, [i, \alpha])$ where $i: K \to Y^{\partial}$ and $\alpha: A \times Y^{\partial} \to Y^{\partial}$ are linear maps which are defined on the canonical basis as:

$$i(1)(y) = c(y)$$

$$\alpha(a, \varphi)(y) = (\varphi \circ \beta(y))(a) = \varphi(\beta(y)(a))$$

In particular, if $S \subseteq K^{A^*}$ is a subsystem such that for every $f \in S$ and $a \in A$, $f_a, a f \in S$, where $f_a(w) = f(aw)$ and $a f(w) = f(wa)$, $w \in A^*$, then we have that $(S, \langle \hat{\epsilon}, \hat{\tau}' \rangle) \in \mathrm{coalg}(B)$ where $\hat{\epsilon}(f) = f(\epsilon)$ and $\hat{\tau}'(f)(a) = a f$. In this case, $\hat{F}(S, \langle \hat{\epsilon}, \hat{\tau}' \rangle) \cong \mathrm{free}(S)$ which is the quotient $V(A^*)/C$ where $C$ is the set, in fact linear congruence, of all linear equations satisfied by the automaton $(S, \hat{\tau})$. Here $V(A^*) = \{\phi: A^* \to K \mid \mathrm{supp}(\phi) \text{ is finite}\}$, where $\mathrm{supp}(\phi) = \{w \in A^* \mid \phi(w) \neq 0\}$ is the support of $\phi$, and the function $\hat{\tau}$ is defined as $\hat{\tau}(f)(a) = f_a$ (see [25]).

Given an $L$-algebra $(X, [i, \alpha])$, we have that $\hat{G}(X, [i, \alpha]) = (X^{\partial}, \langle c, \beta \rangle)$ where the linear maps $c: X^{\partial} \to K$ and $\beta: X^{\partial} \to (X^{\partial})^A$ are defined as

$$c(\varphi) = \varphi(i(1))$$

$$\beta(\varphi)(a)(x) = \varphi(\alpha(a, x))$$

In particular, if $C \subseteq V(A^*) \times V(A^*)$ is a linear congruence on $V(A^*)$, then we have that $(V(A^*)/C, [[\tau'], [\epsilon]]) \in \mathrm{alg}(L)$, where $[\tau')(a, [\phi]) = [a\phi]$, and we have that $\hat{G}(V(A^*)/C, [[\tau'], [\epsilon]]) \cong \mathrm{cofree}(V(A^*)/C)$ which is the minimum set of coequations (power series) satisfied by the automaton $(V(A^*)/C, [\tau])$, where $[\tau](a, [\phi]) = [\phi a]$ (see [25]).

Notice that the contravariant adjunction is not a duality, but if we restrict to vector spaces of finite dimension then we get a duality. In the latter case there is no initial $L$-algebra or, equivalently, there is no final $B$-coalgebra. $\square$

# 5 Duality between equations and coequations

In Section 3, we defined equations as epimorphisms from an initial algebra and coequations as monomorphisms into a final coalgebra. In the previous section, we
2. Given $e_P \in \text{eq}(L, S)$, $m_Q \in \text{coeq}(B, G(S))$, $(X, \alpha) \in \text{alg}(L)$, and $(Y, \beta) \in \text{coalg}(B)$ we have:

i) $(X, \alpha) \models e_P$ if and only if $\hat{G}(X, \alpha) \models \hat{G}(e_P)$.

ii) $\hat{F}(Y, \beta) \models \hat{F}(m_Q)$ if and only if $(Y, \beta) \models m_Q$.

As an application of the previous theorem we have the following.

*Example 8.* (cf. Example 5) For a fixed set $A$ consider the following situation:

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

If we put $S = 1$, then we get a duality between $\text{eq}(L, 1)$, whose objects can be identified with right congruences of $A^*$, and $\text{coeq}(B, 2)$, whose objects can be identified with subalgebras $Q \subseteq 2^{A^*}$ in CABA that are closed under left derivatives. From this setting, if we consider congruences of $A^*$ and subalgebras of $2^{A^*}$ that are closed both under left and right derivatives, we can derive the duality between equations and coequations that was shown in [7, Theorem 22]. We will come back to this situation in a more general setting in Section 7.1 and also in a slightly different setting in Section 7.2. $\square$

*Example 9.* In this example we explicitly show that if the contravariant adjunction is not a duality then sets of coequations are not always sent to sets of equations. For the set $A = \{a, b\}$ consider the situation:

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

In this case, consider the set $S = 1$ of generators. The free $L$-algebra on $S$ generators is given by $A^* = (A^*, \tau')$, where $\tau'(a, w) = aw$, and unit $\eta = \varepsilon$. The cofree $B$-coalgebra on $G(S) = 2$ colours is the coalgebra $2^{A^*} = (2^{A^*}, \nu) = \hat{G}(A^*)$, where $\nu(L)(a)(w) = L(aw)$, and counit $\epsilon(L) = L(\varepsilon)$. Now, consider the element $m_Q \in \text{coeq}(B, 2)$ where $Q = \{\emptyset, A^*\}$ and $m_Q$ is the inclusion map $m_Q: Q \to 2^{A^*}$. Then the codomain of $\hat{F}(m_Q)$ is $(2^Q, \alpha)$ where $\alpha(a, f) = \alpha(b, f) = f$ for all $f \in 2^Q$ (this definition of $\alpha$ follows from Example 4).

We have that $2^Q = (2^Q, \alpha)$ cannot be a homomorphic image of $A^*$. In fact, if there exists an epimorphism $e \in \text{alg}(L)(A^*, 2^Q)$ then there is a right congruence $C$ of $A^*$ such that $(A^*/C, [\tau']) \cong (2^Q, \alpha)$ which means that $A^*/C$ has four equivalence classes and for each equivalence class $[w] \in A^*/C$ we have that $[w] = [aw] = [bw]$, which is a contradiction since the last equality implies that there is only one equivalence class. $\square$
## 5.1 Equations for coalgebras

In this section we show how to define equations for coalgebras by using liftings of contravariant adjunctions. The concepts presented here can be dualized to define coequations for algebras.

Assume that we have lifted a contravariant adjunction between functors $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ to a contravariant adjunction between $\hat{F}: \text{coalg}(B) \to \text{alg}(L)$ and $\hat{G}: \text{alg}(L) \to \text{coalg}(B)$ for an endofunctor $B$ on $\mathcal{C}$ and an endofunctor $L$ on $\mathcal{D}$. Given an equation $e_P \in \text{eq}(L, S)$ for some $S$ in $\mathcal{D}$, we define, for a given coalgebra $(Y, \beta)$ in $\text{coalg}(B)$, $(Y, \beta) \models e_P$, and say that the coalgebra $(Y, \beta)$ satisfies the equation $e_P$, as:

$$ (Y, \beta) \models e_P \iff^{\text{def}} \hat{F}(Y, \beta) \models e_P. $$

Notice that if $\hat{F}$ and $\hat{G}$ form a duality then $\hat{F}(Y, \beta) \models e_P$ is equivalent to $(Y, \beta) \models \hat{G}(e_P)$. One could be tempted to use $(Y, \beta) \models \hat{G}(e_P)$ as a definition for $(Y, \beta) \models e_P$ since $\hat{G}(e_P) \in \text{coeq}(B, G(S))$ but we prefer to avoid this since the dual argument is not true in general, i.e., given $m_Q \in \text{coeq}(B, G(S))$, $\hat{F}(m_Q)$ is not always in $\text{eq}(L, S)$, as it was shown in Example 9.

**Example 10.** Consider the situation given in Example 4 and let $S = \emptyset$. Then we have that for a B-coalgebra (deterministic automaton) $Y = (Y, \langle c, \beta \rangle)$ and a right congruence $C$ on $A^*$:

$$ (Y, \langle c, \beta \rangle) \models C \iff \begin{cases} \forall (u, v) \in C \ u(i(\cdot)) = v(i(\cdot)) \text{ in } \hat{F}(Y, \langle c, \beta \rangle) \\ \forall (u, v) \in C \ \{x \in X \mid c(u(x)) = 1\} = \{x \in X \mid c(v(x)) = 1\}. \end{cases} $$

In words, a right congruence $C$ on $A^*$ is satisfied by $Y = (Y, \langle c, \beta \rangle)$ if for every pair $(u, v) \in C$ the set of states that accept $u$ coincides with the set of states that accept $v$.

In Example 1 we also defined satisfaction of right congruences for deterministic automata, as the canonical notion that arises by viewing (the transition structure of) automata as algebras. According to this, if we consider $(Y, \beta)$ as an $A \times \text{Id}_{\text{Set}}$-algebra, we have a direct definition for $(Y, \beta) \models C$. We conclude this example by showing the relation between $(Y, \langle c, \beta \rangle) \models C$ and $(Y, \beta) \models C$.

Consider the coloured automaton $(Y, \langle c, \beta \rangle)$ on $A = \{a\}$ given by:

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

If we denote by $\langle u = v \rangle$ the least right congruence containing the pair $(u, v) \in A^* \times A^*$, then we have that $(Y, \langle c, \beta \rangle) \models \langle a = aa \rangle$ since

$$ \{y \in Y \mid c(a(y)) = 1\} = \{r, s, t\} = \{y \in Y \mid c(aa(y)) = 1\} $$

but $(Y, \beta) \not\models \langle a = aa \rangle$ since $a(r) = s \neq t = aa(r)$. One can prove that $(Y, \beta) \models \langle u = v \rangle$ implies $(Y, \langle c, \beta \rangle) \models \langle u = v \rangle$ and that the converse holds if $(Y, \langle c, \beta \rangle)$ is minimal. $\square$
**Theorem 12.** Let $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ be contravariant functors that form a duality. Let $\mathbf{L} = (L, \eta, \mu)$ be a monad on $\mathcal{D}$, and $\mathbf{B} = (B, \epsilon, \delta)$ a comonad on $\mathcal{C}$. If there is a natural isomorphism $\gamma: GL \Rightarrow BG$ making the diagrams (3) commute, then:

1. The duality between $F$ and $G$ lifts to a duality $\hat{F}: \mathrm{Coeq}(\mathbf{B}, G(S)) \to \mathrm{Eq}(\mathbf{L}, S)$ and $\hat{G}: \mathrm{Eq}(\mathbf{L}, S) \to \mathrm{Coeq}(\mathbf{B}, G(S))$.

2. Given $e_P \in \mathrm{Eq}(\mathbf{L}, S)$, $m_Q \in \mathrm{Coeq}(\mathbf{B}, G(S))$, $(X, \alpha) \in \mathrm{Alg}(\mathbf{L})$, and $(Y, \beta) \in \mathrm{Coalg}(\mathbf{B})$ we have that:

i) $(X, \alpha) \models e_P$ if and only if $\hat{G}(X, \alpha) \models \hat{G}(e_P)$.

ii) $\hat{F}(Y, \beta) \models \hat{F}(m_Q)$ if and only if $(Y, \beta) \models m_Q$.

We proceed with special cases of our setting where, given the contravariant adjunction and a comonad $\mathbf{B}$ on $\mathcal{C}$, we can canonically define a monad $\mathbf{L}$ on $\mathcal{D}$ such that the contravariant adjunction lifts (Section 6.1). We can also do it in the opposite way, i.e., define a comonad from a given monad, but in this case additional assumptions are required (Section 6.2).

## 6.1 Defining a monad from a comonad

In this part we start with a contravariant adjunction between contravariant functors $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ and a comonad $\mathbf{B} = (B, \epsilon, \delta)$ on $\mathcal{C}$. That is, we have the following setting:

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

The purpose is to find a canonical monad $\mathbf{L} = (L, \eta, \mu)$ on $\mathcal{D}$ together with a lifting $\hat{F}: \mathrm{Coalg}(\mathbf{B}) \to \mathrm{Alg}(\mathbf{L})$ and $\hat{G}: \mathrm{Alg}(\mathbf{L}) \to \mathrm{Coalg}(\mathbf{B})$ of the contravariant adjunction. We choose $L = FBG$, and define $\eta: \mathrm{Id}_\mathcal{D} \Rightarrow L$ and $\mu: LL \Rightarrow L$ by:

$$ \eta = (\mathrm{Id}_\mathcal{D} \underset{\mathrm{FG}}{\overset{\eta^{\mathrm{FG}}}{\Rightarrow}} \mathrm{FG} \underset{\mathrm{FG}}{\overset{\mathrm{F}\epsilon_{\mathrm{G}}}{\Rightarrow}} \mathrm{FBG}) \qquad (4) $$

$$ \mu = (\mathrm{FBGFBG} \underset{\mathrm{FBG}}{\overset{\mathrm{FB}\eta_{\mathrm{BG}}^{\mathrm{GF}}}{\rightleftharpoons}} \mathrm{FBBG} \underset{\mathrm{FBG}}{\overset{\mathrm{F}\delta_{\mathrm{G}}}{\Rightarrow}} \mathrm{FBG}) $$

where $\eta^{\mathrm{FG}}$ and $\eta^{\mathrm{GF}}$ are the units of the contravariant adjunction. With this choice of $(L, \eta, \mu)$ we have the following result.

**Proposition 13.** Let $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ be contravariant functors that form a contravariant adjunction. Let $\mathbf{B} = (B, \epsilon, \delta)$ be a comonad on $\mathcal{C}$. Then $(L, \eta, \mu)$ with $L = FBG$ and $\eta, \mu$ defined as in (4) is a monad on $\mathcal{D}$.

Additionally, if $\eta^{\mathrm{GF}}$ is a natural isomorphism, then the contravariant adjunction between $F$ and $G$ lifts to a contravariant adjunction between $\hat{F}: \mathrm{Coalg}(\mathbf{B}) \to \mathrm{Alg}(\mathbf{L})$ and $\hat{G}: \mathrm{Alg}(\mathbf{L}) \to \mathrm{Coalg}(\mathbf{B})$. In this case, if $F$ and $G$ form a duality then the lifting $\hat{F}$ and $\hat{G}$ is also a duality.
## 6.2 Defining a comonad from a monad

We can dualize the previous proposition in order to define a comonad on $\mathcal{C}$ if we have a monad on $\mathcal{D}$. In order to do this we will assume that the contravariant adjunction is a duality so we can use the fact that the units of the contravariant adjunction are isomorphisms.

Assume that we have a contravariant adjunction between two contravariant functors $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$, and $L = (L, \eta, \mu)$ a monad on $\mathcal{D}$. Define the endofunctor $B$ on $\mathcal{C}$ as $B = GLF$. Now, if we assume that the contravariant adjunction is a duality with units $\eta^{FG}: \mathrm{Id}_{\mathcal{D}} \Rightarrow FG$ and $\eta^{GF}: \mathrm{Id}_{\mathcal{C}} \Rightarrow GF$ that are natural isomorphisms. Then we can define natural transformations $\epsilon: B \Rightarrow \mathrm{Id}_{\mathcal{C}}$ and $\delta: B \Rightarrow BB$ as:

$$ \begin{aligned} \epsilon &= (GLF \underset{G\eta_F}{\overset{G\eta_F}{\rightleftharpoons}} GF \overset{(\eta^{GF})^{-1}}{\underset{(\eta^{GF})}{\rightleftharpoons}} \mathrm{Id}_{\mathcal{C}}) \\ \delta &= (GLF \underset{G\mu_F}{\overset{G\mu_F}{\rightleftharpoons}} GLLF \underset{L_F}{\overset{GL(\eta^{FG})^{-1}}{\rightleftharpoons}} GLFGLF) \end{aligned} \quad (5) $$

Under the previous assumptions and choice of $(B, \epsilon, \delta)$ we get:

**Proposition 14.** Let $F: \mathcal{C} \to \mathcal{D}$ and $G: \mathcal{D} \to \mathcal{C}$ be contravariant functors that form a duality. Let $L = (L, \eta, \mu)$ be a monad on $\mathcal{D}$. Then $(B, \epsilon, \delta)$, where $B = GLF$ and $\epsilon, \delta$ are defined as in (5), is a comonad on $\mathcal{C}$. Further, the duality between $F$ and $G$ lifts to a duality between $\hat{F}: \mathrm{Coalg}(\mathcal{B}) \to \mathrm{Alg}(\mathcal{L})$ and $\hat{G}: \mathrm{Alg}(\mathcal{L}) \to \mathrm{Coalg}(\mathcal{B})$.

# 7 Applications

In this section we will apply results from the previous section to study equations and coequations for dynamical systems and deterministic automata.

## 7.1 Equations and coequations for dynamical systems

Let $M = (M, \cdot, e)$ be a monoid, let $L = (L, \eta, \mu)$ be the monad on Set defined as:

$$ LX = X \times M \qquad \eta_X: X \to X \times M \qquad \mu_X: (X \times M) \times M \to X \times M \\ x \mapsto (x, e) \qquad (x, m, n) \mapsto (x, m \cdot n) $$

and let $B = (B, \epsilon, \delta)$ be the comonad on CABA defined as:

$$ BY = Y^M \qquad \epsilon_Y: Y^M \to Y \qquad \delta_Y: Y^M \to (Y^M)^M \\ f \mapsto f(e) \qquad f \mapsto \lambda_m \cdot \lambda_n f(n \cdot m) $$

Consider the duality between CABA and Set given by the contravariant functors $F: \mathrm{CABA} \to \mathrm{Set}$ and $G: \mathrm{Set} \to \mathrm{CABA}$ defined as $FY = \mathrm{At}(Y)$ and $GX = 2^X$, if we consider the natural isomorphism $\gamma: GL \Rightarrow BG$ given by the canonical isomorphism $\gamma_X: 2^{X \times M} \to (2^X)^M$ then we can easily verify the hypothesis of Theorem 11 to lift the duality between $F$ and $G$ from the following setting:
$$
\begin{array}{ccc}
 & & FY = \mathrm{At}(Y) \\
\mathbf{B} = (B, \epsilon, \delta) & \stackrel{\sim}{\rightleftharpoons} & GX = 2^X \\
 & & \\
 & \leftarrow \stackrel{F}{\rightleftharpoons} & LX = X \times M \\
 & \stackrel{\sim}{\rightleftharpoons} & \\
 & & \\
 & & BY = Y^M \\
 & & \\
 & & \gamma_X : 2^{X \times M} \to (2^X)^M
\end{array}
$$

Observe that elements $(X, \alpha) \in \mathrm{Alg}(\mathbf{L})$ are dynamical systems (monoid actions) on $\mathbf{Set}$, that is, an $\mathbf{L}$-algebra is a set $X$ together with a map $\alpha: X \times M \to X$ that satisfies the properties $\alpha(x, e) = x$ and $\alpha(\alpha(x, m), n) = \alpha(x, m \cdot n)$. Further, a $\mathbf{B}$-coalgebra is a set $Y$ with a map $\beta: Y \to Y^M$ such that $\beta(x)(e) = x$ and $\beta(\beta(x)(m))(n) = \beta(x)(n \cdot m)$.

We are going to consider equations and coequations for dynamical systems for the particular case that the set of generators is $S = 1$. We have that the free algebra $\mathfrak{F}(1)$ in $\mathrm{Alg}(\mathbf{L})$ on $S = 1$ generators is $\mathfrak{F}(1) = (M, \tau)$ where $\tau: M \times M \to M$ is given by $\tau(m, n) = m \cdot n$ and the unit $\eta: 1 \to M$ is given by $\eta = e$, the identity element in $M$. On the other hand, the cofree coalgebra $\mathfrak{C}(G(1)) = \mathfrak{C}(2)$ in $\mathrm{Coalg}(\mathbf{B})$ on 2 colours is $\mathfrak{C}(2) = (2^M, \hat{\tau})$, where $\hat{\tau}: 2^M \to (2^M)^M$ is given by

$$
\hat{\tau}(f)(n) = \{m \in M \mid f(m \cdot n) = 1\}
$$

and the count of $\epsilon: 2^M \to 2$ is given by $\epsilon(f) = f(e)$.

According to this, equations in Eq(L, 1) correspond to quotients $M/C = (M/C, [\tau])$ where $C \subseteq M \times M$ is a right congruence on $M$, i.e. an equivalence relation such that for any $p \in M$, $(m, n) \in C$ implies $(m \cdot p, n \cdot p) \in M$, and the function $[\tau]: M/C \times M \to M/C$ is given by $[\tau]([m], n) = [m \cdot n]$. On the other hand coequations in Coeq($\mathbf{L}$, $G(S)$) correspond to left-closed-subsystems $Q = (Q, \hat{\tau})$, i.e. subalgebras $Q$ of the complete atomic Boolean algebra $2^M$ such that for any $f \in Q$ and $m \in M$, $\hat{\tau}(f)(m) \in Q$.

Now, by using Theorem 12, we have as a consequence a correspondence between right congruences and left-closed-subsystems for dynamical systems.

**Proposition 15.** There is a duality between Eq(L, 1) and Coeq(B, 2) given by $\hat{F}$ and $\hat{G}$ that induces a duality between right congruences on M and left-closed-subsystems of $2^M$.

Using this duality one can prove that right congruences on $M$ and left-closed subsystems of $2^M$ characterize the same classes of dynamical systems.

**Proposition 16.** For any dynamical system $(X, \alpha)$ on $M$ and any right congruence $C$ on $M$ let $e_C \in \mathrm{Alg}(\mathbf{L})(M, M/C)$ be the canonical epimorphism (equation) defined as $e_C(m) = [m]$. The following are equivalent:

i) $(X, \alpha) \models e_C$.

ii) For every colouring $c: X \to 2$ and any $x \in X$ we have that

$$
\{m \in M \mid c(\beta(x)(m)) = 1\} \in \mathrm{Im}(\hat{G}(e_C)).
$$
If $M$ is the free monoid on $A$ generators then we get [24, Corollary 14]. In this case, property ii) in the previous proposition is the definition for satisfaction of coequations given in [7] where the set of coequations considered is $\mathrm{Im}(\hat{G}(e_C))$.

## 7.2 Equations and coequations for automata

Consider the following setting:

$$ \begin{tikzcd} \text{CABA} \arrow[r, "F"] \arrow[d, "G"] & \text{Set} \arrow[r, "\cong"] \arrow[d, "\cong"] & \text{L} = (L, \eta, \mu) \arrow[d, "\cong"'] \arrow[r, "\cong"] \arrow[d, "\cong"'] \end{tikzcd} $$

where $FY = \mathrm{At}(Y)$, $GX = 2^X$, and $L$ is the monad given by:

$$ LX = X^* = \coprod_{i \in \mathbb{N}} X^i \qquad \eta_X : X \to X^* \qquad \mu_X : (X^*)^* \to X^* \\ x \mapsto x \qquad w_1 \cdots w_n \mapsto w_1 \cdots w_n $$

According to Proposition 14, as $F$ and $G$ form a duality, we get a comonad $B = (B, \epsilon, \delta)$ on CABA and a duality between $\mathrm{Coalg}(B)$ and $\mathrm{Alg}(L)$. Observe that $\mathrm{Alg}(L)$ is isomorphic to the category of monoids.

For any set $A$, $LA = A^*$ is the free monoid on $A$ generators, with unit morphism $\eta_A$ and multiplication $\mu_A$. Now we will fix the set $A$ and show how the notion of satisfaction of equations given in [7] for a deterministic automaton on $A$ can be equivalently defined in this setting. In fact, given a deterministic automaton $(X, \alpha: X \times A \to A)$ on $A$ we can use the correspondence:

$$ \alpha: X \times A \to X \\ \alpha: A \to X^X $$

to work with the monoid $X^X = (X^X, \beta) \in \mathrm{Alg}(L)$ with composition of functions as multiplication $\beta$. We have that homomorphic images of $A^*$, i.e., elements in $\mathrm{Eq}(L, A)$, correspond to congruences of the monoid $A^*$. Given any congruence $C$ of $A^*$ we have that $(X, \alpha) \models A^*/C$, if the unique extension $\alpha^\sharp \in \mathrm{Alg}(L)(A^*, X^X)$ of $\alpha$ factors through the canonical morphism $e: A^* \to A^*/C$. That is, we have that $(X, \alpha) \models A^*/C$ if there exists $g_\alpha \in \mathrm{Alg}(L)(A^*/C, X^X)$ such that the following diagram commutes:

<figure><img src="image_15.png" /></figure>
this means that for any $(u, v) \in C$ the transition functions $f_u, f_v \in X^X$, where $f_w(x) = w(x)$, $w \in A^*$, are the same. This is the notion of satisfaction of equations we previously defined in Example 1, and which appears in [7].

We apply $G$ to the previous diagram to get the following diagram:

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

This means that $\mathrm{Im}(2^{\alpha^*}) \subseteq \mathrm{Im}(2^e) = \{L \in 2^{(A^*)} \mid \forall (u,v) \in C, L(u) = L(v)\}$, which is an object in CABA and it is closed under left and right derivatives because $C$ is a congruence.

By Theorem 12, we get a duality between Eq(L, A) and Coeq(B, G(A)) which is the duality between equations and coequations given in [7, Theorem 22]. Additionally, using the previous commutative diagrams, one can prove the equivalence between i) and ii) given in Proposition 16 for the case that $M = A^*$, the congruences $C$ are congruences of $A^*$, and the coequations $\mathrm{Im}(\hat{G}(e_C))$ are subalgebras of $2^M$ that are closed under left and right derivatives, cf. [24, Theorem 17].

## 8 Conclusions

We presented duality results between categories of equations and categories of coequations, Theorem 7. We started our approach by using a more general concept than a duality, namely, contravariant adjunctions. By using this setting we can employ algebraic techniques to study coalgebras as we showed by defining equations for coalgebras and we can also do it the opposite way, define coequations for algebras. Then we showed similar results if we add monads and comonads into our setting, to this end, we proved a lifting theorem to lift contravariant adjunctions to Eilenberg-Moore categories, Theorem 12.

The work here is aimed to understand the interaction between the algebraic and coalgebraic world, including the interpretation of coequations, and the study of comonads. In the future we would like to explore more the coalgebraic aspect, either with the aid of the algebraic side or not, in order to find applications to e.g., tree automata (cf. [17]). Because of limited space we have left out from our examples fundamental dualities such as Stone or Priestley dualities, which will possibly lead to a connection with the recent Eilenberg-type correspondences studied in [10, 3, 4]. We also leave open for future work the question if a converse of Theorem 11 holds.

**Acknowledgements:** We would like to thank Alexander Kurz for his valuable comments, and Jan Rutten for his support and suggestions.
References

1. J. Adámek. A Logic of Coequations. CSL 2005, Springer LNCS 3634.

2. J. Adámek. Birkhoff's covariety theorem without limitation. Commentationes Mathematicae Universitatis Carolinae, vol. 46, no. 2, pp. 197-215.

3. J. Adámek, S. Milius, R. S. R. Myers, and H. Urbat. Generalized Eilenberg Theorem I: Local Varieties of Languages. FoSSaCS 2014: 366-380.

4. J. Adámek, S. Milius, R. S. R. Myers, and Henning Urbat. Varieties of Languages in a Category In Proc. of LICS'15, IEEE.

5. S. Awodey and J. Hughes. Modal operators and the formal dual of Birkhoff's completeness theorem. Math. Struct. in CS, vol. 13, no. 2, pp. 233-258, 2003.

6. S. Awodey. Category theory. Oxford University Press, 2006.

7. A. Ballester-Bolinches, E. Cosme-Llópez, and J.J.M.M. Rutten. The dual equivalence of equations and coequations for automata. Information and Computation, vol. 244, pp. 49-75, 2015.

8. M. Bonsangue and A. Kurz. Duality for logics of transition systems. Proc. FoSSaCS 2005, Springer LNCS 3441, pp. 455-469.

9. R. Clouston and Robert Goldblatt. Covarieties of Coalgebras: Comonads and Coequations. Proc. ICTAC 2005, Springer LNCS 3722, pp. 288-302.

10. M. Gehrke, S. Grigorieff, and J. Pin. Duality and equational theory of regular languages. Proc. ICALP 2008, vol. 5126 of LNCS, pp. 246-257. Springer, 2008.

11. H.P. Gumm. Birkhoff's variety theorem for coalgebras. Contributions to General Algebra, vol. 13, pp. 159-173, 2000.

12. H.P. Gumm and T. Schröder. Covarieties and complete covarieties. ENTCS, vol. 11, pp. 42-55, 1998.

13. C. Hermida and B. Jacobs. Structural induction and coinduction in a fibrational setting. Information and Computation, vol. 145, no. 2, pp. 107-152, 1998.

14. B. Jacobs, A. Silva and A. Sokolova. Trace semantics via determinization. J. Comput. Syst. Sci., vol. 81, no. 5, pp. 859-879, 2015.

15. B. Jacobs and A. Sokolova. Exemplaric expressivity of modal logics. J. Log. and Comput., vol. 20, no. 5, pp. 1041-1068, 2010.

16. B. Klin. Coalgebraic Modal Logic Beyond Sets. ENTCS, 173:177-201, 2007.

17. B. Klin and J. Rot. Coalgebraic trace semantics via forgetful logics. Proc. FoSSaCS 2015. Springer LNCS 9034, pp. 151-166.

18. A. Kurz. Logics for coalgebras and applications to computer science. Doctoral Thesis, Ludwigs-Maximilians-Universität München, 2000.

19. A. Kurz and J. Rosický. Operations and equations for coalgebras. Mathematical Structures in Computer Science 15(1): 149-166, 2005.

20. D. Pavlovic, M. Mislove, and J. Worrell. Testing Semantics: Connecting Processes and Process Logics. AMAST 2006, pp. 308-322 (2006).

21. G. Roșu. Equational axiomatizability for coalgebra. Theoretical Computer Science, vol. 260, no. 1-2, pp. 229-247, (2001).

22. J. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, vol. 249, no. 1, pp. 3-80 (2000).

23. D. Schwencke. Coequational logic for accessible functors. Information and Computation, vol. 208, no. 12, pp. 1469-1489, 2010.

24. J. Salamanca, A. Ballester-Bolinches, M.M. Bonsangue, E. Cosme-Llópez and J.J.M.M. Rutten. Regular varieties of automata and coequations. Proc. MPC 2015. Springer LNCS 9129, pp. 224-237.

25. J. Salamanca, M.M. Bonsangue and J.J.M.M. Rutten. Equations and coequations for weighted automata. Proc. MFCS 2015. Springer LNCS 9234, pp. 444-456.