Under consideration for publication in Math. Struct. in Comp. Science

On Varieties and Covarieties in a Category

J I Ř Í A D Á M E K^{1}^{†} and H A N S – E. P O R S T^{2}^{‡}

1Department of Theoretical Computer Science, Technical University of Braunschweig, 38023 Braunschweig, Germany. 2Department of Mathematics, University of Bremen, 28344 Bremen, Germany.

Received 11 February 2002

A concept of equation morphism is introduced for every endofuctor F of a cocomplete category C. Equationally defined classes of F –algebras for which free algebras exist are called varieties. Every variety is proved to be monadic over C, and conversely, every monadic category is equivalent to a variety. And the Birkhoff Variety Theorem is proved for “Set–like” categories. By dualizing, we arrive at a concept of coequation such that covarieties, i.e., coequationally specified classes of coalgebras with cofree objects, precisely correspond to comonadic categories. Natural examples of covarieties are presented.

Introduction

Our paper whose extended abstract has appeared in (Adámek and Porst 2001) is devoted to a concept of variety of algebras in an arbitrary category C. The basic examples for C = Set include

(1) all finitary varieties of classical universal algebra (groups, lattices, etc.),

(2) all infinitary varieties of bounded arities (e.g., Boolean σ–algebras, σ–complete lattices), and

(3) those infinitary varieties of unbounded arities that have free algebras, e.g., complete semilattices and compact Hausdorff spaces. It is well–known that finitary varieties precisely correspond to finitary monads over

Set (see (Lawvere 1963) or (Manes 1976)) — and it is a folklore that this generalizes to (some concept of) infinitary varieties and arbitrary monads over Set. The result that we consider surprising is that such a correspondence can be formulated naturally over every cocomplete category C. Recall from (Adámek 1974) that for every endofunctor F preserving colimits of ω–chains a free F –algebra X^{♯} on an arbitrary object X can be

† Support under Project SMS No. 34-99141-301 is gratefully acknowledged. ‡ Hospitality of the Department of Mathematics at the University of South Africa and the University of

Stellenbosch is acknowledged, where this author had the opportunity to work on this project during extended stays.

described as an ω–colimit of the following ω–chain (that mimics the iterative construction of the set of all terms in variables from X):

0 → F 0 + X → F (F 0 + X) + X → ⋯

If F does not preserve ω–colimits, we might iterate further in order to obtain a free algebra X^{♯}: on limit steps we form a colimit of the previous chain, and isolated steps take W_{i} and answer with W_{i+1} = F W_{i} + X (i ∈ Ord). If the connecting morphism W_{i} → W_{i+1} is an isomorphism for some i, then W_{i} = X^{♯} is a free F –algebra. Here, however, we do not restrict ourselves to endofunctors having free algebras: we simply work instead with the whole transfinite construction (W_{i})_{i∈Ord}. It has the following property: for every F –algebra A and every morphism f: X → A (interpretation of variables) we obtain a unique cocone f_{i}^{♯}: W_{i} → A of the above chain such that the second component of f_{i+1}^{♯}: F W_{i} + X → A is f (for all ordinals i). We can think of f_{i}^{♯} as computation of terms of depth i.

This enables us to define an equation as a parallel pair of morphisms whose codomain is one of these W_{i}’s:

U ⇉_{v}^{u} W_{i} (i ∈ Ord)

An algebra A is said to satisfy that equation provided that for every morphism f: X → A we have f_{i}^{♯}u = f_{i}^{♯}v. And a full subcategory V ↪ Alg(F) of the category of all F –algebras is called a variety if

i. V is specified by a class of equations, and ii. V–free algebras exist, i.e., the natural forgetful functor V → C has a left adjoint.

This includes e.g. complete semilattices over Set (since free complete semilattices are the power–sets) but not complete lattices (where a free object on 3 generators does not exist—see (Hales 1964)). For any cocomplete category C, varieties are proved to be precisely the monadic categories over C.

The above concept of equation has been, for C = Set, introduced in (Adámek 1983). A closely related concept, for C arbitrary, has been studied by Jan Reiterman in his dissertation, see also (Reiterman 1978), where quotient chains of the above chain (W_{i}) are considered as equations.

Functors F such that every object generates a free F –algebra are called varietors in (Adámek and Trnková 1990). Although varieties are defined, in general, without this assumption, one can say more about algebras over varietors. E.g., one can prove a generalization of the Birkhoff Variety Theorem for all varietors on Set (see (Adámek 1983, Thm 5D5)). In the present paper we prove such a theorem for every complete, regularly cowellpowered category with regular factorizations; a similar result can be found in the above mentioned paper of Jan Reiterman. We can also work with coequalizers c: W_{i} → C of the above pairs u, v rather than the pairs per se. Then to satisfy u = v is the same as to be injective w.r.t. c. A generalization of varieties using the concept of injectivity has been studied in (Herrlich and Ringel 1972) and (Banaschewski and Herrlich 1976). The generalization of Birkhoff’s Variety Theorem requests a study of limits and colimits that we undertake, too.

All these considerations dualize immediately to coalgebras over an endofunctor F of C, since the category Coalg(F) of coalgebras is dual to Alg(F^{op}). Thus, we obtain a general concept of coequation and coequationally defined classes of coalgebras. In case of a covarietor F on Set, a coequation is simply an element of a cofree coalgebra, which is the concept studied in (Gumm 1999). In the present paper we show that this is just a special case of a very general concept: whenever C is a complete category, then comonadic categories over C are precisely the covarieties. And for C = Set and for covarietors F (which includes, e.g., all bounded functors) the Birkhoff Covariety Theorem is proved to hold — thus our concept of covariety is identical with that of (Rutten 2000) and with other concepts in the literature. For example, with covarieties defined by means of projectivity (i.e., a dualization of the above mentioned results of Banaschewski and Herrlich) in (Gumm and Schröder 1998), (Kurz 2000) and (Awoday and Hughes 2000). Covarieties satisfying additional assumptions (i.e., a concept not equivalent to that studied in the present paper) have been studied e.g. in (Cîrstea 2000) and (Ghani et al. 2001).

1. Algebras and Coalgebras

1.1 Standing assumption Throughout the paper C denotes a category and F an endofunctor of C. Our main interest will be in C = Set or Set^{op}, but in general nothing is assumed about C. The dual of a functor G: C → D, i.e., the functor C^{op} → D^{op} acting on objects and morphisms as G, will be denoted by G^{op}.

1.2 Category Alg(F) of F –algebras: Objects of Alg(F), called F –algebras, are pairs (C, α_{C}) where C is an object of C and α_{C}: F C → C is a morphism. Morphisms f: (C, α_{C}) → (D, α_{D}) of Alg(F), called F –algebra homomorphisms, are morphisms f: C → D of C such that f ∘ α_{C} = α_{D} ∘ F f. Composition and identities in Alg(F) are those of C. We denote by

U_{F} : Alg(F) → C ^{†}

the canonical forgetful functor (C, α_{C}) ↦ C.

1.3 Category Coalg(F) of F –algebras: Objects of Coalg(F), called F –coalgebras, are pairs (C, α_{C}) where C is an object of C and α_{C}: C → F C is a morphism. Morphisms f: (C, α_{C}) → (D, α_{D}) of Coalg(F), called F –coalgebra homomorphisms, are morphisms f: C → D of C such that F f ∘ α_{C} = α_{D} ∘ f. Composition and identities are again those of C. We denote by

F U: Coalg(F) → C ^{†}

the canonical forgetful functor (C, α_{C}) ↦ C.

1.4 Lemma For any functor F: C → C the following hold:

1) Coalg(F) = (Alg(F^{op})^{op}), i.e., F –coalgebras from the dual of the category of F^{op}– algebras;

2) _{F} U = (U_{F^{op}})^{op}.

† Whenever confusion is unlikely to arise we will omit the subscript F.

1.5 Examples (1) Algebras on one binary and one nullary operation are F –algebras where F is the endofunctor of Set given by F X = (X × X) + 1. F –coalgebras, i.e., sets C equipped with a function α_{C}: C → C × C + 1, can be viewed as dynamic systems with two inputs and deadlocks. That is, C is the set of all states, and for every state c ∈ C either α_{C}(c) is the pair of states which are the reactions of c to the two inputs, respectively, or c is a deadlock state. Morphisms are the functions preserving reaction to inputs and preserving and reflecting deadlock.

(2) Finitary universal algebras of a given (one–sorted) signature Ω = (Ω_{n})_{n∈ℕ}, where Ω_{n} is the set of all n–ary operation symbols, can be viewed as F –algebras for the following endofunctor F = F_{Ω} of Set: F_{Ω} assigns to a set X the set ∑_{n∈ℕ} Ω_{n} × X^{n}. Correspondingly F_{Ω} assigns to a map f: X → Y the map ∑_{n∈ℕ} Ω_{n} × f^{n}, i.e., the map ∑_{n∈ℕ} Ω_{n} × X^{n} → ∑_{n∈ℕ} Ω_{n} × Y^{n} mapping a pair (ω, (x_{1}, …, x_{n})) to the pair (ω, (fx_{1}, …, fx_{n})). F_{Ω}–coalgebras can be viewed as dynamical systems with several inputs and side effects. This has been demonstrated in (Rutten 2000).

(3) Many–sorted algebras (of a given S–sorted signature Ω) can, analogously, be described as F_{Ω}–algebras for the corresponding endofunctors F_{Ω} of Set^{S}. For example, the category of multigraphs and homomorphisms is the category of 2-sorted algebras of sorts v (vertices) and e (edges) with two unary operations target, source: e → v. This is also a category of coalgebras (for the endofunctor F on Set × Set given by F (X_{v}, X_{e}) = (1, X_{v} × X_{v}) )—in fact, every category of unary algebras is a category of coalgebras as well.

(4) Denote by

P: Set → Set

the power–set functor. P–algebras are sets A endowed with an operation α: PA → A. For example, a complete join semilattice is described by α: M ↦ ∨M (see Example 3.5 below for an equational presentation of complete join semilattices as P–algebras). A P–coalgebra can be considered as precisely a (notation of a) directed graph (i.e., a binary relation) on a set A: given α: A → PA, then α(x) is the set of all elements related to x. Homomorphisms of P–coalgebras are, however, more specialized than the usual graph homomorphisms: for coalgebras A_{i} expressed by graphs R_{i} ⊆ A_{i} ×A_{i} (i= 1,2) a homomorphism of P–coalgebras is a function f: A_{1} → A_{2} such that (a) f is a graph homomorphism, i.e., xR_{1}y implies f(x)R_{2}f(y) and (b) given elements x ∈ A_{1} and y ∈ A_{2} with f(x)R_{2}y there exists x′ ∈ A_{1} with xR_{1}x′ and f(x′) = y.

(5) Denote by

P_{fin}: Set → Set

the finite–power–set functor. P_{fin}–coalgebras are the directed graphs of finite out– degree, with homomorphisms as defined in (4) above.

(6) Labelled transition systems, important both in modal logic and in process algebra, are naturally formalized as coalgebras. For a given set L of labels, a labelled transition system is a set A (of states) together with a binary relation →^{l} on A for every label l ∈ L. Put

F = P(− × L): Set → Set.

Every labelled transition system A defines an F –coalgebra by

α_{A}: A → P(A × L), x ⟼ {(y, l) ∈ A × L; x →^{l} y}.

This gives rise to an equivalence between Coalg(F) and the category of labelled transition systems and system morphisms defined analogously to example (4) above. If L = 1 we obtain the above case, F = P, and sometimes speak about nonlabelled transition systems.

(7) k–algebras Denote by Vec_{k} the category of vector spaces over a field k and linear functions. Recall that a k–algebra is a vector space A together with a bilinear multiplication, i.e., a linear function A ⊗ A → A, which is associative, and a unit e (which we consider as the corresponding morphism e: k → A) of the multiplication (see (Sweedler 1969)). Thus, k–algebras are F –algebras (satisfying additional axioms) of the functor F: Vec_{k} → Vec_{k} given by

F A = (A ⊗ A) + k.

1.6 Remark The above functors F_{Ω} are called polynomial. They can be introduced, more generally, on every category C with finite products and arbitrary coproducts as the smallest class of endofunctors containing Id_{C} and closed under finite products and all coproducts.

2. Free algebras and cofree coalgebras

2.1 Example For polynomial endofunctors F_{Ω} on Set, the concept of free algebra X^{♯} on a set X of generators is well known. We can describe it either recursively as X^{♯} = ∪_{i<ω}X_{i}^{♯} where

X_{0}^{♯} = Ω_{0} + X
= F_{Ω}∅ + X terms of depths 0 are nullary operations and variables
X_{i+1}^{♯} = {(ω, t_{0}, …, t_{n−1}) | ω ∈ Ω_{n}, t_{0}, …, t_{n−1} ∈ X_{i}^{♯}} + X
= F_{Ω}X_{i}^{♯} + X terms of depths i+1

Or directly: X^{♯} is the algebra of all finite “properly” labelled trees. “Properly” means that a node with n > 0 children is labelled by an n-ary operation, and a leaf is labelled by a variable or a nullary operation. We have the universal arrow η_{X}: X → X^{♯}, embedding X into X^{♯}.

2.2 Remark A free F -algebra on an object X (of “variables”) of C can be defined as a pair consisting of an F -algebra

F X^{♯} ⟶^{φ_{X}} X^{♯} and a morphism η_{X}: X → X^{♯}

with the universal property that given an F -algebra (C, α_{C}) and a morphism f: X → C of C there exists a unique F -homomorphism f^{♯} extending f, i.e., such that the following diagram

\xymatrix{F X^{♯} \ar[r]^{φ_{X}} \ar[d]_{F f^{♯}} & X^{♯} \ar[d]^{f^{♯}} & X \ar[l]^{η_{X}} \ar[dl]^{f} \\ F C \ar[r]^{α_{C}} & C}

commutes. In other words, η_{X} is a universal arrow of the forgetful functor U: Alg(F) → C.

In particular, if X = 0 (an initial object of C) then 0^{♯} is an initial F –algebra. Recall that by the famous Lambek’s Lemma (Lambek 1968) α_{0^{♯}}: F 0^{♯} → 0^{♯} is an isomorphism.

2.3 Lemma Let C have binary coproducts. An initial F (−) + X–algebra is equal to a free F –algebra on X.

2.4 Corollary For a free F –algebra X^{♯} one has X^{♯} ≃ F X^{♯} + X

This is Lambek’s Lemma applied to F_{X} = F (−) + X.

It is good to have a name for endofunctors F such that every object of C admits a free F –algebra, that is, such that U has a left adjoint.

2.5 Definition ((Adámek and Trnková 1990)) An endofunctor F: C → C is called a varietor provided that a free F –algebra exists on every C–object.

2.6 Examples (1) Polynomial endofunctors on Set are varietors.

(2) The finite–power–set endofunctor of Set is a varietor. This follows from the fact that it is finitary, i.e., preserves filtered colimits. Also the countable–power–set endofunctor of Set is a varietor because it preserves ℵ_{1}–filtered colimits. We will see below that every λ–accessible endofunctor of Set, i.e., every functor preserving λ–filtered colimits (for some infinite cardinal λ) is a varietor.

(3) The power–set endofunctor P of Set is not a varietor since an initial P–algebra does not exist.

(4) Generalizing (1) above let C have colimits and finite products such that colimits of ω–chains commute with finite products. Then every polynomial endofunctor F_{Ω} on C is a varietor. In fact, it is easy to see that, for all Ω, F_{Ω} preserves colimits of ω–chains. And then free algebras can be obtained by the following

2.7 Finitary Free-Algebra Construction (see (Adámek 1974)): This is an application of the famous construction of an initial F-algebra (the free F -algebra on 0, an initial object of C) as a colimit of the chain

0 ⟶^{!} F 0 ⟶^{F!} F^{2}0 ⟶^{F^{2}0} F^{3}0 ⋯

to the functor F_{X} = F (−) + X (see Lemma 2.3 above). Let C have countable colimits. Given an object X in C we define an ω–chain X_{i}^{♯}(i < ω) as follows:

0 ⟶^{!} F 0 + X ⟶^{F!+X} F (F 0 + X) + X ⟶^{F (F!+X)+X} F (F (F 0 + X) + X) + X ⋯

That is First step X_{0}^{♯} = 0, X_{1}^{♯} = F 0+X with x_{0,1}^{♯} the unique morphism 0 ⟶^{!} F 0 + X, Induction step X_{i+1}^{♯} = F X_{i}^{♯} + X and x_{i+1,j+1}^{♯} = F x_{i,j}^{♯} + X for all i ≤ j.

Lemma Let C be cocomplete and F preserve colimits of ω–chains. Then for every object X of C,

X^{♯} = colim_{i<ω}X_{i}^{♯}

is a free F –algebra on X.

More detailed: let (X_{i}^{♯} ⟶^{x_{i}} X^{♯}) be a colimit cocone. Since F (−) + X preserves that colimit we have a unique morphism

φ_{X}: F X^{♯} + X → X^{♯} with φ_{X} ∘ (F x_{i} + X) = x_{i+1}

The two components η_{X}: X → X^{♯} and α_{X}: F X^{♯} → X^{♯} of φ_{X} form a free F -algebra on X.

Proof. For every F -algebra (C, α_{C}) and any morphism (“assignment to variables”) f: X → C define a cocone of the above chain (computation of terms) recursively as follows:

f_{0}^{♯} =! and f_{i+1}^{♯} = [α_{C} ∘ F f_{i}^{♯}, f]

Then the (unique) factorization X_{i}^{♯} ⟶^{x_{i}} X^{♯} ⟶^{f^{♯}} C = f_{i}^{♯} of that cocone gives the (unique) homomorphism f^{♯}: (X^{♯}, α_{X}) → (C, α_{C}) with f = f^{♯} ∘ η_{X}.

2.8 Examples (1) For the endofunctor F Y = Y × Y + 1 (i.e., one constant and one binary operation) on Set, we know that the terms in X_{i}^{♯} are just the binary trees of depth ≤ i with leaves labelled in X +1. This corresponds precisely to the construction above.

(2) For the endofunctor F Y = Y^{ℕ} (i.e., one ω-ary operation) on Set we again might form the sets X_{i}^{♯} of terms, but here the colimit after ω steps does not give a free F -algebra, of course: we need ω_{1} steps of the following

2.9 Free-Algebra Construction (see (Adámek 1974) or (Adámek and Trnková 1990, IV.3.2)): Let C be a cocomplete category. For every endofunctor F on C and every object X (“of variables”) in C define a transfinite chain of objects X_{i}^{♯} (i any ordinal) and connecting morphisms

x_{i,j}^{♯}: X_{i}^{♯} → X_{j}^{♯} (i ≤ j)

by the following transfinite induction:

First step X_{0}^{♯} = 0, X_{1}^{♯} = F 0+X with x_{0,1}^{♯} the unique morphism 0 ⟶^{!} F 0 + X, Isolated step X_{i+1}^{♯} = F X_{i}^{♯} + X for all ordinals i, x_{i+1,j+1}^{♯} = F x_{i,j}^{♯} + X for all i ≤ j, Limit step X_{j}^{♯} = colim_{i<j}X_{i}^{♯} for all limit ordinals j with colimit cocone x_{i,j}^{♯}, i < j.

We say that the free algebra construction stops after k steps provided that x_{k,k+1}^{♯} is an isomorphism.

2.10 Lemma Let C be cocomplete and F preserve colimits of λ–chains. Then for every object X of C, X_{λ}^{♯} is a free F –algebra on X.

This is analogous to Lemma 2.7.

2.11 Computation of terms In classical universal algebra, where X_{i}^{♯} are the terms of depth < i over variables from X, we have the concept of computation of terms in an algebra A: for every interpretation of variables, i.e., every function f: X → A we extend f to a cocone f_{i}^{♯}: X_{i}^{♯} → A of the free–algebra construction by the well–known algebraic recursion. This is a special case of the following:

Let F be an endofunctor of a cocomplete category C. For every F –algebra (A, α_{A}) and every morphism f: X → A in C we define a cocone f_{i}^{♯}: X_{i}^{♯} → A of the free–algebra construction as follows: First step f_{0}^{♯}: 0 → A is the unique morphism. Isolated step Given f_{i}^{♯}: X_{i}^{♯} → A let

f_{i+1}^{♯}: F X_{i}^{♯} + X → A

have components F X_{i}^{♯} ⟶^{F f_{i}^{♯}} F A ⟶^{α_{A}} A and X ⟶^{f} A. Observe that the compatibility condition

f_{i}^{♯} = f_{i+1}^{♯} ∘ x_{i,i+1}^{♯}

is fulfilled (an easy proof by transfinite induction). Limit Step Given a limit ordinal i and given the cocone f_{j}^{♯}: X_{j}^{♯} → A, j < i, of the first i steps of the free–algebra construction, there is a unique

f_{i}^{♯}: colim_{j<i} X_{j}^{♯} → A

with the (obligatory) property f_{j}^{♯} = f_{i}^{♯} ∘ x_{ji}^{♯} for all j < i.

2.12 Lemma Homomorphisms of F –algebras preserve computation of terms, i.e., given a homomorphism h: (C, α_{C}) → (D, α_{D}) and an assignment of variables f: X → C then, for all ordinals i, (h ∘ f)_{i}^{♯} = h ∘ f_{i}^{♯}.

Proof. We proceed by transfinite induction on i. The case i = 0 is trivial since the domain of both sides is 0. The limit case is immediate from the universal property of colimits. In the isolated case we assume the above equation for i and derive

(h ∘ f)_{i+1}^{♯} = [α_{D} ∘ F (h ∘ f)_{i}^{♯}, h ∘ f]
= [α_{D} ∘ F h ∘ F f_{i}^{♯}, h ∘ f] by induction hypothesis
= [h ∘ α_{C} ∘ F f_{i}^{♯}, h ∘ f] since h is a homomorphism
= h ∘ [α_{C} ∘ F f_{i}^{♯}, f]
= h ∘ f_{i+1}^{♯}

2.13 Proposition If the free–algebra construction stops after k steps, then X_{k}^{♯} is a free F –algebra on X.

More detailed: Denoting the components of x_{k,k+1}^{−1} : F X_{k}^{♯} + X → X_{k}^{♯} by

α_{X}: F X_{k}^{♯} → X_{k}^{♯} and η_{X}: X → X_{k}^{♯}

respectively, these form a free F –algebra on X.

Proof. Let (C, α_{C}) be an F –algebra f: X → C a morphism. From the equation

f_{k}^{♯} = f_{k+1}^{♯} ∘ x_{k,k+1} = [α_{C} ∘ F f_{k}^{♯}, f] ∘ [α_{X}, η_{X}]^{−1}

it follows that f_{k}^{♯} is a homomorphism extending f. The uniqueness is easy to verify.

2.14 Definition ((Adámek and Trnková 1990)) A functor F: C → C with C cocomplete is called constructive varietor provided that its free algebra construction stops for each object X in C.

2.15 Remark A functor F is said to be accessible if it preserves, for some infinite cardinal λ, all λ–filtered colimits (we speak more precisely of λ–accessiblity, then). Accessible Setfunctors are precisely the bounded functors of (Kawahara and Mori 2000) as proved in (Adámek and Porst 2001). Since colimits of λ–chains are λ–filtered, we get the following

Corollary Every accessible endofunctor of a cocomplete category is a constructive varietor.

2.16 A full characterization of endofunctors of Set which are varietors has been presented in (Adámek and Trnková 1990). Let us call an endofunctor trivial provided that its restriction to all nonempty sets and functions is constant. (E.g., the functor ∅ ↦ ∅ and X ↦ 1 for all X ≠ ∅ is trivial.) An object X such that F X is isomorphic to X is called a fixed point of F.

Theorem The following conditions on an endofunctor F of Set are equivalent:

(i) F is a varietor, (ii) F is a constructive varietor, (iii)F has arbitrarily large fixed points, or F is trivial. For each such functor F the category of F –algebras is cocomplete.

Proof. See (Adámek and Trnková 1990, IV.43 and IV.8.2).

Remark An analogous result holds for Vec_{k}: (constructive) varietors are precisely the endofunctors which have arbitrarily large fixed points, or are constant, see (Adámek and Trnková 1990, IV.5.5).

2.17 Example of a varietor on Set which is not accessible. Assume the generalized continuum hypothesis. For a class M of cardinals with 0, 1 ∈ M denote by

P_{M}: Set → Set

the functor assigning to every set A the set of all subsets B ⊆ A with cardB ∈ M. P_{M} assigns to a morphism f: A → A′ the function defined as follows:

B ↦ f[B] if f restricted to B is one–to–one, else B ↦ ∅.

It is easy to see that P_{M} is accessible iff M is a set. And an infinite cardinal α is a fixed point of P_{M} iff α ∉ M. (The proof is easy: use the fact that α^{β} = α for all infinite cardinals β < α, see (Aczel et al. 2002).)

Now choose a class M of cardinals such that neither M nor its complement card \ M is a set. Then P_{M} is a varietor because it has arbitrarily large fixed points (namely all whose cardinality does not lie in M), but it is not accessible.

2.18 Example of a (trivial) non–constructive varietor: let C be the usual ordered class of all ordinals extended by a largest element, ⊤, considered as a category (with ∨ as binary coproduct). The functor F: C ⟶ C with

F (i) = i + 1 for all ordinals i and F (⊤) = ⊤

is a varietor: Alg(F) consists of a single algebra (⊤, α_{⊤}). However, for X = 0 we get X_{i}^{♯} = i for every ordinal i, thus, the free–algebra construction never stops.

2.19 Cofree coalgebras are the corresponding dualization of free algebras. A cofree F -coalgebra on an object X (“of colours”) of C is a coalgebra ψ_{X}: X_{♯} → F X_{♯} together with a (“colouring”) morphism ρ_{X}: X_{♯} → X having the universal property that given an F -coalgebra (C, α_{C}) and a morphism f: C → X of C there exists a unique F -coalgebra homomorphism f_{♯}, such that the following diagram commutes:

\xymatrix{ & C \ar[r]^{α_{C}} \ar[d]^{f_{♯}} \ar[dl]_{f} & F C \ar[d]_{F f_{♯}} \\ X & X_{♯} \ar[l]^{ρ_{X}} \ar[r]^{ψ_{X}} & F X_{♯}}

In other words, ρ_{X} is a couniversal arrow of the forgetful functor U: Coalg(F) → C.

2.20 Definition An endofunctor F: C → C is called a covarietor provided that a cofree F -coalgebra exists on every C-object.

This terminology is justified by the following remark based on 1.4 and 2.3.

2.21 Remark The following are equivalent for any F: C → C:

(i) F is a covarietor. (ii) F^{op} is a varietor. In case C has finite products, another equivalent condition is: (iii)For every object X in C the functor F^{X} = F (−) × X has a final (= terminal)

coalgebra.

2.22 Example Every accessible endofunctor of Set (in fact of any locally presentable category) is a covarietor as shown in (Barr 1993).

A dualization of the free-algebra construction above gives the following 2.23 Cofree Coalgebra Construction: Let C be a complete category. For every endofunctor F on C and every object X (“of colours”) in C define a transfinite cochain of objects X_{♯}^{i} (i any ordinal) and connecting morphisms x_{♯}^{i,j}: X_{♯}^{i} → X_{♯}^{j} (i ≥ j) as follows (where 1 denotes a terminal object of C):

First step X_{♯}^{0} = 1, X_{♯}^{1} = F 1 × X with x_{♯}^{1,0} : F 1 × X ⟶^{!} 1 the unique morphism, Isolated step X_{♯}^{i+1} = F X_{♯}^{i} × X for all ordinals i, x_{♯}^{i+1,j+1} = F x_{♯}^{i,j} × X for all i ≥ j, Limit step X_{♯}^{j} = lim_{i<j}X_{♯}^{i} for all limit ordinals j with limit cone x_{♯}^{j,i}, i < j.

If this cochain construction stops after k steps, i.e, x_{♯}^{k+1,k}: F X_{♯}^{k} × X → X_{♯}^{k} is an isomorphism, for some ordinal k, then X_{♯}^{k} is a cofree F -coalgebra on X. More detailed: Denoting the components of the inverse of x_{♯}^{k+1,k} by

α_{X}: X_{♯}^{k} → F X_{♯}^{k} and ρ_{X}: X_{♯}^{k} → X

these form a cofree F -coalgebra on X. For an F -coalgebra (C, α_{C}) and a morphism f: C → X the extension f_{♯} of f is the k-th member of the cocone f_{♯}^{i}: C → X_{♯}^{i} which is defined dually to 2.11.

2.24 Definition A functor F: C → C is called constructive covarietor provided that the above Construction 2.23 stops for each C-object X.

2.25 Examples (1) Let F = Id_{Set}. For every set X (of colours) we form the first steps of the cofree–coalgebra construction:

1 ← 1 × X ← 1 × X × X ← 1 × X × X × X ← …

where each of the connecting maps is the projection (forgetting the last component). A limit of this ω^{op}–sequence is X_{♯} = X^{ω}, the set of all infinite words over X (with projections as limit maps). For a given unary (co–)algebra (A, α_{A}) and a given colouring f: A → X the unique homomorphism f_{♯}: A → X_{♯} assigns to every element a ∈ A the word of colours of the elements a, α_{A}a, α_{A}^{2}a, …

(2) For polynomial endofunctors F_{Ω} of Set a description of a final coalgebra 1_{♯} (which also can be derived from the cofree coalgebra construction) is as follows: the elements of the coalgebra 1_{♯} are finite and infinite Ω–labelled trees (where Ω–labelled means that a node with k children is labelled by an element of Ω_{k} for all k = 0, 1, 2 …). The structure map

α_{1_{♯}}: 1_{♯} → ∑_{k∈ℕ}Ω_{k} × (1_{♯})^{k}

assigns to a tree t whose root is labelled by ω ∈ Ω_{k} the k–tuple of the subtrees given by the sons of the root (i.e., the corresponding element of (1_{♯})^{k} in the summand indexed by ω); i.e., the coalgebra structure is the inverse of tree tupling. Due to 2.4 we obtain immediately a description of X_{♯} for any set X (of colours). Since F_{Ω}(−) × X ≃ F_{Ω^{X}} (−) for the signature Ω^{X} = (Ω_{n} × X)_{n∈ℕ}, we obtain the following:

X_{♯} is the coalgebra of finite and infinite trees with a node having k children labelled in Ω_{k} × X for all k = 0, 1, 2, . . ..

(3) For P_{fin} the final–coalgebra construction stops after ω + ω steps, see (Worell 2000).

2.26 Theorem Every covariator in Set is constructive.

In fact, to prove this, it is, due to Remark 2.21, sufficient to prove that whenever F has a final coalgebra, the cofree–coalgebra construction for 1 stops, see (Adámek and Koubek 1995).

2.27 A full characterization of covarietors F in Set is not known. Let us call a cardinal number α an exponential fixed point of F provided that every set X whose cardinality lies between α and 2^{α} is a fixed point of F.

2.28 Theorem ((Adámek and Koubek 1995)) Every endofunctor of Set with arbitrarily large exponential fixed points is a covarietor.

2.29 Theorem ((Worell 2000)) Every λ–accessible endofunctor of Set is a covarietor, and the cofree–coalgebra construction stops in λ + λ steps.

2.30 Example of a covarietor on Set which is not accessible. Assume the Generalized Continuum Hypothesis. Let M be a class of cardinals containing 0, 1 such that M is not a set, but there exist arbitrarily large cardinals α with M ∩ [α, 2^{α}] = ∅. Then P_{M} (see 2.17) is a covarietor because it has arbitrarily large exponential fixed points. However, P_{M} is not accessible.

3. Varieties and Covarieties

In classical finitary algebra, an equation in variables from a set X is a pair of terms, i.e., elements of a free algebra X^{♯} on X. That is, a parallel pair

u, v: 1 → X^{♯}

of morphisms in Set. An algebra A satisfies that equation provided that for every interpretation of variables in A, i.e., every function f: X → A, the unique homomorphism f^{♯}: X^{♯} → A extending f (i.e., the function computing terms in A) satisfies

f^{♯}u = f^{♯}v.

This is equivalent to saying that f^{♯} factorizes through a coequalizer

e: X^{♯} → E

of u and v.

Thus, every equation gives us a regular quotient e: X^{♯} → E of the free algebra X^{♯} defining satisfaction in A by requesting that every homomorphism h: X^{♯} → A factors through e:

\xymatrix{X^{♯} \ar[r]^{h} \ar[d]_{e} & A \\ E \ar@{-->}[ur]_{h′}}

Conversely, given a regular quotient e: X^{♯} → E, then satisfaction of e in the above sense is equivalent to the satisfaction of the “classical” equations u = v for all pairs, u, v: 1 → X^{♯} with eu = ev. This leads us to the following concepts, closely related to those introduced in (Adámek 1983) and (Banaschewski and Herrlich 1976):

3.1 Definition Let F be an endofunctor of a cocomplete category C. Using the notation X_{i}^{♯} and f_{i}^{♯} as in 2.9 and 2.11 we define:

1. An equation arrow over X is a regular epimorphism e: X_{i}^{♯} → E for some ordinal i. An F -algebra (C, α_{C}) is said to satisfy e provided that for every morphism f: X → C the morphism f_{i}^{♯} factors through e:

\xymatrix{X_{i}^{♯} \ar[r]^{e} \ar[dr]_{f_{i}^{♯}} & E \ar@{-->}[d] \\  & C}

2. For any class E of equation arrows, Alg(F, E) denotes the full subcategory of Alg(F) formed by all F -algebras satisfying every e ∈ E. Such categories are called equational categories (of F -algebras) over C.

3.2 Examples (1) Varieties of finitary algebras are precisely the equational categories

Alg(F_{Ω}, E).

Here equations e: X_{i}^{♯} → E can always be substituted by equations e: X^{♯} (= X_{ω}^{♯}) → E, as we see below. Moreover, for every variety we only need a single equation–morphism e: X^{♯} → E with X a countable set: just consider the smallest equivalence ∼ on X^{♯} with u ∼ v for every equation u = v in the presentation of the variety. This is generalized in 3.8 below.

(2) Alg(F) is, of course, an equational class for any functor F: put E = ∅.

(3) If C has coequalizers, then for every parallel pair

u, v: C → X_{i}^{♯} (i ∈ Ord)

of morphisms a coequalizer of u and v is an equational arrow. An F –algebra A satisfies this arrow iff

(*) f_{i}^{♯}u = f_{i}^{♯}v for all f: C → A

Conversely, if C has kernel pairs, then every equational arrow e: X_{i}^{♯} → E is a coequalizer of its kernel pair u, v: C → X_{i}^{♯}, thus, satisfaction can be defined via (*). We use the usual notation u = v for the equation morphism that is the coequalizer of u and v.

3.3 Remark We want to distinguish between equational classes of algebras and varieties. The latter are requested to have the (important) property that free algebras exist on every object C of variables. This is not automatic, e.g., Alg(P), for the power–set functor P, is an equational class but not a variety.

Definition By a variety of F –algebras is meant an equational class Alg(F, E) such that the forgetful functor into C (a restriction of U_{F}) has a left adjoint.

3.4 Example “Classical” finitary varieties are precisely varieties of F –algebras for polynomial endofunctors F_{Ω} of Set.

3.5 Example (complete semilattices) The category of complete join semilattices has as objects all posets with joins and as morphisms all functions preserving joins. The objects can be described as precisely those P–algebras α_{A}: PA → A for which the (join-) operation α_{A} satisfies i. α_{A}{a} = a for every a ∈ A and

ii. α_{A}{α_{A}(A_{i}) | i ∈ I} = α_{A} ⋃_{i∈I}A_{i} for all collections A_{i} ⊆ A, i ∈ I.

We can express (i) and (ii) by equation–arrows as follows.

ad i. Put X = {x} and observe that we have

\begin{aligned}X_{0}^{♯} & = & ∅ \\ X_{1}^{♯} & = & P∅ + X = \{∅, x\} \\ X_{2}^{♯} & = & P\{∅, x\} + X = \{∅, x, \{x\}, \{∅\}, \{∅, x\}\} \end{aligned}

Condition (i) is expressed by the equation

{x} = x

or, more precisely, by the equation–arrow e: X_{2}^{♯} → X_{2}^{♯}/∼ which is the canonical map of the equivalence ∼ whose only nonsingleton equivalence class is {x, {x}}.

In fact, a P–algebra (A, α_{A}) satisfies x = {x} iff for every morphism f: X → A (i.e., every element a = f(x) of A) the extension f_{2}^{♯}: X_{2}^{♯} → A satisfies f_{2}^{♯}({x}) = f_{2}^{♯}(x). Equivalently: α_{A}{a} = a.

ad ii. Put X = A and observe that ∪_{i∈I}A_{i} is an element of X_{2}^{♯} and {A_{i} | i ∈ I} an

element of X_{3}^{♯}. Consider the equation

{A_{i} | i ∈ I} = ⋃_{i∈I}A_{i},

or, more precisely, the equation–arrow ē: X_{3}^{♯} → X_{3}^{♯}/∼ where ∼ is the equivalence whose only nonsingleton equivalence class is {{A_{i} |_{i∈I}}, ∪_{i∈I}A_{i}}. The satisfaction of the equation arrow ē implies (ii) trivially: just use f = id: X → A. Conversely, every P–algebra satisfying (i) and (ii) above satisfies the equation arrow ē.

Remark Free complete semilattices exist: they are the powerset–semilattices. Thus complete semilattices form a variety of P–algebras.

3.6 Lemma For arbitrary ordinals i ≤ j, any equation

u = v with u, v: C → X_{i}^{♯}

is equivalent to the equation

x_{ij}u = x_{ij}v.

That is, an F –algebra satisfies the first one iff it satisfies the latter.

Proof. This follows from f_{j}^{♯}x_{ij} = f_{i}^{♯}, see 2.12.

3.7 Corollary If F is a constructive varietor, we only need to consider equations u = v for morphisms u, v: C → X^{♯}.

3.8 Corollary For every accessible endofunctor F of Set and any equational class V of F -algebras there is a single equation arrow e presenting V, i.e. such that V = Alg(F, {e}).

In fact, if F is λ-accessible, then it is easy to see that every equation u = v for elements u, v ∈ X^{♯} (see 3.7 and 2.15) is equivalent to an equation u′ = v′ for suitable elements u′, v′ ∈ M^{♯}, where M is an (arbitrary) set of cardinality λ. Thus, every equational class is presented by a set pairs of elements of M^{♯}. For each of these pairs form a coequalizer, and obtain a set of quotients of M^{♯} in Set. Forming a pushout, e, of that set of (regular) epimorphisms, we obtain V = Alg(F, {e}).

By formally dualizing Definition 3.1, see Lemma 1.4, we obtain the following

3.9 Definition Let F be an endofunctor of a complete category C.

1. A coequation arrow over X is a regular monomorphism m: M → X_{♯}^{i} for some ordinal i. An F –coalgebra (C, α_{C}) is said to satisfy m provided that for every morphism f: C → X the morphism f_{♯}^{i} factors through m.

2. For any class M of coequation arrows Coalg(F, M) denotes the full subcategory of Coalg(F) formed by all F –coalgebras satisfying every m ∈ M. Such categories are called coequational categories (of F –coalgebras) over C.

3.10 Notation For C = Set, given an element d ∈ X_{♯}^{i} we denote by ¬d the coequation arrow

X_{♯}^{i} \ {d} ↪ X_{♯}^{i}.

Thus, a coalgebra A satisfies ¬d iff for every colouring f: A → X we have

f_{♯}^{i}(a) ≠ d for all a ∈ A.

Observe that we do not need any more general coequations: instead of a coequation arrow m: M → X_{♯}^{i} we can always consider the coequations ¬d for all d ∈ X_{i}^{♯} \ m[M].

3.11 Example (nonlabelled transition systems (= graphs)) Here F = P, the power–set functor. We give some examples of covarieties.

(a) No terminals. A state s of a transition system A is terminal if s → t holds for no state t. The non-existence of terminal states is expressed by the coequation ¬∅ for ∅ ∈ P1 = 1_{♯}^{1}. In fact, we have f_{♯}^{0} : A → 1, the constant function, and f_{♯}^{1} : A → P1 = {∅, 1} taking value ∅ for terminal states and 1 for nonterminal states.

(b) One–step reachability of terminals. Consider

1_{♯}^{2} = PP1 = {∅, {∅}, {1}, {∅, 1}}.

Given a state s then f_{♯}^{2}(s) = ∅ iff s is terminal, f_{♯}^{2}(s) = {∅} iff s is nonterminal but only terminal states can be reached from s directly, and f_{♯}^{2}(s) = {1} iff s is nonterminal and only nonterminal states can be reached from s directly. Thus, the coequation ¬{1} means: from every state a terminal state is reachable in at most 1 step.

(c) Reachability of terminals. In the cofree–coalgebra sequence

1 ← P1 ← PP1 ← …

consider the elements d_{n} ∈ P^{n}1 where d_{0} is the unique element of 1, and

d_{n+1} = {d_{n}}.

The sequence d = (d_{n}) = (d_{0}, 1, {1}, {{1}} …) is compatible, i.e., is an element of the limit

1_{♯}^{ω} = lim_{n<ω}1_{♯}^{n}.

For a state s we have f_{♯}^{ω}(s) = d iff f_{♯}^{1}(s) = {1} (i.e., only nonterminals are reached in 1 step) and f_{♯}^{2}(s) = {1} (i.e., only nonterminals are reached in 2 steps) etc. Thus, ¬d expresses the fact that from each state a terminal state is reachable.

(d) Reflexivity, i.e., the fact that s → s, for each state s, can be easily expressed using two colours. Put 2 = {0, 1} and consider the cofree–coalgebra sequence

1 ← P(1) × 2 ← P (P(1) × 2) × 2 ← …

Given a colouring f: A → {0, 1}, then f_{♯}^{2}(s) = (M, f(s)) where M ⊆ P(1) × 2 is the set of all pairs (B, i) where, for some state s′ reachable from s, we have f(s′) = i and, either B = ∅ if s′ is a terminal state, or B = 1, else. Suppose that f_{♯}^{2}(s) = ({1, 0}, 1), then s has colour 1 but every reachable state has colour 0. Thus, s is not reflective. It is easy to see that the coequation ¬({1, 0}, 1) means: for every state s either s → s, or s is terminal. Thus, reflexivity is axiomatized by the two coequations ¬∅ and ¬({1, 0}, 1).

(e) Symmetry, i.e., the fact that

s → t implies t → s (for all states s, t).

Here we use

f_{♯}^{3} : A → P (P (P(1) × 2) × 2) × 2

given by f_{♯}^{3}(s) = (R, f(s)) where R ⊆ P (P(1) × 2) × 2 is the set of all f_{♯}^{2}(t) for edges s → t. Suppose that for a colouring f: A → {0, 1} and a state s we have f_{♯}^{2}(s) = (R, 0) where R ⊆ P (P(1) × 2) × 2 contains an element of the form (−, 1). Every element r ∈ R (a pair consisting of a subset of P(1) × 2 and a colour) corresponds to a state t with s → t in the sense that f_{♯}^{1}(t) = r. Thus, if some element r ∈ R has the form r = (Q, 1), then we have a state t directly reachable from s of colour 1 such that f_{♯}^{2}(t) = Q. Symmetry then guarantees that Q contains (1, 0): in fact, we have the edge t → s where f_{♯}^{1}(s) = (1, 0). Thus, in a symmetric transition system f_{♯}^{3}(s) never has the form (R, 0) where some element of R is (Q, 1) with (1, 0) ∉ Q. Symmetry is axiomatized by the following coequations

¬(R, 0) for all R ⊆ P (P(1) × 2) × 2 containing some (Q, 1) with (1, 0) ∉ Q.

3.12 Example (dynamical systems on two inputs) Here we consider the functor F X = X × X + 1 of Example 1.5(1), thus, coalgebras are dynamical systems on two inputs with deadlock states. Recall that the final coalgebra consists of binary trees with leaves labelled by ⊥.

(a) The coequation

¬ ◯ ⊥

means: no deadlock states.

(b) The coequation

¬ [figure: ⊥; ⊥]

means: every non–deadlock state can continue indefinitely (without encountering a deadlock state).

(c) The coequation

¬ [figure: ⋮]

means: from every state a deadlock state is reachable.

(d) For 2 = {0, 1} we have 2^{♯} = coalgebra of binary trees with leaves labelled by (⊥, 0) or (⊥, 1) and internal nodes labelled by 0 or 1.

The coequation

¬ [figure: 0; 1; 1; 1; 1; 1; 1; ⋮]

means: from every non–periodic state a deadlock state is reachable. (A state is periodic if the system can return to that state after n > 0 steps.)

3.13 Example (Dynamical system on one input [without deadlock]) Here F = Id_{Set}, and coalgebras are just unary algebras. We have X_{♯} = X^{ω}, the set of all infinite words on X.

Given an element a of a (co)algebra A, we say that a lies over a cycle of length n provided that n is the smallest number with α_{A}^{k}(a) = α_{A}^{k+n}(a) for some k ∈ ℕ. The smallest such k is called the distance of a from the cycle.

(a) For 2 = {0, 1} consider

d = 010101 … = (01)^{ω}.

An algebra A satisfies the coequation ¬d iff every element lies over an odd cycle. In fact, A satisfies ¬d iff for every colouring f: A → {0, 1}, given an element a ∈ A, then the word

(f(a), f(α_{A}(a)), f(α_{A}^{2}(a)) …)

is distinct from d. This is certainly true if a lies over an odd cycle. Conversely, if a lies over an even cycle, or does not lie over any cycle (i.e., the elements α_{A}^{k}(a) are pairwise distinct), we can certainly choose a colouring f: A → {0, 1} with

f(α_{A}^{k}(a)) = \{ \begin{matrix}0 & k & even \\ 1 & k & odd. \end{matrix}

Then f_{♯}(a) = 010101 . . ..

(b) For

d = \underbrace{00 … 0}_{s} 010101 … = 0^{s}(01)^{ω}

an algebra A satisfies ¬d iff every element either lies over an odd cycle, or it lies over an even one and has distance less than s from it. Shortly: no element has distance s from an even cycle, and every element lies over a cycle.

(c) Analogously, for

d = \underbrace{00 … 0}_{s} \underbrace{00 … 0}_{p} 1 \underbrace{00 … 0}_{p} 1 … = 0^{s}(0^{p}1)^{ω}

an algebra satisfies ¬d iff no element has distance s from a cycle whose length is a multiple of p, and every element lies over a cycle.

Remark The above example shows that for every set S ⊆ ℕ × ℕ we have the following covariety C_{S} of unary algebras:

A ∈ C_{S}, iff given (s, p) ∈ S, then no element of A has distance s from a cycle of length in pℕ, and every element lies over a cycle.

One can show that these are precisely all covarieties in Coalg(Id).

4. Limits and Colimits

In this section we summarize results on limits and colimits of (co)algebras needed for the proof of Birkhoff’s Variety Theorem in the subsequent section. Most of these results can be found in the existing literature, although e.g. the Colimit Theorem below seems to be new (and easy).

4.1 Products of F –algebras are easy to construct: suppose C has products and let (A_{i}, α_{i}) be a collection of F –algebras (i ∈ I). Form a product A = ∏_{i∈I}A_{i} in C with

projections π_{i}: A ⟶ A_{i}. Then there exists a unique α: F A → A turning each π_{i} into a homomorphism, viz, α = ⟨α_{i} ∘ F π_{i}⟩: F A → ∏ A_{i}. And it is easy to see that (A, α) is a product of the given F –algebras in Alg(F).

4.2 Limits of F –algebras The above construction is a special case of the following fact: the forgetful functor

U: Alg(F) → C

creates limits. This means that, given a diagram D in Alg(F) and forming a limit cone (A ⟶^{π_{i}} UD_{i}) of UD in C, there exists a unique α: F A → A turning each π_{i} into a homomorphism. And (A, α) is, then, a limit of D. The proof is easy, see e.g. (Adámek and Trnková 1990).

Corollary If C is complete then categories of F –algebras are complete.

4.3 Corollary A homomorphism in Alg(F) is an isomorphism (or a monomorphism) iff its underlying morphism is an isomorphism (or a monomorphism resp.) in C.

If C has kernel pairs and F preserves coequalizers of kernel pairs, a homomorphism in Alg(F) is a regular epimorphism iff its underlying morphism is a regular epimorphisms in C.

In fact, a functor creating pullbacks preserves and reflects monomorphisms, isomorphisms, and kernel pairs. And regular epimorphisms are precisely the coequalizers of their kernel pairs.

Since the underlying functor of Alg(F) allows for unique transport of structures and every C-object carries only a set of F -algebras we get

4.4 Corollary If C is wellpowered (i.e., every object has only a set of subobjects) then so are the categories of F –algebras.

4.5 Colimits of F –algebras This is a more difficult topic. Firstly, colimits need not exist, in general. E.g., the power–set functor P: Set → Set does not have any fixed point. Thus, by Lambek’s Lemma, an initial P–algebra (i.e., the empty colimit in Alg (P)) does not exist.

One easy case is that of colimit types preserved by F:

4.6 Proposition For every type of colimits in C which F preserves the category of F – algebras has colimits of that type, created by the forgetful functor.

Proof. Given a diagram D: D → Alg(F) such that C has and F preserves colimits over D, form a colimit (A_{d} ⟶^{c_{d}} A)_{d∈D} of UD in C, where UDd = A_{d}, and observe that, since (F A_{d} ⟶^{F_{c_{d}}} F A)_{d∈D} is a colimit of F UD, there exists a unique α: F A → A turning each c_{d} into a homomorphism. It is easy to see that (A, α) together with c_{d} (d ∈ D) is a colimit of D in Alg(F).

4.7 Example The polynomial functors F_{Ω} : Set → Set preserve filtered colimits. This is true because (i) each functor X ↦ X^{n} (n a natural number) preserves filtered colimits, since finite products and filtered colimits commute in Set and (ii) F_{Ω} is a coproduct of functors (i), and coproducts commute with (filtered) colimits.

Therefore, filtered colimits of “classical” algebras are created by the forgetful functor.

4.8 Recall that a category C is said to have regular factorizations provided that every morphism of C factorizes as a regular epimorphism followed by a monomorphism. A functor U: A → C is said to create regular factorizations provided that for every morphism f: A → B in A with a regular factorization Uf = m∘e in C there exist unique morphisms m_{0} and e_{0} in A with m = Um_{0} and e = Ue_{0}, and moreover, m_{0} is a monomorphism and e_{0} is a regular epimorphism with f = m_{0} ∘ e_{0}.

4.9 Proposition Let C have pullbacks and regular factorizations. If F preserves regular epimorphisms then Alg(F) has regular factorizations created by the forgetful functor.

Remark We prove a more general statement which concerns regular cone–factorizations. Consider a cone, i.e., a (possibly large or empty) collection of morphisms f_{i}: A → B_{i} (i ∈ I). A regular cone–factorization is a regular epimorphism e: A → A′ and a collectively monomorphic cone m_{i}: A′ → B_{i} (i ∈ I) with f_{i} = m_{i}e for all i ∈ I. If a cowellpowered category C has regular factorizations and products, then it has regular cone–factorizations. (In fact, for small cones f_{i}: A → B_{i} just form a regular factorization of ⟨f_{i}⟩_{i∈I}: A → ∏_{i∈I}B_{i}. For large cones use regularly cowellpoweredness on the

coimages of f_{i}, i ∈ I, to reduce to a small cone.) Note that this condition in case of an empty cone simply means: there is a regular epimorphism A ⟶^{e} B such that any two maps r, s: B′ → B coincide. In Set a regular factorization of a cone f_{i}: A → B_{i} can be obtained by factorizing each f_{i} over A/ρ where ρ is the intersection of the kernels of all f_{i}.

We prove that whenever C has pullbacks and regular cone-factorizations, then Alg(F) has regular cone-factorizations created by the forgetful functor.

Proof. Given a cone f_{i}: (A, α_{A}) → (B_{i}, α_{B_{i}}) in Alg(F) and given a regular cone factorization f_{i} = m_{i}e in C with e: A → C, there exists

\xymatrix{F A \ar[r]^{F e} \ar[d]_{α_{A}} & F C \ar[r]^{F m} \ar@{.>}[d]_{α_{C}} & F B \ar[d]^{α_{B}} \\ A \ar[r]_{e} & C \ar[r]_{m_{i}} & B_{i}}

a unique α_{C}: F C → C turning e and each m_{i} into homomorphisms. This follows from the diagonal fill–in property of the regular epimorphism F e and the (possibly empty) monomorphic cone m_{i}. Since m_{i} is monomorphic in C, it follows easily that m_{i}: (C, α_{C}) → (B, α_{B}) is monomorphic in Alg(F). Let us form a kernel pair k_{1}, k_{2} : K → A of e (i.e., a pullback of e and e),

then since e is a regular epimorphism, it is a coequalizer of k_{1} and k_{2} in C. Now, U creates pullbacks, thus, we have homomorphisms k_{1}, k_{2} : (K, α_{K}) → (A, α_{A}), and it is easy to see that e is a coequalizer of k_{1} and k_{2} in Alg(F). Thus, e is a regular epimorphism in Alg(F).

4.10 Corollary For every endofunctor F of Set the category of F –algebras has regular factorizations created by the forgetful functor.

In fact, regular epimorphisms in Set are just the split epimorphisms which all functors preserve.

4.11 Colimit Theorem Let C have pullbacks and regular cone–factorizations. For every varietor F preserving regular epimorphisms, Alg(F) has colimits of all types existing in C.

Proof. Let D: D → Alg(F) be a diagram with UDd = A_{d} (d ∈ D) such that UD has a colimit

(A_{d} ⟶^{c_{d}} C)_{d∈D}

in C. Let η_{C}: C → UC^{♯} be a free F –algebra on C. Form the cone of all homomorphisms r: C^{♯} → R in Alg(F) with the property that each Ur · η_{C} · c_{d} is a homomorphism from Dd to R (d ∈ D). Let

C^{♯} ⟶^{e} E ⟶^{r′} R = C^{♯} ⟶^{r} R

be a regular factorization of that cone in Alg(F) (see 4.9). Then each

c̄_{d} = Ue ∘ η_{C} ∘ c_{d}: Dd → E (d ∈ D)

is a homomorphism. In fact, for every r the following square

\xymatrix{F A_{d} \ar[r]^{F c_{d}} \ar[d]_{α_{A_{d}}} & F C \ar[r]^{F η_{C}} & F UC^{♯} \ar[r]^{F Ue} & F UE \ar[r]^{F Ur′} \ar@{.>}[d]^{α_{E}} & F UR \ar[d]^{α_{R}} \\ A_{d} \ar[r]_{c_{d}} & F C \ar[r]_{η_{C}} & UC^{♯} \ar[r]_{Ue} & UE \ar[r]_{Ur′} & UR}

commutes because Ur ·η_{C} ·c_{d} is a homomorphism. Since the cone of all Ur′ is collectively monomorphic, it follows that the left–hand subsquare commutes.

We claim that (Dd ⟶^{c̄_{d}} (E, α_{E}))_{d∈D} is a colimit of D in Alg(F). It is obviously a cocone of D, because (c_{d}) is a cocone of UD. Let f_{d}: Dd → B be another cocone of D. Then there exists a unique f: C → UB in C with Uf_{d} = f ∘ c_{d} (d ∈ D). The unique homomorphism r: C^{♯} → B with f = Ur ∘ η_{C} is a member of the above cone, thus, we have a factorization r = r′ ∘ m. The homomorphism r′: E → B fulfills f_{d} = r′ ∘ c̄_{d} for all d because

Uf_{d} = f ∘ c_{d} = Ur ∘ η_{C} ∘ c_{d} = Ur′ ∘ Uc̄_{d}.

And r′ is unique: suppose that a homomorphism h: E → B also fulfills f_{d} = h ∘ c̄_{d} for all d, then we have

UhUeη_{c} ∘ c_{d} = Ur′ ∘ Ue ∘ η_{C} ∘ c_{d} (d ∈ D)

which, due to the universal property of colimits, implies

Uh ∘ Ue ∘ η_{C} = Ur′ ∘ Ue ∘ η_{C}

and this implies h ∘ e = r′ ∘ e. Since e is an epimorphism, this proves h = r.

4.12 Corollary Let C be a complete, cocomplete, regularly cowellpowered category with regular factorizations. Then for every varietor F preserving regular epimorphisms the category of F –algebras is cocomplete.

4.13 Theorem For every functor F: Set → Set Alg(F) is cocomplete, provided that F is a varietor. The reverse implication holds under the generalized Continuum Hypothesis.

Proof. The implication above is a consequence of 4.12. Set satisfies all the hypotheses, and F preserves regular (= split) epimorphisms automatically.

The reverse implication follows from (Adámek, Koubek and Pohlová 1972, Theorem III.4) which states a necessary and sufficient condition of cocompleteness of categories of bialgebras, A(F, G). The choice of G = Id_{Set} yields

Alg(F) = A(F, Id_{Set})

and the theorem states that Alg(F) has colimits iff F preserves unions or is non–excessive, which means that for arbitrarily large sets X we have cardF X ≤ cardX. Now every set functor preserving unions is easily seen to be non–excessive. And non–excessive functors are varietors, see (Adámek and Trnková 1990, 4.3).

4.14 Remark Another important criterion for cocompleteness of categories of algebras follows from the theory of locally presentable categories. Recall that a category C is locally λ–presentable provided that it is cocomplete and has a set A of λ–presentable objects (i.e., objects A such that the hom–functor of A preserves λ–filtered colimits) such that all objects of C are λ–filtered colimits of objects of A. Examples: Set, Vec_{k}, Pos are locally ℵ_{0}–presentable, the category of CPO′s is locally ℵ_{1}–presentable. But Set^{op} is not locally presentable.

4.15 Theorem For every accessible endofunctor F of a locally presentable category C the category of F –algebras has colimits. In fact, Alg(F) is locally presentable.

Proof. See (Adámek and Rosický 1994, 2.75).

Using Lemma 1.4, we obtain the following dualizations of the above results.

4.16 Theorem The forgetful functor of the category of F –coalgebras creates colimits and all limits preserved by F.

4.17 Corollary If C is cocomplete then all categories of coalgebras are cocomplete.

4.18 Corollary A homomorphism in Coalg(F) is an isomorphism (or an epimorphism) iff its underlying morphism is an isomorphism (an epimorphism, respectively) in C. If C has cokernel pairs and F perserves equalizers of cokernel pairs, then a homomorphism in Coalg(F) is a regular monomorphisms iff its underlying morphism is a regular monomorphism.

4.19 Corollary If C is cowellpowered, so are all categories of coalgebras.

4.20 Proposition (see also (Gumm and Schröder 2001)) For every covarietor F in Set the category of F –coalgebras is complete.

Proof. If F preserves regular monomorphisms, this follows from the dual of 4.11. Now recall that regular monomorphisms in Set are just one–to–one functions, and that

all except those with empty domains are split (and thus preserved by any functor)! To complete the proof it remains to apply the following result of V. Trnková (see (Adámek and Trnková 1990)).

4.21 LemmaFor every functor F: Set → Set which does not preserve monomorphisms there exists a functor F′: Set → Set preserving monomorphisms, and such that

F X = F′X for all sets X ≠ ∅
F f = F′f for all functions f: X → Y with X ≠ ∅

and F ∅ ≠ ∅ ≠ F′∅.

Proof. See (Adámek and Trnková 1990, III.4.5 – 6).

Remark Given now F and F′ as in this lemma, we have

Alg(F) = Alg(F′)

because no F –algebra (and no F′–algebra) has underlying set ∅. And

Coalg(F) ≅ Coalg(F′)

because the two categories of coalgebras only differ in the name of the codomain of the unique coalgebra (∅, α_{∅}).

In particular, if Coalg(F′) is complete, so is Coalg(F).

4.22 Remark It is not known whether completeness of Coalg(F), where F is a Setfunctor, implies that F is a covarietor.

4.23 Remark Dualizing 4.8, we see that for C with pushouts and coregular factorizations, i.e., factorizations as an epimorphism followed by a regular monomorphism, the following holds: Coalg(F) has coregular factorizations created by U whenever F preserves regular monomorphisms. This also generalizes to factorizations of cocones. In Set a coregular factorization of a cocone f_{i}: B_{i} → A can be obtained by factorizing each f_{i} over the subset X ⊆ A which is the union of the images of all f_{i}. Combined with 4.21 we obtain the following

Corollary If C = Set then all categories of coalgebras have coregular factorizations created by the forgetful functor.

5. Birkhoff Variety (and Covariety) Theorem

5.1 Observation Suppose that F is an endofunctor of a complete category; then the following hold for every equational class V of F –algebras.

1) V is closed under products, i.e., if A_{t} ∈ V for t ∈ T then ∏ A_{t} ∈ V.

2) V is closed under subalgebras, i.e., given a monomorphism m: A → B in Alg(F) with B ∈ V, then A ∈ V.

3) Generalizing 1) and 2), V is closed under monomorphic cones in Alg(F). That is, if m_{t}: A → B_{t} is a monomorphic family of homomorphisms in Alg(F), then if B_{t} ∈ V for all t, then A ∈ V. In fact, if e: X_{i}^{♯} → E is an equation arrow that each B_{t} satisfies, then A satisfies e, too: for every f: X → A factor (m_{t}f)_{i}^{♯} = m_{t}f_{i}^{♯} (see 2.12) through e and use the diagonal fill–in

\xymatrix{X_{i}^{♯} \ar[r]^{e} \ar[d]_{f_{i}^{♯}} & E \ar[d] \ar@{-->}[dl] \\ A \ar[r]_{m_{t}} & B_{t}}

Note that here the indices might even range over a class T.

4) V is closed under retract–carried quotient algebras in Alg(F), i.e., given a homomorphism q: A → B in Alg(F) and a morphism m: UB → UA in C with Uq ∘ m = id, then if A ∈ V, then B ∈ V. In fact, if A satisfies e: X_{i}^{♯} → E then B also satisfies it: for every f: X → B we have a factorization of (mf)_{i}^{♯}: X_{i}^{♯} → A through e, say, (mf)_{i}^{♯} = ge. From 2.12 we get (qg)e = q(mf)_{i}^{♯} = (qmf)_{i}^{♯} = f_{i}^{♯}, showing that f_{i}^{♯} factors through e.

5.2 The Birkhoff Variety Theorem Let C be a complete, regularly cowellpowered category with regular factorizations. For every constructive varietor F preserving regular epimorphisms, varieties of F –algebras are precisely the full subcategories of Alg(F) closed under i. products, ii. subalgebras, and iii. retract–carried quotient algebras.

Remark We will also prove that every variety is reflective in Alg(F) with reflection arrows being regular epimorphisms. Thus, varieties are complete and, in case C is cocomplete, also cocomplete (see 4.11)

Proof. If V is a variety, then it is closed under i. – iii. by 5.1. Conversely, let V be closed under i. – iii.

(a) Observe that Alg(F) has regular cone–factorizations created by the forgetful functor — see Remark 4.9. Since Alg(F) is regularly cowellpowered (which is obvious from 4.9), any full subcategory V of Alg(F) closed under products and subalgebras is closed under monomorphic cones — see (Adámek, Herrlich and Strecker 1990, 16.8). It follows that any such V is reflective in Alg(F): a reflection of an F –algebra A is obtained from the cone of all morphisms with domain A and codomain in V, f_{t}: A → B_{t} (t ∈ T): let e: A → A′ be a regular epimorphism forming a regular factorization of that cone, i.e., we have a monomorphic cone m_{t}: A′ → B_{t} with f_{t} = m_{t} ∘ e. Since B_{t} ∈ V for each t, we conclude A′ ∈ V. It follows that e: A → A′ is a reflection of A.

(b) Let E be the class of all equation arrows e: X^{♯} → A′ where X is an object of C, A = X^{♯} (= X_{i}^{♯} for some i) is a free F –algebra on X, and e: A → A′ is a reflection of A in V. Then we prove

V = Alg(F, E).

(α)Every algebra B ∈ V satisfies each of the equation arrows e: X^{♯} → A′ above. In fact, for every morphism f: X → A the unique homomorphism f^{♯}: X^{♯} → B with f = f^{♯} ∘ η_{X} factors through e (since f^{♯} = f_{t} for some t, and f^{♯} = m_{t} ∘ e).

(β)Every algebra C satisfying each e ∈ E lies in V. Put X = UC and denote by h: X^{♯} → C the unique homomorphism with h ∘ η_{X} = id_{X}. For the reflection e: X^{♯} → A′ we know that, since C satisfies e, the homomorphism h factors through e, say, h = ke. Then k: A′ → C is a regular epimorphism carried by a split epimorphism in C (since h is), and thus from A′ ∈ V we conclude C ∈ V.

5.3 Regular quotients of A in Alg(F) are those B in Alg(F) which admit a regular epimorphism e: A → B. For C = Set the regular quotients in Alg(F) are precisely those carried by (split) epimorphisms in Set (i.e., the “quotients” or “homomorphic images” in the usual sense), see 4.3, since coequalizers of kernel pairs in Set are absolute, i.e., preserved by every functor. Thus, the following is a corollary to 5.2 which, for polynomial functors F, specializes to the classical Birkhoff Variety Theorem.

Corollary For every varietor F over Set, varieties of F –algebras are precisely the full subcategories closed in Alg(F) under products, subalgebras and regular quotients.

5.4 Notation For a class E of morphisms in a category C we denote by InjE the full subcategory of all objects C injective w.r.t. any member e: A → A′ of E (i.e., for every morphism f: A → C there exists f′: A′ → C with f = f′e). We call InjE the injectivity class of E.

5.5 Corollary Under the assumptions of Theorem 5.2, varieties of F –algebras are precisely the injectivity classes InjE in Alg(F), where E is a collection of regular quotients of free F –algebras.

In fact, in the proof of 5.2 we have found, for every variety V, the corresponding collection E, viz, all reflections of free F –algebras in V. Conversely, it is sufficient to verify that InjE, for a class E as above, is closed under i. products — this is trivial, ii. subalgebras — this follows from the diagonal fill–in between monomorphisms and

regular epimorphisms, and iii. retract–carried quotients.

To show iii., let q: R → Q be a homomorphism with Uq ∘ m = id for some m: UQ → UR. If R is E–injective, then so is Q: given e: X^{♯} → E in E and h: X^{♯} → Q, then for g = U(mh)η_{X}: X → UR we form the unique homomorphism g^{♯}: X^{♯} → R with g = Ug^{♯} · η_{X}. There exists a homomorphism k: E → R with g^{♯} = ke. We claim that qk: E → Q is the desired factorization of h through e, i.e., qke = h: X^{♯} → Q. Since both sides are homomorphisms (recall ke = g^{♯}), it is sufficient to observe that

U(qke) ∘ η_{X} = Uq ∘ g = Uq ∘ Um ∘ Uh ∘ η_{X} = Uh ∘ η_{X}.

Using Corollary 3.8 in addition we obtain

5.6 Corollary Let F be an accessible endofunctor of Set and V be an equational class of F -algebras. Then there is a single regular quotient e of a free F -algebra X^{♯}, such that V = Inj{e}.

5.7 Remark Recall that an object A is called a regular projective provided that it is projective (the dual to the above injective) w.r.t. to all regular epimorphisms.

Example: every free F –algebra X^{♯} for an endofunctor F of Set is a regular projective. In fact, given a regular epimorphism e: A → B in Alg(F), then e is a (split) epimorphism in Set, choose m: UB → UA with Ue ∘ m = id. For every homomorphism h: X^{♯} → B form k = (m ∘ Uh ∘ η_{X})^{♯}: X^{♯} → A then by 2.12 we have

e ∘ k = (Ue ∘ m ∘ Uh ∘ η_{X})^{♯} = (Uh ∘ η_{X})^{♯} = h.

5.8 Corollary For a varietor F of Set, varieties of F –algebras are precisely the injectivity classes of regular quotients of regular projectives in Alg(F).

In fact, every variety is such an injectivity class by 5.5 and 5.7. Conversely, let E be a collection of regular quotients of regular projectives. Then InjE is closed under products and subalgebras (the argument is precisely as in 5.5) and it is closed under regular quotients. The argument for the latter is also analogous to 5.5: let q: R → Q with Uq ∘ m = id and e: E → E′ in E be given, with E a regular projective. For h: E → Q we have, since q is a regular epimorphisms (4.10) k: E → R with h = qk. From the fact that R is e–injective it now easily follows that so is Q.

5.9 Remark It might be instructive to show how to obtain, in Alg(F), from a regular quotient of a regular projective, e, a regular quotient of a free algebra, ē, such that injectivity w.r.t. e and ē is equivalent. In fact, consider such an epimorphism, e: (D, α_{D}) → (E, α_{E}). Since the homomorphism id^{♯}: (D^{♯}, φ_{D}) → (D, α_{D}) is a regular epimorphism in Alg(F) and (D, α_{D}) is regularly projective we have a homomorphism

m: (D, α_{D}) → (D^{♯}, φ_{D}) with id^{♯} ∘ m = id.

Choose a pair of homomorphisms u, v with coequalizer e in Alg(F). Then an algebra (C, α_{C}) is orthogonal to e iff for every homomorphism h: (D, α_{D}) → (C, α_{C}) we have h ∘ u = h ∘ v. This is equivalent to stating that for every homomorphism k: (D^{♯}, φ_{D}) → (C, α_{C}) we have k ∘ (m ∘ u) = k ∘ (m ∘ v): given k, put h = k ∘ m, and given h, put k = h ∘ id^{♯}. Thus, if ē: (D^{♯}, φ_{D}) → (Ē, αĒ) denotes a coequalizer of m ∘ u and m ∘ v in Alg(F), then injectivity to ē and e, respectively, is equivalent. (And the former can be substituted by the equations u_{0} = v_{0} obtained by the kernel pair of ē.)

5.10 Remark The above Corollary is much in the spirit of (Herrlich and Ringel 1972) and (Banaschewski and Herrlich 1976).

In the following result we fully characterize varieties as monadic categories over C, i.e., such concrete categories A ⟶^{U} C for which U is a right adjoint and the comparison functor K

\xymatrix{A \ar[rr]^{K} \ar[dr]_{U} &  & C^{𝕋} \ar[dl]^{U^{𝕋}} \\  & C}

of the corresponding monad 𝕋 over C is an equivalence functor.

In general, we call concrete categories (A, U) and (A′, U′) concretely equivalent provided that there exists an equivalence functor K: A → A′ with U = U′K.

5.11 Monadicity Theorem Let C be a cocomplete category. Then monadic categories over C are, up to concrete equivalence, precisely the varieties.

Proof. I. Let V = Alg(F, E) be a variety of F –algebras. By definition, the forgetful functor U: V → C is a right adjoint. By Proposition 4.16, U creates all colimits that F preserves, in particular, U creates absolute coequalizers. Consequently, (V, U) is monadic by Beck’s Theorem (Mac Lane 1971). II. For the converse it suffices to show that, for any monad 𝕋 = (T, η, μ) on a cocomplete category C, the Eilenberg-Moore category C^{𝕋} of 𝕋-algebras coincides with the subcategory Alg(T, E) of Alg(T) for a suitable class E of equation arrows. For doing so consider, for every C-object X, the coproduct

X ⟶^{m_{i+1}} T X_{i}^{♯} + X = X_{i+1}^{♯} ⟵^{n_{i+1}} T X_{i}^{♯}.

A class E_{1} of equation arrows now is defined as follows: for every C-object X let e_{X}: X_{2}^{♯} → E_{X} be a coequalizer of the pair m_{2}, n_{2} ∘ η_{X_{1}^{♯}} ∘ m_{1}. A T -algebra (C, α_{C}) satisfies e_{X} iff, for every morphism f: X → C, the morphism

f_{2}^{♯} = [α_{C} ∘ T f_{1}^{♯}, f]: T X_{1}^{♯} + X → C

satisfies f_{2}^{♯} ∘ m_{2} = f_{2}^{♯} ∘ n_{2} ∘ η_{X_{1}^{♯}} ∘ m_{1} or, equivalently, f = α_{C} ∘ T f_{1}^{♯} ∘ η_{X_{1}^{♯}} ∘ m_{1}. Since η is natural, this is equivalent to f = α_{C} ∘ η_{C} ∘ f which, for X = C and f = 1_{C} yields satisfaction of the 𝕋-algebra axiom α_{C} ∘ η_{C} = 1_{C}. Conversely, α_{C} ∘ η_{C} = 1_{C} yields f = α_{C} ∘ η_{C} ∘ f by composition with f. Thus, the satisfaction of E_{1} is equivalent α_{C} ∘ η_{C} = 1_{C}.

Next we define a class E_{2} of equation arrows as follows: for every C-object X let d_{X}: X + T X_{2}^{♯} = X_{3}^{♯} → D_{X} be a coequalizer of the pair n_{3} ∘ T m_{2} ∘ μ_{X}, n_{3} ∘ T n_{2} ∘ T^{2}m_{1}.

\xymatrix{ & T X \ar[dr]^{T m_{2}} \\ T^{2}X \ar[ur]^{μ_{X}} \ar[dr]_{T^{2}m_{1}} &  & T X_{2}^{♯} \ar[r]^{n_{3}} & X + T X_{2}^{♯} \ar[r]^{d_{X}} & D_{X} \\  & T^{2}X_{1}^{♯} \ar@{-->}[ur]_{T n_{2}}}

A T -algebra (C, α_{C}) satisfies d_{X} iff, for every morphism f: X → C, the morphism

f_{3}^{♯} = [α_{C} ∘ T [α_{C} ∘ T f_{1}^{♯}, f], f]: T X_{2}^{♯} + X → C

satisfies f_{3}^{♯} ∘n_{3} ∘T n_{2} ∘T^{2}m_{1} = f_{3}^{♯} ∘n_{3} ∘T m_{2} ∘μ_{X}. This is equivalent to α_{C} ∘T α_{C} ∘T^{2}f = α_{C} ∘ T f ∘ μ_{X} or, since μ is natural, to α_{C} ∘ T α_{C} ∘ T^{2}f = α_{C} ∘ μ_{C} ∘ T^{2}f. Choosing f = 1_{C} this yields satisfaction of the 𝕋-algebra axiom α_{C} ∘ T α_{C} = α_{C} ∘ μ_{C}. Conversely, α_{C} ∘ T α_{C} = α_{C} ∘ μ_{C} yields α_{C} ∘ T α_{C} ∘ T^{2}f = α_{C} ∘ μ_{C} ∘ T^{2}f by composition with T^{2}f. Thus, the satisfaction of E_{2} is equivalent to α_{C} ∘ T α_{C} = α_{C} ∘ μ_{C}.

Chosing E = E_{1} ∪ E_{2} one thus gets C^{𝕋} = Alg(T, E).

5.12 Example (infinitary universal algebra) Generalizing the finitary Ω–algebras of 1.5(2), we introduce here a large signature as a collection Ω = (Ω_{n})_{n∈card} of sets Ω_{n} (of n–ary operation symbols) indexed by cardinal numbers n. An Ω–algebra is a set A together with an n–ary operation ω_{A}: A^{n} → A for all n ∈ card and ω ∈ Ω_{n}. We denote by Ω–Alg the category of all Ω–algebras and homomorphisms. Well, strictly speaking, this is not a category (having ”too many” objects) but a quasicategory: if Ω_{n} ≠ ∅ for arbitrarily large cardinal numbers n, then the collection of all Ω–algebras on the set {0, 1} is already a proper class. However, we are actually interested in varieties of Ω–algebras, and those are legitimate categories, as we show below.

The concept of Ω–terms over a set X of variables (disjoint from any Ω_{n}) is introduced as usual: the class T_{Ω}X of all terms is the smallest class containing X and containing ω(t_{i})_{i<n} for any n ∈ card, ω ∈ Ω_{n}, and t_{i} ∈ T_{Ω}X for i < n. Computation of terms in an Ω–algebra A is also standard: given f: X → A, extend it to f^{♯}: T_{Ω}X → A by f^{♯}(ω(t_{i})_{i<n}) = ω_{A}(f^{♯}(t_{i}))_{i<n}. If Ω is small, then T_{Ω}X is a free Ω–algebra on X, if Ω is large, no such free algebra over X exists (even for X = 1). By a variety of Ω–algebras we mean an equationally defined full subcategory V of Ω–Alg having free algebras, i.e., such that the obvious forgetful functor U: V → Set has a left adjoint.

Although Ω–Alg is, for Ω large, not expressible by any functor (because Alg(F) is a category for any F, and Ω–Alg is not), every variety V of Ω–algebras is a monadic category over Set. This follows from Beck’s theorem, see the argument in (Mac Lane 1971, VI.8).

By dualizing the above results, using 1.4, we obtain the following result, where quotients of a coalgebra A are represented by epimorphisms e: A → B in Coalg(F), and coretractcarried subcoalgebras of A are carried by monomorphisms in Coalg(F) which split in C. Regular subcoalgebras are subcoalgebras represented by regular monomorphisms.

5.13 Theorem (Birkhoff Covariety Theorem.) Let C be a cocomplete, regularly wellpowered category with coregular factorizations. For every constructive covarietor F preserving regular monomorphisms, covarieties of F –coalgebras are precisely the full subcategories of Coalg(F) closed under

i. coproducts, ii. quotient coalgebras, and iii. coretract-carried subcoalgebras.

5.14 Regular subcoalgebras of A in Coalg(F) are those B in Coalg(F) which admit a regular monomorphism m: B → A. For C = Set the regular subcoalgebras in Coalg(F) are precisely those carried by monomorphisms in Set (i.e., the “subcoalgebras” in the usual sense; monomorphisms are more general in Coalg(F)!); this follows from 4.18 if F preserves monomorphisms, since equalizers of cokernel pairs of functions f: B → A with B ≠ ∅ in Set are absolute, i.e., preserved by every functor (and every empty homomorphism (∅, α_{∅}) → (A, α_{A}) is an equalizer of the two coproduct injections of (A, α_{A}) + (A, α_{A})). If F does not preserve monomorphisms, apply 4.21.

Thus, since every covariety contains the empty coalgebra, the following corollary is an immediate consequence of 5.13 for functors F which preserve monomorphisms; if F does not preserve monomorphisms, apply again 4.21.

Corollary For every covarietor F over Set, covarieties of F –coalgebras are precisely the full subcategories closed in Coalg(F) under coproducts, regular subcoalgebras, and quotient coalgebras.

5.15 Corollary Under the assumptions of Birkhoff Covariety Theorem, covarieties of F -coalgebras are precisely the projectivity classes of regular subcoalgebras of cofree F – coalgebras.

5.16 Corollary For a covarietor F over Set, covarieties of F –coalgebras are precisely the projectivity classes of regular subobjects of regular injectives in Coalg(F).

5.17 For the sake of completeness we recall the following result of (Gumm 1999); note that this is not the dual of 5.6 (though embeddings of subcoalgebras are precisely the regular monomorphisms)!

Let C be a covariety of F -coalgebras for a bounded Set-functor. Then C is the projectivity class of a single embedding of a subcoalgebra into a cofree F -coalgebra.

As mentioned in the introduction, this is the type of characterization of covarieties studied by Rutten, Gumm and others.

5.18 Example Given a category Vec_{k} of vector spaces over a field k denote by F the endofunctor of Vec_{k} sending a space V to k × (V ⊗ V). F is a constructive covarietor (see (Porst 2001)). k–coalgebras in the traditional sense (see e.g. (Sweedler 1969)) obviously form a full subcategory of Coalg(F). By straightforward diagram chasing one can prove that this subcategory satisfies the condition of the Birkhoff Covariety Theorem 5.13 (see (Porst 2001)). Thus the category of k–coalgebras is a covariety of F –coalgebras.

5.19 Comonadicity Theorem Let C be a complete category. Then comonadic categories over C are, up to concrete equivalence, precisely the covarieties.

While the last theorem shows that the dual of a covariety over Set is a variety over Set^{op} it moreover implies the following additional dualization principle:

5.20 Proposition The dual of a covariety over Set is equivalent to a variety over Set.

Proof. Let C be a covariety over Set with underlying functor U. By means of the contravariant power-set functor P′ the category Set^{op} is monadic over Set. Let V : C → Set be the composite of U^{op} and P′. We need to show that V is monadic. Since V has a left adjoint and creates limits it suffices to prove that V creates coequalizers of congruence relations (= kernel pairs). Hence let r, s: (C, α_{C}) → (D, α_{D}) be a pair of C-morphisms such that V r, V s is a congruence relation and let q: P′(D) → X be its coequalizer. Since P′ reflects congruence relations and creates their coequalizers there is a unique Set^{op}-morphism q′: D → X′ with P′(q′) = q and this is a coequalizer of the congruence relation Ur, Us. If X′ ≠ ∅ this will even be a split coequalizer such that U creates from it a coequalizer of r, s. The remaining case X′ = ∅ is trivial: the unique F -coalgebra structure on ∅ obviously does the job.

6. Conclusions and Future Research

As mentioned in the introduction, our paper has been inspired by a number of interesting articles devoted to covarieties of coalgebras in the category Set. We have somehow felt that we missed a “beginning of the story”: whereas the concept of a variety has been inspired by examples such as groups and lattices, and developed further through Birkhoff’s classical variety theorem to the more general categorical concepts, in the realm of coalgebras all this has been missing. In the process of asking ourselves what the analogue of equations of universal algebra for coalgebras is we have, to our surprise, observed that the situation is not clear enough for varieties either: the equivalence between (infinitary) varieties and monadicity over Set did not seem to have an adequate formalization over other categories. This has led us to the concept of equation based on the free–algebra construction for a functor F that, in fact, does not have free algebras. The fact that, then, the slogan

varietal = monadic

holds for all cocomplete categories seems to support our approach.

To dualize the story, and to get the concepts of coequation and covariety so that the slogan

covarietal = comonadic

holds in complete categories has been an easy way to the original goal of our paper. But then we were surprised of how scarce the concrete examples of covarieties in literature were. In the present paper we have shown a number of natural examples of covarieties. Some of them, e.g., reflexivity and symmetry for transition systems, are somehow reminiscent of modal logic, but we have not pursued this in any way.

In order to prove an analogue of Birkhoff’s (Co) Variety Theorem much more than just limits and colimits needs to be assumed. But we hope that the side conditions presented in our paper are close to the minimum of what one should request. It would be worthwhile to supplement the results above with counter–examples demonstrating that this or that of the side conditions is indispensible.

Our paper is an extension and refinement of the extended abstract (Adámek and Porst 2001) except that the last part of that abstract, in which

accessible = bounded

is proved for all set functions has been omitted. The reason is that we are preparing a paper (Adámek and Porst) devoted to the properties of the categories of coalgebras on accessible functors, where this result fits much better. (The main property is that if F is λ–accessible then F –algebras form a λ–accessible category; this holds “almost” but not quite).

References

Aczel, P., Adámek, J., Milius, S. and Velebil, J. (2002) Infinite trees and iteration theories: a

coalgebraic view. Submitted. Adámek, J. (1974) Free algebras and automata realizations in the language of categories. Com-

ment. Math. Univ. Carolinae 15, 589–602. Adámek, J. (1983) Theory of Mathematical Structures. D. Reidel Publ. Comp. Dordrecht. Adámek, J., Herrlich, H. and Strecker,G.E. (1990) Abstract and Concrete Categories. Wiley

Interscience. New York Adámek, J. and Koubek, V. (1995) On the greatest fixed point of a functor. Theor. Comp.

Science 150, 57–75. Adámek, J., Koubek, V. and Pohlová, V. (1972) The colimits in generalized algebraic categories.

Note Univ. Carolinae 13, 29–40. Adámek, J. and Porst, H.-E. (2001) From Varieties of Algebras to Covarieties of Coalgebras.

Electronic Notes in Theor. Comp. Sci. 44.

J. Adámek and H.–E. Porst 32

Adámek, J. and Porst, H.-E. On finitely and infinitely presentable coalgebras. In preparation. Adámek, J. and Rosický, J. (1994) Locally Presentable and Accessible Categories. Cambridge

University Press. Cambridge. Adámek, J. and Trnková, V. (1990) Automata and Algebras in Categories. Kluwer Acad. Publ..

Dordrecht Awodey, S. and Hughes, J. (2000) The coalgebraic dual of Birkhoff’s variety theorem. Tech.

Rep. CMU–PHIL–109, Carnegie–Mellon University, Pittsburgh, PA. Banaschewski, B. and Herrlich, H. (1976) Subcategories defined by implications. Houston J.

Math. 2, 149–171. Barr, M. (1993) Terminal coalgebras in well-founded set theory. Theoretical Computer Science

114, 299–315. Cîrstea, C. (2000) An algebra-coalgebras framework for system specification. Electronic Notes

in Theor. Comp. Sci. 33. Ghani, N., Lüth, C., de Marchi, F. and Power, J. (2001) Algebras, coalgebras, monads and

comonads. Electronic Notes in Theor. Comp. Sci. 44. Gumm, H. P. (1999) Elements of the general theory of coalgebras. Preprint. Gumm, H. P. and Schröder, T. (1998) Covarieties and Complete Covarieties. Electronic Notes

in Theor. Comp. Sci. 11. Gumm, H. P. and Schröder, T. (2001) Products of coalgebras. Algebra univers. 46, 163–185. Hales, A.W. (1964) On the non–existence of free complete Boolean algebras. Fund. Math. 54

(1964), 45–66. Herrlich, H. and Ringel C.M. (1972) Identities in categories. Can. Math. Bull. 15, 297–299. Kawahara, Y. and Mori, M. (2000) A small final coalgebra theorem. Theoretical Computer

Science 233, 129–145. Kurz, A. (2000) Logic for coalgebras and applications to computer science. Dissertation, Ludwig–

Maximilians–Universität, Munich. Lambek, J. (1968) A fixpoint theorem for complete categories. Math. Z. 103, 151–161. Lawvere, F.W. (1963). Functorial semantics of algebraic theories. PhD thesis, Columbia Uni-

versity. Mac Lane, S. (1971) Categories for the working mathematician. Springer. Berlin-Heidelberg-

New York. Manes, E. G. (1976) Algebraic Theories. Springer. New York. Porst, H.–E. (2001) Algebra, Coalgebra, and Dualization. Research Report 319/01(3). University

of South Africa. Reiterman, J. (1973) One more categorical model of universal algebra. Math. Z. 161, 137–146. Rutten, J.J.M.M. (2000) Universal Coalgebra: a theory of systems. Theoret. Comp. Sci. 249

(2000), 3–80. Sweedler, M. E. (1969) Hopf Algebras. Benjamin. New York. Worell, J. (2000) Terminal sequences of accessible endofunctors. Tech. Rep. Tr-02-00, Oxford.