                         CMCS’01 Preliminary Version

From Varieties of Algebras to Covarieties of Coalgebras

Jiří Adámek ^{1,2}

Department of Theoretical Computer Science Technical University of Braunschweig Braunschweig, Germany

Hans–E. Porst ^{3,4}

Department of Mathematics University of Bremen Bremen, Germany

Abstract

Varieties of F -algebras with respect to an endofunctor F on an arbitrary cocomplete category C are defined as equational classes admitting free algebras. They are shown to correspond precisely to the monadic categories over C. Under suitable assumptions satisfied in particular by any endofunctor on Set and Set^{op} the Birkhoff Variety Theorem holds. By dualization, covarieties over complete categories C are introduced, which then correspond to the comonadic categories over C, and allow for a characterization in dual terms of the Birkhoff Variety Theorem. Moreover, the well known conditions of accessibilitly and boundedness for Set-functors F, sufficient for the existence of cofree F -coalgebras, are shown to be equivalent.

Introduction

What is a variety? A classical answer is: an equationally presented class of finitary algebras (such as groups, lattices, etc). Less classical answer: an equationally presented class of algebras with infinitary operations of possibly unbounded arities (such as complete semilattices or compact Hausdorff spaces). The first, classical, case corresponds precisely to algebras of a finitary monad

1 Support under Project SMS No. 34-99141-301 is gratefully acknowledged.

2 Email: adamek@iti.cs.tu-bs.de

3 This paper was written during an extended stay of the second author at the Department of Mathematics of the University of Stellenbosch, whose hospitality is gratefully acknowledged.

4 Email: porst@math.uni-bremen.de

This is a preliminary version. The final version will be published in Electronic Notes in Theoretical Computer Science

                       URL: www.elsevier.nl/locate/entcs

Adámek and Porst

over Set. The latter one, then, to algebras of an arbitrary monad over Set. This, however, has nothing to do with Set as a base category: we are going to introduce equations for —and equational classes of—F -algebras, where F is an endofunctor on any cocomplete category C. Those equational classes that have free algebras are called varieties. They are proved to precisely correspond to monadic categories over C. Although this is a folklore fact, it seems that it has never been really formulated. Our formulation is based on the construction of free F -algebras as a colimit of “term-objects” (which, in general, diverges: we do not assume that free F -algebras exist) presented by the first author in [2]. Functors F for which free F -algebras exist are called varietors in [6]. For all varietors on Set (and all varietors on “reasonable” categories preserving regular epimorphisms) the Birkhoff Variety Theorem generalizes to the present context: varieties are precisely the full subcategories of Alg(F) which are closed under products, subalgebras and quotients.

What is a covariety? It is a simple but important observation that for every endofunctor on a category C the category Coalg(F) of all F -coalgebras is the dual of the category of F^{op}-algebras, where F^{op} is the endofunctor on C^{op} acting as F. Consequently, by simple dualization we obtain the concept of coequation and coequational class of coalgebras. Those coequational classes that have cofree coalgebras (i.e., which are varieties of F^{op}-algebras) are called covarieties. And, for complete base categories, those are precisely the comonadic categories. If F is a covarietor, i.e., if all cofree coalgebras exist, and C = Set or C is “reasonable” and F preserves regular monomorphisms, then covarieties are precisely the full subcategories of Coalg(F) which are closed under coproducts, quotients and subcoalgebras.

Covarieties—for bounded endofunctors on Set only—have been considered by various authors. The equivalence of our approach, when specialized to this particular case, to most of these concepts will be shown below.

Which Functors are (Co-)Varietors? Varietors on Set have been com-

pletely characterized in [6] by the existence of arbitrarily large fixed points. A full characterization of covarietors on Set is not known, but several sufficient conditions are known: M. Barr shows in [9] that every accessible functor is a covarietor, and Y. Kawahara and M. Mori [17] prove that every bounded functor has a final coalgebra (from which it follows that every bounded functor is a covarietor). In the present note we prove that accessibility is, in fact, equivalent to boundedness, and both are equivalent to F being small, i.e., a small colimit of hom-functors. This seems to be the first time that the implication accessible ⟹ small has been properly proved (but see e.g. P. Freyd [11], which contains this result implicitly).

1 Algebras and coalgebras with respect to a functor

Let F: C → C be an endofunctor of some category C. Categories Alg(F) and Coalg(F) are defined as follows.

Objects of Alg(F), called F -algebras (over C), are pairs (C, α_{C}) where C is a C-object and α_{C}: F C → C is a C-morphism. Morphisms f: (C, α_{C}) → (D, α_{D}) of Alg(F), called F -algebra homomorphisms, are C -morphisms f: C → D making the diagram

\xymatrix{F C \ar[r]^{F f} \ar[d]_{α_{C}} & F D \ar[d]^{α_{D}} \\ C \ar[r]_{f} & D}

commute.

Objects of Coalg(F), called F -coalgebras (over C), are pairs (C, α_{C}) where C is a C-object and α_{C}: C → F C is a C-morphism. Morphisms f: (C, α_{C}) → (D, α_{D}) of Coalg(F), called F -coalgebra homomorphisms, are C-morphisms f: C → D making the diagram

\xymatrix{C \ar[r]^{f} \ar[d]_{α_{C}} & D \ar[d]^{α_{D}} \\ F C \ar[r]_{F f} & F D}

commute.

Composition and identities in Alg(F) and Coalg(F) respectively are those of C.

Alg(F) and Coalg(F) are concrete categories over C in that they are equipped with canonical underlying functors

F U: Alg(F) → C and U_{F} : Coalg(F) → C

respectively^{5} .

The dual of a functor F: C → D is the functor F^{op}: C^{op} → D^{op} acting on objects and morphisms as F. With these notations one has

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

1. Coalg(F) = (Alg(F^{op}))^{op}

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

1.2 Example Let Ω be a signature in Birkhoff’s sense, i.e., Ω = (Ω_{n})_{n∈ℕ} is a countable family of sets Ω_{n}. We shall describe the category AlgΩ of Ω-algebras—up to a concrete isomorphism— as (Alg(F), U) for a functor F = F_{Ω} : Set → Set as follows:

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})).

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

Functors of the form F_{Ω} are called polynomial functors.

We collect a number of well known properties of categories of F -algebras in the case C = Set as follows:

1.3 Theorem For every endofunctor F of Set the following hold:

1. Alg(F) has all limits and these are created by U.

2. Alg(F) has all colimits. Those which are preserved by F are created by U.

3. Alg(F) has regular factorizations of homomorphisms; these are created by U.

1.4 Remark The above properties hold in more general situations than just over Set: as an inspection of the essentially standard proofs (see e.g. [3] or [6]) shows, the following properties of the category C = Set and the functor F respectively are needed only:

• C is complete, cocomplete, (regularly) co-wellpowered and has (regular epi, mono)-factorizations of homomorphisms.

• F preserves (regular) epimorphisms.

These conditions can be assumed to be satisfied in particular for every endofunctor on the category Set^{op}, too. One only has to recall the following result of V.Trnková (see [6, III.4.5-6]):

Every endofunctor F on Set either preserves monomorphisms, or there is a monomorphism-preserving functor F′ which coincides with F on all nonempty sets and functions, and F′∅ ≠ ∅ ≠ F ∅.

It follows that, concerning categories Alg(F) and Coalg(F) over Set, one always may assume that F preserves monomorphisms: Coalg(F) and Coalg(F′) are (concretely) isomorphic, while Alg(F) = Alg(F′) whenever F fails to preserve monomorphisms.

By means of Lemma 1.1 one thus gets by dualization the following properties of categories of F -coalgebras:

1.5 Theorem Let F be an endofunctor of Set. Then the following hold:

1. Coalg(F) has all colimits and these are created by U.

2. Coalg(F) has all limits. Those which are preserved by F are created by U.

3. Coalg(F) has regular factorizations for homorphisms; these are created by U.

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

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

2.2 Remark Free F -algebras on X for an object X (of “variables”) of C can be defined for all functors F: C → C as pairs 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 commutes.

\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}

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

2.3 Lemma Let F: C → C be a functor where C has finite coproducts and X a C-object. The following are equivalent for a morphism ι_{X}: X + F I_{X} → I_{X} with components η_{X}: X → I_{X} and α_{X}: F I_{X} → I_{X}.

(i) (I_{X}, ι_{X}) is the initial algebra of type X + F (−). (ii) (I_{X}, α_{X}) is the free F -algebra on X with universal morphism η_{X}.

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

This is Lambek’s Lemma (saying that initial F -algebras are fixed points of F) applied to F_{X} = X + F (−).

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 ([6]) 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. If, more generally, C has 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 [2]): 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}!} F^{3}0 ⋯

to the functor F_{X} = X + F (−) (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 ⟶^{!}X + F 0 ⟶^{X+F!} X + F (X + F 0) ⟶^{X+F (X+F!)} (X + F (X + F (X + F 0)) ⋯

That is:

• X_{0}^{♯} = 0, X_{1}^{♯} = X + F 0 = X + F X_{0}^{♯} and x_{0,1}^{♯} = 0 ⟶^{!}X + F 0 is the unique morphism

• X_{i+1}^{♯} = X + F X_{i}^{♯} and x_{i+1,j+1}^{♯} = X + F x_{i,j}^{♯} for all i ≤ j

Claim: If F —and thus X + F —preserve a colimit X^{♯} = colim_{i<ω}X_{i}^{♯} of the above chain, then X^{♯} is a free F -algebra on X. More detailed: suppose (X_{i}^{♯} ⟶^{x_{i}} X^{♯}) is a colimit cocone. If X + F preserves that colimit we have a unique morphism

φ_{X}: X + F X^{♯} → X^{♯} with φ_{X} ∘ (X + F x_{i}) = 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}^{♯} = [f, α_{C} ∘ F f_{i}^{♯}]

Then the (unique) factorization X_{i}^{♯} ⟶^{x_{i}} X^{♯} ⟶^{f^{♯}} C = f_{i}^{♯} gives the (unique) homomorphism f^{♯}:(X^{♯}, α_{X}) → (C, α_{C}) with f = f^{♯} ∘ η_{X}. ◇ 2.8 Examples 1. For the endofunctor F Y = 1 + Y × Y (i.e., one constant

and one binary operation) on Set, we know that the terms in X_{i}^{♯} are just the binary trees of depths ≤ i 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 [2] or [6, 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:

• X_{0}^{♯} = 0, X_{1}^{♯} = X + F 0 with x_{0,1}^{♯} being the unique morphism 0 ⟶^{!} X + F 0

• X_{i+1}^{♯} = X + F X_{i}^{♯} for all ordinals i, x_{i+1,j+1}^{♯} = X + F x_{i,j}^{♯} for all i ≤ j

• X_{j}^{♯} = colim_{i<j}X_{i}^{♯} for all limit ordinals j with colimit cocone x_{i,j}^{♯}, i < j.

Claim: If the above chain construction stops after k steps, i.e, if k is an ordinal such that x_{k,k+1}^{♯}: X_{k}^{♯} → X + F X_{k}^{♯} is an isomorphism, then X_{k}^{♯} is a free F -algebra on X. More detailed: Denoting the inverse of x_{k,k+1} by φ_{X} with components

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

these form a free F -algebra on X. Proof Given an F -algebra (C, α_{C}) and a morphism f: X → C we define a cocone f_{i}^{♯}:X_{i}^{♯} → C (i an ordinal) by transfinite induction as above (leaving out the limit steps; compatibility f_{j}∘x_{i,j}^{♯} = f_{i} (i < j) implies that the f_{i} (i < j) determine f_{j} for limit ordinals j):

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

Now f_{k}^{♯}:X_{k}^{♯} → C is the unique homomorphism with f = f_{k}^{♯} ∘ η_{X}. ◇

2.10 Definition ([6]) A functor F: C → C is called constructive varietor provided that its Free-Algebra Construction 2.9 stops for each C-object X.

A functor can be a varietor, though the above chain-construction fails to stop for every X (see e.g. [6, IV.3.A]). However we have the following results:

2.11 An endofunctor F on a cocomplete category which preserves colimits of λ-chains for some infinite cardinal λ is a constructive varietor.

In fact, if F preserves X_{λ}^{♯} = colim_{j<λ}X_{j}^{♯}, then the free algebra construction stops after λ steps.

2.12 Theorem ([6, 4.3], [4]) Every varietor on each of the categories Set, Set^{op}, Vec_{k} ^{6} and Vec_{k}^{op} is a constructive varietor.

Calling an endofunctor F on Set trivial iff F is constant on nonempty sets one can prove (note that trivial endofunctors clearly are varietors):

2.13 Theorem ([6]) A non-trivial endofunctor F on Set is a (constructive) varietor iff F has arbitrarily large fixed points.

2.14 Cofree coalgebras are the corresponding dualization of free algebras. A cofree F -coalgebra (with respect to a functor F: C → C) on a C- object X (“of colours”) 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_{♯} extending f, i.e., such that the diagram

\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_{♯}}

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

2.15 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.1 and 2.3.

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

• F is a covarietor.

• F^{op} is a varietor.

In case C has finite products, another equivalent condition is:

• For every object X in C the functor F^{X} = X × F has a terminal (= final) coalgebra.

Dualization of the free-algebra construction above gives the following

2.17 Cofree Coalgebra Construction: Let C be a complete category. For every endofunctor F on C and every object X (“of colours”) in C define

6 This is the category of vector spaces over some field k.

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):

• X_{♯}^{0} = 1, X_{♯}^{i} = X × F 1 with x_{♯}^{1,0} : X × F 1 ⟶^{!}1 the unique morphism

• X_{♯}^{i+1} = X × F X_{♯}^{i} for all ordinals i, x_{♯}^{i+1,j+1} = X × F x_{♯}^{i,j} for all i ≥ j

• 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, if k is an ordinal such that x_{♯}^{k,k+1} : X × F X_{♯}^{k} → X_{♯}^{k} is an isomorphism, then X_{♯}^{k} is a cofree F - coalgebra on X. More detailed: Denoting the inverse of x^{k,k+1} by φ_{X}: X_{♯}^{k} → X × F X_{♯}^{k} with components

α_{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 by transfinite induction (leaving out the limit steps) as follows:

f_{♯}^{0} =! and f_{♯}^{i+1} = ⟨f, F f_{♯}^{i} ∘ α_{C}⟩.

2.18 Definition A functor F: C → C is called constructive covarietor provided that its Cofree-Coalgebra Construction 2.17 stops for each C-object X.

As the dual of Corollary 2.11 the following holds:

2.19 Corollary An endofunctor F on a complete category which preserves limits of λ-cochains for some infinite cardinal λ is a constructive covarietor.

2.20 Examples 1. Polynomial functors on Set are covarietors (here λ = ω).

2. Generalized polynomial functors on Set, i.e., functors F Y = ∑_{i∈I} Y^{C_{i}} for a given family (C_{i})_{i∈I} of (not necessarily finite) sets are covarietors (again, λ = ω).

3. Every endofunctor on Set which has arbitrarily large exponential fixed points (i.e., there are arbitrarily large sets X such that each set Y with cardX ≤ cardY ≤ card expX is a fixed point of F) is a covarietor (see [4]). Compare with Theorem 2.13.

3 Varieties and Covarieties

The following definition generalizes concepts from [1]:

3.1 Definitions Let F be an endofunctor of a cocomplete category C. Using the notation X_{i}^{♯} and f_{i}^{♯} as in 2.9 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) spanned by all F -algebras satisfying every e ∈ E. Such categories are called equational categories (of F -algebras) over C.

3. An equational category Alg(F, E) over C will be called a variety (of F - algebras) over C provided that the underlying functor

U_{E} = U|_{Alg(F,E)} : Alg(F, E) → C

has a left adjoint.

3.2 Remarks 1. Equations in classical (finitary) universal algebra are pairs of terms, i.e, parallel pairs of morphisms

u, v: 1 → X^{♯} = X_{ω}^{♯}

An algebra (C, α_{C}) satisfies this equation iff for every morphism f: X → C the unique homomorphism f^{♯} = f_{ω}^{♯} extending f merges u and v, i.e,

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

This is equivalent to the satisfaction, in the above sense, of the equation arrow e: X^{♯} → E which is a coequalizer of u and v.

In general, every pair of parallel morphisms (with C-objects A, X and an ordinal i)

u, v: A → X_{i}^{♯}

in C defines an equation arrow e: X_{i}^{♯} → E, a coequalizer of u and v. An algebra (C, α_{C}) “satisfies u = v” (in the expected sense: for every morphism f: X → C we have f_{i}^{♯} ∘ u = f_{i}^{♯} ∘ v) iff (C, α_{C}) satisfies e in the above sense.

2. If the base category C has kernel pairs, then, conversely, equation arrows can be substituted by parallel pairs: given a regular epimorphism e: X_{i}^{♯} → E, denote by u, v: A → X_{i}^{♯} a kernel pair of e. Then an algebra satisfies u = v iff it satisfies e.

Observe here that the index i can be upgraded arbitrarily: given a parallel pair u, v: A → X_{i}^{♯} and an ordinal j > i, put u′ = x_{i,j}^{♯}u and v′ = x_{i,j}^{♯}v. Then the equations u = v and u′ = v′ are satisfied by the same algebras.

3. Let C have kernel pairs and let F be a constructive varietor. It follows from 2. that all equations we have to consider are of the form

u, v: A → X^{♯}

for objects A, X in C: in fact, upgrade any given parallel pair to an ordinal j such that X^{♯} = X_{j}^{♯}. Here, the satisfaction of u = v by (C, α_{C}) means that for every f: X → C the unique homomorphism f^{♯}: (X^{♯}, φ_{X}) → (C, α_{C}) merges u and v. Since all homomorphisms h on (X^{♯}, φ_{X}) have the form h = f^{♯} (for f = h ∘ η_{X}), we see that (C, α_{C}) satisfies u = v iff hu = hv for all homorphisms h: (X^{♯}, φ_{X}) → (C, α_{C}). Thus we can, equivalently, work with equation arrows

e: X^{♯} → E

which are regular quotients, in C, of free F -algebras.

4. Suppose that F is a constructive varietor such that Alg(F) has coequalizers (e.g., whenever C has kernel pairs and regular factorizations of morphisms, is regularly cowellpowered and F preserves regular epimorphisms, see Remark 1.4). Then instead of regular epimorphisms e: X^{♯} → E in C we can work with regular epimorphisms in Alg(F). For that purpose recall the following notions:

(a) An object I in a category C is called injective w.r.t. a given morphism e: C → D provided that each morphism h: C → I factorizes over e:

\xymatrix{h: C \ar[r]^{e} \ar[dr]_{h} & D \ar@{-->}[d] \\  & I}

(b) Given a class E of homomorphisms, we denote by InjE the injectivity class of E, i.e., the full subcategory of Alg(F) spanned by all algebras injective w.r.t. each e ∈ E.

(c) The injectives w.r.t. all regular monomorphisms are called the regular injectives.

(d) The dual notions are (regular) projective and projectivity class ProjE. Now observe that for every equation u, v: A → X^{♯} we have a new

equation u^{♯}, v^{♯}: A^{♯} → X^{♯} which is satisfied by precisely the same algebras (C, α_{C}) (because, given a homomorphism h: (X^{♯}, φ_{X}) → (C, α_{C}), then (hu)^{♯} = hu^{♯} and (hv)^{♯} = hv^{♯}). Thus, if ē: (X^{♯}, φ_{X}) → (Ē, αĒ) denotes a coequalizer of u^{♯} and v^{♯} in Alg(F), then for every algebra (C, α_{C}) we have

(C, α_{C}) satisfies e ⟺ (C, α_{C}) is injective w.r.t. ē.

5. Consider the base category C = Set. It then follows from 4. that, for any

varietor F: Set → Set, every variety of F -algebras is specified by injectivity to regular epimorphisms of Alg(F) with regularly projective domains^{7} .

The converse is also true:

every class of F -algebras specified by injectivity to regular epimorphisms of Alg(F) with regularly projective domains is a variety.

In fact, consider such an epimorphism, e: (D, α_{D}) → (E, α_{E}), in Alg(F). Since 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 ē.)

This concept of equation and its satisfaction has already been considered by H. Herrlich and his co-authors in [16] and [8].

3.3 Example The power-set functor P on Set is not a varietor. However, we can consider equational categories of P-algebras. Complete semilattices are an example. In fact, the join-operation of a complete (upper) semilattice C is an arrow α_{C} : PC → C satisfying (i) α_{C}{x} = x, and (ii) α_{C} ⋃ M_{i} = α_{C}{α_{C}M_{i} | i ∈ I} for any collection M_{i} in PC. Conversely, every P-algebra satisfying (i) and (ii) is a (join operation of a unique) complete semilattice. Now (i) can be expressed by the equation arrow e: X_{2}^{♯} → E where X = {x} and e just merges x and {x}, whereas (ii) corresponds to the equation arrows f: X_{3}^{♯} → F where X is an arbitrary set and, for a given collection M_{i} in PX, f merges ⋃ M_{i} with {M_{i} | i ∈ I}. The homomorphisms are precisely the functions preserving all joins.

The following lemma—to be proven by an easy transfinite induction—will be used frequently:

3.4 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}^{♯}.

7 Every free F -algebra over Set is regularly projective by the axiom of choice.

3.5 Proposition Alg(F, E) is always closed in Alg(F) under

1. subalgebras and all limits which exist;

2. homomorphic images carried by split epimorphisms in C.

Proof 1. is trivial by an obvious diagonal fill-in argument.

2. Let r: (C, α_{C}) → (D, α_{D}) be a homomorphism with coretraction s in C, where (C, α_{C}) satisfies the equation arrow e: X_{i}^{♯} → E. Given f: X → D, one has r ∘ (s ∘ f)_{i}^{♯} = (r ∘ s ∘ f)_{i}^{♯} = f_{i}^{♯}. Thus, since (s ∘ f)_{i}^{♯} factorizes through e so does f_{i}^{♯}. ◇

3.6 Theorem Monadic categories over a cocomplete category C are precisely the categories concretely equivalent to varieties over C.

Proof I. Sufficiency: By Beck’s Theorem we have to verify that the underlying functor of a variety Alg(F, E) creates split coequalizers. Since Alg(F, E) is closed under quotients splitting in C, it suffices to prove that U: Alg(F) → C creates absolute coequalizers. This is proved exactly as in the proof of Becks’s Theorem (see [18]).

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}} X + T X_{i}^{♯} = 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}^{♯} = [f, α_{C} ∘ T f_{1}^{♯}]: X + T X_{1}^{♯} → 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}^{♯} = [f, α_{C} ∘ T [f, α_{C} ∘ T f_{1}^{♯}]]: X + T X_{2}^{♯} → 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 α_{C} ∘ T α_{C} = α_{C} ∘ μ_{C}.

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

3.7 Theorem Let C be a cocomplete, regularly co-wellpowered category with regular factorizations and kernel pairs. If F: C → C is a constructive varietor preserving regular epimorphisms, the following are equivalent for any full subcategory K of Alg(F):

(i) K is a variety. (ii) K is closed under subalgebras, products and homomorphic images carried

by split epimorphisms.

Proof In view of Proposition 3.5 we only have to show that (ii) implies (i). By Remark 1.4, Alg(F) has regular factorizations. Thus (ii) implies that K is a reΩective subcategory whose reΩection-arrows are regular epimorphisms in Alg(F), see [3, 16.8]. Let now E be the class of all reΩection-arrows of free algebras. We claim K = InjE. Trivially each algebra in K is injective w.r.t. all reΩection arrows. Conversely, if (C, α_{C}) is injective w.r.t. the reΩection r of the free algebra (F, α_{F}) over C, then the homomorphic extension id_{C}^{♯} of the identity of C factors as id_{C}^{♯} = g ∘ r. This shows that g is—as a C-morphism— a retraction. Thus, (C, α_{C}) is a split-epi carried quotient of the K-reΩection of (F, α_{F}), hence belonging to K by hypothesis. Thus, K = InjE. From Remark 3.2.4 above we conclude that K is a variety. ◇

3.8 Corollary (Birkhoff Variety Theorem) For every varietor F on the category Set, varieties of F -algebras are precisely the full subcategories closed under products, subalgebras and homomorphic images.

3.9 Remark In the special case C = Set it suffices, in the proof of Theorem 3.7 above, to take as E the set of reΩection arrows of free algebras on sets of cardinality less than λ (λ a regular cardinal), provided that F preserves λ-directed colimits (see e.g. proof of [5, 3.9]).

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

3.10 Definitions Let F be an endofunctor of a complete category C.

1. An 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) is the full subcategory of Coalg(F) spanned by all F -coalgebras satisfying every m ∈ M. Such categories are called coequational categories (of F -coalgebras) over C.

3. A coequational category Coalg(F, M) will be called a covariety (of F - coalgebras) over C provided that the underlying functor

U^{M} = U|_{Coalg(F,M)} : Coalg(F, M) → C

has a right adjoint (that is, if Alg(F^{op}, M) is a variety over C^{op}).

By dualizing the respective results on equational categories and varieties we immediately obtain the following results.

3.11 Corollary Comonadic categories over a complete category C are precisely the categories concretely equivalent to covarieties over C.

3.12 Corollary (Birkhoff Covariety Theorem) For every covarietor F on the category Set, covarieties of F -algebras are precisely the full subcategories closed under coproducts, subalgebras and homomorphic images^{8} .

3.13 Remarks 1. Clearly, by duality, an equivalent condition for a full subcategory of Coalg(F) (over Set) to be a covariety is to be a projectivity class w.r.t. of some class of regular monomorphisms M with cofree codomains.

2. Moreover, as in the case of varieties over Set (see Remark 3.9), also covarieties of F -coalgebras over Set can be specified by projectivity w.r.t. a set of regular monomorphisms—in fact a single one—with cofree codomains, provided that the functor F preserves λ-directed colimits for some regular cardinal λ. This follows easily from the boundedness property (see Theorem 4.1 below) of these functors (see [20,12]). Note, however, that this observation cannot be obtained by dualization of Remark 3.9.

8 Observe that, in Coalg(F), the homorphic images are given by (plain) epimorphims while the embeddings of subalgebras are the regular monomorphisms.

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

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

Proof By means of the contravariant power-set functor P′ the category Set^{op} is monadic over Set. Let V : Coalg(F, M) → Set be the composite of (U^{M})^{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 Coalg(F, M)-morphisms sich that V r, V s is a congruence relation and let q: P′(D) → X be its coequalizer. Since P′ reΩects 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 U^{M}r, U^{M}s. If X′ ≠ ∅ this will even be a split coequalizer such that U^{M} creates from it a coequalizer of r, s. The remaining case X′ = ∅ is trivial: the unique F - coalgebra structure on ∅ obviously does the job. ◇

3.15 Remarks 1. Coequations and their satisfaction have the following simple interpretation in the case of coalgebras over Set: define, for every “coterm” x ∈ X_{♯}^{i}, the coequation [x] as the following embedding

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

A coalgebra (C, α_{C}) satisfies [x] iff x does not lie in the image of f_{♯}^{i}:C → X_{♯}^{i} for any colouring f: C → X. These are all the coequations needed: we can substitute an arbitrary coequation

m: M → X_{♯}^{i}

by the set of coequations {[x] | x ∈ X_{♯}^{i} \ m[M]}.

2. Various concepts of covariety of F -coalgebras—all restricted to the case of a bounded endofunctor on Set (thus, a varietor—see Section 4)—have already been discussed in the literature:

• subcategories of Alg(F) closed w.r.t. coproducts, subcoalgebras and homomorphic images ([20]).

• projectivity classes in Alg(F) w.r.t. collections of embeddings of subcoalgebras of cofree coalgebras ([13]).

• projectivity classes in Alg(F) w.r.t. collections of embeddings of subcoalgebras of regularly injective coalgebras ([14]^{9} , [7]). Theorem 3.12 (in connection with Remark 3.2) shows in particular that all of them are equivalent to the concept introduced here if specialized to bounded Set-functors.

9 Here, regular injectivity is called extension property

3. A more complicated concept of coequation appears in [10]; this probably is not equivalent to the one above.

4 Properties of Set-functors

Every endofunctor F of Set preserving colimits of λ-chains (or, equivalently, λfiltered colimits) for some regular cardinal λ is a varietor by 2.11. Such functors are called accessible, see [19]. An accessible functor is also a covarietor, as observed by M. Barr [9]. A different criterion is due to Y. Kawahara and M. Mori (see [17] or also [20] and [15]): recall that F is called bounded if there exists an infinite cardinal λ such that for every F -coalgebra (C, α_{C}) and every element x of C there is a coalgebra homomorphism h: (D, α_{D}) → (C, α_{C}) with x ∈ h[D] and cardD ≤ λ. We are going to prove that this, however, is equivalent to accessibility and both are equivalent to F being small, i.e., a small colimit of hom-functors:

4.1 Theorem For an endofunctor F of Set the following conditions are equivalent:

(i) F is small; (ii) F is accessible; (iii) F is bounded.

Proof I. Suppose first that the given endofunctor F preserves finite intersections (i.e., pullbacks of monomorphisms).

(iii) ⟹ (i): For the above cardinal λ let D be the (essentially small) category of all pairs (X, x) where X is a set of cardinality ≤ λ and x ∈ F X, with morphisms f : (X, x) → (X′, x′) all functions f : X′ → X with F f(x′) = x. We prove that F is a colimit of the diagram V : D → [Set, Set] where V (X, x) = hom(X, −) with the colimit cocone f_{(X,x)} having components

f_{(X,x)}^{Y}: hom(X, Y) → F Y, q ⟼ F q(x) for all q: X → Y.

That is, we prove that for every set Y

(a) the maps f_{(X,x)}^{Y} are collectively epimorphic, and

(b) whenever f_{(X,x)}^{Y}(q) = f_{(X′,x′)}^{Y}(q′) then q is connected with q′ by a zig–zag in the diagram of elements of V composed with the evaluation–at–Y, eval_{Y} : [Set, Set] → Set.

Proof of (a): Given y ∈ F Y, for the coalgebra (Y, const(y)) there exists a homomorphism h : (D, α_{D}) → (Y, const(y)) with card D ≤ λ which fulfills D ≠ ∅ if Y ≠ ∅. For Y ≠ ∅ choose d_{0} ∈ D, then (D, d) ∈D with d = α_{D}(d_{0})

f_{(D,d)}^{Y}(h) = F h(α_{D}(d)) = const(y) · h(d) = y. The case Y = ∅ is trivial since (Y, y) ∈D.

Proof of (b): We have F q(x) = F q′(x′) for some q: X → Y and q′: X′ → Y. Factor q as an epimorphism e: X → Z followed by a monomorphism m: Z → Y and put z = F q(x); analogously e′, m′, and z′. By assumtion, F preserves the pullback

\xymatrix{ & P \ar[dr]^{u′} \ar[dl]_{u} \\ Z \ar[dr]_{m} &  & Z′ \ar[dl]^{m′} \\  & Y}

The equality F m(z) = F q(x) = F q′(x′) = F m′(z′) thus guarantees that there exists p ∈ F P with z = F u(p) and z′ = F u′(p′). And since cardP ≤ card(Z × Z′) ≤ card(X × X′) ≤ λ^{2} = λ, we obtain an object (P, p) of D with morphisms

(X, x) ⟵^{q} (Z, z) →^{u} (P, p) ⟵^{u′} (Z′, z′) →^{q} (X′, x′)

forming the desired zig-zag.

(i) ⟹ (ii): Every hom–functor is accessible, and a small colimit of accessible functors is accessible, see [11].

(ii) ⟹ (iii): Let F preserve λ–filtered colimits for some regular cardinal λ. Since every set is a λ–filtered colimit of all subsets of cardinality less than λ, we see that

(∗) given sets C and T ⊆ F C with card T < λ there exists a subset m: B ↪ C with cardB < λ and T ⊆ F m[F B].

We prove that F is bounded: given (C, α_{C}) and x ∈ C define a λ–chain m_{i}: B_{i} ↪ C (i < λ) of subsets of cardinality less than λ by transfinite induction as follows:

• B_{0} = {x};

• given B_{i}, apply (∗) to T = α_{C}[B_{i}] to get m_{i+1} : B_{i+1} → C with m_{i} ⊆ m_{i+1}, α_{C}[B_{i}] ⊆ F m_{i+1}[F B_{i+1}], and cardB_{i+1} < λ;

• given a limit ordinal i define B_{i} = ⋃_{j<i} B_{j} – due to the regularity of λ, if

cardB_{j} < λ for all j < i, then cardB_{i} < λ.

Define D = ⋃_{i<λ} B_{i} and h = colim m_{i}: D → A, then since F preserves the

colimit D = colimB_{i}, and since α_{C}[B_{i}] is contained in the image of F m_{i+1} for each i < λ_{i} we see that α_{C}[D] is contained in the image of F h. Thus, we have α_{D}: D → F D for which h: (D, α_{D}) → (C, α_{C}) is a coalgebra homomorphism. And cardD ≤ ∑_{i<λ} cardB_{i} = λ. Since x ∈ B_{0} ⊆ D, this proves that F is bounded.

II. For F: Set → Set arbitrary we use the result of V.Trnková (see [6, III.4.5-6]) that there exists a functor F′ preserving finite intersections and such that F X = F′X for all nonempty sets X (and F h = F′h for all nonempty functions h). It is easy to verify that F satisfies one of the properties (i)–(iii) iff so does F′. ◇

4.2 Example of a covarietor which is not small. Given a class M of cardinal numbers, define P_{M}: Set → Set on objects X by P_{M}X = {A ⊆ X; A = ∅ or cardA ∈ M} and an morphismus f: X → Y by P_{M}f(A) = f[A] if f/A is injective, else = ∅. Then P_{M} is small iff M is small ( = bounded). But every infinite set X with cardX ∉ M is, obviously, a fixed point of P_{M}. It is easy to find an unbounded class M for which P_{M} has arbitrarily large exponential fixed points (i.e., M is unbounded but has arbitrarily large ”exponential holes”). Then P_{M} is a varietor and covarietor but is not small.

References

[1] J. Adámek. Theory of Mathematical Structures. D. Reidel Publ. Comp., 1983. Dordrecht.

[2] J. Adámek. Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae 15 (1974), 589–602.

[3] J. Adámek, H. Herrlich, and G.E. Strecker, Abstract and Concrete Categories, Wiley Interscience, 1990. New York

[4] J. Adámek and V. Koubek. On the greatest fixed point of a functor. Theor. Comp. Science 150 (1995), 57–75.

[5] J. Adámek and J. Rosický. Locally Presentable and Accessible Categories. Cambridge University Press, 1994. Cambridge.

[6] J. Adámek and V. Trnková. Automata and Algebras in Categories. Kluwer Acad. Publ., 1990. Dordrecht

[7] S. Awodey and J. Hughes. The coalgebraic dual of Birkhoff’s variety theorem. Preprint.

[8] B. Banaschewski and H. Herrlich. Subcategories defined by implications. Houston J. Math. 2 (1976), 149–171.

[9] M. Barr. Terminal coalgebras in well-founded set theory. Theoretical Computer Science 114 (1993), 299–315.

[10] C. Cîrstea. An algebra-coalgebras framework for system specification. Electronic Notes in Theor. Comp. Sci. 33 (2000).

[11] P. Freyd. Several new concepts: lucid and concordant functors, prelimits, precolimits, lucid and concordant completions of categories. Lect. Notes Mathem. 99 (1969), 196–241. Springer,

[12] H. P. Gumm. Elements of the general theory of coalgebras. Preprint.

Adámek and Porst

[13] H. P. Gumm. Equational and implicational classes of coalgebras. Preprint.

[14] H. P. Gumm and T. Schröder. Covarieties and Complete Covarieties. Electronic Notes in Theor. Comp. Sci. 11 (1998).

[15] H. P. Gumm and T. Schröder. Products of coalgebras. Preprint.

[16] H. Herrlich and C.M. Ringel. Identities in categories. Can. Math. Bull. 15 (1972), 297–299.

[17] Y. Kawahara and M. Mori. A small final coalgebra theorem. Theoretical Computer Science 233 (2000), 129–145.

[18] S. MacLane. Categories for the working mathematician. Springer, 1971. Berlin-Heidelberg-New York.

[19] M. Makkai and R. Paré. Accessible categories: the foundations of categorical model theory. Contemporary Math., 104, 1989. Amer. Math. Soc., Providence.

[20] J.J.M.M. Rutten. Universal Coalgebra: a theory of systems. Report CS-R9652. CWI Amsterdam, 1996