Theory and Applications of Categories, Vol. 14, No. 18, 2005, pp. 424–450.

BIRKHOFF’S VARIETY THEOREM WITH AND WITHOUT FREE ALGEBRAS

To the memory of Jan Reiterman

JIŘÍ ADÁMEK, VĚRA TRNKOVÁ

Abstract. For large signatures Σ we prove that Birkhoff’s Variety Theorem holds (i.e., equationally presentable collections of Σ-algebras are precisely those closed under limits, subalgebras, and quotient algebras) iff the universe of small sets is not measurable. Under that limitation Birkhoff’s Variety Theorem holds in fact for F -algebras of an arbitrary endofunctor F of the category Class of classes and functions.

For endofunctors F of Set, the category of small sets, Jan Reiterman proved that if F is a varietor (i.e., if free F -algebras exist) then Birkhoff’s Variety Theorem holds for F -algebras. We prove the converse, whenever F preserves preimages: if F is not a varietor, Birkhoff’s Variety Theorem does not hold. However, we also present a nonvarietor satisfying Birkhoff’s Variety Theorem. Our most surprising example is two varietors whose coproduct does not satisfy Birkhoff’s Variety Theorem.

1. Introduction

Garrett Birkhoff characterized in 1935 varieties of finitary algebras; in his proof he used free algebras substantially. In the present paper we investigate the limitations of generalizations of Birkhoff’s result beyond “finitary” and, to a restricted extent, beyond “over Set”. Recall the original statement of Birkhoff’s Variety Theorem: a full subcategory of Alg Σ, the category of algebras on a finitary signature Σ, is presentable by equations iff it is closed under

(a) regular quotients,

(b) subobjects, and

(c) products

in Alg Σ. Well, this is not the original formulation: instead of full subcategory Birkhoff used classes of Σ-algebras, and he spoke about homomorphic images in (a), and subalgebras in (b). However, for algebras over Set it is well-known and easy to prove that

Both authors supported by the Czech Grant Agency under No. 201/02/0148; the second author supported also by MSM 0021620839.

Received by the editors 2005-08-22 and, in revised form, 2005-11-14. Transmitted by Walter Tholen. Published on 2005-12-18. 2000 Mathematics Subject Classification: 18C10. Key words and phrases: variety, Birkhoff’s Theorem. \begin{matrix}c \\ ◯ \end{matrix} Jiří Adámek, Věra Trnková, 2005. Permission to copy for private use granted.

regular epimorphisms are precisely the surjective homomorphisms, and subobjects are precisely the subalgebras. Notice also that in (c) above closure under limits may be felt as more “natural”—but in the presence of (b) this is equivalent to closure under products, of course. This fact is (dramatically) no longer true if we move from sets to classes, as we mention below.

There are good reasons for attempting to generalize Birkhoff’s Variety Theorem in Categorical Algebra: for some “juicy” examples of categories that we consider algebraic, e.g., the category Comp T_{2} of compact Hausdorff spaces, the corresponding signature is not finitary, and, in fact, it is not a small signature. There are two ways of dealing with this: we either substitute signatures by endofunctors of Set (e.g., for Comp T_{2} the canonical endofunctor to consider is the ultrafilter functor β, see Example 2.5 (iii) and 3.4) or we admit that a signature may be a class of operation symbols—and then we move from Set to Class, the category of classes. In the present paper we do both:

(1) For F -algebras where F is an endofunctor of Set we study the question of when Birkhoff’s Variety Theorem holds. Jan Reiterman observed that whenever F is a varietor, i.e., free F -algebras exist, then Birkhoff’s Variety Theorem holds. We prove the converse implication for all functors preserving nonempty preimages (which is a weak requirement fulfilled e.g. by all functors weakly preserving pullbacks): whenever such a functor is not a varietor than Birkhoff’s Variety Theorem does not hold for F -algebras. On the other hand, we present an example of a set functor which is not a varietor, although it satisfies Birkhoff’s Variety Theorem. A full characterization of all set functors for which Birkhoff’s Variety Theorem holds is an open problem. We also present varietors F and G such that Birkhoff’s Variety Theorem fails for F + G, where algebras of F + G are just “bialgebras” carrying a structure of an F -algebra as well as that of a G-coalgebra; we consider this to be very surprising.

(2) For endofunctors of Class, Birkhoff’s Variety Theorem (with closure under limits in (c) above) is proved to hold whenever the universe Set of small sets is not “too large”: what we need is the set-theoretical assumption that Set is not measurable. In fact, this assumption is also necessary: if Set is measurable then even Σ-algebras do not satisfy Birkhoff’s Variety Theorem for large signatures Σ.

Standard categorical concepts and facts used in the text without explanation can be found in Mac Lane [15] or Adámek-Herrlich-Strecker [5].

Acknowledgement. In his seminal dissertation entitled “Categorical Algebraic Constructions” [17] Jan Reiterman developed a theory of algebraized chains, and later he summarized the main ideas in his paper [18]. That paper was a basic inspiration for us: the reader will see that the part concerning endofunctors of Set uses ideas of [18] extensively. In particular, algebraized chains play a crucial role in the proof of the Main Theorem in Section 3.

2. Preliminary Facts About Set Functors

2.1. Throughout this section F denotes an endofunctor of Set, the category of small sets. We also use the notation

Set^{∗}

for the full subcategory of Set on all nonempty sets.

2.2. Fact. (See [20] or [9].) For every set functor F there exists a set functor F^{∗} preserving

(i) monomorphisms and

(ii) finite intersections (i.e., pullbacks of monomorphisms)

such that F^{∗} coincides on Set^{∗} with F.

2.3. Notation. We denote by C_{01} the functor with ∅ [figure]∅ and X [figure]1 for all nonempty sets X.

A natural transformation ϱ: C_{01} [figure] F is called a distinguished point of F. In 2.2 we can define F^{∗} by taking as F^{∗}∅ the set of all distinguished points (and, for f: ∅ [figure] X defining F^{∗}f by ϱ [figure] ϱ_{X}).

2.4. Remark. Recall from the survey paper [19] that in coalgebra one often works with set functors which preserve weak pullbacks (i.e. turn pullback squares to squares having the same factorization property except that factorizations need not be unique). We will use a weaker assumption: F preserve nonempty preimages, i.e., it preserve pullbacks along a monomorphism in Set^{∗}. The implication

weakly preserves pullbacks ⟹ preserves nonempty preimages

is easily verified: given a preimage

[figure: Y_{0}; Y; n; X_{0}; Y_{0}; f_{0}; X_{0}; X; m; X; Y; f]

with X_{0} ≠ ∅, then m is a split monomorphism, therefore, F m is a monomorphism. Thus, the F -image of the square, being a weak pullback, is a pullback.

2.5. Examples. (i) Preservation of weak pullbacks is a relatively weak assumption: the collection of all set functors preserving weak pullbacks is closed under

product (in particular power-to-n for any cardinal n)

coproduct, and

composition.

Since that collection contains the identity functor Id and the constant functors, it contains all the polynomial functors H_{Σ} where Σ is a signature: recall that H_{Σ} is given on objects X by

H_{Σ}X = ∐_{σ∈Σ} X^{n} n = arity of σ

and is thus a coproduct of limit-preserving functors.

(ii) Also the power-set functor 𝒫 weakly preserves pullbacks. Recall that 𝒫 is defined on objects X by 𝒫X = exp X and on morphisms f: X [figure] Y by 𝒫f: M [figure] f[M]. The composite functor 𝒫(Σ × −) whose coalgebras are the labelled transition system with action set Σ, see [19], consequently also preserves pullbacks.

(iii) Another example: the ultrafilter functor β defined on objects X by

βX = the set of all ultrafilters on X

and on morphisms f: X [figure] Y by

βf: 𝒰 [figure] {V ⊆ Y; f^{−1}(V) ∈ 𝒰 }

weakly preserves pullbacks. In fact, let

[figure: Z; T; g; X; Z; f̄; X; Y; ḡ; Y; T; f]

be a pullback. We are to show that given ultrafilters 𝒰 ∈ βY and 𝒱 ∈ βZ with βf(𝒰 ) = βg(𝒱 ), there exists an ultrafilter 𝒲 ∈ βX with βf̄(𝒲 ) = 𝒱 and βḡ(𝒲 ) = 𝒰 . Observe that the collection of all sets

D_{A,B} = f̄^{−1}(A) ∩ ḡ^{−1}(B)

with A ∈ 𝒱 and B ∈ 𝒰 fulfilling f[B] = g[A] is closed under finite intersections, and does not contain ∅. (In fact, choose C ∈ βf(𝒰 ) with f^{−1}(C) ⊆ B and g^{−1}(C) ⊆ A, then D_{A,B} contains the preimage of C.) Therefore, there exists an ultrafilter 𝒲 containing all D_{A,B}’s. It is easy to verify that 𝒲 is mapped to 𝒱 by βf̄ and to 𝒰 by βḡ.

2.6. Fact. Preservation of nonempty preimages is even weaker than preservation of weak pullbacks: The collection of all set functors preserving nonempty preimages is closed under

product,

coproduct, composition, and

subfunctor.

And the collection of all functors preserving weak pullbacks is its a proper subcollection. The proofs of the four closure properties are trivial and we omit them.

Recall from [1] the subfunctor (−)_{2}^{3} of the polynomial functor (−)^{3} assigning to every set X the subset X_{2}^{3} ⊆ X × X × X of all triples whose components are not pairwise distinct. Then (−)_{2}^{3} does not preserve weak pullbacks, but it does preserve nonempty preimages because (−)^{3} does.

2.7. Examples. (1) The polynomial functors, the power-set functor 𝒫 and the functor 𝒫(Σ × −) preserve weak pullbacks, thus, preserve nonempty preimages.

(2) Our insistence on “nonempty” is inspired by the fact that the implication

preserves weak pullbacks ⟹ preserves preimages

is false in general. A counterexample is C_{2,1}, taking ∅ to a two-element set and all nonempty sets to 1. This functor preserves weak pullbacks (obviously), but it does not preserve the preimage

[figure: 1; 1 + 1; inr; ∅; 1; ∅; 1; 1; 1 + 1; inl]

(where inl or inr denote the left and the right coproduct injections).

(3) A functor not preserving nonempty preimages: let D be the quotient of (−)^{2} modulo the diagonal. That is, on objects X we have DX = X × X/_{∼} where ∼ is the smallest equivalence relation with the diagonal △ ⊆ X × X as one class. For every function f: X [figure] 1 where X has at least two elements the functor D does not preserve the preimage

[figure: 1; 1 + 1; _{inl_{1}}; X; 1; f; X; X + X; ^{inl^{X}}; X + X; 1 + 1; f+f]

2.8. Remark. (i) Let us call a set functor preconstant if its restriction to the category Set^{∗} of all nonempty sets is naturally isomorphic to a constant functor. It follows from results of V. Koubek [13], see also 3.4.7 in [9], that every set functor F is either preconstant, or there exists a cardinal γ such that for every set X we have:

card X ≥ γ  implies  card F X ≥ card X.

(In [9] preconstant functors are called constant.)

(ii) Every set functor F is a coproduct

F = ∐_{s∈S} F_{s}

of indecomposable functors, called the components of F. (In fact, put S = F 1 and for s ∈ F 1 let F_{s}X ⊆ F X be the preimage of s under F t_{X} for the unique t_{X}: X [figure] 1. See [20] or [9] for more details.)

2.9. Lemma. Every component of a set functor preserving nonempty preimages is faithful or preconstant.

Proof. It is easy to see that a set functor preserves nonempty preimages iff every component does. Therefore, we can restrict ourselves to indecomposable set functor F (i.e., with card F 1 = 1).

Suppose that F is a non-faithful indecomposable functor preserving nonempty preimages. Every non-faithful set functor has a distinguished point φ: C_{01} [figure]F, see [20] or [9]. Consider the preimage as in 2.7 (3). (We denote by inl_{X} and inr_{X} the left and right coproduct injections X [figure] X + X.) Since F f is a constant function, it follows that F (f +f) maps both of the subobjects F inl_{X} and F inr_{X} onto the element φ_{1+1} ∈ F (1 + 1), and so does F inl_{1}. Thus, the preimage of F inl_{1} under F (f + f) contains F inr_{X}. However, this preimage is F inl_{X}, and since F is indecomposable, the intersection of F inl_{X} and F inr_{X} has one element. This proves that F X has one element. Thus, F is preconstant.

2.10. Remark. Faithful components G of any set functor preserve finite intersections, see [9]. In particular, they preserve disjointness of subobjects: if m_{1} : M_{1} [figure]X and m_{2} : M_{2} [figure] X are disjoint subobjects of X, then Gm_{1} and Gm_{2} are disjoint subobjects of GX.

3. Birkhoff’s Variety Theorem in Set

3.1. We work here with algebras in the category Set (of small sets) whose type is determined by an endofunctor F of that category. That is, an algebra is a set A equipped by a mapping α: F A [figure]A. Given algebras (A, α) and (B, β), a homomorphism is a function f: A [figure] B such that the square

[figure: F B; B; β; F A; F B; F f; F A; A; α; A; B; f]

commutes. These algebras were first studied by J. Lambek [14]. We denote the category of these algebras by Alg F.

3.2. Example. The classical Σ-algebras (for a signature Σ, i.e., a set Σ of operation symbols with prescribed arities which are arbitrary cardinals) are captured by the polynomial functor, see 2.5.

3.3. Example. The category Alg 𝒫 where 𝒫 is the power-set functor, see 2.5 (iii), contains e.g. the variety of complete join semilattices as a full subcategory: to every such semilattice A assign the function α: 𝒫A [figure]A of formation of joins, then 𝒫homomorphisms are precisely the functions preserving joins.

3.4. Example. As in 2.5 (iii), let β denote the ultrafilter functor. Then the category Alg β contains e.g. the category of compact Hausdorff spaces as a full subcategory: to every such space A assign the function α: βA [figure] A taking every ultrafilter to its unique limit point in A. Then β-homomorphisms are precisely the continuous functions (because, among compact Hausdorff spaces, these are precisely the functions preserving limit points of ultrafilters).

3.5. Example. Let F be a preconstant functor. Then Alg F is the category of Σ-algebras for a signature Σ consisting of nullary operation symbols, except that the empty algebra is possibly added.

In fact, a preconstant functor F with F ∅ = ∅ has the property that card F X = n, for X ≠ ∅, independent of X. Then Alg F is the category of algebras with n nullary operation symbols plus the empty algebra.

If a preconstant functor F fulfils F ∅ ≠ ∅ then Alg F contains only nonempty algebras; they are, again, just algebras on n nullary operations for the above n.

3.6. Definition. (See [9].) An endofunctor F is called a varietor if free F -algebras exist, i.e., if the forgetful functor of Alg F has a left adjoint.

3.7. Theorem. (See [21] and [9].) A set functor F is a varietor iff

(a) F has arbitrarily large fixed points (i.e., arbitrarily large sets X with F X ≅ X), or

(b) F is preconstant.

3.8. Example. H_{Σ} is a varietor, but neither 𝒫 nor β are.

3.9. Remark. (i) Let F be a varietor. By an equation is understood a pair (u, v) of elements in a free F -algebra ϕ(X) on set X (of variables). Notation: u = v.

An F -algebra A satisfies the equation u = v if for every map f: X [figure] A (“interpretation” of the variables in A) the corresponding homomorphism f^{#} : ϕ(X) [figure] A fulfills f^{#}(u) = f^{#}(v).

(ii) What do we mean by equations in case F is not a varietor? For a general endofunctor F a transfinite chain “approximating” the free algebra ϕ(X) has been defined in [2] (see also [9]). We denote this chain by

W (X): Ord [figure] Set

and call it the free-algebra chain. Its objects W_{i}(X) and connecting morphisms w_{i,j}: W_{i}(X) [figure]W_{j}(X) (for i ≤ j in Ord) are determined uniquely up-to natural isomorphism by the following rules:

a) W_{0}(X) = X and W_{1}(X) = X + F X; w_{0,1} : X [figure]X + F X is the coproduct injection,

b) W_{j+1}(X) = X + F W_{j}(X) and w_{i+1,j+1} = X + F w_{i,j} for all ordinals i ≤ j,

and

c) W_{j}(X) = colim_{i<j} W_{i}(X) with the colimit cocone (w_{i,j})_{i<j} for all limit ordinals j.

(iii) Given an F -algebra F A [figure: α] A and an interpretation f: X [figure] A of variables, we denote by f_{i}^{#} : W_{i}(X) [figure] A the unique cocone with

f_{0}^{#} = f  and f_{i+1}^{#} = [f, α·F f_{i}^{#}]: X + F W_{i}(X)  [figure] A.

(iv) By an equation u = v is meant a pair u, v ∈ W_{i}(X) for a set X of variables and an ordinal i.

The equation is called trivial if u and v is the same element of W_{i}(X). And it is called reduced if it is non-trivial, and u or v lies in the complement of ⋃_{j<i} w_{j,i}[W_{j}(X)].

3.10. Definition. We say that an algebra A satisfies an equation u = v (u, v ∈ W_{i}(X)) provided that for every map f: X [figure] A we have

f_{i}^{#}(u) = f_{i}^{#}(v).

By a variety of F -algebras is meant a full subcategory 𝒱 of Alg F which is equationally presentable (i.e., for which a class of equations exists such that 𝒱 consists of precisely all F -algebras satisfying each of the given equations).

3.11. Remark. Every non-trivial equation u = v, u, v ∈ W_{i}(X) determines a reduced equation u′ = v′ logically equivalent to it; an algebra satisfies u = v iff it satisfies u′ = v′. In fact, find the smallest j such that w_{j,i}(u′) = u and w_{j,i}(v′) = v for some u′, v′ ∈ W_{j}(X). Then u′ = v′ is reduced.

3.12. Remark. As proved in [21], for every varietor a free algebra on X always has the form W_{i}(X) for some ordinal i. Thus, the above concept of equation is, for varietors, just the usual one.

3.13. Example. Complete lattices. These can be canonically represented as a full subcategory of Alg(𝒫 + 𝒫 ): to every complete lattice A assign the function [join, meet]: 𝒫A+ 𝒫A [figure] A. Then homomorphisms in Alg(𝒫 + 𝒫 ) are precisely the functions preserving joins and meets.

This full subcategory is a variety of Alg(𝒫 + 𝒫 ). For example, the axiom join{x} = x is expressed by forming, for X = {x}, the elements u = x and v = ({x}, 1) in W_{1}(X) = X+𝒫X×{1, 2} (where 𝒫X×{1, 2} represents 𝒫X + 𝒫X ) and considering an equation u = v. Analogously for all other axioms expressing the fact that an abstract algebra α: 𝒫A + 𝒫A [figure] A has the form α = [join, meet] for a complete lattice on A. In this case we will need a proper class of equations.

3.14. Example. Monadic algebras. For every monad (T, η, μ) the category of Eilenberg-Moore algebras is a variety of Alg T. Conversely, whenever a variety of F -algebras has free algebras, then it is monadic. See [8] (where the terminology was slightly different: the concept of variety was called equational subcategory there).

3.15. Remark. (i) The above Definition 3.10 was introduced in [3].

(ii) Jan Reiterman uses (in [18]) algebraized chains, rather than the free-algebra construction, to define varieties (which he calls “equational varieties”). For the present case where the base category is Set he remarks (see his 3.3) that his concept is obviously equivalent to that of 3.10 above.

(iii) Whenever a free F -algebra X^{#} exists, then the free-algebra construction stops, i.e., w_{i,i+1} : W_{i} [figure]X + F W_{i} is an isomorphism for some i, and X^{#} = W_{i} (where the universal arrow X [figure]X^{#} and the algebra structure F X^{#} [figure]X^{#} form the components of w_{i,i+1}^{−1}).

Conversely, whenever the free-algebra construction stops after i steps, then it yields a free algebra X^{#} = W_{i}. See [21] or also [9].

3.16. Lemma. Every variety of F -algebras is closed in Alg F under regular quotients, subobjects and products.

The proof is trivial.

3.17. Definition. We say that a set functor F satisfies Birkhoff’s Variety Theorem if varieties of F -algebras are precisely the full subcategories of Alg F closed under regular quotients, subobjects, and products.

3.18. Examples. (See [18].)

(i) Every varietor in Set satisfies Birkhoff’s Variety Theorem.

(ii) The power-set functor does not satisfy Birkhoff’s Variety Theorem. In fact, a counter-example is the class of all 𝒫-algebras A for which there exists a cardinal α such that A satisfies u = v whenever u, v lie in W_{i}(X) but not in W_{α}(X) for some i > α. We use the same idea in the proof of the Main Theorem.

3.19. Example. For every small set 𝒜 of F -algebras the closure \overline{𝒜} of 𝒜 under products, subalgebras and regular quotient algebras is a variety.

To prove this, let 𝒜′ be a closure of 𝒜 under limits and subalgebras. Then the canonical forgetful functor U: 𝒜′ [figure]Set is a right adjoint. In fact, the category of F -algebras has small limits and large intersections created by its forgetful functor. Therefore, 𝒜′ has limits and large intersections, and U preserves them. Since 𝒜 is a small cogenerator of 𝒜′, the Special Adjoint Functor Theorem guarantees a left adjoint Φ_{𝒜} of U. Now \overline{𝒜} is the closure of 𝒜′ under regular quotient algebras, which implies that the algebras Φ_{𝒜} X are free on X in \overline{𝒜} (recall that epimorphisms split in Set). By Theorem 4.4 in [18] we conclude that \overline{𝒜} is a variety.

3.20. Example. All compact Hausdorff spaces, see 3.4, have the property that the trivial ultrafilter ẋ (of all sets containing x) converges to x. Thus, they satisfy the equation

x = ẋ for x, ẋ ∈ W_{1}(X) = X + βX.

In fact, compact Hausdorff spaces form a variety of β-algebras. This follows from the fact, established by E. Manes [16], that they are Eilenberg-Moore algebras of the well-known monad whose underlying functor is β, see 3.14.

3.21. Lemma. For every set functor and every set X ≠ ∅ of variables the connecting morphisms w_{i,j}: W_{i}(X) [figure] W_{j}(X) are always monomorphisms.

Proof. This follows easily by transfinite induction: in the isolated step

w_{i+1,j+1} = id_{X} +F w_{i,j}

use the fact that F w_{i,j} is a monomorphism since w_{i,j} is a split monomorphism (in fact, X ≠ ∅ implies W_{i}(X) ≠ ∅), and coproducts of monomorphisms in Set are monomorphisms. In the limit steps use the fact that

(a) a colimit cone w_{i,j}: W_{i}(X) [figure]W_{j}(X) (for i < j) of a chain of monomorphisms in Set is formed by monomorphisms, and

(b) the connecting morphism w_{j,j+1} : W_{j}(X) [figure] W_{j+1}(X) of a cone

W_{i+1}(X) = X + F W_{i}(X) [figure: id_{X} +F w_{i,j}] X + F W_{j}(X) = W_{j+1}(X)

of monomorphisms is a monomorphism.

3.22. Observation. (i) The free-algebra construction W_{i}(X) of 3.9 yields a chain of endofunctors W_{i} on Set. The definition of W_{i} on morphisms y: Y [figure] X is an obvious transfinite induction: W_{0}(y) = y and W_{i+1}(y) = y + F W_{i}(y).

(ii) Given an algebra A and two functions

Y [figure: y] X [figure: f] A,

then for every ordinal i we have

f_{i}^{#}·W_{i}(y) = (fy)_{i}^{#} : W_{i}(Y) [figure] A.

This is trivial to prove by transfinite induction.

In the isolated step we use the triangle

[figure: Y + F W_{i}(Y); A; [fy,α·F (fy)_{i}^{#}]; Y + F W_{i}(Y); X + F W_{i}(X); y+F W_{i}(y); X + F W_{i}(X); A; [f,α·F f_{i}^{#}]]

which commutes by the induction hypothesis. Limit steps just use the uniqueness of factorizations through colimit cones.

3.23. Main Theorem. For a set functor which preserves nonempty preimages the following conditions are equivalent:

(i) Birkhoff’s Variety Theorem holds for F -algebras, and

(ii) F is a varietor.

Proof. Let F preserve nonempty preimages. If it is not a varietor, then we find a class 𝒱 of F -algebras which is not a variety although it is closed under regular quotients, subalgebras, and products.

Given a cardinal α, we choose a set X of cardinality α and denote, for every i > α, by ∼_{i} the equivalence relation on W_{i}(X) given by

t ∼_{i} s iff t = s or t, s ∉ w_{α,i}[W_{α}(X)].

Denote by 𝒱_{α} the variety of F -algebras presented by all equations

u = v for u, v ∈ W_{i}(X) with i > α and u ∼_{i} v.

Observe that α ≤ β implies 𝒱_{α} ⊆ 𝒱_{β}. Consequently, since each 𝒱_{α} is closed under regular quotients, subalgebras and products, so is the union

𝒱 = ⋃_{α∈Card} 𝒱_{α}.

We now prove that 𝒱 is not a variety by verifying that

(a) for every nontrivial equation u = v there exists an algebra in 𝒱 which does not satisfy u = v

and

(b) 𝒱 is a proper subcategory of Alg F.

Proof of (a).

For every cardinal α > 0 choose a set X of cardinality α and denote by (W (X), p) the free algebra construction considered as an algebraized chain in the sense of [18], i.e., p is the collection p_{i}: F W_{i}(X) [figure]W_{i+1}(X) = X + F W_{i}(X) of the right coproduct injections. Define a quotient functor

e: W (X) [figure] \overline{W} (X)

of this functor W (X): Ord [figure]Set by the following rule: given an ordinal i then e_{i}: W_{i}(X) [figure]W_{i}(X)/_{∼_{i}} is the canonical quotient map of the above equivalence ∼_{i} on W_{i}(X). It is obvious that this defines a functor \overline{W} (X): Ord [figure] Set and a natural transformation e: W (X) [figure] \overline{W} (X). We will prove that this is a quotient object of the algebraized chain (W (X), p), i.e., that for every i ∈ Ord there exists p̄_{i} such that the square

[figure: F \overline{W}_{i}(X); \overline{W}_{i+1}(X); p̄_{i}; F W_{i}(X); F \overline{W}_{i}(X); F e_{i}; F W_{i}(X); X + F W_{i}(X) = W_{i+1}(X); p_{i}; X + F W_{i}(X) = W_{i+1}(X); \overline{W}_{i+1}(X); e_{i+1}]

commutes. Here it is where our assumption that F preserves nonempty preimages is applied. For i ≤ α there is nothing to prove; also all i > α with W_{i}(X) = w_{α,i}[W_{α}(X)] are obvious: in this case, e_{i} is a bijection hence F e_{i} is also a bijection. In the remaining case, i.e. i > α and W_{i}(X) ⊋ w_{α,i}[W_{α}(X)], we have a canonical isomorphism r: W_{α}(X) + 1

[figure] \overline{W}_{i}(X) such that the square

[figure: W_{α}(X) + 1; \overline{W_{i}(X)}; r; W_{α}(X); W_{α}(X) + 1; inl; W_{α}(X); W_{i}(X); w_{α,i}; W_{i}(X); \overline{W_{i}(X)}; e_{i}]

commutes (where inl denotes the left coproduct injection). Here we can observe that W_{α}(X) ≠ ∅ (because α > 0 and X has cardinality α) and the above square is a preimage. Consequently, the F -image of that square is a preimage. This clearly implies that whenever F e_{i} merges two distinct elements of F W_{i}(X), then they both lie outside F w_{α,i}[F W_{α}(X)], i.e., as elements of W_{i+1}(X) they are equivalent (under ∼_{i+1}). Consequently, e_{i+1}·p_{i} merges such elements too. This proves the existence of p̄_{i} above.

Thus, we define an algebraized chain (\overline{W} (X), p̄) which is a quotient of the free-algebra chain, and is stationary (i.e., the connecting morphisms of \overline{W} (X) are, from some ordinal on, isomorphisms). From 3.9 in [18] we conclude that the chain (\overline{W} (X), p̄) has a reflection A^{α} in the full category Alg F. This F -algebra A^{α} lies in the variety 𝒱_{α} and does not satisfy any non-trivial equation u = v with u, v ∈ W_{i}(Y) for any set Y with card Y ≤ α and any ordinal i ≤ α. See the detailed argument of Example 4.6 in [18] (formulated for the power-set functor, but valid generally). Since α was any cardinal, this proves the claim (a).

Proof of (b).

We construct a set D and an F -algebra on it, denoted also by D, such that for every ordinal α there exists an ordinal i > α and elements

t_{1}, t_{2} ∈ W_{i+1}(D) − w_{α,i+1}[W_{α}(D)]  (1)

such that

D does not satisfy t_{1} = t_{2},  (2)

This proves D ∉ 𝒱_{α}. Consequently, D lies in Alg F − 𝒱 .

From Lemma 2.9 we know that F = G + H where

G has all components faithful

and

H is preconstant.

It follows that

G preserves disjointness of subobjects,  (3)

see Remark 2.10. Next, there exists an infinite cardinal γ such that for every set X we have

card X ≥ γ  implies  card GX > card X.  (4)

In fact, since H is preconstant and F is not a varietor, it follows from Theorem 3.7 that G is not a varietor; i.e., it does not have arbitrarily large fixed points. On the other hand, since G is faithful, for every set X ≠ ∅ we have card GX ≥ card X, see [9]—thus,

(4) follows. Since H is preconstant, we can choose the above γ so that

card X ≥ γ  implies  card F X = card GX.  (5)

Moreover, from (4) we conclude that

card X ≥ γ  implies  card W_{i}(X) < card W_{i+1}(X) for all i ∈ Ord.  (6)

In fact, we have W_{i+1}(X) = X + F W_{i}(X) and we can apply (4) to W_{i}(X) in place of X (since by 3.21 card W_{i}(X) ≥ card X ≥ γ). Finally observe that 3.21 and (4), (5) yield that

card X ≥ γ  implies  card W_{i+1}(X) = card F W_{i}(X).  (7)

Choose a set Z of cardinality γ. We define an F -algebra on the coproduct

D = Z + Z  with injections u_{l}, u_{r}: Z  [figure] D

for which we prove that the identity function f = id_{D} has for every ordinal i the following property:

the preimages of u_{l} and u_{r} under f_{i+1}^{#} : W_{i+1}(D) [figure] D have cardinalities at least card W_{i+1}(D).

(8)

We then derive D ∉ 𝒱_{α} by choosing t_{1} in the preimage of u_{l} under f_{i+1}^{#} and t_{2} in the preimage of u_{r}. It follows that f_{i+1}^{#} does not merge t_{1} and t_{2}, consequently, (2) follows. And from (6) we derive that card W_{i+1}(D) > card W_{α}(D), therefore we can choose t_{1}, t_{2} so that (1) holds.

Due to (3) there exists an algebra structure δ: F D [figure]D for which the following diagram

[figure: GD; F D; inl; F D; D; δ; GZ; GD; G_{u_{l}}; GZ; Z; v_{l}; Z; D; u_{l}; GZ; GD; G_{ur}; GZ; Z; v_{r}; Z; D; u_{r}]

commutes, where v_{l}, v_{r} are arbitrarily chosen and inl denotes the left coproduct injection GD [figure] F D = GD + HD. This algebra fulfils (8) for all ordinals i: The proof for u_{l} will be performed by transfinite induction on i. The proof for u_{r} follows by symmetry.

First step: this follows from our choice of Z and of f = id above.

Isolated step: we have, by induction hypothesis, subobjects

m_{l}: M_{l}  [figure] W_{i}(D) and m_{r}: M_{r}  [figure] W_{i}(D)

such that f_{i}^{#}·m_{l} factorizes through u_{l} and f_{i}^{#}·m_{r} through u_{r}:

[figure: Z; D; u_{l}; M_{l}; Z; p_{l}; M_{l}; W_{i}(D); m_{l}; W_{i}(D); D; f_{i}^{#}; D; Z; u_{r}; W_{i}(D); D; W_{i}(D); M_{r}; m_{r}; M_{r}; Z; p_{r}]

and card M_{l} = card M_{r} = card W_{i}(D). From this we prove that the preimage of u_{l} under f_{i+1}^{#} has cardinality card W_{i+1}(D), analogously for u_{r}. In fact, consider the following subobject of W_{i+1}(D)

GM_{l} [figure: Gm_{l}] GW_{i}(D) [figure: inl] F W_{i}(D) [figure: inr] W_{i+1}(D)

(with inl or inr being the left or the right coproduct injections) whose cardinality is, due to (5) and (7),

card GM_{l} = card F M_{l} = card F W_{i}(D) = card W_{i+1}(D).

This subobject when composed with f_{i+1}^{#} = [f, δ·F f^{#}] factorizes through u_{l}:

[figure: GZ; GD; Gu_{l}; GM_{l}; GZ; Gp_{l}; GM_{l}; GW_{i}(D); Gm_{l}; GW_{i}(D); GD; Gf_{i}^{#}; GD; F D; inl; GW_{i}(D); GD; GW_{i}(D); F W_{i}(D); inl; F W_{i}(D); F D; F f_{i}^{#}; F W_{i}(D); W_{i+1}(D); inr; GZ; Z; v_{l}; Z; D; u_{l}; F D; D; δ; W_{i+1}(D); D; f_{i+1}^{#}]

Limit step: for every limit ordinal i the preimage of u_{l} under f_{i}^{#} = colim_{j<i} f_{j}^{#} is a colimit of the subchain of W_{j}(D) (j < i) formed by the preimages of u_{l} under f_{j}^{#} (j < i)

— in fact, pullbacks commute with chain colimits in Set. The cardinality of the colimit of all preimages of u_{l} is, by induction hypothesis, the supremum of card W_{j}(D) for j < i, and this is precisely card W_{i}(D).

3.24. Corollary. For a functor F: Set [figure]Set preserving nonempty preimages the following conditions are equivalent:

(i) F is a varietor,

(ii) Birkhoff’s Variety Theorem holds for F -algebras,

(iii) the category of F -algebras is cocomplete,

(iv) F has arbitrarily large fixed points.

In fact, (ii)  [figure](i) by Theorem 3.23, (i)  [figure](ii) due to Theorem 4.4 in [18], the

equivalence (i) [figure] (iii) was proved in [6] and (i) [figure] (iv) in [21].

3.25. Example. We present two endofunctors F_{1} and F_{2} of Set such that

(i) F_{1} and F_{2} are varietors

therefore, Birkhoff’s Variety Theorem holds for F_{1} and F_{2}, but

(ii) F_{1} + F_{2} is not a varietor and does not satisfy Birkhoff’s Variety Theorem.

This example, based on ideas of Václav Koubek (private communication) was already presented in [9], Example 4.4.4, but there we only mentioned the fact that F_{1} + F_{2} is not a varietor.

We begin by choosing a class C_{1} ⊆ Card of cardinal numbers such that both C_{1} and C_{2} = Card −C_{1} have the property that, for k = 1 or 2,

there exist arbitrarily large cardinal β with (β, 2^{β}] ⊆ C_{k}  (∗)

(where (β, 2^{β}] denotes the cardinal interval of all α ∈ Card with β < α ≤ 2^{β}). The class C_{1} can be defined as C_{1} = ⋃_{i∈Ord} D_{i} where D_{0} = (ℵ_{0}, 2^{ℵ_{0}}], D_{i+1} = D_{i} ∪ (2^{δ}, 2^{2^{δ}}] for δ = sup D_{i}, and D_{i} = ⋃_{j<i} D_{j} for limit ordinals i. We then define a functor F_{k} (k = 1 or 2) on objects X by

F_{k}X = {M ⊆ X; M = ∅ or card M ∈ C_{k}}

and on morphisms f: X [figure] Y by

F_{k}f: M [figure] \begin{cases}f[M] & if f restricted to M is monic \\ ∅ & else \end{cases}

This is well defined: F_{k} preserves composition and identity maps obviously. Observe that F_{1} is a varietor by 3.7: whenever C_{2} contains (β, 2^{β}] with β infinite, then a set X of cardinality 2^{β} is a fixed point of F_{1}: for every cardinal α ≤ β we have card X^{α} = (2^{β})^{α} = 2^{β} = card X, thus, F_{1}X ≅ X. By symmetry, F_{2} is a varietor. But F_{1} + F_{2} is not a varietor since it has no fixed point: for every set X with card X ∈ C_{k} we have card F_{k}X ≥ card X^{X} > card X.

3.26. Proposition. The functor F_{1} + F_{2} in Example 3.25 does not satisfy Birkhoff’s Variety Theorem.

Proof. This is a modification of the proof of Theorem 3.23 in which we have to overcome the difficulty that F = F_{1} + F_{2} does not preserve nonempty preimages.

Modification of the proof of (a). The only argument in the proof of 3.23 (a) using preservation of preimages concerned the existence of p̄_{i}: F \overline{W}_{i}(X) [figure] \overline{W}_{i+1}(X). This is clear in our case: given distinct elements a, b ∈ F W_{i}(X) with F e_{i}(a) = F e_{i}(b), we verify directly that e_{i+1}·p_{i} also merges a, b. Suppose, e.g., that a, b ∈ F_{1}W_{i}(X) (these elements clearly lie in the same component of F).

(i) Let F_{1}e_{i}(a) = ∅. Then F_{1}e_{i}(b) = ∅ which means that a, b are either empty or contain distinct elements equivalent under ∼_{i}. In the latter case the image under p_{i} contains elements equivalent under ∼_{i+1}, thus, e_{i+1}·p_{i} merges a and b.

(ii) Let F_{1}e_{i}(a) ≠ ∅. Then a contains no pair of distinct elements equivalent under ∼_{i}, and the same holds for b. Therefore a and b have the same intersection with w_{α,i}[W_{α}(X)] and at most one element is outside w_{α,i}[W_{α}(X)]. Moreover, from F_{1}e_{i}(a) = F_{1}e_{i}(b) it follows that if one of the sets a, b is a subset of w_{α,i}[W_{α}(X)] then so is the other one. This implies that e_{i+1}·p_{i} merges a and b.

Modification of the proof of (b). Choose a cardinal γ such that for every set X and every k = 1, 2 we have

card X ≥ γ  implies  card F_{k}X ≥ card X.

Define an algebra on D = Z + Z (with card Z = γ and with injections u_{l} and u_{r}) so that the diagram

[figure: Z; D; u_{l}; F_{1}D; Z; v_{l}; F_{1}D; F_{1}D + F_{2}D; inl; F_{1}D + F_{2}D; D; δ; D; Z; u_{r}; F_{1}D + F_{2}D; D; F_{1}D + F_{2}D; F_{2}D; inr; F_{2}D; Z; v_{r}]

commutes. We will prove that f = id_{D} has the analogous property to (8) in 3.23:

the preimages of u_{l} and u_{r} under f_{i+2}^{#} : W_{i+2}(D) [figure] D have cardinalities at least card W_{i+1}(D).

(9)

This implies D ∉ 𝒱 as in the proof in 3.23.

For every ordinal i, recalling W_{i+1}(D) = D+F W_{i}(D), we have the following subobject of W_{i+2}(D):

F_{1}F W_{i}(D) [figure: F_{1} inr] F_{1}W_{i+1}(D) [figure: inl] F W_{i+1}(D) [figure: inr] W_{i+2}(D).

This subobject is contained in the preimage of u_{l} under f_{i+2}^{#} because its composite with

f_{i+2}^{#} = [f, δ·F f_{i+1}^{#}]

factorizes through u_{l}:

[figure: F_{1}F D; F_{1}D; F_{1}δ; F_{1}F W_{i}(D); F_{1}F D; F_{1}F f_{i}^{#}; F_{1}F W_{i}(D); F_{1}W_{i+1}(D); F_{1} inr; F_{1}W_{i+1}(D); F_{1}D; F_{1}D; F D; inl; F_{1}W_{i+1}(D); F_{1}D; F_{1}f_{i+1}^{#}; F_{1}W_{i+1}(D); F W_{i+1}(D); inl; F W_{i+1}(D); F D; F f_{i+1}^{#}; F W_{i+1}(D); W_{i+2}(D); inr; F_{1}D; Z; v_{l}; Z; D; u_{l}; F D; D; δ; W_{i+2}(D); D; f_{i+2}^{#}]

Consequently, the preimage of u_{l} has cardinality at least

card F_{1}F W_{i}(D) ≥ card F W_{i}(D) = card W_{i+1}(D).

In fact, the first inequality follows from the above choice of γ and X, since, obviously,

card F W_{i}(D) ≥ γ.

The proof that preimage of u_{r} has cardinality at least card W_{i+1}(D) follows by symmetry.

3.27. Example. A modification β̄ of the ultrafilter functor, see 2.5 (iii), which

(a) is not a varietor, but

(b) fulfils Birkhoff’s Variety Theorem.

Recall that ẋ denotes the trivial ultrafilter of all sets containing x. Define β̄ on objects by

β̄X = βX/∼

where ∼ is the least equivalence relation merging all trivial ultrafilters. Its equivalence class {ẋ; x ∈ X} is denoted by

b ∈ β̄X.

For a function f: X [figure] Y define β̄f by

β̄f(b) = b

and given a nontrivial ultrafilter 𝒰 ∈ βX then

β̄f(𝒰 ) = \begin{cases}βf(𝒰 ) & if f·m is monic for some member M ↪^{m} X of 𝒰 \\ b & else \end{cases}

It is clear that since βX has cardinality larger than X for infinite sets X, we have

card β̄X > card X for X infinite.

Thus, β̄ is not a varietor.

3.28. Proposition. β̄ fulfils Birkhoff’s Variety Theorem.

Proof. (1) Let us prove that for every β̄-algebra (A, α) and the smallest infinite cardinal c_{A} > card A we have that A satisfies all reduced (see 3.9 (iv)) equations t = b in W_{i}(A) with i ≥ c_{A}.

We proceed by induction in i, where both the first step (i = c_{A}) and every limit step are trivial by default: given a reduced equation in W_{i}(A) the ordinal i is not a limit ordinal.

Isolated step: We assume that A satisfies every reduced equation s = b where s ∈ W_{j}(A) for some j with c_{A} ≤ j ≤ i. Then we prove that A satisfies every reduced equation

t = b with t ∈ W_{i+1}(A).

Assuming the contrary, i.e.,

f_{i+1}^{#}(t) ≠ α(b) for some f: A [figure] A

we derive a contradiction. Since t = b is reduced, t ∈ A + β̄[W_{i}(A)] lies in the right-hand summand, i.e., t is an ultrafilter on W_{i}(A). Since f_{i+1}^{#}(t) ≠ α(b) there exists

m: M ↪ W_{i}(A) a member of t such that f_{i}^{#}·m is monic.

In particular,

card M ≤ card A < c_{A}.

Moreover, without loss of generality we can assume

f_{i}^{#}(s) ≠ α(b) for all s ∈ M

(since f_{i}^{#}·m is monic of M, and we can substitute M by M − {s_{0}} for any s_{0} ∈ M: the ultrafilter t is non-trivial, thus, with M it contains M − {s_{0}}). By induction hypothesis none of the equations s = b (with s ∈ M) is reduced in W_{i}(A). Let s′ = b be a logically equivalent reduced equation in W_{i(s)}(A) for some ordinal i(s) < i, see Remark in 3.10. From f_{i}^{#}(s) ≠ α(b) it follows that A does not satisfy s′ = b which, by induction hypothesis, implies

i(s) < c_{A}.

Moreover, card M < c_{A}, thus, there exists j < c_{A} which is an upper bound of all i(s)—that is,

M ⊆ w_{j,i}[W_{j}(A)].

Denote by t̄ the ultrafilter of all preimages of the members of t under w_{j,i}. Since w_{j,i} is a monomorphism, see Lemma 3.21, we get

t = β̄w_{j,i}(t̄) = w_{j+1,i+1}(t̄).

Since j < c_{A}, this contradicts to t = b being reduced.

(2) For every class 𝒜 of β̄-algebras denote by E(𝒜) the class of all reduced equations satisfied by every algebra of 𝒜. Assuming that 𝒜 is closed under limits, subalgebras and regular quotient algebras, we prove that 𝒜 is presented by E(𝒜). Express 𝒜 as a union of an increasing chain of small sets

𝒜 = ⋃_{j∈Ord} 𝒜_{j}.

Each 𝒜_{j} generates the variety \overline{𝒜} _{j} of Example 3.19. Given an algebra B satisfying all equations which hold for all algebras of 𝒜:

E(B) ⊇ E(𝒜) = ⋂_{j∈Ord} E(𝒜_{j})

we prove B ∈ 𝒜. Then 𝒜 is a variety.

Denote by Ω the small set of all reduced equations in W_{r}(B) for all r < c_{B} (see (1) above). Since Ω − E(𝒜_{j}) is an increasing chain with

Ω − E(B) ⊆ Ω − E(𝒜) = ⋃_{j∈Ord} Ω − E(𝒜_{j})

and Ω is small, there exists an ordinal k with Ω − E(B) ⊆ Ω − E(𝒜_{k}). It follows that for every reduced equation t = b which holds in 𝒜_{k} we have: t = b holds in B. (If t = b lies in Ω, this is obvious from Ω − E(B) ⊆ Ω − E(𝒜_{k}), if t = b does not lie in Ω, apply (1) above and 3.22.) Consequently, also all non-reduced equations t = b holding in 𝒜_{k} hold in B, see the Remark in 3.10.

The set 𝒜_{k} is small, thus we can choose an infinite cardinal

d > card A for every algebra A ∈ 𝒜_{k}.

Given a reduced equation

t = s in W_{i}(A) lying in E(𝒜_{k}) − E(B)  (+)

(i.e., such that B does not satisfy it but algebras of 𝒜_{k} do), we conclude that

i < d.

In fact, for i ≥ d assume, without loss of generality, that t is reduced in W_{i}(A)−w_{j,i}[W_{j}(A)] for all j < i—then t = b holds in 𝒜_{k}, see (1) above. From (+) we conclude that b = s holds in 𝒜_{k}. By our choice of k it follows that t = b and b = s hold in B—in contradiction to t = s not being an element of E(B).

We conclude that the set E(𝒜_{k}) − E(B) is small. Since E(B) contains E(𝒜) = ⋂_{i∈Ord} E(𝒜_{i}), for every member t = s of E(𝒜_{k}) − E(B), there exists an ordinal l ≥ k such that E(𝒜_{l}) does not contain t = s. Now E(𝒜_{k}) − E(B) is small, so we can choose l independently of k. Then E(𝒜_{l}) is disjoint from E(𝒜_{k}) − E(B)—that is, E(B) ⊇ E(𝒜_{l}). Now \overline{𝒜} _{l} is a variety (see 3.19) with E(𝒜_{l}) = E(\overline{𝒜} _{l}). This proves B ∈ \overline{𝒜} _{l} ⊆ 𝒜.

3.29. Concluding Remark. For set functors F preserving nonempty preimages the question of Birkhoff’s Variety Theorem is completely answered by Theorem 3.22: it is equivalent to F being a varietor. However, by a slight modification of the proof also some interesting functors can be included which do not preserve nonempty preimages. For example the functor F_{1} + F_{2} in 3.26—this functor is a modification of the power-set functor strongly resembling the modification of β performed in 3.27. Yet, the conclusion of 3.27 is opposite to that of 3.26, which indicates that the precise characterization of set functors for which Birkhoff’s Variety Theorem holds is a complicated problem.

The functor β̄ of 3.26 is not faithful. However, by a modification of the proof of 3.28 one can show that the faithful functor β̄ + Id also satisfies Birkhoff’s Variety Theorem without being a varietor.

4. Birkhoff’s Variety Theorem for Classes

4.1. The Category Class. We work here in ZFC (Zermelo-Fraenkel Set Theory with the Axiom of Choice) with a choice of a universe of “small” sets. If ℵ_{∞} denotes the cardinality of this universe, then the category Set of small sets can, as in [7], be identified with the category of all sets of cardinalities smaller than ℵ_{∞}. And the category Class of classes can be identified with that of all sets of cardinalities at most ℵ_{∞}. More precisely: our foundation is ZFC with a strongly inaccessible cardinal ℵ_{∞}. Then Set is the category of all sets which hereditarily have cardinality smaller than ℵ_{∞}. This is clearly equivalent to the category of all sets of cardinality smaller than ℵ_{∞}. Analogously for Class. Thus, the above identification does not influence any categorical results.

We denote by Ord and Card the classes of all small ordinals and small cardinals, respectively. Thus, ℵ_{∞} is the first ordinal outside of Ord.

4.2. Notation. Given an endofunctor F of Class, we denote, analogously to 3.1, by Alg F the category of all F -algebras F A [figure: α] A and homomorphisms and we call F a varietor if the forgetful functor Alg F [figure] Class has a left adjoint—i.e., every object K generates a free F -algebra Φ(K). We denote by η_{K}: K [figure] Φ(K) the universal arrow.

4.3. Theorem. (See [7].) Every endofunctor of Class is a varietor.

4.4. Remark. We say that Set is measurable if the cardinal ℵ_{∞} is measurable. In other words, a nontrivial two-valued measure exists on a proper class which is α-additive for all small cardinals α. The negation of this assumption states that every ultrafilter on a class closed under small intersections is trivial (i.e., consists, for some element x, of all classes containing x). As proved by J. Isbell [12], this is equivalent to Set being codense in Class. In other words: every class is a limit of a large diagram of small sets.

4.5. Definition. Given an endofunctor F of Class, by an equation is meant a pair t_{1}, t_{2} of elements of a free algebra Φ(K). An F -algebra A is said to satisfy the equation provided that for every map f: K [figure]A the corresponding homomorphism f^{#} : Φ(K)

[figure] A fulfils f^{#}(t_{1}) = f^{#}(t_{2}).

A collection 𝒜 of F -algebras is called a variety if it can be presented by equations, i.e., if there exists a class ℰ of equations such that members of the collection 𝒜 are precisely the F -algebras which satisfy every equation in ℰ.

4.6. Remark. A class ℰ of equations can also be described by an epimorphism in Class e: Φ(K) ↠ E. An F -algebra A satisfies the equations of ℰ iff every homomorphism from Φ(K) to A factorizes through e.

4.7. Example. Let Σ = (Σ_{n})_{n∈Card} be a (possibly large) signature, i.e., a class of “operation” symbols together with an “arity” function assigning to every operation symbol a small cardinal. Then Σ-algebras are precisely the algebras on the polynomial endofunctor F_{Σ} : Class [figure] Class defined on objects by

F_{Σ}X = ∐_{n∈Card} Σ_{n} × X^{n}.

As a concrete example consider Σ = Card where each symbol has arity zero. H. Herrlich observed in [11] that the class 𝒜 of all algebras A for which there exists i ∈ Card such that all the constants j ≥ i form the same element in A is closed under

(i) products

(ii) subalgebras, and

(iii) regular quotient algebras.

And it is clear that 𝒜 is not a variety. However, if in (i) “products” are substituted by “limits”, it turns out that 𝒜 is no longer a counter-example to Birkhoff’s Variety Theorem. At least not if Set is not (compare Example 4.9):

4.8. Birkhoff’s Variety Theorem for Classes. Assuming that Set is not measurable, every endofunctor F of the category of classes has the property that varieties are precisely the classes of F -algebras closed under regular quotients, subobjects, and limits.

4.9. Remark. (i) Limits are not restricted to mean “small limits” but all limits existing in Alg F. (In 4.7 (i), products are also not restricted to mean “small products” but all products existing in Alg F.)

(ii) Every variety can be presented by a single quotient of a free F -algebra as will be seen in the following proof.

Proof. (1) Let 𝒜 be a full subcategory of Alg F closed as above. Let K be a proper class, and denote by Φ(K) a free F -algebra on K. Let ∼_{i} (i ∈ I) be the collection of all congruences on Φ(K) such that the quotient algebra

A_{i} = Φ(K)/∼_{i}

lies in 𝒜. We prove below that if ∼ is the meet of these congruences, then also the algebra

A = Φ(K)/∼

lies in 𝒜. This implies that 𝒜 is a variety presented by the canonical quotient c: Φ(K) [figure] A. In fact, let B be an algebra in 𝒜, then for every homomorphism h: Φ(K) [figure]B the kernel congruence of h is ∼_{i} for some i (because 𝒜 is closed under subalgebras), thus, h = m·c_{i} for the canonical quotient c_{i}: Φ(K) [figure] Φ(K)/∼_{i} and for some homomorphism m: A_{i} [figure] B.

[figure: A; A_{i} = Φ(K)/∼_{i}; c̄_{i}; Φ(K); A; c; Φ(K); A_{i} = Φ(K)/∼_{i}; Φ(K); B; h; Φ(K); A_{i} = Φ(K)/∼_{i}; c_{i}; B; A_{i} = Φ(K)/∼_{i}; m]

Since ∼ refines ∼_{i}, we also have a canonical homomorphism

c̄_{i}: A [figure] A_{i} with c_{i} = c̄_{i}·c (i ∈ I).

This implies that h factorizes through c, i.e., B satisfies the equations in the kernel of c. Conversely, let B be an F -algebra satisfying them. We prove B ∈ 𝒜. Without loss of generality, B ≠ ∅ (if B = ∅ then B is a subalgebra of every F -algebra, thus, it lies in 𝒜). Let f: K [figure] B be an epimorphism (which exists since K is a proper class). Then the corresponding homomorphism f̄: Φ(K) [figure] B factorizes though c:

[figure: Φ(K); B; f̄; Φ(K); A; c; B; A; h]

and h is a homomorphism (because both hc and c are homomorphisms and, since c is a split epimorphism in Class, F c is an epimorphism). Since for the universal arrow η_{K} we see that f = h·c·η_{K} is an epimorphism in Class, so is h. Thus, A ∈ 𝒜 implies B ∈ 𝒜, due to closedness under quotient algebras.

It remains to prove A ∈ 𝒜. Let D be the diagram in 𝒜 whose objects are A_{i} for i ∈ I and whose morphisms are the canonical quotients c_{ij}: A_{i} [figure] A_{j}

[figure: A_{i}; A_{j}; c_{ij}; A; A_{i}; c̄_{i}; A; A_{j}; c̄_{j}]

for all i, j ∈ I such that ∼_{i} refines ∼_{j}. We prove that the cone (c̄_{i})_{i∈I} is a limit cone of D— then A ∈ 𝒜 since 𝒜 is closed under limits. The only nontrivial part is the verification that given a compatible collection

x_{i} ∈ A_{i} (i ∈ I),

there exists a unique x ∈ A with x_{i} = c̄_{i}(x) for all i ∈ I. In fact, consider

ℱ = {F ⊆ A; x_{i} ∈ c̄_{i}[F] for all i ∈ I}.

This is, obviously, a filter; in fact, an ultrafilter: given a disjoint decomposition A = V_{1}∪V_{2}, then V_{t} ∈ ℱ for t = 1 or 2. (Assuming the contrary, we have for t = 1, 2 an index i(t) with x_{i(t)} ∉ c̄_{i(t)}[V_{t}]. The kernel of ⟨c̄_{i(1)}, c̄_{i(2)}⟩: A [figure]A_{i(1)} × A_{i(2)} has the form ∼_{j} for some j ∈ I—this follows from 𝒜 being closed under finite products and subalgebras. Since ∼_{j} refines ∼_{i(1)}, we have

x_{i(1)} = c_{j,i(1)}(x_{j}),

therefore c̄_{i(1)} = c_{j,i(1)}·c̄_{j} implies

x_{j} ∉ c̄_{j}[V_{1}].

Analogously, x_{j} ∉ c̄_{j}[V_{2}]—a contradiction, since c̄_{j} is an epimorphism.) In fact, the same argument as above can be used to prove that for every disjoint decomposition A = ⋃_{t∈T} V_{t} where T is a small set we have V_{t} ∈ ℱ for some t ∈ T. In other words, ℱ is closed under small intersections. Since Set is not measurable, ℱ contains {x} for a unique x ∈ A. Then c̄_{i}(x) = x_{i}.

(2) If 𝒜 is a variety, then it is closed under limits. In fact, suppose that (A, α)

[figure: h_{i}] (A_{i}, α_{i}) (i ∈ I) is a limit cone of a diagram D in Alg F and suppose that each (A_{i}, α_{i}) satisfies equations e: Φ(K) ↠ E see 4.6. We prove that (A, α) also satisfies them.

For every homomorphism f̄: Φ(K) [figure] A we have factorizations

h_{i}·f̄ = k_{i}·e (k_{i}: E [figure] A_{i})

for all i ∈ I. Since (k_{i}·e)_{i∈I} is a cone of D and e is an epimorphism in Class, (k_{i})_{i∈I} is a cone of D in Class, thus, we have a unique k: E [figure] A with

h_{i}·k = k_{i} (i ∈ I).

Here we use the (trivial) fact that the forgetful functor of Alg F preserves limits. From the equalities

h_{i}·f̄ = h_{i}·(k·e) (i ∈ I)

it follows that f̄ = k·e. Therefore, A satisfies e.

The verification that 𝒜 is closed under subalgebras and regular quotient algebras is straightforward.

4.10. Example. A class of Σ-algebras which is not a variety but is closed under limits, subalgebras, and regular quotient algebras. We assume here that Set is measurable, i.e., a proper class K is not a limit of the canonical diagram K/ Set [figure]Class of all maps f: K [figure] X with X small. Consider Σ = K as the signature of nullary operation symbols. Let 𝒜 be the collection of all algebras (A, (k^{A})_{k∈K}) such that A^{∗} = {k^{A}; k ∈ K} is a small set. Then 𝒜 is clearly closed under subalgebras and regular quotient algebras. We verify that it is also closed under limits. Let D: 𝒟 [figure]𝒜 be a diagram with a limit A [figure: c_{d}]A_{d} (d ∈ 𝒟^{obj}) in Alg Σ. Then A^{∗} is contained in a limit, L, in Class, of the diagram formed by the sets A_{d}^{∗} and the corresponding restrictions of the connecting morphisms of D. Since each A_{d}^{∗} is a small set, and since Set is measurable, L cannot be isomorphic to K—thus, A^{∗} is a small set. That is, A ∈ 𝒜.

However, 𝒜 is not a variety: for every pair k ≠ l in K there exists an algebra A ∈ 𝒜 with k^{A} ≠ l^{A}.

4.11. Example. Denote by 𝒫′ the extension of the power-set functor to Class: 𝒫′X is the class of all small subsets of X. Assuming that Set is not measurable, Birkhoff’s Variety Theorem holds for 𝒫′, but not for 𝒫. This is surprising because the equations used for 𝒫′ are not more expressive than those used for 𝒫. However, given a collection 𝒱 of 𝒫-algebras closed under products, subalgebras and regular quotients in Alg 𝒫, it is in general not closed under limits in Alg 𝒫′. Now let 𝒱 ′ be the closure of 𝒱 under limits, subalgebras and regular quotients in Alg 𝒫′. This is an equational class of 𝒫′-algebras, but there is no reason why its intersection with Alg 𝒫 should be 𝒱 . Thus, things are not all that surprising, after all: the collection of all 𝒫-algebras lying in 𝒱 ′ is simply the equational hull of 𝒱 in Alg 𝒫.

5. Conclusions and Related Research

Jan Reiterman proved in [18] that for varietors F on Set Birkhoff’s Variety Theorem holds. That is, presentability by equations is equivalent to closure under limits, subalgebras and regular quotient algebras. Originally, we wanted to prove the converse, inspired by ideas of [18]. This goal was achieved for endofunctors F preserving nonempty preimages (which is a weak side condition). For such functors we proved that Birkhoff’s Variety Theorem holds iff F is a varietor. For general functors the converse is not true, i.e., there exist functors F: Set [figure] Set which are not varietors and for which Birkhoff’s Variety Theorem holds.

Open problem. Characterize endofunctors F of Set for which Birkhoff’s Variety Theorem holds in Alg F.

In ZFC with a choice of small sets, the “standard” set theory plus the axiom of choice, we also proved that all endofunctors of Class fulfill Birkhoff’s Variety Theorem under the set-theoretic assumption that the cardinality of Set is non-measurable. In view of the above result of J. Reiterman, and the fact that all endofunctors of Class are varietors, see [7], it seems in fact surprising that any set-theoretical assumptions are needed. But they are: we presented a simple example of a non-equational class of Σ-algebras which is closed under limits, subalgebras and regular quotient algebras, where Σ is just a class of nullary symbols—whenever the set-theoretical assumption above is not fulfilled.

How far can the results above be generalized to categories other than Set and Class? Nothing much is known for general categories. However, for the dual categories Set^{op} and Class^{op} the following is proved in [4]:

BIRKHOFF’S VARIETY THEOREM WITH AND WITHOUT FREE ALGEBRAS  449

(a) Every endofunctor of Class^{op} is a varietor and Birkhoff’s Variety Theorem holds.

(b) There exists an endofunctor of Set^{op} for which Birkhoff’s Variety Theorem does not hold.

References

[1] P. Aczel and N. Mendler, A final coalgebra theorem, Lect. Notes Comp. Science 389, Springer-Verlag 1989, 357–365.

[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, Theory of mathematical structures, Reidel Publ., Dordrecht 1983.

[4] J. Adámek, Birkhoff’s covariety theorem without limitations, Comment. Math. Univ. Carolinae 46 (2005), 197–215.

[5] J. Adámek, H. Herrlich and G. Strecker, Abstract and concrete categories, Wiley

Publ. 1990, see online version http://katmat.math.uni-bremen.de/acc

[6] J. Adámek, V. Koubek and V. Pohlová, Colimits in the generalized algebraic categories, Acta Univ. Carolinae 13 (1972) 311–324.

[7] J. Adámek, S. Milius and J. Velebil, On coalgebra based on classes, Theor. Comp. Science 316 (2004) 3–23.

[8] J. Adámek and H.-E. Porst, On varieties and covarieties in a category, Math. Structures Comput. Sci. 13 (2003), 201–232.

[9] J. Adámek and V. Trnková, Automata and algebras in a category (Kluwer Academic Publishers, Dordrecht, 1990).

[10] G. Birkhoff, On the structure of abstract algebras, Proc. Camb. Phil. Soc. 31 (1935), 433–454.

[11] H. Herrlich, Remarks on categories of algebras defined by a proper class of operations, Quaestiones Mathematicae 13 (1990) 385–393.

[12] J. R. Isbell, Adequate categories, Illinois Journal of Mathematics 4 (1960) 541–552.

[13] V. Koubek, Set functors, Comment. Math. Univ. Carolinae 12 (1971) 175–195.

[14] J. Lambek, A fixed point theorem for complete categories, Math. Zeitschrift 103 (1968), 151–161.

[15] S. Mac Lane, Categories for the working mathematician, Second Edition, Springer-Verlag, New York, Berlin, Heidelberg 1998.

[16] E. G. Manes, A triple-theoretic construction of compact algebras, Lecture Notes in Mathematics 80 (1969) 91–119.

[17] J. Reiterman, Categorical Algebraic Constructions, doctoral thesis (in Czech), Charles University, Prague 1976.

[18] J. Reiterman, One more categorial model of universal algebra, Math. Zeitschrift 161 (1978) 137–146.

[19] J. Rutten, Universal coalgebra: a theory of systems, Theor. Comp. Science 249 (2000), 3–80.

[20] V. Trnková, Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), 323–352.

[21] V. Trnková, J. Adámek, V. Koubek and J. Reiterman, Free algebras, input processes and free monads, Comment. Math. Univ. Carolinae 16 (1975) 339–351.

Institute of Theoretical Computer Science Technical University of Braunschweig

Faculty of Mathematics and Physics Charles University, Prague

Email: J.Adamek@tu-bs.de,
      Trnkova@karlin.mff.cuni.cz

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/14/18/14-18.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca