       This is the final preprint version of a paper which appeared at
Algebra and Number Theory, 3 (2009) 847-879.  The published version is accessible
 to subscribers at  https://pjm.math.berkeley.edu/ant/2009/3-8/p01.xhtml .

ON COPRODUCTS IN VARIETIES, QUASIVARIETIES AND PREVARIETIES

GEORGE M. BERGMAN

Abstract. If the free algebra F on one generator in a variety V of algebras (in the sense of universal algebra) has a subalgebra free on two generators, must it also have a subalgebra free on three generators? In general, no; but yes if F generates the variety V.

Generalizing the argument, it is shown that if we are given an algebra and subalgebras, A_{0} ⊇ ⋯ ⊇ A_{n}, in a prevariety (𝕊 ℙ -closed class of algebras) P such that A_{n} generates P, and also subalgebras B_{i} ⊆ A_{i−1} (0 < i ≤ n) such that for each i > 0 the subalgebra of A_{i−1} generated by A_{i} and B_{i} is their coproduct in P, then the subalgebra of A generated by B_{1}, …, B_{n} is the coproduct in P of these algebras.

Some further results on coproducts are noted:

If P satisfies the amalgamation property, then one has the stronger “transitivity” statement, that if A has a finite family of subalgebras (B_{i})_{i∈I} such that the subalgebra of A generated by the B_{i} is their coproduct, and each B_{i} has a finite family of subalgebras (C_{ij})_{j∈J_{i}} with the same property, then the subalgebra of A generated by all the C_{ij} is their coproduct.

For P a residually small prevariety or an arbitrary quasivariety, relationships are proved between the least number of algebras needed to generate P as a prevariety or quasivariety, and behavior of the coproduct operation in P.

It is shown by example that for B a subgroup of the group S = Sym(Ω) of all permutations of an infinite set Ω, the group S need not have a subgroup isomorphic over B to the coproduct with amalgamation S ∐_{B} S. But under various additional hypotheses on B, the question remains open.

1. Prologue, for the non-expert.

It is well known that the free group on two generators contains a subgroup free on three generators. Can one deduce, from this alone, that it contains a subgroup free on four generators?

It is unfair to say “from this alone” without indicating what facts about groups are to be taken for granted. So suppose we want to use only the fact that groups form a variety of algebras in the sense of universal algebra – a class of structures consisting of all sets with a family of operations of specified arities, satisfying a specified list of identities. Then we can ask, for V any variety, and n any positive integer,

(1)

If in V the free algebra on n generators has a subalgebra free on n + 1 generators, must it have a subalgebra free on n + 2 generators?

Our first result will be a negative answer to this question, in the most extreme case, n = 1.

On the other hand, a fact that is second nature to combinatorial group theorists is that if G_{1} and G_{2} are overgroups of a common group H, and one forms G_{1} ∐_{H} G_{2}, their coproduct with amalgamation of H (in group-theorists’ notation and language G_{1} ∗_{H} G_{2}, their free product with amalgamation of H), then the canonical maps of G_{1} and G_{2} into that coproduct are embeddings. This says that the variety of all groups has “the amalgamation property”; and we shall see in §6 that if a variety V has this property, then it also has the property that for any algebras A_{1}, A_{2} in V and subalgebras B_{1} ⊆ A_{1}, B_{2} ⊆ A_{1}, the coproduct A_{1} ∐ A_{2} contains the coproduct B_{1} ∐ B_{2}. From this it is not hard to show that for any such V, (1) has an affirmative answer.

2000 Mathematics Subject Classification. Primary: 08B25, 08B26, 08C15. Secondary: 03C05, 08A60, 08B20, 20M30. Key words and phrases. Coproduct of algebras in a variety, quasivariety or prevariety. Free algebra on n generators which

contains a subalgebra free on > n generators. Amalgamation property. Number of algebras needed to generate a quasivariety or prevariety. Symmetric group on an infinite set.

arXiv reference: 0806.1750 . After publication of this note, updates, errata, related references etc., if found, will be recorded at http://math.berkeley.edu/∼ gbergman/papers .

However, the amalgamation property is relatively rare. For instance, though it is satisfied by the variety of all groups, and by all varieties of abelian groups, it does not seem to be satisfied by most other varieties of groups – in fact, it is a longstanding open question whether it is satisfied by any variety of groups other than those just mentioned [15, Problem 6], [11, p.422].

But in section §2, after finding our counterexample to (1), we shall see that a different condition, more common than the amalgamation property, implies a positive answer to (1); namely, that the free algebra of rank n in V generate V, i.e., not lie in any proper subvariety thereof. (As, for example, the free group of rank 2 generates the variety of all groups.)

In §§3-4 we shall generalize this to a result about when an algebra (not necessarily free) containing a coproduct of subalgebras, some of which in turn contain coproducts of subalgebras, will itself contain an “obvious” iterated coproduct. The condition that a certain one of our algebras generate the class we are working in will again be a key assumption; not, this time, for generation as a variety, but as a prevariety, which means, roughly, a class of algebras determined by identities and universal implications. (For example, the class of torsion-free groups, i.e., groups satisfying (∀ x) x^{n} = 1 ⟹ x = 1 for each n > 0, is a prevariety.) The definition of prevariety, and of the related concept of quasivariety, are recalled in §3.

We end with some further results on quasivarieties and prevarieties, and a brief section on subgroups of infinite symmetric groups.

I am indebted to the referee for several helpful suggestions, and to the editorial staff of the journal for requesting that I write this introduction for the general reader.

Carrying that suggestion further, I have added, as §11, a quick summary of some common terminology which should make this note readable (if not light reading) by anyone for whom this prologue was. Readers not familiar with the basic language of universal algebra might start with that section.

2. Free subalgebras of free algebras.

The original question that led to this investigation, [2, Question 4.5], was whether an algebra A in a variety V which contains a subalgebra isomorphic to the coproduct in V of two copies of itself, A ∐_{V} A, must also contain a copy of the 3-fold coproduct A ∐_{V} A ∐_{V} A. As indicated above, this can fail even for A free of rank 1 : a free algebra of rank 1 in a variety V may have a subalgebra free of rank 2 but fail to have any subalgebra free of rank 3. Let us begin by examining how we might concoct such an example.

To do so, we must “foil” the obvious ways one would expect a free 3-generator subalgebra to arise. If ⟨x⟩ is free on x and contains a subalgebra ⟨y, z⟩ free on y and z, then y = px and z = qx for some derived unary operations p, q of V. Since ⟨qx⟩ is isomorphic to ⟨x⟩, its subalgebra corresponding to ⟨y, z⟩, namely ⟨pqx, qqx⟩, will be free on those two generators, and one might expect ⟨px, pqx, qqx⟩ to be free on the three indicated generators. (If it seems to the reader that it must be free on those elements, he or she may be implicitly assuming that V has the amalgamation property, to be discussed in §6.)

For this to fail, there must be some ternary relation T in the operations of V such that T (px, pqx, qqx) is an identity in one variable x, but T (u, v, w) is not satisfied by all 3-tuples of elements of algebras in V. On the other hand, since y = px and z = qx generate a free algebra, the relation T (px, pqx, qqx) implies that T (y, pz, qz) is an identity in two variables y and z in V.

Let us pause to note that if we construct a variety with such an identity T, we will have eliminated one possibility for a free 3-generator subalgebra of ⟨x⟩ of rank 3; but every 3-tuple of expressions obtained from y and z using the operations of V represents another potential generating set for a free subalgebra. In principle, we might use different relations to exclude different 3-tuples; but let us see whether we can make do with just one such relation T, such that T (u, v, w) holds for all 3-tuples (u, v, w) of elements of ⟨x⟩. Note that in this case, since ⟨x⟩ contains a free algebra of rank two, V must satisfy identities saying that T (u, v, w) holds for any elements u, v, w of any V-algebra that lie in a common 2-generator subalgebra.

In testing out this approach, let us temporarily allow structures involving primitive relations as well as operations. Then we could let V be the class of objects defined by two primitive unary operations, p and q, and one primitive ternary relation, T, subject only to the countable family of “identities”

(2)  T (a(y, z), b(y, z), c(y, z)),

one for each 3-tuple of words a, b, c in two variables y, z and the operations p, q. (Of course, since p and q are unary, each of a, b, c really just involves one of y or z.) In an object of V generated by ≤ 2 elements, T thus holds identically, so in describing the structures of ≤ 2-generator objects, we can ignore the relation T, and simply specify the actions of p and q. Since the family of identities (2) by which we have defined V includes no identities in the operations p and q alone, the possible structures of such objects are simply the structures of M-set, for M the free monoid on generators p and q. In this monoid M, the left ideal generated by p and q is free on those two elements; hence in the free V-object on one generator x, the elements px and qx satisfy no relations in p and q; so with T, as noted, also contributing no information, px and qx indeed generate a free subobject. On the other hand, if we take the free M-set on three generators x, y, z, and define T to hold precisely on those 3-tuples thereof in which all three components lie in a subalgebra generated by two elements, we see that this satisfies the definition of a free V-object on three generators, and that T (x, y, z) does not hold. Hence the free object on one generator does not contain a copy of the free object on three generators.

Let us now try to mimic the above behavior in a variety of genuine algebras. In addition to two unary operations p and q, let us introduce a 0-ary operation 0 and a ternary operation t, with the idea that the relation T (u, v, w) will be the condition t(u, v, w) = 0. To keep our new operations from complicating our structures more than necessary, let us introduce some “nonproliferation” identities:

(3)  p0 = q0 = p t(x, y, z) = q t(x, y, z) = 0.
(4)  t(u, v, w) = 0 whenever any of u, v, w is either 0, or is itself of the form t(u′, v′, w′).

Finally, we impose the identities corresponding to (2):

(5)  t(a(x, y), b(x, y), c(x, y)) = 0 for all derived operations a, b, c in two variables.

In a free V-algebra, the elements t(u, v, w) that are not 0 may be thought of as “tags”, showing that certain 3-tuples (u, v, w) obtained from the generators using p and q alone do not have the form indicated in (5). By (3) and (4), these elements have essentially no other effect. By the same reasoning as for structures with a primitive relation T, we get

Proposition 1. Let V be the variety defined by a zeroary operation 0, two unary operations p and q, and a ternary operation t, subject to identities (3), (4), (5).

Then in the free V-algebra F_{V}(x) on one generator x, the subalgebra generated by px and qx is free on those generators; but F_{V}(x) (and hence also the free algebra on two generators) has no subalgebra free on three or more generators. □

The above result was based on F_{V}(x) satisfying an identity (namely, t(x, y, z) = 0) that did not hold in all of V; and we might hope that if V is a variety where this does not happen, but which, as above, has unary derived operations p and q such that px and qx are free generators of the subalgebra ⟨px, qx⟩ ⊆ F_{V}(x), then the subalgebra ⟨px, pqx, qqx⟩ will have to be free on the indicated three generators. To investigate this question, consider a ternary relation T in the operations of V about which we now merely assume that T (px, pqx, qqx) holds in F_{V}(x), and let us see whether we can deduce that T holds for all 3-tuples of elements of F_{V}(x).

As noted earlier, the conditions that T (px, pqx, qqx) holds in F_{V}(x), and that y = px and z = qx generate a free algebra ⟨y, z⟩, show that in that free algebra, T (y, pz, qz) holds, hence that in any Valgebra, T holds on any 3-tuple whose last two terms are obtained from a common element by applying p, respectively, q to it. Let us now apply this observation to a 3-tuple in F_{V}(x) of the form (a(px, qx), px, qx) where a is any derived operation of V, and use the independence of px and qx a second time. We conclude that T (a(y, z), y, z) holds for every such a. In other words, in any V-algebra, T holds on every 3-tuple whose first term lies in the subalgebra generated by the last two terms.

But there is no evident way to carry this process further. And in fact, we can again get a negative result by the same technique of realizing T as t(u, v, w) = 0, embodying the conditions that we have found T must satisfy, this time, in the system of identities:

(6)  t(u, pv, qv) = 0 for all u, v.
(7)  t(a(u, v), u, v) = 0 for all u, v, and all binary terms a.

The one tricky point is to show that the variety so defined now has the property that there are no identities satisfied by the free algebra on one generator that are not identities of the whole variety. In contrast to the earlier example, our development has not called on any such identities; but neither has it shown that none exist. With some work, one can prove this; but an easier approach, which we will follow, is to let V_{0} denote the variety defined by the identities discussed above, and let our V be the subvariety of V_{0} generated by the free algebra on one generator therein. Here are the details.

Proposition 2. Let V_{0} be the variety defined by a zeroary operation 0, two unary operations p and q, a ternary operation t, and the identities (3), (4), (6), and (7); and let V be the subvariety of V_{0} generated by the free algebra F_{V_{0}}(x) on one generator. Thus, F_{V}(x) = F_{V_{0}}(x), so V is generated by F_{V}(x).

In this situation, the subalgebra ⟨px, qx⟩ ⊆ F_{V}(x) is free in V (and in fact in V_{0}) on the two generators px and qx; but the subalgebra ⟨px, pqx, qqx⟩ is not free in V (and hence not in V_{0}) on px, pqx and qqx.

Proof. The last sentence of the first paragraph is clear in the general context of a subvariety generated by a free algebra in any variety.

We shall next show that ⟨px, qx⟩ ⊆ F_{V}(x) is free on px and qx in V_{0}. Since it is a subalgebra of F_{V}(x) and hence belongs to V, it will then a fortiori be free on those generators in that subvariety.

To do this, we need to prove that any relation satisfied in F_{V}(x) by px and qx also holds between y and z in F_{V_{0}}(y, z). Let M again denote the free monoid on the two symbols p and q. We know as before that the elements of F_{V}(x) obtained from x using p and q alone form a free M-set on one generator, and hence that the sub-M-set M{px, qx} is free as an M-set on px and qx. Thus, if the given relation satisfied by px and qx involves only the operations p and q, it will indeed be satisfied by y and z. Hence in what follows, we may assume the relation involves t and/or 0.

Now by (3) and (4), if either side of our relation in px and qx involves 0 or t other than in the outermost position, that side equals 0, and the corresponding expression in y and z does as well; so we can replace that side by 0 in our relation. Given the forms of the identities (6) and (7), it is not hard to see that to complete our proof it will suffice to show that if

(8)  t(b(px, qx), c(px, qx), d(px, qx)) = 0

is an identity of V_{0}, where

(9)  b(px, qx), c(px, qx), d(px, qx) ∈ M{px, qx},

then V_{0} also satisfies the identity

(10) t(b(y, z), c(y, z), d(y, z)) = 0.

Moreover, (3) and (4) yield no relations of the form (8) satisfying (9), so we need only look at relations (8) of the forms (6) and (7).

An instance of (7) can have the form (8) only if the given u and v have the forms c(px, qx) and d(px, qx); but then putting y and z in place of px and qx in that instance of (7) again gives an instance of (7), and hence a relation in F_{V_{0}}(y, z), as required. If an instance of (6) has the form (8), then we have u = b(px, qx), but there are two possibilities for the element v : it can either be x, or of the form e(px, qx). In the former case, this instance of (6) is also an instance of (7), and the preceding argument applies. In the latter case, the relation has the form t(b(px, qx), pe(px, qx), qe(px, qx)) = 0, and we see that t(b(y, z), pe(y, z), qe(y, z)) = 0 is again an instance of (6), and hence a relation in F_{V_{0}}(y, z). This completes the proof that ⟨px, qx⟩ is free on px and qx.

To see, finally, that ⟨px, pqx, qqx⟩ is not free on the indicated generators in V, we note that F_{V_{0}}(x), which generates V, has 3-tuples of elements of M{x} to which neither (6) nor (7) applies, e.g., (x, qx, px). Hence t(x, y, z) = 0 is not an identity of V; hence the elements px, pqx, qqx, which do satisfy that relation, cannot be free generators of a free subalgebra. □

After obtaining the above result, I wondered whether for every 3-tuple (ax, bx, cx) in M{x}, one could find a ternary relation T_{a,b,c} on M{x} that could be embodied in a construction like the above, giving an algebra in which that 3-tuple was not a free generating set. If so, then it would seem that by defining a variety with operations 0, p, and q and countably many ternary operations t_{a,b,c}, one for each such choice of a, b and c, one should be able to get an example where, as above, F_{V}(x) generated V and ⟨px, qx⟩ ⊆ F_{V}(x) was free on px, qx, but where F_{V}(x) contained no subalgebra free on three generators.

But just a bit more experimentation revealed 3-tuples (ax, bx, cx) for which no T_{a,b,c} with the desired property exists. Translating the resulting obstruction into a proof of a positive statement, this is

Proposition 3. Let V be a variety of algebras such that the free algebra F_{V}(x) on one generator generates V as a variety, and contains a subalgebra free of rank 2 in V, say on generators px and qx, where p and q are derived unary operations of V. Then the subalgebra ⟨px, pqx, pqqx⟩ ⊆ F_{V}(x) is free in V on the indicated three generators.

Proof. It will suffice to show that for any three elements

(11) ax, bx, cx ∈ F_{V}(x),

there exists a homomorphism ⟨px, pqx, pqqx⟩ → F_{V}(x) carrying px, pqx, pqqx to ax, bx, cx respectively, since this will show that every relation satisfied by px, pqx and pqqx is an identity of F_{V}(x), and hence, by hypothesis, of V.

Given elements (11), let us first use the freeness of ⟨px, qx⟩ to get a homomorphism f : ⟨px, qx⟩ → F_{V}(x) carrying px to aqqx, and qx to x. Thus the image of (px, pqx, pqqx) under this map is (aqqx, px, pqx). Since this 3-tuple, and hence the subalgebra it generates, again lies in ⟨px, qx⟩, we can compose this homomorphism with another homomorphism, g : ⟨px, qx⟩ → F_{V}(x); let this take px to bqx and qx to x. This takes the preceding 3-tuple to (aqx, bqx, px). Finally, mapping ⟨px, qx⟩ to F_{V}(x) by the homomorphism h sending px to cx and qx to x, we get the desired 3-tuple (ax, bx, cx). Hence, the composite hgf : ⟨px, pqx, pqqx⟩ → F_{V}(x) acts as required. □

In the question we have answered, the choice of ranks one, two and three was, of course, made to give a concrete test problem. This, and the restriction to free algebras rather than coproducts of general algebras, make our counterexamples, Propositions 1 and 2, formally stronger, but our positive result, Proposition 3, weaker than the corresponding result without those restrictions. We shall generalize Proposition 3 in the next two sections so as to remove these restrictions.

3. Prevarieties and quasivarieties.

In the proof of Proposition 3, we used the fact that if V is the variety generated by an algebra A, then a V-algebra generated by a family of elements, B = ⟨{x_{i} | i ∈ I}⟩, is free on those generators if and only if there exist homomorphisms B → A taking the x_{i} to all choices of I-tuples of elements of A. For our generalization, we would like to say similarly that if an algebra B is generated by a family of subalgebras B_{i} (i ∈ I), then it is their coproduct if and only if every system of homomorphisms from the algebras B_{i} to our given algebra A extends to a homomorphism B → A. We shall see that this is true for coproducts, not in the variety generated by A, but in the prevariety so generated (definition recalled below).

There are a few points of notation and terminology in which usage is not uniform; we begin by addressing these.

First, we admit the empty algebra when the operations of our algebras include no zeroary operations. Second, note that the operators ℍ , 𝕊 and ℙ on classes of algebras that appear in Birkhoff’s Theorem

and related results each come in two slightly different flavors. One may associate to a class X of algebras the class of all factor algebras of members of X by congruences, or the class of algebras isomorphic to such factor algebras, i.e., the homomorphic images of members of X. Likewise, one may associate to X the family of subalgebras of members of X, or the family of algebras isomorphic to such subalgebras; i.e., algebras embeddable in members of X. And finally, we may associate to X the class of direct product algebras constructed from members of X in the standard way as algebras of tuples, or the class of algebras isomorphic to algebras so constructed, i.e., algebras P that admit a family of maps to the indicated members of X giving P the universal property of their direct product. It is probably an accident of history that the symbols ℍ , 𝕊 and ℙ were assigned, in two cases (subalgebras and products) to particular explicit constructions, but in the remaining case (homomorphic images) to the isomorphism-closed concept. The standard remedy is to introduce an operator 𝕀 , taking every class X of algebras to the class of algebras isomorphic to members of X, and apply 𝕀 in conjunction with 𝕊 and ℙ when the wider construction is desired. But that wider construction usually is what is desired, so (following [14]) we will use the less standard definitions:

Definition 4. If X is a class of algebras of the same type, then 𝕊 X will denote the class of algebras isomorphic to subalgebras of algebras in X, and ℙ X the class of algebras isomorphic to direct products of algebras in X (including the direct product of the empty family, the 1-element algebra). As usual, ℍ X will denote the class of homomorphic images of algebras in X.

A third point on which terminology is divided concerns the definition of “quasivariety”. Both usages agree that this means a class of algebras A determined by a set of conditions of the form

(12) (∀ x ∈ A^{I}) (⋀_{j∈J} a_{j}(x) = b_{j}(x)) ⟹ c(x) = d(x),

where I and J are sets, and the a_{j} and b_{j} and c and d are I-ary terms in the algebra operations. (J may be empty, in which case (12) represents an ordinary identity.) The point of disagreement is whether I and J are required to be finite. The more standard usage, which, somewhat reluctantly, I will follow, assumes this; a class of algebras defined by sentences (12) where I and J are not required to be finite is then called a prevariety. The other usage is exemplified by [1], where “quasivariety” is defined with no finiteness restriction on I and J, while “prevariety” is used for a still more general sort of class of algebras (typified by monoids in which every element is invertible; i.e. groups regarded as monoids).

(My discomfort with the standard usage is that the prefix “pre-” suggests a concept used mainly for technical purposes in the development of another concept, as in “preorder”, “presheaf” and “precategory”. Also, the relationship between “prevariety” and “quasivariety” is not mnemonic, as “quasivariety” and “elementary quasivariety” would be. Incidentally, if X is a finite set of finite algebras, the prevariety and the quasivariety that it generates are the same, so works like [7] don’t have to distinguish the concepts.)

The concept of quasivariety is a natural one only for finitary algebras. (The constructions of reduced products and ultraproducts, occurring in standard characterizations of quasivarieties, are not in general defined on infinitary algebras.) Most of our results on prevarieties will not require finitariness; so algebras comprising prevarieties will not be assumed finitary unless this is explicitly stated.

We summarize this and some related conventions in

Definition 5. A prevariety will mean a class P of algebras of a given (not necessarily finitary) type that can be defined by a class of conditions of the form (12); equivalently that is closed under the operators 𝕊 and ℙ .

A prevariety P which is finitary (i..e, every primitive operation of which has finite arity), will be called a quasivariety if

(13) P can be defined by conditions (12) in each of which I and J are finite,

equivalently,

(14) P is closed under ultraproducts,

equivalently,

(15) P is closed under reduced products.

If X is a class of algebras of a given type, the least prevariety containing X, namely, 𝕊 ℙ X, will be called the prevariety generated by X. Likewise, if the type is finitary, the least quasivariety containing X, namely, 𝕊 ℙ ℙ_{ult} X = 𝕊 ℙ_{red} X, where ℙ_{ult} and ℙ_{red} denote, respectively, the constructions of ultraproducts and reduced products (and algebras isomorphic thereto), will be called the quasivariety generated by X. Again without the assumption of finitariness, the least variety containing X, namely, ℍ 𝕊 ℙ X, will be called the variety generated by X.

In any prevariety, one has algebras presented by arbitrary systems of generators and relations. In particular, every family of algebras has a coproduct. A useful characterization of these is

Lemma 6. Let X be a class of algebras of a given type, let P = 𝕊 ℙ X be the prevariety generated by X, let B be an algebra in P, and let f_{i} : B_{i} → B (i ∈ I) be a family of maps from algebras in P into B.

Then the algebra B is a coproduct of the B_{i} in P, with the f_{i} as the coprojection maps, if and only if the following two conditions are satisfied:

(16) B is generated as an algebra by the union of the images f_{i}(B_{i}).

(17)

For every A in our generating class X, and every choice of a family of maps g_{i} : B_{i} → A (i ∈ I), there exists a homomorphism g : B → A such that g_{i} = gf_{i} for all i ∈ I.

Sketch of proof. “Only if” is straightforward: the necessity of (16) is shown, as usual, by applying the universal property of B as a coproduct to the maps f_{i}, regarded as taking the B_{i} into the subalgebra C of B that they together generate (which belongs to P, since P is closed under taking subalgebras); while the necessity of (17) is a case of that universal property.

Conversely, assuming (16) and (17), let us show that B and the f_{i} satisfy the universal property of the coproduct. Let C be any algebra in P, given with homomorphisms a_{i} : B_{i} → C.

If there exists a homomorphism a : B → C with a_{i} = af_{i} for all i, then by (16) it will be unique.

To see that such a map exists, we write C as a subalgebra of a direct product ∏_{j∈J} A_{j} with all A_{j} in X. Then for each j ∈ J, the composites of the given maps a_{i} : B_{i} → C with the j-th projection C → A_{j} give a system of maps a_{ij} : B_{i} → A_{j} (i ∈ I). By (17), for each j the a_{ij} are induced by a single map a_{∗j} : B → A_{j}; doing this for all j ∈ J gives a map a : B → ∏_{J} A_{j}, whose restriction to each f_{i}(B_{i}) ⊆ B lies in C ⊆ ∏_{j∈J} A_{j}. Hence a(B) lies in C by (16). The relations a_{ij} = a_{∗j}f_{i} now show that a_{i} = af_{i}, as required. □

Remarks: We shall see in §7 that it can happen that though each B_{i} lies in P = 𝕊 ℙ X, no A ∈ X simultaneously admits maps from all B_{i}. In that case, condition (17) is vacuous, and the lemma says that (16) characterizes the coproduct ∐_{P} B_{i}. Though implausible-sounding, this is correct: in that case an algebra B with maps of the B_{i} into it, to belong to P = 𝕊 ℙ X, must embed in the product of the vacuous family of members of X, hence can have at most one element, so there is hardly any way it can differ from the desired universal object; (16) merely guarantees that if all B_{i} are empty, B is also.

In a different direction, taking I = ∅ in the above result and recalling that a coproduct of the empty family of objects in a category is an initial object of the category, the result says that an algebra B is initial in P if and only if it is generated by the empty set and admits a homomorphism into each A ∈ X.

4. P-independent subalgebras.

Definition 7. If A is an algebra in a prevariety P, we shall call a family of subalgebras B_{i} ⊆ A (i ∈ I) P-independent if the subalgebra B ⊆ A that they generate, given with the system of inclusion maps B_{i} → B, is a coproduct of the B_{i} in P.

Here, finally, is the promised generalization of Proposition 3.

Theorem 8. Suppose that P is a prevariety of algebras and A_{0} an algebra in P, and that for some natural number n we are given subalgebras A_{1}, …, A_{n} and B_{1}, …, B_{n} of A_{0}, such that for i = 1 … n, A_{i} and B_{i} are P-independent, and are both contained in A_{i−1}. Assume, moreover, that P is generated as a prevariety by A_{n}.

Then B_{1}, …, B_{n} are P-independent.

Proof. Let us prove by induction on i = 0, …, n a statement a little stronger than what we will need for i = n, namely that for every system of homomorphisms f_{j} : B_{j} → A_{i} (j = 1, …, i), there exists a unique homomorphism f from the subalgebra of A_{0} generated by B_{1}, …, B_{i} and A_{i} into A_{i} which acts on each B_{j} (j = 1, …, i) as f_{j}, and which acts as the identity on A_{i}.

This is clear for i = 0. Let 0 < i ≤ n, inductively assume the result for i − 1, and suppose we are given f_{j} : B_{j} → A_{i} (j = 1, …, i). Since A_{i} ⊆ A_{i−1}, our inductive hypothesis gives us a homomorphism g from the subalgebra of A_{0} generated by B_{1}, …, B_{i−1} and A_{i−1} into A_{i−1} which agrees with f_{j} for j = 1, …, i − 1, and is the identity on A_{i−1}. Note that g will carry the subalgebra generated by B_{1}, …, B_{i} and A_{i} into the subalgebra generated by A_{i} (into which it carries B_{1}, …, B_{i−1} and A_{i}) and B_{i} (which is contained in A_{i−1}, and so is left fixed).

But by assumption, that subalgebra is the coproduct of A_{i} and B_{i}, so we can map it into A_{i} by a homomorphism h which acts as the identity on A_{i} and as f_{i} on B_{i}. Now f = hg clearly has the property required for our inductive step.

Taking the i = n case of our result, and ignoring the condition that f be the identity on A_{n}, we see that the subalgebra B ⊆ A_{0} generated by B_{1}, …, B_{n} satisfies (17) for X the singleton family {A_{n}}. Since by assumption A_{n} generates P, Lemma 6 tells us that B is the coproduct of the B_{i} in P. □

Remark: We might call a family of subalgebras B_{i} of an algebra A in a prevariety P, given with a distinguished member B_{0} which generates P, “almost P-independent” if every family of homomorphisms f_{i} : B_{i} → B_{0} such that f_{0} is the identity map of B_{0} can be realized by a homomorphism on the subalgebra generated by the B_{i}. We see from the proof of Theorem 8 that that theorem remains true if the P-independence hypothesis is weakened to say that each pair (A_{i}, B_{i}), with A_{i} taken as the distinguished member, is almost P-independent, and the conclusion strengthened to say that the n+1-tuple (A_{n}, B_{1}, …, B_{n}), with A_{n} as distinguished member, is almost P-independent. The condition of almost Pindependence seemed too technical to use in the formal statement of the theorem; but one might keep it in mind. It is interesting that while Proposition 2 showed that in the situation described there, the subalgebras ⟨px⟩, ⟨pqx⟩ and ⟨qqx⟩ of F_{V}(x) were not V-independent, the above proof shows that, with the last of them taken as distinguished, they are almost V-independent.

Note that Theorem 8 holds even in the case n = 0 : If A_{0} generates P, then the subalgebra of A_{0} generated by the empty set is the initial object of P.

A case of Theorem 8 with a simpler hypothesis is

Corollary 9. Suppose A and B_{1}, …, B_{n} are algebras in a prevariety P, such that A generates P, and such that for each i, A contains an isomorphic copy of A ∐_{P} B_{i}. Then A contains an isomorphic copy of ∐_{P}^{i=1,...,n} B_{i}. □

Recall next that a free algebra in a prevariety P is also free on the same generators in the variety V generated by P. Hence we can apply the above results to free algebras in a variety, and obtain the following result extending Proposition 3 (though we omit, for brevity, the explicit description of the free generators).

Corollary 10. Suppose V is a variety and m < n are positive integers such that the free V-algebra F_{V}(x_{1}, …, x_{m}) on m generators has a subalgebra free on n generators, and such that V is generated as a variety by F_{V}(x_{1}, …, x_{m}). Then for every natural number N, F_{V}(x_{1}, …, x_{m}) has a subalgebra free on N generators.

Proof. A free V-algebra F_{V}(x_{1}, …, x_{n}) has subalgebras free on all smaller numbers of generators; so the above hypothesis implies that F_{V}(x_{1}, …, x_{m}) has a subalgebra free on m+1 generators. This is a coproduct of a free algebra on m generators and a free algebra on one generator, so we get the hypothesis of Corollary 9 with P the prevariety generated by A = F_{V}(x_{1}, …, x_{m}), the n of that corollary taken to be N, and each B_{i} taken to be free on one generator. The conclusion shows that F_{V}(x_{1}, …, x_{m}) has a subalgebra free on N generators in the prevariety it generates. As noted, a free algebra in a prevariety P is also free in the variety V generated by P. □

Can we strengthen this result to give free subalgebras of countably infinite rank? Yes if our algebras are finitary. We will need

Lemma 11. Let P be a prevariety of finitary algebras, A an algebra in P, and (B_{i})_{i∈I} a family of subalgebras of A, such that every finite subset I_{0} ⊆ I is contained in a subset I_{1} ⊆ I such that the family of subalgebras (B_{i})_{i∈I_{1}} is P-independent. Then (B_{i})_{i∈I} is P-independent.

Proof. We need to show that the map f_{I} : ∐_{P}^{I} B_{i} → A whose composite with each coprojection q_{j} : B_{j} → ∐_{P}^{I} B_{i} is the inclusion of B_{j} in A is one-to-one. By finitariness of P, every element of ∐_{P}^{I} B_{i} lies in the subalgebra generated by finitely many of the B_{i}, hence it will suffice to show that for any finite subset I_{0} ⊆ I, the restriction of f_{I} to the subalgebra of ∐_{P}^{I} B_{i} generated by {B_{i} | i ∈ I_{0}} is one-to-one. By assumption, I_{0} is contained in a subset I_{1} such that the family (B_{i})_{i∈I_{1}} is P-independent; hence the canonical map f_{I_{1}} : ∐_{P}^{I_{1}} B_{i} → A is one-to-one; but that map factors through f_{I}, so f_{I} is one-to-one on its image, the subalgebra of ∐_{P}^{I} B_{i} generated by {B_{i} | i ∈ I_{1}}, hence on the smaller subalgebra generated by {B_{i} | i ∈ I_{0}}, as required. □

(We shall see in §6 and §8 respectively that if a prevariety P either satisfies the amalgamation property – which is not in general the case in the situation we are interested in here – or is generated as a prevariety by a single algebra – which is true in the situation to which we are about to apply the above lemma – then any subfamily of a P-independent family of subalgebras is P-independent; so in such cases, the hypothesis of the above lemma can be simplified merely to say that every finite subset of I is P-independent. But in a general prevariety P, a subfamily of a P-independent family need not be P-independent, hence that simplified statement does not carry the full force of the lemma. For an example of P-independence not carrying over to subfamilies, take for P the variety V of monoids with two distinguished elements x and y, let A be the V-algebra generated by a universal 2-sided inverse to x, denoted x^{−1}, let B_{1} and B_{2} both be the subalgebra of A generated by u = x^{−1}y, which is a free monoid on two generators u and x, regarded as a member of V by setting y = xu, and let B_{3} be the whole algebra A. It is not hard to verify that in B_{1} ∐_{V} B_{2}, the images u_{1}, u_{2} of the copies of u from B_{1} and B_{2} are distinct (though they satisfy xu_{1} = xu_{2}). Since in A itself, in contrast, their images are equal, B_{1} and B_{2} are not V-independent subalgebras of A. But in B_{1} ∐_{V} B_{2} ∐_{V} B_{3}, the properties of 2-sided inverses force the generators of B_{1} and B_{2} to fall together with the corresponding elements of B_{3}, so the family consisting of these three subalgebras satisfies the definition of V-independence.)

Combining the above lemma with our earlier results, we get

Corollary 12. Let P, in (i) and (ii) below, be a prevariety of finitary algebras, and V, in (iii), a variety of such algebras. Then

(i) If A_{0} ⊇ A_{1} ⊇ ⋯ ⊇ A_{i} ⊇ … are algebras in P such that every A_{i} generates P as a prevariety; and if for each i > 0, B_{i} is a subalgebra of A_{i−1} such that A_{i} and B_{i} are P-independent, then the countable family (B_{i})_{i>0} is P-independent.

Hence, (ii) If A is an algebra which generates P as a prevariety, and we are given a countable family of algebras (B_{i})_{i>0} in P, such that for each i, A has a subalgebra isomorphic to A ∐_{P} B_{i}, then A has a subalgebra isomorphic to ∐_{P}^{i>0} B_{i}.

Hence, (iii) If for some positive integer m the free algebra F_{V}(x_{1}, …, x_{m}) generates V as a variety, and contains a subalgebra free on > m generators, then it contains a subalgebra free on countably many generators. □

Lemma 11 and Corollary 12 both fail if the assumption that our algebras are finitary is deleted. To see this for the lemma, let V be the variety determined by one operation a of countably infinite arity, and identities saying that whenever two of x_{0}, x_{1}, … are equal, we have

(18) a(x_{0}, x_{1}, …) = x_{0}.

Let A be a countably infinite set, on which a is defined by letting (18) hold for all x_{0}, x_{1}, …. Then every finite subset of A is a free subalgebra on that set, from which one sees that any finite family of distinct singleton subsets is an independent set of subalgebras; but the set of all of these is not independent, because their coproduct in the variety V, the free V-algebra on countably many generators, does not satisfy (18) identically.

To show that the statements of Corollary 12 all need the finitariness condition, it suffices to give a counterexample to statement (iii) in the absence of that condition. The idea will be the same as above, but the details are more complicated, and I will be a little sketchy.

The variety in question will have countably many zeroary operations c_{0}, c_{1}, …, two unary operations p and q, an operation a of countable arity, and an additional zeroary operation 0, satisfying the analogs of (3) and (4) with a in place of t. As in §2, let M denote the free monoid on the symbols p and q. Let V_{0} be defined by the abovementioned analogs of (3) and (4), together with the (uncountable) family of identities saying that

(19) a(x_{0}, x_{1}, …) = 0 if infinitely many of the x_{i} belong to M{u} for some common element u.

These identities do not imply a(c_{0}, c_{1}, …) = 0, so a(x_{0}, x_{1}, …) = 0 is not an identity in any free algebra in V_{0}. Once again, let V be the subvariety of V_{0} generated by the free algebra F_{V}(x) on one generator.

One finds that the subalgebra ⟨px, qx⟩ ⊆ F_{V}(x) = F_{V_{0}}(x) is free on px and qx. The key point is that if an element a(x_{0}, x_{1}, …) with x_{0}, x_{1}, ⋯ ∈ ⟨px, qx⟩ equals 0 in F_{V}(x) by an application of (19), and the element u of the hypothesis of (19) is x, then the infinite family of elements of M{u} in question will be the union of a family of elements of M{px} and a family of elements of M{qx}, one of which must still be infinite; so the relation a(x_{0}, x_{1}, …) = 0 still follows from the expressions for the x_{i} in terms of px and qx.

However, I claim that F_{V}(x) contains no subalgebra free on countably many generators. For note that a family of independent elements of F_{V}(x) cannot include the value of any primitive or derived zeroary operation (since their behavior under homomorphisms is not free), nor any element obtained with the help of a, by the analogs of (3) and (4); hence such a family must lie entirely in M{x}. But by (19) (with u = x), any infinite family x_{0}, x_{1}, … of elements of M{x} satisfies the relation a(x_{0}, x_{1}, …) = 0, which we have seen is not an identity of V; so no infinite family of elements of F_{V}(x) is independent.

5. Some questions.

Proposition 1 shows that Corollary 10 becomes false if we delete the assumption that F_{V}(x_{1}, …, x_{m}) generates P. In the absence of that assumption, it is not clear what forms the relation of mutual embeddability can assume.

Question 13. For V a variety, let us call natural numbers m and n V-equivalent (with respect to embeddability of free algebras) if F_{V}(x_{1}, …, x_{m}) and F_{V}(x_{1}, …, x_{n}) each contain an isomorphic copy of the other. Clearly, the V-equivalence classes are blocks of consecutive integers. Which decompositions of the natural numbers into blocks can be realized in this way?

More generally, given a prevariety P and algebras A_{1}, …, A_{r} in P, let us define a preorder ⪯ on r-tuples of natural numbers by writing (m_{1}, …, m_{r}) ⪯ (n_{1}, …, n_{r}) if the coproduct in P of m_{1} copies of A_{1}, m_{2} copies of A_{2}, etc., through m_{r} copies of A_{r}, is embeddable in the coproduct of n_{1} copies of A_{1} etc., through n_{r} copies of A_{r}. What preorderings on ω^{r} can be realized in this way? In particular, what equivalence relations on ω^{r} can be the equivalence relation determined by such a preorder? Do these answers change if one requires P to be a variety?

In [18], for certain varieties V of Lie algebras over a field of characteristic 0, bounds are obtained on n/m for any m, n equivalent under the relation of the first paragraph of Question 13 above. The idea is to note that if F_{V}(x_{1}, …, x_{m}) and F_{V}(x_{1}, …, x_{n}) are mutually embeddable, they must have the same Gelfand-Kirillov dimension (a measure of growth rate). Upper and lower bounds are obtained for the Gelfand-Kirillov dimension of F_{V}(x_{1}, …, x_{n}), leading to the asserted conclusions. However, it seems most likely that for such V, the Gelfand-Kirillov dimension of F_{V}(x_{1}, …, x_{n}) will grow with n in a “smooth” fashion; if so, one should in fact be able to prove that no free algebras of distinct ranks in V are mutually embeddable, in which case such varieties will not give interesting examples relevant to Question 13.

For results on isomorphisms and surjections among free algebras, rather than embeddings, see [16], [6], and [8]. The last of these shows that all consistent cases are realized by module-varieties Mod_{R} for rings R.

In generalizing Proposition 3 from free algebras to general coproducts, we found that the context that made the argument work was that of coproducts in a prevariety. Theorem 8 does not give us the corresponding statement for general A_{0}, …, A_{n}, B_{1}, …, B_{n} with the prevariety P replaced by a variety V, and the condition that P be generated by A_{n} as a prevariety replaced by the condition that V be generated by A_{n} as a variety, since for a variety V and an algebra A ∈ V, the condition that V be generated by A as a variety is weaker than the condition that it be generated by A as a prevariety. (E.g., the variety of abelian groups is generated by the infinite cyclic group as a variety, but not as a prevariety, since all groups in the prevariety it generates must be torsion-free.) But I don’t have a counterexample to the modified statement.

Question 14. (i) Does Theorem 8 remain true if “prevariety” is everywhere replaced by “variety”?

If not, or if the question proves difficult, one might examine some special cases, such as (ii) If in Corollary 9 we replace “prevariety” by “variety”, and add the assumption that A is free of rank 1 in that variety (but not that the B_{i} are free), does the statement still hold? (iii) If V is a variety, and A an algebra that generates V as a variety, and that contains as a subalgebra a coproduct of two copies of itself in V, must it contain a coproduct of three copies of itself in V ?

More likely to have positive answers, since quasivarieties are more like prevarieties than varieties are, is

Question 15. Same questions (i), (ii), (iii) as above, but with “variety” everywhere replaced by “quasivariety” (necessarily, of finitary algebras).

Looking back further, to §2, the mixture of positive and negative results there suggests

Question 16. Is there a nice criterion for whether a 3-tuple (a, b, c) of monoid words in two letters p, q has the property proved in Proposition 3 to hold for the 3-tuple (p, pq, pqq), and in Proposition 2 not to hold for the 3-tuple (p, pq, qq), namely, of witnessing the existence of subalgebras free on 3 generators in all relatively free 1-generator algebras ⟨x⟩ that contain free 2-generator subalgebras ⟨px, qx⟩ in the varieties they generate?

More generally, given n > 1 and N > 1, one may ask for a criterion for an N-tuple (a_{1}, …, a_{N}) of words in n letters p_{1}, …, p_{n} to witness the existence of a free subalgebra on N generators in any relatively free algebra on one generator that contains a free subalgebra ⟨p_{1}x, …, p_{n}x⟩ on n generators in the variety it generates.

(Still more generally, for n > m > 0 and N > 1, one may ask how to decide whether a given N-tuple of terms in m variables and n operation symbols each of arity m witnesses the result of Corollary 10. But since terms in operation symbols of arity > 1 are more complicated than words in unary operation symbols, there seems to be less likelihood of a simple answer.)

The next four sections are related to, but do not depend on, the material above, except for the definitions. Section 6 recalls what it means for a category of algebras to have the amalgamation property, obtains some equivalent statements, and then shows that for prevarieties with that property, one has stronger results on when a family of subalgebras of an algebra generates a subalgebra isomorphic to their coproduct than those that we have seen to hold in general. In a different direction, motivated by the fact that the prevarieties considered in §4 were by hypothesis each generated by a single algebra, §§7-9 show that the number of algebras needed to generate a prevariety has important consequences for the behavior of coproducts therein. The brief section §10, which is included in this note only for convenience, answers a different question about coproducts, also raised in [2], concerning subgroups of the full symmetric group on an infinite set.

6. The amalgamation property, and its consequences for P-independence.

In any class of algebras that admits coproducts with amalgamation (pushouts), it is well known and easy to verify that the amalgamation property (definition recalled in (20) below) is equivalent to the condition that for all pairs of one-to-one maps with common domain, A → B and A → C, the coprojection maps of B and C into the coproduct with amalgamation B ∐_{A} C are also one-to-one. The next lemma gives some further consequences of that property, in the same vein. We formulate it in a context more general than that of categories of algebras, though less sophisticated than that of [10, §6].

In that lemma, the functor U : C → Set plays the role of the underlying set functor of a category of algebras, but we shall not need to assume it faithful, as one does when defining the concept of a concrete category.

One other notational remark: So far, I have generally written ∐_{P} for “coproduct in the category P ”; but when discussing coproducts with amalgamation of an object, we will use the subscript position for that object, leaving the category to be understood from the context. I will follow this mixed practice for the rest of the paper, showing the category when no amalgamation is involved. (The superscript position, which might otherwise be assigned to one of these, is used here for index sets over which coproducts are taken. If there were danger of ambiguity, we could write ∐_{P,A} rather than ∐_{A}, or regard coproducts with amalgamation as coproducts in a comma category (A ↓ P) and so write ∐_{(A ↓ P)} .)

Lemma 17. Let C be a category and U : C → Set a functor, and let us call a morphism f in C “one-to-one” if U(f) is a one-to-one set map, and emphasize this by indicating such morphisms using tailed arrows: ↣ .

Assume that C admits pushouts of pairs of one-to-one morphisms; i.e., that if f : S ↣ A and g : S ↣ B are one-to-one, then the coproduct with amalgamation A ∐_{S} B exists. (But we do not assume at this point that the maps of S, A and B to that coproduct are one-to-one.)

Then the following three conditions are equivalent:

(20)

C has the amalgamation property ([10, p.82]). That is, given objects A, B, C of C, and oneto-one morphisms f : A ↣ B, g : A ↣ C, there exists an object D, and one-to-one morphisms f′ : B ↣ D, g′ : C ↣ D, such that f′f = g′ g.

(21)

For all objects S, T, A, B and one-to-one morphisms S ↣ T, S ↣ A, and f : A ↣ B in C,

the induced morphism f ∐_{S}T : A ∐_{S} T → B ∐_{S} T is one-to-one.

(22)

For all objects S, positive integers n, and finite families of objects and one-to-one morphisms S ↣ A_{i} and f_{i} : A_{i} ↣ B_{i} in C (i=1, …, n), the induced morphism ∐_{S}^{i=1,...,n} f_{i} : ∐_{S}^{i=1,...,n} A_{i} → ∐_{S}^{i=1,...,n} B_{i} is one-to-one.

Moreover, if C also admits direct limits (colimits over directed partially ordered sets), and if U respects these (e.g., if C is a quasivariety of finitary algebras, and U its underlying set functor), then C has coproducts with amalgamation of possibly infinite families of one-to-one maps S ↣ A_{i} (for fixed S, and i ranging over a possibly infinite set I); and (22) goes over to such coproducts. That is, (20)-(22) are also equivalent to:

(23)

For all objects S, nonempty sets I, and families of objects and one-to-one morphisms S ↣ A_{i} and f_{i} : A_{i} ↣ B_{i} in C (i ∈ I), the induced morphism ∐_{S}^{i∈I} f_{i} : ∐_{S}^{i∈I} A_{i} → ∐_{S}^{i∈I} B_{i} is one-to-one.

Proof. (20) ⇒ (21): Given objects and maps as in (21), the amalgamation property implies, as mentioned above, that the coprojection A → A ∐_{S} T is one-to-one. From this and the assumed one-to-one-ness of the map A → B we similarly get one-to-one-ness of the coprojection A ∐_{S}T → B ∐_{A}(A ∐_{S}T) = B ∐_{S}T, as desired.

(21) ⇒ (20): Given objects and maps as in (20), apply (21) with A and its identity map in the role of S and its map to A, and with C in the role of T, noting that the domain of the resulting map, A ∐_{A}C, can be identified with C. This gives one-one-ness of the coprojection C → B ∐_{A} C. By symmetry one also has one-one-ness of the coprojection B → B ∐_{A} C. Taking D = B ∐_{A}C, we get (20).

(21) ⇒ (22): The case n = 1 of (22) is trivial. To get the case n = 2 we make a double application of (21), first getting one-one-ness for f_{1} ∐_{S} A_{2} : A_{1} ∐_{S} A_{2} ↣ B_{1} ∐_{S} A_{2} and then for B_{1} ∐_{S} f_{2} : B_{1} ∐_{S} A_{2} ↣ B_{1} ∐_{S} B_{2}. Composing, we get one-one-ness of the desired map.

This shows that two-fold coproducts over S respect one-to-one-ness of maps among objects having oneto-one maps of S into them. Induction now gives the corresponding result for n-fold coproducts.

(22) ⇒ (21): Given objects and maps as in (21), apply the n = 2 case of (22) with A ↣ B in the role of f_{1} : A_{1} ↣ B_{1} and the identity map of C in the role of f_{2} : A_{2} ↣ B_{2}.

Under the additional assumptions about direct limits, one notes that for infinite I, one can obtain ∐_{S}^{i∈I} A_{i} as the direct limit, over the directed system of all finite subsets I_{0} ⊆ I, of the objects ∐_{S}^{i∈I_{0}} A_{i}. Since by (22), the indicated maps among these finite coproducts are one-to-one, and by assumption direct limits respect U (and hence one-one-ness), the corresponding maps among the coproducts over I are also one-to-one. The converse is immediate: (23) includes (22). □

Let us now note how the amalgamation property implies conditions on independent subalgebras stronger than those of §4. In considering categories of algebras, we shall understand the functor U of Lemma 17 to be the underlying set functor. Thus, “one-to-one”, in our formulation (20) of the amalgamation property and our statements of conditions equivalent thereto, has its usual meaning for algebras.

Corollary 18. Suppose that P is a prevariety having the amalgamation property, that A is a P-algebra, that (B_{i})_{i∈I} is a finite P-independent family of subalgebras of A, and that for each i ∈ I, (C_{ij})_{j∈J_{i}} is a finite P-independent family of subalgebras of B_{i}. Then (C_{ij})_{i∈I, j∈J_{i}} is a P-independent family of subalgebras of A. (In particular, in such a prevariety, examples like those of Propositions 1 and 2 cannot occur.)

If P is in fact a quasivariety having the amalgamation property, then the above result holds without the finiteness restrictions on I and the J_{i}.

Proof. Since all the algebras named are subalgebras of A, the unique homomorphic image of the initial algebra of P in all of them is the same; let us call this S. Because S is a homomorphic image of the initial algebra of our category, the operator ∐_{S} on nonempty families of algebras containing S is just ∐_{P} .

We now apply the implication (20) ⇒ (22) of Lemma 17 (or if P is a quasivariety, the stronger implication (20) ⇒ (23)), taking for the S of (22) and (23) the S of the preceding paragraph, and for the maps A_{i} ↣ B_{i} the inclusions ∐_{P}^{j∈J_{i}} C_{ij} ⊆ B_{i}. We conclude that the natural map from ∐_{P}^{i∈I}(∐_{P}^{j∈J_{i}} C_{ij}) = ∐_{P}^{i∈I, j∈J_{i}} C_{ij} to ∐_{P}^{I} B_{i} is one-to-one. Identifying the latter algebra with its embedded image in A, we get the desired conclusion.

To get the parenthetical remark about examples like those of Propositions 1 and 2, we take I = {0, 1}, J_{0} = {0}, J_{1} = {0, 1}, and let A, the B_{i} and the C_{ij} all be free of rank 1. □

Remarks: Lemma 17 was a compromise between proving the minimum we needed to get the above corollary – that (20) implies the special case of (22) where S is the image of the initial object of C in A, and so can be ignored in forming coproducts (and if C has, and U respects, direct limits, the corresponding case of (23)) – and digressing to state and prove a more complete statement. That statement would involve the versions of conditions (20) and (22) for κ-fold families for any cardinal κ, would establish the equivalence between those two conditions for each such κ, would note that the statements for larger κ imply those for smaller κ, and would verify that the statements for finite κ ≥ 2 are all equivalent, and also equivalent to (21). The reader should not find it hard to work out the details.

The reason we brought S into (22), though the only case of (22) that our application needed was where S was a homomorphic image of the initial object and so had no effect, was so as to get an if-and-only-if relation between (22) and (20), the amalgamation property. (The latter is a well-known property, satisfied by the categories of groups, semilattices, lattices, and commutative integral domains, and many others. See the first column of the table in [10, pp.98-107] for more results, positive and negative.) That equivalence fails if S in (22) is restricted to homomorphic images of the initial object. For instance, the normal form for coproducts of monoids shows that the variety Monoid satisfies the cases of (21)-(23) where S is the initial (trivial) monoid. However Monoid does not satisfy the amalgamation property (20); e.g., letting A = ⟨x⟩, the free monoid on one generator, and letting B and C be the overmonoids of A gotten by adjoining a left inverse y, respectively a right inverse z, to x, one finds that in B ∐_{A}C, the elements xy of B and zx of C fall together with 1; so the maps from B and C to this algebra are not one-to-one. On the other hand, because the special case of (21)-(23) which we have seen suffices for Corollary 18 holds, Monoid does satisfy the conclusion of that corollary.

Here is another result (alluded to in the discussion following Lemma 11) of a sort similar to the above, which for simplicity of wording we will again state in terms of the amalgamation property, though again, only the cases of (21)-(23) where S is a homomorphic image of the initial object of P are needed.

Corollary 19. Suppose P is a prevariety having the amalgamation property, and A a P-algebra. Then every nonempty subfamily of a P-independent family of subalgebras of A is P-independent.

Proof. Given a P-independent family of subalgebras B_{i} (i ∈ I) of A, their P-independence says that the subalgebra of A that they generate is isomorphic to their coproduct, which we see coincides with their coproduct over the common image S in all these algebras of the initial algebra of P. For any nonempty subset J ⊆ I, the coproduct of the B_{i} for i ∈ J likewise coincides with their coproduct over S. We now apply (21) with this algebra S for both the S and A of that condition, with ∐_{S}^{J} B_{i} for T, and with ∐_{S}^{I−J} B_{i} for B, and then bring in the assumed P-independence of the whole family. We thus get one-one-ness of the natural maps shown by the first arrow in

(24) ∐_{P}^{J} B_{i} ≅ ∐_{S}^{J} B_{i} ↣ ∐_{S}^{J} B_{i} ∐_{S} ∐_{S}^{I−J} B_{i} ≅ ∐_{S}^{I} B_{i} ≅ ∐_{P}^{I} B_{i} ↣ A,

and the above arrows and isomorphisms compose to the map we wished to show one-to-one. □

7. P-compatible algebras.

The prevarieties considered in §4 were each generated by a single algebra. Although any variety of algebras can be generated as a variety by a single algebra (namely, by a free algebra on sufficiently many generators), prevarieties generated as prevarieties by a single algebra are rather special. This was shown by Mal’cev for quasivarieties, in a result that we will generalize in the next section. In this section we shall see that the size of the collection of algebras needed to generate P as a prevariety is a nontrivial and interesting invariant of P, even if P happens to be a variety.

Definition 20. Let P be a prevariety. Then a set X of P-algebras will be called P-compatible if for every A_{0} ∈ X, the coprojection map A_{0} → ∐_{P}^{A∈X} A is one-to-one; equivalently, if there exists an algebra B in P admitting one-to-one homomorphisms A → B for all A ∈ X.

Theorem 21. Suppose P is a prevariety that is residually small (i.e., that can be generated as a prevariety by a set of algebras) and κ is a cardinal. Then condition (25) below implies condition (26); and if P is a quasivariety (in which case, we recall, our algebras are assumed finitary), the two conditions are equivalent.

(25) P can be generated, as a prevariety, by a set of ≤ κ algebras.

(26)

Every set X of subdirectly irreducible algebras in P can be written as the union of ≤ κ subsets X_{α} (α ∈ κ), each of which is P-compatible.

Proof. (25) ⇒ (26): Suppose P is generated by a set of ≤ κ algebras, Y = {B_{α} | α ∈ κ}, and that as in (26), X is a set of subdirectly irreducible algebras in P. Each A ∈ X is embeddable in a direct product of copies of the B_{α}, hence, being subdirectly irreducible, in one of the B_{α}. Letting X_{α} be the set of members of X embeddable in B_{α}, we get the conclusion of (26) (using the second formulation in the definition of P-compatibility).

To prove that when P is a quasivariety, (26) ⇒ (25), note that by our residual smallness hypothesis, there is a set X of subdirectly irreducible algebras in P which contains, up to isomorphism, all such algebras. By (26) we may write X = ⋃_{α∈κ} X_{α} where each X_{α} is P-compatible. Hence for each α, we can choose an algebra A_{α} in P in which all members of X_{α} can be embedded. Since a quasivariety is generated as a prevariety by its subdirectly irreducible algebras [9, Theorem 3.1.1], the prevariety generated by {A_{α} | α ∈ κ} is all of P. □

To get easy examples showing that the least κ for which (26) holds can be, inter alia, any natural number, consider algebras with just a single unary operation a, and for each positive integer d, let C_{d} be the algebra of this type consisting of d elements, x, ax, …, a^{d−1}x, cyclically permuted by a.

Now let n be any natural number, and d_{1}, , …, d_{n} be positive integers none of which is the least common multiple of any subset of the others. (In particular, none of them is 1, since 1 is the least common multiple of the empty set.) Let P be the prevariety generated by the n algebras C_{d_{1}}, …, C_{d_{n}}. Since this is generated by finitely many finite finitary algebras, it is a quasivariety. From the description P = 𝕊 ℙ {C_{d_{1}}, …, C_{d_{n}}} we see that all algebras in P satisfy

(27) (∀ x) a^{lcm(d_{1},...,d_{n})}x = x,
(28) (∀ x, y, z) ax = x ⟹ y = z,

(29)

For all x, the least positive integer d such that a^{d}x = x is the least common multiple of some subset of {d_{1}, …, d_{n}},

(30) (∀ x, y) a^{d}x = x ⟹ a^{d}y = y.

From (27)-(30) and our assumption that none of the d_{i} is the least common multiple of a subset of the rest, one can verify that the subdirectly irreducible objects of P are precisely the n algebras C_{d_{i}}; and by (30) these are pairwise incompatible; so for this quasivariety, the least κ as in Theorem 21 is n.

For d_{1}, …, d_{n} as above, consider next, for contrast, the quasivariety P generated by a single algebra, the disjoint union C_{d_{1}} ⊔ … ⊔ C_{d_{n}}. This will still satisfy (27), (28) and (29), but not (30). The algebras C_{d_{1}}, …, C_{d_{n}} will still be subdirectly irreducible in P, but they are no longer incompatible. Indeed, since P is generated by a single algebra, the least cardinal κ as in Theorem 21 is now 1.

For an intermediate case, given d_{1}, d_{2}, d_{3} as above, let P be generated by the three disjoint unions C_{d_{1}} ⊔ C_{d_{2}}, C_{d_{1}} ⊔ C_{d_{3}} and C_{d_{2}} ⊔ C_{d_{3}}. Since none of these generating algebras contains copies of all three C_{d_{i}}, these algebras, and hence all algebras in P, satisfy the implication

(31) (∀ x_{1}, x_{2}, x_{3}, y, z) (a^{d_{1}}x_{1} = x_{1}) ∧ (a^{d_{2}}x_{2} = x_{2}) ∧ (a^{d_{3}}x_{3} = x_{3}) ⟹ y = z.

Hence, though any two of C_{d_{1}}, C_{d_{2}} and C_{d_{3}} are P-compatible, the set consisting of all three is not.

If we take an infinite sequence of integers d_{1}, d_{2}, …, none of which divides any of the others (for instance, the primes), and let P be the prevariety generated by all finite disjoint unions of the C_{d_{i}}, this will no longer be a quasivariety. For it will satisfy the sentence

(32) (∀ x_{1}, …, x_{n}, …; y; z) ( ⋀_{i=1}^{∞} a^{d_{i}}x_{i} = x_{i}) ⟹ y = z,

so the direct limit, as sets with one unary operation, of the above generating family of finite unions of C_{i} (mapped into one another by inclusion) does not lie in P; their direct limit in P is, by (32), the trivial (one-element) algebra. This example also shows that in our earlier result, Lemma 17, the added direct limit hypothesis was indeed needed to get from (20)-(22) to (23). For it is easy to see that P satisfies (20), while to see that it does not satisfy (23), we may take for S and the A_{i} the empty algebra, and for the B_{i} the above algebras C_{d_{i}}.

To see that the implication (26) ⇒ (25) of Theorem 21, which we proved for quasivarieties, does not hold for general prevarieties, let us construct a prevariety not having “enough” subdirectly irreducible algebras: Let p be a prime, let G be the additive group of an infinite-dimensional vector space over the field of p elements, and let P be the prevariety consisting of all G-sets A such that if an element of A is fixed by an element of G, then all elements of A are fixed by that element, and if an element of A is fixed by infinitely many elements of G, then all elements of A are equal. Then P is residually small: the set of G-sets G/H for all finite subgroups H ⊂ G generates P. But any finite-dimensional subspace of G is an intersection of two properly larger finite dimensional subspaces, hence any nontrivial algebra in P can be decomposed as a subdirect product of algebras with larger pointwise stabilizers; so P has no subdirectly irreducible algebras, so it satisfies (26) for κ = 0. On the other hand, no two nonempty algebras in P having different pointwise stabilizers are compatible, so (25) does not hold for any finite κ.

8. All under one roof: prevarieties where all algebras are P-compatible.

For prevarieties that can be generated by one algebra, a stronger result can be proved than the κ = 1 case of (26); moreover, we can weaken the above assumption “generated by one algebra” to a condition that is necessary as well as sufficient for our strengthened conclusion.

We need the following definition. (Recall that a preordering ⪯ on a set or class means a reflexive, transitive, but not necessarily antisymmetric binary relation.)

Definition 22. A preordered class (K, ⪯) will be called absolutely directed if every set of elements of K is majorized by some element of K.

In particular, a preordered set is absolutely directed if and only if it has a greatest element (an element ⪰ all elements).

In the next result, condition (33) can be seen to be a strengthening of the κ = 1 case of (26) (with “nontrivial” replacing “subdirectly irreducible”), while (34) is a weakening of the condition that P be generated as a prevariety by a single algebra. The equivalence of (35) and (37) for quasivarieties is due to Mal’cev.

By the trivial algebra we will always mean the one-element algebra. (So trivial algebras and empty algebras are never the same thing.)

Theorem 23 (cf. Mal’cev [13], [9, Proposition 2.1.19]). Let P be a prevariety, and let ⪯ be the preordering “is embeddable in” among algebras in P. Then the following conditions are equivalent.

(33) Every set of nontrivial algebras in P is P-compatible.
(34) P is generated as a prevariety by a class of algebras absolutely directed under ⪯ .

Moreover, if P is a quasivariety (so that, again, our algebras are assumed finitary), then the above conditions are also equivalent to each of

(35) Every pair of nontrivial algebras in P is P-compatible.
(36) P is generated as a quasivariety by a class of algebras absolutely directed under ⪯ .
(37) P is generated as a quasivariety by a single algebra.

Proof. (33) says that the class of nontrivial algebras in P is absolutely directed under ⪯ . But P is generated as a prevariety by its nontrivial algebras (the trivial algebra being the direct product of the empty family thereof), so this implies (34).

To show (34) ⇒ (33), let X be an absolutely directed class of algebras generating P, and Y any set of nontrivial algebras in P. Since Y is a set, we can find a set X_{0} ⊆ X, homomorphisms into members of which separate points of algebras in Y, and by the absolute directedness of X, some one algebra A ∈ X contains embedded images of all members of X_{0}; hence homomorphisms into A separate points of algebras in Y. Hence if we form a direct product A^{I} of sufficiently many copies of A, then for each nonempty B ∈ Y, we can use maps to some coordinates of A^{I} to separate points of B; and since B is nontrivial and nonempty, the set of maps so used will be nonempty, and we can repeat some of them to fill in the remaining coordinates if any; thus we can embed B in A^{I}. The same conclusion is vacuously true if B is empty, so A^{I} has subalgebras isomorphic to all B ∈ Y, proving that Y is P-compatible.

Now let P be a quasivariety.

Clearly, (33) ⇒ (35). The converse holds because we can go from pairwise coproducts to finite coproducts by induction, while coproducts of infinite families are direct limits of coproducts of finite families, and in a quasivariety, direct limits respect the underlying set functor. Thus, (33)-(35) are equivalent.

(34) ⇒ (36) is trivial, since the quasivariety generated by a class of algebras contains the prevariety generated by the same class. We shall now show (36) ⇒ (37), then note two alternative ways of getting back from (37): to (34), or to (35).

Given (36), let X be an absolutely directed class of algebras generating P as a quasivariety. Since the finite sentences (12) form (modulo notation) a set, if we choose for each such sentence not satisfied by P a member of X for which it fails, we get a set of algebras X_{0} ⊆ X which again generates P. By assumption, X_{0} is majorized by an algebra A ∈ X, and this will likewise generate P, proving (37).

Now assume (37), and let A be an algebra that generates P as a quasivariety.

On the one hand, one can deduce (34) from the fact that P is generated as a prevariety by the class of ultrapowers of A ([9, Corollary 2.3.4(i)]; cf. last paragraph of Definition 5 above) by verifying that that class is absolutely directed under ⪯ . The idea is that given a set of ultrafilters U_{j} (j ∈ J), each on a set I_{j}, these yield a “product” filter on ∏^{J} I_{j}, and any ultrafilter U containing this will have the property that all the ultrapowers A^{U_{j}} embed in the ultrapower A^{U}.

To get (35), on the other hand, suppose by way of contradiction that B_{0} and B_{1} were a non-P-compatible pair of nontrivial algebras in P. Without loss of generality, suppose B_{0}, has non-one-to-one coprojection into B_{0} ∐_{P} B_{1}; let elements x ≠ y of B_{0} fall together there. Since P is determined by finite sentences (12), the conjunction of finitely many of these universal sentences with finitely many equations holding among finitely many elements of B_{0} and B_{1} must imply x = y. But every finite system of relations among elements of each of the B_{i} is realizable by relations among some family of elements of A (otherwise A, and hence P, would satisfy an implication (12) saying that the conjunction of such a system of relations implies that all elements are equal, contradicting our assumption that the B_{i} are nontrivial). On the other hand, since P does not satisfy an implication forcing x = y to hold in B_{0}, the above equations involving elements of B_{0} must be satisfiable by a family of elements of A with distinct elements representing x and y. But combining this family with the family of elements of A chosen above to satisfy our finitely many relations holding in B_{1}, we see that the sentences (12) defining P imply that those two elements are equal, giving the required contradiction. □

In the above theorem we had to exclude the trivial algebra from certain statements. The following addendum to that theorem shows that in many prevarieties, not only is that restriction unnecessary, but trivial algebras can be used in formulating a very simple criterion, (39), for the equivalent conditions of the theorem to hold.

Corollary 24. In the context of Theorem 23, suppose that

(38) P has at least one nontrivial algebra with a trivial subalgebra

(i.e., a nontrivial algebra with an element idempotent under all the algebra operations).

Then (33)-(34), and, if P is a quasivariety, (35)-(37) are equivalent to the condition obtained by deleting the word “nontrivial” from (35); and also to

(39) Every algebra in P is P-compatible with the trivial algebra.

Proof. It is easy to deduce from (38) that each of (33) and (35) is equivalent to the formally strengthened version of itself gotten by deleting the restriction “nontrivial”: given a set X of algebras (respectively, a pair of algebras) of P including the trivial algebra, which we want to embed simultaneously in some algebra, we “sneak the trivial member of our set in” by hiding it in a nontrivial algebra as in (38), then apply (33) (respectively, (35)) to the resulting family of nontrivial algebras. As a special case of this version of either condition, we have (39).

On the other hand, given (39), we can get the strengthened form of (33) by a version of the construction by which one embeds a family of groups in their direct product group. Let {B_{i} | i ∈ I} be any set of algebras in P. By (39), embed each B_{i} in an algebra A_{i} containing an idempotent element e_{i}. Taking A = ∏^{I} A_{i}, we can embed each B_{j} in A by using the inclusion map at the j-th component, and mapping to every other component by collapsing everything to a trivial subalgebra. □

Clearly every prevariety of groups, monoids, or lattices satisfies (39), hence satisfies (33) with the nontriviality condition deleted, (34), and, if it is a quasivariety, (35)-(37).

On the other hand, the variety V of unital associative (or unital associative commutative) algebras over any field satisfies (33) (and hence (34)-(37)), by the standard description of coproducts of such algebras, but not (38) or the version of (33) with “nontrivial” deleted; rather, the trivial algebra in V (where 1 = 0) is not V-compatible with any other algebra. Hence in the absence of (38), the exclusion of the trivial algebra in (33) and (35) is indeed needed to make Theorem 23 hold. Our constructions in the preceding section with unary algebras also illustrate this: in the prevariety generated by a single algebra C_{d} (d > 1), the conditions of Theorem 23 hold, but C_{d} satisfies (∀ x, y, z) ax = x ⟹ y = z, so the trivial algebra is not P-compatible with any nontrivial algebra.

There are also examples where (38) holds, but where the equivalent conditions of Theorem 23 and Corollary 24 do not; for example, the variety of groups or monoids with one distinguished element, or of lattices with two distinguished elements: a counterexample to (39) is given by any group or monoid with distinguished element that is not the identity, or any lattice with a pair of distinguished elements that are not equal.

These same examples also show that the analog of the implication (37) ⟹ (33) does not hold for varieties, with “generated as a variety” in place of “generated as a quasivariety”, since every variety satisfies the analog of (37).

The next corollary is a result promised in the comment following Lemma 11.

Corollary 25. Suppose P is a prevariety generated by a single algebra, or, more generally, satisfying (34), and let (B_{i})_{i∈I} be a family of nontrivial algebras in P. (Again, if P satisfies (38), the restriction “nontrivial” can be dropped.) Then

(40) For every J ⊆ I, the natural map ∐_{P}^{i∈J} B_{i} → ∐_{P}^{i∈I} B_{i} is one-to-one.

Hence

(41)

Any subfamily of a P-independent family of subalgebras of a nontrivial algebra A is P-independent.

Proof. To see (40), note that ∐_{P}^{i∈I} B_{i} ≅ (∐_{P}^{i∈J} B_{i}) ∐_{P} (∐_{P}^{i∈I−J} B_{i}), with the natural map ∐_{P}^{i∈J} B_{i} → ∐_{P}^{i∈I} B_{i} corresponding to the first coprojection under this decomposition. By the implication (34) ⇒ (33) (or its modified version if P satisfies (38)), the indicated coproducts over J and I − J are P-compatible, hence that coprojection map is one-to-one, as claimed. (A slight hiccup in this argument: If J or I − J is empty, can we be sure the coproduct over that subset, namely the initial algebra, is nontrivial? No, but if it is trivial, and if P is not the trivial prevariety, then since the initial algebra can be mapped into every algebra, (38) holds, and so we are in the case where we don’t need nontriviality.)

To get (41), recall that the statement that (B_{i})_{i∈I} is an independent family of subalgebras of A means that the subalgebra of A generated by these subalgebras can be identified with their coproduct. If none of the B_{i} is trivial, then this observation together with (40) immediately gives the desired conclusion. If at least one of the B_{i} is trivial, then since by assumption A is not, (38) holds, and by the parenthetical addendum to the first part of this corollary, we again have (40) and can proceed as before. □

On a different topic, let us note the extent to which Theorem 21 does and does not go over from prevarieties to quasivarieties.

Corollary 26. If P is a quasivariety, then (even without the residual smallness assumption of Theorem 21), condition (26) implies

(42) P can be generated as a quasivariety by ≤ κ algebras.

The reverse implication holds if κ is finite, but not for any infinite κ.

Proof. (26) ⇒ (42): A quasivariety P is generated as a prevariety, and hence as a quasivariety, by its subdirectly irreducible algebras [9, Theorem 3.1.1], hence, as in the proof of Theorem 23, we can find a set X of these that generates it as a quasivariety. By (26) we can write X as ⋃_{α∈κ} X_{α} where each X_{α} is P-compatible. If for each α ∈ κ we let A_{α} be an algebra in P containing embedded images of all members of X_{α}, then P is generated as a quasivariety by this set of κ algebras.

For the converse assertion when κ is a natural number n, let P be generated as a quasivariety by A_{1}, …, A_{n}. Then P = 𝕊 ℙ ℙ_{ult}{A_{1}, …, A_{n}}, where ℙ_{ult} denotes closure under ultraproducts; thus, each Psubdirectly irreducible object of P is embeddable in a member of ℙ_{ult}{A_{1}, …, A_{n}}. Moreover, the operator ℙ_{ult} respects finite decompositions; that is, any ultraproduct of a family of structures indexed by a finite union of sets, (A_{i})_{i∈I_{1}∪···∪I_{n}}, can be written as an ultraproduct of one of the subfamilies (A_{i})_{i∈I_{m}}. Hence ℙ_{ult}{A_{1}, …, A_{n}} = ℙ_{ult}{A_{1}} ∪ ⋯ ∪ ℙ_{ult}{A_{n}}. The class of subdirectly irreducible algebras in P that are embeddable in members of a given ℙ_{ult}{A_{i}} is contained in the 1-generator quasivariety 𝕊 ℙ ℙ_{ult}{A_{i}}, hence by the implication (37) ⇒ (33), each of these n classes has the property that all its subsets are P-compatible. This gives (26).

On the other hand, given any infinite κ, let V be the variety of sets given with a κ-tuple of zeroary operations (constants) c_{α} (α ∈ κ). Since as a quasivariety, V is generated by its finitely presented objects [9, Proposition 2.1.18], and there are only κ of these, it satisfies (42). On the other hand, since all operations are zeroary, every equivalence relation on a V-algebra is a congruence, so the subdirectly irreducible algebras are precisely the 2-element algebras. We have one of these for each 2-class equivalence relation on κ, and one more corresponding to the partition of that set into κ and ∅. This gives 2^{κ} subdirectly irreducible algebras, no two of which are V-compatible. □

9. Afterthoughts on P-compatible algebras.

Perhaps the concept of “ P-compatible algebras” is not the best handle on the phenomena we have been examining; or at least should be complemented by another way of looking at them. Suppose that for algebras A and B in P, we say that A is “comfortable” with B in P if the coprojection A → A ∐_{P} B is one-to-one; equivalently, if A is P-compatible with some homomorphic image of B in P. This relation is not in general symmetric; e.g., in the variety of associative unital rings, each ring ℤ/nℤ is comfortable with ℤ, but not vice versa. Algebras A and B are P-compatible if and only if each is comfortable with the other. (So the relations of P-compatibility and of being comfortable in P may be characterized in terms of one another.) More generally, an arbitrary family of algebras is P-compatible if and only if each is comfortable with the coproduct of the others.

If P is generated as a prevariety by a class of algebras X, we see that an algebra A is comfortable in P with an algebra B if and only if homomorphisms into members of X that contain homomorphic images of B separate points of A. Hence, if we classify algebras B ∈ P according to which algebras A are comfortable with them, then algebras B_{1} and B_{2} will belong to the same equivalence class under this relation if the subclass of X consisting of algebras containing homomorphic images of B_{1} coincides with the subclass of those containing images of B_{2}. (We do not assert the converse.) In particular, if P is residually small, so that X can be taken to be a set, the number of these equivalence classes has the cardinality of a set. More generally, if P is generated by the union of κ classes of algebras, each absolutely directed under the relation ⪯ of Theorem 23, the same reasoning shows that it will have at most 2^{κ} equivalence classes under this equivalence relation. On the other hand, if we classify algebras according to which other algebras they are comfortable with, we may, so far as I can see, get up to 2^{2^{κ}} classes.

For any algebra A in P, the class of algebras which are comfortable with A forms a subprevariety of P. The class of algebras that A is comfortable with likewise yields a subprevariety on throwing in the trivial algebra. (A stronger statement, also easy to see, is that this class is closed under taking subalgebras and under taking products with arbitrary algebras in P; equivalently, that if this class contains an algebra B, then it contains every algebra in P admitting a homomorphism to B.)

10. On infinite symmetric groups: an answer and a question.

This last section does not depend on any of the preceding material.

It was shown in [3] (cf. [2]) that for Ω an infinite set, the group S = Sym(Ω) of all permutations of Ω contains a coproduct of two copies of itself (from which it was deduced by other properties of that group that it contains a coproduct of 2^{card(Ω)} copies of itself). In [2, Question 4.4], I asked, inter alia, whether, for every subgroup B of S, if we regard S as a member of the variety of groups given with homomorphisms of B into them, S contains a coproduct of two copies of itself in that variety.

The answer is negative. To see this, pick any x ∈ Ω and let B be the stabilizer in S of x. Writing elements of S to the left of their arguments and composing them accordingly, we see that the partition of S into left cosets of B classifies elements according to where they send x, and that for each y ∈ Ω, the coset sending x to y has elements of finite order; e.g., if y ≠ x, the 2-cycle interchanging x and y.

On the other hand, I claim that if S_{1} and S_{2} are any two groups with a common subgroup B proper in each, then in the coproduct with amalgamation S_{1} ∐_{B} S_{2} there are left cosets of B containing no elements of finite order. Indeed, the standard normal form in that coproduct shows that each left coset is generated by a possibly empty alternating string of left coset representatives of B in S_{1} and S_{2}. When that string is nonempty and has even length, one sees that elements of finite order cannot occur. Hence for S = Sym(Ω) and B as above, S, as a group containing B, cannot contain a copy of S_{1} ∐_{B} S_{2}.

So let us modify our earlier question.

Question 27. For Ω an infinite set, what nice conditions, if any, on a subgroup B ⊆ S = Sym(Ω) will imply that S has a subgroup containing B and isomorphic over B to S ∐_{B} S?

For instance, will this hold if B is equal to, or contained in, the stabilizer of a subset of Ω having the same cardinality as Ω ? If B is finite?

In that same question in [2], I asked whether for any submonoid B of the monoid Self(Ω) of self-maps of Ω, the monoid Self(Ω) must contain, over B, a coproduct of two copies of itself with amalgamation of B. It seems likely that the subgroup B ⊂ Sym(Ω) ⊂ Self(Ω) used above also gives a counterexample to this part of the question. This will be so if we can show that the subgroup of invertible elements of the monoid coproduct of two copies of Self(Ω) with amalgamation of B is isomorphic to the group coproduct of two copies of Sym(Ω) with amalgamation of B, since we have seen that this is not embeddable over B in the group Sym(Ω) of invertible elements of Self(Ω). But the analysis of coproducts of monoids with amalgamation, even when the submonoid being amalgamated is a group, seems difficult.

The final part of that question posed the same problem for the endomorphism algebra of an infinitedimensional vector space over a field. To this I also do not know the answer; and in view of the results of [17], it is natural to ask the same question for lattices of equivalence relations on an infinite set.

11. Glossary for the non-expert in universal algebra.

I indicate below the meanings of some basic concepts of universal algebra, though more briefly and informally than would be done in a textbook presentation. (Definitions of some other concepts are recalled in the sections where they are used. I do not define concepts of category theory, such as coproduct; or of set theory, such as ultraproduct, and the distinction between sets and proper classes. For these, see standard references such as [12], [5].)

An n-ary operation on a set X means a function X^{n} → X; here n is called the arity of the operation. An algebra is a set given with a family of operations of specified arities. The list of operation-symbols and their arities is the type of the algebra (used here only in the phrase “algebras of the same type”). Constants in the definition of an algebra structure (e.g., the 0 and 1 of a ring structure) are in this note regarded as zeroary operations; indeed, X^{0} is a 1-element set, so a map X^{0} → X specifies an element of X. Given a subset S of an algebra X, the subalgebra of X generated by S is here denoted ⟨S⟩.

The given operations of an algebra are called primitive operations. Expressions in a family of variablesymbols and iterated applications of the primitive operations determine derived operations. Such expressions are themselves called terms. For instance, (x y) z and x (y z) are distinct ternary terms in the operations of a group. (They must be considered distinct so that they can be used to write the group identity of associativity.) The variable-symbols are also considered terms; they are the starting-point for the recursive construction of all terms. This technical sense of “term” will not stop us from using the word in other ways, e.g., in referring to the m-th term of a sequence.

An algebra all of whose primitive operations have finite arity is called finitary. (This does not preclude there being infinitely many primitive operations; e.g., we have this for modules over an infinite ring.)

As indicated in §1, a variety of algebras is the class of all algebras of a given type satisfying a given set of identities. In any variety V, one can construct a free algebra on any set, satisfying the usual universal property.

The above concepts are assumed from §2 on. Starting with §3, we also refer to the variety of algebras generated by a family X of algebras of a given type, i.e., the least variety containing X. This is clearly the class of all algebras that satisfy all identities satisfied by all members of X. Birkhoff’s Theorem states that it is also the class of all homomorphic images of subalgebras of (generally infinite) direct products of members of X, abbreviated ℍ 𝕊 ℙ (X). (Definitions of prevariety and quasivariety, and results for these analogous to Birkhoff’s Theorem, are recalled in §3.)

To motivate a concept used from §7 on, note that if an algebra A is embedded in a direct product ∏_{I} A_{i}, by a homomorphism with components f_{i} : A → A_{i}, then A ≅ f(A) ⊆ ∏_{I} f_{i}(A). Modeled on the properties of this subalgebra, one defines a subdirect product of a family of algebras (B_{i})_{i∈I} to be a subalgebra of ∏_{I} B_{i} which projects surjectively to each B_{i}. An algebra that, up to isomorphism, cannot be so expressed without one of the projection maps being an isomorphism is called subdirectly irreducible.

References

[1] Jiří Adámek and Lurdes Sousa, On reflective subcategories of varieties, J. Algebra 276 (2004) 685–705. MR 2005c:18003.

[2] George M. Bergman, Some results on embeddings of algebras, after de Bruijn and McKenzie, Indag. Math. 18 (2007) 349–403. MR 2008m:08016.

[3] N. G. de Bruijn, Embedding theorems for infinite groups, Nederl. Akad. Wetensch. Proc. Ser. A. 60 = Indag. Math. 19 (1957) 560–569. MR 20#4589. (In addition to the correction to this paper made in [4], the result quoted at p.561, 6th paragraph should exclude the countable case, and the result quoted at p.566, 3rd from last paragraph, should include, when n = ℵ_{0}, the case of the infinite alternating group.)

[4] N. G. de Bruijn, Addendum to “Embedding theorems for infinite groups”, Nederl. Akad. Wetensch. Proc. Ser. A 67 = Indag. Math. 26 (1964) 594–595. MR 30#142.

[5] C. C. Chang and H. J. Keisler, Model Theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, v.73. North-Holland, 1990. MR 91c:03026.

[6] David M. Clark, Varieties with isomorphic free algebras, Colloq. Math. 20 (1969) 181–187. MR 39#5445.

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

[8] P. M. Cohn, Some remarks on the invariant basis property, Topology 5 (1966) 215–228. MR 33#5676.

[9] Viktor A. Gorbunov, Algebraic theory of quasivarieties, Consultants Bureau, 1998. MR 2001a:08004.

[10] E. W. Kiss, L. Márki, P. Pröhle and W. Tholen, Categorical algebraic properties. A compendium on amalgamation, congruence extension, epimorphisms, residual smallness, and injectivity, Studia Sci. Math. Hungar. 18 (1982) 79– 140. MR 85k:18003.

[11] L. G. Kovács and M. F. Newman, Hanna Neumann’s problems on varieties of groups, pp. 417–431 in Proceedings of the Second International Conference on the Theory of Groups (Australian Nat. Univ., Canberra, 1973 ), SLNM, v. 372, Springer, 1974. MR 50#4750.

[12] Saunders Mac Lane, Categories for the Working Mathematician, Springer GTM, v.5, 1971. MR 50#7275.

[13] A. I. Mal’cev, Several remarks on quasivarieties of algebraic systems (Russian), Algebra i Logika Sem. 5 (1966) 3– 9. MR 34#5728.

[14] Ralph N. McKenzie, George F. McNulty and Walter F. Taylor, Algebras, Lattices, Varieties. Vol. I, Wadsworth & Brooks/Cole, 1987. MR 88e:08001.

[15] Hanna Neumann, Varieties of groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer, 1967. MR 35#6734.

[16] S. Świerczkowski, On isomorphic free algebras, Fund. Math. 50 (1961/1962) 35–44. MR 25#2017.

[17] Friedrich Wehrung, Embedding coproducts of partition lattices, Acta Sci. Math. (Szeged) 73 (2007) 429–443. MR 2008m:06011.

[18] M. V. Zaĭtsev, Embeddability of relatively free Lie algebras (Russian), Uspekhi Mat. Nauk 47 (1992) 191–192; translation in Russian Math. Surveys 47 (1992) 236–237. MR 94c:17013.

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

E-mail address: gbergman@math.berkeley.edu