Theory and Applications of Categories, Vol. 20, No. 12, 2008, pp. 334–404.

COLIMITS OF REPRESENTABLE ALGEBRA-VALUED FUNCTORS

GEORGE M. BERGMAN

Abstract. If C and D are varieties of algebras in the sense of general algebra, then by a representable functor C → D we understand a functor which, when composed with the forgetful functor D → Set, gives a representable functor in the classical sense; Freyd showed that these functors are determined by D-coalgebra objects of C. Let Rep(C, D) denote the category of all such functors, a full subcategory of Cat(C, D), opposite to the category of D-coalgebras in C.

It is proved that Rep(C, D) has small colimits, and in certain situations, explicit constructions for the representing coalgebras are obtained.

In particular, Rep(C, D) always has an initial object. This is shown to be “trivial” unless C and D either both have no zeroary operations, or both have more than one derived zeroary operation. In those two cases, the functors in question may have surprisingly opulent structures.

It is also shown that every set-valued representable functor on C admits a universal morphism to a D-valued representable functor.

Several examples are worked out in detail, and areas for further investigation are noted.

In §§1-7 below we develop our general results, and in §§9-14, some examples. (One example is also worked in §5, to motivate the ideas of §6.)

R. Paré has pointed out to me that my main result, Theorem 4.6, can be deduced from [19, Theorem 6.1.4, p.143, and following remark, and ibid. Corollary 6.2.5, p.149]. However, as he observes, it is useful to have a direct proof.

Much of this work was done in 1986, when the author was partially supported by NSF grant DMS 85-02330.

arXiv:0711.0674. Received by the editors 2007-11-10 and, in revised form, 2008-07-18. Transmitted by Robert Paré. Published on 2008-07-23. 2000 Mathematics Subject Classification: Primary: 18A30, 18D35. Secondary: 06E15, 08C05, 18C05,

20M50, 20N02 .

Key words and phrases: representable functor among varieties of algebras, initial representable functor, colimit of representable functors, final coalgebra, limit of coalgebras; binar (set with one binary operation), semigroup, monoid, group, ring, Boolean ring, Stone topological algebra.

\begin{matrix}c \\ ◯ \end{matrix} George M. Bergman, 2008. Permission to copy for private use granted.

I. GENERAL RESULTS.

1. Conventions; algebras, coalgebras, and representable functors.

In this note, morphisms in a category will be composed like set-maps written to the left of their arguments. The composition-symbol ∘ will sometimes be introduced as an aid to the eye, with no change in meaning. So given morphisms f : X → Y and g : Y → Z, their composite is gf or g ∘ f : X → Z.

Throughout, C and D will denote fixed varieties (equational classes) of algebras, in which the operations may have infinite arities and/or be infinite in number unless the contrary is stated, but are always required to form a small set.

Let us set up our notation, illustrating it with the case of the variety C. We assume given a set Ω_{C}, which will index the operations, and a cardinal-valued function ari_{C} on Ω_{C}, the arity function. We fix a regular infinite cardinal λ_{C} greater than every ari_{C}(α) (α ∈ Ω_{C}). An Ω_{C}-algebra will mean a pair A = (|A|, (α_{A})_{α∈Ω_{C}} ), where |A| is a set, and for each α ∈ Ω_{C}, α_{A} is a set-map |A|^{ari_{C} (α)} → |A|. We denote the category of such algebras, with the obvious morphisms, by Ω_{C}-Alg .

For every cardinal κ, let T_{Ω_{C}} (κ), the “term algebra” on κ, denote a free Ω_{C}-algebra on a κ-tuple of indeterminates, and let Φ_{C} be a subset of ⋃_{κ<λ_{C}} |T_{Ω_{C}} (κ)| × |T_{Ω_{C}} (κ)|, our set of intended identities. Then we define an object of C to mean an Ω_{C}-algebra A with the property that for every κ < λ_{C}, every map x : κ → |A| and every element (s, t) ∈ Φ_{C} ∩ (|T_{Ω_{C}} (κ)| × |T_{Ω_{C}} (κ)|), the κ-tuple x “satisfies the identity s = t”, in the sense that the images of s and t under the homomorphism T_{Ω_{C}} (κ) → A extending x, which we may denote s(x) and t(x), are equal. We take C to be the full subcategory of Ω_{C}-Alg with this object-set, and write U_{C} : C → Set for its underlying set functor.

Note that if C has no zeroary operations (i.e., if Ω_{C} has no elements of arity 0), then the empty set has a (unique) structure of C-algebra, and gives the initial object of C.

The corresponding notation, Ω_{D}, ari_{D}, λ_{D}, Φ_{D}, etc., applies to D. We will generally abbreviate ari_{C}(α) or ari_{D}(α) to ari(α) when there is no danger of ambiguity.

(Observe that our definition requires that every variety C be given with a distinguished set of defining identities Φ_{C}. The choices of Φ_{C} and Φ_{D} will not come into the development of our main results in §§2-5. But Φ_{D} will be called on in §6-7, where we develop methods for the explicit construction of our colimit functors.)

If A is a category in which all families of < λ_{D} objects have coproducts, an Ω_{D}- coalgebra R in A will mean a pair R = (|R|, (α^{R})_{α∈Ω_{C}} ), where |R| is an object of A, and each α^{R} is a morphism |R| → ∐_{ari(α)} |R|; the α^{R} are the co-operations of the coalgebra. For each α ∈ Ω_{D} and each object A of A, application of the homfunctor A(−, A) to the co-operation α^{R} induces an operation α_{A(R,A)} : A(|R|, A)^{ari(α)} → A(|R|, A); these together make A(|R|, A) an Ω_{D}-algebra, which we will denote A(R, A). We thus get a functor A(R, −) : A → Ω_{D}-Alg.

Note that this is a nontrivial extension of standard notation: If A and B are objects of A, then A(A, B) denotes the hom-set; if R is an Ω_{D}-coalgebra in A, then A(R, B) denotes an Ω_{D}-algebra with the hom-set A(|R|, B) as underlying set. We are also making the symbol | | do double duty: If A is an object of the variety C, then |A| denotes its underlying set; if R is a coalgebra object in C, we denote by |R| its underlying C-algebra; thus ||R|| will be the underlying set of that underlying algebra. In this situation, “an element of R”, “an element of |R|” and “an element of ||R||” will all mean the same thing, the first two being shorthand for the third. In symbols we will always write this r ∈ ||R||. We also extend the standard language under which the functor A(|R|, −) : A → Set is said to be representable with representing object |R|, and call A(R, −) : A → Ω_{D}-Alg a representable (algebra-valued) functor, with representing coalgebra R.

A more minor notational point: Whenever we write something like ∐_{κ} A, this will denote a κ-fold copower of the object A, with the index which ranges over κ unnamed; thus, a symbol such as ∐_{κ} A_{ι} denotes the κ-fold copower of a single object A_{ι}. On the few occasions (all in §7) where we consider coproducts other than copowers, we will show the variable index explicitly in the subscript on the coproduct-symbol, writing, for instance, ∐_{ι∈κ} A_{ι} to denote (in contrast to the above) a coproduct of a family of objects A_{ι} (ι ∈ κ).

If R = (|R|, (α^{R})_{Ω_{C}} ) is an Ω_{D}-coalgebra in A, and s, t ∈ |T_{Ω_{D}}(κ)|, then the necessary and sufficient condition for the algebras A(R, A) to satisfy the identity s = t for all objects A of A is that the κ-tuple of coprojection maps in the Ω_{D}-algebra A(R, ∐_{κ} |R|) satisfy that relation. In this case, we shall say that the Ω_{D}-coalgebra R cosatisfies the identity s = t. If R cosatisfies all the identities in Φ_{D}, we shall call R a D-coalgebra object of A, and call the functor it represents a representable D-valued functor on A.

Whenever a functor F : A → D has the property that its composite with the underlying set functor U_{D} is representable in the classical sense, then the D-algebra structures on the values of F in fact arise in this way from a D-coalgebra structure on the representing A-object. If A not only has small coproducts but general small colimits, the D-valued functors that are representable in this sense are precisely those that have left adjoints [14], [6, Theorem 9.3.6], [9, Theorem 8.14]. We shall write Coalg(A, D) for the category of D-coalgebras in A, taking for the morphisms R → S those morphisms |R| → |S| that make commuting squares with the co-operations, and we shall write Rep(A, D) for the category of representable functors A → D, a full subcategory of Cat(A, D). Up to equivalence, Rep(A, D) and Coalg(A, D) are opposite categories.

The seminal paper on these concepts is [14] (though the case where C is a variety of commutative rings and D the variety of groups, or, occasionally, rings, was already familiar to algebraic geometers, the representable functors corresponding to the “affine algebraic groups and rings”). For a more recent exposition, see [6, §§9.1-9.4]. In [9] the structure of Coalg(C, D) is determined for many particular varieties C and D.

(The term “coalgebra” is sometimes used for a more elementary concept: Given any functor F : Set → Set, a set A given with a morphism A → F (A) is called, in that usage, an F -coalgebra. The existence of final coalgebras in that sense has also been studied [1], [4], and, as we shall see, has a slight overlap with the concept studied in this note. Still another use of “coalgebra”, probably the earliest, which also has relations to these two, and is basic to the theory of Hopf algebras, is that of a module M over a commutative ring, given with a map M → M ⊗ M; cf. [20, pp.4 to end] and [9, §§29-32, §43]. And in fact, as the referee has pointed out, results analogous to some of those in this note were proved for coalgebras in that sense over thirty years ago, by a similar approach [3].)

The first step toward our results will be an easy observation.

1.1. Lemma. If A has small colimits, then so does Coalg(A, D); equivalently, Rep(A, D) has small limits. Moreover, the underlying A-object of a colimit of D-coalgebras in A is the colimit of the underlying A-objects of these algebras. Equivalently, the composite of the limit of the corresponding representable functors with the underlying set functor U_{D} is the limit of the composites of the given functors with U_{D}, and may thus be evaluated at the set level by taking limits of underlying sets.

Proof. Since D has small limits, the category of D-valued functors on any category also has small limits, which may be computed object-wise; hence by properties of limits of algebras, these commute with passing to underlying sets. In particular, a functor F from a small category E to Rep(A, D) will have a limit L in D^{A}, and U_{D} ∘ L will be the limit of the set-valued functors U_{D} ∘ F (E). The latter limit is represented by the colimit of the underlying A-objects of the coalgebras representing the F (E); call this colimit object |R|. As noted above, representability of U_{D} ∘ L : A → Set by |R| implies representability of L : A → D by a coalgebra R with underlying A-object |R|.

(One can get the same result starting at the coalgebra end, using the general fact that “colimits commute with colimits” to deduce that a colimit of underlying objects of a diagram of coalgebras inherits co-operations from these, and verify that the resulting coalgebra has the universal property of the desired colimit.)

Knowing that Rep(A, D) has small limits, to prove that it has small colimits we need “only” prove that it satisfies the appropriate solution-set condition ([18, Theorem V.6.1], [6, Theorem 7.10.1]). Easier said than done!

We shall get such a result in the case where A is a variety C. In the next section, we motivate the technique to be used (after giving a couple of results showing cases to avoid when thinking about examples), then preview the remainder of the paper.

2. Background; trivial cases; motivation of the proof; overview of the paper.

Let me first describe what led me to the questions answered below.

Let Ring^{1} denote the category of associative unital rings, and for any field K, let Ring_{K}^{1} denote the category of associative unital K-algebras. (When I write “K-algebra”, “algebra” will be meant in the ring-theoretic sense; otherwise it is always meant in the general sense.) In [9, §25], descriptions are obtained of all representable functors from Ring_{K}^{1} into a number of varieties of algebras (general sense!), including Ring^{1}. The result for the lastmentioned variety says that for every representable functor F : Ring_{K}^{1} → Ring^{1}, there exist two linearly compact associative unital K-algebras A and B, such that F is isomorphic to the functor taking every object S of Ring_{K}^{1} to the direct product of completed tensor-product rings S ˆ⊗A × S^{op} ˆ⊗B. (One doesn’t need to know precisely what these terms mean to appreciate the point that is coming up. For general background: the category of linearly compact K-vector spaces is dual to the category of all K-vector spaces, and a linearly compact topology on an associative unital K-algebra A makes it an inverse limit of finite-dimensional K-algebras [9, §24]. In this situation, the completed tensor product of a K-algebra S with A is the inverse limit of the tensor products of S with those finite-dimensional K-algebras.)

Now the category of linearly compact associative unital K-algebras has an initial object, the field K given with the discrete topology, and under the above characterization of representable functors, the operation of completed tensor product with this object describes the forgetful functor Ring_{K}^{1} → Ring^{1}. Hence the result cited shows that Rep(Ring_{K}^{1}, Ring^{1}) has an initial object, the functor taking S to S × S^{op}, regarded as a ring. The coalgebra representing this functor has for underlying object the free associative unital K-algebra in two indeterminates, K⟨x, y⟩.

(The same conclusion is true for K any commutative ring, and, in fact, in a still more general context [9, §28]. However, there is no analog in these contexts to the duality between vector spaces and linearly compact vector spaces, and hence no interpretation of representable functors in terms of completed tensor products. Indeed, the existence and description of the initial object might not have been discovered without the motivation of the case where K is a field.)

The above result suggests that for general varieties C and D, the category Rep(C, D) might have an initial object, which might have a non-obvious form. It was this tantalizing hint that led to the present investigations.

Curiously, if, in the preceding example, the unitality condition is dropped from the class of rings taken as the domain variety, or the codomain variety, or both, then Rep(C, D) still has an initial object, but not an “interesting” one – it is trivial, represented by the 0- or 1-dimensional K-algebra depending on the case. This sort of triviality occurs in some very general classes of situations. Let us now prove this, so that the reader who wishes to think about the arguments of later sections in the light of examples of her or his choosing will be able to consider cases that have a chance of being nontrivial.

2.1. Theorem. (i) Suppose A is a variety of algebras with no zeroary operations (or more generally, is a category with small coproducts such that the initial object of A admits no morphisms from non-initial objects into it). Let D be a variety of algebras having at least one zeroary operation. Then for any representable functor F : A → D, the underlying A-object of the coalgebra representing F is the initial object of A; hence F is the functor taking every object to the 1-element D-algebra. (So, in particular, Rep(A, D) has this trivial functor as its initial object.)

(ii) Suppose A is a variety of algebras with a unique derived zeroary operation (or more generally, is a category with small coproducts whose initial object is also a final object), and let D be any variety of algebras. Then Rep(A, D) has an initial object, namely the functor taking all objects of A to the 1-element algebra in D, represented by the initial-final object of A with the unique D-coalgebra structure that it admits. (However, in this case, Rep(A, D) may have nontrivial non-initial objects.)

(iii) Suppose A is a variety of algebras with more than one derived zeroary operation (or more generally, is a category with small coproducts and a final object, such that the unique morphism from the initial to the final object is an epimorphism but not invertible), and let D be any variety of algebras having at most one derived zeroary operation. Then Rep(A, D) has an initial object F. Namely –

(iii.a) If D has no zeroary operations, F is represented by the final object of A, which under the above hypotheses has a unique D-coalgebra structure, and takes objects of A that admit morphisms from the final object into them to the 1-element (final) D-algebra, and objects which do not admit such a morphism to the empty (initial) D-algebra.

(iii.b) If D has exactly one derived zeroary operation, then F is represented by the initial object of A, with its unique D-coalgebra structure, and so takes all objects to the 1-element algebra.

(But in these situations, too, Rep(A, D) may have nontrivial non-initial objects.)

Thus, assuming A a variety of algebras, the only situations where Rep(A, D) can have an initial object whose values are not exclusively 0- or 1-element algebras are if neither A nor D has zeroary operations, or if both A and D have more than one derived zeroary operation.

Proof. First, some general observations. Recall that if a category A has an initial object I, then this is the colimit of the empty diagram, and in particular, is the coproduct of the empty family of algebras. It follows that any copower of I is again I. From this we can see that I has a unique D-coalgebra structure for every variety D.

More generally, suppose A has an initial object I and that J is an epimorph of I. (For example, A might be the category of unital commutative rings, so that I is the ring ℤ of integers, and J might be a prime field, ℤ/pℤ or ℚ.) Then a copower ∐_{κ} J can be identified with the pushout of the system of maps from I to a κ-tuple of copies of J (because I is initial), so by the assumption that I → J is an epimorphism, if κ ≠ 0 that pushout will again be J. (On the other hand, if κ = 0, then that pushout is I.) The argument of the preceding paragraph now generalizes to show that for every D without zeroary operations, such an object J also has a unique structure of D-coalgebra.

With these observations in mind, we shall prove the various statements of the theorem, in each case under the “more general” hypothesis. (In each case, it is easy to see that that hypothesis holds for the particular class of varieties with which the statement begins.)

In the situation of (i), since D has a zeroary operation, the representing object R of F must have a zeroary co-operation, i.e., a morphism in A from |R| to the initial object. But by assumption on A, that can only happen if |R| is the initial object, giving the indicated conclusion.

In the situation of (ii), we can form a D-coalgebra in A by taking the initial-final object (often called a zero object) Z as underlying object, and noting as above that as the initial object, Z has a unique D-coalgebra structure. Because Z is also a final object, the underlying A-object of every D-coalgebra in A admits a unique map to Z, and this clearly forms commuting squares with the co-operations. Thus, the corresponding coalgebra is final in Coalg(A, D), and so determines an initial representable functor.

To verify the parenthetical assertion that representable functors other than this one may also exist, let A = Group, and note that the forgetful functor to Semigp is representable, as is the identity functor of A. These two examples cover the cases where D has no zeroary operations or a unique derived zeroary operation. If D has more than one derived zeroary operation, a representable functor from a category A of the indicated sort must take values in the proper subvariety of D determined by the identities saying that the values of all these operations are equal, since an object of A clearly has a unique zeroary co-operation. Although for some D (e.g., Ring^{1}) that subvariety is trivial, for others it is not. For instance, if D is the variety of groups with an additional distinguished element, then the subvariety in question consists of groups with the identity as that element, and the functor from Group to that subvariety which leaves the group structure unchanged is not trivial.

In case (iii.a), the assumption that the unique map from the initial to the final object of A is an epimorphism implies (by the observations of the second paragraph of this proof) that the final object of A admits a unique D-coalgebra structure for every variety D with no zeroary operations. It is easy to see that the resulting coalgebra is final in Coalg(A, D), as asserted; the description of the functor represented is also clear.

In the case (iii.b), where D has a unique derived zeroary operation, the conclusion actually requires no assumption on A but that it have an initial object. (Indeed, statements (i) and (ii) imply the same conclusion for such D.) To get that conclusion, observe that the value of the unique zeroary derived operation of D yields a unique one-element subalgebra in every object of D (e.g., when D = Group or Monoid, the subalgebra {e}). Hence the functor represented by the initial object of A with its unique D-coalgebra structure, taking every object to the one-element D-algebra, has a unique morphism to every functor A → D, hence is initial in D^{A}, and so, a fortiori, in Rep(A, D).

In these two situations, identity functors and forgetful functors again show that not every representable functor need be trivial.

The above theorem, in the case where A is a variety C of algebras, is summarized in the chart below. In that chart, I means that the initial representable functor is represented by the initial object, F means that it is represented by the final object, IF means it is represented by the initial-final object, an exclamation point means that the functor so represented is the only representable functor, and an exclamation point in parenthesis means that, though the functor in question may not be the only one, there is a strong restriction on representable functors, namely that they take as values algebras in which all derived zeroary operations are equal. Stars mark the two cases in which nontrivial initial representable functors can occur.

zeroary derived operations of D^{0}  ^{1}  ^{> 1}^{0} ∗  ^{I!}  ^{I!}^{1}  ^{IF}  ^{IF}  ^{IF (!)}^{>1}  ^{F}  ^{I}  ∗^{zeroary}^{derived}^{operations}^{of C}

In contrast to the triviality of the seven cases covered by the above theorem, the structure of the initial representable functor in the two starred cases can be surprisingly rich; we shall see this for a case belonging to the upper left-hand corner in §5, and for further examples of both cases in §§9-13. However, let us note a subcase of the upper left-hand case where the functors one gets are again fairly degenerate.

2.2. Proposition. Suppose D is a polyunary variety; i.e., that ari(α) = 1 for all α ∈ Ω_{D}. Then for any variety A of algebras (or more generally, for any category A having small colimits and a final object), the category Rep(A, D) has an initial object F, represented by the final object T of A, with its unique D-coalgebra structure, namely the structure in which every primitive co-operation is the identity.

Thus, if A is a variety, then for every object A of A, the algebra F (A) has for underlying set the set of those x ∈ |A| such that {x} forms a subalgebra of A, and has the D-algebra structure in which every primitive operation of D acts as the identity.

Proof. Since A(T, T) is a trivial monoid, there is a unique way to send the primitive unary operations of D to maps T → T, and this will make T a D-coalgebra. Recalling that T is final in A we see that for every D-coalgebra R in A, the unique morphism |R| → T becomes a morphism of coalgebras, so the coalgebra described is final in Coalg(A, D).

The description of the functor represented by this coalgebra when A is a variety is immediate.

From this point on, when the contrary is not stated, the domain category of our functors will be the variety C (assumed fixed in §1); so when we use the terms “representable functor” and “coalgebra” without qualification, these will mean “representable functor C → D”, and “D-coalgebra in C”.

Let me now motivate the technique of proof of the existence of final objects in Coalg(C, D), then indicate how to extend that technique to other limits.

Our Lemma 1.1 and Freyd’s Initial Object Theorem will establish the existence of an initial representable functor if we can find a small set W_{funct} of representable functors such that every object of Rep(C, D) admits a morphism from some member of W_{funct}; equivalently, a small set W_{coalg} of coalgebras such that every coalgebra admits a morphism into a member of W_{coalg}. Let us call an object R of Coalg(C, D) “strongly quasifinal” if every morphism of coalgebras with domain R which is surjective on underlying algebras is an isomorphism. (I will motivate this terminology in a moment.) It will not be hard to show that every coalgebra admits a morphism onto a strongly quasifinal coalgebra, so it will suffice to show that up to isomorphism, there is only a small set of these. To see how to get this smallness condition, note that no strongly quasifinal coalgebra R can be the codomain of two distinct morphisms of coalgebras with a common domain R′; for if it were, then their coequalizer in Coalg(C, D) (which by Lemma 1.1 has for underlying C-algebra the coequalizer of the corresponding maps in C) would contradict the strong quasifinality condition. (It is natural to call the property of admitting at most one morphism from every object “quasifinality”, hence our use of “strong quasifinality” for the above condition that implies it.) Thus, if we can find a small set V of coalgebras such that every coalgebra is a union of subcoalgebras isomorphic to members of V (where we shall define a “subcoalgebra” of R to mean a coalgebra which can be mapped into R by a coalgebra morphism that is one-to-one on underlying C-algebras, and also induces oneto-one maps of their copowers), then the cardinalities of strongly quasifinal coalgebras R will be bounded by the sum of the cardinalities of the members of V (since each member of V can be mapped into R in at most one way), giving the required smallness condition.

Naively, we would like to say that each coalgebra R is the union of the subcoalgebras “generated” by the elements r ∈ |R|, bound the cardinalities of coalgebras that can be “generated” by single elements, and take the set of such coalgebras as our V. Unfortunately, there is not a well-defined concept of the subcoalgebra generated by an element. Nevertheless, we shall be able to build up, starting with any element, or more generally, any subset X of ||R||, a subcoalgebra which contains X, and whose cardinality can be bounded in terms of that of X.

How? We will begin by closing X under the C-algebra operations of |R|. We will then consider the image of the resulting subalgebra of |R| under each co-operation α^{R} : |R| → ∐_{ari(α)} |R| (α ∈ Ω_{D}). This image will be contained in the subalgebra of ∐_{ari(α)} |R| generated by the images, under the ari(α) coprojections |R| → ∐_{ari(α)} |R|, of certain elements of |R|. The set of these elements is not, in general, unique, but the number of them that are needed can be bounded with the help of λ_{C}. Taking the subalgebra of |R| that they generate, we then repeat this process; after λ_{C} iterations, it will stabilize, giving a subalgebra |R|′ ⊆ |R| such that each co-operation α^{R} carries |R|′ into the subalgebra of ∐_{ari(α)} |R| generated by the images of |R|′ under the coprojections.

This |R|′ still may not define a subcoalgebra of R, because when we use the inclusion |R|′ ⊆ |R| to induce homomorphisms

∐_{ari(α)} |R|′ → ∐_{ari(α)} |R| (α ∈ Ω_{D}),  (1)

these may not be one-to-one; hence the co-operations α^{R} : |R| → ∐_{ari(α)} |R|, though they carry |R|′ into the image of (1), may not lift to co-operations |R|′ → ∐_{ari(α)} |R|′.

However, given |R|′, we can now find a larger subalgebra |R|′′, whose cardinality we can again bound, such that the inclusion |R|′′ ⊆ |R| does induce one-to-one maps ∐_{κ} |R|′′ → ∐_{κ} |R| for all cardinals κ. We then have to repeat the process of the preceding paragraph so that the images of our new algebra under the co-operations of R are again contained in the subalgebras generated by the images of the coprojections. Applying these processes alternately (or better, applying one step of each alternately, since nothing is gained by iterating one process to completion before beginning the other), we get a subcoalgebra of R containing X, whose cardinality we can bound.

Taking such a bound μ for the case card(X) = 1, any set of representatives of the isomorphism classes of coalgebras of cardinality ≤ μ gives the V needed to complete our proof.

In view of the messiness of the above construction, the bound on the cardinality of the final coalgebra that it leads to is rather large. But this reflects the reality of the situation. For instance, if C is Set, and D the variety of sets given with a single binary operation, we shall see in §5 that the final object of Coalg(C, D) is the Cantor set, with co-operation given by the natural bijection from that set to the disjoint union of two copies of itself. Since this coalgebra has cardinality 2^{ℵ_{0}}, the functor it represents takes a 2-element set to a D-algebra of cardinality 2^{2^{ℵ_{0}}}. (Incidentally, because in this example, C = Set and the variety D is defined without the use of identities, this final coalgebra is also the final coalgebra in the sense of [1] and [4], with respect to the functor taking every set to the disjoint union of two copies of itself.)

How will we modify the above construction of final coalgebras to get general small limits in Coalg(C, D) ? Consider the task of finding a product of objects R_{1} and R_{2} in this category, i.e., an object universal among coalgebras R with morphisms f_{1} : R → R_{1} and f_{2} : R → R_{2}. Such a pair of maps corresponds, at the algebra level, to a map f : |R| → |R_{1}| × |R_{2}|; let us call the latter algebra S_{base}. To express in terms of f the fact that f_{1} and f_{2} are compatible with the co-operations of R_{1} and R_{2}, let us, for each α ∈ Ω_{D}, define S_{α} to be the C-algebra ∐_{ari(α)} |R_{1}|×∐_{ari(α)} |R_{2}|. The ari(α) coprojection maps |R_{i}| → ∐_{ari(α)} |R_{i}| (i = 1, 2) induce ari(α) maps S_{base} → S_{α}; let us call these “pseudocoprojections”; thus, each S_{α} is an object of C with ari(α) pseudocoprojection maps of S_{base} into it, and an additional map of S_{base} into it, induced by α^{R_{1}} and α^{R_{2}}, which we shall call the “pseudo-co-operation” α^{S}. We shall call systems S of objects and morphisms of the sort exemplified by this construction “pseudocoalgebras” (Definition 4.1 below).

Then a coalgebra R with morphisms into R_{1} and R_{2} can be regarded as a coalgebra with a morphism into the above pseudocoalgebra S. More generally, if we are given any small diagram of coalgebras, then a cone from a coalgebra R to that diagram is equivalent to a morphism from R to an appropriate pseudocoalgebra. Thus, it will suffice to show that for every pseudocoalgebra S, the category of coalgebras with morphisms to S has a final object. The construction sketched above for final coalgebras in fact goes over with little change to this context.

After obtaining this existence result in the next two sections, we will show that in many cases, these colimits can be constructed more explicitly, as inverse limits of what we shall call “precoalgebras”. (The example mentioned above where the final coalgebra is the Cantor set will lead us to that approach.)

3. Subcoalgebras of bounded cardinality.

Recall that λ_{C} is a regular infinite cardinal such that every primitive operation of α ∈ Ω_{C} has ari(α) < λ_{C}. A standard result is

3.1. Lemma. [6, Lemma 8.2.3] If A is an algebra in C and X a generating set for A, then every element of A is contained in a subalgebra generated by < λ_{C} elements of X.

Let us fix a notation for algebras presented by generators and relations. For any set X, let F_{C}(X) denote the free algebra on X in C. If Y is a subset of |F_{C}(X)| × |F_{C}(X)|, let ⟨X | Y ⟩_{C} be the quotient of F_{C}(X) by the congruence generated by Y. If A is a C-algebra, a presentation of A will mean an isomorphism with an algebra ⟨X | Y ⟩_{C}. Every algebra A has a canonical presentation, with X = |A|, and Y consisting of all pairs (α_{F_{C} (X)}(x), α_{A}(x)) with α ∈ Ω_{C} and x ∈ |A|^{ari(α)}.

If X_{0} is a subset of X, we shall often regard F_{C}(X_{0}) as a subalgebra of F_{C}(X). Here is the analog of the preceding lemma for relations.

3.2. Corollary. Let A = ⟨X | Y ⟩_{C}, let X_{0} be a subset of X, and let p and q be elements of F_{C}(X_{0}) which fall together under the composite of natural maps F_{C}(X_{0}) ↪ F_{C}(X) → A.

Then there exist a set X_{1} with X_{0} ⊆ X_{1} ⊆ X, and a set Y_{1} ⊆ Y ∩ (|F_{C}(X_{1})| × |F_{C}(X_{1})|), such that the difference-set X_{1} − X_{0} and the set Y_{1} both have cardinality < λ_{C}, and such that p and q already fall together under the composite map F_{C}(X_{0}) ↪ F_{C}(X_{1}) → ⟨X_{1} | Y_{1}⟩_{C}.

Proof. By hypothesis, (p, q) lies in the congruence on F_{C}(X) generated by Y. A congruence on F_{C}(X) can be described as a subalgebra of F_{C}(X) × F_{C}(X) which is also an equivalence relation on |F_{C}(X)|, and the latter condition can be expressed as saying that it contains all pairs (r, r) (r ∈ |F_{C}(X)|), and is closed under both the unary operation (r, s) ↦ (s, r) and the partial binary operation carrying a pair of elements of the form ((r, s), (s, t)) to the element (r, t).

We can apply the preceding lemma to this situation, either using the observation that the proof of that lemma works equally well for structures with partial operations, or by noting that if we extend the above partial operation to a total operation by making it send ((r, s), (s′, t)) to (r, s) if s ≠ s′, then closure under that total operation is equivalent to closure under the given partial operation. Either way, we get the conclusion that if we extend the C-algebra structure of F_{C}(X) × F_{C}(X) to embrace the two additional operations expressing symmetry and transitivity, then our given element (p, q) lies in the subalgebra of the resulting structure generated by some subset

Y_{0} ⊆ Y ∪ {(r, r) | r ∈ |F_{C}(X)|}

of cardinality < λ_{C}. The elements of Y_{0} coming from Y will form a set Y_{1} of cardinality < λ_{C}, and by the preceding lemma, each component of each of these elements will lie in the subalgebra of F_{C}(X) generated by some subset of X of cardinality < λ_{C}, and the same will be true of each of the < λ_{C} elements r occurring in pairs (r, r) ∈ Y_{0}. As λ_{C} is a regular cardinal, the union of these subsets will be a set X′_{1} ⊆ X of cardinality < λ_{C} such that Y_{0} lies in |F_{C}(X′_{1})|×|F_{C}(X′_{1})|. By construction, (p, q) lies in the subalgebra of this product generated by Y_{0} under our extended algebra structure. Letting X_{1} = X_{0} ∪ X′_{1}, we conclude that p and q fall together in ⟨X_{1} | Y_{1}⟩_{C}, as claimed, and that X_{1} and Y_{1} satisfy the desired cardinality restrictions.

(Incidentally, this proof would not have worked if we had rendered the elements (r, r) by zeroary operations, rather than generating elements, since |F_{C}(X_{1})|×|F_{C}(X_{1})| would not have been closed in |F_{C}(X)| × |F_{C}(X)| under all these operations.)

To go from the bounds on the cardinalities of the sets constructed in the above lemma and corollary to bounds on the cardinalities of the algebras they generate, we will want

3.3. Definition. If κ is a cardinal and λ an infinite cardinal, then κ^{λ−} will denote the least cardinal μ ≥ κ such that μ^{ι} = μ for all ι < λ.

To see that this makes sense, note that κ^{λ} is not changed on exponentiating by λ, hence, a fortiori, it is not changed on exponentiating by any positive ι < λ, so the class of cardinals μ with that property is nonempty; hence it has a least member.

Immediate consequences of the above definition are

(κ^{λ−})^{λ−} = κ^{λ−}.  (2)
max(κ, μ)^{λ−} = max(κ^{λ−}, μ^{λ−}).  (3)

Note also that for ι < λ and κ > 1 we have κ^{λ−} ≥ κ^{ι} > ι. Hence

If κ > 1, then κ^{λ−} ≥ λ.  (4)

We also see

For all κ > 1 one has κ^{ℵ_{0}−} = max(κ, ℵ_{0}).  (5)

(Leo Harrington has pointed out to me that for λ a regular cardinal, which will always be the case below, what I am calling κ^{λ−} can be shown equal to what set theorists call κ^{<λ}, namely sup_{ι<λ} κ^{ι}. However, we shall not need this fact.)

The following result is very likely known.

3.4. Lemma. If a C-algebra A is generated by a set X, then

card(|A|) ≤ max(card(X), card(Ω_{C}), 2)^{λ_{C} −}.

Proof. We construct subsets X_{0} ⊆ X_{1} ⊆ ⋯ ⊆ X_{λ_{C}} of |A| as follows: Take X_{0} = X. For every successor ordinal ι+1 let X_{ι+1} consist of all elements of X_{ι} and all elements of the form α_{A}(x) where α ∈ Ω_{C} and x = (x_{γ})_{γ∈ari(α)} ∈ X_{ι}^{ari(α)}. For every limit ordinal ι let X_{ι} = ⋃_{η∈ι} X_{η}.

Since λ_{C} is a regular cardinal exceeding all the cardinals ari(α) (α ∈ Ω_{C}), we see that X_{λ_{C}} is closed under the operations of C, so as it contains X_{0} = X, it is all of |A|. Let us now show by induction that for all ι ≤ λ_{C},

card(X_{ι}) ≤ max(card(X), card(Ω_{C}), 2)^{λ_{C} −}.  (6)

Clearly, (6) holds for ι = 0. Let us write μ for the right-hand side of (6), which is independent of ι, and by (4) is ≥ λ_{C}. At each successor ordinal ι+1, the number of elements we adjoin as values of each operation α_{A} is at most card(X_{ι})^{ari(α)} ≤ μ^{ari(α)} ≤ μ, since ari(α) < λ_{C}. Hence, doing this for all card(Ω_{C}) operations brings in ≤ μ·card(Ω_{C}) ≤ μ elements. Likewise, at a limit ordinal ι, we take the union of a family of card(ι) ≤ λ_{C} ≤ μ sets of cardinality ≤ μ, hence again get a set of cardinality ≤ μ.

Taking ι = λ_{C} in (6), we get card(|A|) ≤ μ, as required.

For the step in our proof where we will enlarge an arbitrary subalgebra of |R| to a subcoalgebra of R, we will first need to define “subcoalgebra”. For this in turn we will need

3.5. Definition. A subalgebra A of a C-algebra B will be called copower-pure if for every cardinal κ, the induced map

∐_{κ} A → ∐_{κ} B is one-to-one.  (7)

When this holds, we shall often identify ∐_{κ} A with its image in ∐_{κ} B .

An example of a subalgebra which is not copower-pure was noted in [7, discussion preceding Question 4.5]: Let C be the variety of groups determined by the identities satisfied in the infinite dihedral group, which include x^{2}y^{2} = y^{2}x^{2}, but not xy = yx, nor x^{n} = 1 for any n > 0. Let B be the infinite cyclic group ⟨x⟩, which is free on one generator in C, and A the subgroup ⟨x^{2}⟩ ⊆ B . Then B ∐ B is the free C-algebra on two generators, x_{0} and x_{1}, hence is noncommutative, hence the same is true of A ∐ A. But the image of A ∐ A in B ∐ B is generated by x_{0}^{2} and x_{1}^{2}, which commute by the identity noted; so the map A ∐ A → B ∐ B is not an embedding.

3.6. Lemma. A subalgebra A of a C-algebra B is copower-pure if and only if (7) holds for all κ < λ_{C}.

Proof. “Only if” is clear; for the converse, assume (7) holds whenever κ < λ_{C}. Suppose we are given κ not necessarily < λ_{C}, and distinct elements p, q ∈ | ∐_{κ} A|. Since ∐_{κ} A is generated by the images of A under the κ coprojection maps, we see from Lemma 3.1 that p and q will lie in the subalgebra generated by the copies of A indexed by some subset I ⊆ κ with 0 < |I| < λ_{C}. Now a set-theoretic retraction of κ onto I (a left inverse to the inclusion of I in κ) induces algebra retractions ∐_{κ} A → ∐_{I} A and ∐_{κ} B → ∐_{I} B, making a commuting square with the maps ∐_{κ} A → ∐_{κ} B and ∐_{I} A → ∐_{I} B. By choice of I, the elements p and q lie in the subalgebra ∐_{I} A ⊆ ∐_{κ} A, and since |I| < λ_{C}, the map ∐_{I} A → ∐_{I} B is one-to-one; so p and q have distinct images in ∐_{I} B, and hence in ∐_{κ} B.

We are now ready for

3.7. Definition. If R and R′ are D-coalgebras in C, then we will call R′ a subcoalgebra of R if |R′| is a copower-pure C-subalgebra of |R|, and for each α ∈ Ω_{D}, the co-operation α^{R′} is the restriction to |R′| ⊆ |R| of α^{R}.

Thus, for a subalgebra A ⊆ |R| to yield a subcoalgebra of R, it must be copower-pure, and have the property that each α^{R} carries A into ∐_{ari(α)} A.

(Remark: It would probably be more natural in the above definition to require (7) to hold only for κ < λ_{D}; and perhaps to remove that condition entirely when the arities of the operations of D are all ≤ 1. But for simplicity, we will stick with the above definition.)

We shall now prove the existence of subcoalgebras satisfying cardinality bounds, as sketched earlier. (Note that the “μ” of the next result is not necessarily the same as the value so named in the proof of Lemma 3.4, since it also involves card(Ω_{D}).)

3.8. Theorem. Let R be a D-coalgebra object of C, and X a subset of ||R||. Then R has a subcoalgebra R′ whose underlying set contains X, and has cardinality at most

μ = max(card(X), card(Ω_{C}), card(Ω_{D}), 2)^{λ_{C} −}.  (8)

Proof. We shall construct a chain of subalgebras A_{0} ⊆ A_{1} ⊆ ⋯ ⊆ A_{λ_{C}} of |R|, and show that A_{λ_{C}} is the underlying C-algebra of a subcoalgebra R′ with the asserted properties.

We take for A_{0} the subalgebra of |R| generated by X; by Lemma 3.4 this has cardinality ≤ μ.

Assuming for some ι < λ_{C} that A_{ι} has been constructed, and has cardinality at most μ, we obtain A_{ι+1} by adjoining ≤ μ further elements chosen as follows.

First, for every κ < λ_{C}, and every pair of elements p, q ∈ | ∐_{κ} A_{ι}| which have equal image under the natural map ∐_{κ} A_{ι} → ∐_{κ} |R|, I claim we can adjoin to A_{ι} a set of < λ_{C} elements whose presence causes the images of these elements in the copower of the resulting algebra to fall together. Indeed, this follows from Corollary 3.2, and the observation that given a presentation |R| = ⟨X | Y ⟩_{C}, the copower ∐_{κ} |R| can be presented by taking the union of κ copies of X, and for each of these, a copy of Y. Note also that ∐_{κ} A_{ι} is generated by κ copies of A_{ι}, which has cardinality ≤ μ; hence by Lemma 3.4 it itself has cardinality ≤ μ, hence there are at most μ such pairs p, q to deal with; so for each κ < λ_{C}, we are adjoining at most μ elements. The number of such cardinals κ is ≤ λ_{C}; so in handling all such pairs p, q, for all κ < λ_{C}, we adjoin ≤ μ new elements of |R| to A_{ι}.

In addition, for each operation symbol α ∈ Ω_{D}, and each p ∈ |A_{ι}|, consider the image of p under the co-operation α^{R} : |R| → ∐_{ari(α)} |R|. By Lemma 3.1, this will lie in the subalgebra of ∐_{ari(α)} |R| generated by a subset X_{p,α}, having cardinality < λ_{C}, of the generating set for that copower given by the union of the images of the coprojections. So X_{p,α} is contained in the union of the images, under those coprojections, of a set X′_{p,α} of < λ_{C} elements of |R|. For each p ∈ |A_{ι}| and α ∈ Ω_{D}, let us include such a set X′_{p,α} in the set of elements we are adjoining to A_{ι}. Letting p run over the ≤ μ elements of A_{ι}, and α over the elements of Ω_{D}, we see that this process adjoins ≤ μ · card(Ω_{D}) · λ_{C} ≤ μ new elements. Let A_{ι+1} be the subalgebra of |R| obtained by adjoining to A_{ι} the two families of elements described in this and the preceding paragraph.

On the other hand, if ι is a limit ordinal, we let A_{ι} be the C-subalgebra of |R| generated by ⋃_{η∈ι} |A_{η}|. That union, being a union of ≤ λ_{C} sets of cardinality ≤ μ, will itself have cardinality ≤ μ, and it follows from Lemma 3.4 that A_{ι} will as well.

Now consider the subalgebra A = A_{λ_{C}} of |R|. Since λ_{C} is by assumption a regular cardinal, the union ⋃_{η∈λ_{C}} |A_{η}| involved in the construction of A is over a chain of cofinality λ_{C}, which strictly majorizes the arities of all operations of C; hence that union is closed under those operations, so |A| is that union.

I claim that A is copower-pure in |R|. Indeed, given any κ < λ_{C}, and elements p, q of ∐_{κ} A that fall together ∐_{κ} |R|, we can find < λ_{C} elements of A such that p and q lie in the subalgebra of ∐_{κ} A generated by images of those elements under coprojection maps; and we can then find some ι such that all those elements lie in A_{ι}. Thus we get p′, q′ ∈ | ∐_{κ} A_{ι}| which map to p, q ∈ | ∐_{κ} A|; so their images under the composite map ∐_{κ} A_{ι} → ∐_{κ} A → ∐_{κ} |R| fall together. Hence, by the construction of A_{ι+1}, the images of p′ and q′ fall together in ∐_{κ} A_{ι+1}, hence they do so in ∐_{κ} A, i.e., p = q, as required.

It remains to show that each co-operation α^{R} (α ∈ Ω_{D}) carries A ⊆ |R| into the subalgebra ∐_{ari(α)} A of ∐_{ari(α)} |R|. Every element p ∈ |A| lies in some A_{ι}, and by construction, A_{ι+1} contains elements which guarantee that α^{R}(p) lies in the subalgebra of ∐_{ari(α)} |R| generated by the image of ∐_{ari(α)} A_{ι+1}, hence, a fortiori, in ∐_{ari(α)} A.

3.9. Corollary. If R is a D-coalgebra object of C, then for every element p of |R| there is a subcoalgebra R′ of R whose underlying C-algebra contains p, and has cardinality at most max(card(Ω_{C}), card(Ω_{D}), 2)^{λ_{C} −}.

In particular, if C and D each have at most countably many operations, and all operations of C are finitary, then every element of a D-coalgebra object of C is contained in a countable or finite subcoalgebra.

4. Pseudocoalgebras, and the solution set condition.

We now come to the pseudocoalgebras of our sketched development.

4.1. Definition. By a D-pseudocoalgebra in a category A, we shall mean a 4-tuple

S = (S_{base}, (S_{α})_{α∈Ω_{D}}, (c_{α,ι}^{S})_{α∈Ω_{D}, ι∈ari(α)}, (α^{S})_{α∈Ω_{D}}),  (9)

where S_{base} and the S_{α} are objects of A (the “base object” and the “pseudocopower objects”), and for each α ∈ Ω_{D}, α^{S} (the α-th “pseudo-co-operation”) and the c_{α,ι}^{S} (the “pseudocoprojections”, one for each ι ∈ ari(α)) are morphisms S_{base} → S_{α}.

A morphism of D-pseudocoalgebras f : S → S′ will mean a family of morphisms

f_{base} : S_{base} → S′_{base}, and f_{α} : S_{α} → S′_{α} (α ∈ Ω_{D})  (10)

which make commuting squares with the c_{α,ι}^{S} and c_{α,ι}^{S′}, and with the α^{S} and α^{S′}. The category of D-pseudocoalgebras in A will be denoted Pseudocoalg(A, D).

Note that the operation-set Ω_{D} and arity-function ari_{D} of D come into the definition of D-pseudocoalgebra, but the identities of D do not. In the use we will make of pseudocoalgebras, the fact that those identities are, by definition, cosatisfied by the D-coalgebras we map to them will be all that matters. Let us make clear in what sense one can map coalgebras to pseudocoalgebras.

4.2. Definition. If R is a D-coalgebra, or more generally, an Ω_{D}-coalgebra, in A, then we define the associated D-pseudocoalgebra ψ(R) to have

ψ(R)_{base} = |R|, ψ(R)_{α} = ∐_{ari(α)} |R|,

c_{α,ι}^{ψ(R)} = the ι-th coprojection: |R| → ∐_{ari(α)} |R|, and

α^{ψ(R)} = α^{R} : |R| → ∐_{ari(α)} |R|.

Clearly, ψ yields a full and faithful functor Coalg(A, Ω_{D}-Alg) → Pseudocoalg(A, D), so when there is no danger of ambiguity, we shall treat Coalg(A, Ω_{D}-Alg) and its subcategory Coalg(A, D) as full subcategories of Pseudocoalg(A, D); in particular we shall speak of morphisms from coalgebras to pseudocoalgebras. If S is a Dpseudocoalgebra, then a D-coalgebra given with a morphism to S, i.e., an object of the comma category (Coalg(A, D) ↓ S), will be called a D-coalgebra over S.

We shall say that a pseudocoalgebra S “is an Ω_{D}-coalgebra” if it is isomorphic to ψ(R) for some Ω_{D}-coalgebra R, in other words, if for every α, the object S_{α} is the copower ∐_{ari(α)} S_{base}, with the pseudocoprojections c_{α,ι}^{S} as the coprojections. We will say that S is a D-coalgebra if it is an Ω_{D}-coalgebra R which cosatisfies the identities of D.

Note that if R is a coalgebra and S a pseudocoalgebra, then every morphism f : R → S is determined by f_{base} : |R| → S_{base}, since once this is given, the components f_{α} are uniquely determined by the property of making commuting squares with the coprojections and pseudocoprojections, via the universal property of ∐_{ari(α)} |R|. Of course, in general not every map f_{base} : |R| → S_{base} induces a morphism f : R → S, since the maps f_{α} so determined by f_{base} may fail to satisfy the remaining condition, that the squares they make with the co-operations and pseudo-co-operations commute.

We now again restrict attention to the case where the variety C plays the role of A. To the convention that “coalgebra”, unmodified, means “D-coalgebra in C” we add the convention that “pseudocoalgebra”, unmodified, means “D-pseudocoalgebra in C”. Note that these pseudocoalgebras are simply a kind of many-sorted algebra, so there is no difficulty constructing limits of such objects.

We recall from Lemma 1.1 that Coalg(C, D) has small colimits, given on underlying C-algebras by the colimits of the corresponding algebras in C. It follows that if we have a diagram of coalgebras over a fixed pseudocoalgebra S, its colimit coalgebra has an induced morphism into S, and so will also be the colimit of the given diagram in the comma category (Coalg(C, D) ↓ S).

4.3. Definition. A morphism of coalgebras will be called surjective if it is surjective on underlying C-objects.

If f : R → R′ is a surjective morphism in (Coalg(C, D) ↓ S), for some pseudocoalgebra S, then R′ (given with the map f from R) will be called an image coalgebra of R over S. To avoid dealing with the non-small set of isomorphic copies of each such image, we shall call an image coalgebra R′ of R standard if the map ||R|| → ||R′|| is the canonical map from a set to its set of equivalence classes under an equivalence relation.

A coalgebra R over S will be called strongly quasifinal over S if the only surjective morphisms out of R in (Coalg(C, D) ↓ S) are the isomorphisms.

Given a coalgebra R over a pseudocoalgebra S, the category of all standard images of R over S will form a partially ordered set, isomorphic to a sub-poset of the lattice of congruences on the C-algebra |R|. We cannot expect that the set of congruences on |R| such that the D-coalgebra structure of R extends to the resulting factor-algebra will be closed under intersections; but it will be closed under arbitrary joins, since, as just noted, colimits of coalgebras over S correspond to colimits of underlying C-objects. We deduce

4.4. Lemma. Let S be a pseudocoalgebra and R a coalgebra over S. Then the standard images of R over S form a (small) complete lattice. The greatest element of this lattice is, up to isomorphism, the unique strongly quasifinal homomorphic image of R over S.

We can now show that, up to isomorphism, the strongly quasifinal coalgebras over S form a small set.

4.5. Lemma. Let S be a pseudocoalgebra, and R a strongly quasifinal coalgebra over S. Then distinct subcoalgebras of R are nonisomorphic as coalgebras over S.

Hence in view of Corollary 3.9, card(||R||) is ≤ the sum of the cardinalities of all (up to isomorphism over S) coalgebras over S of cardinality at most

max(card(Ω_{C}), card(Ω_{D}), 2)^{λ_{C} −}.  (11)

This sum is at most

max(card(|S_{base}|), λ_{D})^{max(card(Ω_{C} ), card(Ω_{D}), 2)^{λ_{C} −}}.  (12)

Hence, up to isomorphism, there is only a small set of coalgebras R strongly quasifinal over S.

Proof. If we had two distinct embeddings into R over S of some coalgebra R′ over S, then the coequalizer of the resulting diagram R′ \overrightarrow{⟶} R would be a proper image of R over S, contradicting the strong quasifinality of R. This gives the assertion of the first paragraph. Hence if we break the subcoalgebras of R of cardinality at most (11) into their isomorphism classes over S, no more than one copy of each can occur, and by Corollary 3.9, such subcoalgebras have union R, giving the second assertion, from which the final sentence of the lemma clearly follows.

To get the explicit bound (12), let us write μ for the cardinal (11) and ν for (12). We shall show that the number of structures of coalgebra over S on a set X of cardinality ≤ μ is at most ν. Since there are ≤ μ < ν cardinalities ≤ μ, this will give ≤ ν isomorphism classes of strongly quasifinal coalgebras over S altogether, and since each such coalgebra has cardinality ≤ μ < ν, the sum of their cardinalities will be ≤ ν, as required.

To bound the number of structures of coalgebra over S on X, note that such a structure is determined by several maps (subject to restrictions that we will not repeat because they do not come into our calculations):

a map X → |S_{base}|,  (13)
for each α ∈ Ω_{C}, a map X^{ari(α)} → X,  (14)

making X a C-algebra A; and once this has been done,

for each α ∈ Ω_{D}, a map A → ∐_{ari(α)} A,  (15)

giving the D-coalgebra structure.

Given X of cardinality ≤ μ, the number of possible choices for (13) is bounded by card(|S_{base}|)^{μ}. For each α ∈ Ω_{C}, the number of choices for the map in (14) is ≤ μ^{μ^{ari(α)}}, but by definition (see (11)), μ is not increased by exponentiation by ari(α) < λ_{C}, so this bound is ≤ μ^{μ}. Letting α run over Ω_{C}, we conclude that the number of choices for (14) is ≤ (μ^{μ})^{card(Ω_{C} )} = μ^{μ card(Ω_{C} )}. But again by definition, μ ≥ card(Ω_{C}), so the product μ card(Ω_{C}) simplifies to μ; hence the number of choices for (14) is ≤ μ^{μ}.

Finally, for each α ∈ Ω_{D}, the copower in (15) will be generated by an ari(α)-tuple of copies of X, hence by a set of cardinality ≤ ari(α) μ ≤ λ_{D} μ, so by Lemma 3.4 that copower has cardinality ≤ max(λ_{D} μ, card(Ω_{C}), 2)^{λ_{C} −} = (λ_{D} μ)^{λ_{C} −} (since card(Ω_{C}) and 2 are majorized by μ). Hence for each α ∈ Ω_{D} the number of maps as in (15) is ≤ ((λ_{D} μ)^{λ_{C} −})^{μ} ≤ ((λ_{D} μ)^{μ})^{μ} = (λ_{D} μ)^{μ}. Letting α run over Ω_{D}, we get an additional factor of card(Ω_{D}) in the exponent, but this again is absorbed by μ. Bringing together the choices made in (13), (14) and (15), we get the bound

card(|S_{base}|)^{μ} μ^{μ} (λ_{D}^{μ} μ^{μ})  (16)

on the number of possible structures. Note also that for any infinite cardinal λ and any cardinal κ > 1, one knows that κ^{λ} > λ, hence λ^{λ} ≤ (κ^{λ})^{λ} = κ^{λλ} = κ^{λ}. Applying this with μ in the role of λ and λ_{D} in the role of κ, we see that the μ^{μ} terms can be dropped from (16). Rewriting the product as a maximum, and putting in the definition (11) of μ, we get the desired bound (12).

We deduce

4.6. Theorem. Let S be a pseudocoalgebra. Then the category of coalgebras over S has a final object. The cardinality of the underlying set of this object is at most (12).

Proof. Since the category has small colimits, and every object has a morphism into a strongly quasifinal object, and up to isomorphism there is only a small set of such objects, the dual statement to the Initial Object Theorem gives the required final object. Since a final object is in particular strongly quasifinal, the cardinality of its underlying set is bounded by (12).

We can now show Coalg(C, D) complete. Given a small category E and a functor F : E → Coalg(C, D), each coalgebra F (E) (E ∈ Ob(E)) can be regarded as a pseudocoalgebra, ψ(F (E)), and this system of pseudocoalgebras has a limit, which can be constructed objectwise. Let

S = \underleftarrow{lim}_{E} ψ F.

If R is a coalgebra, then a cone in Coalg(C, D) from R to the diagram of coalgebras F is equivalent to a morphism of pseudocoalgebras R → S. Hence the final object of (Coalg(C, D) ↓ S) corresponds to a limit of F. This gives

4.7. Theorem. Coalg(C, D) has small limits; equivalently, Rep(C, D) has small colimits. Moreover, given a small category E and a functor F : E → Coalg(C, D), we have

card(|| \underleftarrow{lim} F ||) ≤ max(card(\underleftarrow{lim}_{E} ||F (E)||), λ_{D})^{max(card(Ω_{C} ), card(Ω_{D}), 2)^{λ_{C} −}}.  (17)

Since most of algebra is done with finitary operations, and often with only finitely many of them, let us record what our result says in that case.

4.8. Corollary. If C and D each have only finitely many operations, and all of these are finitary, then the final D-coalgebra object of C has underlying set of at most continuum cardinality.

In fact, this remains true if “finitely many operations” is generalized to “at most countably many operations”, the assumption of finite arity on the operations of D (but not of C) is generalized to that of arity less than the continuum, and “the final D-coalgebra of C” is generalized to “the limit of any diagram of at most countably many D-coalgebra objects of C, each of which has underlying set of at most continuum cardinality.”

Proof. In the situation of the generalized statement, the right-hand side of (17) is bounded by

max((2^{ℵ_{0}})^{ℵ_{0}}, 2^{ℵ_{0}})^{max(ℵ_{0}, ℵ_{0}, 2)^{ℵ_{0}−}} = (2^{ℵ_{0}})^{ℵ_{0}^{ℵ_{0}−}} = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}}.

We can apply Theorem 4.6 to other pseudocoalgebras S than those arising from limit diagrams. One such application gives the next result; we omit the cardinality estimate, which the reader can easily supply.

4.9. Theorem. If A is an object of C, then there is a universal D-coalgebra object R of C with a C-algebra homomorphism |R| → A. In other words, the forgetful functor Coalg(C, D) → C has a right adjoint; equivalently, the functor Rep(C, D) → Rep(C, Set) given by composition with the underlying set functor on D has a left adjoint.

More generally, suppose D′ is a variety whose type Ω_{D′} is a “subtype” of Ω_{D}; i.e., such that the operation-symbols of D′ form a subset of the operation-symbols of D, and its arity function is the restriction of that of D. (We make no assumption on the identities of D′.) Then for any D′-coalgebra R′ of C there exists a universal D-coalgebra object R of C with a C-algebra homomorphism |R| → |R′| that respects D′-co-operations.

Proof. Let us establish the first assertion, then note how to adapt the argument to the second. Given A, we define a pseudocoalgebra S by letting S_{base} = A, and, for each α ∈ Ω_{D}, taking S_{α} to be the final object of C, with the unique maps from S_{base} to that final object serving (necessarily) both as pseudocoprojections c_{α,ι}^{S} and as pseudo-co-operations α^{S}. Then a morphism from a D-coalgebra object R of C to S is equivalent to a C-algebra homomorphism f : |R| → A. Thus, the final coalgebra R over S of Theorem 4.6 is a coalgebra with a universal map |R| → A.

Given D′ and R′ as in the second statement, we form the D′-pseudocoalgebra ψ(R′), and extend this to a D-pseudocoalgebra S by letting S_{α} be the final object of C for each α ∈ Ω_{D} − Ω_{D′}. The pseudocoprojections and pseudo-co-operations correspondinging to these α are uniquely determined, and the R given by Theorem 4.6 again has the desired universal property.

The construction of the first paragraph of the above theorem can be thought of as giving a “cofree coalgebra” on each object A of C; equivalently a “free” representable D-valued functor G on each representable set-valued functor E on C. The latter is not, of course, the composite of E with the free D-algebra functor F : Set → D, which is in general not representable. For instance, for C = Group, D = Ab, and E the underlying set functor U_{Group}, the representable functor G : Group → Ab “free” on E is the trivial functor, since there are no nontrivial representable functors Group → Ab, as follows from the description of all representable functors Group → Group that will be recalled in §13 below. In contrast, we will see in that section that for C = D = Group or C = D = Monoid, the free representable D-valued functor on any nontrivial representable set-valued functor is nontrivial, and easy to describe.

A generalization of the first paragraph of Theorem 4.9 that naturally suggests itself is that for every representable functor F : D → E between varieties, the induced functor F ∘ − : Rep(C, D) → Rep(C, E) should have a left adjoint. This seems likely to be true: In the case where F is underlying-set-preserving, one can prove it from the present second assertion of the theorem, by replacing D with an equivalent variety, having the original operations of D, plus some additional ones corresponding to those derived operations of D that yield the operations of E, so that F becomes a forgetful functor.

However, this generalization of the first assertion of the theorem, if true, would still not subsume the second assertion, since the latter does not assume that the forgetful functor D → Ω_{D′}-Alg has values in D′. The question of the “right” generalization of Theorem 4.9 obviously merits investigation. We shall, however, devote the rest of this note to exploring the constructions described by our theorems as stated.

5. Some examples with C = Set.

The proofs in the preceding section were quite uninformative as to the structures of the limit coalgebras obtained. To investigate these, let us use the heuristic of [6, §3.2]: To construct an object with a right universal property, consider an element x of a (not necessarily universal) object A of the desired sort, ask what data one can describe that such an element will determine, and what restrictions one can find that these data must satisfy. Then see whether the set of all possible values for data satisfying those restrictions can be given a structure of object of the indicated sort, induced by that of the assumed object A. If so, the result should be the desired universal object.

We will here apply this approach to the construction of the final object of Coalg(Set, Binar), where Binar is the category of sets with a single binary operation β, not subject to any identities.

Let S be the final Binar-pseudocoalgebra in Set, with S_{base} and S_{β} both 1-element sets. We want to find a right-universal coalgebra over S, so our heuristic says we should think about a general Binar-coalgebra R in Set over S, and an element x ∈ |R|. (Since C is here Set, what we would otherwise write ||R|| is simply |R|.)

Given x, the first datum that we get from it is its image in S_{base}; but this tells us nothing.

The structure of Binar-coalgebra on R also gives a map |R| → |R| ∐ |R|. Combining this with our “useless” map |R| → S_{base}, we get a map

|R| → |R| ∐ |R| → S_{base} ∐ S_{base}.  (18)

Identifying the right-hand side with {0, 1}, we thus see that we can associate to every element of |R| a member of the latter set.

Now that we have this map |R| → {0, 1}, we can combine it in turn with the cooperation, getting a composite map

|R| → |R| ∐ |R| → {0, 1} ∐ {0, 1} ≅ {0, 1} × {0, 1} = {0, 1}^{2}.  (19)

Here, in the “≅” step, we are using the identification X ∐ X ≅ {0, 1} × X for any set X. Thus, the first coordinate of the image of an element x ∈ |R| under (19) specifies which copy of |R| it is mapped into by β : |R| → |R| ∐ |R|. This was already determined by the image of x under (18); so the image of x under (19) is gotten by bringing in a second coordinate, specifying which “side” of the indicated copy of |R| the element x maps to.

Repeating this process, we find at the next step that each element of |R| determines an element of {0, 1}^{3} extending its image under (19); and so on. Thus, after countably many steps, we get a map

|R| → {0, 1}^{ω}.  (20)

There is no evident way to get more information out of an element of |R|, since its image under

|R| → |R| ∐ |R| → {0, 1}^{ω} ∐ {0, 1}^{ω} ≅ {0, 1} × {0, 1}^{ω}  (21)

is determined by its image in {0, 1}^{ω} : an element which maps to (a_{0}, a_{1}, a_{2}, …) under (20) can be seen to map to (a_{0}, (a_{1}, a_{2}, …)) under (21). This translates to say that (20) is a morphism of coalgebras from R to the coalgebra with underlying Setobject {0, 1}^{ω}, and co-operation

(a_{0}, a_{1}, a_{2}, …) ↦ (a_{0}, (a_{1}, a_{2}, …)) ∈ {0, 1} × {0, 1}^{ω} ≅ {0, 1}^{ω} ∐ {0, 1}^{ω}.  (22)

It is straightforward to verify that the map (20) we have built up is the unique morphism from R to this coalgebra; so this coalgebra structure on {0, 1}^{ω}, the Cantor set, makes it the final object of Coalg(Set, Binar). (This shows, by the way, that the cardinality bound of Corollary 4.8 is best possible, even in the case of the first paragraph thereof! The proof of that result shows that R is, however, a union of strongly quasifinal subcoalgebras of cardinality ≤ 2^{ℵ_{0}−} = ℵ_{0}; the reader might find it interesting to identify these.)

The representable functor Set → Binar determined by the above final coalgebra carries every set A to the set of all A-valued functions (with no continuity condition) on the Cantor set, furnished with the binary operation that takes two such functions f and g to the function β(f, g) which can be described – using the standard geometric picture of the Cantor set as a subset of the unit interval – as gotten by drawing the graphs of f and g on the real line, with a unit distance between them, then “compressing” the abscissa by a factor of 1/3, so that the resulting function again has domain the Cantor set.

The heuristic cited above said that after finding data that an element x of a coalgebra would determine, we should look for restrictions those data would have to satisfy. Above, we found no such restrictions, because the variety C had trivial algebra structure, the variety Binar involved no identities, and the pseudocoalgebra S was trivial.

The above example would be enough to motivate the construction of the next section; but having begun to look at representable functors from Set to algebras with one binary operation, let us see what happens when identities are imposed on that operation.

Because of the paucity of algebraic structure on Set, many natural identities can be realized by representable functors only in trivial ways. For instance, for the commutative identity

β(a, a′) = β(a′, a),

to be cosatisfied by S means that if we map any x ∈ |S | by β^{S} to |S | ∐ |S |, and then apply to its image the map that interchanges the two copies of |S | in that coproduct, the image is unchanged. No element x can have this property; hence |S | must be the empty set; so the only representable functor from Set to algebras with a commutative binary operation is the one taking all sets to the 1-element algebra.

An example of an identity of a less restrictive sort is

β(a, β(a′, a′′)) = β(a, β(a′, a′′′)),  (23)

saying that β(−, β(−, −)) is independent of its last argument. Letting D be the subvariety of Binar determined by (23), we find, as before, that the data one can get from an element x of any object S of Coalg(Set, D) is a string of 1’s and 0’s, and that the co-operation on these is given by (22). However, condition (23) says that if the image of x under β^{S} lies in the second copy of |S |, then on applying β^{S} again to that copy, the new image cannot also lie in the second copy of |S |; for its image therein would have to have equal images under any pair of maps a′′, a′′′ from |S | into any set. This says that the image of x ∈ |S | under (19) cannot be the string 11. Moreover, (23) applies to occurrences of β(−, β(−, −)) within larger expressions; hence the image of x under (20) cannot have two successive 1’s anywhere.

The set |R′| of sequences satisfying this condition forms the underlying set of the final object R′ of Coalg(Set, D); it constitutes a closed subset of the Cantor set which is uncountable, but has measure zero under the natural probability measure on that set. (That this subset has measure zero follows from the fact that the number of finite strings of length n with no two successive 1’s is the Fibonacci number f_{n+2}, and that f_{n+2}/2^{n} → 0 as n → ∞.) Geometrically, one obtains |R′| from the full Cantor set by deleting the right-hand half of the right-hand half-Cantor-set, and doing the same recursively to all the natural copies of the Cantor set within itself. (What I am calling a “half-Cantor-set” is the part of the Cantor set within one of the non-deleted “thirds” in its geometric construction.) Given any set A, the value of our representable functor Set → D at A consists of all A-valued functions on |R′|. To compose two such functions f and g, one again draws their graphs with unit space between them, but this time, one strikes off the right-hand side of the graph of g; only then will compressing the abscissa give a function β(f, g) on |R′|. It is not hard to see directly that this operation β satisfies (23).

Let us look next at the subvariety D of Binar determined by the identity superficially similar to (23),

β(a, β(a′, a′′′)) = β(a, β(a′′, a′′′)),  (24)

saying that β(−, β(−, −)) is independent of its middle argument. For an object S of Coalg(Set, D), this translates to say that the image of any x ∈ |S | under (20) can contain no 1 followed immediately by a 0. Thus, the only strings that can occur are those consisting of a (possibly empty, possibly infinite) string of 0’s followed, if it is finite, by an infinite string of 1’s. This set is still infinite, but is now countable. Writing x_{i} (i ∈ ω) for the string consisting of i 0’s followed by an infinite string of 1’s, and x_{ω} for the infinite string of 0’s, we conclude that the final object of Coalg(Set, D) has underlying set {x_{0}, x_{1}, …, x_{ω}}, and that the induced representable functor takes every set A to the set of all sequences (a_{0}, a_{1}, …, a_{ω}) ∈ A^{ω+1}, with operation β((a_{0}, a_{1}, …, a_{ω}), (b_{0}, b_{1}, …, b_{ω})) = (b_{0}, a_{0}, a_{1}, …, a_{ω}). One finds, incidentally, that this algebra satisfies the stronger identity

β(a, β(a′, a′′)) = β(a, a′′).  (25)

An identity with still more restrictive consequences is associativity,

β(a, β(a′, a′′)) = β(β(a, a′), a′′).  (26)

Here one easily verifies that the only strings in {0, 1}^{ω} that satisfy the corresponding condition are 00...0... and 11...1... . Calling these x_{0} and x_{1}, we find that the resulting representable functor takes a set A to A×A, with operation β((a_{0}, a_{1}), (b_{0}, b_{1})) = (a_{0}, b_{1}); in semigroup theorists’ language, a “rectangular band” [12].

Of course, the coalgebras described above are merely the final objects in their respective categories, not the only such objects. For instance, for D the subvariety of Binar determined by (24), a random example of a D-coalgebra object S of Set is the 2-element set |S | = {x, y} with the co-operation that, written as a map |S | → {0, 1} × |S |, has the form

x ↦ (1, y),  y ↦ (1, x).  (27)

This induces the functor that takes every set A to A × A with the binary operation

β((a, b), (a′, b′)) = (b′, a′),  (28)

which is easily seen to satisfy (24) (but which, unlike the initial representable functor with that property, does not satisfy (25)). The unique map of the above coalgebra to the final object in the variety of D-coalgebras carries both x and y to “11...1...”. Equivalently, the unique morphism from our initial representable functor Set → D to the functor given by (28) carries every sequence (a_{0}, a_{1}, …; a_{ω}) to (a_{0}, a_{0}).

6. Precoalgebras.

When we determined the final object of Coalg(Set, Binar) in the preceding section, the structure of its underlying algebra (i.e., set), the Cantor set, arose as the inverse limit of the system of finite sets

⋯ → {0, 1}^{n} → ⋯ → {0, 1}^{2} → {0, 1}^{1} → {0, 1}^{0}.  (29)

For none of the above sets were we given a map {0, 1}^{n} → {0, 1}^{n} ∐ {0, 1}^{n}. Rather, for each of them we had a map {0, 1}^{n} → {0, 1}^{n−1} ∐ {0, 1}^{n−1}. We shall abstract this sort of structure in the next definition.

I have so far avoided choosing a notation for the coprojection maps from an object to a copower of itself, though I have written the ι-th pseudocoprojection map of a pseudocoalgebra S as c_{α,ι}^{S} : S_{base} → S_{α}. Below, we will need to write down formulas relating pseudocoprojections and genuine coprojections; so given a cardinal κ, an object A of a category A having a κ-fold copower, and an ι ∈ κ, let us write the ι-th coprojection map of A into that copower as

q_{κ,ι}^{A} : A → ∐_{κ} A.  (30)

In the next definition, I use Latin rather than Greek letters for elements of the ordinal θ because in our main application, θ will be ω+1, and most of what we do will concern its finite elements. Also, on encountering expressions such as ∐_{ari(α)} (P_{j})_{base}, the reader should recall that, as indicated in §1, this denotes the ari(α)-fold copower of the single object (P_{j})_{base}, not the coproduct of a family of different objects.

6.1. Definition. Let θ be an ordinal and A a category with small coproducts. By a θ-indexed precoalgebra P of type Ω_{D} in A we will mean an inverse system of D-pseudo-coalgebras (P_{k})_{k∈θ} with connecting maps

p_{j,k} : P_{k} → P_{j} (j ≤ k ∈ θ)  (31)

satisfying (in addition to the properties defining an inverse system) the following two conditions:

(i) For every successor ordinal j +1 ∈ θ and every α ∈ Ω_{D}, we have

(P_{j+1})_{α} = ∐_{ari(α)} (P_{j})_{base},  (32)

with the pseudocoprojection associated with each ι ∈ ari(α) given by

c_{α,ι}^{P_{j+1}} = q_{ari(α),ι}^{(P_{j})_{base}} ∘ (p_{j,j+1})_{base}, i.e., the composite mapping

(P_{j+1})_{base} → (P_{j})_{base} → ∐_{ari(α)} (P_{j})_{base} = (P_{j+1})_{α},

(33)

and with the connecting map (p_{j,j+1})_{α} : (P_{j+1})_{α} → (P_{j})_{α} taken to be the unique map making commuting triangles with the pseudocoprojections c_{α,ι}^{P_{j}} of P_{j} and the genuine coprojection maps q_{ari(α),ι}^{(P_{j})_{base}} : (P_{j})_{base} → ∐_{ari(α)} (P_{j})_{base} = (P_{j+1})_{α}; that is, the unique map (p_{j,j+1})_{α} satisfying

(p_{j,j+1})_{α} _{∘} q_{ari(α),ι}^{(P_{j})_{base}} = c_{α,ι}^{P_{j}} for all ι ∈ ari(α).  (34)

(ii) For every nonzero limit ordinal k ∈ θ and every α ∈ Ω_{D}, we have

(P_{k})_{α} = \underleftarrow{lim}_{j<k}(P_{j})_{α}, with the connecting maps (p_{j,k})_{α} : (P_{k})_{α} → (P_{j})_{α} given by the universal cone associated with this inverse limit.

(35)

A morphism f : P → P′ of θ-indexed precoalgebras will mean a morphism of inverse systems of pseudocoalgebras, which “respects” the relation (32), in the sense that for every α ∈ Ω_{D} and every successor ordinal j +1 ∈ θ, the component (f_{j+1})_{α} : (P_{j+1})_{α} → (P′_{j+1})_{α} is the ari(α)-fold copower of the component (f_{j})_{base} : (P_{j})_{base} → (P′_{j})_{base}.

Note that the above definition does not specify the objects (P_{k})_{base}, the connecting maps (p_{j,k})_{base}, or the pseudo-co-operations α^{P_{k}}, nor, for k a limit ordinal, the pseudocoprojections c_{α,ι}^{P_{k}}. However, the description of P as an inverse system, together with the definition of a morphism of pseudocoalgebras, imply certain relations that these must satisfy. In particular, for k a limit ordinal, the pseudocoprojections and pseudoco-operations are uniquely determined by (35) as soon as (P_{k})_{base} and its cone of maps (p_{j,k})_{base} are given. Let us also verify that given ordinals j ≤ j′ with j′+1 ∈ θ, we have

(p_{j+1,j′+1})_{α} = ∐_{ari(α)} (p_{j,j′})_{base},  (36)

as one would expect from (32). This is trivial for j = j′. In the contrary case, by the definition of the right-hand side of (36), it suffices to prove that for all ι ∈ ari(α) we have (p_{j+1,j′+1})_{α} ∘ q_{ari(α),ι}^{P_{j′}} = q_{ari(α),ι}^{P_{j}} ∘ (p_{j,j′})_{base}. Substituting (p_{j+1,j′+1})_{α} = (p_{j+1,j′})_{α} ∘ (p_{j′,j′+1})_{α} into the left side of this equation, and (p_{j,j′})_{base} = (p_{j,j+1})_{base} ∘ (p_{j+1,j′})_{base} into the right side, and simplifying the results using (34) and (33) respectively, we see that the desired equality is a case of the commuting square relating pseudocoprojections under the map p_{j+1,j′} : P_{j′} → P_{j+1}.

The above definition, like the definition of a D-pseudocoalgebra S in §4, brings in D only through its type, Ω_{D}. In the definition of D-pseudocoalgebra, no more was needed; the identities of D came in via the genuine D-coalgebras mapped to S, whose colimit gave our final D-coalgebra. Here, however, we will be creating D-coalgebras out of precoalgebras, so we will need to introduce the concept of a precoalgebra cosatisfying an identity.

The analogs, in a precoalgebra P, of the primitive co-operations α^{R} (α ∈ Ω_{D}) of a coalgebra are the pseudo-co-operations α^{P_{k}}. We shall now form from these further maps, corresponding to derived operations, i.e., Ω_{D}-terms – expressions constructed by formal composition from primitive operations and projection operations (with the latter appearing only at the “bottom” step).

We need one bit of notation: If A and B are objects of a category A, κ is a cardinal such that ∐_{κ} A exists, and we are given a family of morphisms f_{ι} : A → B (ι ∈ κ), then ⋁_{ι∈κ} f_{ι} : ∐_{κ} A → B will denote the morphism (whose existence and uniqueness are guaranteed by the universal property of ∐_{κ} A) satisfying

(⋁_{ι∈κ} f_{ι}) ^{∘} q_{κ,η}^{A} = f_{η} for all η ∈ κ.  (37)

6.2. Definition. Suppose s is an Ω_{D}-term of arity γ, and P a θ-indexed precoalgebra of type Ω_{D} in a category A. For j ≤ k ∈ θ, a (j, k)-instance of s in P (unique, by the next lemma, if it exists for the given k, j and s) will mean a map

(P_{k})_{base} → ∐_{γ} (P_{j})_{base},

arising under the following recursive construction:

If s is the ι-th projection map for some ι ∈ γ, then for all j ≤ k ∈ θ, the (j, k)- instance of s is given by q_{γ,ι}^{(P_{j})_{base}} ∘ (p_{j,k})_{base}. (In particular, taking j = k, the (k, k)- instance of the ι-th projection s is the ι-th coprojection, q_{γ,ι}^{(P_{k})_{base}}.)

If s has the form α(u_{0}, u_{1}, …), where α ∈ Ω_{D}, and (u_{0}, u_{1}, …) is an ari(α)-tuple of Ω_{D}-terms (some or all of which may be projections and/or primitive operations), each of arity γ, and if for some i ≤ j < k ∈ θ we have, for each ι ∈ ari(α), an (i, j)-instance of u_{ι}, which we denote U_{ι} : (P_{j})_{base} → ∐_{γ} (P_{i})_{base}, then an (i, k)-instance of s is given by the composite map

(⋁_{ι∈ari(α)} U_{ι}) ∘ α^{P_{j+1}} ∘ (p_{j+1,k})_{base} : (P_{k})_{base} → (P_{j+1})_{base} → (P_{j+1})_{α} = ∐_{ari(α)} (P_{j})_{base} → ∐_{γ} (P_{i})_{base}.

(38)

Point (iii) of the following lemma is the uniqueness result mentioned in the first paragraph of the above definition.

6.3. Lemma. Let s be an Ω_{D}-term of arity γ, and P a θ-indexed precoalgebra of type Ω_{D}, for some ordinal θ. Then

(i) If for some i ≤ k ≤ k′ ∈ θ there exists an (i, k)-instance S of s in P, then there is also an (i, k′)-instance, given by S ∘ (p_{k,k′})_{base}.

(ii) If for some i′ ≤ i ≤ k ∈ θ there exists an (i, k)-instance S of s in P, then there is also an (i′, k)-instance, given by (∐_{γ}(p_{i′,i})_{base}) ∘ S.

(iii) If for some i ≤ k ∈ θ there exist (i, k)-instances of s in P, then all such instances are equal.

Proof. If s is a projection map, then (i) and (ii) follow immediately from the relation p_{i,k} = p_{i,j} ∘ p_{j,k}, and (iii) holds because there are no choices in that case of Definition 6.2. So assume s = α(u_{0}, u_{1}, …) as in the second part of Definition 6.2, and suppose inductively that the three statements are true for all the u_{ι} (ι ∈ ari(α)).

Statement (i) follows again from the formula (p_{j,k′})_{base} = (p_{j,k})_{base} ∘ (p_{k,k′})_{base}, applied in this case to the definition of an instance of s = α(u_{0}, u_{1}, …). Statement (ii) is obtained by combining that definition with the inductive assumption that (ii) holds for all u_{ι}.

In verifying (iii), note that given the inductive assumption that (iii) holds for all u_{ι}, the only place nonuniqueness can come into the definition of an (i, k)-instance of s is in the choice of j. So suppose we have i ≤ j < j′ < k, and that for each ι ∈ ari(α) there is an (i, j)-instance U_{ι} of u_{ι}. Then by part (i) and our inductive assumption, the unique (i, j′)-instance of each u_{ι} is given by U′_{ι} = U_{ι} ∘ (p_{j,j′})_{base}. We now evaluate (38) with j′ for j, getting the map

(⋁_{ι∈ari(α)} U′_{ι}) ∘ α^{P_{j′+1}} ∘ (p_{j′+1,k})_{base}

= (⋁_{ι∈ari(α)}(U_{ι} ∘ (p_{j,j′})_{base})) ∘ α^{P_{j′+1}} ∘ (p_{j′+1,k})_{base}

= (⋁_{ι∈ari(α)} U_{ι}) ∘ (∐_{ari(α)}(p_{j,j′})_{base}) ∘ α^{P_{j′+1}} ∘ (p_{j′+1,k})_{base}

= (⋁_{ι∈ari(α)} U_{ι}) ∘ (p_{j+1,j′+1})_{α} ∘ α^{P_{j′+1}} ∘ (p_{j′+1,k})_{base} (by (36))

= (⋁_{ι∈ari(α)} U_{ι}) ∘ α^{P_{j+1}} ∘ (p_{j+1,j′+1})_{base} ∘ (p_{j′+1,k})_{base}

= (⋁_{ι∈ari(α)} U_{ι}) ∘ α^{P_{j+1}} ∘ (p_{j+1,k})_{base},

(39)

giving the required equality of our two (i, k)-instances of s.

Let us define the depth of an Ω_{D}-term by taking projections to have depth 0, and recursively defining depth(α(u_{0}, u_{1}, …)), where α is a primitive operation, to be the ordinal sup_{ι∈ari(α)}(depth(u_{ι}))+1. Then one can verify by induction that in a θ-indexed precoalgebra of type Ω_{D}, an Ω_{D}-term s has a (j, k)-instance if and only if k ≥ j +depth(s).

We can now say what it means for a precoalgebra of type Ω_{D} to cosatisfy a system of identities.

6.4. Definition. Let P be a θ-indexed precoalgebra of type Ω_{D} in a category A.

Given Ω_{D}-terms s and t of the same arity γ, we shall say that P cosatisfies the identity s = t if for all j < k ∈ θ for which both a (j, k)-instance of s and a (j, k)- instance of t exist, these are equal as maps (P_{k})_{base} → ∐_{γ}(P_{j})_{base}.

If our category A is a variety C of algebras, we shall say that the identity s = t is cosatisfied at an element x ∈ |(P_{k})_{base}| if for all j < k ∈ θ for which both a (j, k)-instance of s and a (j, k)-instance of t exist, these agree on x.

Recalling from §1 that Φ_{D} denotes a set of defining identities for the variety D, we shall say that P is a D-precoalgebra if it is a precoalgebra of type Ω_{D} which cosatisfies each member of Φ_{D}.

Remarks. If two sets of identities for Ω_{D}-algebras, Φ_{D} and Φ′, are each derivable from the other by the standard method of computing with identities, then the same Ω_{D}- algebras satisfy Φ_{D} and Φ′, and the same Ω_{D}-coalgebras cosatisfy them. But it is not in general true that the same Ω_{D}-precoalgebras cosatisfy them. This is because when (for example) we deduce an identity s = t in Φ′ from the identities in Φ_{D}, the Ω_{D}-terms s and t may both have smaller depth than some terms of the identities of Φ_{D} from which we derived them, or than some terms appearing in intermediate steps of the derivation. (E.g., the group identities and the depth-3 identity ((x·x)·x)·x = x·x imply the depth-1 identity x · x = e.) Then s and t will admit (j, k)-instances for some pairs (j, k) such that not all terms of the original identities and/or intermediate steps do, so there is no way to deduce the cosatisfaction of all instances of s = t from the cosatisfaction of all instances of the identities of Φ_{D}.

On the other hand, for any j and k sufficiently far apart to accommodate all steps of a derivation of s = t from the identities of Φ_{D}, cosatisfaction of the identities of Φ_{D} does imply cosatisfaction of the (j, k)-instance of s = t. (This is why the coalgebras we will get by a limit process from our D-precoalgebras in the next section will cosatisfy all identities holding in the variety D, regardless of our choice of defining identities.)

It is to make the concept of a D-precoalgebra well defined despite the above phenomenon that we are using a nonstandard definition of variety, in which a variety D must be given with a specified set Φ_{D} of defining identities. Another way to get welldefinedness would have been to require that a D-precoalgebra cosatisfy all identities holding in D. But this would not have gotten around the underlying problem. For instance, if D_{1} and D_{2} are two varieties of the same type Ω_{D}, then under that definition, an Ω_{D}-precoalgebra might be both a D_{1}-precoalgebra and a D_{2}-precoalgebra without being a D_{1} ∩ D_{2}-precoalgebra, since it could cosatisfy all identities of D_{1} and of D_{2}, but fail to cosatisfy some identities that these together imply. And more important for us, in calculations such as those we will carry out in §§9-12 for particular varieties, it will be simplest if one only needs to study cosatisfaction of a fixed family of defining identities.

Back to the task at hand. Let S be a D-pseudocoalgebra in C. Then for any ordinal θ > 0 there is a natural recursive construction of a θ-indexed D-precoalgebra P having P_{0} = S. Namely, suppose 0 < k ∈ θ, and that the pseudocoalgebras P_{j} and connecting maps among them have been defined for all j < k, so as to make (P_{j})_{j<k} a k-indexed D-pseudocoalgebra. Let us describe how to define P_{k} and its maps to the P_{j}.

First suppose k is a successor ordinal, k = j +1. The objects (P_{j+1})_{α} (α ∈ Ω_{D}) and the connecting maps (p_{j,j+1})_{α} : (P_{j+1})_{α} → (P_{j})_{α} are determined by (32) and (34), so we need only construct (P_{j+1})_{base} and the maps coming from it. Let us start by forming a universal object having maps to all the necessary objects:

Q_{j+1} = (P_{j})_{base} × ∏_{α∈Ω_{D}}(P_{j+1})_{α}.  (40)

We regard Q_{j+1} as a candidate for (P_{j+1})_{base}, with the projection to (P_{j})_{base} as the candidate for the map (p_{j,j+1})_{base}, the projections to the (P_{j+1})_{α} as the candidates for the pseudo-co-operations α^{P_{j+1}}, and finally, with the candidate for each pseudocoprojection c_{α,ι}^{P_{j+1}} given, as required by (33), by the composite of the projection Q_{j+1} → (P_{j})_{base} with the ι-th coprojection q_{ari(α),ι}^{(P_{j})_{base}} : (P_{j})_{base} → ∐_{ari(α)}(P_{j})_{base} = (P_{j+1})_{α}.

In general, the maps described above will not satisfy the conditions required to give a morphism of pseudocoalgebras P_{j+1} → P_{j}. However, if we replace Q_{j+1} by the joint equalizer of the pairs of maps that need to agree, this gives us a universal k+1-indexed Ω_{D}-precoalgebra extending the given j +1-indexed D-precoalgebra. Passing, further, to the equalizer of all pairs of maps out of this subalgebra of Q_{j+1} that must agree if our Ω_{D}-precoalgebra is to cosatisfy the identities of Φ_{D}, and calling this new equalizer (P_{j+1})_{base}, we get a universal extension of our j +1-indexed D-precoalgebra (P_{i})_{i<j+1} to a k+1-indexed D-precoalgebra (P_{i})_{i≤j+1}.

If k is a limit ordinal, we similarly know that the objects (P_{k})_{α} (α ∈ Ω_{D}) must be defined by (35). In this case we take as our candidate for (P_{k})_{base} the object

Q^{k} = \underleftarrow{lim}_{j<k}(P^{j})^{base},  (41)

and as candidates for the maps (p_{j,k})_{base}, the universal cone of maps from this object to the (P_{j})_{base} (j < k). This automatically has pseudocoprojection and pseudo-co-operation maps, induced under the limit process by the pseudocoprojection and pseudo-co-operation maps of the P_{j} (j < k), which will make the necessary diagrams commute to give us an Ω_{D}-precoalgebra. Will it also cosatisfy the identities of D ? It will if D is finitary, since in that case, if we take such an identity s = t, and for some i < k calculate the (i, k)-instances of s and t, then our calculation will involve only finitely many indices j < k, so these indices will have a common strict upper bound k_{0} < k; and we can get (i, k_{0}+1)-instances of s and t, which by hypothesis will be equal; whence by Lemma 6.3(i) and (iii), our (i, k)-instances of s and t are also equal. For not necessarily finitary D, the same argument works if k has cofinality ≥ λ_{D}. If, finally, D is infinitary and k has cofinality < λ_{D}, and not all identities of D are cosatisfied by this Ω_{D}-precoalgebra, we replace Q_{k}, as before, with the joint equalizer of the relevant pairs of maps, i.e., we use the subalgebra (P_{k})_{base} ⊆ Q_{k} consisting of all elements at which these identities are cosatisfied.

Let us record the universal property of the above construction.

6.5. Proposition. Let S be a D-pseudocoalgebra in C, let θ > 0 be an ordinal, and let P be the θ-indexed D-precoalgebra with P_{0} = S constructed recursively as described above. Then P is final among θ-indexed D-precoalgebras P′ with P′_{0} = S, or more generally, given with a morphism P′_{0} → S.

In particular, if R is a genuine D-coalgebra with a morphism to S, then the precoalgebra formed by taking θ copies of R (regarded as pseudocoalgebras via the functor ψ), and connecting them by identity morphisms, admits a unique map to P extending the given map to S = P_{0}.

Let me sketch concretely how the morphism of the last paragraph above is obtained. Given k > 0, suppose that for all j < k we have obtained a unique family of morphisms of pseudocoalgebras f_{j} : R → P_{j} that make commuting triangles with the maps p_{i,j} : P_{j} → P_{i}, and such that f_{0} is the given map R → P_{0}. If k is a successor ordinal j +1, then for each α ∈ Ω_{D}, we must, by the definition of a morphism of precoalgebras, take (f_{j+1})_{α} to be ∐_{ari(α)}(f_{j})_{base} : ∐_{ari(α)} |R| → ∐_{ari(α)}(P_{j})_{base} = (P_{j+1})_{α}. To construct (f_{j+1})_{base}, we first map |R| into each of the components of the product algebra Q_{j+1} of (40): into (P_{j})_{base} by (f_{j})_{base}, and into each (P_{j+1})_{α} by composing the co-operation α^{R} of R with (f_{j+1})_{α}, described above. The combined map |R| → Q_{j+1} is easily shown to make commuting squares with maps down to the components of P_{j}. Moreover, the identities of D are cosatisfied at all elements of the image of that map |R| → Q_{j+1}, because they are cosatisfied by the coalgebra R. Hence the above map factors through the subalgebra (P_{j+1})_{base} ⊆ Q_{j+1}, giving the desired map (f_{j+1})_{base}.

If k is a limit ordinal, on the other hand, the maps (f_{k})_{α} are obtained from the maps (f_{j})_{α} (j < k) by the universal property of (P_{k})_{α} as a limit algebra, while (f_{k})_{base} is obtained, by this same property, as a map into Q_{k}, and is again seen to land in (P_{k})_{base} because R cosatisfies the identities of D.

Before applying precoalgebras to get a concrete description of the universal coalgebras of Theorem 4.6, let us note a couple of examples of the phenomenon alluded to in the remark following Definition 6.4: that two systems Φ_{D} and Φ′ of identities for Ω_{D}-algebras which are satisfied by the same class of algebras, and hence cosatisfied by the same class of coalgebras, may be cosatisfied by different classes of precoalgebras. As suggested there, let us take Φ_{D} to consist of the usual identities for groups together with the depth-3 identity ((x · x) · x) · x = x · x, and Φ′ to differ from Φ_{D} only in that the lastmentioned identity is replaced by x · x = e. Let C be any variety having a cogroup R which does not cosatisfy x · x = e; e.g., C = Group, and R = the coalgebra representing the identity functor. Let us define a 2-indexed Ω_{Group}-precoalgebra P in C by letting P_{0} and P_{1} both be R, with p_{0,1} the identity morphism. Then P cosatisfies the identities of Group, and vacuously cosatisfies the depth-3 identity ((x · x) · x) · x = x · x, since there are no instances of it to test; but it does not cosatisfy x · x = e, because there is an instance thereof, and its cosatisfaction would be equivalent to the cosatisfaction of that identity by R.

If the use of a 2-indexed precoalgebra here feels unsatisfying, we can get from this example an ω-indexed precoalgebra P with the same properties: Take P_{0}, P_{1}, and p_{0,1} as above, while for 2 ≤ k ∈ ω, let (P_{k})_{base} be the initial algebra in C. The remainder of the structure of P is uniquely determined by Definition 6.1, and it is easy to see that P still has the properties described above.

(The reader might find it amusing to try to find a precoalgebra cosatisfying Φ′, i.e., the group identities together with x · x = e, but not the set Φ′′ consisting of those same identities together with x · y = y · x, known to be implied in groups by the identity x · x = e. Since x · y = y · x has the same depth, 1, as x · x = e, one needs to modify the above trick – but only slightly.)

Let us also note why, in defining what it means for a precoalgebra P to cosatisfy an identity s = t, we restricted attention to (j, k)-instances with j strictly less than k. The only operations admitting (k, k)-instances are the projections; so essentially the only nontrivial identity having (k, k)-instances is x = y, which defines the trivial variety of any type. Cosatisfaction of the (k, k)-instance of this identity would be the statement that the two coprojections (P_{k})_{base} \overrightarrow{⟶} (P_{k})_{base} ∐ (P_{k})_{base} coincide. But the way we constructed the level P_{k} in our universal D-precoalgebra P involved taking equalizers of pairs of maps to objects of the previously constructed lower levels P_{j} (j < k); so that construction would have to be adjusted considerably to make it possible to impose cosatisfaction of the (k, k)-instance of x = y. Further, one of the objects so modified would be (P_{0})_{base}, contradicting our choice to let P_{0} be the given pseudocoalgebra S. In contrast, our slightly weaker definition of cosatisfaction allows us to treat x = y like other identities.

7. Coalgebras from precoalgebras.

Let us now see how to get coalgebras from the universal precoalgebras P constructed in Proposition 6.5.

A nice situation is if the construction of the P_{k} eventually “stabilizes”, in the sense that after some point, as one adds new steps, the connecting morphisms p_{j,k} are all isomorphisms of precoalgebras. (Having an isomorphism at one step is not enough to guarantee this. One may get a run of isomorphisms which, if extended far enough to test a certain identity, would fail to cosatisfy it; instead, our recursive construction modifies P_{k} by that step. One can bound the lengths of such unstable runs in terms of the depths of the identities of D; the bound will be at most λ_{D}.) If our construction does stabilize, then once that happens, the pseudocoprojection maps (P_{k})_{base} → (P_{k})_{α} become genuine coprojection maps (P_{k})_{base} → ∐_{ari(α)}(P_{k})_{base}, and the common value of the P_{k} will be the desired final D-coalgebra over the pseudocoalgebra S. Conversely, if for some k, P_{k} is in fact a D-coalgebra (i.e., if the pseudocopower objects are copowers of the base object, and the identities of D are cosatisfied in the resulting Ω_{D}-coalgebra), then our construction will stabilize at that point.

I do not know whether such stabilization always occurs:

7.1. Question. For all choices of varieties C and D, and pseudocoalgebra S, does the construction of Proposition 6.5 eventually stabilize, in the sense that there exists an ordinal θ_{0} such that whenever θ_{0} ≤ i < j < θ, the morphism p_{i,j} : P_{j} → P_{i} of (P_{k})_{k∈θ} is an isomorphism?

Assuming D finitary, we shall show below that if C belongs to a certain rather restricted class of varieties, then our construction indeed stabilizes by θ_{0} = ω; and that for a larger class of varieties C, containing more cases of interest, one can take P_{ω}, do a little trimming, and again get the desired final coalgebra over S.

To state the relevant conditions, recall that given small categories E and F and a functor G from E×F into a category A, if one forms limits over E and colimits over F in the two possible orders (assuming these limits and colimits exist), then their universal properties yield a comparison morphism

\underrightarrow{lim}_{Y ∈F} \underleftarrow{lim}_{X∈E} G(X, Y) → \underleftarrow{lim}_{X∈E} \underrightarrow{lim}_{Y ∈F} G(X, Y),

and that when this is an isomorphism, one says the indicated limit and colimit commute. We shall now show that if A is a variety C such that the above commutativity condition holds whenever we take for E the opposite of the ordered set ω and for F any finite set (each regarded as a category in the natural way), then the desired stabilization condition holds for all D-precoalgebras in C if the variety D is finitary; and we will note some C to which this result is applicable.

(We repeat a notational warning given earlier: In expressions like \underleftarrow{lim}_{k∈ω} ∐_{n} A_{k}, the symbol ∐_{n} indicates that we are taking the n-fold copower of what follows. The index running over n is not shown; in particular, it is not k, which here indexes the inverse limit. Note also that when we speak of an inverse limit over ω, or write \underleftarrow{lim}_{k∈ω}, it is understood that ω is made a category in the way opposite to its order structure.)

7.2. Proposition. Suppose A is a category having finite copowers and having inverse limits over ω, and suppose that these commute; i.e., that

For every inverse system of objects A_{k} of A indexed by ω, and every natural number n, the comparison morphism ∐_{n} \underleftarrow{lim}_{k∈ω} A_{k} → \underleftarrow{lim}_{k∈ω} ∐_{n} A_{k} is an isomorphism.

(42)

Suppose, further, that D is a finitary variety, and (P_{k})_{k∈ω} an ω-indexed D-precoalgebra in A, and that we extend this to an ω+1-indexed precoalgebra of type Ω_{D} by letting

(P_{ω})_{base} = \underleftarrow{lim}_{k∈ω}(P_{k})_{base},  (43)

with connecting maps (p_{k,ω})_{base} given by the canonical cone of maps from the above object to the objects (P_{k})_{base}. (As noted following Definition 6.1, this is enough to determine the extended Ω_{D}-precoalgebra, since ω is a limit ordinal.)

Then (P_{k})_{k∈ω+1} is again a D-precoalgebra. Moreover, P_{ω} is a D-coalgebra.

In particular, if A is a variety C, and P is the universal ω+1-indexed precoalgebra built from a pseudocoalgebra S as in Proposition 6.5, then P_{ω} is the final D-coalgebra in C over S.

Sketch of Proof. For each α ∈ Ω_{D}, note that

(P_{ω})_{α} = \underleftarrow{lim}_{k∈ω}(P_{k})_{α} = \underleftarrow{lim}_{0<k∈ω} ∐_{ari(α)}(P_{k−1})_{base} = \underleftarrow{lim}_{k∈ω} ∐_{ari(α)}(P_{k})_{base}

≅ ∐_{ari(α)} \underleftarrow{lim}_{k∈ω}(P_{k})_{base} = ∐_{ari(α)}(P_{ω})_{base} .

One finds that the pseudocoprojection maps (P_{ω})_{base} → (P_{ω})_{α} ≅ ∐_{ari(α)}(P_{ω})_{base} are the genuine coprojection maps, making P_{ω} a coalgebra. As discussed in the lines following (41), the fact that D is finitary and (P_{k})_{k∈ω} cosatisfies the defining identities of D as a precoalgebra implies that (P_{k})_{k∈ω+1} also cosatisfies them as a precoalgebra; and one deduces from this that P_{ω} cosatisfies them as a coalgebra, i.e., is a D-coalgebra.

The final assertion is easily seen from Proposition 6.5.

The next proposition establishes a sufficient condition for (42) (and another property we will subsequently find useful) to hold in a variety C. Let me illustrate the technical-looking hypothesis by contrasting the properties of coproducts in the two varieties Semigp and Monoid.

Given any semigroup A, consider the natural homomorphism from A ∐ A to the coproduct {x} ∐ {x} of two copies of the final (one-element) semigroup {x}. The two generators of {x} ∐ {x} are q_{2,0}^{{x}}(x) and q_{2,1}^{{x}}(x); and we see from the normal form for coproducts of semigroups that if an element u of A ∐ A maps to, say, q_{2,0}^{{x}}(x) q_{2,1}^{{x}}(x) q_{2,0}^{{x}}(x) in {x} ∐ {x}, then it must have the form q_{2,0}^{A}(y_{1}) q_{2,1}^{A}(y_{2}) q_{2,0}^{A}(y_{3}) in A ∐ A, for unique y_{1}, y_{2}, y_{3} ∈ |A|. On the other hand, in the variety Monoid, the coproduct of two copies of the final monoid {e} is again {e}, so every element of a monoid A ∐ A maps to the unique element thereof, so knowing that an element u ∈ |A ∐ A| maps to e does not yield a fixed monoid word that we can say represents u in terms of elements q_{2,0}^{A}(y_{i}) and q_{2,1}^{A}(y_{j}). We now state for a general variety C the condition we have shown that Semigp has, but Monoid does not have, letting {x} now denote the final (1-element) algebra of C :

For every u ∈ |{x} ∐ {x}| there exists a derived operation s_{u} of C such that

u = s_{u}(q_{2,0}^{{x}}(x), …, q_{2,0}^{{x}}(x), q_{2,1}^{{x}}(x), …, q_{2,1}^{{x}}(x)),

(say with n_{0} arguments q_{2,0}^{{x}}(x) and n_{1} arguments q_{2,1}^{{x}}(x)), and such that for every C-algebra A, and every element b ∈ |A ∐ A| which is carried to u by the map A ∐ A → {x} ∐ {x} induced by the unique map A → {x}, there exist unique elements b_{1}, …, b_{n_{0}+n_{1}} ∈ |A| such that

b = s_{u}(q_{2,0}^{A}(b_{1}), …, q_{2,0}^{A}(b_{n_{0}}), q_{2,1}^{A}(b_{n_{0}+1}), …, q_{2,1}^{A}(b_{n_{0}+n_{1}})).

(44)

The next result shows that condition (44) is useful, but restrictive.

7.3. Proposition. Let C be a finitary variety satisfying (44). Then it satisfies the two conditions

For every functor F : E → C where E is a connected small category, and every cardinal κ, the comparison morphism ∐_{κ} \underleftarrow{lim}_{E} F (E) → \underleftarrow{lim}_{E} ∐_{κ} F (E) is an isomorphism.

(45)

For every one-to-one homomorphism f : A → B of objects of C, and every cardinal κ, the induced map ∐_{κ} f : ∐_{κ} A → ∐_{κ} B is one-to-one. (In the language of Definition 3.5, every subalgebra of a C-algebra is copower-pure.)

(46)

Moreover, (44) holds, inter alia, in every finitary variety without zeroary operations and without identities, and also in the varieties Semigp and Ab; on the other hand, it does not hold in Monoid, Group or Lattice.

Proof. Using the observation that an n+1-fold coproduct A_{0} ∐ … ∐ A_{n} can be written as the n-fold coproduct (A_{0} ∐ A_{1}) ∐ A_{2} ∐ … ∐ A_{n}, it is easy to show by induction that (44) implies, for all positive integers n, the corresponding condition with pairwise copowers replaced by n-fold copowers; and using the fact that C is finitary, one passes in turn to the same result for κ-fold copowers, for any cardinal κ.

Fixing κ, let us now choose for each u ∈ | ∐_{κ}{x}| a derived operation s_{u} as in the version of (44) for κ-fold copowers, say of arity n_{u}. Then we see that the κ-fold copower functor on C can be described, at the set level, as the disjoint union over u of the functors X ↦ X^{n_{u}}. The disjoint union operation on sets commutes with limits over connected categories, and constructions X ↦ X^{n} commute with all limits, yielding the commutativity result (45). Similarly, disjoint unions and constructions X ↦ X^{n} respect one-one-ness, giving (46).

Let us now verify the assertions about particular varieties.

If C is a variety without zeroary operations and without identities, then every element of a coproduct algebra A ∐ B, where for notational convenience we assume A and B disjoint, can be written uniquely as a word in elements of A and elements of B, subject only to the condition that no operation occurring in this word has for its arguments elements of A alone or elements of B alone. (If there were zeroary operations, then these, and words involving them, would be counterexamples to this statement.) Comparing this normal form for elements of A ∐ A and their images in {x} ∐ {x}, we see that (44) holds in such varieties. The same applies to coproducts of semigroups, using the normal form for A ∐ B given by parenthesis-free products of elements of A and B, in which no two successive factors come from the same semigroup, and for Ab, using the normal form in which every element is written as the sum of an element of A and an element of B.

To prove (by a method different from our earlier informal sketch) that (44) does not hold for C = Monoid, and to get the corresponding results for Group and Lattice, we first note that {x} ∐ {x} is finite in each of these cases (the one-element algebra in the first two cases, since x is the identity element; a four-element lattice in the last). Hence if (44) held, the coproduct of two copies of any finite algebra in C would be finite. But from the standard normal forms we see that the coproduct of two copies of any nontrivial finite group or monoid is infinite. In the lattice case, we recall that the free lattice L on two generators is finite (|L| = {x_{0}, x_{1}, x_{0}∨x_{1}, x_{0}∧x_{1}}), but that the coproduct of two copies of this L, the free lattice on four generators, is infinite [10, §VI.8, Exercise 4] [6, Exercise 5.3.9].

The variety Monoid not only fails to satisfy (44), but also the consequence (45), including the case we are interested in, (42). For an element on the right side of the morphism of (42) can have images in the monoids ∐_{n} A_{k} whose lengths as monoid words increase without bound as a function of k (since the length of such a word will shorten under a monoid homomorphism whenever some factor maps to the identity element), and such an element cannot lie in the image of that morphism. This behavior has analogs in most naturally arising varieties of algebras. For instance, in lattices, the identity (x∨y)∧x = x has the consequence that a length-3 word (x∨y)∧x′ collapses to length 1 when x and x′ fall together, and one can use this to build counterexamples to (42).

In later sections, we will use Propositions 7.2 and 7.3 to get explicit descriptions of final coalgebras in certain varieties C satisfying (44), and hence (42). But since (42) excludes so many important cases, let us consider a condition on a variety C that is a little weaker, but has consequences that are almost as pleasant:

For every ω-indexed inverse system of objects A_{k} of C, and every natural number n, the comparison morphism ∐_{n} \underleftarrow{lim}_{k∈ω} A_{k} → \underleftarrow{lim}_{k∈ω} ∐_{n} A_{k} is oneto-one.

(47)

As before, we will supplement the next result with examples of varieties that satisfy its hypotheses and varieties that don’t. But these will take more work than before (inter alia because positive examples are more plentiful), so we will make them a separate following lemma.

7.4. Proposition. Suppose C is a variety of algebras which satisfies (46) and (47), D is a finitary variety, and P is any ω-indexed Ω_{D}-precoalgebra in C. Let (P_{k})_{k∈ω+1} be the ω+1-indexed extension of P obtained by constructing P_{ω} using (43). Then –

(i) For each subalgebra A of (P_{ω})_{base} and α ∈ Ω_{D}, the subalgebra of (P_{ω})_{α} generated by the images c_{α,ι}^{P_{ω}}(A) of A (ι ∈ ari(α)) can be identified with ∐_{ari(α)} A, with the restrictions of the maps c_{α,ι}^{P_{ω}} as its coprojections q_{ari(α),ι}^{A}.

(ii) The set of subalgebras A ⊆ (P_{ω})_{base} such that each pseudo-co-operation α^{P_{ω}} carries A into the above subalgebra ∐_{ari(α)} A ⊆ (P_{ω})_{α}, and which thereby become Ω_{D}-coalgebras with the restrictions of the α^{P_{ω}} as their co-operations, has a largest element. Let us denote this by |R|, and the resulting coalgebra by R.

(iii) If the Ω_{D}-precoalgebra P is a D-precoalgebra, then the above coalgebra R will be a D-coalgebra. If P is in fact the universal ω-indexed D-precoalgebra built from a pseudocoalgebra S, as in Proposition 6.5, then R is the final D-coalgebra over S.

Proof. For each α in Ω_{D}, the case of (i) with A = (P_{ω})_{base} follows from (43), (35) and (47), while (46) allows us to go from this case to that of any A ⊆ (P_{ω})_{base}.

Let me indicate two ways of obtaining the |R| of (ii): “from above” and “from below”. The former approach uses a transfinite recursion: Start with |R|_{(0)} = (P_{ω})_{base}, and

assuming recursively that |R|_{(η)} has been defined, let |R|_{(η+1)} be the subalgebra thereof consisting of all elements whose image in each (P_{ω})_{α} under α^{P_{ω}} (α ∈ Ω_{D}) lies in the subalgebra generated by the images of |R|_{(η)} under the c_{α,ι}^{P_{ω}}. For limit ordinals η, let |R|_{(η)} = ⋂_{ϵ<η} |R|_{(ϵ)}. Thus, we get a descending chain of subalgebras, which must stabilize because (P_{ω})_{base} has small underlying set, yielding the desired |R|.

For the alternative construction “from below”, let X be the set of all subalgebras A of (P_{ω})_{base} such that the image of A under each pseudo-co-operation lies in the subalgebra of (P_{ω})_{α} generated by the images of A under the pseudocoprojections. Then the algebra generated by all members of X will lie in X, and be the desired |R|.

For P a D-precoalgebra, as in (iii), we observed following (41) that (if D was finitary, as it is here,) the identities of D were cosatisfied in (P_{k})_{k∈ω+1}. As before, it is easy to deduce that they will also be cosatisfied in |R| as a coalgebra, and that for P obtained from P_{0} = S as in Proposition 6.5, R is the final D-coalgebra over S.

Conditions (46) and (47) tend to hold in varieties where coproducts have nice normal forms, as illustrated by the proof of the assertions of the first paragraph of the next result.

7.5. Lemma. In addition to the varieties C satisfying (44), conditions (46) and (47) hold in the varieties Group and Monoid, and in the varieties of all unital or nonunital, commutative or not-necessarily-commutative (four combinations in all) associative algebras over a field K. Hence, in these cases, Proposition 7.4 shows how to construct the final D-coalgebra in C whenever D is a variety of finitary algebras.

On the other hand, neither (46) nor (47) holds in the subvarieties of Group, Monoid and Semigp generated by the infinite dihedral group, nor in any of the four varieties of rings (ℤ-algebras) corresponding to the four varieties of K-algebras just mentioned.

Proof. To prove (46) and (47) in Monoid, recall that a coproduct ∐_{ι∈κ} A_{ι} in that category has a normal form almost like that of coproducts in Semigp: we again assume for notational simplicity that the A_{ι} are disjoint, and the normal form again consists of parenthesis-free finite products with no two successive factors coming from the same monoid A_{ι}. But these products are now subject to the restriction that no factor be the identity element 1 of the monoid from which it comes, while the length-zero product is allowed, and becomes the identity element of the coproduct monoid.

It is immediate that given submonoids A_{ι} ⊆ B_{ι}, an expression for an element of ∐_{ι∈κ} A_{ι} will be in normal form if and only if it is so in ∐_{ι∈κ} B_{ι}, so the inclusion of the former in the latter is one-to-one. The case where all B_{ι} are copies of a single monoid, and the submonoids A_{ι} are likewise equal, is (46). Under the hypothesis of (47), if an element of ∐_{n} \underleftarrow{lim}_{k∈ω} A_{k} is written in normal form, then the image of that normal form expression in any ∐_{n} A_{k} automatically satisfies the condition that successive factors come from different objects, while the statement that none of those factors is 1 constitutes a finite set of conditions, which will hold simultaneously for all sufficiently large k. Thus, elements in normal form in ∐_{n} \underleftarrow{lim}_{k∈ω} A_{k} map to elements in the ∐_{n} A_{k} that are in normal form for sufficiently large k; and increasing k still further if necessary, we can get any two elements of ∐_{n} \underleftarrow{lim}_{k∈ω} A_{k} with distinct normal forms to have images in ∐_{n} A_{k} with distinct normal forms; hence their images in \underleftarrow{lim}_{k∈ω} ∐_{n} A_{k} are distinct.

The considerations for groups are identical, since their normal form is the same as for monoids.

In the variety of associative unital K-algebras, one has an analogous normal form result for a coproduct ∐_{ι∈κ} A_{ι} of nonzero algebras: One chooses for each of the A_{ι} an arbitrary K-vector-space basis X_{ι} containing the identity element 1 ∈ |A_{ι}| and (again assuming the A_{ι} disjoint), the result says that the set of parenthesis-free products of nonidentity members of the union of these bases, in which no two successive factors come from the same X_{ι}, forms a K-vector-space basis of ∐_{ι∈κ} A_{ι}, with the empty product representing 1. So given nonzero algebras and subalgebras A_{ι} ⊆ B_{ι}, we may take a basis of each A_{ι} which contains 1, extend it to a basis of B_{ι}, and observe that an expression in normal form for a member of ∐_{ι∈κ} A_{ι} is also the expression in normal form for the image of that element in ∐_{ι∈κ} B_{ι}. As above, (46) follows. In the situation of (47), if we let X denote a K-vector space basis of \underleftarrow{lim}_{k} A_{k} containing 1, then the expression for any element of ∐_{n} \underleftarrow{lim}_{k} A_{k} involves the copies of only finitely many elements of X, and since these finitely many elements and 1 are linearly independent, they will have images in some A_{k} that are linearly independent, and so can be incorporated into a basis of that A_{k}; so with linear independence in place of distinctness, the argument from the monoid case also goes over. (As noted, the above normal form is restricted to nonzero algebras, equivalently, algebras in which 1 ≠ 0. Cases involving the zero algebra are trivial to handle.)

In the variety of “nonunital” associative K-algebras (meaning algebras without a zeroary operation giving a multiplicative identity element 1, which may or may not happen to have such an element, and where such elements, when they exist, need not be respected by homomorphisms), the normal form and the reasoning are very similar: one merely deletes all mention of identity elements, no longer allows length-zero products, and does not exclude the zero algebra.

Coproducts in varieties of commutative associative K-algebras have much simpler normal forms. In the unital case, one again takes a basis (which may, but need not, contain 1) for each algebra; a basis for an n-fold coproduct (n ∈ ω) is then given by the set of products of one basis element from each algebra, with factors 1 not excluded:

∏_{m=1,...,n} X_{m} = {x_{1} … x_{n} | x_{1} ∈ X_{1}, …, x_{n} ∈ X_{n}}.  (48)

In the nonunital case, this doesn’t suffice, since a product of basis elements from a proper subset of the X_{m} will not lie in (48); so we allow expressions with variable numbers of factors; a basis is given by

⋃_{∅≠s⊆{1,...,n}} ∏_{m∈s} X_{m}.  (49)

In either case, the reader can easily supply the arguments giving (46) and (47).

The first of our negative assertions concerns the variety C of groups generated by the infinite dihedral group. The example given following Definition 3.5 shows that (46) fails in that variety for κ = 2 and the inclusion 2ℤ → ℤ of infinite cyclic groups. For a counterexample to (47), we shall use an inverse system given by a chain ⋯ ⊆ A_{2} ⊆ A_{1} ⊆ A_{0} of subgroups of a certain group A; thus, the inverse limit of that system will be the intersection of those subgroups. Let A be the abelian group ℤ×⨁_{ω} ℤ/2ℤ, let q : ℤ → ℤ/2ℤ be the quotient map, and for each k ∈ ω, let A_{k} be the subgroup of A consisting of all elements (m; a_{0}, a_{1}, …) (m ∈ ℤ, a_{j} ∈ ℤ/2ℤ) such that q(m) = a_{0} = ⋯ = a_{k−1}. (As usual, the groups ℤ and ℤ/2ℤ are written additively; but A and its subgroups will be thought of as written multiplicatively, since we will be dealing with the noncommutative group structures of their copowers in C.) Letting z = (2; 0, 0, …) ∈ |A|, we see that in each A_{k}, z is a square, namely of any element (1; 1, …, 1, 0, …) with initial string of components 1 ∈ ℤ/2ℤ of length ≥ k; but the group \underleftarrow{lim}_{k∈ω} A_{k} = ⋂_{k∈ω} A_{k} has no elements with odd first component, since that would force infinitely many components of the ⨁_{ω} ℤ/2ℤ summand to be nonzero. Rather, we see that \underleftarrow{lim}_{k∈ω} A_{k} is free on the single generator z; hence the two copies of z in (\underleftarrow{lim}_{k∈ω} A_{k}) ∐ (\underleftarrow{lim}_{k∈ω} A_{k}) do not commute; but their images commute in \underleftarrow{lim}_{k∈ω}(A_{k} ∐ A_{k}), since z is a square in each A_{k}; so the map of (47) is not one-to-one.

Since these examples used identities not involving the inverse or identity-element operations, they also work in the subvarieties of Monoid and of Semigp generated by the infinite dihedral group.

In the four varieties of ℤ-algebras listed, one can get counterexamples using, similarly, cases where an element z in a subring B of a ring A, respectively in an inverse limit of rings A_{k} does not admit a solution to z = 2z_{0} in that subring or inverse limit, though it does in A, respectively in all the A_{k}. In this case, in place of the fact, used in the preceding examples, that in our subvarieties of Group, etc., squares commute but some non-squares do not, we can use the fact that in rings, an element z for which there is a solution to z = 2z_{0} must have product 0 with any element y satisfying 2y = 0, but that other elements z need not behave in this way. The reader should not find it hard to construct specific examples.

Our construction of the precoalgebra from which we obtained the final object of Coalg(Set, Binar) was in several ways simpler than the general construction summarized in Proposition 6.5 above. Point (iii) of the next result indicates a class of cases to which one of these simplifications applies.

7.6. Proposition. For S a pseudocoalgebra, let us, in this proposition, write π^{S} : S_{base} → ∏_{α∈Ω_{D}} S_{α} for the map induced by the pseudo-co-operations α^{S} : S_{base} → S_{α} (α ∈ Ω_{D}).

Let S be a D-pseudocoalgebra in C, θ > 0 an ordinal, and P the final θ-indexed D-precoalgebra with P_{0} = S, constructed as in Proposition 6.5. Then

(i) If π^{S} is one-to-one, then π^{P_{k}} is one-to-one for every k ∈ θ.

(ii) If π^{S} is surjective, and D has no identities (i.e., is the variety of all Ω_{D}-algebras), then π^{P_{k}} is surjective for all finite k ∈ θ.

(iii) If π^{S} is bijective (e.g., if S is the trivial pseudocoalgebra) and D has no identities, then π^{P_{k}} is bijective for every k ∈ θ.

In this last situation, if we use the bijections π^{P_{k}} to identify each (P_{k})_{base} with ∏_{α∈Ω_{D}}(P_{k})_{α}, then the homomorphisms (p_{j,k})_{base} : (P_{k})_{base} → (P_{j})_{base} correspond to the maps ∏_{α∈Ω_{D}}(P_{k})_{α} → ∏_{α∈Ω_{D}}(P_{j})_{α} induced by the maps (p_{j,k})_{α} : (P_{k})_{α} → (P_{j})_{α}.

Proof. We will get (i) and (iii) by transfinite induction on k, and show that surjectivity as in (ii) carries over from any ordinal j (finite or infinite) to its successor j +1, which by finite induction gives (ii).

First suppose k is a successor ordinal j +1, so that (P_{k})_{base} is constructed as in the discussion beginning with (40).

Under the hypothesis of (i), let s and t be distinct elements of (P_{j+1})_{base}; we need to show that they are separated by at least one of the pseudo-co-operations α^{P_{j+1}}. By the construction of P_{j+1} referred to, they are separated either by one of these, or by the map (p_{j,j+1})_{base} : (P_{j+1})_{base} → (P_{j})_{base}. In the latter case, by inductive assumption their images under this map are separated by some α^{P_{j}}, and from the commuting square made by α^{P_{j}} and α^{P_{j+1}}, we see that s and t are also separated by the latter map.

For (ii), consider any u in ∏_{α∈Ω_{D}}(P_{j+1})_{α}. By our assumption that (ii) holds for P_{j}, the image of u in ∏_{α∈Ω_{D}}(P_{j})_{α} can be written π^{P_{j}}(v) for some v ∈ |(P_{j})_{base}|. Let w = (v, u) ∈ |Q_{j+1}| = |(P_{j})_{base}| × | ∏_{α∈Ω_{D}}(P_{j+1})_{α}|. Our choice of v guarantees that w satisfies the equalizer conditions imposed, in the construction of (P_{j+1})_{base} from Q_{j+1}, to insure that p_{j,j+1} is morphism of pseudocoalgebras. The other equalizer conditions imposed there were to insure that the identities of D were cosatisfied, so for D having no identities, that set of conditions is empty. Hence (v, u) is an element of P_{j+1}, and it maps to u under π^{P_{j+1}}, as required.

The k = j +1 step for (iii) follows from the conjunction of the steps for (i) and (ii). (Although (ii) is only stated for finite k, we formulated our inductive step for an arbitrary successor ordinal, as required to obtain this step of (iii).)

In the case where k is an infinite limit ordinal, P_{k} is just the Q_{k} of (41) if D has no identities, as in (iii), or a subalgebra thereof in the general case. Since inverse limits preserve products, one-one-ness and bijectivity (though not, in general, surjectivity), the transfinite inductive steps of (i) and (iii) follow.

The condition that D have no identities in part (iii) above is highly restrictive; but in §5, after describing the final object of Coalg(Set, Binar) using that idea, we obtained the final objects of Coalg(Set, D), for subvarieties D of Binar defined by various identities, as subcoalgebras of that object. Points (ii) and (iv) of the next result note a general context in which this technique works.

7.7. Proposition. Let C be a variety satisfying (46), and D any variety. Let S (in parts (ii) and (iv) below) be any D-pseudocoalgebra in C, and let θ (in parts (iii) and (iv)) be any nonzero ordinal. Then

(i) The image of any homomorphism of D-coalgebras in C, f : R → R′, is a subcoalgebra of R′, and cosatisfies every identity that is cosatisfied by R or by R′.

(ii) If R′ denotes the final Ω_{D}-coalgebra over S, then the final D-coalgebra R over S can be identified with a subcoalgebra of R′, which will be the largest such subcoalgebra that cosatisfies the identities in Φ_{D}.

(iii) Given a homomorphism f : P → P′ of θ-indexed D-precoalgebras in C, let P′′ denote the system of subalgebras (P′′_{k})_{base} ⊆ (P′_{k})_{base} and (P′′_{k})_{α} ⊆ (P′_{k})_{α} given by the images of the components of f, except for (P′′_{k})_{α} when k is a nonzero limit ordinal, which, in accordance with (35), we define to be the subalgebra of (P′_{k})_{α} naturally isomorphic to \underleftarrow{lim}_{j<k}(P′′_{j})_{α}. Then P′′ is subprecoalgebra of P′, and cosatisfies every identity cosatisfied by P or by P′.

(iv) If P′ denotes the final θ-indexed Ω_{D}-precoalgebra with P′_{0} = S, then the final θindexed D-precoalgebra P with P_{0} = S can be identified with a subprecoalgebra of P′, which will be the largest such subprecoalgebra that cosatisfies the identities in Φ_{D}.

Proof. The hypothesis (46) insures that subalgebras in C are copower-pure. It is then easy to see that in (i), the image of f will be a subcoalgebra, and will cosatisfy the identities referred to. The argument for (iii) is similar. (The existence of a subalgebra of (P′_{k})_{α} naturally isomorphic to \underleftarrow{lim}_{j<k}(P′′_{j})_{α} follows from the fact that the (P′′_{j})_{α} are subalgebras of the (P′_{j})_{α}, mapped into one another by the connecting maps.)

To get (ii), we apply (i) to the case where R is the final D-coalgebra over S, R′ the final Ω_{D}-coalgebra over S, and f the morphism R → R′ given by the universal property of R′. By (i), f(R) is a coalgebra; so as R is strongly quasifinal over S, the map f : R → f(R) must be an isomorphism, so we may identify R with the subcoalgebra f(R) of R′. If R′ had any D-subcoalgebra R′′ not contained in R, then the unique map of R′′ to the final D-coalgebra R over S would give a map R′′ → R′ over S distinct from the inclusion, contradicting the universal property of R′.

Similarly, (iv) follows from (iii).

(Remark: The awkward construction of the precoalgebra P′′ of (iii) above is necessitated by (35). It might be preferable, instead, to modify the definition of precoalgebra by weakening (35) to merely require that for k a limit ordinal > 0, the natural map (P_{k})_{α} → \underleftarrow{lim}_{j<k}(P_{j})_{α} be a monomorphism. When A is a variety C this simply says that the family of maps (P_{k})_{α} → (P_{j})_{α} separates points of (P_{k})_{α}. If this change of definition proves feasible, then one could take P′′ in the above result simply to be the image of P in P′, in analogy with (i).)

We will apply these results to several examples in Part II below. We end Part I by noting –

8. A few directions for further investigation.

In [9, §§63-64], generalizing work of D. Tall and G. Wraith [21] [22, §9], I defined a “TWcomonad” on a variety C to be a representable functor F : C → C with a comonad structure (morphisms F → F F and F → Id_{C} making appropriate diagrams commute).

Actually, the main focus there was on the left adjoints of such functors, called “TWmonads”. As noted in [14], for any coalgebra R, the left adjoint to the functor represented by R can be viewed as a construction of “generalized tensor product with R. ” Coalgebras given with morphisms that make the functors they represent TW-comonads and the adjoints thereof TW-monads, I dubbed “TW-monad objects” in [9]. But since we have not dealt with left adjoints of representable functors here, I will mainly use the language of TW-comonads in these remarks. (To complicate things further, in [9] I also defined “WT-monads”, “WT-comonads”, and “WT-comonad objects”, to mean representable functors with monad structures, respectively their left adjoints, i.e., “tensor product-like” functors with comonad structures, respectively the coalgebras with additional structure that induce these functors. But these will not be relevant below.)

Recall that a “coalgebra object” with respect to a comonad F – a different usage from the sense of coalgebra with which we are concerned in this paper – means an object A of C with a morphism A → F (A) making appropriate diagrams commute. It was shown in [9] that coalgebra objects (in that sense) with respect to a TW-comonad are the same as algebra objects (in the analogous sense) with respect to the corresponding TW-monad, and that the category of these is equivalent to a new variety of algebras (in the sense of this paper), obtained by adjoining to C additional unary operations, corresponding to the elements of any generating set (as an algebra) for the representing coalgebra, and appropriate identities.

It was also noted that the initial representable functor from a variety C to itself (for the existence of which, in the general case, I referred to this not-yet-written paper) always has a structure of TW-comonad. For C = Ring^{1}, it was shown, using the description of the initial representable functor Ring^{1} → Ring^{1} as S ↦ S × S^{op}, that the coalgebras with respect to this comonad are the rings with involution (an involution meaning an antiautomorphism of exponent 2).

Now the concept of a ring with involution is of considerable independent interest; it gives, for instance, the class of rings over which one can define the conjugate transpose of a matrix, and hence such constructions as the group of unitary matrices. (The transpose operation alone, without conjugation, is of little use for matrices over noncommutative rings; it behaves nicely in the commutative case only because there, the identity map is an involution.) This suggests that for other varieties, the extensions arising from their initial representable endofunctors may also be of use. The initial representable endofunctors (final coalgebras) of several varieties will be determined in the remaining sections of this note. I have no present plans to pursue the study of the corresponding extended varieties; some reader might find it interesting to do so.

Of course, if we start with a variety such as Monoid or Group having a unique derived zeroary operation, then the initial representable functor, and hence the resulting TW-monad and comonad, are trivial by Theorem 2.1(ii). But if C is any variety, and we fix a nontrivial object A of C, then the comma category (A ↓ C) of C-algebras with homomorphisms of A into them can be regarded as a variety, with any generating set for A as additional zeroary operations; and perhaps the above construction on such varieties would give useful information.

It would be interesting to know whether the above “variety of coalgebras with respect to the initial representable endofunctor” construction is idempotent (up to natural equivalence).

To see another direction for investigation, let us start with the following observations: In Set, the kinds of algebra structures that can arise are extremely diverse, while coalgebra structures are much more limited. On the other hand, once one has varieties C of set-based algebras, the consideration of objects of C with algebra structure (in the sense of an algebra structure on an object of a general category A with products) gives nothing essentially new; an object of C with a C′-algebra structure is simply an algebra in yet another variety C′′. This can be thought of as a consequence of the fact that products in C′ are formed using products of underlying sets. (There are, though, some interesting questions on how C′′ relates to C and C′; cf. [6, §§9.12-13].)

However, coalgebra objects in a variety of algebras C can be very diverse [9].

In a category Coalg(C, D) of such coalgebras, if we now look at D′-coalgebra objects for another variety D′, this again gives nothing essentially new; these are simply D′′-coalgebra objects of C for an appropriate D′′; essentially because coproducts in Coalg(C, D) arise from coproducts of underlying C-algebras.

However, products in Coalg(C, D) do not in general arise from products of underlying C-algebras; they are examples of limits, which we have seen are “exotic” in these categories. So – what can one say about C′-algebra objects of Coalg(C, D), for C′ another variety? I don’t know.

We have seen (Theorem 4.9, first paragraph) that given varieties C and D, every object A of C determines an object R of Coalg(C, D) with a universal map |R| → A in C. This says that the contravariant functor Coalg(C, D) → Set given by S ↦ C(|S|, A) is represented by R. But, of course, the sets C(|S|, A) have natural structures of D-algebra, C(S, A); so the above coalgebra R has a D-algebra structure in Coalg(C, D). It would be desirable to understand this structure.

In addition to the above open-ended directions for investigation, there are several straightforward ways that it should be possible to generalize the results of this note. A quasivariety [13] is a class of algebras of a given type defined by identities and universal Horn sentences, i.e., universal equational implications. (For example, if, to the operations and identities for groups, we add the implications (∀ x) (x^{n}= e ⟹ x = e), one for each positive integer n, we get the quasivariety of torsion-free groups.) The left sides of these implications are required to be finite conjunctions of equations; if this finiteness restriction is removed, the resulting more general classes of algebras are called prevarieties. As is the case with identities, the satisfaction of such a universal implication by all the values of a representable functor F can be detected in the structure of the representing coalgebra R : An implication of this sort in κ variables holds for the values of F if and only if the joint coequalizer in C of the family of pairs of maps |R| → ∐_{κ} |R| corresponding to the hypotheses of the implication also coequalizes the pair of maps corresponding to the conclusion. One should be able to adapt the material of the preceding sections to the case where C and D are general prevarieties.

Categories of algebras in which some of the operations are partial, with domain given by the set at which specified relations in other operations hold (subject to conditions that avoid vicious circles) should also be amenable to such treatment. Cf. [5, §6] for a bit of motivation, and an example. (In contrast, the category of fields, where the domain of the inverse operation is the set of elements where the relation x = 0 does not hold, is notoriously uncooperative from the point of view of universal constructions.) The same should be true of categories of algebraic structures involving relations as well as operations (subject to appropriate sorts of axioms), and to categories of many-sorted algebras.

Indeed, it was this potential embarrassment of riches that led me to restrict the present development to varieties.

II. EXAMPLES.

In the remaining sections, we shall compute some explicit examples of limit coalgebras, especially final coalgebras.

9. The final object of Coalg(Binar, Binar).

In §5 we described the final co-Binar object of Set; let us now determine the final co-Binar object of Binar. As before, the unique element of Ω_{Binar}, i.e., the primitive binary operation of our algebras, will be denoted β.

Because our “C” is Binar, which has no identities, Propositions 7.2 and 7.3 tell us that we can get our final coalgebra as P_{ω}, where P is the ω+1-indexed precoalgebra built from the trivial pseudocoalgebra, and that this object P_{ω} will be the inverse limit of the P_{k} with k ∈ ω. On the other hand, because our “D” is Binar, Proposition 7.6(iii) tells us that each (P_{j+1})_{base} (j ∈ ω) can be constructed as (P_{j})_{base} ∐ (P_{j})_{base}. For that result says that the “product of pseudo-co-operations” map π^{P_{j+1}} is an isomorphism, and with only one pseudo-co-operation, π^{P_{j+1}} is just β^{P_{j+1}}.

Let us look at this last result in the more general context where D is still Binar and P_{0} is still the trivial pseudocoalgebra, but C is an arbitrary variety. Let us write (P_{0})_{base} as {x}, and express the fact that for every operation α of C, α(x, …, x) = x, by calling x “idempotent”. Thus (P_{1})_{base}, the coproduct of two copies of (P_{0})_{base} = {x}, will be freely generated as a C-algebra by two idempotent elements, which we shall denote x_{0} and x_{1}; (P_{2})_{base}, the coproduct of two copies of (P_{1})_{base}, will be freely generated by four idempotent elements x_{00}, x_{01}, x_{10}, x_{11}, etc.. We fix our notation so that for each idempotent generator x_{a} of (P_{j})_{base}, where a ∈ {0, 1}^{j}, the two coprojections (P_{j})_{base} → (P_{j})_{base} ∐ (P_{j})_{base} = (P_{j+1})_{base} take x_{a} to x_{0a} and x_{1a} respectively. It is then easy to verify by induction on j that the maps (p_{j,j+1})_{base} : (P_{j+1})_{base} → (P_{j})_{base} act by dropping indices from the other end of our subscripts, sending generators x_{a0} and x_{a1} of (P_{j+1})_{base} (a ∈ {0, 1}^{j}) to x_{a} in (P_{j})_{base}. Hence our inverse system of algebras (P_{k})_{base} (k ∈ ω) and their connecting morphisms takes the form

… → {x_{00}} ∐ {x_{01}} ∐ {x_{10}} ∐ {x_{11}} → {x_{0}} ∐ {x_{1}} → {x},  (50)

where the morphisms act by

x_{a i} ↦ x_{a} (a ∈ {0, 1}^{j}, i ∈ {0, 1}).  (51)

Back, now, to the case C = Binar. I claim that in this case one can encode elements of (P_{1})_{base} = {x_{0}} ∐ {x_{1}} by certain {0, 1}-valued functions on the Cantor set. We shall formally regard the Cantor set as {0, 1}^{ω}, but for convenience in description, I will often use language corresponding to the “middle thirds in the unit interval” Cantor set, referring, for instance, to the “left” and “right” halves of the set. (I hope this will be more helpful than confusing.) Here is the encoding:

The elements x_{0} and x_{1} will be represented by the constant functions 0 and 1 respectively. If two elements s and t are represented by functions f_{s} and f_{t} respectively, let us represent β(s, t) by the function whose graph on the “left half” of the Cantor set is a compressed copy of the graph of f_{s}, and on the “right half”, a compressed copy of the graph of f_{t}. In terms of strings of 0’s and 1’s (which we will write without parentheses or commas), this says that

f_{β(s,t)}(0a) = f_{s}(a), f_{β(s,t)}(1a) = f_{t}(a) (a ∈ {0, 1}^{ω}).  (52)

Note that (52) is consistent with the relations β(x_{0}, x_{0}) = x_{0}, β(x_{1}, x_{1}) = x_{1}; and that the {0, 1}-valued functions on {0, 1}^{ω} that we get by recursive application of (52) starting with the constant functions 0 and 1 are continuous relative to the standard topology on {0, 1}^{ω} and the discrete topology on {0, 1}. In fact, this construction yields a bijection between elements of {x_{0}} ∐ {x_{1}} and such continuous functions: this follows from the facts that every element y ∈ |{x_{0}} ∐ {x_{1}}| is uniquely expressible as β(s, t), where unless y is x_{0} or x_{1}, each of s and t has smaller depth than y; and that every continuous {0, 1}-valued function f on the Cantor set is uniquely expressible as in (52) for unique continuous functions g and h in place of f_{s} and f_{t}, where unless f is the constant function 0 or 1, these functions are constant on “coarser” clopen subsets than f.

In exactly the same way, elements of (P_{2})_{base} = {x_{00}} ∐ {x_{01}} ∐ {x_{10}} ∐ {x_{11}} may be represented by continuous {00, 01, 10, 11}-valued functions on {0, 1}^{ω}, and so forth. The connecting morphisms of (50), (51) are seen to correspond to the operation of sending {0, 1}^{j+1}-valued functions to {0, 1}^{j}-valued functions by dropping the final 0 or 1 in the output-symbols.

It is not hard to deduce that on passing to the inverse limit, we get a bijection between elements of (P_{ω})_{base} = \underleftarrow{lim}_{k∈ω}(P_{k})_{base} and functions \{0, 1\}^{ω} → \{0, 1\}^{ω} continuous with respect to the standard topology on both copies of {0, 1}^{ω}. The Binar-operation on this set is again described by (52).

Turning to co-operations, we have noted that by Proposition 7.6(iii), for each j ∈ ω, the pseudo-co-operation β^{P_{j+1}} : (P_{j+1})_{base} → (P_{j+1})_{β} = (P_{j})_{base} ∐ (P_{j})_{base} is an isomorphism, taking each generator of the form x_{0a} to q_{2,0}^{(P_{j})_{base}}(x_{a}), and each generator of the form x_{1a} to q_{2,1}^{(P_{j})_{base}}(x_{a}). Identifying (P_{j+1})_{β} with (P_{j+1})_{base} via this map, we see that the image of the first pseudocoprojection, c_{β,0}^{P_{j+1}} : (P_{j+1})_{base} → (P_{j+1})_{β}, is the subalgebra generated by the elements of the form x_{0a} (a ∈ {0, 1}^{j}), and that of the second pseudocoprojection, c_{β,1}^{P_{j+1}}, is the subalgebra generated by the elements x_{1a}. Passing to the inverse limit, and using the “middle thirds” image of the Cantor set, we see that q_{2,0}^{P_{ω}} acts by vertically compressing the graph of an element of P_{ω} so as to get a function taking values in the lower half of the Cantor set, while q_{2,1}^{P_{ω}} similarly compresses it to a function with values in the upper half. Regarding P_{ω} as a coalgebra R, the co-operation β^{R} : |R| → |R| ∐ |R| thus works by “breaking up” the graph of a general element y of R into segments in which the value is in the lower half-Cantor-set and segments in which it is in the upper half-Cantor-set (each segment having for domain a “sub-Cantor-set” consisting of all elements beginning with some specified string of 0-s and 1-s), and using this decomposition to write y as a β_{|R|}-word in the corresponding elements of q_{2,0}^{P_{ω}}(|R|) and q_{2,1}^{P_{ω}}(|R|).

This completes the description of the universal object R! (That description was sketched, without using the language of coalgebras, as [6, last two exercises of §8.3].)

Though the set ||R|| has a more complicated form than the underlying set of the initial object of Coalg(Set, Binar) found in §5, note that its cardinality is still that of the continuum; for a continuous map {0, 1}^{ω} → {0, 1}^{ω} is determined by its values at a countable dense subset of its domain, so there are at most (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}} such maps.

A curious property of this example is that not only does the co-operation β^{R} give an isomorphism of |R| with the coproduct in Binar of two copies of itself, as required by Proposition 7.6; the operation β_{|R|} likewise gives a bijection of ||R|| with the product in Set of two copies of itself. I do not know whether this is an instance of some general result.

The set ||R|| of continuous maps from the Cantor set to itself also has a natural monoid structure, given by composition of maps. I likewise do not know whether this has any interpretation as “additional structure” on the coalgebra R we have constructed.

10. The final object of Coalg(Binar, Semigp).

When we turn to co-Semigp objects of Binar, we cannot apply Proposition 7.6(iii) directly, since the variety Semigp is defined using a nonempty set of identities; but we can take the above description of the final Binar-precoalgebra and Binar-coalgebra, and use Proposition 7.7(iv) and (ii) to obtain the corresponding final Semigp-precoalgebra and coalgebra as substructures thereof. Let us write P′ for the precoalgebra we called P in the preceding section, and let P here denote the subprecoalgebra thereof determined by the condition that β cosatisfy the associative identity.

The first instance of that identity arises in P′_{2}. In constructing the two derived pseudoco-operation maps that we must equalize, we in each case begin by mapping (P′_{2})_{base} into (P′_{1})_{base} ∐ (P′_{1})_{base} by β^{P′_{2}}, and then map this, in different ways, into

(P′_{0})_{base} ∐ (P′_{0})_{base} ∐ (P′_{0})_{base}.  (53)

Namely, to get one derived pseudo-co-operation, we map our first (P′_{1})_{base} by β^{P′_{1}} into (P′_{0})_{base} ∐ (P′_{0})_{base}, which we identify with the subalgebra of (53) generated by the first two copies of (P′_{0})_{base}, while mapping the second (P′_{1})_{base} by (p_{0,1})_{base} into (P′_{0})_{base} which we identify with the third copy. To get the other derived pseudo-co-operation, we apply (p_{0,1})_{base} to our first (P′_{1})_{base}, and β^{P′_{1}} to the second, identifying its codomain with the subalgebra of (53) generated by the second and third copies. Denoting the images of the unique element x of (P′_{0})_{base} under the three coprojections into (53) by x_{λ}, x_{μ}, x_{ρ} (mnemonic for the left, middle and right terms in the associative law), we find that our two derived pseudo-co-operations act by

x^{00} ↦ x^{λ},  x^{01} ↦ x^{μ},  x^{10} ↦ x^{ρ},  x^{11} ↦ x^{ρ},  (54)

and

x^{00} ↦ x^{λ},  x^{01} ↦ x^{λ},  x^{10} ↦ x^{μ},  x^{11} ↦ x^{ρ}.  (55)

respectively. Note that the only generators of (P′_{2})_{base} on which these two maps agree are x_{00} and x_{11}. Now the object of Binar freely generated by any set X of idempotent elements has a normal form, consisting of all expressions in these generators with no subexpression which can be simplified by the idempotence relations, i.e., no β(x, x) with x ∈ X. Comparing normal forms in the domains and codomains of the above two maps, it is not hard to verify that their equalizer will be the subcoalgebra of (P′_{2})_{base} generated by x_{00} and x_{11}. (Perhaps the easiest way to see this is to regard members of P′_{2}, as in the preceding section, as {00, 01, 10, 11}-valued functions on the Cantor set, and (54), (55) as determining maps from these to {λ, μ, ρ}-valued functions on that set.) Hence (P_{2})_{base} is the subalgebra ⟨x_{00}, x_{11}⟩ of (P′_{2})_{base}.

Instances of coassociativity at higher levels similarly give the condition that for any generator x_{i_{0}...i_{k}} occurring in the expression for any element of (P_{k})_{base}, successive indices i_{j}, i_{j+1} must be equal, so (P′_{j})_{base} is just ⟨x_{0...0}, x_{1...1}⟩. The limit object is therefore ⟨x_{0^{∞}}, x_{1^{∞}}⟩; its co-operation takes x_{0^{∞}} to its own image under the first coprojection, and x_{1^{∞}} to its own image under the second coprojection. The corresponding initial object of Rep(Binar, Semigp) can be described as taking each binar, A, to the set of pairs {(a, b) ∈ |A| × |A| | a^{2}=a, b^{2}=b}, with operation (a, b) · (c, d) = (a, d). (Like the construction of the initial semigroup-valued representable functor on Set, this is a “rectangular band” construction.)

What if we modify the task of the preceding section in the opposite way, and seek to describe the final object of Coalg(Semigp, Binar), equivalently, the initial representable functor Semigp → Binar ?

Since our new “C”, Semigp, like Binar, satisfies (44), while “D” is again Binar, we can again say that the representing object will have for underlying algebra the inverse limit of the chain of idempotent-generated objects (in this case, semigroups) written as in (50) and (51). In the preceding section, we used the “rigidity” of the normal form in Binar to identify elements of that inverse limit with certain functions on the Cantor set. No such model is evident when the base-category is Semigp. An element of (P_{1})_{base} can be represented by a finite alternating string of 0’s and 1’s; an element of (P_{2})_{base} mapping to such an element is obtained by replacing each of the 0’s with a finite alternating string of 00’s and 01’s, and each of the 1’s with a finite alternating string of 10’s and 11’s; and so on. But I don’t see any “geometric” description of the inverse limit of these semigroups.

Nevertheless, the description of each P_{k} (k ∈ ω) as a semigroup freely generated by certain idempotents will prove useful in the next section, where we will construct the subprecoalgebra of this P that yields the final object of Coalg(Semigp, Semigp).

11. The final object of Coalg(Semigp, Semigp).

In our construction of the final object of Coalg(Binar, Semigp) above, the pseudocoalgebras P_{j} stabilized quickly: P_{1} already made all the distinctions that were going to be made among elements of sets (P_{j})_{base}, and once these propagated up to the pseudocopower object at the next stage, we could have verified that P_{2} was a genuine coalgebra, and was our desired final object.

In constructing the final object of Coalg(Semigp, Semigp), our structure will also stabilize early: All the distinctions among elements of that coalgebra will be present in (P_{2})_{base}; when we reach (P_{3})_{base} the process of eliminating elements at which the associative identity is not cosatisfied will stabilize, and at the next step, the pseudocopower object (P_{4})_{β} will catch up, making P_{4} the desired coalgebra.

Let us, in this section, write P′ for the ω-indexed Binar-precoalgebra in Semigp referred to at the end of the last section, built up universally on the trivial pseudocoalgebra P′_{0}; thus the inverse system of semigroups (P′_{k})_{base} is given by (50) and (51), with “ ∐ ” interpreted as coproduct of semigroups. By Proposition 7.7(iv), the precoalgebra we want is the largest subprecoalgebra of P′ cosatisfying the associative identity.

As before, the first instance of that identity occurs in P′_{2}. The elements of (P′_{2})_{base} at which that identity is cosatisfied are those at which the two homomorphisms into the semigroup freely generated by three idempotent elements x_{λ}, x_{μ}, x_{ρ} given by (54) and (55) agree. However, because semigroups have a less rigid structure than binars, the equalizer of those two homomorphisms is larger than the subsemigroup generated by the two elements of {x_{00}, x_{01}, x_{10}, x_{11}} on which they agree. For instance, it is easy to verify that it contains the product x_{00}x_{01}x_{10}x_{11}; namely, that both maps send this to x_{λ}x_{μ}x_{ρ}.

It would be convenient for the computations to come if we could say that the common image of an element of (P_{2})_{base} under the homomorphisms (54) and (55) was also their image under the homomorphism

x^{00} ↦ x^{λ},  x^{01} ↦ x^{μ},  x^{10} ↦ x^{μ},  x^{11} ↦ x^{ρ}.  (56)

However, this is not true. The simplest counterexample I know is the element

(x_{00} x_{01})^{2} x_{10} x_{00} x_{01} x_{10} x_{11} x_{01} (x_{10} x_{11})^{2}.  (57)

The reader can verify that (54) and (55) both send this to

(x_{λ} x_{μ})^{2} x_{ρ} x_{λ} (x_{μ} x_{ρ})^{2},

so that it belongs to (P_{2})_{base}, but that (56) sends it to the different value

(x_{λ} x_{μ})^{2} x_{λ} x_{μ} x_{ρ} (x_{μ} x_{ρ})^{2}.

However, the next result shows that (56) does agree with (54) and (55) on the image of (p_{2,3})_{base} : (P_{3})_{base} → (P_{2})_{base}; indeed, that this is true for the corresponding precosemigroup in any variety C of algebras.

11.1. Lemma. Let C be a variety of algebras, and P the precoalgebra arising in the construction of the final object of Coalg(C, Semigp). Then the homomorphism determined by (56), from (P′_{2})_{base} to the algebra freely generated by three idempotents x_{λ}, x_{μ}, x_{ρ}, agrees on the subalgebra (p_{3,2})_{base}((P_{3})_{base}) ⊆ (P_{2})_{base} with the common value of the homomorphisms determined by (54) and (55).

Proof. Since the map (p_{3,2})_{base} takes each generator x_{ijk} of (P′_{3})_{base} to x_{ij} in (P′_{2})_{base}, what we wish to show is that the composites of that map with (54) and (55), namely the maps given on our idempotent generators by

x_{00k} ↦ x_{λ},  x_{01k} ↦ x_{μ},  x_{10k} ↦ x_{ρ},  x_{11k} ↦ x_{ρ},  and  (58)

x^{00k} ↦ x^{λ},  x^{01k} ↦ x^{λ},  x^{10k} ↦ x^{μ},  x^{11k} ↦ x^{ρ}  (59)

(which by what we already know agree on (P_{3})_{base} with each other), also agree on (P_{3})_{base} with the composite of (p_{2,3})_{base} with (56), namely, the map given on generators by

x^{00k} ↦ x^{λ},  x^{01k} ↦ x^{μ},  x^{10k} ↦ x^{μ},  x^{11k} ↦ x^{ρ}.  (60)

The equality of the maps (58) and (59) is the (3, 0)-instance of the associative identity in P; a stronger condition is the (3, 1)-instance of that identity. This involves the corresponding maps into the coproduct of three copies of (P′_{1})_{base}. That coproduct is freely generated by six idempotents: “λ”, “μ” and “ρ” copies of the two idempotent generators x_{0} and x_{1} of (P′_{1})_{base}. Let us write these x_{λ0}, x_{λ1}, x_{μ0}, x_{μ1}, x_{ρ0}, x_{ρ1}. Then the (3, 1)-instance of the associative law says that the maps defined on (P′_{3})_{base} by

x_{00k} ↦ x_{λk},  x_{01k} ↦ x_{μk},  x_{10k} ↦ x_{ρ0},  x_{11k} ↦ x_{ρ1},  and  (61)
x^{00k} ↦ x^{λ0},  x^{01k} ↦ x^{λ1},  x^{10k} ↦ x^{μk},  x^{11k} ↦ x^{ρk}  (62)

agree on (P_{3})_{base}. Note the loss of the subscript k in the last two terms of (61) and the first two terms of (62). This happens because, in the definition of cosatisfaction of the associativity identity β(β(−, −), −) = β(−, β(−, −)), the second argument of the outer β on the left, and the first argument of the outer β on the right, in order to be comparable with the other arguments, have to be carried down from (P′_{2})_{base} to (P′_{1})_{base} by (p_{1,2})_{base}, which acts by lopping off the last subscript.

Now elements of (P_{3})_{base} are restricted not only by the cosatisfaction of associativity on that object, but by the fact that they lie in the subalgebra generated by the images of (P_{2})_{base} in (P′_{2})_{β} = (P′_{3})_{base}, under the two coprojection maps x_{ij} ↦ x_{0ij} and x_{ij} ↦ x_{1ij}, and that the elements of that subalgebra (P_{2})_{base} themselves cosatisfy the associative identity. To see how to use this fact, let us look at (61) as defining a homomorphism on (P′_{3})_{base} = (P′_{2})_{base} ∐ (P′_{2})_{base}, and note that it carries the first copy of (P′_{2})_{base} isomorphically to the subalgebra of (P′_{1})_{base} ∐ (P′_{1})_{base} ∐ (P′_{1})_{base} generated by the four idempotent elements x_{λk} and x_{μk}, merely relabeling the generators by replacing initial subscriptstrings 00 and 01 by λ and μ respectively; while it acts in a non-one-one way on the second copy; and that the codomain of (61) is the coproduct of the images of those two copies. Restricting attention to the action of (61) on the subalgebra (P_{3})_{base} ⊆ (P′_{3})_{base}, let us write down the fact that the elements that come from the first copy of (P′_{2})_{base} (i.e., expressions where all subscripts begin with “0”) are images under x_{ij} ↦ x_{0ij} of elements cosatisfying the associative law; this may be expressed as the equality, on that image, of the maps obtained from (54) and (55) by prefixing a “0” to all subscripts. Taking into account the relabeling, referred to above, of that copy of (P′_{2})_{base} via the first two arrows of (61), and noting that we are not making any changes in the image of the second copy of (P′_{2})_{base}, this says that on the image of (P_{3})_{base} under (61), the homomorphisms into the C-algebra freely generated by idempotent elements x_{0λ}, x_{0μ}, x_{0ρ}, x_{ρ0}, x_{ρ1} given by

x_{λ0} ↦ x_{0λ},  x_{λ1} ↦ x_{0μ},  x_{μk} ↦ x_{0ρ},  x_{ρk} ↦ x_{ρk},  and  (63)

x^{λk} ↦ x^{0λ},  x^{μ0} ↦ x^{0μ},  x^{μ1} ↦ x^{0ρ},  x^{ρk} ↦ x^{ρk}  (64)

agree.

Let us now collapse the codomain ⟨x_{0λ}, x_{0μ}, x_{0ρ}, x_{ρ0}, x_{ρ1}⟩ of (63) and (64) onto the algebra ⟨x_{λ}, x_{μ}, x_{ρ}⟩ freely generated by three idempotent elements, by the homomorphism sending x_{0λ} to x_{λ}, x_{0μ} and x_{0ρ} both to x_{μ}, and x_{ρ0} and x_{ρ1} both to x_{ρ}. Then (63) and (64) yield maps

x_{λ0} ↦ x_{λ},  x_{λ1} ↦ x_{μ},  x_{μk} ↦ x_{μ},  x_{ρk} ↦ x_{ρ}  and  (65)
x^{λk} ↦ x^{λ},  x^{μk} ↦ x^{μ},  x^{ρk} ↦ x^{ρ},  (66)

which still agree on the image of (P_{3})_{base} under (61). But on (P_{3})_{base}, (61) agrees with (62), so we will get the same results by following (61) with (66), and by following (62) with (65), namely

x_{00k} ↦ x_{λ},  x_{01k} ↦ x_{μ},  x_{10k} ↦ x_{ρ},  x_{11k} ↦ x_{ρ},  and
x_{00k} ↦ x_{λ},  x_{01k} ↦ x_{μ},  x_{10k} ↦ x_{μ},  x_{11k} ↦ x_{ρ}.

These are precisely (58) and (60), completing the proof of the lemma.

Remarks. The above result presumably has something to do with the identity

(ab)(cd) = a(bc)d

in Semigp, where the right-hand side means the common value of (a(bc))d and a((bc)d). But while that relation is trivial to derive, I was only able to find the proof of the above lemma by “enlightened trial and error”. Some illuminating way of looking at such computations is clearly desirable.

The proof of the lemma did not use the assumption that the x_{ijk} were idempotent, so one really should prove it in a wider context. But I did not want to complicate further the already messy proof.

We now return to the case C = Semigp. The above lemma motivates

11.2. Definition. |R| ⊆ (P′_{2})_{base} will denote the subsemigroup of elements at which the maps (54), (55) and (56) all agree.

In the remainder of this section, we shall obtain a precise description of |R|, and show that the precosemigroup structure on P induces a structure of cosemigroup on |R|, and that the resulting cosemigroup R is the final cosemigroup we are seeking. We will then examine the functor Semigp → Semigp that it represents.

The reader who intends to follow the calculations of the next few pages in detail would do well to copy onto a slip of paper displays (54), (55) and (56) (perhaps in abbreviated form, e.g., showing only the subscripts), or memorize them with their display-numbers, since we will refer to them repeatedly. (Also, if at some point the reader feels the need for examples of elements of |R| to help in thinking about the assertions we will be proving, he or she can look ahead at (68), (71), and the paragraph preceding Lemma 11.4.)

11.3. Lemma. Let r be an element of |R|, written in the normal form for (P′_{2})_{base}, i.e., as a word in x_{00}, x_{01}, x_{10}, x_{11} with none of these generators occurring twice in succession. Then

(i) The expression for r begins with an x_{00} or x_{11}, and ends with an x_{00} or x_{11}.

(ii) In the expression for r, there are no occurrences of x_{00} adjacent to x_{10} in either order, nor of x_{11} adjacent to x_{01} in either order.

(iii) If r has two occurrences of x_{00} with no x_{00} or x_{11} between them, then what occurs between them is precisely the length-1 string x_{01}. Likewise, if r has two occurrences of x_{11} with no x_{00} or x_{11} between them, then what occurs between them is precisely x_{10}.

(iv) If r has the form s x_{00} x_{11} t for some possibly empty strings s and t, then the factors s x_{00} and x_{11} t also belong to |R|. Likewise, if r has the form s x_{11} x_{00} t, then s x_{11} and x_{00} t belong to |R|.

(v) If r has length > 1, then its expression includes occurrences of both x_{00} and x_{11}.

Proof. (i): If r began with x_{01}, then its image under (55) would begin with x_{λ}, while its image under (54) would begin with x_{μ}, a contradiction. The same reasoning applies with “end” in place of “begin”, and the analogous computation excludes elements that begin or end with x_{10}.

To get the remaining assertions, let us first note that when either (54) or (56) is applied to r, only the generator x_{00} is mapped to x_{λ}; hence for any i, the i-th occurrence of x_{00} in r (if such exists) yields the i-th occurrence of x_{λ} in the image element; hence the initial string of r up to (respectively, through) the i-th occurrence of x_{00} is mapped by both (54) and (56) to the initial string of the image of r up to (respectively, through) the i-th occurrence of x_{λ}; and the same holds for the terminal strings following (respectively beginning with) the i-th occurrences of x_{00} and x_{λ}. These conclusions are not true of the images of these substrings under (55); rather, if we write “(55) and (56)” in place of “(54) and (56)”, we get the analogous results with x_{11} and x_{ρ} in place of x_{00} and x_{λ}.

To see (ii) now, simply observe that if the i-th occurrence of x_{00} in r were immediately preceded by x_{10}, then in the image of r under (54), the i-th occurrence of x_{λ} would be immediately preceded by x_{ρ}, while in the image under (56) it would be immediately preceded by x_{μ}, a contradiction. The statement for x_{10} immediately following x_{00}, and the corresponding statements for x_{11} and x_{01}, are seen in the same way.

To see (iii), suppose that the i-th and i+1st occurrences of x_{00} have no x_{11} between them. Since they cannot be adjacent (our expression for r being in normal form), they have a nonempty string of x_{01}’s and x_{10}’s between them. Hence in the image of r under (56), the i-th and i+1st occurrences of x_{λ} have precisely an x_{μ} between them; but the only way we can get this in the image under (54) is if they have only a single x_{01} between them. Again, the second statement is proved in the same way.

To get (iv), suppose the i-th occurrence of x_{00} in r is immediately followed by the j-th occurrence of x_{11}, and we factor r at this point, writing r = s x_{00} x_{11} t. Applying (56), we see that the i-th occurrence of x_{λ} in the image element is immediately followed by the j-th occurrence of x_{ρ}, giving a factorization of that image as u = v x_{λ} x_{ρ} w. Here v x_{λ}, the image of s x_{00} under (56), is both the initial string of u through the i-th occurrence of x_{λ}, and the initial string up to (but not including) the j-th occurrence of x_{ρ}. By our earlier observations, the former characterization also makes this element the image of s x_{00} under (54), while the latter makes it the image of s x_{00} under (55). Hence those three images of s x_{00} are equal; so s x_{00} ∈ |R|. The statement that x_{11} t ∈ |R| is obtained in the same way, as are the corresponding results when x_{00} follows x_{11}.

To show (v), suppose first that r does not contain x_{11}. Then (i) and (iii) imply that has the form x_{00}(x_{01}x_{00})^{i} for some i ≥ 0. The images of this element under (54) and (55) are x_{λ}(x_{μ}x_{λ})^{i} and x_{λ} respectively, so i = 0, showing that r has length 1. We get the same conclusion if r does not contain x_{00}, completing the proof of (v).

Let us now use the above tools to dig our way into the structure of an element r ∈ |R|. By (i) above, such an element must begin with x_{00} or x_{11}. Assume the former without loss of generality. That may be all of r, for it is easy to see that x_{00} ∈ |R|. If it is not all of r, then by (ii), the following factor must be x_{11} or x_{01}. In the former case, writing r = x_{00} x_{11} t, we know by (iv) that each of the factors x_{00} and x_{11} t, lies in |R|, and we are reduced to studying elements with shorter expressions. So suppose the second factor is x_{01}. This may be followed either by another x_{00} or by an x_{10}. In the former case, this new x_{00} must again be followed by x_{01}. (It can’t be terminal by (v), and it can’t be followed by x_{11}, because if it were, then by (iv) the product of the terms up to that point, x_{00} x_{01} x_{00}, would belong to |R|, again contradicting (v).) Repeating these considerations, we see that r will begin with some string (x_{00} x_{01})^{i+1} (i ∈ ω), followed by an x_{10}.

This x_{10} cannot terminate r by (i), so it must be followed by x_{11} or x_{01}. If we get x_{01}, then the next term can only be another x_{10}; the apparent alternative x_{00} is ruled out by the fact that such an x_{00} and the preceding x_{00} would have x_{01} x_{10} x_{01} between them, contradicting (iii). Repeating this argument, we get a (possibly empty) string of alternating x_{10}’s and x_{01}’s, finally followed by x_{10} x_{11}; i.e., r begins

(x_{00} x_{01})^{i+1}(x_{10} x_{01})^{j}(x_{10} x_{11}) (i, j ∈ ω).

(Note that if j = 0, the “(x_{10} x_{01})^{j}” in this expression is not a semigroup element, but merely means that nothing is inserted between the (x_{00} x_{01})^{i+1} and the (x_{10} x_{11}). This interpretation of possibly zero exponents will be in effect throughout this section.)

If the above x_{11} is not the final term of r, then it must be followed either by x_{00} (in which case we can again reduce to the study of two shorter elements of |R| using (iv)), or by another x_{10}. Let us collect as large a power of x_{10} x_{11} as we can, and note what the next two factors, if any, can be; we conclude that if the element we have been considering cannot be factored at an x_{00} - x_{11} interface, then it must have the form

r = (x_{00} x_{01})^{i+1}(x_{10} x_{01})^{j}(x_{10} x_{11})^{k+1} s, where i, j, k ∈ ω, and s is either the empty string, or begins with x_{10} x_{01}.

(67)

Let us now apply (54) and (55) to this description (67) of r.

The image of (67) under (54) begins with (x_{λ} x_{μ})^{i+1}(x_{ρ} x_{μ})^{j} x_{ρ} (where, in evaluating the image of (x_{10} x_{11})^{k+1}, we have used the idempotence of x_{ρ}), and the last clause of (67) shows that if this is not the whole of that image, it is followed by another x_{μ}.

On the other hand, the image of (67) under (55) begins x_{λ} (x_{μ} x_{λ})^{j}(x_{μ} x_{ρ})^{k+1} (where in evaluating the first part, we use the idempotence of x_{λ}), possibly followed by a string beginning x_{μ} x_{λ}.

Equating the powers of x_{λ} x_{μ} with which these images begin, we see that j = i. If we then compare the number of terms x_{ρ} occurring before each image either ends or shows another x_{λ}, we see that this is at least j +1 in the first case and exactly k+1 in the second, so k ≥ j = i; so the term (x_{10} x_{11})^{k+1} of (67) has a left factor (x_{10} x_{11})^{i+1}. We conclude that r begins with a factor to which we give the name

p_{i} = (x_{00} x_{01})^{i+1}(x_{10} x_{01})^{i}(x_{10} x_{11})^{i+1} (i ∈ ω).  (68)

We remark that if we write the final factor x_{01} of the initial string (x_{00} x_{01})^{i+1} in (68) twice (as we may since all our generators are idempotent), and likewise the initial factor x_{10} of the terminal string (x_{10} x_{11})^{i+1}, and combine these with the middle string, then the expression assumes the non-reduced, but somewhat more elegant form

(x_{00} x_{01})^{i+1}(x_{01} x_{10})^{i+1}(x_{10} x_{11})^{i+1}.  (69)

It is straightforward to verify that the element p_{i} described by (68), equivalently, (69), lies in |R| : its image under each of (54), (55) and (56) is

(x_{λ} x_{μ})^{i+1} (x_{μ} x_{ρ})^{i+1}  (70)

(where again, for elegance, I am using a non-reduced expression, with the middle occurrence of x_{μ} repeated).

What about the remaining factor of r, if any? If it is nonempty, let us write r = p_{i} s and apply (54), (55) and (56), calling the images of s under these three maps s_{1}, s_{2} and s_{3}, respectively. Then the fact that p_{i} s ∈ |R| tells us that

(x_{λ} x_{μ})^{i+1} (x_{μ} x_{ρ})^{i+1} s_{1} = (x_{λ} x_{μ})^{i+1} (x_{μ} x_{ρ})^{i+1} s_{2} = (x_{λ} x_{μ})^{i+1} (x_{μ} x_{ρ})^{i+1} s_{3}.

This does not imply that s_{1} = s_{2} = s_{3}, since the idempotent x_{ρ} to the left of these three elements may mask distinctions between them. But it clearly implies that x_{ρ} s_{1} = x_{ρ} s_{2} = x_{ρ} s_{3}, hence that x_{11} s ∈ |R|. Thus, if we write r as p_{i} · x_{11} s, using the fact that p_{i} ends with the idempotent element x_{11}, then the factors p_{i} and x_{11} s lie in |R|, and we can apply the same considerations to the second of these, which is shorter than r.

We assumed above that r began with x_{00}. If instead it begins with x_{11}, then the nontrivial case is when this is followed by something other than x_{00}, and in that case, by symmetry (interchanging subscripts 0 and 1, subscripts λ and ρ, and applications of (54) and (55) throughout the preceding argument), we get an initial string which we name

q_{i} = (x_{11} x_{10})^{i+1}(x_{01} x_{10})^{i}(x_{01} x_{00})^{i+1} (i ∈ ω),  (71)

which likewise belongs to |R|, and, if it is not the whole of r, can be split off so as to leave a shorter factor in |R|.

We conclude that |R| is generated by the elements x_{00}, x_{11}, p_{i} and q_{i} (i ∈ ω). It is easy to check the relations these satisfy in (P′_{2})_{base}, and deduce

11.4. Lemma. The semigroup |R| has the presentation

⟨x_{00}, x_{11}, p_{i}, q_{i} (i∈ω) | x_{00}^{2}=x_{00}, x_{11}^{2}=x_{11}, x_{00} p_{i}=p_{i}=p_{i} x_{11}, x_{11}q_{i}=q_{i}=q_{i} x_{00}⟩. (72)

It has a normal form consisting of all strings in the indicated generators which contain no substrings x_{00}^{2}, x_{11}^{2}, x_{00} p_{i}, p_{i} x_{11}, x_{11} q_{i} or q_{i} x_{00}.

Our next task is to find a natural co-operation on |R|. We know that every object S of Coalg(Semigp, Semigp) has a unique family of pseudocoalgebra maps S → P_{k} ⊆ P′_{k} (k ∈ ω) making commuting triangles with the connecting maps p_{j,j+1}, and that for every such S, the map |S| → (P′_{2})_{base} lands in our subsemigroup |R|. We shall now show that every r ∈ |R| lifts under (p_{2,3})_{base} to a unique r′ ∈ |(P′_{3})_{base}| which has a chance of being in the image of the map |S| → (P′_{3})_{base} for such an S. We will find that this yields an isomorphism φ of |R| with a subsemigroup |R|′ ⊆ (P′_{3})_{base}; thus, φ composed with the pseudo-co-operation of P′_{3} gives a co-operation β^{R} : |R| → |R| ∐ |R|. We will verify that β^{R} cosatisfies the associative identity, and deduce that the resulting coalgebra R = (|R|, β^{R}) is in fact the final object of Coalg(Semigp, Semigp).

So let r be any element of |R|. By the description of the map (p_{2,3})_{base} : (P′_{3})_{base} → (P′_{2})_{base}, the general element r′ of (P′_{3})_{base} that maps to r is obtained from r by replacing each term x_{ij} (i, j ∈ {0, 1}) by a nonempty (possibly length-1) alternating string of factors x_{ij0} and x_{ij1}. Moreover, since any element of (P′_{2})_{base} that lies in the image of a cosemigroup S belongs to |R|, any element r′ of (P′_{3})_{base} in the image of a cosemigroup must have the property that the pseudo-co-operation of P′_{3} carries it into the subsemigroup |R| ∐ |R| ⊆ (P′_{2})_{base} ∐ (P′_{2})_{base} = (P′_{3})_{β}. Explicitly, this means that if we break r′ up as a product of substrings formed from generators x_{0jk} alternating with substrings formed from generators x_{1jk}, each such substring is formed from an element of |R| by prefixing the index 0, respectively 1, to all subscripts.

Consider now the case where the expression for r begins with the string p_{i}, for some i ∈ ω. In particular, its initial substring consisting of generators with first subscript 0 is exactly (x_{00} x_{01})^{i+1}. Hence for any r′ ∈ (P′_{3})_{base} that maps to r, the initial substring of r′ consisting of generators with first subscript 0 is the result of prefixing 0 to the subscript of each factor in an element u of |R| which, when broken up into words in x_{00} and x_{01}, alternating with words in x_{10} and x_{11}, yields i+1 of each sort, beginning with one of the former sort.

Assuming that r′ lies in the image of a cosemigroup, the associative identity must be cosatisfied at r′, hence the results of applying (61) and (62) to r′ will agree. (The reader might copy those two displays onto a slip of paper for use in reading the next few paragraphs – that will be the last such slip of paper needed.) Now when we apply (62), each string of factors x_{000} and x_{001} collapses to one term x_{λ0} and each string of factors x_{010} and x_{011} collapses to x_{λ1}, so the image of r′ under that map begins with (x_{λ0} x_{λ1})^{i+1}, followed by a term with a different subscript. But for the image of r′ under the other map, (61), to have this form, we see that r′ must begin with precisely (x_{000} x_{001})^{i+1}, followed by a term with a different subscript. Hence the element of |R| to whose subscripts we prefix a 0 to get the initial substring of r′ must begin with (x_{00} x_{01})^{i+1} but no higher power of x_{00} x_{01}. From our study of elements of |R|, we can therefore say that this element begins with p_{i}.

This says that r′ must begin

(x_{000} x_{001})^{i+1}(x_{010} x_{001})^{i}(x_{010} x_{011})^{i+1},  (73)

and applying (61) and (62) to this in turn, we get, from the former, (x_{λ0} x_{λ1})^{i+1}(x_{μ0} x_{λ1})^{i} (x_{μ0} x_{μ1})^{i+1}, but from the latter (after collapsing repeated factors), simply (x_{λ0} x_{λ1})^{i+1}. Thus, on applying (62), the terms immediately after (73) in r′ must yield (x_{μ0} x_{λ1})^{i} (x_{μ0} x_{μ1})^{i+1}. Noting how (62) acts, we conclude that those terms begin with an i-fold alternation of single terms x_{100} with alternating products of x_{010} and x_{011}, followed at the end by (x_{100} x_{101})^{i+1}. (A priori, there might also be an initial alternating product of x_{010} and x_{011} before the first term x_{100}, whose image after applying (62) would be absorbed by the preceding x_{λ1}. But this would mean that the element of |R| to whose subscripts one prefixes 0 to get the initial terms of r′ would consist of p_{i} followed by further terms x_{10} and x_{11}, and by our description of |R|, this is impossible.)

Now each of the alternating products of x_{010} and x_{011} mentioned in the preceding paragraph must be the image of an element s ∈ |R| under prefixing 0 to all subscripts; so each such s must consist only of factors x_{10} and x_{11}, so by Lemma 11.3(v), s = x_{11}. So the additional terms we have found on our element r′ are (x_{100} x_{011})^{i}(x_{100} x_{101})^{i+1}.

Another cycle of the same sort (which the reader is invited to work out) adds on a factor (x_{110} x_{101})^{i} x_{110}. (Just as the loss of the subscript k at the left-hand side of (62) started this process moving, by causing the images of (73) under these two maps to have unequal lengths, so the loss of that subscript at the right-hand side of (61) slows it down at this point, so that we add only i+1 terms rather than 2i+1 as before.) Still another cycle tacks on a factor (x_{111} x_{110})^{i} x_{111}, and there the process stops: the expression so obtained,

{p′_{i} = \atop (x_{000}x_{001})^{i+1}(x_{010}x_{001})^{i}(x_{010}x_{011})^{i+1}(x_{100}x_{011})^{i}(x_{100}x_{101})^{i+1}(x_{110}x_{101})^{i}(x_{110}x_{111})^{i+1},} (74)

has the same images under (61) and (62); moreover, it maps precisely to p_{i} under (p_{3,2})_{base}.

(We remark, in passing, that, paralleling (69), we can rewrite (74) as

{p′_{i} = \atop (x_{000}x_{001})^{i+1}(x_{001}x_{010})^{i+1}(x_{010}x_{011})^{i+1}(x_{011}x_{100})^{i+1}(x_{100}x_{101})^{i+1}(x_{101}x_{110})^{i+1}(x_{110}x_{111})^{i+1}} (75)

showing that our precosemigroup has somewhere learned how to count from 0 to 7 in base 2).

Thus, if r = p_{i} s, then we can write r′ = p′_{i} s′ for p′_{i} as in (74), and some s′. As noted earlier, s may or may not belong to |R|; similarly, s′ may or may not inherit the properties that (61) and (62) agree on it and that β^{P′_{3}} carries it into |R| ∐ |R|; but if we repeat the idempotent generator x_{11} at the right end of p_{i}, and the x_{111} at the right end of p′_{i}, and attach the extra copies to s and s′ respectively, we get factorizations r = p_{i} · x_{11}s and r′ = p′_{i} · x_{111}s′, for which it is immediate to verify that both factors inherit these properties, and that (p_{2,3})_{base} carries the latter factorization to the former.

By symmetry, what we have proved for p_{i} and p′_{i} likewise holds for q_{i} and the element

{q′_{i} = \atop (x_{111}x_{110})^{i+1}(x_{101}x_{110})^{i}(x_{101}x_{100})^{i+1}(x_{011}x_{100})^{i}(x_{011}x_{010})^{i+1}(x_{001}x_{010})^{i}(x_{001}x_{000})^{i+1}} (76)

(for which

{q′_{i} = \atop (x_{111}x_{110})^{i+1}(x_{110}x_{101})^{i+1}(x_{101}x_{100})^{i+1}(x_{100}x_{011})^{i+1}(x_{011}x_{010})^{i+1}(x_{010}x_{001})^{i+1}(x_{001}x_{000})^{i+1}} (77)

is again a variant form). The reader can quickly verify the easier cases we have passed over: that if the expression for r as in Lemma 11.4 begins, not with a p_{i} or a q_{i}, but with x_{00} or x_{11}, then r′ will begin with x_{000} or x_{111}, and that if these are not all of r and r′, we can peel them off so as to leave shorter elements still having the properties in question.

Complementing the hard work above with some easier calculations, we get

11.5. Lemma. For each r ∈ ||R|| there exists a unique element φ(r) ∈ |(P′_{3})_{base}| satisfying the following three conditions:

(i) (p_{2,3})_{base}(φ(r)) = r.

(ii) The homomorphisms (61) and (62) agree on φ(r).

(iii) β_{3}^{P} (φ(r)) ∈ |R| ∐ |R|.

The resulting map φ : |R| → (P′_{3})_{base} is an embedding of semigroups, and sends the generators x_{00}, x_{11}, p_{i}, q_{i} of |R| respectively to the elements x_{000}, x_{111}, p′_{i}, q′_{i} of (P′_{3})_{base}.

Proof. It is clear that x_{000}, x_{111}, p′_{i}, q′_{i} satisfy the relations among x_{00}, x_{11}, p_{i}, q_{i} comprising the presentation (72) of |R|, so mapping the latter to the former, we get a homomorphism φ : |R| → (P′_{3})_{base}.

Our preceding discussion shows that φ(r) is the only element of (P′_{3})_{base} that can satisfy (i), (ii) and (iii), and that it does satisfy (i) and (ii). To verify (iii), we take the image under φ of each of our generators of |R|, break it into strings of generators whose subscripts begin with 0 alternating with strings whose subscripts begin with 1, and look at the former as images of elements of P′_{2} under q_{2,0}^{(P′_{2})_{base}}, and the latter as images of elements of the same semigroup under q_{2,1}^{(P′_{2})_{base}}. Abbreviating q_{2,i}^{(P′_{2})_{base}}(u) to u^{(i)} to avoid long expressions (and confusion with our elements q_{i}), we find that

\begin{matrix}β^{P′_{3}}(x_{000}) = x_{00}^{(0)}, & β^{P′_{3}}(x_{111}) = x_{11}^{(1)}, \\ β^{P′_{3}}(p′_{i}) = p_{i}^{(0)}(x_{00}^{(1)} x_{11}^{(0)})^{i} p_{i}^{(1)}, & β^{P′_{3}}(q′_{i}) = q_{i}^{(1)}(x_{11}^{(0)} x_{00}^{(1)})^{i} q_{i}^{(0)}. \end{matrix}

Clearly the terms from (P′_{2})_{base} to which ^{(0)} and ^{(1)} are above applied are members of |R|.

This makes β^{P′_{3}} ∘ φ a co-operation β^{R} : |R| → |R| ∐ |R|; explicitly

\begin{matrix}β^{R}(x_{00}) = x_{00}^{(0)}, & β^{R}(x_{11}) = x_{11}^{(1)}, \\ β^{R}(p_{i}) = p_{i}^{(0)}(x_{00}^{(1)} x_{11}^{(0)})^{i} p_{i}^{(1)}, & β^{R}(q_{i}) = q_{i}^{(1)}(x_{11}^{(0)} x_{00}^{(1)})^{i} q_{i}^{(0)}, \end{matrix}  (78)

making R = (|R|, β^{R}) a coalgebra. It is straightforward to verify that β^{R} is coassociative. For example, the reader is encouraged to check that the derived co-operations corresponding to the two sides of the associative identity, when applied to p_{i}, both yield

p_{i}^{(λ)} (x_{00}^{(μ)} x_{11}^{(λ)})^{i} p_{i}^{(μ)} (x_{00}^{(ρ)} x_{11}^{(μ)})^{i} p_{i}^{(ρ)}.  (79)

Thus, R belongs to Coalg(Semigp, Semigp). The proof that it is the final object of that category will now be quick.

Let S be any object of Coalg(Semigp, Semigp), and let the components of the unique morphism from S to the precoalgebra P be f_{k} : S → P_{k} (k ∈ ω). Since these maps respect (pseudo-)co-operations, we have, in particular,

(f_{3})_{β} _{∘} β^{S} = β^{P_{3}} _{∘} (f_{3})_{base}.  (80)

Now looking at the commuting square formed from the (pseudo)coprojections of S and of P_{3}, and invoking (32), we see that the term (f_{3})_{β} in (80) can be written as a copower, ∐_{ari(β)} (f_{2})_{base}. On the other hand, in the right-hand side of (80), we can insert φ ∘ (p_{2,3})_{base} between the two factors, since (p_{2,3})_{base} carries f_{3} of an element of |S | to f_{2} of that element, and φ, by construction, will carry the resulting element back to its only preimage in (P′_{3})_{base} that can possibly be in the image of f_{3}. When we make this insertion, the combination β^{P_{3}} ∘ φ gives, by definition, β^{R}, and (80) becomes

∐_{ari(β)} (f_{2})_{base} ^{∘} β^{S} = β^{R} ^{∘} (f_{2})_{base},  (81)

showing that (f_{2})_{base} is a morphism of coalgebras S → R.

To show that this is the only morphism of coalgebras S → R, note first that the inclusion of the subsemigroup |R| in (P_{2})_{base} induces a morphism g from the coalgebra R to the final 3-indexed precobinar (P′_{k})_{k∈3}, and that this morphism separates elements of |R|. Hence if we had two distinct morphisms S → R, then composing these with g, we would get distinct morphisms S → (P′_{k})_{k∈3}, contradicting the universal property of that 3-indexed precoalgebra (Proposition 6.5).

Thus

11.6. Theorem. The cosemigroup R with underlying semigroup (72) and co-opera-tion (78) is the final object of Coalg(Semigp, Semigp).

What does the functor represented by this coalgebra R, i.e., the initial object E of Rep(Semigp, Semigp), look like? Writing a, b, c_{i}, d_{i} for the images of x_{00}, x_{11}, p_{i} and q_{i} respectively under a semigroup homomorphism on |R|, it can be described as taking a semigroup A to the semigroup with underlying set

{|E(A)| = \{ (a; b; c_{0}, c_{1}, …; d_{0}, d_{1}, …) ∈ |A|^{1+1+ω+ω} | \atop a^{2} = a, b^{2} = b, ac_{i} = c_{i} = c_{i}b, bd_{i} = d_{i} = d_{i}a (i ∈ ω)\}}  (82)

(cf. (72)), and operation

{(a; b; …, c_{i}, …; …, d_{i}, …) (a′; b′; …, c′_{i}, …; …, d′_{i}, …) \atop = (a; b′; …, c_{i} (a′b)^{i} c′_{i}, …; …, d′_{i} (ba′)^{i} d_{i}, …)}  (83)

(cf. (78)). The formula for the c_{i} and d_{i} components of (83) is an instance of what semigroup theorists [12] call a Rees matrix semigroup construction.

As an example of the universal property of R, consider, in Coalg(Semigp, Semigp), the object S representing the identity functor. This is represented by the free semigroup on one generator y, with comultiplication given by

β^{S}(y) = y^{(0)}y^{(1)}.  (84)

When we map this into P, y is necessarily mapped to x in (P_{0})_{base}, so by (84) the image of β^{S}(y) in (P_{1})_{β} is x^{(0)}x^{(1)}; so the image of y in (P_{1})_{base} is the corresponding element, x_{0} x_{1}. (Cf. the discussion of how such maps are constructed following Proposition 6.5.) Hence, again using (84), the image of β^{S}(y), in (P_{2})_{β} is (x_{0} x_{1})^{(0)}(x_{0} x_{1})^{(1)}; so the image of y in (P_{2})_{base} is x_{00} x_{01} x_{10} x_{11}. Note that this is (x_{00} x_{01})^{1}(x_{10} x_{01})^{0} (x_{10} x_{11})^{1} = p_{0} ∈ |R|. Thus, the unique map from the cosemigroup S representing the identity functor to the final cosemigroup R is the semigroup homomorphism taking the free generator y of |S | to p_{0} ∈ |R|.

Since p_{0} corresponds to the coordinate c_{0} of (82), the corresponding morphism of representable functors from E to the identity takes the infinite tuples of (82) and ignores all coordinates except c_{0}, which it uses as its value. This mapping is not in general onto: its image is the subsemigroup of A consisting of those elements that are fixed by multiplication by at least one idempotent on the left and by at least one idempotent on the right; in particular, it is empty if A has no idempotents. This nonsurjectivity is inevitable: there are representable semigroup-valued functors F which give the empty semigroup when applied to semigroups having no idempotents, so to be an initial representable functor, and thus have homomorphisms to such F, E must also give the empty semigroup in such cases. On the other hand, since representable functors between varieties respect final objects, every representable functor F : Semigp → Semigp will, when applied to the 1-element semigroup, give a 1-element semigroup; hence F must also give nonempty semigroups on all semigroups into which the 1-element semigroup can be mapped, i.e., all semigroups that do have idempotent elements.

As easy variants of this example, the unique morphism from E to the direct product of two copies of the identity functor takes each element as in (82) to the pair (c_{0}, c_{0}); the unique morphism to the opposite-semigroup functor A ↦ A^{op} projects to the coordinate d_{0}, rather than c_{0}.

For a different sort of example, let F be the functor taking every semigroup A to its underlying set, with the left zero multiplication s · t = s. Then the unique morphism E → F will carry each infinite tuple as in (82) to its first coordinate a. Again this will in general be nonsurjective, though in this case, the image of E in F will be a representable subfunctor, taking each semigroup A to the semigroup consisting of the set of idempotent elements of |A|, with the left zero multiplication.

Though each of the above morphisms from the initial representable functor throws away almost all the information contained in (82), a morphism from E to a nontrivial representable functor F cannot throw away all such information. If it did, it would have to send all of E(A) to a single distinguished element of F (A); but a nontrivial representable functor on a variety without zeroary operations does not admit such a choice of distinguished element. From the coalgebra point of view, the corresponding observation is that the image in R of the coalgebra S representing F cannot be empty unless S is the empty coalgebra, i.e., unless F is the trivial functor.

These examples have not involved the “exotic” coordinates of (83), the c_{i} and d_{i} with i > 0. There are no representable functors that I was previously aware of whose morphisms from the initial representable functor involve those coordinates; but one can easily design such functors. Our initial functor E itself is one, of course. One can also cut it down, throwing away all the relations in (82), and all but three of the coordinates, getting the construction sending A to the set of all 3-tuples (a, b, c) of elements of |A|, with the multiplication (a, b, c)(a′, b′, c′) = (a, b′, c (a′b)^{i}c′), for arbitrary fixed i. It is easy to verify that this is associative, and that the unique morphism from E to this functor uses the coordinates a, b, and c_{i}.

More generally, if one takes any semigroup word w in m+n variables, one can define a representable functor F taking every semigroup A to the set of all m + n + 1-tuples

(a_{1}, …, a_{m}; b_{1}, …, b_{n}; c)  (85)

of elements of A, with the operation

{(a_{1}, …, a_{m}; b_{1}, …, b_{n}; c) (a′_{1}, …, a′_{m}; b′_{1}, …, b′_{n}; c′) \atop = (a_{1}, …, a_{m}; b′_{1}, …, b′_{n}; c w(a′_{1}, …, a′_{m}, b_{1}, …, b_{n}) c′),}  (86)

which it is easy to verify is associative. To describe the map from E to this functor, break the word w into alternating blocks of occurrences of the “a” variables (the first m) and the “b” variables (the last n), and count these blocks, starting from the first block of “a” variables (ignoring any “b” variables that may precede them), and ending with the last block of “b” variables (ignoring any “a” variables that may follow that block). Say these constitute i blocks of “a” variables alternating with i block “b” variables, for some i ∈ ω. (This i may be 0, namely, if w consists only of a word in the “b” variables followed by a word in the “a” variables, with one of those words possibly empty.) Then the unique morphism E → F assigns to all a_{r} the value a, to all b_{r} the value b, and to c the value c_{i}.

We remark that (86) looks more natural if we rewrite our m+n+1-tuples so as to put the coordinate c in the middle, and abbreviate a_{1}, …, a_{m} to a, b_{1}, …, b_{n} to b, and w(a′_{1}, …, a′_{m}, b_{1}, …, b_{n}) to b ∗ a′. Then (86) becomes

(a, c, b) (a′, c′, b′) = (a, c (b ∗ a′) c′, b′).  (87)

In particular, the fact that the multiplication keeps a and b′ as coordinates, while the expression between c and c′ involves, not these, but b and a′, looks reasonable in this notation, and the calculation by which one verifies associativity becomes “trivial”.

What do we learn about general representable functors between semigroups from our description of the initial such functor E? I do not have a good answer. One interesting consequence is that for any representable functor F, the unique morphism E → F yields elements of the semigroups F (A) on which any two morphisms of representable functors from F to a common functor must agree. So, for instance, any two morphisms from the underlying-set-with-left-zero-operation functor into a common representable functor G must agree on the set of idempotent elements (i.e., elements idempotent with respect to the operation of A. Under the operation of F (A), all elements are idempotent.) That this is not true of other elements can be seen by comparing the identity endomorphism of F with the endomorphism taking each element s to the element s^{2} (where the “square” is interpreted in terms of the original multiplication of A). These endomorphisms agree on idempotent elements only.

The same argument tells us that any two morphisms from the identity functor to a common representable functor must agree on all elements that are fixed on each side by multiplication by at least one idempotent. But in this case, they must agree everywhere; for the unique cosemigroup morphism from the coalgebra representing the identity functor into R, described at the end of the paragraph following (84), is one-to-one, hence it is a monomorphism, so the corresponding map of representable functors is an epimorphism. (This is not true of identity functors of all varieties. For instance, in Ab, multiplication by each integer n gives an endomorphism of the identity functor, so that functor has many distinct morphisms to itself, so the map from the initial functor to it is not epic.)

Another possible use of our description of the final object of Coalg(Semigp, Semigp) lies in the fact that elements of a general cosemigroup in Semigp may be classified according to their images under the unique morphism to R, giving a start toward the task of describing all such objects (cf. [9, Problem 21.7, p.94]). An easy case, which we leave to the reader to verify, is

11.7. Proposition. Consider objects S of Coalg(Semigp, Semigp) such that the unique homomorphism S → R carries all elements of ||S || to x_{00} ∈ ||R||.

Each such coalgebra S may be obtained by taking a semigroup B and an idempotent endomorphism ϵ : B → B, and letting

|S | = B,  (88)
β^{S} = q_{2,0}^{B} ϵ; i.e., β^{S}(b) = ϵ(b)^{(0)} (b ∈ |B |).  (89)

The corresponding representable functor carries every semigroup A to the set of homomorphisms h : B → A, under the semigroup operation

h · h′ = h ϵ.  (90)

It would be interesting to know the answer to

11.8. Question. Let S be an object of Coalg(Semigp, Semigp), and f the unique morphism in that category from S to the final object R.

Must the semigroup |S| be generated by those of its elements that are sent by f to members of the generating set {x_{00}, x_{11}, p_{i}, q_{i} (i ∈ ω)} of |R|?

If so, must |S| in fact have a presentation such that the common value in |R| of the two sides of every relation also belongs to that generating set?

Let me conclude this section by mentioning that my original investigation of the structure of the final object R of Coalg(Semigp, Semigp), though it led to the same result, Theorem 11.6 above, took a somewhat different route. I considered an arbitrary object S of Coalg(Semigp, Semigp) and an arbitrary element s ∈ ||S||, and looked at the images of s under the binary, ternary, etc., co-operations of S corresponding to multiplication of two, three, etc., elements of a semigroup. (Thus, I used coassociativity from the start, rather than thinking of S as a cobinar, and then adding the assumption that it cosatisfied the associative law.) From the image of s under the binary co-operation, I extracted a “λ, ρ-signature”, a word in the alphabet {λ, ρ}, which from our present point of view encodes the image of s in {x}^{(λ)} ∐ {x}^{(ρ)}. Its images in the 3- and 4-fold copowers similarly gave a “λ, μ, ρ-signature” and a “λ, μ_{1}, μ_{2}, ρ-signature”. Examining the relations between these signatures, I determined which strings could occur, and verified that the semigroup of λ, μ, ρ-signatures that occurred could be given the structure of our desired final cosemigroup.

That development, used in the first drafts of this note, was about as lengthy as the present one, though the formulas were a bit shorter, as suggested by comparison of (69) and (70). I eventually switched to the present development for the sake of coherence with the methods of other sections of this note. But the alternative approach might be kept in mind by anyone wishing to look further at coalgebras with coassociative co-operations.

12. Examples with > 1 derived zeroary operations.

We saw in Theorem 2.1 (last paragraph) that the only situations where the initial object of Rep(C, D) can have nontrivial nonempty algebras among its values are when C and D either both have no zeroary operations, or both have more than one derived zeroary operation. So far, we have looked at cases of the former sort.

A very elementary example of a variety with more than one derived zeroary operation is the one determined by a single primitive zeroary operation α_{0}, a single primitive unary operation α_{1}, and no identities; i.e., the variety of sets with a distinguished element, and an endomap not assumed to fix that element. (The derived zeroary operations are α_{0}, α_{1}(α_{0}), …, α_{1}^{i}(α_{0}), ….)

Taking any variety C, and the above variety as D, let P be the final D-precoalgebra in C having for P_{0} the trivial pseudocoalgebra. By Proposition 7.6(iii), (P_{1})_{base} can be identified with the direct product of the 0-fold and 1-fold copowers of (P_{0})_{base}. The 1-fold copower is just (P_{0})_{base}, the trivial algebra; hence that direct product can be identified with the 0-fold copower of (P_{0})_{base}; i.e., the initial object of C. Let us denote this by I_{C}; we know that it will be nonempty and nontrivial precisely if C has more than one derived zeroary operation.

We find that passage to each subsequent level of P brings in one more copy of I_{C}, so that (P_{k})_{base} = I_{C}^{k}. Taking the limit, we get (P_{ω})_{base} = I_{C}^{ω} , where the pseudo-co-operation α_{0}^{P_{ω}} projects I_{C}^{ω} to its component indexed by 0, while α_{1}^{P_{ω}} is the “left shift” map.

Propositions 7.2 and 7.3 tell us that if C is a finitary variety satisfying (44), then P_{ω} will be a coalgebra, the final object of Coalg(C, D). But in fact, those hypotheses on C are not needed here. Their purpose was to guarantee that ari(α)-fold copowers commuted with ω-indexed inverse limits for all α ∈ Ω_{D}, but this is automatic when all elements of Ω_{D} are zeroary or unary. (The 1-fold copower functor is the identity and commutes with everything; the 0-fold copower is the constant functor giving the initial algebra, and constant functors commute with limits over connected categories.)

Indeed, either by following the above precoalgebra approach, or by directly checking the universal property, it is not hard to verify the following general statement.

12.1. Lemma. In a category X with an initial object, let such an object be denoted I_{X}.

Suppose A is a category having small products and coproducts, and D a variety with only zeroary and unary primitive operations (with or without identities). Then Coalg(A, D) has a final object R, with underlying A-object |R| = I_{A}^{|I_{D}|}, where the (primitive or arbitrary) zeroary D-co-operations of R are given by the projections to the components indexed by the values in |I_{D}| of the corresponding zeroary operations of I_{D}, and where the (primitive or arbitrary) unary D-co-operations of R are determined (contravariantly) by the action of the corresponding unary operations of I_{D} on the index-set |I_{D}|.

For concreteness, let us return to the case where D is the variety defined by one zeroary operation, one unary operation, and no identities. Let C be an arbitrary variety with more than one derived zeroary operation, and let R be the final D-coalgebra of C, which by the above observations has underlying C-algebra I_{C}^{ω}. If I_{C} is finite or countable, then R has the cardinality of the continuum; and for many choices of C – e.g., D itself, or the variety of sets with two distinguished elements, or the variety of vector-spaces with a distinguished vector, over a countable or finite field – we find that the corresponding representable functor C(R, −) takes all nontrivial finite or countable objects of C to objects of D having cardinality 2^{ℵ_{0}^{ℵ_{0}}}.

As a curious exception, suppose C is the category of abelian groups with one distinguished element, so that I_{C} is ℤ with distinguished element 1. Then |R| is the group ℤ^{ω} of all sequences of integers, with the constant sequence (1, 1, …) as distinguished element. It is known that the only group homomorphisms ℤ^{ω} → ℤ are the finite linear combinations of the projection maps [15, Proposition 94.1]. Hence, if we apply our functor C(R, −) to ℤ, with any n ∈ |ℤ| made the distinguished element, we get a countable D-object, the set of those finite linear combinations of projection maps ℤ^{ω} → ℤ whose coefficients sum to n (with distinguished element given by n times the projection onto the 0-component, and endomap given by the right shift operator on those strings of coefficients). On the other hand, if we apply C(R, −) to ℤ/pℤ or ℚ (with any distinguished element), we find that the resulting object again has cardinality 2^{ℵ_{0}^{ℵ_{0}}}.

A very different class of cases where we can get a nice handle on the final object of a category Coalg(C, D) is when D is an arbitrary variety, and C the variety Boole of Boolean rings (commutative associative unital rings satisfying the identities 2 = 0 and x^{2} = x). The variety Boole is dual to the category Stone of Stone spaces, i.e., totally disconnected compact Hausdorff spaces, via the functor taking every Boolean ring A to its prime spectrum, equivalently, to the set Boole(A, 2) of its homomorphisms into the 2-element Boolean ring, under the function topology; the inverse functor takes each Stone space X to the set Stone(X, 2) of continuous {0, 1}-valued functions on X, made a Boolean ring under pointwise operations, equivalently, to the set of clopen subsets of X, made a Boolean ring in the usual way [16, Introduction and §II.4].

Hence, D-coalgebras in Boole correspond to D-algebra objects in Stone. These can be described as D-algebras given with totally disconnected compact Hausdorff topologies on their underlying sets, with respect to which the D-operations are continuous. The representable functor Boole → D corresponding to such a topological D-algebra X can be described as taking each Boolean ring B to the D-algebra of continuous X-valued functions on the Stone space of B. (In particular, we can recover the underlying D-algebra of X from the functor by evaluating the latter on the Boolean ring 2, corresponding to the 1-point Stone space.)

Any finite set with the discrete topology is a Stone space, so any finite D-algebra gives a D-algebra object of Stone. For some varieties D, such as those of associative (unital or nonunital) rings, semigroups, monoids, groups, and distributive lattices (and, automatically, all subvarieties of these), it is known [16, VI.2.6-9], [8] that

The topological D-algebras with Stone topologies are precisely the inverse limits of systems of finite D-algebras, with the topologies induced by the discrete topologies on those finite algebras.

(91)

When this holds, every such Stone algebra is, in particular, the inverse limit of all its finite homomorphic images; and given an arbitrary D-algebra A, the category of Stone D-algebras furnished with homomorphisms of A into them will have as initial object the inverse limit of all finite homomorphic images of A.

Now note that the category (A ↓ D) of (non-topologized) D-algebras with homomorphisms of A into them can be regarded as a variety D′, by taking any presentation ⟨X | Y ⟩_{D} for A in D, and letting D′ have, in addition to the operations and identities of D, an X-tuple of additional zeroary operations, subject to the relations Y. So the above inverse limit of finite homomorphic images of A can be regarded as the initial Stone topological D′-algebra.

For example, suppose that D = Group and ⟨X | Y ⟩_{D} is the infinite cyclic group (where we can take X a singleton and Y empty), or that D = Ring^{1} and ⟨X | Y ⟩_{D} is the initial ring (X and Y both empty). In these cases, the initial Stone D′-algebra will be the inverse limit of the finite groups or rings ℤ/nℤ. (This inverse limit, called the “profinite completion of ℤ”, is the direct product over all primes p of the groups or rings of p-adic integers.)

In this example, our Stone algebra, and hence the value of our initial representable functor at the Boolean ring 2, merely has the cardinality of the continuum, and the final coalgebra to which it corresponds is merely countable, in contrast to some of our earlier examples. This is an instance of a general phenomenon. Before formulating it, let us note that if D satisfies (91), then that property will be inherited by D′ = (A ↓ D) for any D-algebra A, and that if A is finitely generated, then if D is describable in terms of finitely many primitive operations, all of finite arity, these properties will be inherited by D′. Hence it suffices to prove the next result for such a variety D, understanding that it will then be applicable to varieties D′ = (A ↓ D) when A is a finitely generated D-algebra.

12.2. Lemma. Suppose D is a finitary variety with only finitely many primitive operations, which satisfies (91). Then the final object of Coalg(Boole, D) is at most countable; equivalently, the initial Stone D-algebra has separable topology.

Proof. From the fact that D is finitary with finitely many primitive operations, one sees that up to isomorphism, there are at most countably many finite D-algebras. Hence the initial D-algebra has at most countably many finite homomorphic images, so the initial Stone D-algebra is the inverse limit of an at most countable inverse system of finite algebras. Every continuous {0, 1}-valued function on that inverse limit is induced by such a function on one of these algebras; so the Boolean ring of all such functions is at most countable.

Sometimes our final coalgebras are even smaller than the above result requires. If one takes for D the variety of groups, and lets ⟨X | Y ⟩_{D} be an infinite group with no finite homomorphic images, such as

⟨ w, x, y, z | wxw^{−1} = x^{2}, xyx^{−1} = y^{2}, yzy^{−1} = z^{2}, zwz^{−1} = w^{2} ⟩,  (92)

(or, going outside the context of Lemma 12.2 to a non-finitely-generated example, but still using the fact that Group satisfies (91), the additive group of rational numbers), then the initial Stone D′-algebra is trivial, making the final object of Coalg(Boole, D′) the 2-element (initial) Boolean ring. In this case, the derived zeroary operations of D′ cannot be distinguished by representable functors on Boole, and we are effectively reduced to case (iii) of Theorem 2.1.

In the other direction, taking varieties D not satisfying (91), one again gets examples where the final object of Coalg(Boole, D) has continuum cardinality. For instance, if we let D be, as at the beginning of this section, the variety of sets with a single zeroary and a single binary operation, then by the discussion there, the final object of Coalg(Boole, D) will be 2^{ω}, the countable direct power of the initial object 2 = {0, 1} of Boole. The corresponding Stone D-algebra can be described as the Stone-Čech compactification of ω, with the element 0 ∈ ω as the value of the zeroary operation, and the endomap induced by n ↦ n+1 as the unary operation. Some more familiar varieties not satisfying (91) are the variety of Lie algebras over a finite field (this may be deduced from [9, Example 25.49, p.126]) and the variety of all lattices ([8, second example on p.10]).

Incidentally, one’s first impression on looking at the statement of Lemma 12.2 might be that it should surely be possible to weaken the hypothesis “finitely many operations” to “at most countably many”; but this is not so. If D is the variety of sets with an ω-tuple of zeroary operations, then (91) is inherited from the variety Set, but by Lemma 12.1, the final object of Coalg(Boole, D) again has for underlying algebra the uncountable Boolean algebra 2^{ω}.

Infinite compact Hausdorff spaces are “typically” uncountable, but not always. Can the initial Stone object of a variety D be countably infinite? I found this a hard one to answer; but here is an example. Let D be the variety of lattices (or upper semilattices, or lower semilattices) with one additional zeroary operation α_{0}, and one additional unary operation α_{1}, subject to the identities saying that α_{1} is increasing, i.e., α_{1}(x) ∧ x = x and/or α_{1}(x) ∨ x = α_{1}(x) (depending on which operations are assumed present). I leave the determination of the initial Stone topological object of D to the reader who would like a challenging exercise. (Note that one cannot assume that D satisfies (91).)

If D is a variety whose initial object is finite, then even without (91) one can see that this finite object, regarded as a finite Stone space, will be the initial Stone object of D, and so will determine the initial representable functor Boole → D. We find, in particular, that the initial representable functor Boole → Boole is the identity.

There are other dualities between varieties of algebras and structures with compact topologies; cf. [2], [11]. It would be worth seeing whether these also lead to useful results about coalgebras, equivalently, representable functors.

It would also be worth examining whether some of the properties of varieties D that allow one to prove (91) might also allow one to prove results about D-coalgebras in general varieties. In both §10 and §11 above, the associative identity trimmed uncountable cobinars P′_{ω} down to countable cosemigroups R = P_{ω}. Is this a case of a more general phenomenon? Cf. also [9, §32, first paragraph], where a statement formally resembling (91) is translated into a dual statement about “coalgebras”, though in one of the other senses of that word.

Yet another example of an initial representable functor between varieties with more than one derived zeroary operation is the one that motivated this investigation, as noted in §2: the initial object of Rep(Ring^{1}, Ring^{1}), given by S ↦ S × S^{op} [9, Corollary 25.22]. (That result is generalized a bit in [9, Exercise 31.12(vi)].)

13. Universal constructions in Coalg(Group, Group) and Coalg(Monoid, Monoid).

Since the varieties of groups and of monoids have unique derived zeroary operations (giving the identity element), Theorem 2.1 tells us that the initial representable functor from either of them to any variety, or from any variety to either of them, is trivial; equivalently, that the corresponding final coalgebras have initial algebras for underlying algebra. But other limits of coalgebras involving these varieties need not be trivial. Let us briefly examine products in Coalg(Group, Group).

Kan [17] determined the structure of all comonoid objects in Group. These all extend uniquely to cogroup structures, so we shall describe his result as determining the cogroups in Group. The functors these represent are simply the direct powers of the identity functor. If we take an arbitrary cogroup R in Group, the precise statement is that its underlying group |R| is free on the set consisting of the nonidentity elements x satisfying β^{R}(x) = x^{(0)}x^{(1)} (where β ∈ Ω_{Group} again denotes the primitive binary operation). Now a morphism R → S of cogroups must take elements of R satisfying β^{R}(x) = x^{(0)}x^{(1)} to elements of S with the same property; so it must take each member of the canonical free generating set for |R| either to a member of the corresponding generating set for |S|, or to the identity element, e. If we write Id_{Group} for the identity functor of Group, and Id_{Group}^{n} for the n-fold direct power of this functor (the functor taking each group G to G^{n} – not, of course, the n-fold composite of Id_{Group}), then this is equivalent to saying that a morphism Id_{Group}^{m} → Id_{Group}^{n} is determined by specifying, as the value to be assigned at each of the n coordinates of the codomain groups, either a specified one of the m coordinates of the domain groups, or the value e.

So, though one could phrase Kan’s result as saying that the isomorphism classes of cogroups in Group correspond to the isomorphism classes of sets, the category Coalg(Group, Group) is actually equivalent, not to Set, but to the category Set^{pt} of pointed sets, by the functor taking each coalgebra R to the set {x | β^{R}(x) = x^{(0)}x^{(1)}}, with e as basepoint.

The product of two pointed sets (X, e_{X}) and (Y, e_{Y}) is (X × Y, (e_{X}, e_{Y})). Thus, the product of the cogroups in Group represented by the free groups on m and on n generators will be free on (m + 1)(n + 1) − 1 generators (with +1 to count the basepoint e in the description of the relevant pointed sets, and −1 to discount the basepoint in the product set). In terms of representable functors, the coproduct of Id_{Group}^{m} and Id_{Group}^{n} in Rep(Group, Group) is therefore Id_{Group}^{mn+m+n}. To describe the universal maps Id_{Group}^{m} → Id_{Group}^{mn+m+n} and Id_{Group}^{n} → Id_{Group}^{mn+m+n}, note that for any such pair of maps, each coordinate of Id_{Group}^{mn+m+n} must select either some coordinate of Id_{Group}^{m} or the identity, and either some coordinate of Id_{Group}^{n} or the identity. The universal pair is such that the mn + m + n coordinates together cover all possible choices exactly once, except for the simultaneous choice of the identity for both coordinates.

It is interesting to observe that for S and S′ objects of Coalg(Group, Group) and S × S′ their product in this category, the pair of projection maps S × S′ → S and S × S′ → S′ does not in general separate elements of the underlying set ||S × S′|| of the product coalgebra. For example, let us write the underlying free group of the coalgebra representing Id_{Group} as |S | = ⟨x⟩, and the underlying free group of the product coalgebra S×S as |S×S | = ⟨g_{x,x}, g_{x,e}, g_{e,x}⟩, where the subscripts indicate where the generators are sent under the two projection maps. Since this group is free, we have g_{x,e} g_{e,x} ≠ g_{e,x} g_{x,e}; but the two sides of this inequality fall together under both projection maps to |S |.

We saw in Theorem 4.9 that for every object A of a variety C, and every variety D, there exists an object R of Coalg(C, D) with a universal C-algebra homomorphism |R| → A; a coalgebra “cofree” on A, corresponding to a representable functor “free” on an arbitrary representable set-valued functor. For C = D = Group and any group A, it is not hard to show that this universal R corresponds, under the above description of Coalg(Group, Group), to the pointed set (|A|, e_{A}), with the universal homomorphism taking the generator of the free group |R| corresponding to each a ∈ |A| to that element of A. So, for instance, if A is the free group on one generator (representing the underlying-set functor), then |R| will be a free group on countably many generators, indexed by the nonzero integers, and the corresponding representable functor will be the direct power Id_{Group}^{|ℤ|−{0}} of the identity functor. The underlying-set functor is mapped to U_{Group} ∘ Id_{Group}^{|ℤ|−{0}} by sending each element b of the underlying set of a group B to (b^{n})_{n∈|ℤ|−{0}}.

The description we have given of the category of representable functors from groups to groups goes over almost unchanged to representable functors from groups to monoids, and from monoids to groups, the only adjustment being that the identity functor on groups is replaced in the first case by the forgetful functor from groups to monoids, and in the second by the group-of-invertible-elements functor from monoids to groups. But the structure of representable functors from monoids to monoids, worked out in [9, §20] and [6, §9.5], is more complicated. (In [9], incidentally, we called monoids “semigroups with neutral element”.) Such functors F correspond not to sets, but to certain sorts of bipartite directed graphs, where vertices on one side correspond to coordinates of F (S) that are multiplied as in S, those on the other side to elements that use the opposite multiplication, and the edges of the graph represent conditions specifying certain coordinates of one sort as left or right inverses of certain coordinates of the other sort. (Here the identity element sits in the intersection of the two sets, violating the usual definition of bipartite graph. It is not connected by edges to any other elements, and could be excluded if we were only concerned with the structures of individual functors and their representing coalgebras.

But its importance, as above, comes out in the description of morphisms among these functors and coalgebras.)

For details, the reader can see [9] or [6]; but let me sketch some elementary examples. Let R be the comonoid representing the functor that takes every monoid A to the monoid A × A^{op}; let R′ represent the functor that takes every A to the submonoid of A × A^{op} consisting of pairs (a, b) with ab = e; and let R′′ represent the functor that takes every A to the still smaller submonoid consisting of pairs (a, b) with ab = e = ba. Each of these functors has an inclusion morphism into the one that precedes; hence our comonoids have maps R → R′ → R′′. These are in fact surjective; on underlying monoids they are

⟨x, y⟩ → ⟨x, y | xy = e⟩ → ⟨x, y | xy = e = yx⟩,  (93)

where the arrows carry generators to generators with the same name, and where, in each case, the comultiplication is given by

x ↦ x^{(0)}x^{(1)},  y ↦ y^{(1)}y^{(0)}.  (94)

Now by the results of [9] or [6], every object S of Coalg(Monoid, Monoid) has underlying monoid generated by {z ∈ ||S|| | β^{S}(z) = z^{(0)}z^{(1)} or z^{(1)}z^{(0)}}, hence every morphism of such objects is determined by its behavior on this set. For each of the above objects, this set is {x, y, e}, and the maps (93) are clearly bijective on these sets. (In the formalism of [9] and [6], these objects correspond to the bipartite graphs [ · | ·], [ · | →·] and [ · | ↔·] respectively.) Hence these maps of coalgebras are both monomorphisms and epimorphisms, but not isomorphisms.

Let us consider one more comonoid, S, representing the identity functor, with underlying monoid ⟨x⟩ free on one generator (and bipartite graph [ · | ]). Note that the inclusion S → R′′ is also both a monomorphism and an epimorphism (because it has these properties in Monoid), though in contrast to the morphisms (93), it is not surjective. If we factor this map in the obvious way as S → R → R′′, we see that a composite a ∘ b of morphisms of coalgebras can be both epic and monic, and a also be epic and monic, without b being epic.

What about the cofree coalgebra on a monoid A? One finds that it corresponds to the bipartite graph obtained by taking two copies of A, say {a_{0} | a ∈ |A|} ∪ {a_{1} | a ∈ |A|}, using one as the left side of our graph and the other as the right side, collapsing e_{0} and e_{1} to a single identity element, and drawing directed edges from a_{0} to b_{1} and from a_{1} to b_{0} whenever ab = e.

14. A quick look of Coalg(Ring^{1}, Ab).

Let Ring^{1} denote the variety of associative rings with 1, and Ab the variety of abelian groups, which we will write additively. In [9, Theorem 13.15] it is shown, inter alia, that Coalg(Ring^{1}, Ab) is equivalent to Ab. Precisely, if we denote by U the forgetful functor taking every ring to its underlying abelian group, then every representable functor Ring^{1} → Ab can be obtained by following U with a representable functor Ab(A, −) : Ab → Ab, for some abelian group A. (As is well-known, every abelian group is the representing object of a unique representable functor Ab → Ab, the group structure being given by elementwise operations on group homomorphisms.) The object of Coalg(Ring^{1}, Ab) representing this composite is the tensor ring ℤ⟨A⟩, i.e., the result of applying to A the left adjoint to U, with a co-Ab-structure that the reader can easily write down; and these constructions yield a functorial equivalence.

Limits in Ab are easy to describe, and yield descriptions of the corresponding limits in Coalg(Ring^{1}, Ab).

Note that the tensor ring construction does not respect one-one-ness of maps. For instance, let A be the abelian group ⟨a, b | pb = 0⟩ for any prime p (the direct sum of ℤ and ℤ/pℤ), let B be the subgroup of A generated by pa and b, and let f : B → A be the inclusion map. Then in ℤ⟨B ⟩ the element (pa)b is easily shown to be nonzero, but its image in ℤ⟨A⟩ can be written p(ab) = a(pb) = a0 = 0.

Consequently, statements about Ab that refer to one-one-ness may not go over to Coalg(Ring^{1}, Ab). For instance, in Ab, every one-to-one map is an equalizer (e.g., of its canonical map onto its cokernel group, and the zero map thereto); in particular, this is true of the inclusion A ⊆ B of the preceding paragraph; hence the induced map in the equivalent category Coalg(Ring^{1}, Ab) is also an equalizer; showing that equalizers in that category need not be one-to-one on underlying sets.

References

[1] Peter Aczel and Nax Mendler, A final coalgebra theorem, in Category theory and computer science (Manchester, 1989), 357–365, Lecture Notes in Computer Science, 389, Springer, 1989. MR 91f:18001.

[2] Richard F. Arens and Irving Kaplansky, Topological representations of algebras, Trans. A. M. S. 63 (1948) 457-481. MR 10, p. 7.

[3] Michael Barr, Coalgebras over a commutative ring, J. Algebra 32 (1974) 600–610. MR 53#5707.

[4] Michael Barr, Terminal coalgebras in well-founded set theory, Theoretical Computer Science 114 (1993) 299–315. MR 94m:18006a. Additions and corrections, ibid. 124 (1994) 189–192. MR 94m:18006b.

[5] George M. Bergman, Some category-theoretic ideas in algebra (a too-brief tour of algebraic structure, monads, and the adjoint tower), Proceedings of the 1974 International Congress of Mathematicians (Vancouver) v. I, pp. 285-296, Canadian Mathematical Congress, 1975. MR 58#22222.

[6] George M. Bergman, An Invitation to General Algebra and Universal Constructions, pub. Henry Helson, Berkeley, CA, 1998. Readable online at http://math.berkeley. edu/∼ gbergman/245. MR 99h:18001.

[7] George M. Bergman, Some results on embeddings of algebras, after de Bruijn and McKenzie, Indag. Math. 18 (2007) 349–403. arXiv:0704.0275. MR2373687. http:// www.sciencedirect.com/science/journal/00193577 .

[8] George M. Bergman, Infinite Galois theory, Stone spaces, and profinite groups, course handout, 1997, 12 pp., http://math.berkeley.edu/ ∼ gbergman/grad.hndts/ infGal+profin.ps.

[9] George M. Bergman and Adam O. Hausknecht, Cogroups and Co-rings in Categories of Associative Rings, A. M. S. Mathematical Surveys and Monographs, v.45, ix + 388 pp., 1996. MR 97k:16001.

[10] Garrett Birkhoff, Lattice Theory, 3rd edition, A. M. S. Colloquium Publications, v. XXV, 1967. MR 37#2638.

[11] David M. Clark and Brian A. Davey, Natural Dualities for the Working Algebraist, Cambridge University Press, 1998. MR 2000d:18001.

[12] A. H. Clifford and G. B. Preston, The algebraic theory of semigroups, v. I., Mathematical Surveys No. 7, A. M. S., 1961. MR 24#A2627.

[13] P. M. Cohn, Universal Algebra, 2nd ed., Reidel, 1981. MR 82j:08001.

[14] Peter Freyd, Algebra-valued functors in general and tensor products in particular, Colloquium Mathematicum (Wrocław) 14 (1966) 89–106. MR 33#4116.

[15] Fuchs, László, Infinite abelian groups. Vol. II, Pure and Applied Mathematics. Vol. 36-II. Academic Press, 1973. MR 50#2362.

[16] Peter T. Johnstone, Stone Spaces, Cambridge Studies In Advanced Math., vol. 3, Cambridge University Press, 1982. MR 85f:54002.

[17] Daniel M. Kan, On monoids and their dual, Boletín de la Sociedad Matemática Mexicana (2) 3 (1958) 52-61. MR 22#1900.

[18] Saunders Mac Lane, Categories for the Working Mathematician, Springer Graduate Texts in Mathematics, v.5, 1971. MR 50#7275.

[19] Michael Makkai and Robert Paré, Accessible Categories: the foundations of categorical model theory, Contemporary Mathematics, 104, 1989, ISBN 0-8218-5111-X. MR 91a:03118.

[20] Moss E. Sweedler, Hopf Algebras, Math. Lecture Note Series, Benjamin, N.Y., 1969. MR 40#5705.

[21] D. O. Tall and G. C. Wraith, Representable functors and operations on rings, Proc. London Math. Soc. (3) 20 (1970) 619–643. MR 42#258.

[22] Gavin C. Wraith, Algebraic Theories, Lecture Note Series, vol. 22, Aarhus Universitet, Matematisk Institut, Lectures Autumn 1969, revised version of notes, Feb. 1975. (MR 41#6943 reviews the original version; the revision has far fewer errors. But note re p.49, line 6 from bottom: it is not true that “... every monad on A^{b} arises in this way”.)

Department of Mathematics, University of California Berkeley, CA 94720-3840, USA

Email: gbergman@math.berkeley.edu

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/20/12/20-12.{dvi,ps,pdf}

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. 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 strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

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

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Georgia Southern University: gavin seal@fastmail.fm

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com 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)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 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