# Unveiling Eilenberg–type correspondences: Birkhoff’s Theorem for (finite)
algebras + Duality

Julian Salamanca  CWI Amsterdam, The Netherlands<EMAIL_ADDRESS>
###### Abstract.

The purpose of the present paper is to show that:

Eilenberg–type correspondences = Birkhoff’s theorem for (finite) algebras +
duality.

We consider algebras for a monad $\mathsf{T}$ on a category $\mathcal{D}$ and
we study (pseudo)varieties of $\mathsf{T}$–algebras. Pseudovarieties of
algebras are also known in the literature as varieties of finite algebras. Two
well–known theorems that characterize varieties and pseudovarieties of
algebras play an important role here: Birkhoff’s theorem and Birkhoff’s
theorem for finite algebras, the latter also known as Reiterman’s theorem. We
prove, under mild assumptions, a categorical version of Birkhoff’s theorem for
(finite) algebras to establish a one–to–one correspondence between
(pseudo)varieties of $\mathsf{T}$–algebras and (pseudo)equational
$\mathsf{T}$–theories. Now, if $\mathcal{C}$ is a category that is dual to
$\mathcal{D}$ and $\mathsf{B}$ is the comonad on $\mathcal{C}$ that is the
dual of $\mathsf{T}$, we get a one–to–one correspondence between
(pseudo)equational $\mathsf{T}$–theories and their dual, (pseudo)coequational
$\mathsf{B}$–theories. Particular instances of (pseudo)coequational
$\mathsf{B}$-theories have been already studied in language theory under the
name of “varieties of languages” to establish Eilenberg–type correspondences.
All in all, we get a one–to–one correspondence between (pseudo)varieties of
$\mathsf{T}$–algebras and (pseudo)coequational $\mathsf{B}$–theories, which
will be shown to be exactly the nature of Eilenberg–type correspondences.

###### Key words and phrases:

Birkhoff’s theorem, Birkhoff’s theorem for finite algebras, Eilenberg–type
correspondence, duality, (pseudo)variety of algebras, (co)monad,
(pseudo)(co)equational theory.

The research of this author is funded by the Dutch NWO project 612.001.210.

## Introduction

The goal of the present paper is to show that:

Eilenberg–type correspondences = Birkhoff’s theorem for (finite) algebras +
duality.

Eilenberg’s theorem is an important result in algebraic language theory,
stating that there is a one–to–one correspondence between certain classes of
regular languages, called varieties of languages, and certain classes of
monoids, called pseudovarieties of monoids [18, Theorem 34]. The concept of
regular language, which is defined in terms of deterministic automata, has an
equivalent machine–independent algebraic definition, namely, a language
recognized by a finite monoid. Recognizable languages on an alphabet $\Sigma$
are inverse images of monoid homomorphisms with domain $\Sigma^{*}$ and as
codomain any finite monoid. This algebraic approach allows us to study various
kinds of recognizable languages where the notion of homomorphism between
algebras is a key ingredient.

The study of algebras and classes of algebras is a main subject of study in
universal algebra. A well–known theorem in this area is Birkhoff’s variety
theorem [11], which states that a class of algebras of a given type is defined
by a set of equations if and only if it is a variety, i.e., it is closed under
homomorphic images, subalgebras, and products. Later, a Birkhoff’s theorem for
finite algebras was also obtained [8, 30], also known as Reiterman’s theorem.
In Birkhoff’s theorem for finite algebras the kind of equations are of a more
general kind, they can be defined by using topological techniques or can be
equivalently defined by using the so–called implicit operations. In this case,
the classes of algebras considered are pseudovarieties of algebras, also known
as varieties of finite algebras, which are defined as classes of finite
algebras of the same type that are closed under homomorphic images,
subalgebras and finite products.

To state Eilenberg–type theorems, which establish one–to–one correspondences
between (pseudo)varieties of algebras and (pseudo)varieties of languages, one
has to define and find the corresponding notion of a (pseudo)variety of
languages which is, in general, a non–trivial problem. There are
Eilenberg–type correspondences in the literature such as, e.g., [28] for
pseudovarieties of ordered monoids and ordered semigroups, the one in [31] for
pseudovarieties of finite dimensional $\mathbb{K}$–algebras, [29] for
pseudovarieties of idempotent semirings and [7, Theorem 39] for varieties of
monoids.

The work in the present paper has its basis in [14, 34]. We take the main idea
given in [14], where algebras for a monad $\mathsf{T}$ on $\mathcal{D}$ are
considered, to define the natural notion of a (pseudo)variety of
$\mathsf{T}$–algebras. In order to characterize the kind of equations defining
a (pseudo)variety of $\mathsf{T}$–algebras, we use the natural approach of
capturing equations as epimorphisms in $\mathcal{D}$, i.e., congruences, and
add the condition that those equations are closed under substitution. These
properties are captured in categorical terms to define the notion of a
(pseudo)equational $\mathsf{T}$–theory. We obtain that, under mild
assumptions, (pseudo)varieties of $\mathsf{T}$–algebras are exactly classes of
(finite) $\mathsf{T}$–algebras that are defined by (pseudo)equational
$\mathsf{T}$–theories, and that they are in one–to–one correspondence. This
will give us a categorical version of Birkhoff’s theorem for (finite)
$\mathsf{T}$–algebras. Once we get this one–to–one correspondence between
(pseudo)varieties of $\mathsf{T}$–algebras and (pseudo)equational
$\mathsf{T}$–theories, we use a category $\mathcal{C}$ that is dual to
$\mathcal{D}$ and a result given in [34] that allows us to define a canonical
comonad $\mathsf{B}$ on $\mathcal{C}$ that is dual to $\mathsf{T}$ and lift
the duality between $\mathcal{C}$ and $\mathcal{D}$ to their corresponding
Eilenberg–Moore categories. With this duality, there is a canonical
correspondence between (pseudo)equational $\mathsf{T}$–theories and their
corresponding dual, i.e., (pseudo)coequational $\mathsf{B}$–theories. Our most
important examples of (pseudo)coequational $\mathsf{B}$–theories are those
given in Eilenberg–type correspondences, i.e., “varieties of languages”. All
in all, we get a one–to–one correspondence between (pseudo)varieties of
$\mathsf{T}$–algebras and (pseudo)coequational $\mathsf{B}$–theories. We will
show how this concept of (pseudo)coequational $\mathsf{B}$–theories coincides
with the different notions of “varieties of languages” in Eilenberg–type
correspondences, which bring us to our slogan, Eilenberg–type correspondences
= Birkhoff’s theorem for (finite) algebras + duality. As a consequence, we can
summarize Eilenberg–type correspondences in the following picture:

(pseudo)varietiesof $\mathsf{T}$–algebrasEilenberg–type
correspondences$op$$\left(\begin{array}[]{c}\text{(pseudo)equational}\\\
\text{$\mathsf{T}$--theories}\end{array}\right)$

where ‘$op$’ denotes the dual operator. This easy to understand and
straightforward one–to–one correspondence gives us what we called an abstract
Eilenberg–type correspondence for (pseudo)varieties of $\mathsf{T}$–algebras,
Proposition 2 and 4, from which we recover and discover particular instances
of Eilenberg–type correspondences for different kinds of algebraic structures,
i.e., $\mathsf{T}$–algebras. It is worth mentioning that Eilenberg–type
correspondences have not been fully understood for the last forty years, which
can be witnessed by the numerous published results on the subject that deal
with specific kinds of algebras such as [7, 18, perpin, 28, 29, 31, 37] and
categorical generalizations such as [2, 14, 36, 33] in which the direct
relation between “varieties of languages” and equational theories, by using
duality, is not studied or explored to find and justify the defining
properties of a “variety of languages”.

Related work. We briefly summarize here some related work (see the Conclusions
for a more detailed discussion.) There are various generalizations of
Birkhoff’s theorem for (finite) algebras such as [5, 9, 8, 17]. In order to
derive Eilenberg–type correspondences, in this paper we prove a categorical
versions of Birkhoff’s theorem for algebras and finite algebras, which are
stated, under mild assumptions, as one–to–one correspondences between
(pseudo)varieties of algebras and (pseudo)equational theories. The variety
version is derived from [9] and the pseudovariety version is based on the
observation that pseudovarieties of algebras are directed unions of of
equational classes of finite algebras [8, Proposition 4]. It is worth
mentioning that the proof presented here for Birkhoff’s theorem for finite
$\mathsf{T}$–algebras does not involve the use of topology nor profinite
techniques, in contrast to [8, 17, 30].

Related work such as [20, 21, 22, 23] have influenced and motivated the use of
duality in language theory to characterize recognizable languages and to
derive local versions of Eilenberg–type correspondences. In the present paper,
the use of duality is a key aspect that helps us to understand and unveil
Eilenberg–type correspondences.

There are some works in which categorical approaches to derive Eilenberg–type
correspondences are used, notably [2, 14, 36, 33]. The work in [36] subsumes
the work made in [2, 14] and the present paper subsumes the work made in [33,
14]. The kind of algebras considered in [2] are algebras with a monoid
structure which restricts the kind of algebras one can consider, e.g.,
Eilenberg’s theorem [18, Theorem 34s] for pseudovarieties of semigroups cannot
be derived from [2]. A different approach to get a general Eilenberg–type
theorem is the approach given in [14] were the algebras considered are
algebras for a monad $\mathsf{T}$ on $\operatorname{\mathtt{Set}}^{S}$, for a
fixed set $S$. The fact that all the monads considered are on
$\operatorname{\mathtt{Set}}^{S}$ was not general enough to cover cases such
as [28, 29] in which the varieties of languages are not necessarily Boolean
algebras. The approach in [14] of considering algebras for a monad
$\mathsf{T}$ is also considered and generalized in [33, 36] as well as in the
present paper. One of the main challenges in categorical approaches to
Eilenberg–type correspondences is to define the right concept of a “variety of
languages”. The definition of a “variety of languages” given in [36] depends
of finding what they call a “unary representation”, which is a set of unary
operations on a free algebra satisfying certain properties, see [36,
Definition 3.7.]. From this “unary representation” one can construct syntactic
algebras and define the kind derivatives that define a “variety of languages”.
The definition of a “variety of languages” in the present paper is a
categorical one which avoids the explicit definition of derivatives and
existence of syntactic algebras. In the present paper, derivatives are
captured coalgebraically and syntactic algebras are not used to prove the
abstract Eilenberg–type correspondences theorems, but both of those concepts
can be easily obtained via duality in each concrete case. Coalgebraic
approaches, from which one can easily define the concept of a “variety of
languages”, are not used in [14, 36]. Another important related work is [7],
in which an Eilenberg–type correspondence for varieties of monoids is shown,
which is an Eilenberg–type correspondence that can be derived from the present
paper but not from [2, 14, 36]. The work made in [7] motivates the study of
Eilenberg–type correspondences for other classes of algebras different than
pseudovarieties. It is worth mentioning that in [7] the duality between
equations and coequations is studied for the first time in the context of an
Eilenberg–type correspondence.

All in all, the contributions of the present paper can be summarized as
follows:

  1. -

To unveil Eilenberg–type correspondences and show that:

Eilenberg–type correspondences = Birkhoff’s theorem for (finite) algebras +
duality.

  2. -

To show and understand where “varieties of languages” come from, that is:

“varieties of languages” = duals of (pseudo)equational theories.

This fact was conjectured by the author in [33].

  3. -

To provide categorical versions of Birkhoff’s theorem for (finite)
$\mathsf{T}$–algebras as one–to–one correspondences between (pseudo)varieties
of $\mathsf{T}$–algebras and (pseudo)equational $\mathsf{T}$–theories, which
are easily obtained from [8, 9]. A categorical definition of a
(pseudo)equational theory is given.

  4. -

To show a categorical version of Birkhoff’s theorem for finite algebras
without the use of topology nor profinite techniques.

  5. -

To provide a general and abstract Eilenberg–type correspondence theorem that
encompasses existing Eilenberg–type correspondences from the literature. Not
only for (local) pseudovarieties of algebras but also for (local) varieties of
algebras.

  6. -

To derive Eilenberg–type correspondences without the use of syntactic
algebras.

  7. -

To show that the notion of derivatives used to define the different kinds of
“varieties of languages” in Eilenberg–type correspondences is exactly the
coalgebraic structure of an object, which is easily derived via duality, is
most of the cases, from the notion of an algebra homomorphism.

We present the content of our paper as follows: In Section 1, we fix some
notation and some categorical facts we will use through the paper. In Section
2, we state an abstract Eilenberg–type correspondence for varieties of
$\mathsf{T}$–algebras, which is derived from a categorical version of
Birkhoff’s theorem plus duality. As an application, we derive Eilenberg–type
correspondences for some varieties of algebras. In Section 3, we redo Section
2, for the case of pseudovarieties of $\mathsf{T}$–algebras, i.e., we use
Birkhoff’s theorem for finite $\mathsf{T}$–algebras. In Section 4, we do a
similar work for local (pseudo)varieties of $X$–generated
$\mathsf{T}$–algebras whose proof easily follows from what is done in Section
2 and Section 3. Then we finish in Section 5 with the conclusions of this
work.

##  1\. Preliminaries

We introduce the notation and some facts that we will use in the paper. We
assume that the reader is familiar with basic concepts from category theory
and (co)algebra, see, e.g., [4, 32].

Given a category $\mathcal{D}$ and a monad $\mathsf{T}=(T,\eta,\mu)$ on
$\mathcal{D}$, we denote the category of (Eilenberg–Moore)
$\mathsf{T}$-algebras and their homomorphisms by
$\operatorname{Alg}(\mathsf{T})$. Objects in $\operatorname{Alg}(\mathsf{T})$
are pairs $\mathbf{X}=(X,\alpha)$ where $X$ is an object in $\mathcal{D}$ and
$\alpha\in\mathcal{D}(TX,X)$ is a morphism $\alpha:TX\to X$ in $\mathcal{D}$
that satisfies the identities $\alpha\circ\eta_{X}=id_{X}$ and $\alpha\circ
T\alpha=\alpha\circ\mu_{X}$ . A homomorphism from a $\mathsf{T}$-algebra
$\mathbf{X_{1}}=(X_{1},\alpha_{1})$ to a $\mathsf{T}$-algebra
$\mathbf{X_{2}}=(X_{2},\alpha_{2})$ is a morphism
$h\in\mathcal{D}(X_{1},X_{2})$ such that $h\circ\alpha_{1}=\alpha_{2}\circ
Th$.

Dually, given a category $\mathcal{C}$ and a comonad
$\mathsf{B}=(B,\epsilon,\delta)$ on $\mathcal{C}$,
$\operatorname{Coalg}(\mathsf{B})$ denotes the category of (Eilenberg–Moore)
$\mathsf{B}$-coalgebras. Objects in $\operatorname{Coalg}(\mathsf{B})$ are
pairs $\mathbf{Y}=(Y,\beta)$ where $Y$ is an object in $\mathcal{C}$ and
$\beta\in\mathcal{C}(Y,BY)$ satisfies the identities
$\epsilon_{Y}\circ\beta=id_{Y}$ and $B\beta\circ\beta=\delta_{Y}\circ\beta$. A
homomorphism from a $\mathsf{B}$-coalgebra $\mathbf{Y_{1}}=(Y_{1},\beta_{1})$
to a $\mathsf{B}$-coalgebra $\mathbf{Y_{2}}=(Y_{2},\beta_{2})$ is a morphism
$h\in\mathcal{C}(Y_{1},Y_{2})$ such that $\beta_{2}\circ h=Bh\circ\beta_{1}$.

If $\mathcal{D}$ and $\mathcal{C}$ are dual categories and $\mathsf{T}$ is a
monad on $\mathcal{D}$, then there is a canonical comonad $\mathsf{B}$ on
$\mathcal{C}$ such that the duality between $\mathcal{D}$ and $\mathcal{C}$
lifts to their corresponding Eilenberg–Moore categories.

######  Proposition .

[34, Proposition 14] Let $F:\mathcal{C}\to\mathcal{D}$ and
$G:\mathcal{D}\to\mathcal{C}$ be contravariant functors that form a duality
with natural isomorphisms $\eta^{GF}:Id_{\mathcal{C}}\Rightarrow GF$ and
$\eta^{FG}:Id_{\mathcal{D}}\Rightarrow FG$. Let $\mathsf{T}=(T,\eta,\mu)$ be a
monad on $\mathcal{D}$. Then $\mathsf{B}=(B,\epsilon,\delta)$, where $B=GTF$
and $\epsilon,\delta$ are defined as:

$\displaystyle\epsilon$
$\displaystyle=(GLF\xRightarrow{G\eta_{F}}GF\xRightarrow{(\eta^{GF})^{-1}}Id_{\mathcal{C}})$
$\displaystyle\delta$
$\displaystyle=(GLF\xRightarrow{G\mu_{F}}GLLF\xRightarrow{GL(\eta^{FG})^{-1}_{LF}}GLFGLF),$

is a comonad on $\mathcal{C}$. Further, the duality between $F$ and $G$ lifts
to a duality between
$\widehat{F}:\operatorname{Coalg}(\mathsf{B})\to\operatorname{Alg}(\mathsf{T})$
and
$\widehat{G}:\operatorname{Alg}(\mathsf{T})\to\operatorname{Coalg}(\mathsf{B})$.∎

The following is a list of the categories we will use in the examples given in
this paper:

Category |  Objects |  Morphisms
---|---|---
$\operatorname{\mathtt{Set}}$ |  Sets |  Functions
$\operatorname{\mathtt{CABA}}$ |  Complete atomic Boolean algebras |  Complete Boolean algebra homomorphisms
$\operatorname{\mathtt{Poset}}$ |  Partially ordered sets |  Order preserving functions
$\operatorname{\mathtt{AlgCDL}}$ |  Algebraic completely distributive lattices |  Complete lattice homomorphisms
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}$ |  $\mathbb{K}$–vector spaces |  Linear maps
$\operatorname{\mathtt{StVec}_{\mathbb{K}}}$ |  Topological $\mathbb{K}$–vector spaces that are Stone spaces, i.e, they have compact, Hausdorff and zero dimensional topology |  Linear continuous maps
$\operatorname{\mathtt{JSL}}$ |  Join semilattices with zero |  Join semilattice homomorphisms preserving zero
$\operatorname{\mathtt{StJSL}}$ |  Topological join semilattices with zero that are Stone spaces |  Continuous join semilattice homomorphisms preserving zero

We will use the facts that $\operatorname{\mathtt{Set}}$ is dual to
$\operatorname{\mathtt{CABA}}$, $\operatorname{\mathtt{Poset}}$ is dual to
$\operatorname{\mathtt{AlgCDL}}$, $\operatorname{\mathtt{Vec}_{\mathbb{K}}}$
is dual to $\operatorname{\mathtt{StVec}_{\mathbb{K}}}$ for a finite field
$\mathbb{K}$ and that $\operatorname{\mathtt{JSL}}$ is dual to
$\operatorname{\mathtt{StJSL}}$. For a given concrete category $\mathcal{C}$,
we denote the full subcategory of $\mathcal{C}$ consisting of its finite
objects by $\mathcal{C}_{f}$. In the case of $\operatorname{Alg}(\mathsf{T})$
and $\operatorname{Coalg}(\mathsf{B})$, we denote them by
$\operatorname{Alg}_{f}(\mathsf{T})$ and
$\operatorname{Coalg}_{f}(\mathsf{B})$, respectively.

Let $\mathcal{D}$ be a category and let $\mathscr{E}$ and $\mathscr{M}$ be
classes of morphisms in $\mathcal{D}$. $\mathscr{E}/\mathscr{M}$ is called a
factorization system on $\mathcal{D}$ if:

  1. i)

Each of $\mathscr{E}$ and $\mathscr{M}$ is closed under composition with
isomorphisms,

  2. ii)

Every morphism $f$ in $\mathcal{D}$ has a factorization $f=m\circ e$, with
$e\in\mathscr{E}$ and $m\in\mathscr{M}$.

  3. iii)

Given any commutative diagram

$\cdot$$\cdot$$\cdot$$\cdot$$m$$e$$f$$g$

with $e\in\mathscr{E}$ and $m\in\mathscr{M}$, there is a unique diagonal
fill–in, i.e., a unique morphism $d$ such that the following diagram commutes:

$\cdot$$\cdot$$\cdot$$\cdot$$m$$e$$f$$d$$g$

A factorization system $\mathscr{E}/\mathscr{M}$ is proper if every morphism
in $\mathscr{E}$ is epi and every morphism in $\mathscr{M}$ is mono. We will
use the following facts about factorization systems [1].

######  Lemma .

Let $\mathcal{D}$ be a category and $\mathscr{E}/\mathscr{M}$ be a
factorization system on $\mathcal{D}$ such that every morphism in
$\mathscr{M}$ is mono. Then $f\circ g\in\mathscr{E}$ implies
$f\in\mathscr{E}$.∎

######  Lemma .

Let $\mathcal{D}$ be a category, $\mathsf{T}=(T,\eta,\mu)$ a monad on
$\mathcal{D}$ and $\mathscr{E}/\mathscr{M}$ a proper factorization system on
$\mathcal{D}$. If $T$ preserves the morphisms in $\mathscr{E}$ then
$\operatorname{Alg}(\mathsf{T})$ inherits the same $\mathscr{E}/\mathscr{M}$
factorization system.∎

##  2\. Eilenberg–type correspondences for varieties of $\mathsf{T}$–algebras

Varieties of algebras have been studied in universal algebra and equational
logic. In particular, Birkhoff’s variety theorem (see, e.g., [11, 16]) states
that a class of algebras of the same type is a variety, i.e., it is closed
under homomorphic images, subalgebras and (not necessarily finite) products,
if and only if it is definable by equations. As a consequence, for a fixed
type of algebras, we get a one–to–one correspondence between varieties of
algebras and equational theories. Birkhoff’s theorem has been generalized to a
categorical level, see, e.g., [1, 5, 9, 10], to characterize subcategories of
a given category that are, in some sense, equationally defined. In this
section, we provide, under mild assumptions, a Birkhoff’s theorem for
varieties of $\mathsf{T}$–algebras, Theorem 1, which, in order to derive
Eilenberg–type correspondences, will be stated as a one–to–one correspondence
between varieties of $\mathsf{T}$–algebras and equational
$\mathsf{T}$–theories. A categorical definition of an equational
$\mathsf{T}$–theory will be given.

Next we dualize the categorical definition of an equational
$\mathsf{T}$–theory to get that of a coequational $\mathsf{B}$–theory, where
$\mathsf{B}$ is a comonad on a category $\mathcal{C}$. Our main contribution
is to note that particular instances of coequational $\mathsf{B}$–theories
have been already studied in the literature under the name of “varieties of
languages” to establish Eilenberg–type correspondences, e.g., [7, Theorem 39].
Thus, if we assume that $\mathcal{D}$ and $\mathcal{C}$ are dual categories
and that the comonad $\mathsf{B}$ is the dual of the monad $\mathsf{T}$, as in
Proposition 1, then, by duality, we get a one–to–one correspondence between
equational $\mathsf{T}$–theories and coequational $\mathsf{B}$–theories. All
in all, we get a one–to–one correspondence between varieties of
$\mathsf{T}$–algebras and coequational $\mathsf{B}$–theories, which is the
abstract Eilenberg–type correspondence for varieties of $\mathsf{T}$–algebras,
Proposition 2. The main facts in this section can be summarized in the
following picture:

Varieties of$\mathsf{T}$–algebrasBirkhoff’s thm.Theorem
1Equational$\mathsf{T}$–theoriesDualityCoequational$\mathsf{B}$–theoriesEilenberg–type
correspondenceProposition 2

where each arrow symbolizes a one–to–one correspondence and $\mathsf{B}$ is
the comonad that is the dual of the monad $\mathsf{T}$.

###  2.1. Birkhoff’s Theorem for $\mathsf{T}$–algebras

The concept of a variety of algebras and an equationally defined class can be
formulated in categorical terms to prove a categorical version of Birkhoff’s
theorem [1, 5, 9, 10]. We prove in this subsection that, under mild
assumptions, there is a one–to–one correspondence between varieties of
$\mathsf{T}$–algebras and equational $\mathsf{T}$–theories, Theorem 1, where
$\mathsf{T}$ is a monad on a category $\mathcal{D}$. The definition of variety
of $\mathsf{T}$–algebras, which depends on the concept of homomorphic images
and subalgebras, will be defined by using a factorization system
$\mathscr{E}/\mathscr{M}$ on $\mathcal{D}$. In order to define the concept of
equational $\mathsf{T}$–theories, we base our approach on [16, Definition
II.14.16]. After providing the assumptions and basic definitions needed to
state Theorem 1, its proof will easily follow from the assumptions needed by
using the work by Banaschewski and Herrlich [9].

We fix a complete category $\mathcal{D}$, a monad $\mathsf{T}=(T,\eta,\mu)$ on
$\mathcal{D}$, a factorization system $\mathscr{E}/\mathscr{M}$ on
$\mathcal{D}$ and a full subcategory $\mathcal{D}_{0}$ of $\mathcal{D}$. We
will use the following assumptions:

  1. (B1)

The factorization system $\mathscr{E}/\mathscr{M}$ is proper. That is, every
map in $\mathscr{E}$ is an epimorphism and every map in $\mathscr{M}$ is a
monomorphism.

  2. (B2)

For every $X\in\mathcal{D}_{0}$, the free $\mathsf{T}$–algebra
$\mathbf{TX}=(TX,\mu_{X})$ is projective with respect to $\mathscr{E}$ in
$\operatorname{Alg}(\mathsf{T})$. That is, for every
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{B})$ with
$X\in\mathcal{D}_{0}$ and
$e\in\operatorname{Alg}(\mathsf{T})(\mathbf{A},\mathbf{B})\cap\mathscr{E}$
there exists $g\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ such
that the following diagram commutes:

$B$$A$$TX$$e$$h$$g$

  3. (B3)

For every $\mathbf{A}\in\operatorname{Alg}(\mathsf{T})$ there exists
$X_{A}\in\mathcal{D}_{0}$ and
$s_{A}\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX_{A}},\mathbf{A})\cap\mathscr{E}$.

  4. (B4)

$T$ preserves morphisms in $\mathscr{E}$.

  5. (B5)

For every $X\in\mathcal{D}_{0}$, there is, up to isomorphism, only a set of
$\mathsf{T}$–algebra morphisms in $\mathscr{E}$ with domain $\mathbf{TX}$.

The notion of a variety of $\mathsf{T}$–algebras, which depends on the concept
of homomorphic images and subalgebras, will be defined by using the
factorization system $\mathscr{E}/\mathscr{M}$ on $\mathcal{D}$, which is
lifted to $\operatorname{Alg}(\mathsf{T})$ using (B1) and (B4), Lemma 1. The
role of $\mathcal{D}_{0}$ is that the objects from which “variables” for the
equations are considered are objects in $\mathcal{D}_{0}$. Assumption (B2) of
$\mathbf{TX}$ being projective with respect to $\mathscr{E}$,
$X\in\mathcal{D}_{0}$, will play a fundamental role in relating varieties of
algebras with equational theories. Assumption (B3) guarantees that every
algebra in $\operatorname{Alg}(\mathsf{T})$ is the homomorphic image of a free
$\mathsf{T}$–algebra with object of generators from $\mathcal{D}_{0}$.
Condition (B5) will allow us to define the equational theory for a given
variety of algebras.

For Birkhoff’s classical variety theorem [11], we can take
$\mathcal{D}=\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$, $\mathscr{E}=$
surjections, $\mathscr{M}=$ injections, and $\mathsf{T}$ to be the term monad
for a given type of algebras $\operatorname{\tau}$, i.e.,
$TX=T_{\operatorname{\tau}}(X)$, the set of terms of type
$\operatorname{\tau}$ on the set of variables $X$ (see Example 2.1 and Example
2.1). Another important example will be given by
$\mathcal{D}=\operatorname{\mathtt{Poset}}$, with $\mathcal{D}_{0}=$ discrete
posets (i.e., we do not want the “variables” to be ordered) to obtain a
Birkhoff theorem for ordered algebras [12].

We now give the necessary definitions to formulate our Birkhoff theorem for
$\mathsf{T}$–algebras. We start by defining varieties of
$\mathsf{T}$–algebras.

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$ and $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$. Let $K$ be a class of algebras in
$\operatorname{Alg}(\mathsf{T})$. We say that $K$ is closed under
$\mathscr{E}$–quotients if $\mathbf{B}\in\operatorname{Alg}(\mathsf{T})$ for
every
$e\in\operatorname{Alg}(\mathsf{T})(\mathbf{A},\mathbf{B})\cap\mathscr{E}$
with $\mathbf{A}\in K$. We say that $K$ is closed under
$\mathscr{M}$–subalgebras if $\mathbf{B}\in\operatorname{Alg}(\mathsf{T})$ for
every
$m\in\operatorname{Alg}(\mathsf{T})(\mathbf{B},\mathbf{A})\cap\mathscr{M}$
with $\mathbf{A}\in K$. We say that $K$ is closed under products if
$\prod_{i\in I}\mathbf{A}_{i}\in K$ for every set $I$ such that
$\mathbf{A}_{i}\in K$, $i\in I$. A class $V$ of algebras in
$\operatorname{Alg}(\mathsf{T})$ is called a variety of $\mathsf{T}$–algebras
if it is closed under $\mathscr{E}$–quotients, $\mathscr{M}$–subalgebras and
products.

Now, we define the other main concept to state our Bikhoff’s theorem for
$\mathsf{T}$–algebras, namely, the concept of an equational
$\mathsf{T}$–theory.

Let $\mathcal{D}$ be a category, $\mathsf{T}$ a monad on $\mathcal{D}$,
$\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}$ and
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$. An
equational $\mathsf{T}$–theory on $\mathcal{D}_{0}$ is a family of
$\mathsf{T}$–algebra morphisms
$\operatorname{\mathtt{E}}=\\{TX\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}\\}_{X\in\mathcal{D}_{0}}$
in $\mathscr{E}$ such that for any $X,Y\in\mathcal{D}_{0}$ and any
$g\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{TY})$ there exists
$g^{\prime}\in\operatorname{Alg}(\mathsf{T})(\mathbf{Q_{X}},\mathbf{Q_{Y}})$
such that the following diagram commutes:

$TY$$Q_{Y}$$TX$$Q_{X}$$e_{Y}$$e_{X}$$\forall g$$g^{\prime}$

Intuitively, in the setting of Birkhoff’s classical variety theorem, for every
object $X\in\mathcal{D}_{0}$ (i.e., a set of variables) the morphism $e_{X}$,
which we asssume to be a surjection, represents the set of equations
$\ker(e_{X})$, which is a congruence on $\mathbf{TX}$, i.e., it is an
equivalence relation on $TX$ which is closed under the componentwise algebric
operations. Commutativity of the diagram above means that the family of all
equations $\\{\ker(e_{X})\\}_{X\in\mathcal{D}_{0}}$ is closed under any
substitution $g\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{TY})$.
The previous definition generalizes the definition of an equational theory to
a categorical level, cf. [16, Definition II.14.16].

######  Example .

Consider the case $\mathcal{D}=\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$,
$\mathscr{E}=$ surjections and $\mathscr{M}=$ injections. For a given type of
algebras $\operatorname{\tau}$, consider the monad
$\mathsf{T}_{\operatorname{\tau}}=(T_{\operatorname{\tau}},\eta,\mu)$ such
that $T_{\operatorname{\tau}}(X)$ is the set of terms for
$\operatorname{\tau}$ on variables $X$, see [16, Definition II.10.1]. The unit
$\eta_{X}:X\to T_{\operatorname{\tau}}(X)$ is the inclusion function and
multiplication $\mu_{X}:T_{\operatorname{\tau}}(T_{\operatorname{\tau}}(X))\to
T_{\operatorname{\tau}}(X)$ is the identity map. Now,
$\operatorname{Alg}(\mathsf{T}_{\operatorname{\tau}})$ is the category of
algebras $\mathbf{A}=(A,\alpha)$ of type $\operatorname{\tau}$, where
$\alpha:T_{\operatorname{\tau}}(A)\to A$ is the evaluation $\alpha(t)$ in $A$
of each term $t\in T_{\operatorname{\tau}}(A)$. An equational
$\mathsf{T}_{\operatorname{\tau}}$–theory on
$\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$ is a family of surjective
homomorphisms
$\operatorname{\mathtt{E}}=\\{T_{\operatorname{\tau}}(X)\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}\\}_{X\in\operatorname{\mathtt{Set}}}$
in $\operatorname{Alg}(\mathsf{T}_{\operatorname{\tau}})$ such that every
$\ker(e_{x})$ is a congruence on $T_{\operatorname{\tau}}(X)$ and the family
$\\{\ker(e_{X})\\}_{X\in\mathcal{D}_{0}}$ is closed under substitution, i.e.,
for $\left(p(x_{1},\ldots,x_{n}),q(x_{1},\ldots,x_{n})\right)\in\ker(e_{X})$
and $r_{x}\in T_{\operatorname{\tau}}(Y)$, $x\in X$, we have that
$(p(r_{x_{1}},\ldots,r_{x_{n}}),q(r_{x_{1}},\ldots,r_{x_{n}}))\in\ker(e_{Y})$,
where $t(r_{x_{1}},\ldots,r_{x_{n}})$ is the term in
$T_{\operatorname{\tau}}(Y)$ obtained from $t(x_{1},\ldots,x_{n})\in
T_{\operatorname{\tau}}(X)$ by replacing each variable $x_{i}$ by $r_{x_{i}}$,
$i=1,\ldots,n$.∎

######  Example .

Consider the case $\mathcal{D}=\operatorname{\mathtt{Poset}}$,
$\mathcal{D}_{0}=$ the full subcategory of discrete posets, $\mathscr{E}=$
surjections and $\mathscr{M}=$ embeddings. Let $\operatorname{\tau}$ be a type
of algebras. An ordered algebra of type $\operatorname{\tau}$ is a triple
$A=(A,\leq_{A},\\{f_{A}:A^{n_{f}}\to A\\}_{f\in\operatorname{\tau}})$ such
that $(A,\leq_{A})\in\operatorname{\mathtt{Poset}}$ and all the functions
$f_{A}:A^{n_{f}}\to A$ are order preserving, where the order in $A^{n_{f}}$ is
componentwise, $f\in\operatorname{\tau}$. We can define the monad
$\mathsf{T}_{\operatorname{\tau}}=(T_{\operatorname{\tau}},\eta,\mu)$ where
$T_{\operatorname{\tau}}(X,\leq_{X})$ is the poset
$(T_{\operatorname{\tau}}(X),\leq_{\mathsf{T}_{\operatorname{\tau}}(X)})$
defined as: $x\leq_{\mathsf{T}_{\operatorname{\tau}}(X)}y$ for every $x,y\in
X$ such that $x\leq_{X}y$, and
$f(t_{1},\ldots,t_{n_{f}})\leq_{\mathsf{T}_{\operatorname{\tau}}(X)}f(q_{1},\ldots,q_{n_{f}})$
for every $f\in\operatorname{\tau}$ and terms $t_{i},q_{i}\in
T_{\operatorname{\tau}}(X)$ such that
$t_{i}\leq_{\mathsf{T}_{\operatorname{\tau}}(X)}q_{i}$, $i=1,\ldots,n_{f}$.
Algebras in $\operatorname{Alg}(\mathsf{T}_{\operatorname{\tau}})$ are ordered
algebras of type $\operatorname{\tau}$.

An equational $\mathsf{T}_{\operatorname{\tau}}$–theory is a family
$\operatorname{\mathtt{E}}=\\{T_{\operatorname{\tau}}(X)\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}\\}_{X\in\mathcal{D}_{0}}$
of surjective homomorphisms, which are trivially order preserving since
$T_{\operatorname{\tau}}(X)$ is discrete for any $X\in\mathcal{D}_{0}$, such
that $\overrightarrow{\ker}(e_{X})$ is an admissible preorder on
$T_{\operatorname{\tau}}(X)$ 111A preorder $\sqsubseteq$ on an ordered algebra
$(A,\leq_{A},\\{f_{A}:A^{n_{f}}\to A\\}_{f\in\operatorname{\tau}})$ of type
$\operatorname{\tau}$ is compatible if for every $f\in\operatorname{\tau}$ and
$a_{i},b_{i}\in A$ with $a_{i}\sqsubseteq b_{i}$, $i=1,\ldots,n_{f}$, we have
that $f_{A}(a_{1},\ldots,a_{n_{f}})\sqsubseteq f_{A}(b_{1},\ldots,b_{n_{f}})$.
A preorder $\sqsubseteq$ is admissible if it is compatible and $a\sqsubseteq
b$ whenever $a\leq_{A}b$. The congruence $\theta_{\sqsubseteq}$ on $A$ induced
by the compatible preorder $\sqsubseteq$ is the relation
$\theta_{\sqsubseteq}$ on $A$ defined as
$\theta_{\sqsubseteq}:=\sqsubseteq\cap\sqsubseteq^{-1}$. Then
$(A/\theta_{\sqsubseteq},\leq_{\sqsubseteq})$ is an ordered algebra with the
order given by $[x]\leq_{\sqsubseteq}[y]$ iff $x\sqsubseteq y$. See [12].,
where $\overrightarrow{\ker}(e_{X}):=\\{(u,v)\mid e_{X}(u)\leq e_{X}(v)\\}$,
and the family $\\{\overrightarrow{\ker}(e_{x})\\}_{X\in\mathcal{D}_{0}}$ is
closed under substitution as in the previous example. In this case,
$\overrightarrow{\ker}(e_{X})$ represents the equations and inequations of
terms with variables in $X$ in the equational
$\mathsf{T}_{\operatorname{\tau}}$–theory. Note that if we take
$\mathcal{D}_{0}=\operatorname{\mathtt{Poset}}$ then condition (B2) does not
hold.∎

Given an equational $\mathsf{T}$–theory
$\operatorname{\mathtt{E}}=\\{TX\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}\\}_{X\in\mathcal{D}_{0}}$
and an algebra $\mathbf{A}\in\operatorname{Alg}(\mathsf{T})$, we say that
$\mathbf{A}$ satisfies $\operatorname{\mathtt{E}}$, denoted as
$\mathbf{A}\models\operatorname{\mathtt{E}}$, if $\mathbf{A}$ is
$\operatorname{\mathtt{E}}$–injective, that is, if for every
$X\in\mathcal{D}_{0}$ and every
$f\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ there exists a
$\mathsf{T}$–algebra morphism $g_{f}$ such that $f=g_{f}\circ e_{X}$.

Intuitively, $\mathbf{A}\models\operatorname{\mathtt{E}}$ if for every
assignment $f\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ of the
variables $X$ to elements of the algebra $\mathbf{A}$, all the equations
represented by $e_{X}\colon
TX\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}Q_{X}$ hold in
$\mathbf{A}$. Given an equational $\mathsf{T}$–theory
$\operatorname{\mathtt{E}}$ we denote the models of
$\operatorname{\mathtt{E}}$ by
$\operatorname{Mod}(\operatorname{\mathtt{E}})$, that is:

$\operatorname{Mod}(\operatorname{\mathtt{E}}):=\\{\mathbf{A}\in\operatorname{Alg}(\mathsf{T})\mid\mathbf{A}\models\operatorname{\mathtt{E}}\\}$

A class $K$ of $\mathsf{T}$–algebras is defined by $\operatorname{\mathtt{E}}$
if $K=\operatorname{Mod}(\operatorname{\mathtt{E}})$.

######  Theorem 1 (Birkhoff’s Theorem for $\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}$ and
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$. Assume (B1)
to (B5). Then a class $K$ of $\mathsf{T}$–algebras is a variety of
$\mathsf{T}$–algebras if and only if it is defined by an equational
$\mathsf{T}$–theory on $\mathcal{D}_{0}$. Additionally, varieties of
$\mathsf{T}$–algebras are in one–to–one correspondence with equational
$\mathsf{T}$–theories on $\mathcal{D}_{0}$. ∎

From the previous theorem we have the following.

######  Example 2.1.

By considering the monad and the categories given in Example 2.1 we obtain the
classical Birkhoff variety theorem [11].∎

######  Example 2.2.

By considering the monad and the categories given in Example 2.1 we obtain the
Birkhoff variety theorem for ordered algebras [12].∎

######  Example 2.3 (cf. [7, Theorem 39]).

Consider the case $\mathcal{D}=\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$,
$\mathsf{T}$ the monad given by $TX=X^{*}$, where $X^{*}$ is the free monoid
on $X$, $\mathscr{E}=$ surjections and $\mathscr{M}=$ injections. We have that
conditions (B1) to (B5) are fullfilled. Therefore we have a one–to–one
correspondence between varieties of monoids and equational
$\mathsf{T}$–theories. Now, consider the category
$\mathcal{C}=\mathcal{C}_{0}=\operatorname{\mathtt{CABA}}$ which is dual to
$\operatorname{\mathtt{Set}}$ and let $\mathsf{B}$ be the comonad on
$\operatorname{\mathtt{CABA}}$ that is dual to the monad $\mathsf{T}$ on
$\operatorname{\mathtt{Set}}$, i.e, $B$ is defined, up to isomorphism, as
$B(2^{X})=2^{X^{*}}$. Then, by duality, we have a one–to–one correspondence
between equational $\mathsf{T}$–theories $\operatorname{\mathtt{E}}$ and its
dual $\operatorname{\mathtt{E}}^{\partial}$, i.e., families of monomorphisms
$\\{S_{X}\xhookrightarrow{m_{X}}BX\\}_{X\in\mathcal{C}_{0}=\mathcal{C}}$ in
$\operatorname{Coalg}(\mathsf{B})$ such that for any $X,Y\in\mathcal{C}_{0}$
and any $g\in\operatorname{Coalg}(\mathsf{B})(\mathbf{BX},\mathbf{BY})$ there
exists
$g^{\prime}\in\operatorname{Coalg}(\mathsf{B})(\mathbf{S_{X}},\mathbf{S_{Y}})$
such that $m_{Y}\circ g=g^{\prime}\circ m_{X}$.

This notion of the dual of an equational $\mathsf{T}$–theory is equivalent
with the –more complicated– notion of a variety of languages in [7, Definition
35] (see Example 2.4 for more details). In this setting, we get a one–to–one
correspondence between varieties of monoids and duals of equational
$\mathsf{T}$–theories, i.e., varieties of languages. This is exactly the
Eilenberg–type theorem [7, Theorem 39].∎

###  2.2. Abstract Eilenberg–type correspondence for varieties of
$\mathsf{T}$–algebras

As we saw in Example 2.3, by Using Theorem 1 and duality, we can derive
Eilenberg–type correspondences for varieties of $\mathsf{T}$–algebras. In this
subsection we state the abstract Eilenberg–type correspondence for varieties
of $\mathsf{T}$–algebras, i.e., a one–to–one correspondence between varieties
of $\mathsf{T}$–algebras and duals of equational $\mathsf{T}$–theories, and
then instantiate this result to some particular cases. We dualize the
definition of an equational $\mathsf{T}$–theory as follows.

Let $\mathcal{C}$ be a category, $\mathsf{B}=(B,\epsilon,\delta)$ a comonad on
$\mathcal{C}$, $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{C}$ and $\mathcal{C}_{0}$ a full subcategory of $\mathcal{C}$. A
coequational $\mathsf{B}$–theory on $\mathcal{C}_{0}$ is a family of
$\mathsf{B}$–coalgebra morphisms
$\operatorname{\mathtt{M}}=\\{S_{Y}\xhookrightarrow{m_{Y}}BY\\}_{Y\in\mathcal{C}_{0}}$
in $\mathscr{M}$ such that for any $X,Y\in\mathcal{C}_{0}$ and any
$g\in\operatorname{Coalg}(\mathsf{B})(\mathbf{BX},\mathbf{BY})$ there exists
$g^{\prime}\in\operatorname{Coalg}(\mathsf{B})(\mathbf{S_{X}},\mathbf{S_{Y}})$
such that the following diagram commutes:

$S_{Y}$$BY$$S_{X}$$BX$$m_{Y}$$m_{X}$$g^{\prime}$$\forall g$

Intuitively, every $\mathbf{S_{Y}}$ is a $\mathsf{B}$–subcoalgebra of the
cofree coalgebra $\mathbf{BY}=(BY,\delta_{Y})$, and the family
$\\{S_{Y}\\}_{Y\in\mathcal{C}_{0}}$ is closed under any coalgebra morphism,
i.e., for every morphism
$g\in\operatorname{Coalg}(\mathsf{B})(\mathbf{BX},\mathbf{BY})$, $x\in S_{X}$
implies $g(x)\in S_{Y}$. As an example of coequational $\mathsf{B}$–theories
we have the “varieties of languages” defined in [7, Definition 35] which we
describe in a simpler way in Example 2.4. Now, with the previous definition,
Theorem 1 and duality, we have the following.

######  Proposition 2 (Abstract Eilenberg–type correspondence for varieties of
$\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$ and $\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}$.
Assume (B1) to (B5). Let $\mathcal{C}$ be a category that is dual to
$\mathcal{D}$, $\mathcal{C}_{0}$ the corresponding dual category of
$\mathcal{D}_{0}$ and let $\mathsf{B}$ be the comonad on $\mathcal{C}$ that is
dual to $\mathsf{T}$ which is defined as in Proposition 1. Then there is a
one–to–one correspondence between varieties of $\mathsf{T}$–algebras and
coequational $\mathsf{B}$–theories on $\mathcal{C}_{0}$.

In the rest of this section we show some particular instances of
Eilenberg–type correspondences derived from the the previous proposition. We
start with the continuation of Example 2.3 by describing the defining
properties of the coequational $\mathsf{B}$–theories that correspond to
varieties of monoids. Then we do a similar work to derive Eilenberg–type
correspondences for other kind of varieties such as semigroups, groups, monoid
actions, ordered monoids, vector spaces and idempotent semirings. It is worth
mentioning that these kind of results, except for the one in Example 2.4 which
was shown in [7, Theorem 39], seem to be new and cannot be derived with
categorical approaches given in [2, 14, 36].

######  Example 2.4 (Example 2.3 continued).

From the setting of Example 2.3 we get a one–to–one correspondence between
varieties of monoids and coequational $\mathsf{B}$–theories on
$\operatorname{\mathtt{CABA}}$. The latter can be characterized as operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete atomic Boolean algebra
$\operatorname{\mathtt{Set}}(X^{*},2)$ of subsets of $X^{*}$, i.e., every
element in $\operatorname{\mathscr{L}}(X)$ is a language on $X$.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{*}$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of monoids $h:Y^{*}\to
X^{*}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

The previous notion of a coequational $\mathsf{B}$–theory on
$\operatorname{\mathtt{CABA}}$ is equivalent with the –more complicated–
notion of a variety of languages in [7, Definition 35]. This one–to–one
correspondence is exactly the Eilenberg–type theorem [7, Theorem 39] (see
Example 2.5 and Appendix for more details).∎

The following example describes explicitely Eilenberg–type correspondences for
varieties of algebras of any given type $\operatorname{\tau}$ where each
function symbol in $\operatorname{\tau}$ has finite arity.

######  Example 2.5.

Let $\operatorname{\tau}$ be a type of algebras where each function symbol
$g\in\operatorname{\tau}$ has arity $n_{g}\in\mathbb{N}$ and let $K$ be a
variety of algebras of type $\operatorname{\tau}$. Consider the case
$\mathcal{D}=\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$, $\mathscr{E}=$
surjections, $\mathscr{M}=$ injections and let $\mathsf{T}_{K}$ be the monad
such that for every $X\in\operatorname{\mathtt{Set}}$, $T_{K}X$ is the
underlying set of the free algebra in $K$ on $X$ generators (see [16,
Definition II.10.9] and [27, VI.8]). We have that
$\operatorname{\mathtt{CABA}}$ is dual to $\operatorname{\mathtt{Set}}$, so we
can consider $\mathcal{C}=\mathcal{C}_{0}=\operatorname{\mathtt{CABA}}$. By
using the duality between $\operatorname{\mathtt{CABA}}$ and
$\operatorname{\mathtt{Set}}$, each coequational $\mathsf{B}$–theory can be
indexed by $\mathcal{D}_{0}=\operatorname{\mathtt{Set}}$ and can be presented,
up to isomorphism, as a family
$\\{S_{X}\xhookrightarrow{m_{X}}2^{T_{K}X}\\}_{X\in\operatorname{\mathtt{Set}}}$.
From this, we present coequational $\mathsf{B}$–theories as operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ given by
$\operatorname{\mathscr{L}}(X):=\operatorname{Im}(m_{X})$. Then, we get a
one–to–one correspondence between varieties of algebras in $K$ and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete atomic Boolean algebra
$\operatorname{\mathtt{Set}}(T_{K}X,2)$ of subsets of $T_{K}X$.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under derivatives with respect to
the type $\operatorname{\tau}$. That is, for every $g\in\operatorname{\tau}$
of arity $n_{g}$, every $1\leq i\leq n_{g}$, every $t_{j}\in T_{K}X$, $1\leq
j<n_{g}$, and every $L\in\operatorname{\mathscr{L}}(X)$ we have that
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathscr{L}}(X)$ where
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathtt{Set}}(T_{K}X,2)$
is defined as

$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(t)=L(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1}))$

$t\in T_{K}X$. That is, for every function symbol $g\in\operatorname{\tau}$ we
get $n_{g}$ kinds of derivatives.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of
$\mathsf{T}_{K}$–algebras $h:T_{K}Y\to T_{K}X$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

In fact, we have the following:

  1. a)

Condition i) above follows from the fact that
$\operatorname{\mathscr{L}}(X)=\operatorname{Im}(m_{X})\cong
S_{X}\in\operatorname{\mathtt{CABA}}$ and
$\operatorname{Im}(m_{X})\subseteq\operatorname{\mathtt{Set}}(T_{K}X,2)$.

  2. b)

Condition ii) above follows from lifting the duality between
$\operatorname{\mathtt{Set}}$ and $\operatorname{\mathtt{CABA}}$ to a duality
between $\operatorname{Alg}(\mathsf{T_{K}})$ and
$\operatorname{Coalg}(\mathsf{B})$. In fact, every surjective
$\mathsf{T}_{K}$–algebra morphism
$e_{X}:T_{K}X\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}Q_{X}$
defines the injective morphism $\operatorname{\mathtt{Set}}(e_{X},2)$ in
$\operatorname{Coalg}(\mathsf{B})$ which is defined as
$\operatorname{\mathtt{Set}}(e_{X},2)(f)=f\circ e_{X}$,
$f\in\operatorname{\mathtt{Set}}(Q_{X},2)$, and from this we have:

$\operatorname{\mathscr{L}}(X)=\operatorname{Im}(\operatorname{\mathtt{Set}}(e_{X},2))=\\{f\circ
e_{X}\mid f\in\operatorname{\mathtt{Set}}(Q_{X},2)\\}.$

Closure of $\operatorname{\mathscr{L}}(X)$ under under derivatives with
respect to the type $\operatorname{\tau}$ follows from the fact that $e_{X}$
is a $\mathsf{T}_{K}$–algebra morphism. In fact, for every
$f\in\operatorname{\mathtt{Set}}(Q_{X},2)$ we have:

$\displaystyle(f\circ e_{X})^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(t)$
$\displaystyle=(f\circ
e_{X})(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1}))$
$\displaystyle=f(e_{X}(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1})))$
$\displaystyle=f(g(e_{X}(t_{1}),\ldots,e_{X}(t_{i-1}),e_{X}(t),e_{X}(t_{i}),\ldots,e_{X}(t_{n_{g}-1}))))$
$\displaystyle=\left(f^{(i)}_{(g,e_{X}(t_{1}),\ldots,e_{X}(t_{n_{g}-1}))}\circ
e_{X}\right)(t)$

where the function
$f^{(i)}_{(g,e_{X}(t_{1}),\ldots,e_{X}(t_{n_{g}-1}))}\in\operatorname{\mathtt{Set}}(Q_{X},2)$
is defined for every $q\in Q_{X}$ as
$f^{(i)}_{(g,e_{X}(t_{1}),\ldots,e_{X}(t_{n_{g}-1}))}(q)=f(g(e_{X}(t_{1}),\ldots,e_{X}(t_{i-1}),q,e_{X}(t_{i}),\ldots,e_{X}(t_{n_{g}-1})))$.
Therefore, $(f\circ
e_{X})^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}=f^{(i)}_{(g,e_{X}(t_{1}),\ldots,e_{X}(t_{n_{g}-1}))}\circ
e_{X}\in\operatorname{\mathscr{L}}(X)$, i.e., $\operatorname{\mathscr{L}}(X)$
is closed under derivatives with respect to the type $\operatorname{\tau}$.

Conversely, any $S\in\operatorname{\mathtt{CABA}}$ closed under derivatives
with respect to the type $\operatorname{\tau}$ such that $S$ is a subalgebra
of $\operatorname{\mathtt{Set}}(T_{K}X,2)\in\operatorname{\mathtt{CABA}}$ will
define, by duality, the canonical surjective function $e_{S}:T_{K}X\to
T_{K}X/\theta_{S}$ where $\theta_{S}\subseteq T_{K}X\times T_{K}X$ is defined
as:

$\theta_{S}:=\\{(v,w)\in T_{K}X\times T_{K}X\mid\exists
A\in\operatorname{At}(S)\text{ s.t. }A(w)=A(v)=1\\}$

where $\operatorname{At}(S)$ is the set of atoms of $S$. Clearly, $\theta_{S}$
is an equivalence relation on $T_{K}X$ since $\operatorname{At}(S)$ is a
partition of $T_{K}X$. We only need to show that $\theta_{S}$ is an
$\operatorname{\tau}$–congruence on $\mathbf{T_{K}X}$ 222A
$\operatorname{\tau}$–congruence on an algebra $\mathbf{A}$ of type
$\operatorname{\tau}$ is an equivalence relation $\theta\subseteq A\times A$
on $A$ such that for every $g\in\operatorname{\tau}$ of arity $n_{g}$, every
$1\leq i\leq n_{g}$ and $a_{j}\in A$, $1\leq j<n_{g}$, the property
$(u,v)\in\theta$ implies $(g(a_{1},\ldots a_{i-1},u,a_{i},\ldots
a_{n_{g}-1}),g(a_{1},\ldots a_{i-1},v,a_{i},\ldots a_{n_{g}-1}))\in\theta$.
(cf. [16, Definition II.5.1]). In fact, let $g\in\operatorname{\tau}$ of arity
$n_{g}$, let $1\leq i\leq n_{g}$, let $t_{j}\in T_{K}X$, $1\leq j<n_{g}$, and
assume $(u,v)\in\theta$, i.e., there exists $A\in\operatorname{At}(S)$ such
that $A(u)=A(v)=1$, we have to show that $(g(t_{1},\ldots
t_{i-1},u,t_{i},\ldots t_{n_{g}-1}),g(t_{1},\ldots t_{i-1},v,t_{i},\ldots
t_{n_{g}-1}))\in\theta$. If $(g(t_{1},\ldots t_{i-1},u,t_{i},\ldots
t_{n_{g}-1}),g(t_{1},\ldots t_{i-1},v,t_{i},\ldots t_{n_{g}-1}))\notin\theta$
then there exists $B\in\operatorname{At}(S)$ such that $B(g(t_{1},\ldots
t_{i-1},u,t_{i},\ldots t_{n_{g}-1}))\neq B(g(t_{1},\ldots
t_{i-1},v,t_{i},\ldots t_{n_{g}-1}))$ which means that
$B^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(u)\neq
B^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(v)$ with
$B^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in S$ by closure under derivatives
with respect to the type $\operatorname{\tau}$. Therefore $A\cap
B^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}$ is an element in $S$ such that
$0<A\cap B^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}<A$ which contradicts the fact
that $A$ is an atom. This proves that $(g(t_{1},\ldots t_{i-1},u,t_{i},\ldots
t_{n_{g}-1}),g(t_{1},\ldots t_{i-1},v,t_{i},\ldots t_{n_{g}-1}))\in\theta$,
which means that $e_{S}$ is a surjective $\mathsf{T}$–algebra morphism.

  3. c)

Condition iii) above is the commutativity of the diagram in Definition 2.2.

Conversely, each operator $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}$ with the properties i), ii) and iii) above
defines the coequational $\mathsf{B}$–theory
$\\{\operatorname{\mathscr{L}}(X)\xhookrightarrow{i_{X}}2^{T_{K}X}\\}_{X\in\operatorname{\mathtt{Set}}}$
where $i_{X}$ is the inclusion $\mathsf{B}$–coalgebra morphism. Note that
conditions i) and ii) above are exactly the properties that
$\operatorname{\mathscr{L}}(X)$ is a $\mathsf{B}$–subcoalgebra of
$\operatorname{\mathtt{Set}}(T_{K}X,2)$.∎

######  Example 2.6.

From the previous general example we can provide details for the properties
i), ii) and iii) in Example 2.4. In fact, for the case of monoids we have the
type $\operatorname{\tau}=\\{e,\cdot\\}$ where $e$ is a nullary function
symbol and $\cdot$ is a binary function symbol. We write $x\cdot y$ for
$\cdot(x,y)$. By considering the variety $K$ of monoids, we get the monad
$\mathsf{T}_{K}$ such that $T_{K}X=X^{*}$, where $X^{*}$ is the free monoid on
$X$. Then, we have:

  1. 1)

Properties i) and iii) in Example 2.5 trivially become properties i) and iii)
in Example 2.4.

  2. 2)

Property ii) in Example 2.5 does not give us any kind of derivatives for the
nullary function symbol $e\in\operatorname{\tau}$, but will give us the
derivatives $L^{(1)}_{(\cdot,u)}$ and $L^{(2)}_{(\cdot,u)}$ for the binary
function symbol $\cdot\in\operatorname{\tau}$, $u\in T_{K}X=X^{*}$, which are
defined for every $w\in X^{*}$ as

$L^{(1)}_{(\cdot,u)}(w)=L(w\cdot u)=L(wu)\text{\ \ and\ \
}L^{(2)}_{(\cdot,u)}(w)=L(u\cdot w)=L(uw)$

which are respectively the left and right derivatives of $L$ with respect to
$u$.

In a similar way, from Example 2.5, we get the following Eilenberg–type
correspondences

  1. (1)

A one–to–one correspondence between varieties of semigroups and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

    1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete atomic Boolean algebra
$\operatorname{\mathtt{Set}}(X^{+},2)$ of subsets of $X^{+}$, i.e., every
element in $\operatorname{\mathscr{L}}(X)$ is a language on $X$ not containing
the empty word.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{+}$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of semigroups
$h:Y^{+}\to X^{+}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that
$L\circ h\in\operatorname{\mathscr{L}}(Y)$.

  2. (2)

A one–to–one correspondence between varieties of groups and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

    1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete Boolean algebra
$\operatorname{\mathtt{Set}}(\mathfrak{F}_{G}(X),2)$ of subsets of the free
group $\mathfrak{F}_{G}(X)$ on $X$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives and
inverses. That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x},L^{-1}\in\operatorname{\mathscr{L}}(X)$, where
${}_{x}L(w)=L(wx)$, $L_{x}(w)=L(xw)$ and $L^{-1}(w)=L(w^{-1})$,
$w\in\mathfrak{F}_{G}(X)$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of groups
$h:\mathfrak{F}_{G}(Y)\to\mathfrak{F}_{G}(X)$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

  3. (3)

For a fixed monoid $\mathbf{M}=(M,e,\cdot)$ a one–to–one correspondence
between varieties of $\mathbf{M}$–actions, i.e., dynamical systems on
$\mathbf{M}$, and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}$ such that for every
$X\in\operatorname{\mathtt{Set}}$:

    1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete atomic Boolean algebra
$\operatorname{\mathtt{Set}}(M\times X,2)$ of subsets of $M\times X$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under translations. That is, if
$L\in\operatorname{\mathscr{L}}(X)$ and $m\in M$ then
$mL\in\operatorname{\mathscr{L}}(X)$, where $mL(n,x)=L(m\cdot n,x)$, $(n,x)\in
M\times X$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of $\mathbf{M}$–actions
$h:M\times Y\to M\times X$ (i.e., $h(m\cdot(n,y))=m\cdot h(n,y)$) and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

  4. (4)

Consider the type of algebras $\operatorname{\tau}=\\{\cdot,(\underline{\ \
})^{\omega}\\}$ where $\cdot$ is a binary operation and $(\underline{\ \
})^{\omega}$ is a unary operation. Now, let $\mathsf{T}$ be the free monad on
$\operatorname{\mathtt{Set}}$ for the algebras of type $\operatorname{\tau}$
that satisfy the following equations:

$(x\cdot y)\cdot z=x\cdot(y\cdot z)$ |  $x^{\omega}\cdot y=x^{\omega}$ |  $(y\cdot x^{\omega})^{\omega}=y\cdot x^{\omega}$
---|---|---
$(x^{n})^{\omega}=x^{\omega}$, $n\geq 1$ |  $(x\cdot y)^{\omega}=x\cdot(y\cdot x)^{\omega}$ |

Here $x\cdot y$ is the product of $x$ and $y$, in that order, and $x^{\omega}$
represents the infinite product $x\cdot x\cdot\cdots$. Hence, for every
$X\in\operatorname{\mathtt{Set}}$ the algebra $\mathbf{TX}$ has as carrier set
the set $X^{+}\cup X^{(\omega)}$, where $X^{(\omega)}$ represents the set of
all ultimately periodic sequences in $X^{\omega}$, i.e., every element in
$X^{(\omega)}$ is of the form $uv^{\omega}$ for some $u,v\in X^{+}$, and
$X^{+}\cup X^{(\omega)}$ has the natural operations $\cdot$ of concatenation
and $(\underline{\ \ })^{\omega}$ of “infinite power”.
In this case, we get a one–to–one correspondence between varieties of
semigroups with infinite exponentiation and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

    1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{CABA}}$ and it is a
subalgebra of the complete atomic Boolean algebra
$\operatorname{\mathtt{Set}}(X^{+}\cup X^{(\infty)},2)$ of subsets of
$X^{+}\cup X^{(\infty)}$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives and
infinite exponentiation. That is, if $L\in\operatorname{\mathscr{L}}(X)$ and
$u\in X^{+}\cup X^{(\infty)}$ then
${}_{u}L,L_{u},L^{\omega}\in\operatorname{\mathscr{L}}(X)$, where
${}_{u}L(w)=L(wu)$, $L_{u}(w)=L(uw)$ and $L^{\omega}(w)=L(w^{\omega})$, $w\in
X^{+}\cup X^{(\omega)}$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of $\mathsf{T}$–algebras
$h:Y^{+}\cup Y^{(\infty)}\to X^{+}\cup X^{(\infty)}$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

We can do a similar work as in Example 2.5 to get Eilenberg–type
correspondences for varieties of ordered algebras for any given type.

######  Example 2.7.

Let $\operatorname{\tau}$ be a type of algebras where each function symbol
$g\in\operatorname{\tau}$ has arity $n_{g}\in\mathbb{N}$ and let $K$ be a
variety of ordered algebras of type $\operatorname{\tau}$. Consider the case
$\mathcal{D}=\operatorname{\mathtt{Poset}}$, $\mathcal{D}_{0}=$ discrete
posets, $\mathscr{E}=$ surjections, $\mathscr{M}=$ embeddings and let
$\mathsf{T}_{K}$ be the monad such that for every
$\mathbf{X}=(X,\leq)\in\operatorname{\mathtt{Poset}}$,
$T_{K}\mathbf{X}:=(T_{K}X,\leq_{T_{K}X})$ is the underlying poset of the free
ordered algebra in $K$ on $\mathbf{X}$ generators (see, e.g., [13, Proposition
1]). We have that $\operatorname{\mathtt{AlgCDL}}$ is dual to
$\operatorname{\mathtt{Poset}}$, so we can consider
$\mathcal{C}=\operatorname{\mathtt{AlgCDL}}$,
$\mathcal{C}_{0}=\operatorname{\mathtt{CABA}}$. Similar to Example 2.5, by
using the duality between $\operatorname{\mathtt{Poset}}$ and
$\operatorname{\mathtt{AlgCDL}}$, each coequational $\mathsf{B}$–theory can be
indexed by $\operatorname{\mathtt{Set}}$ (i.e., we consider every object
$X\in\operatorname{\mathtt{Set}}$ as the object
$(X,=)\in\operatorname{\mathtt{Poset}}$, which is in $\mathcal{D}_{0}$) and
can be presented, up to isomorphism, as a family
$\\{S_{X}\xhookrightarrow{m_{X}}2^{T_{K}X}\\}_{X\in\operatorname{\mathtt{Set}}}$,
then we present coequational $\mathsf{B}$–theories as operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ given by
$\operatorname{\mathscr{L}}(X):=\operatorname{Im}(m_{X})$. Then, we get a
one–to–one correspondence between varieties of ordered algebras in $K$ and
operators $\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such
that for every $X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{AlgCDL}}$ and it is a
subalgebra of the algebraic completely distributive lattice
$\operatorname{\mathtt{Poset}}(T_{K}X,\mathbf{2}_{c})\cong\operatorname{\mathtt{Set}}(T_{K}X,2)$
of subsets of $T_{K}X$. Here $\mathbf{2}_{c}\in\operatorname{\mathtt{Poset}}$
is the two–element chain.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under derivatives with respect to
the type $\operatorname{\tau}$. That is, for every $g\in\operatorname{\tau}$
of arity $n_{g}$, every $1\leq i\leq n_{g}$, every $t_{j}\in T_{K}X$, $1\leq
j<n_{g}$, and every $L\in\operatorname{\mathscr{L}}(X)$ we have that
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathscr{L}}(X)$ where
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathtt{Set}}(T_{K}X,2)$
is defined as

$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(t)=L(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1}))$

$t\in T_{K}X$. That is, for every function symbol $g\in\operatorname{\tau}$ we
get $n_{g}$ kinds of derivatives.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of
$\mathsf{T}_{K}$–algebras $h:T_{K}Y\to T_{K}X$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 2.8 (cf. [28, Theorem 5.8]).

From the previous example we can obtain Eilenberg–type correspondences for
varieties of ordered semigroups, varieties of ordered monoids, varieties of
ordered groups, and so on. For instance, for the case of varieties of ordered
semigroups we can consider the type $\operatorname{\tau}=\\{\cdot\\}$ where
$\cdot$ is a binary function symbol and $K$ is the variety of ordered
semigroups. Then we get a one–to–one correspondence between varieties of
ordered semigroups and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}$ such that for every
$X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{AlgCDL}}$ and it is a
subalgebra of the algebraic completely distributive lattice
$\operatorname{\mathtt{Set}}(X^{+},2)$ of subsets of $X^{+}$, i.e. every
element in $\operatorname{\mathscr{L}}(X)$ is a language on $X$ not containing
the empty word. In particular, $\operatorname{\mathscr{L}}(X)$ is closed under
unions and intersections.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{+}$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of semigroups
$h:Y^{+}\to X^{+}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that
$L\circ h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 2.9 (cf. [31, Théorème III.1.1.]).

Let $\mathbb{K}$ be a finite field. Consider the case
$\mathcal{D}=\mathcal{D}_{0}=\operatorname{\mathtt{Vec}_{\mathbb{K}}}$,
$\mathscr{E}=$ surjections, and $\mathscr{M}=$ injections. We have that
$\operatorname{\mathtt{StVec}_{\mathbb{K}}}$ is dual to
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}$, so we can consider
$\mathcal{C}=\mathcal{C}_{0}=\operatorname{\mathtt{StVec}_{\mathbb{K}}}$. For
every set $X$ denote by $\mathsf{V}(X)$ the $\mathbb{K}$–vector space with
basis $X$. Consider the monad $T(\mathsf{V}(X))=\mathsf{V}(X^{*})$, where
$X^{*}$ is the free monoid on $X$. Then we get a one–to–one correspondence
between varieties of $\mathbb{K}$–algebras and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{StVec}_{\mathbb{K}}}$
and it is a subspace of the space
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}(\mathsf{V}(X^{*}),\mathbb{K})$ where
the topology on
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}(\mathsf{V}(X^{*}),\mathbb{K})$ is
the subspace topology of the product $\mathbb{K}^{\mathsf{V}(X^{*})}$.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $v\in\mathsf{V}(X^{*})$
then ${}_{v}L,L_{v}\in\operatorname{\mathscr{L}}(X)$, where ${}_{v}L(w)=L(wv)$
and $L_{v}(w)=L(vw)$, $w\in\mathsf{V}(X^{*})$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, $\mathbb{K}$–linear map
$h:\mathsf{V}(Y^{*})\to\mathsf{V}(X^{*})$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 2.10 (cf. [29, Theorem 5 (iii)]).

Consider the case $\mathcal{D}=\operatorname{\mathtt{JSL}}$,
$\mathcal{D}_{0}=$ free join semilattices, i.e.,
$\mathcal{D}_{0}=\\{(\mathcal{P}_{f}(X),\cup)\mid
X\in\operatorname{\mathtt{Set}}\\}$, where $\mathcal{P}_{f}(X)$ is the set of
all finite subsets of $X$, $\mathscr{E}=$ surjections and $\mathscr{M}=$
injections. We have that $\operatorname{\mathtt{StJSL}}$ is dual to
$\operatorname{\mathtt{JSL}}$, so we can consider
$\mathcal{C}=\operatorname{\mathtt{StJSL}}$ and
$\mathcal{C}_{0}=\\{\operatorname{\mathtt{JSL}}((\mathcal{P}_{f}(X),\cup),2)\mid
X\in\operatorname{\mathtt{Set}}\\}$. Let $\mathsf{T}$ be the monad on
$\operatorname{\mathtt{JSL}}$ such that $T(S,\lor)$ is the free idempotent
semiring on $(S,\lor)\in\operatorname{\mathtt{JSL}}$. Then we get a one–to–one
correspondence between varieties of idempotent semirings and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}$ such that for
every $X\in\operatorname{\mathtt{Set}}$:

  1. i)

$\operatorname{\mathscr{L}}(X)\in\operatorname{\mathtt{StJSL}}$ and it is a
subspace of $\operatorname{\mathtt{Set}}(X^{*},2)$ where the topology given on
$\operatorname{\mathtt{Set}}(X^{*},2)$ is the subspace topology of the product
$2^{X^{*}}$. In particular, $\operatorname{\mathscr{L}}(X)$ is closed under
union.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{*}$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, semiring homomorphism
$h:\mathcal{P}_{f}(Y^{*})\to\mathcal{P}_{f}(X^{*})$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L^{\sharp}\circ
h\circ\eta_{Y^{*}}\in\operatorname{\mathscr{L}}(Y)$, where
$\eta_{Y^{*}}\in\operatorname{\mathtt{Set}}(Y^{*},\mathcal{P}_{f}(Y^{*}))$ and
$L^{\sharp}\in\operatorname{\mathtt{JSL}}(\mathcal{P}_{f}(X^{*}),2)$ are
defined as $\eta_{Y^{*}}(w)=\\{w\\}$ and
$L^{\sharp}(\\{w_{1},\ldots,w_{n}\\})=\bigvee_{i=1}^{n}L(w_{i})$. Note that
the composite $L^{\sharp}\circ h\circ\eta_{Y^{*}}$ is the same as
$h^{(-1)}(L)$ defined in [29]. The reason of the exponent ♯ and the use of
$\eta_{Y^{*}}$ is that we are using the isomorphism:

$\displaystyle\operatorname{\mathtt{JSL}}(\mathcal{P}_{f}(X^{*}),$
$\displaystyle 2)\cong\operatorname{\mathtt{Set}}(X^{*},2)$ $\displaystyle\
f\mapsto f\circ\eta_{X^{*}}$ $\displaystyle\ L^{\sharp}\mapsfrom L$

See the Appendix for more details.∎

######  Remark 2.11.

Note that Eilenberg–type correspondences for varieties of
$\mathbb{K}$–algebras and idempotent semirings can also be obtained from
Example 2.5.

##  3\. Eilenberg–type correspondences for pseudovarieties of
$\mathsf{T}$–algebras

This section is similar to the previous one with the restriction that all the
algebras considered are finite. We state a categorical version of Birkhoff’s
theorem for finite $\mathsf{T}$–algebras and an abstract Eilenberg–type
correspondence for pseudovarieties of $\mathsf{T}$–algebras. We use the prefix
‘pseudo’ to indicate that all the algebras considered are finite. That is, a
pseudovariety of $\mathsf{T}$–algebras is a variety of finite
$\mathsf{T}$–algebras, which is a class of finite $\mathsf{T}$–algebras closed
under homomorphic images, subalgebras and finite producs. The Birkhoff variety
theorem for finite algebras has been previously proved to prove that a class
of finite algebras of the same type is a pseudovariety, i.e., it is closed
under subalgebras, homomorphic images and finite products, if and only if it
is defined by ‘extended equations’ [30, 8]. An ‘extended equation’ is a
concept that generalizes the concept of an equation and can be defined by
using topological techniques or, alternatively, by implicit operations [30,
8]. Reiterman’s proof for the Birkhoff theorem for finite algebras involves
topological methods in which the set of $n$–ary implicit operations is the
completion of the set of $n$–ary terms [30]. A topological approach was also
explored by Banaschewski by using uniformities [8]. Recently, in [17],
profinite techniques were used to define the concept of profinite equations
which are the kind of equations that define pseudovarieties of
$\mathsf{T}$–algebras.

We provide a categorical version of the Birkhoff theorem for finite algebras,
Theorem 3, which, under mild assumptions, establishes a one–to–one
correspondence between pseudovarieties of $\mathsf{T}$–algebras and
pseudoequational $\mathsf{T}$–theories. Different versions of this theorem
such as [30, 8, 17] use topological approaches and/or profinite techniques. In
the present paper, topological approaches and profinite techniques are not
used, thus avoiding constructions of certain limits and profinite completions,
which gives us a better and basic understanding on how pseudovarieties are
characterized. The main strategy we follow to state and prove our theorem is
that pseudovarieties of algebras are exactly directed unions of equational
classes of finite algebras, which is a fact that was proved in [6, 8, 19]. The
definition of pseudoequational $\mathsf{T}$–theories is based on the previous
observation and the categorical dual of “varieties of languages” that was used
by the author to derive an Eilenberg–type correspondence for
$\mathsf{T}$–algebras [33].

As in the previous section, the main purpose of this approach is to derive
Eilenberg–type correspondences for pseudovarieties of $\mathsf{T}$–algebras.
This is summarized in the following picture:

Pseudovarietiesof $\mathsf{T}$–algebrasBirkhoff’s thm. forfinite
$\mathsf{T}$–alg. Thm.
3Pseudoequational$\mathsf{T}$–theoriesDualityPseudocoequational$\mathsf{B}$–theoriesEilenberg–type
correspondenceProposition 4

###  3.1. The Birkhoff theorem for finite $\mathsf{T}$–algebras

Throughout this section, we fix a complete concrete category $\mathcal{D}$
such that its forgetful functor preserves epis, monos and products, a monad
$\mathsf{T}=(T,\eta,\mu)$ on $\mathcal{D}$, a full subcategory
$\mathcal{D}_{0}$ of $\mathcal{D}$ and a factorization system
$\mathscr{E}/\mathscr{M}$ on $\mathcal{D}$. We make the following assumptions:

  1. (Bf1)

The factorization system $\mathscr{E}/\mathscr{M}$ is proper.

  2. (Bf2)

For every $X\in\mathcal{D}_{0}$, the free $\mathsf{T}$–algebra
$\mathbf{TX}=(TX,\mu_{X})$ is projective with respect to $\mathscr{E}$ in
$\operatorname{Alg}(\mathsf{T})$. That is, for every
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{B})$ with
$X\in\mathcal{D}_{0}$ and
$e\in\operatorname{Alg}(\mathsf{T})(\mathbf{A},\mathbf{B})\cap\mathscr{E}$
there exists $g\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ such
that $e\circ g=h$.

  3. (Bf3)

For every finite $\mathbf{A}\in\operatorname{Alg}(\mathsf{T})$ there exists
$X_{A}\in\mathcal{D}_{0}$ and
$s_{A}\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX_{A}},\mathbf{A})\cap\mathscr{E}$.

  4. (Bf4)

$T$ preserves morphisms in $\mathscr{E}$.

In order to talk about finite algebras, we assume that the category
$\mathcal{D}$ is a concrete category. That is, if
$U:\mathcal{D}\to\operatorname{\mathtt{Set}}$ is the forgetful functor for the
concrete category $\mathcal{D}$, then an object $X\in\mathcal{D}$ is finite if
$U(X)$ is a finite set. Similarly, an algebra
$\mathbf{A}\in\operatorname{Alg}(\mathsf{T})$ is finite if its carrier object
$A\in\mathcal{D}$ is finite. The algebras of interest will be the objects
$\operatorname{Alg}_{f}(\mathsf{T})$ of finite algebras in
$\operatorname{Alg}(\mathsf{T})$. The factorization system
$\mathscr{E}/\mathscr{M}$ on $\mathcal{D}$, which is lifted to
$\operatorname{Alg}(\mathsf{T})$ by using (Bf1) and (Bf4), allows us to define
the concept of homomorphic image and subalgebra. In this case, the requirement
of the forgetful functor $U$ preserving epis, monos and products, will give us
the property that subalgebras, homomorphic images and finite products of
finite algebras are also finite. The purpose of the subcategory
$\mathcal{D}_{0}$ is that the objects from which “variables” for the equations
are considered are objects in $\mathcal{D}_{0}$. Assumption (Bf3) guarantees
that every algebra is the homomorphic image of a free one with object of
generators in $\mathcal{D}_{0}$.

To obtain Birkhoff’s theorem for finite algebras we can consider
$\mathcal{D}=\operatorname{\mathtt{Set}}$, $\mathcal{D}_{0}=$ finite sets,
$\mathscr{E}=$ surjections, $\mathscr{M}=$ injections, and $\mathsf{T}$ to be
the term monad for a given type of algebras $\operatorname{\tau}$, i.e.,
$TX=T_{\operatorname{\tau}}(X)$, the set of terms of type
$\operatorname{\tau}$ on the set of variables $X$ (see Example 2.1). Another
important example will be given by $\mathcal{D}=\operatorname{\mathtt{Poset}}$
and $\mathcal{D}_{0}$ to be the full subcategory of finite discrete posets (as
before, we do not want the “variables” to be ordered).

Now, we will define the main concepts needed to state our categorical
Birkhoff’s theorem for finite $\mathsf{T}$–algebras.

Let $\mathcal{D}$ be a complete concrete category such that its forgetful
functor preserves epis, $\mathsf{T}$ a monad on $\mathcal{D}$,
$\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}_{0}$ and
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$. Assume
(Bf1) and (Bf4). A pseudoequational $\mathsf{T}$–theory on $\mathcal{D}_{0}$
is an operator $\operatorname{\mathtt{P}}$ on $\mathcal{D}_{0}$ such that for
every $X\in\mathcal{D}_{0}$, $\operatorname{\mathtt{P}}(X)$ is a nonempty
collection of $\mathsf{T}$–algebra morphisms in $\mathscr{E}$ with domain
$\mathbf{TX}$ and finite codomain and:

  1. i)

For every finite set $I$ and $f_{i}\in\operatorname{\mathtt{P}}(X)$, $i\in I$,
there exists $f\in\operatorname{\mathtt{P}}(X)$ such that every $f_{i}$
factors through $f$, $i\in I$.

  2. ii)

For every $e\in\operatorname{\mathtt{P}}(X)$ with codomain $\mathbf{A}$ and
every $\mathsf{T}$–algebra morphism $e^{\prime}\in\mathscr{E}$ with domain
$\mathbf{A}$ we have that $e^{\prime}\circ e\in\operatorname{\mathtt{P}}(X)$.

  3. iii)

For every $Y\in\mathcal{D}_{0}$, $f\in\operatorname{\mathtt{P}}(X)$ and
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TY},\mathbf{TX})$ we have that
$e_{f\circ h}\in\operatorname{\mathtt{P}}(Y)$ where $f\circ h=m_{f\circ
h}\circ e_{f\circ h}$ is the factorization of $f\circ h$.

Pseudovarieties of algebras are exactly directed unions of equational classes
of finite algebras [6, 8, 19]. With this in mind, we can give an intuition of
the previous definition. In fact, for each object $X\in\mathcal{D}_{0}$ of
variables every morphism $f\in\operatorname{\mathtt{P}}(X)$ represents a set
of equations on $X$, namely $\ker(f)$, which can be equivalently given by a
$\mathsf{T}$–algebra morphism in $\mathscr{E}$ with domain $\mathbf{TX}$.
Condition i) says that the set of all the equations on a fixed $X$ is a
directed set, i.e., for every set of equations
$f_{i}\in\operatorname{\mathtt{P}}(X)$, $i\in I$, with $I$ finite, there is an
upper bound $f\in\operatorname{\mathtt{P}}(X)$. Here $f$ is an upper bound of
$\\{f_{i}\mid i\in I\\}$ if every $f_{i}$ factors through $f$. Condition iii)
says that all the equations considered are preserved under any substitution
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TY},\mathbf{TX})$ of variables in
$Y$ by terms in $TX$, this condition is related to the commutativity of the
diagram given in Definition 2.1. Condition ii) is needed for uniqueness of the
pseudoequational theory defining a given pseudovariety of algebras. In fact,
two directed unions of equational classes of finite algebras can give us the
same pseudovariety, but if we put the requirement of being downward closed,
which is the requirement in condition ii), then we get uniqueness.

Given an algebra $\mathbf{A}\in\operatorname{Alg}_{f}(\mathsf{T})$, we say
that $\mathbf{A}$ satisfies $\operatorname{\mathtt{P}}$, denoted as
$\mathbf{A}\models\operatorname{\mathtt{P}}$, if for every
$X\in\mathcal{D}_{0}$ and
$f\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ we have that $f$
factors through some morphism in $\operatorname{\mathtt{P}}(X)$. We denote by
$\operatorname{Mod}_{f}(\operatorname{\mathtt{P}})$ the finite models of
$\operatorname{\mathtt{P}}$, that is:

$\operatorname{Mod}_{f}(\operatorname{\mathtt{P}}):=\\{\mathbf{A}\in\operatorname{Alg}_{f}(\mathsf{T})\mid\mathbf{A}\models\operatorname{\mathtt{P}}\\}$

A class $K$ of finite $\mathsf{T}$–algebras is defined by
$\operatorname{\mathtt{P}}$ if
$K=\operatorname{Mod}_{f}(\operatorname{\mathtt{P}})$.

Let $K$ be a class of algebras in $\operatorname{Alg}_{f}(\mathsf{T})$. We say
that $K$ is closed under $\mathscr{E}$–quotients if $\mathbf{B}\in K$ for
every
$e\in\operatorname{Alg}(\mathsf{T})(\mathbf{A},\mathbf{B})\cap\mathscr{E}$
with $\mathbf{A}\in K$. We say that $K$ is closed under
$\mathscr{M}$–subalgebras if $\mathbf{B}\in K$ for every
$m\in\operatorname{Alg}(\mathsf{T})(\mathbf{B},\mathbf{A})\cap\mathscr{M}$
with $\mathbf{A}\in K$. We say that $K$ is closed under finite products if
$\prod_{i\in I}\mathbf{A}_{i}\in K$ for every finite set $I$ such that
$\mathbf{A}_{i}\in K$, $i\in I$.

Let $\mathcal{D}$ be a complete concrete category, $\mathsf{T}$ a monad on
$\mathcal{D}$ and $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$. A class $K$ of finite algebras in
$\operatorname{Alg}(\mathsf{T})$ is called a pseudovariety of
$\mathsf{T}$–algebras  if it is closed under $\mathscr{E}$–quotients,
$\mathscr{M}$–subalgebras and finite products.

######  Example 3.1.

Consider the setting $\mathcal{D}=\operatorname{\mathtt{Set}}$,
$\mathcal{D}_{0}=$ finite sets, $\mathscr{E}=$ surjections, $\mathscr{M}=$
injections, and $\mathsf{T}$ to be the term monad for a given type of algebras
$\operatorname{\tau}$. Then we have that equational classes of finite algebras
are examples of pseudovarieties of $\mathsf{T}$–algebras. For example, finite
semigroups, finite monoids, finite groups, finite vector spaces, finite
Boolean algebras, finite lattices, and so on. In [8], some non–equational
examples of pseudovarieties are shown such as:

  1. (1)

the finite commutative monoids satisfying some identity $x^{n}=x^{n+1}$,
$n=1,2,\ldots$,

  2. (2)

the finite cancellation monoids,

  3. (3)

the finite abelian $p$–groups, for a given prime number $p$, and

  4. (4)

the finite products of finite fields of a given prime characteristic.

Each of those pseudovarieties is not equational. In fact, every equation
satisfied in the given pseudovariety is also satisfied in the larger
pseudovariety, i.e., the pseudovariety of all commutative monoids for (1), the
pseudovariety of all monoids for (2), the pseudovariety of all abelian groups
for (3), and the pseudovariety of all commutative rings with unit of a given
prime characteristic for (4).∎

Now we can formulate our categorical Birkhoff’s theorem for finite
$\mathsf{T}$–algebras as follows.

######  Theorem 3 (Birkhoff’s Theorem for finite $\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete concrete category such that its forgetful
functor preserves epis, monos and products, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}_{0}$ and
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$. Assume
(Bf1) to (Bf4). Then a class $K$ of finite $\mathsf{T}$–algebras is a
pseudovariety of $\mathsf{T}$–algebras if and only if is defined by a
pseudoequational $\mathsf{T}$–theory on $\mathcal{D}_{0}$. Additionally,
pseudovarieties of $\mathsf{T}$–algebras are in one–to–one correspondence with
pseudoequational $\mathsf{T}$–theories on $\mathcal{D}_{0}$. ∎

Now we derive Birkhoff’s theorem for pseudovarieties of (ordered) algebras for
a given type, then show an example of a particular pseudovariety of algebras
with its defining pseudoequational $\mathsf{T}$–theory and finish this
subsection by deriving Eilenberg’s theorem [18, Theorem 34] to show a
one–to–one correspondence between pseudovarieties of monoids and
pseudovarieties of languages.

######  Example 3.2.

Consider the case $\mathcal{D}=\operatorname{\mathtt{Set}}$,
$\mathcal{D}_{0}=$ finite sets, $\mathscr{E}=$ surjections, $\mathscr{M}=$
injections and, for a given type of algebras $\operatorname{\tau}$, let
$\mathsf{T}_{\operatorname{\tau}}$ be the term monad for
$\operatorname{\tau}$. Then, by Theorem 3, a class of algebras of type
$\operatorname{\tau}$ is a pseudovariety if and only if it is defined by a
pseudoequational $\mathsf{T}_{\operatorname{\tau}}$–theory.∎

######  Example 3.3.

Consider the case $\mathcal{D}=\operatorname{\mathtt{Poset}}$,
$\mathcal{D}_{0}=$ finite discrete posets, $\mathscr{E}=$ surjections,
$\mathscr{M}=$ embeddings and, for a given type of algebras
$\operatorname{\tau}$, let $\mathsf{T}_{\operatorname{\tau}}$ be the monad on
$\operatorname{\mathtt{Poset}}$ defined in Example 2.1. Then, by Theorem 3, a
class of ordered algebras of type $\operatorname{\tau}$ is a pseudovariety if
and only if it is defined by a pseudoequational
$\mathsf{T}_{\operatorname{\tau}}$–theory.∎

######  Example 3.4.

Consider the case $\mathcal{D}=\operatorname{\mathtt{Set}}$,
$\mathcal{D}_{0}=$ finite sets, $\mathsf{T}$ the monad given by $TX=X^{*}$,
where $X^{*}$ is the free monoid on $X$, $\mathscr{E}=$ surjections, and
$\mathscr{M}=$ injections. We have that conditions (Bf1) to (Bf4) are
fullfilled. In this case, we have that $\operatorname{Alg}(\mathsf{T})$ is the
category of monoids. To describe the pseudovariety of all commutative monoids
satisfying some identity $x^{n}=x^{n+1}$, $n=1,2,\ldots$, we define
$\operatorname{\mathtt{P}}$ on $\mathcal{D}_{0}$ as follows:

  1. -

For every $X\in\mathcal{D}_{0}$, and $n=1,2\ldots$, we define the surjective
homomorphism of monoids
$e_{n}:X^{*}\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}\mathfrak{F}_{n}(X)$,
where $\mathfrak{F}_{n}(X)$ is the free commutative monoid on $X$ that
satisfies the identity $x^{n}=x^{n+1}$. That is,
$\mathfrak{F}_{n}(X)=(\operatorname{\mathtt{Set}}(X,\mathbb{N}),\cdot,0)$
where $0\in\operatorname{\mathtt{Set}}(X,\mathbb{N})$ is the zero function,
i.e., $0(x)=0$ for every $x\in X$, and $\cdot$ is defined on
$\operatorname{\mathtt{Set}}(X,\mathbb{N})$ as $(f\cdot
g)(x)=\min\\{n,f(x)+g(x)\\}$. $e_{n}$ is defined on the set of generators $X$
as $e_{n}(x)=\chi_{x}$, where $\chi_{x}(x)=1$ and $\chi_{x}(y)=0$ for $x\neq
y$. Define $\operatorname{\mathtt{P}}(X)$ as:

$\operatorname{\mathtt{P}}(X)=\\{e^{\prime}\circ e_{n}\mid
n\in\mathbb{N}^{+}\text{ and $e^{\prime}$ is a $\mathsf{T}$--algebra morphism
in $\mathscr{E}$ with domain $\mathfrak{F}_{n}(X)$}\\}$

We have then that $\operatorname{\mathtt{P}}$ is a pseudoequational
$\mathsf{T}$–theory and $\operatorname{Mod}_{f}(\operatorname{\mathtt{P}})$ is
the pseudovariety of all finite commutative monoids that satisfy some identity
$x^{n}=x^{n+1}$, $n=1,2,\ldots$.∎

In the next example we derive Eilenberg’s variety theorem [18, Theorem 3.4.].
Given a finite set $\Sigma$, i.e., an alphabet, a language $L$ on $\Sigma$ is
a subset $L$ of $\Sigma^{*}$, i.e., a collection of words with letters in
$\Sigma$. We identify a language $L$ on $\Sigma$ by its characteristic
function $L:\Sigma^{*}\to 2$. A language $L$ on $\Sigma$ is recognizable if
there exists a finite monoid $\mathbf{A}$, a homomorphism of monoids
$h:\Sigma^{*}\to A$ and a function $L^{\prime}:A\to 2$ such that
$L^{\prime}\circ h=L$. We denote by $\operatorname{Rec}(\Sigma)$ the Boolean
algebra of all recognizable languages on $\Sigma$. A pseudovariety of
languages is an operator $\operatorname{\mathscr{L}}$ such that for every
finite set $\Sigma$ we have:

  1. i)

$\operatorname{\mathscr{L}}(\Sigma)$ is a subalgebra of the Boolean algebra
$\operatorname{Rec}(\Sigma)$,

  2. ii)

$\operatorname{\mathscr{L}}(\Sigma)$ is closed under left and right
derivatives. That is, ${}_{a}L,L_{a}\in\operatorname{\mathscr{L}}(\Sigma)$ for
every $L\in\operatorname{\mathscr{L}}(\Sigma)$ and $a\in\Sigma$, and

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every alphabet $\Gamma$, homomorphism of monoids $h:\Gamma^{*}\to\Sigma^{*}$
and $L\in\operatorname{\mathscr{L}}(\Sigma)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(\Gamma)$.

Eilenberg’s variety theorem [18, Theorem 34] says that there is a one–to–one
correspondence between pseudovarieties of monoids and pseudovarieties of
languages. This theorem is derived from Theorem 3 as follows.

######  Example 3.5 (Eilenberg’s variety theorem).

Consider the setting as in the previous example, i.e.,
$\mathcal{D}=\operatorname{\mathtt{Set}}$, $\mathcal{D}_{0}=$ finite sets,
$\mathsf{T}$ the monad given by $TX=X^{*}$, where $X^{*}$ is the free monoid
on $X$, $\mathscr{E}=$ surjections, and $\mathscr{M}=$ injections. Then, we
have a one–to–one correspondence between pseudovarieties of monoids, i.e.,
pseudovarieties of $\mathsf{T}$–algebras, and pseudoequational
$\mathsf{T}$–theories on $\mathcal{D}_{0}$. Now, we have that pseudoequational
$\mathsf{T}$–theories on $\mathcal{D}_{0}$ are in one–to–one correspondence
with pseudovarieties of languages. In fact, every pseudoequational
$\mathsf{T}$–theory $\operatorname{\mathtt{P}}$ on $\mathcal{D}_{0}$ defines
the pseudovariety of languages
$\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}$ defined as
$\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}(X):=\bigcup_{e\in\operatorname{\mathtt{P}}(X)}\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))$,
and every pseudovariety of languages $\operatorname{\mathscr{L}}$ defines the
pseudoequational $\mathsf{T}$–theory
$\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}$ on $\mathcal{D}_{0}$
such that $\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ is the
collection of all $\mathsf{T}$–algebra morphisms $e\in\mathscr{E}$ with domain
$\mathbf{TX}$ and finite codomain such that
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathscr{L}}(X)$,
$X\in\mathcal{D}_{0}$. Furthermore, this correspondence is bijective, that is,
for every pseudoequational $\mathsf{T}$–theory $\operatorname{\mathtt{P}}$ on
$\mathcal{D}_{0}$ and every pseudovariety of languages
$\operatorname{\mathscr{L}}$ we have that
$\operatorname{\mathtt{P}}=\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}}$
and
$\operatorname{\mathscr{L}}=\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}}$
(see Example 3.6 for more details). ∎

###  3.2. Abstract Eilenberg–type correspondence for pseudovarieties of
$\mathsf{T}$–algebras

As we saw in Example 3.5, we can derive Eilenberg–type correspondences for
pseudovarieties of $\mathsf{T}$–algebras from Birkhoff’s theorem for finite
$\mathsf{T}$–algebras, Theorem 3. Eilenberg–type correspondences for
pseudovariaties of $\mathsf{T}$–algebras are exactly one–to–one
correspondences between pseudovarieties of $\mathsf{T}$–algebras and duals of
pseudoequational $\mathsf{T}$–theories. By dualizing the definition of a
pseudoequational $\mathsf{T}$–theory we get the following.

Let $\mathcal{C}$ be a concrete category such that its forgetful functor
preserves monos, $\mathsf{B}=(\mathsf{B},\epsilon,\delta)$ a comonad on
$\mathcal{C}$, $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{C}$ and $\mathcal{C}_{0}$ a full subcategory of $\mathcal{C}$.
Assume (Bf1) and that $B$ preserves the morphisms in $\mathscr{M}$. A
pseudocoequational $\mathsf{B}$–theory on $\mathcal{C}_{0}$ is an operator
$\operatorname{\mathtt{R}}$ on $\mathcal{C}_{0}$ such that for every
$X\in\mathcal{C}_{0}$, $\operatorname{\mathtt{R}}(X)$ is a nonempty collection
of $\mathsf{B}$–coalgebra morphisms in $\mathscr{M}$ with codomain
$\mathbf{BX}$ and finite domain and:

  1. i)

For every finite set $I$ and $f_{i}\in\operatorname{\mathtt{R}}(X)$, $i\in I$,
there exists $f\in\operatorname{\mathtt{R}}(X)$ such that every $f_{i}$
factors through $f$, $i\in I$.

  2. ii)

For every $m\in\operatorname{\mathtt{R}}(X)$ with domain $\mathbf{A}$ and
every $\mathsf{B}$–coalgebra morphism $m^{\prime}\in\mathscr{M}$ with codomain
$\mathbf{A}$ we have that $m\circ m^{\prime}\in\operatorname{\mathtt{R}}(X)$.

  3. iii)

For every $Y\in\mathcal{C}_{0}$, $f\in\operatorname{\mathtt{R}}(X)$ and
$h\in\operatorname{Coalg}(\mathsf{B})(\mathbf{BX},\mathbf{BY})$ we have that
$m_{h\circ f}\in\operatorname{\mathtt{R}}(Y)$ where $h\circ f=m_{h\circ
f}\circ e_{h\circ f}$ is the factorization of $h\circ f$.

With the previous definition, Theorem 3 and duality, we have the following:

######  Proposition 4 (Abstract Eilenberg–type correspondence for
pseudovarieties of $\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete concrete category such that its forgetful
functor preserves epis, monos and products, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathcal{D}_{0}$ a full subcategory of $\mathcal{D}_{0}$ and
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$. Assume
(Bf1) to (Bf4). Let $\mathcal{C}$ be a category that is dual to $\mathcal{D}$,
let $\mathcal{C}_{0}$ be dual of $\mathcal{D}_{0}$ and $\mathsf{B}$ be the
comonad on $\mathcal{C}$ that is dual to the monad $\mathsf{T}$ on
$\mathcal{D}$ which is defined as in Proposition 1. Then there is a one–to–one
correspondence between pseudovarieties of $\mathsf{T}$–algebras and
pseudocoequational $\mathsf{B}$–theories on $\mathcal{C}_{0}$.

We will consider the same settings given in the examples in subsection 2.2 to
obtain the following Eilenberg–type correspondences for pseudovarieties of
$\mathsf{T}$–algebras. In all of them, we only need to change the category
$\mathcal{D}_{0}$ and condition i) for the operators
$\operatorname{\mathscr{L}}$ (see Appendix for their details).

######  Example 3.6 (cf. Example 2.5).

In this example we obtain an Eilenberg–type correspondence for any
pseudovariety of algebras of any given type $\operatorname{\tau}$, where each
of the function symbols in $\operatorname{\tau}$ has finite arity. Let
$\operatorname{\tau}$ be a type of algebras where each function symbol
$g\in\operatorname{\tau}$ has arity $n_{g}\in\mathbb{N}$ and let $K$ be a
variety of algebras for of type $\operatorname{\tau}$. Consider the case
$\mathcal{D}=\operatorname{\mathtt{Set}}$,
$\mathcal{D}_{0}=\operatorname{\mathtt{Set}}_{f}$, $\mathscr{E}=$ surjections,
$\mathscr{M}=$ injections and let $\mathsf{T}_{K}$ be the monad such that for
every $X\in\operatorname{\mathtt{Set}}$, $T_{K}X$ is the underlying set of the
free algebra in $K$ on $X$ generators (see [16, Definition II.10.9] and [27,
VI.8]). We have that $\operatorname{\mathtt{CABA}}$ is dual to
$\operatorname{\mathtt{Set}}$, so we can consider
$\mathcal{C}=\operatorname{\mathtt{CABA}}$ and
$\mathcal{C}_{0}=\operatorname{\mathtt{CABA}}_{f}$. In this case, we get a
one–to–one correspondence between pseudovarieties of algebras in $K$ and
operators $\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}_{f}$
such that for every $X\in\operatorname{\mathtt{Set}}_{f}$:

  1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean algebra and it is a subalgebra of
the complete atomic Boolean algebra $\operatorname{\mathtt{Set}}(T_{K}X,2)$ of
subsets of $T_{K}X$ such that for every $L\in\operatorname{\mathscr{L}}(X)$
there exists a finite algebra $\mathbf{A}$ in $K$, a morphism
$h\in\operatorname{Alg}(\mathsf{T}_{K})(\mathbf{T_{K}X},\mathbf{A})$ and
$L^{\prime}\in\operatorname{\mathtt{Set}}(A,2)$ such that $L=L^{\prime}\circ
h$.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under derivatives with respect to
the type $\operatorname{\tau}$. That is, for every $g\in\operatorname{\tau}$
of arity $n_{g}$, every $1\leq i\leq n_{g}$, every $t_{j}\in T_{K}X$, $1\leq
j<n_{g}$, and every $L\in\operatorname{\mathscr{L}}(X)$ we have that
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathscr{L}}(X)$ where
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathtt{Set}}(T_{K}X,2)$
is defined as

$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(t)=L(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1}))$

$t\in T_{K}X$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}_{f}$, homomorphism of
$\mathsf{T}_{K}$–algebras $h:T_{K}Y\to T_{K}X$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

In fact, let $\operatorname{\mathtt{P}}$ be a pseudoequational
$\mathsf{T}_{K}$–theory on $\operatorname{\mathtt{Set}}_{f}$ and let
$\operatorname{\mathscr{L}}$ be an operator on
$\operatorname{\mathtt{Set}}_{f}$ satisfying the three properties above. Then:

  1. a)

Define the operator $\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}$
on $\operatorname{\mathtt{Set}}_{f}$ as
$\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}(X):=\bigcup_{e\in\operatorname{\mathtt{P}}(X)}\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))$.
We claim that $\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}$
satisfies the three properties above. In fact, as the family
$\operatorname{\mathtt{P}}(X)$ is directed in the sense of Definition 3.1 i),
then the union
$\bigcup_{e\in\operatorname{\mathtt{P}}(X)}\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathtt{Set}}(T_{K}X,2)$
is a directed union of finite objects in $\operatorname{\mathtt{CABA}}$ which
is a Boolean subalgebra of $\operatorname{\mathtt{Set}}(T_{K}X,2)$. As each
$e\in\operatorname{\mathtt{P}}(X)$ has as codomain a finite algebra in $K$
then $\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))$ is a subset of
$\operatorname{\mathtt{Set}}(T_{K}X,2)$ which is closed under derivatives with
respect to the type $\operatorname{\tau}$ (see Example 2.5). The previous
argument shows that $\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}$
satisfies properties i) and ii) above. Now, closure under morphic preimages
follows from property iii) in Definition 3.1. Therefore,
$\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}$ satisfies the three
properties above.

  2. b)

Define the operator $\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}$
on $\operatorname{\mathtt{Set}}_{f}$ such that
$\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ is the collection
of all $\mathsf{T}_{K}$–algebra morphisms $e\in\mathscr{E}$ with domain
$\mathbf{T_{K}X}$ and finite codomain such that
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathscr{L}}(X)$.
We claim that $\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}$ is a
pseudoequational $\mathsf{T}_{K}$–theory. In fact, we have that
$\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ is nonempty since
$e:\mathbf{T_{K}X}\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}\mathbf{1}\in\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$,
where $\mathbf{1}$ is the one–element $\mathsf{T}_{K}$–algebra. By definition,
we have that $\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$
satisfies property ii) in Definition 3.1, and, it also satisfies property iii)
in Definition 3.1 since $\operatorname{\mathscr{L}}$ is closed under morphic
preimages. Now, consider a family
$\\{T_{K}X\overset{e_{i}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}A_{i}\\}_{i\in
I}$ in $\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ with $I$
finite such that
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e_{i},2))\subseteq\operatorname{\mathscr{L}}(X)$,
we need to find a morphism
$e\in\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ such that
every $e_{i}$ factors through $e$. In fact, let $\mathbf{A}$ be the product of
$\prod_{i\in I}\mathbf{A_{i}}$ with projections $\pi_{i}:A\to A_{i}$, then, by
the universal property of $\mathbf{A}$ there exists a $\mathsf{T}_{K}$–algebra
morphism $f:T_{K}X\to A$ such that $\pi_{i}\circ f=e_{i}$, for every $i\in I$.
Let $f=m_{f}\circ e_{f}$ be the factorization of $f$ in
$\operatorname{Alg}(\mathsf{T}_{K})$. We claim that $e=e_{f}$ is a morphism in
$\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}(X)$ such that every
$e_{i}$ factors through $e$. Clearly, from the construction above, each
$e_{i}$ factors through $e=e_{f}$. Now, let’s prove that
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathscr{L}}(X)$.
In fact, let $\mathbf{S}$ be the codomain of $e=e_{f}$ and let
$g\in\operatorname{\mathtt{Set}}(S,2)$. We have to prove that $g\circ
e\in\operatorname{\mathscr{L}}(X)$ which follows from the following
straightforward identity:

$g\circ e=\bigcup_{s\in g}\left(\bigcap_{i\in I}h_{i,s}\circ e_{i}\right)$

where $h_{i,s}\in\operatorname{\mathtt{Set}}(A_{i},2)$ is the set
$\\{\pi_{i}(m_{f}(s))\\}$ (i.e., we express the subset $g$ of $S$ as the union
of its points and each point $s\in S$ is represented as $\bigcap_{i\in
I}h_{i,s}\circ\pi_{i}\circ m_{f}$). Now, for every $s\in S$ and $i\in I$ the
composition $h_{i,s}\circ e_{i}$ belongs to $\operatorname{\mathscr{L}}(X)$
since $h_{i,s}\circ
e_{i}\in\operatorname{Im}(\operatorname{\mathtt{Set}}(e_{i},2))\subseteq\operatorname{\mathscr{L}}(X)$.
As $S$ and $I$ are finite then $g\circ e\in\operatorname{\mathscr{L}}(X)$
because $\operatorname{\mathscr{L}}(X)$ is a Boolean algebra.

  3. c)

We have that
$\operatorname{\mathtt{P}}=\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}}$.
In fact, for every $X\in\operatorname{\mathtt{Set}}_{f}$ the inclusion
$\operatorname{\mathtt{P}}(X)\subseteq\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}}(X)$
is obvious. Now, to prove that
$\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}}(X)\subseteq\operatorname{\mathtt{P}}(X)$,
let
$e^{\prime}\in\operatorname{Alg}(\mathsf{T})(\mathbf{T_{K}X},\mathbf{A})\cap\mathscr{E}$
with finite codomain such that
$e^{\prime}\in\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}}}(X)$,
i.e.,
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e^{\prime},2))\subseteq\bigcup_{e\in\operatorname{\mathtt{P}}(X)}\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))$.
Then the previous inclusion means that for every
$f\in\operatorname{\mathtt{Set}}(A,2)$ there exists
$e_{f}\in\operatorname{\mathtt{P}}(X)$ and $g_{f}$ such that $f\circ
e^{\prime}=g_{f}\circ e_{f}$. As $\\{e_{f}\mid
f\in\operatorname{\mathtt{Set}}(A,2)\\}$ is finite, then there exists
$e\in\operatorname{\mathtt{P}}(X)$ such that each $e_{f}$ factors through $e$.
We will prove that $e^{\prime}$ factors through
$e\in\operatorname{\mathtt{P}}(X)$ which will imply that
$e^{\prime}\in\operatorname{\mathtt{P}}(X)$, since $\operatorname{\mathtt{P}}$
is a pseudoequational $\mathsf{T}_{K}$–theory. It is enough to show that
$\ker(e)\subseteq\ker(e^{\prime})$. In fact, assume that $(u,v)\in\ker(e)$ and
define $f^{\prime}\in\operatorname{\mathtt{Set}}(A,2)$ as $f^{\prime}(x)=1$
iff $x=e^{\prime}(u)$. Then, as $e_{f^{\prime}}$ factors through $e$ we have
that $\ker(e)\subseteq\ker(e_{f^{\prime}})$ which implies
$(u,v)\in\ker(e_{f^{\prime}})$. But
$\ker(e_{f^{\prime}})\subseteq\ker(g_{f^{\prime}}\circ
e_{f^{\prime}})=\ker(f^{\prime}\circ e^{\prime})$, which implies that
$(u,v)\in\ker(f^{\prime}\circ e^{\prime})$, i.e.,
$1=f^{\prime}(e^{\prime}(u))=f^{\prime}(e^{\prime}(v))$, but the later
equality means that $e^{\prime}(u)=e^{\prime}(v)$ by definition of
$f^{\prime}$, i.e., $(u,v)\in\ker(e^{\prime})$ as desired.

  4. d)

We have that
$\operatorname{\mathscr{L}}=\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}}$.
In fact, for every $X\in\operatorname{\mathtt{Set}}_{f}$ the inclusion
$\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}}(X)\subseteq\operatorname{\mathscr{L}}(X)$
is obvious. Now, to prove
$\operatorname{\mathscr{L}}(X)\subseteq\operatorname{\mathscr{L}}_{\operatorname{\mathtt{P}}_{\operatorname{\mathscr{L}}}}(X)$
we need to find for every $L\in\operatorname{\mathscr{L}}(X)$ a surjective
homomorphism $e:T_{K}X\to A$ with $\mathbf{A}\in K$ such that
$L\in\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathscr{L}}(X)$.
In fact, for $L\in\operatorname{\mathscr{L}}(X)$ let $e^{\prime}:T_{K}X\to B$
be a homomorphism with $\mathbf{B}\in K$ and
$g\in\operatorname{\mathtt{Set}}(B,2)$ such that $L=g\circ e^{\prime}$, this
can be done by property i) above. Let $\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle$ be the subset of
$\operatorname{\mathtt{Set}}(T_{K}X,2)$ obtained from $\\{L\\}$ which is
closed under Boolean combinations and derivatives with respect to the type
$\operatorname{\tau}$. We show that $\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle\in\operatorname{Coalg}_{f}(\mathsf{B})$, that is,
we show that $\langle\mkern-3.0mu\langle L\rangle\mkern-3.0mu\rangle$ is a
finite object in $\operatorname{\mathtt{CABA}}$ that is closed under
derivatives with respect to the type $\operatorname{\tau}$. In fact,
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e^{\prime},2))\in\operatorname{Coalg}_{f}(\mathsf{B})$
is such that $\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle\subseteq\operatorname{Im}(\operatorname{\mathtt{Set}}(e^{\prime},2))$,
which implies that $\langle\mkern-3.0mu\langle L\rangle\mkern-3.0mu\rangle$ is
a finite Boolean algebra, i.e., an object in
$\operatorname{Coalg}_{f}(\mathsf{B})$. By construction of
$\langle\mkern-3.0mu\langle L\rangle\mkern-3.0mu\rangle$ we have that
$L\in\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle\subseteq\operatorname{\mathscr{L}}(X)$ since
$\operatorname{\mathscr{L}}$ satisfies properties i) and ii) above. Now, let
$i\in\operatorname{Coalg}(\mathsf{B})(\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle,\operatorname{\mathtt{Set}}(T_{K}X,2))$ be the
inclusion morphism, then by duality we have that the dual morphism $e$ in
$\operatorname{Alg}(\mathsf{T}_{K})$ of $i$ is such that
$L\in\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))\subseteq\operatorname{\mathscr{L}}(X)$
(in fact,
$\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))=\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle$). Note that the codomain of $e$ is in $K$ since
it is an $\mathscr{E}$–quotient of $\mathbf{B}\in K$.

######  Remark 3.7.

Note that, for every “language” $L\in\operatorname{\mathtt{Set}}(T_{K}X,2)$,
the object $\langle\mkern-3.0mu\langle L\rangle\mkern-3.0mu\rangle$ in d)
above is the $\mathsf{B}$–subcoalgebra of
$\operatorname{\mathtt{Set}}(T_{K}X,2)$ generated by $L$ which implies, by
duality, that its dual is the syntactic algebra $\mathbf{S}_{L}$ of $L$.
Additionally, by using duality and the construction of
$\langle\mkern-3.0mu\langle L\rangle\mkern-3.0mu\rangle$, we have that every
“language” in $\operatorname{Im}(\operatorname{\mathtt{Set}}(e,2))$ (i.e.,
recognized by the syntactic algebra of $L$) is a Boolean combination of
derivatives of $L$, where $e$ is the dual of the inclusion
$i\in\operatorname{Coalg}(\mathsf{B})(\langle\mkern-3.0mu\langle
L\rangle\mkern-3.0mu\rangle,\operatorname{\mathtt{Set}}(T_{K}X,2))$.∎

######  Example 3.8.

From the previous example, we get the following Eilenberg–type
correspondences:

  1. (1)

[18, Theorem 34] A one–to–one correspondence between pseudovarieties of
monoids and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

    1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean subalgebra of
$\operatorname{\mathtt{Set}}(X^{*},2)$ such that for every
$L\in\operatorname{\mathscr{L}}(X)$ there exists a finite monoid $\mathbf{M}$,
a homomorphism $h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{M})$
and $L^{\prime}\in\operatorname{\mathtt{Set}}(M,2)$ such that $L^{\prime}\circ
h=L$, i.e., $L$ is a recognizable language on $X$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{*}$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of monoids $h:Y^{*}\to
X^{*}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

  2. (2)

[18, Theorem 34s] A one–to–one correspondence between pseudovarieties of
semigroups and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

    1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean subalgebra of
$\operatorname{\mathtt{Set}}(X^{+},2)$ such that for every
$L\in\operatorname{\mathscr{L}}(X)$ there exists a finite semigroup
$\mathbf{S}$, a homomorphism
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{S})$ and
$L^{\prime}\in\operatorname{\mathtt{Set}}(S,2)$ such that $L^{\prime}\circ
h=L$, i.e., $L$ is a recognizable language on $X$ not containing the empty
word.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{+}$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of semigroups
$h:Y^{+}\to X^{+}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that
$L\circ h\in\operatorname{\mathscr{L}}(Y)$.

  3. (3)

A one–to–one correspondence between pseudovarieties of groups and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}_{f}$ such that
for every $X\in\operatorname{\mathtt{Set}}_{f}$:

    1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean subalgebra of
$\operatorname{\mathtt{Set}}(\mathfrak{F}_{G}(X),2)$ such that for every
$L\in\operatorname{\mathscr{L}}(X)$ there exists a finite group $\mathbf{G}$,
a homomorphism $h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{G})$
and $L^{\prime}\in\operatorname{\mathtt{Set}}(G,2)$ such that $L^{\prime}\circ
h=L$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives and
inverses. That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x},L^{-1}\in\operatorname{\mathscr{L}}(X)$, where
${}_{x}L(w)=L(wx)$, $L_{x}(w)=L(xw)$ and $L^{-1}(w)=L(w^{-1})$,
$w\in\mathfrak{F}_{G}(X)$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of groups
$h:\mathfrak{F}_{G}(Y)\to\mathfrak{F}_{G}(X)$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

  4. (4)

For a fixed monoid $\mathbf{M}=(M,e,\cdot)$, a one–to–one correspondence
between pseudovarieties of $\mathbf{M}$–actions, i.e., dynamical systems on
$\mathbf{M}$, and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

    1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean subalgebra of
$\operatorname{\mathtt{Set}}(M\times X,2)$ such that for every
$L\in\operatorname{\mathscr{L}}(X)$ there exists a finite $\mathbf{M}$–action
$\mathbf{S}$, a homomorphism
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{S})$ and
$L^{\prime}\in\operatorname{\mathtt{Set}}(S,2)$ such that $L^{\prime}\circ
h=L$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under translations. That is, if
$L\in\operatorname{\mathscr{L}}(X)$ and $m\in M$ then
$mL\in\operatorname{\mathscr{L}}(X)$, where $mL(n,x)=L(m\cdot n,x)$, $(n,x)\in
M\times X$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of $\mathbf{M}$–actions
$h:M\times Y\to M\times X$ (i.e., $h(m\cdot(n,y))=m\cdot h(n,y)$) and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.

  5. (5)

(cf. [37]) A one–to–one correspondence between pseudovarieties of semigroups
with infinite exponentiation and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

    1. i)

$\operatorname{\mathscr{L}}(X)$ is a Boolean subalgebra of
$\operatorname{\mathtt{Set}}(X^{+}\cup X^{(\infty)},2)$ such that for every
$L\in\operatorname{\mathscr{L}}(X)$ there exists a finite semigroup with
infinite exponentiation $\mathbf{S}$, a homomorphism
$h\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{S})$ and
$L^{\prime}\in\operatorname{\mathtt{Set}}(S,2)$ such that $L^{\prime}\circ
h=L$.

    2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives and
infinite exponentiation. That is, if $L\in\operatorname{\mathscr{L}}(X)$ and
$u\in X^{+}\cup X^{(\infty)}$ then
${}_{u}L,L_{u},L^{\omega}\in\operatorname{\mathscr{L}}(X)$, where
${}_{u}L(w)=L(wu)$, $L_{u}(w)=L(uw)$ and $L^{\omega}(w)=L(w^{\omega})$, $w\in
X^{+}\cup X^{(\omega)}$.

    3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of $\mathsf{T}$–algebras
$h:Y^{+}\cup Y^{(\infty)}\to X^{+}\cup X^{(\infty)}$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

In the next example we obtain an Eilenberg–type correspondence for any variety
of ordered algebras for a given type $\operatorname{\tau}$ such that each
function symbol in $\operatorname{\tau}$ has a finite arity.

######  Example 3.9 (cf. Example 2.7).

Let $\operatorname{\tau}$ be a type of algebras where each function symbol
$g\in\operatorname{\tau}$ has arity $n_{g}\in\mathbb{N}$ and let $K$ be a
variety of ordered algebras of type $\operatorname{\tau}$. Consider the case
$\mathcal{D}=\operatorname{\mathtt{Poset}}$, $\mathcal{D}_{0}=$ finite
discrete posets, $\mathscr{E}=$ surjections, $\mathscr{M}=$ embeddings and let
$\mathsf{T}_{K}$ be the monad such that for every
$\mathbf{X}=(X,\leq)\in\operatorname{\mathtt{Poset}}$,
$T_{K}\mathbf{X}:=(T_{K}X,\leq_{T_{K}X})$ is the underlying poset of the free
ordered algebra in $K$ on $\mathbf{X}$ generators (see [13, Proposition 1]).
We have that $\operatorname{\mathtt{AlgCDL}}$ is dual to
$\operatorname{\mathtt{Poset}}$, so we can consider
$\mathcal{C}=\operatorname{\mathtt{AlgCDL}}$,
$\mathcal{C}_{0}=\operatorname{\mathtt{CABA}}_{f}$. In this case, we get a
one–to–one correspondence between pseudovarieties of ordered algebras in $K$
and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

  1. i)

$\operatorname{\mathscr{L}}(X)$ is a distributive sublattice of
$\operatorname{\mathtt{Poset}}(T_{K}X,\mathbf{2}_{c})\cong\operatorname{\mathtt{Set}}(T_{K}X,2)$
of subsets of $T_{K}X$ such that for every $L\in\operatorname{\mathscr{L}}(X)$
there exists a finite ordered algebra $\mathbf{A}$ in $K$, a morphism
$h\in\operatorname{Alg}(\mathsf{T}_{K})(\mathbf{T_{K}X},\mathbf{A})$ and
$L^{\prime}\in\operatorname{\mathtt{Poset}}(A,\mathbf{2}_{c})$ such that
$L=L^{\prime}\circ h$. Here $\mathbf{2}_{c}\in\operatorname{\mathtt{Poset}}$
is the two–element chain.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under derivatives with respect to
the type $\operatorname{\tau}$. That is, for every $g\in\operatorname{\tau}$
of arity $n_{g}$, every $1\leq i\leq n_{g}$, every $t_{j}\in T_{K}X$, $1\leq
j<n_{g}$, and every $L\in\operatorname{\mathscr{L}}(X)$ we have that
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathscr{L}}(X)$ where
$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}\in\operatorname{\mathtt{Set}}(T_{K}X,2)$
is defined as

$L^{(i)}_{(g,t_{1},\ldots,t_{n_{g}-1})}(t)=L(g(t_{1},\ldots,t_{i-1},t,t_{i},\ldots,t_{n_{g}-1}))$

$t\in T_{K}X$. That is, for every function symbol $g\in\operatorname{\tau}$ we
get $n_{g}$ kinds of derivatives.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of
$\mathsf{T}_{K}$–algebras $h:T_{K}Y\to T_{K}X$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 3.10 ([28, Theorem 5.8] cf. Example 2.8).

From the previous example we can obtain Eilenberg–type correspondences for
pseudovarieties of ordered semigroups, pseudovarieties of ordered monoids,
pseudovarieties of ordered groups, and so on. For instance, for the case of
pseudovarieties of ordered monoids we can consider the type
$\operatorname{\tau}=\\{e,\cdot\\}$ where $e$ is a nullary function symbol,
$\cdot$ is a binary function symbol and $K$ is the variety of ordered monoids.
Then we get a one–to–one correspondence between pseudovarieties of ordered
monoids and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

  1. i)

$\operatorname{\mathscr{L}}(X)$ is a distributive sublattice of the
distributive lattice $\operatorname{\mathtt{Set}}(X^{*},2)$ of subsets of
$X^{*}$, i.e., every element in $\operatorname{\mathscr{L}}(X)$ is a language
on $X$, such that every $L\in\operatorname{\mathscr{L}}(X)$ is a regular
language.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{*}$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, homomorphism of monoids $h:Y^{*}\to
X^{*}$ and $L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 3.11 (cf. [31, Théorème III.1.1.] and Example 2.9).

Let $\mathbb{K}$ be a finite field. Consider the case
$\mathcal{D}=\operatorname{\mathtt{Vec}_{\mathbb{K}}}$, $\mathcal{D}_{0}=$
finite $\mathbb{K}$–vector spaces, $\mathscr{E}=$ surjections and
$\mathscr{M}=$ injections. We have that
$\operatorname{\mathtt{StVec}_{\mathbb{K}}}$ is dual to
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}$, so we can consider
$\mathcal{C}=\operatorname{\mathtt{StVec}_{\mathbb{K}}}$ and
$\mathcal{C}_{0}=$ finite $\mathbb{K}$–vector spaces. For every set $X$ denote
by $\mathsf{V}(X)$ the $\mathbb{K}$–vector space with basis $X$. Consider the
monad $T(\mathsf{V}(X))=\mathsf{V}(X^{*})$, where $X^{*}$ is the free monoid
on $X$. Then we get a one–to–one correspondence between pseudovarieties of
$\mathbb{K}$–algebras and operators $\operatorname{\mathscr{L}}$ on
$\operatorname{\mathtt{Set}}_{f}$ such that for every
$X\in\operatorname{\mathtt{Set}}_{f}$:

  1. i)

$\operatorname{\mathscr{L}}(X)$ is a $\mathbb{K}$–vector space which is a
subspace of
$\operatorname{\mathtt{Vec}_{\mathbb{K}}}(\mathsf{V}(X^{*}),\mathbb{K})$ such
that every element $S$ in $\operatorname{\mathscr{L}}(X)$ is a recognizable
series on $X$, i.e., there exists a $\mathbb{K}$–algebra morphism
$h:\mathbf{TX}\to\mathbf{A}$, with $\mathbf{A}$ finite, and
$S^{\prime}\in\operatorname{\mathtt{Vec}_{\mathbb{K}}}(A,\mathbb{K})$ such
that $S^{\prime}\circ h=S$.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $v\in\mathsf{V}(X^{*})$
then ${}_{v}L,L_{v}\in\operatorname{\mathscr{L}}(X)$, where ${}_{v}L(w)=L(wv)$
and $L_{v}(w)=L(vw)$, $w\in\mathsf{V}(X^{*})$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, $\mathbb{K}$–linear map
$h:\mathsf{V}(Y^{*})\to\mathsf{V}(X^{*})$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L\circ
h\in\operatorname{\mathscr{L}}(Y)$.∎

######  Example 3.12 ([29, Theorem 5 (iii)] cf. Example 2.10).

Consider the case $\mathcal{D}=\operatorname{\mathtt{JSL}}$,
$\mathcal{D}_{0}=$ finite free join semilattices, i.e.,
$\mathcal{D}_{0}=\\{(\mathcal{P}(X),\cup)\mid
X\in\operatorname{\mathtt{Set}}_{f}\\}$, where $\mathcal{P}$ is the powerset
operator, $\mathscr{E}=$ surjections and $\mathscr{M}=$ injections. We have
that $\operatorname{\mathtt{StJSL}}$ is dual to $\operatorname{\mathtt{JSL}}$,
so we can consider $\mathcal{C}=\operatorname{\mathtt{StJSL}}$ and
$\mathcal{C}_{0}=\\{\operatorname{\mathtt{JSL}}((\mathcal{P}(X),\cup),2)\mid
X\in\operatorname{\mathtt{Set}}_{f}\\}$. Let $\mathsf{T}$ be the monad on
$\operatorname{\mathtt{JSL}}$ such that $T(S,\lor)$ is the free idempotent
semiring on $(S,\lor)\in\operatorname{\mathtt{JSL}}$. Then we get a one–to–one
correspondence between pseudovarieties of idempotent semirings and operators
$\operatorname{\mathscr{L}}$ on $\operatorname{\mathtt{Set}}_{f}$ such that
for every $X\in\operatorname{\mathtt{Set}}_{f}$:

  1. i)

$\operatorname{\mathscr{L}}(X)$ is a join subsemilattice of
$\operatorname{\mathtt{Set}}(X^{*},2)$ such that every
$L\in\operatorname{\mathscr{L}}(X)$ is a regular language. In particular,
$\operatorname{\mathscr{L}}(X)$ is closed under union.

  2. ii)

$\operatorname{\mathscr{L}}(X)$ is closed under left and right derivatives.
That is, if $L\in\operatorname{\mathscr{L}}(X)$ and $x\in X$ then
${}_{x}L,L_{x}\in\operatorname{\mathscr{L}}(X)$, where ${}_{x}L(w)=L(wx)$ and
$L_{x}(w)=L(xw)$, $w\in X^{*}$.

  3. iii)

$\operatorname{\mathscr{L}}$ is closed under morphic preimages. That is, for
every $Y\in\operatorname{\mathtt{Set}}$, semiring homomorphism
$h:\mathcal{P}_{f}(Y^{*})\to\mathcal{P}_{f}(X^{*})$ and
$L\in\operatorname{\mathscr{L}}(X)$, we have that $L^{\sharp}\circ
h\circ\eta_{Y^{*}}\in\operatorname{\mathscr{L}}(Y)$ (see Example 2.10).∎

######  Remark 3.13.

Note that Eilenberg–type correspondences for pseudovarieties of
$\mathbb{K}$–algebras and idempotent semirings can also be obtained from
Example 3.6.

##  4\. Local Eilenberg–type correspondences

In this section, we provide abstract versions of local Eilenberg–type
correspondences for local (pseudo)varieties of $\mathsf{T}$–algebras. Local
Eilenberg–type correspondences have been studied in [3, 22]. The main idea of
local Eilenberg–type correspondences is to work with a fixed alphabet, which
in our notation reduces to consider the case in which the category
$\mathcal{D}_{0}$ has only one object, say $X$. In order to do this, the kind
of algebras considered in this local version are algebras that are generated
by the object $X$ in the following sense.

Let $\mathcal{D}$ be a category, $\mathsf{T}$ a monad on $\mathcal{D}$,
$\mathscr{E}/\mathscr{M}$ a factorization system on $\mathcal{D}$ and
$X\in\mathcal{D}$. An algebra $\mathbf{A}\in\operatorname{Alg}(\mathsf{T})$ is
$X$–generated if
$\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})\cap\mathscr{E}$ is
nonempty.

We have that $\mathscr{E}$–quotients of $X$–generated $\mathsf{T}$–algebras
are $X$–generated, but this property does not hold in general for
$\mathscr{M}$–subalgebras and products. Thus, we will restrict our attention
to $X$–generated $\mathscr{M}$–subalgebras, i.e., $\mathscr{M}$–subalgebras
that are $X$–generated, and subdirect products. The latter are defined as
follows.

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathscr{E}/\mathscr{M}$ a proper factorization system on
$\mathcal{D}$ such that $T$ preserves the morphisms in $\mathscr{E}$. Let
$X\in\mathcal{D}$ and let $\mathbf{A}_{i}$ be an $X$–generated
$\mathsf{T}$–algebra with
$e_{i}\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A}_{i})\cap\mathscr{E}$,
$i\in I$. We define the subdirect product of the family
$\\{(\mathbf{A}_{i},e_{i})\\}_{i\in I}$ as the $X$–generated
$\mathscr{M}$–subalgebra $\mathbf{S}$ of $\prod_{i\in I}\mathbf{A}_{i}$
described in the following commutative diagram:

$TX$$\prod_{i\in I}A_{i}$$A_{j}$$S$$e_{j}$$e_{e}\ $$\pi_{j}$$e$$m_{e}$

where $e$ is obtained from the morphisms $e_{j}$, $j\in I$, and the universal
property of the product $\prod_{i\in I}\mathbf{A}_{i}$ and $e=m_{e}\circ
e_{e}$ is the factorization of $e$. We say that the subdirect product
$\mathbf{S}$ defined above is finite if $I$ is a finite set.

To obtain local versions of Eilenberg–type correspondences, the concept of
(pseudo)variety used is: classes of (finite) $X$–generated
$\mathsf{T}$–algebras closed under $\mathscr{E}$–quotients, $X$–generated
$\mathscr{M}$–subalgebras and (finite) subdirect products. We state the two
corresponding local versions in the rest of this section. Proofs are made in a
similar way by using local versions of Birkhoff’s theorem for (finite)
$\mathsf{T}$–algebras.

###  4.1. Eilenberg–type correspondence for local varieties of
$\mathsf{T}$–algebras

In this subsection, we provide Eilenberg–type correspondences for local
varieties of $\mathsf{T}$–algebras. For this purpose, as in Section 2, we
first provide a local version of Birkhoff’s theorem.

We fix a complete category $\mathcal{D}$, a monad $\mathsf{T}=(T,\eta,\mu)$ on
$\mathcal{D}$, $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$ and $X\in\mathcal{D}$. We will use the following assumptions:

  1. (b1)

The factorization system $\mathscr{E}/\mathscr{M}$ is proper.

  2. (b2)

The free $\mathsf{T}$–algebra $\mathbf{TX}=(TX,\mu_{X})$ is projective with
respect to $\mathscr{E}$ in $\operatorname{Alg}(\mathsf{T})$.

  3. (b3)

$T$ preserves morphisms in $\mathscr{E}$.

  4. (b4)

There is, up to isomorphism, only a set of $\mathsf{T}$–algebra morphisms in
$\mathscr{E}$ with domain $\mathbf{TX}$.

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, and $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$. Assume (b1) and (b3). Let $X\in\mathcal{D}$. A class $K$ of
$X$–generated $\mathsf{T}$–algebras is a local variety of $X$–generated
$\mathsf{T}$–algebras if it is closed under $\mathscr{E}$–quotients,
$X$–generated $\mathscr{M}$–subalgebras and subdirect products.

Let $\mathcal{D}$ be a category, $\mathsf{T}$ a monad on $\mathcal{D}$,
$X\in\mathcal{D}$ and $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$. A local equational $\mathsf{T}$–theory on $X$ is a
$\mathsf{T}$–algebra morphism
$TX\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}$
in $\mathscr{E}$ such that for any
$g\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{TX})$ there exists
$g^{\prime}\in\operatorname{Alg}(\mathsf{T})(\mathbf{Q_{X}},\mathbf{Q_{X}})$
such that the following diagram commutes:

$TX$$Q_{X}$$TX$$Q_{X}$$e_{X}$$e_{X}$$\forall g$$g^{\prime}$

Note that, in the setting of Example 2.1, a local equational
$\mathsf{T}$–theory
$TX\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}$
on $X$ is characterized, up to isomorphism, by its kernel $\ker(e_{X})$. In
this case, the property of $e_{X}$ being a local equational
$\mathsf{T}$–theory is exactly the property of $\ker(e_{X})$ being a fully
invariant congruence of $\mathbf{TX}$ [16, Definition II.14.1]. This
generalizes the definition of an equational theory over $X$ in [16, Definition
II.14.9] to a categorical level.

Given a local equational $\mathsf{T}$–theory
$TX\overset{e_{X}}{\operatorname{\longrightarrow\mkern-15.0mu\rightarrow}}Q_{X}$
on $X$ and an $X$–generated $\mathsf{T}$–algebra $\mathbf{A}$, we say that
$\mathbf{A}$ satisfies $e_{X}$, denoted as $\mathbf{A}\models e_{X}$, if every
morphism $f\in\operatorname{Alg}(\mathsf{T})(\mathbf{TX},\mathbf{A})$ factors
through $e_{X}$. We denote by $\operatorname{Mod}(e_{X})$ the $X$–generated
models of $e_{X}$, that is:

$\operatorname{Mod}(e_{X})=\\{\mathbf{A}\in\operatorname{Alg}(\mathsf{T})\mid\text{
$\mathbf{A}$ is $X$--generated and $\mathbf{A}\models e_{X}$}\\}.$

A class $K$ of $X$–generated $\mathsf{T}$–algebras is defined by $e_{X}$ if
$K=\operatorname{Mod}(e_{X})$.

######  Theorem 5 (Local Birkhoff’s theorem for $\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, $X\in\mathcal{D}$ and $\mathscr{E}/\mathscr{M}$ a factorization
system on $\mathcal{D}$. Assume (b1) to (b4). Then a class $K$ of
$X$–generated $\mathsf{T}$–algebras is a local variety of $X$–generated
$\mathsf{T}$–algebras if and only if is defined by a local equational
$\mathsf{T}$–theory on $X$. Additionally, local varieties of $X$–generated
$\mathsf{T}$–algebras are in one–to–one correspondence with local equational
$\mathsf{T}$–theories on $X$.∎

Let $\mathcal{C}$ be a category, $\mathsf{B}$ a comonad on $\mathcal{C}$,
$Y\in\mathcal{C}$ and $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{C}$. A local coequational $\mathsf{B}$–theory on $Y$ is a
$\mathsf{B}$–coalgebra morphism $S_{Y}\xhookrightarrow{m_{Y}}BY$ in
$\mathscr{M}$ such that for any
$g\in\operatorname{Coalg}(\mathsf{B})(\mathbf{BY},\mathbf{BY})$ there exists
$g^{\prime}\in\operatorname{Coalg}(\mathsf{B})(\mathbf{S_{Y}},\mathbf{S_{Y}})$
such that the following diagram commutes:

$S_{Y}$$BY$$S_{Y}$$BY$$m_{Y}$$m_{Y}$$\forall g$$g^{\prime}$

With the previous definition, Theorem 5 and duality, we have the following.

######  Proposition 6 (Abstract Eilenberg–type correspondence for varieties of
$X$–generated $\mathsf{T}$–algebras).

Let $\mathcal{D}$ be a complete category, $\mathsf{T}$ a monad on
$\mathcal{D}$, $\mathscr{E}/\mathscr{M}$ a factorization system on
$\mathcal{D}$ and $X\in\mathcal{D}$. Assume (b1) to (b4). Let $\mathcal{C}$ be
a category that is dual to $\mathcal{D}$, $Y$ the corresponding dual object of
$X$ and let $\mathsf{B}$ be the comonad on $\mathcal{C}$ that is dual to
$\mathsf{T}$ which is defined as in Proposition 1. Then there is a one–to–one
correspondence between local varieties of $X$–generated $\mathsf{T}$–algebras
and local coequational $\mathsf{B}$–theories on $Y$.

######  Example 4.1.

By fixing an object $X\in\mathcal{D}_{0}$, we can get corresponding local
versions of the Eilenberg–type correspondences showed in subsection 2.2 for
varieties of $X$–generated $\mathsf{T}$–algebras. For example, the local
version of Example 2.4 reads as follows: There is a one–to–one correspondence
between varieties of $X$–generated monoids and subalgebras
$\mathbf{S}\in\operatorname{\mathtt{CABA}}$ of the complete atomic Boolean
algebra $\operatorname{\mathtt{Set}}(X^{*},2)$ such that:

  1. i)