Some results on embeddings of algebras, after de Bruijn and McKenzie^{∗}

George M. Bergman

April 7, 2011

              This is the final preprint version of a paper which appeared at
    Indagationes Mathematicae, 18 (2007) 349-403.  The published version is accessible
           in PDF at  /~gbergman/papers/embed_reprt.pdf
                  or  http://dx.doi.org/10.1016/S0019-3577(07)00018-3 .

Abstract

In 1957, N. G. de Bruijn showed that the symmetric group Sym(Ω) on an infinite set Ω contains a free subgroup on 2^{card(Ω)} generators, and proved a more general statement, a sample consequence of which is that for any group A of cardinality ≤ card(Ω), the group Sym(Ω) contains a coproduct of 2^{card(Ω)} copies of A, not only in the variety of all groups, but in any variety of groups to which A belongs. His key lemma is here generalized to an arbitrary variety of algebras V, and formulated as a statement about functors Set → V. From this one easily obtains analogs of the results stated above with “group” and Sym(Ω) replaced by “monoid” and the monoid Self(Ω) of endomaps of Ω, by “associative K-algebra” and the K-algebra End_{K}(V) of endomorphisms of a K-vector-space V with basis Ω, and by “lattice” and the lattice Equiv(Ω) of equivalence relations on Ω. It is also shown, extending another result from de Bruijn’s 1957 paper, that each of Sym(Ω), Self(Ω) and End_{K}(V) contains a coproduct of 2^{card(Ω)} copies of itself.

That paper also gave an example of a group of cardinality 2^{card(Ω)} that was not embeddable in Sym(Ω), and R. McKenzie subsequently established a large class of such examples. Those results are shown here to be instances of a general property of the lattice of solution sets in Sym(Ω) of sets of equations with constants in Sym(Ω). Again, similar results – this time of varying strengths – are obtained for Self(Ω), End_{K}(V), and Equiv(Ω), and also for the monoid Rel(Ω) of binary relations on Ω.

Many open questions and areas for further investigation are noted.

1 Conventions, and outline.

Throughout this note, Ω will be an infinite set. Each ordinal (in particular, each natural number) is understood to be the set of all smaller ordinals; the set of all natural numbers is denoted ω. Functions, including elements of permutation groups, will be written to the left of their arguments and composed accordingly. The word “algebra” will be used in the sense of general algebra (universal algebra), except in the combination “K-algebra”, which will always mean an associative unital algebra in the sense of ring theory, over a field K assumed fixed throughout this note. In those contexts, V will denote a vector space with basis Ω over that field K.

In §§2-3 we develop results to the effect that algebras arising as values of certain sorts of functors can be embedded in certain infinite direct product algebras, and obtain, as immediate corollaries, results on embeddability of groups, monoids, K-algebras, and lattices in the group Sym(Ω), the monoid Self(Ω), the K-algebra End_{K}(V), and the lattice Equiv(Ω) respectively (all defined as in the abstract). The remaining sections obtain results specific to embeddings in one or another of those four structures, and in the monoid Rel(Ω). In §4 (and two appendices, §§10-11) it is shown that one can embed into each of the first three of these algebras a coproduct of 2^{card(Ω)} copies of that same algebra, while §§5-8 obtain restrictions on algebras A embeddable in these five algebras, in terms of order-properties of chains of solution sets of systems of equations in A. §9 suggests some ways in which the results of this note might be extended.

∗2000 Mathematics Subject Classifications. Primary: 08B25. Secondary: 06Bxx, 08B20, 16S50, 18A99, 20B07, 20M20, 54Hxx. This preprint is readable online at http://math.berkeley.edu/∼ gbergman/papers/ , and arXiv:math/0606407 . The former version is likely to be updated more frequently than the latter.

For some further unusual properties of Sym(Ω) and of some of the other structures here considered, cf. [4], [5, §6], [6], and works referred to in those papers.

I am indebted to Anatole Khelif for inadvertently bringing these questions to my attention, to Zachary Mesyan for a careful reading of the first draft, to Andreas Blass and Vladimir Tolstykh for helpful information on the literature, and to the referee for several useful suggestions and corrections.

2 Free algebras.

Recall that by Cayley’s Theorem, every group of cardinality ≤ card(Ω) can be embedded in the symmetric group Sym(Ω) on Ω; in particular, Sym(Ω) contains free groups of all ranks ≤ card(Ω). An obvious question is whether it contains larger free groups, for example, a free group of rank card(Sym(Ω)) = 2^{card(Ω)}. In [7], de Bruijn answered this question affirmatively by a method which also gave embeddings of many interesting nonfree groups in Sym(Ω). We will begin by illustrating his key trick, concerning subalgebras of direct products, in the case of free algebras, making the trivial generalization from the variety of groups to arbitrary varieties of algebras. In the next section, his more general statement will be motivated, reformulated in functorial terms, and generalized still further.

In these two sections, V will be any variety of finitary algebras. (“Finitary” means that every operation has finite arity, but does not exclude varieties with infinitely many operations; for example, modules over an infinite ring.)

Proposition 2.1 (cf. [7]). Let H be the free algebra on ℵ_{0} generators in a variety V. Then the direct product algebra H^{card(Ω)} has a subalgebra free on 2^{card(Ω)} generators.

Proof. Let P(Ω) denote the power set of Ω, and P_{fin}(Ω) ⊆ P(Ω) the set of finite subsets of Ω. Then card(P(Ω)) = 2^{card(Ω)} and card(P_{fin}(Ω)) = card(Ω), so it will suffice to find a P(Ω)-tuple of elements of H^{P_{fin}(Ω)} that satisfies no relations other than the identities of V.

For each s ∈ P_{fin}(Ω), let H_{s} denote the factor indexed by s in our product H^{P_{fin}(Ω)}, and let us pick 2^{card(s)} of the ℵ_{0} free generators of H_{s}, denoting these x_{s,t}, with t ranging over the subsets of s. For every r ∈ P(Ω), let X_{r} be the element of H^{P_{fin}(Ω)} which, for each s ∈ P_{fin}(Ω), has H_{s}-component x_{s,r∩s}.

We claim that the P(Ω)-tuple of elements (X_{r})_{r∈P(Ω)} satisfies no relations other than identities of V. Indeed, since V is finitary, any relation satisfied by these elements involves only finitely many of them; let R(X_{r_{1}}, …, X_{r_{n}}) be such a relation, where r_{1}, …, r_{n} are distinct elements of P(Ω). Choose a finite subset s ⊆ Ω such that r_{1} ∩ s, …, r_{n} ∩ s are distinct. Then the s-components of X_{r_{1}}, …, X_{r_{n}}, namely x_{s,r_{1}∩s}, …, x_{s,r_{n}∩s}, are independent indeterminates in H_{s}, so projecting the relation R(X_{r_{1}}, …, X_{r_{n}}) that we assumed to hold in H^{P_{fin}(Ω)} onto the component H_{s} of that product, we see that it is an identity of V.

Corollary 2.2. (i) The symmetric group Sym(Ω) on Ω has subgroups free on 2^{card(Ω)} generators in every variety V of groups. (ii) The monoid Self(Ω) of endomaps of Ω has submonoids free on 2^{card(Ω)} generators in every variety V of monoids. (iii) The endomorphism ring End_{K}(V) of the K-vector space V with basis Ω has K-subalgebras free on 2^{card(Ω)} generators in every variety V of associative K-algebras. (iv) The lattice Equiv(Ω) of equivalence relations on Ω has sublattices free on 2^{card(Ω)} generators in every variety V of lattices.

Proof. Cayley’s Theorem shows that every group of cardinality ≤ card(Ω) is embeddable in Sym(Ω), and similar arguments give embeddings of all monoids with ≤ card(Ω) elements in Self(Ω) and of all associative K-algebras of vector-space dimension ≤ card(Ω) in End_{K}(V). The corresponding statement for embeddability of lattices in Equiv(Ω) is Whitman’s Theorem [21]. (Whitman does not explicitly say there that if the given lattice L is infinite, then the set on which he represents it has cardinality ≤ card(L), but this can be verified from his construction; or one can deduce the possibility of an embedding with this cardinality condition from the embeddability result without it.) In particular, each of these structures contains a copy of the free algebra H on ℵ_{0} generators in any subvariety V of the given variety, since that free algebra is countable, or in the K-algebra case, countable dimensional.

Moreover, each of the four algebras named contains a card(Ω)-fold direct product of copies of itself. To see this, let us write the given set Ω as a disjoint union of card(Ω) subsets of cardinality card(Ω), Ω = ⋃_{i∈card(Ω)} Ω_{i}. Then within Sym(Ω), the subgroup of consisting those permutations that respect each Ω_{i} is such a direct product, and the analogous statement holds in the monoid Self(Ω). In the K-algebra case we similarly use the algebra of endomorphisms that carry the span of each subset Ω_{i} of our basis Ω of V into itself, and in the lattice case, the sublattice of equivalence relations that relate members of each Ω_{i} only with other members of Ω_{i}.

Since we saw in the first paragraph that each of our objects contains a free algebra H on countably many generators in the (arbitrary) subvariety V, it follows that it will contain a copy of the product algebra H^{card(Ω)}, and Proposition 2.1 now gives the desired conclusions.

Note that the embedding of Equiv(Ω)^{card(Ω)} in Equiv(Ω) used in the second paragraph of the above proof takes the least element of Equiv(Ω)^{card(Ω)} to the least element of Equiv(Ω), but does not take the greatest element to the greatest element. (It takes that element to the relation whose equivalence classes are the sets Ω_{i}.) With a little more work, however, one can get the an embedding that respects both greatest and least elements.

Namely, fix any p ∈ Ω, and let Ω′ ⊆ Ω^{card(Ω)} be the set of elements (x_{i})_{i∈card(Ω)} such that x_{i} = p for all but finitely many i. We see that card(Ω′) = card(Ω), so it will suffice to embed Equiv(Ω)^{card(Ω)} in Equiv(Ω′). We do this by taking each card(Ω)-tuple (α_{i})_{i∈card(Ω)} (α_{i} ∈ Equiv(Ω)) to the relation α ∈ Equiv(Ω′) such that ((x_{i}), (y_{i})) ∈ α if and only if (x_{i}, y_{i}) ∈ α_{i} for all i. It is straightforward to show that this is a lattice embedding which indeed respects least and greatest elements.

So Corollary 2.2(iv) also holds for lattices with greatest and/or least element, and mappings respecting these elements. For brevity, I will not mention lattices with this additional structure in subsequent sections, except when points come up where I notice that what we can prove about lattices with such structure differs from what we can prove for lattices without it. (Incidentally, both the above embedding and the one in the proof of Corollary 2.2(iv) also respect infinitary meets and joins; but this is not relevant to our embedding results, since those require that the algebra operations used be finitary.)

3 Coproducts and functors.

The free algebra on a set Ω in a variety V is the coproduct in V of an Ω-tuple of copies of the free algebra on one generator. To start the ball of generalization rolling, let us note how to extend the proof of Proposition 2.1 to the case where free algebras are replaced by coproducts of copies of an arbitrary algebra.

In our proof of Proposition 2.1, we chose in each copy H_{s} of H a P(s)-tuple (x_{s,t})_{t⊆s} of distinct members of our ℵ_{0}-tuple of free generators. This time, let H be the coproduct in V of ℵ_{0} copies of a fixed algebra A, and let us take for each s ∈ P_{fin}(Ω) a P(s)-tuple (p_{s,t})_{t⊆s} of distinct members of the ℵ_{0}-tuple of coprojection maps A → H_{s} defining the coproduct structure. We can then define, for each r ∈ P(Ω), a map P_{r} : A → H^{P_{fin}(Ω)} by letting the composite of P_{r} with each projection H^{P_{fin}(Ω)} → H_{s} be p_{s,r∩s}. With these adjustments, the proof of Proposition 2.1 goes over, and we likewise get the corollary that if A is any group, monoid, associative K-algebra, or lattice, of cardinality, respectively K-dimension, ≤ card(Ω), and V any variety of groups, monoids, K-algebras or lattices containing A, then the group Sym(Ω), the monoid Self(Ω), the K-algebra End_{K}(V) or the lattice Equiv(Ω) contains a coproduct in V of 2^{card(Ω)} copies of A.

To suggest the next level of generalization, let me give a more or less random concrete example. Let A be the group presented by two generators, x and y, and the relations saying that the generator x has exponent 2, and commutes with the element obtained by conjugating it by the square of the generator y :

(1) x^{2} = 1,

(2) x (y^{2} x y^{−2}) = (y^{2} x y^{−2}) x.

Now if I is any index-set, let F (I) be the group presented by generators x_{i}, y_{i} (i ∈ I) subject to the relations

(3) x_{i}^{2} = 1 (i ∈ I), (4) x_{i} ((y_{j}y_{k}) x_{i} (y_{j}y_{k})^{−1}) = ((y_{j}y_{k}) x_{i} (y_{j}y_{k})^{−1}) x_{i} (i, j, k ∈ I, not necessarily distinct).

Looking at the i = j = k case of these relations, we see that for each i, there is a homomorphism A → F (I) acting by x ↦ x_{i}, y ↦ y_{i}. This is in fact an embedding, for we also see from (1)-(4) that there exists a homomorphism F (I) → A mapping all x_{i} to x and all y_{i} to y, which gives a left inverse to each of the preceding homomorphisms. (Note, incidentally, that the choices made in (3) and (4), to turn x^{2} to x_{i}^{2}, but y^{2} to y_{j} y_{k}, were somewhat arbitrary: other choices would have led to these same conclusions, so the relations (1) and (2) did not uniquely determine (3) and (4).)

Though the group F (I) is generated by an I-tuple of embedded homomorphic images of A, our presentation does not make it a coproduct of those subgroups, since the relations (4) relate elements from different copies of A; nor does it make it their coproduct in some subvariety of groups, since (3) and (4) do not describe identities satisfied by all elements of F (I). We see, however, as for coproducts, that any map of index-sets I → J induces a group homomorphism F (I) → F (J), making F a functor from sets to groups.

We shall find below that the idea of Proposition 2.1 can be used to show that F (ℵ_{0})^{card(Ω)} contains a copy of F (2^{card(Ω)}), and that the corresponding statement holds with the variety of groups replaced by any variety V of finitary algebras, and (3) and (4) by any such system of “relations parametrized by families of indices”.

We could give a careful formulation of this concept of a “parametrized system of generators and relations”. Fortunately, we do not have to, for we shall see that the concept is equivalent to one that can be defined in a simpler way. We noted above that the construction F was a functor Set → V; and it clearly satisfies

(5) For every set I, the algebra F (I) is generated by the union of the images of A = F (1) under the homomorphisms induced by all maps 1 → I.

I claim, conversely, that any functor Set → V satisfying (5) corresponds to a system of algebras determined by “generators and relations with parameters” in the sense suggested by the above discussion. Indeed, given F, let us take for generator-symbols (corresponding to the x and y in our group-theoretic example) any generating set X for F (1). For every set I, every i ∈ I, and every x ∈ X, let us write x_{i} for the image of x under the map F (1) → F (I) induced by the map 1 → I taking 0 to i. Then (5) shows that F (I) is generated by

(6) {x_{i} | x ∈ X, i ∈ I}.

To get relations, let us, for each natural number n, choose a set of relations presenting F (n) in terms of the generators x_{i} (x ∈ X, i ∈ n), and let us turn each of these into a “system of relations with parameters” by replacing the subscripts 0, …, n−1 ∈ n on the generators appearing in each relation with symbols i_{0}, … i_{n−1} ranging over a general index-set I.

We see from the functoriality of F that for any I, the generators (6) of F (I) satisfy all instances of the system of relations so obtained. To see that no more relations are needed, note that any relation satisfied in F (I) by the elements (6) can involve only finitely many of these elements, say those coming from the image of F (n) under some one-to-one map n → I, for some n ∈ ω. If I ≠ ∅, we can take n > 0, so that we may choose a left inverse I → n to this map, and applying F to it, we see that the corresponding relation indeed holds in F (n), and so is a consequence of the system of relations we have chosen. If I = ∅ = 0, then n will also equal 0, and such a map likewise exists, yielding the same conclusion. Thus, the indicated system of generators and relations indeed determines F (I) for all I. (Equations satisfied by the empty set of generators correspond to relations on the set of zeroary operations of V, which hold in all F (I) including F (0). However, for the arguments below, we only need the values of F (I) for nonempty index-sets I, so nothing is lost if the reader prefers to consider F a functor from the category of nonempty sets to V, and so avoid dealing with the case I = ∅.)

De Bruijn [7] proves his embeddability results for what he calls “symmetrically generated groups”. On examination, these turn out to be precisely the values F (I) of group-valued functors F satisfying (5). However, rather than stopping here, we may ask whether, in addition to allowing relations like (4) that depend on more than one parameter, we could allow this in our generators as well. For example, suppose we associate to each set I the group F (I) with generators

(7) x_{ij} (i, j ∈ I), subject to relations

(8) x_{ij}x_{jk} = x_{jk}x_{ij} (i, j, k ∈ I).

It is again clear that maps among index-sets induce homomorphisms among these groups, giving a functor F : Set → Group, and that the corresponding statement is true for systems of algebras of any variety V presented by generators and relations similarly parametrized by multiple subscripts. The resulting functors will not in general satisfy (5), but assuming the string of subscripts on each generator is finite, they will satisfy

(9) For every set I, the algebra F (I) is the union of the images of the homomorphisms F (a) : F (n) → F (I), where n ranges over ω, and a over all set-maps n → I.

Conversely, it is straightforward to show, as before, that the values of any functor satisfying (9) arise from this sort of presentation-with-parameters.

We can now give our generalization of Proposition 2.1. As indicated in the second paragraph of §2, V denotes an arbitrary fixed variety of finitary algebras.

Theorem 3.1 (cf. [7, Theorem 3.1]). Let F be a functor Set → V satisfying (9). Then F (ℵ_{0})^{card(Ω)} has a subalgebra isomorphic to F (2^{card(Ω)}).

Proof. As in the proof of Proposition 2.1, it suffices to construct an embedding h : F (P(Ω)) → F (ℵ_{0})^{P_{fin}(Ω)}; and again, we may specify such an h by giving its composites with the projections of F (ℵ_{0})^{P_{fin}(Ω)} onto the factors F (ℵ_{0}) corresponding to each s ∈ P_{fin}(Ω). For each such s, let c_{s} : P(Ω) → P(s) be defined by r ↦ r ∩ s, and let us choose an embedding e_{s} : P(s) → ℵ_{0}, and take the composite of h with the sth projection to be F (e_{s}c_{s}) : F (P(Ω)) → F (ℵ_{0}).

To show that h is an embedding, consider any two elements u ≠ v ∈ F (P(Ω)). We claim there exists a component of F (ℵ_{0})^{P_{fin}(Ω)} at which h(u) and h(v) have distinct coordinates.

Indeed, from (9) we can see that the images in F (P(Ω)) of homomorphisms F (a) : F (n) → F (P(Ω)) induced by maps a : n → P(Ω) (n ∈ ω) form a directed system of subalgebras with union F (P(Ω)). Hence u and v will together lie in such an image; so let u = F (a)(u_{0}), v = F (a)(v_{0}) for some a : n → P(Ω) and u_{0}, v_{0} ∈ F (n), necessarily distinct; here we may assume n > 0.

Now choose s ∈ P_{fin}(Ω) such that a(0)∩s, …, a(n−1)∩s are distinct. Then the composite map e_{s} c_{s} a : n → P(Ω) → P(s) → ℵ_{0} is one-to-one, hence it has a left inverse. Hence so does F (e_{s} c_{s} a) : F (n) → F (ℵ_{0}); hence that is also one-to-one. In particular, the images of u_{0} and v_{0} under the latter map, which are the s-coordinates of h(u) and h(v), are distinct, as required.

As before, we immediately get the particular embeddability results:

Theorem 3.2 (cf. [7, Theorem 3.1]). Suppose F is a functor from Set to (i) the category of groups, respectively (ii) the category of monoids, (iii) the category of associative algebras over a field K, or (iv) the category of lattices; and suppose that F satisfies (9), and has the property that the cardinality of F (ℵ_{0}) in case (i), (ii) or (iv), or its K-dimension in case (iii), is ≤ card(Ω). (For instance, starting with an algebra A of cardinality or K-dimension ≤ card(Ω), one might define F to be the functor associating to every set I the I-fold coproduct of copies of A in some fixed variety or quasivariety containing A.)

Then F (2^{card(Ω)}) is embeddable in (i) Sym(Ω), (ii) Self(Ω), (iii) End_{K}(V), or (iv) Equiv(Ω), respectively.

The reader may have noticed when we first proved Proposition 2.1 that we did not really need the factors in our product to be free of rank ℵ_{0}; free objects of finite nonzero ranks would do, as long as there were at least card(Ω) such factors of rank greater than or equal to each natural number N; and, similarly, that in the proof of Theorem 3.1, we could have used a direct product (with enough repetitions) of objects F (n) for n finite, instead of a power of F (ℵ_{0}). However, it is not hard to verify in each of these cases that the product of such a family would contain an embedded copy of F (ℵ_{0})^{card(Ω)}, reducing these situations to that of Theorem 3.1. Let us record here the observation from which this follows.

Lemma 3.3 (cf. [7]). Let F be a functor Set → V satisfying (9). Then ∏_{0<n<ω} F (n) has a subalgebra isomorphic to F (ℵ_{0}).

Proof. For each n > 0, let f_{n} : ℵ_{0} = ω → n be the map taking each natural number r to min(r, n−1), and define f : F (ℵ_{0}) → ∏_{0<n<ω} F (n) to have F (f_{n}) as its nth coordinate, for each n. An argument of the sort used in the proof of Theorem 3.1 shows that any two distinct elements of F (ℵ_{0}) have distinct projections in some F (n), so f is an embedding.

It would be interesting to look for results similar to those of this section for functors on categories other than Set. I leave these investigations to others, but give below one such result I have noticed, and a couple of examples of how it can be applied.

Theorem 3.4. Let T.ord be the category whose objects are totally ordered sets, and whose morphisms are isotone maps (maps satisfying x ≤ y ⟹ a(x) ≤ a(y)), and let every ordinal, and likewise the set ℝ of real numbers, be regarded as objects of T.ord via their standard orderings. Suppose F : T.ord → V is a functor satisfying the analog of (9) with “totally ordered set” for “set”, and “isotone maps” for “set-maps”. Then F (ω)^{ℵ_{0}} has a subalgebra isomorphic to F (ℝ).

Proof. The set P_{fin}(ℚ) of finite sets of rational numbers is countable, so it suffices to embed F (ℝ) in F (ω)^{P_{fin}(ℚ)}. Given s ∈ P_{fin}(ℚ) whose distinct elements are q_{1} < ⋯ < q_{n}, let a_{s} : ℝ → ω be the isotone map which sends each r ∈ ℝ to the greatest i ∈ {1, …, n} such that q_{i} ≤ r if such an i exists, and sends all r < q_{1} to 0. Let h : F (ℝ) → F (ω)^{P_{fin}(ℚ)} be the map whose composite with the projection indexed by each s ∈ P_{fin}(ℚ) is F (a_{s}).

It is not hard to see that we will be able to complete the proof as we did that of Theorem 3.1 if for every finite set of real numbers r_{0} < ⋯ < r_{n}, we can find an s ∈ P_{fin}(ℚ) and an isotone map b : ω → ℝ such that the map ba_{s} : ℝ → ω → ℝ fixes r_{0}, …, r_{n}. To do this, choose q_{1}, …, q_{n} ∈ ℚ so that r_{i−1} < q_{i} ≤ r_{i} (i = 1, …, n), let s = {q_{1}, …, q_{n}}, and let b take i to r_{i} for i = 0, …, n, and be extended in an arbitrary isotone manner to larger i. Thus, a_{s} takes r_{i} (i = 0, …, n) to i, which b takes back to r_{i}, as required.

For a functor F as in the above theorem, the algebras F (I) will have presentations by systems of generators and relations indexed by finite sequences of subscripts from I, where the indices occurring in each generator or relation may be constrained by inequalities of the form i ≤ j. A simple example is the functor associating to each totally ordered set I the group presented by generators x_{i} and y_{i} (i ∈ I) subject to the relations

(10) x_{i} y_{j} = y_{j} x_{i} for i ≤ j in I.

Another is the functor taking each I to the (commutative) monoid presented by generators x_{i} (i ∈ I) and relations

(11) x_{i} x_{j} = x_{i} = x_{j} x_{i} for i ≤ j in I.

In each of these cases, the object F (ω) is countable, hence embeddable in Sym(ℵ_{0}), respectively Self(ℵ_{0}); hence, combining Theorem 3.4 with the method of proof of Theorem 3.2, we see that F (ℝ) is also embeddable in Sym(ℵ_{0}), respectively Self(ℵ_{0}). Likewise, the group algebra K F (ℝ) for F determined by (10), and the monoid algebra K F (ℝ) for F determined by (11), are the values at ℝ of K-algebra-valued functors satisfying the analog of (9), and so are embeddable in End_{K}(V) for V countable-dimensional. I do not see any way to obtain these results from Theorems 3.1 and 3.2 themselves.

Let us note in connection with the group-theoretic construction (10) (and for some later uses) that if X is any set, and R any symmetric reflexive binary relation on X, and we form the group G presented by the generating set X and the relations

(12) xx′ = x′x ((x, x′) ∈ R),

then distinct subsets of X generate distinct subgroups of G (clear by looking at the abelianization of G), and elements x, x′ ∈ X commute in G if and only if (x, x′) ∈ R. To see the latter statement, consider any x ∈ X, and let G_{0} be the group presented as above, but using the set X − {x} and the restriction of R to that set. Then G can be described as an HNN extension [15] of G_{0}, obtained by adjoining an additional generator x, whose conjugation action is specified on the subgroup generated by {y ∈ X − {x} | (x, y) ∈ R} as the identity map. By the structure of HNN extensions, conjugation by x fixes precisely the elements of that subgroup, giving the asserted characterization of the commuting pairs of elements of X.

4 Each of Sym(Ω), Self(Ω) and End_{K}(V) contains a coproduct of copies of itself.

In the case of Theorem 3.2 where F (I) is the I-fold coproduct of copies of an algebra A, the number of copies of A in the conclusion, 2^{card(Ω)}, is, in general, as large as it can be, embeddability of larger coproducts being precluded by the size (i.e., cardinality or K-dimension) of the object we are trying to embed in. But the assumption that A itself has cardinality or K-dimension ≤ card(Ω) is not forced in that way; we assumed it so that we could be sure that the coproduct of countably many copies of A would be embeddable in the object in question.

Can we prove results of the same sort for any larger algebras A?

We shall sketch in the next few paragraphs a proof that the symmetric group Sym(Ω) contains a coproduct of two copies of itself. Hence, by iteration, it contains coproducts of all finite numbers of copies of itself, hence, by Lemma 3.3, a coproduct of countably many copies of itself, hence, by Theorem 3.1, a coproduct of 2^{card(Ω)} copies of itself. This result, like those that we generalized in preceding sections, was proved by de Bruijn in [7]. We will then see how to adapt our argument to the case of the monoid Self(Ω), and, with more work, the associative algebra End_{K}(V).

(In an earlier version of this note, I asked whether the corresponding result held for the lattice Equiv(Ω). An affirmative answer has been given by F. Wehrung [20].)

As indicated above, the hard step, for each of these objects, is to show that it contains the coproduct of two copies of itself. Note that to do this for the group Sym(Ω) is equivalent to finding two faithful actions of Sym(Ω) on Ω (or on some set of the same cardinality) such that there is no nontrivial “interaction” between the permutations giving these actions. In its most naive form, the idea behind the construction we shall describe is to take the natural representation of Sym(Ω) on Ω, and the same representation conjugated by a “random” permutation t of Ω, and hope that elements of the two representations will not interact.

As stated, this is much too naive: no matter how we choose t to eliminate interaction among certain permutations in our two representations, it will inevitably lead to interaction among others. However, suppose we replace the set Ω by the disjoint union of card(Ω) copies of itself, on each of which we start with the natural representation of Sym(Ω), and on each of which we perturb this representation by a different “t”. Then we can hope that any given interaction among finitely many elements of our original and perturbed images of Sym(Ω) will be avoided in at least one of these copies. If this is so, then the representation of Sym(Ω)∐Sym(Ω) on our union of copies of Ω will be faithful.

In particular, we might index our set of copies of Ω by the group Sym_{fin}(Ω) of all permutations of Ω that move only finitely many elements, and on the copy indexed by each t in that group, let that t be our perturbing permutation.

There is still one difficulty: When we construct a t to prevent interaction in some long expression w in elements from our two groups, the behavior of t that we need at one step may be different from the behavior we want at a later step. To get around this, each copy of Ω in the above sketch will be replaced by a disjoint union of countably many copies of itself, Ω × ω, and t will range over Sym_{fin}(Ω × ω). Given a group relation w = v that we want to cause to fail, we will find that we can select our t and an element (p_{1}, 0) ∈ Ω × {0} so that as we apply w or v to (p_{1}, 0), that element is moved by successive occurrences of t into Ω × {1}, Ω × {2}, etc., and on each of those copies, we shall be able to independently control what t does.

As mentioned, the above technique can also be adapted to the monoid Self(Ω), and to the K-algebra End_{K}(V). In the next lemma, the group, monoid, and K-algebra cases are all stated, and the proof is given for the first two. I have relegated the longer proof for End_{K}(V) to an appendix, §10, so as not to interrupt the flow of the paper. (Another appendix, §11, gives an alternative construction in the Sym(Ω) case, which I found before encountering de Bruijn’s papers, but was not able to adapt to the monoid or K-algebra cases. It may, however, be of independent group-theoretic interest.)

Recall that we are writing functions to the left of their arguments (in contrast to the usage in many papers in the theory of infinite symmetric groups).

Lemma 4.1 (cf. [7]). (i) Sym(Ω) contains a coproduct of two copies of itself as a group. (ii) Self(Ω) contains a coproduct of two copies of itself as a monoid. (iii) End_{K}(V) contains a coproduct of two copies of itself as an associative K-algebra.

Proof of (i) and (ii). We shall verify (ii), then deduce (i) from it.

Recall that the normal form for an element of the coproduct M ∐N of two monoids is

(13) … α(g_{i}) β(g_{i−1}) α(g_{i−2}) β(g_{i−3}) …,

where α : M → M ∐N, β : N → M ∐N are the coprojection maps, the elements g_{k} with k of one parity (in (13), the parity of i) are elements of M − {1}, and those with k of the other parity are elements of N − {1}. In (13), I do not explicitly show the first and last factors, because each may involve either α or β. The identity element is given by the empty product (13).

Thus, elements of Self(Ω)∐Self(Ω) can be written uniquely as products (13) in which all g_{i} come from Self(Ω) − {1}.

To prove (ii), it suffices to construct a faithful action of Self(Ω)∐Self(Ω) on a set of the same cardinality as Ω. As suggested in the above discussion, that set will be the disjoint union of a family of copies of Ω × ω indexed by the group Sym_{fin}(Ω × ω). On every copy of Ω × ω, we let elements α(g) (g ∈ Self(Ω)) act in the “natural” manner, g((p, k)) = (g(p), k) (p ∈ Ω, k ∈ ω), while on the copy of Ω × ω indexed by t ∈ Sym_{fin}(Ω × ω), we let β(g) act by t g t^{−1}, i.e., the conjugate by t of that same natural action.

To prove that the resulting action of Self(Ω)∐Self(Ω) on our union of copies of Ω×ω is faithful, assume we are given two distinct elements of that monoid, say (13) and

(14) … α(h_{j}) β(h_{j−1}) α(h_{j−2}) β(h_{j−3}) ….

We shall show below how to obtain a t ∈ Sym_{fin}(Ω × ω) such that the induced actions of (13) and (14) on Ω × ω, namely

(15) … g_{i} (t g_{i−1} t^{−1}) g_{i−2} (t g_{i−3} t^{−1}) … and … h_{j} (t h_{j−1}t^{−1}) h_{j−2} (t h_{j−3}t^{−1}) …,

act differently on a certain element of Ω × ω.

The t we shall construct will be of order 2, so the above two expressions take the forms

(16) … g_{i} t g_{i−1} t g_{i−2} t g_{i−3} t … and … h_{j} t h_{j−1} t h_{j−2} t h_{j−3} t ….

We may assume, by interchanging (13) and (14) if necessary, that the former expression involves at least as many factors from Sym(Ω) as the latter, and, moreover, that if they have the same number of such factors, and have αs and βs in the same places, then for the least value k such that g_{k} ≠ h_{k}, some element of Ω on which g_{k} and h_{k} disagree is moved by the former.

If the rightmost term of our original expression (13) is an α term, rather than a β term, let us multiply both lines of (16) on the right by t, and likewise if the left-hand term of (13) is an α term, let us multiply both lines on the left by t. Since t is going to be invertible, the non-equality of the new expressions, which we will prove, is equivalent to the non-equality of the old ones. The first of the new expressions can now be written more precisely; the two products have become

(17) t g_{n} t … t g_{i} t g_{i−1} t g_{i−2} t g_{i−3} t … t g_{1} t, and … t h_{i} t h_{i−1} t h_{i−2} t h_{i−3} t ….

Clearly, by the assumptions we have made, the first line of (17) has at least as many occurrences of t as the second.

To construct our promised t, let us now choose, for each k ∈ {1, …, n}, an element p_{k} ∈ Ω that is moved by g_{k}; moreover, we take it to be an element at which g_{k} and h_{k} disagree whenever this is possible; i.e., we require this for every value of k such that there exists an element moved by g_{k} at which g_{k} and h_{k} differ. We then define t to fix all elements of Ω × ω except the following 2(n + 1) elements, which we let it transpose in pairs, as shown:

(18) (p_{1}, 0) ↔ (p_{1}, 1), (g_{k}(p_{k}), k) ↔ (p_{k+1}, k+1) (1 ≤ k < n), (g_{n}(p_{n}), n) ↔ (g_{n}(p_{n}), n+1).

Note that (18) is consistent: For 1 ≤ k ≤ n, g_{k} moves p_{k}, hence the two elements of Ω×{k} on which (18) prescribes (in different ways) the behavior of t, namely (p_{k}, k) and (g_{k}(p_{k}), k), are distinct.

We now see that when the element shown on the first line of (17) is applied to (p_{1}, 0), the successive factors of that element (reading from the right), namely t, g_{1}, t, g_{2}, t, …, move it as follows (19) (p_{1}, 0) ↦ (p_{1}, 1) ↦ (g_{1}(p_{1}), 1) ↦ (p_{2}, 2) ↦ (g_{2}(p_{2}), 2) ↦ (p_{3}, 3) ↦

… ↦ (g_{n−1}(p_{n−1}), n − 1) ↦ (p_{n}, n) ↦ (g_{n}(p_{n}), n) ↦ (g_{n}(p_{n}), n + 1).

In particular, (p_{1}, 0) is carried from Ω × {0} into Ω × {n + 1}.

When we instead apply the second line of (17) to (p_{1}, 0) there are several possible cases. If there are fewer factors h_{j} than g_{i}, there will be fewer factors t in that second line than in the first line, so there is no way the permutation represented by the second line can move an element from Ω × {0} into Ω × {n + 1}. If there are the same number, n, of hs as of gs, but if the αs and βs don’t appear on the same factors, then since the first line of (17) was adjusted to have a t at each end, the second line will not; so again there will be fewer factors t, and (p_{1}, 0) cannot be moved all the way into Ω × {n + 1}.

Finally, if there are the same number of factors and the αs and βs appear in the same positions, then by assumption, for the least k such that g_{k} ≠ h_{k}, the element g_{k} moves some element of Ω at which these elements disagree (see sentence after (16)), and by our choice of p_{k}, the latter will be such an element (first sentence of paragraph containing (18)). When we apply the second line of (17) to (p_{1}, 0), the input to the factor h_{k} will be (p_{k}, k) (since the terms have agreed up to this point), so the output will be (h_{k}(p_{k}), k) ≠ (g_{k}(p_{k}), k). Thus, our element will fail to be in the unique position (cf. (18)) from which it can “catch the boat” to be shifted by t from Ω × {k} to Ω × {k + 1}; and since t moves elements by only one level at a time, our element will not be able to catch up later on. So the second line of (17) does not move (p_{1}, 0) into Ω × {n + 1}, hence the two lines represent distinct elements of Self(Ω × ω), completing the proof of (ii).

To deduce (i) from (ii), note that the normal forms of coproducts of groups and of monoids are formally the same, hence the inclusion of Sym(Ω) in Self(Ω) induces an embedding of Sym(Ω)∐Sym(Ω) into Self(Ω)∐Self(Ω). Since monoid homomorphisms carry invertible elements to invertible elements, the image of this copy of Sym(Ω)∐Sym(Ω) under the embedding of statement (ii) lies in the group Sym(Ω) of invertible elements of Self(Ω), so we have indeed embedded Sym(Ω)∐Sym(Ω) in Sym(Ω), as required.

As mentioned earlier, the proof of (iii) will be given in an appendix, §10.

By the reasoning sketched at the beginning of this section, we deduce

Theorem 4.2. (i) Sym(Ω) contains a coproduct of 2^{card(Ω)} copies of itself as a group. (ii) Self(Ω) contains a coproduct of 2^{card(Ω)} copies of itself as a monoid. (iii) End_{K}(V) contains a coproduct of 2^{card(Ω)} copies of itself as an associative K-algebra.

Hence, for instance, if A is any group, not necessarily of cardinality ≤ card(Ω), that is embeddable in Sym(Ω), then the coproduct of 2^{card(Ω)} copies of A in the category of groups is also embeddable in Sym(Ω).

I should mention that at the beginning of this section, when I said that the cardinal 2^{card(Ω)} appearing in our results was, in general, the best we could hope for, the phrase “in general” was a hedge. There is an exception, concerning the algebras End_{K}(V) when K is a field of cardinality > 2^{card(Ω)}. We will see at the end of §10 that in that case, we can get a stronger conclusion than Theorem 4.2(iii).

Note that Theorem 4.2, unlike the results of previous sections, says nothing about coproducts in subvarieties of our varieties. So we ask,

Question 4.3. Suppose A is a group, monoid or associative K-algebra which belongs to a subvariety V of the variety of all such algebras, and which is embeddable in Sym(Ω), Self(Ω) or End_{K}(V) respectively.

Must the same be true of the coproduct in V of two copies of A? (If this is indeed true for all such A, the corresponding statement will hold for coproducts in V of 2^{card(Ω)} copies of such A, by Lemma 3.3 and Theorem 3.1.)

In the case where V is the variety of abelian groups, or any subvariety thereof, one has an affirmative answer, for de Bruijn [8, Theorem 4.3] shows that every abelian group of cardinality ≤ 2^{card(Ω)} is embeddable in Sym(Ω). However, the analog of this stronger statement fails for all varieties of groups not contained in the variety of abelian groups, by a result of McKenzie that will be recalled in the next section.

A question similar to the preceding, but concerning additional constants rather than additional identities, is Question 4.4. Suppose B is a subgroup of Sym(Ω), a submonoid of Self(Ω), or a sub-K-algebra of End_{K}(V).

Must Sym(Ω), Self(Ω) or End_{K}(V) respectively have a subalgebra containing B, and isomorphic over B to the coproduct of two copies of Sym(Ω), Self(Ω) or End_{K}(V) with amalgamation of B (i.e., isomorphic over B to the pushout, in the variety of all groups, semigroups, or K-algebras, of the diagram formed by B and two copies of the indicated algebra; equivalently, to the coproduct of two copies of that algebra in the variety of groups, monoids or K-algebras with distinguished constants corresponding to the elements of B) ?

If this is not true in general, does it become true when B has some “good” form; e.g., in the case of Self(Ω), when B is a group of invertible elements, or in the case of End_{K}(V) when B is a division algebra?

Turning back to the argument we used to get Theorem 4.2 from Lemma 4.1, we should note that a certain fact was implicitly called on which is true of the varieties of all groups, all monoids, and all associative Kalgebras, and in many other familiar varieties of algebras, but not in all – namely that, given inclusions of algebras A′ ⊆ A and B′ ⊆ B, the induced homomorphism of coproducts in our variety,

(20) A′ ∐B′ → A∐B,

is also injective. It is this that allows us to say that if an algebra A contains a coproduct of two copies of itself, it contains a coproduct of any finite number of such copies.

An example of a variety V where the injectivity of maps (20) fails is the variety of groups generated by the infinite dihedral group. To see this, note that V satisfies the identity

(21) (x^{2}, y^{2}) = 1,

but no identity x^{n} = 1 (n > 0). Let A and B be infinite cyclic groups ⟨x⟩ and ⟨y⟩; these are each free on one generator in V. Let A′, B′ be the subgroups ⟨x^{2}⟩ ⊆ A and ⟨y^{2}⟩ ⊆ B, which are isomorphic to A and B. The coproduct A∐B in V is the free algebra on {x, y} in that variety, hence is noncommutative, and so the same is true of A′ ∐B′. But the image of A′ ∐B′ in A∐B is generated by x^{2} and y^{2}, which commute by (21), so the map A′ ∐B′ → A∐B is not an embedding.

Though this shows that the principle we used in the proof of Theorem 4.2 is not valid in all varieties, it does not show that the consequence of that principle that we used, concerning objects containing coproducts of copies of themselves, can fail. So we ask

Question 4.5. Does there exist an algebra A in a variety V such that A contains the coproduct in V of two copies of itself, but not the coproduct of three such copies?

The preceding results about fitting into Sym(Ω), Self(Ω) and End_{K}(V) multiple copies of themselves suggest questions about fitting these objects into each other, in various ways. We record two easy results in this direction:

Lemma 4.6. (i) End_{K}(V) contains an embedded copy of K Self(Ω), the monoid algebra over K on the monoid Self(Ω). (ii) Self(Ω) contains an embedded copy of Equiv(Ω)_{∧}, i.e., Equiv(Ω) made a monoid under the meet operation ∧.

Proof. (i) Let K⟨Ω⟩ denote the free associative K-algebra on Ω. Then the action of Self(Ω) on Ω induces an action of Self(Ω) on K⟨Ω⟩ by K-algebra endomorphisms, which extends to an action of the monoid algebra K Self(Ω) by vector-space endomorphisms of K⟨Ω⟩. Since K⟨Ω⟩ has the same vector-space dimension, card(Ω), as V, our assertion will follow if we can show that the endomorphisms of K⟨Ω⟩ induced by any finite family g_{1}, …, g_{n} of distinct elements of Self(Ω) are K-linearly independent.

Given such g_{1}, …, g_{n}, let us choose p_{1}, …, p_{m} ∈ Ω such that no two of g_{1}, …, g_{n} behave the same on all of these elements. Regarding p_{1}, …, p_{m} as members of the free generating set Ω of K⟨Ω⟩, we can form the product p_{1} … p_{m} therein, and observe that the actions of g_{1}, …, g_{n} take this monomial to distinct monomials, hence are indeed K-linearly independent.

(ii) If we regard equivalence relations on Ω as subsets of Ω × Ω, then the meet operation on Equiv(Ω) is the restriction of the intersection operation on P(Ω × Ω), hence it will suffice to embed P(Ω × Ω)_{∩} in Self(Ω). Since card(Ω × Ω) = card(Ω) = card(Ω × 2), we can do this, in turn, if we can embed P(Ω)_{∩} in Self(Ω × 2). To do this, let us send each S ⊆ Ω to the endomap of Ω × 2 that fixes all elements (p, 0), and also all elements (p, 1) with p ∈ S, but sends (p, 1) to (p, 0) if p ∉ S. The verification that this is a monoid homomorphism, and indeed an embedding, is straightforward.

We will see in §6 that the analog of statement (ii) above with “meet” replaced by “join” is false.

It is also interesting to note that the analog of (i) fails if Ω replaced by a finite set with n ≥ 2 elements. Indeed, for n ≥ 3, even the group algebra K Sym(Ω) cannot be embedded in End_{K}(V), for it has dimension n!, while End_{K}(V) has dimension only n^{2}. In particular, the n! permutation matrices do not generate a copy of the group algebra – they are not linearly independent. To get the nonembeddability statement for K Self(Ω) when n = 2, let R = K Self(2), and note by comparing dimensions that a K-algebra embedding of R in M_{2}(K) would have to be an isomorphism. Let z ∈ Self(2) be the map taking both elements of 2 to 0, and note that it satisfies the left-zero identity (∀ a) za = z. Hence zR ⊆ Kz, hence z R (1 − z) = 0; but M_{2}(K) has no idempotent z with this property other than 0 and 1.

5 Restrictions on groups embeddable in Sym(Ω) and monoids embeddable in Self(Ω).

With such vast classes of groups, monoids, associative K-algebras and lattices embeddable in Sym(Ω), Self(Ω), End_{K}(V), and Equiv(Ω), it is natural to ask whether there are groups, etc., of cardinality, respectively K-dimension, ≤ 2^{card(Ω)}, that are not so embeddable.

For the case of groups, de Bruijn [7] showed, in effect, that for any set I of cardinality > card(Ω), the group presented by generators x_{i} (i ∈ I) and relations

(22) x_{i}^{2} = 1 (i ∈ I),

(23) (x_{i} x_{j})^{3} = 1 (i, j ∈ I, distinct),

(24) (x_{i} x_{j} x_{k} x_{l})^{5} = 1 (i, j, k, l ∈ I, distinct),

cannot be embedded in Sym(Ω). Note that the fact that the indices in (23) and (24) are required to be distinct keeps this system of groups from having the form to which the results of §3 apply. (If those indices were not required to be distinct, then setting k = i, l = j in (24) would give (x_{i}x_{j})^{10} = 1, which, combined with (23), would give x_{i}x_{j} = 1, making the group collapse to Z_{2}.)

On the other hand, de Bruijn claimed in [7] that his result corresponding to Theorem 3.1 showed that the restricted direct product (called in [7] the direct product) of 2^{card(Ω)} copies of any group A of cardinality ≤ card(Ω) could be embedded in Sym(Ω) – not noticing that because the commutativity relations which the restricted direct product construction imposes on elements of different copies of A fail to hold among elements of a single copy (unless A is commutative), that result is not applicable. In [8] he corrected this error, noting that the argument is only valid when A is abelian, and posed his earlier assertion as an open question.

That question was answered in the negative by McKenzie [16], who showed that if G is a group such that for some index set I with card(I) > card(Ω) there are elements x_{i}, y_{i} ∈ G (i ∈ I) satisfying

(25) x_{i}y_{j} = y_{j}x_{i} whenever i ≠ j, but x_{i}y_{i} ≠ y_{i}x_{i},

then G cannot be embedded in Sym(Ω).

We shall see that McKenzie’s criterion is an instance of more general facts. By a centralizer subgroup in a group G, let us understand a subgroup of the form

(26) C_{G}(X) = {g ∈ G | (∀ x ∈ X) gx = xg}

for some subset X ⊆ G. A subgroup H < G is clearly a centralizer subgroup if and only if H = C_{G}(C_{G}(H)). Recall also that a jump in a totally ordered set means a pair of elements x < y such that {z | x < z < y} is empty. A totally ordered set without jumps can have subsets with jumps; for instance, the set of reals or of rationals has none, but their subset ℤ has countably many. We shall see below that the lattice of centralizer subgroups of Sym(Ω), and hence of any group embeddable therein, contains no chains with > card(Ω) jumps, while the lattice of centralizer subgroups of a group with a family of elements satisfying (25) does have such chains.

In fact, we shall prove the former result not only for centralizer subgroups, but for subsets of Sym(Ω) defined by arbitrary systems of equations (in several variables) with constants in Sym(Ω), which will also yield a quick proof of de Bruijn’s example. Our result will follow from the fact that such solution subsets are closed in the function topology on Sym(Ω), together with the following lemma in general topology.

Note that unless explicitly stated, we do not assume topologies to be Hausdorff. The function topology, to which we will apply the lemma in this section, is Hausdorff, but in the next section we will apply the same lemma to both Hausdorff and non-Hausdorff topologies.

Lemma 5.1. Let T be a topological space having an infinite basis (or more generally, subbasis) B of open sets. Then the lattice of open subsets of T contains no chain with > card(B) jumps. Hence its opposite, the lattice of closed subsets of T, also has no such chains. In particular, that lattice contains no well-ordered or reverse-well-ordered chains of cardinality > card(B).

Proof. The case where B is a subbasis reduces to that in which it is a basis, since in the former case, a basis is given by the set of intersections of finite subsets of B, and for B infinite there are only card(B) of these. So we assume B a basis.

Suppose C is a chain of open subsets of T. For each jump U ⊂ V in C, let us choose a point p_{(U,V)} ∈ V − U. Since V is a neighborhood of p_{(U,V)}, our basis B contains some subneighborhood N_{(U,V)} ⊆ V of p_{(U,V)}; let N_{(U,V)} be so chosen for each jump U ⊂ V. Then if U ⊂ V and U′ ⊂ V′ are distinct jumps, say with U ⊂ V ⊆ U′ ⊂ V′, we must have N_{(U,V)} ≠ N_{(U′,V′)}, since N_{(U,V)} ⊆ V, while N_{(U′,V′)} contains p_{(U′,V′)} ∉ U′. Hence distinct jumps in C give distinct elements N_{(U,V)} ∈ B, so the number of jumps in C does not exceed card(B).

Recall next that if Ω and Ω′ are sets, and we give Ω′ the discrete topology, then the function topology on the set of all maps Ω → Ω′ has for a subbasis of open sets the sets U_{y,x} = {f : Ω → Ω′ | f(x) = y} (x ∈ Ω, y ∈ Ω′), since a basis for the open sets of Ω′ is given by the singletons {y}. In particular, if Ω is infinite, the function topology on the set Self(Ω) has a subbasis of cardinality card(Ω × Ω) = card(Ω). Hence for any set J, the direct product of a J-tuple of copies of this space has a subbasis of cardinality card(Ω) card(J). So we get

Corollary 5.2. If card(J) ≤ card(Ω), then the lattice of subsets of Self(Ω)^{J} closed in the product topology on that set induced by the function topologies on the factors Self(Ω) has no chains with > card(Ω) jumps.

Let us now connect this topology with our algebraic structure. It is straightforward to verify that the operation of composition on Self(Ω) is continuous in the function topology; moreover, on its subset Sym(Ω), the operation of functional inverse is also continuous, since it simply interchanges U_{y,x} ∩ Sym(Ω) and U_{x,y} ∩ Sym(Ω) for all x and y. (We remark, however, that Sym(Ω) is not closed in Self(Ω).) Hence given a pair of monoid words (respectively group words) v, w, in a variable t and constants from Self(Ω) (respectively, from Sym(Ω)), the solution set {a | v(a) = w(a)} will be closed in the function topology on Self(Ω) (respectively, Sym(Ω)). More generally, we may look at the solution set of any family of such pairs of words in any number of variables. Let us set up notation for such sets in an arbitrary algebra.

Definition 5.3. For A an algebra in a variety V, and J a set, we shall understand a principal solution set in A^{J} to mean a set of the form

(27) S_{v=w} = {a = (a_{j})_{j∈J} ∈ A^{J} | v(a) = w(a)} ⊆ A^{J},

where v and w are words in a J-tuple of variables (t_{j})_{j∈J}, constants from A, and the operations of V.

A solution set in A^{J} will mean the intersection of an arbitrary family of principal solution sets. We shall denote by L_{A, J}^{=} the complete lattice of all solution sets in A^{J}.

Here we understand the intersection of the empty family of principal solution sets to be the whole set A^{J}. Thus, L_{A, J}^{=} is, as asserted, a complete lattice, the join of any X ⊆ L_{A, J}^{=} being the intersection of those principal solution sets that contain all members of X. (The superscript “=” in L_{A, J}^{=} indicates that our solution sets are defined by equations, as in (27). In the next section we shall also make use of solution sets defined by inequalities.)

In the next result, though J is allowed to have cardinality up to card(Ω), the most common cardinality in our applications will be 1.

Theorem 5.4. Let J be any set of cardinality ≤ card(Ω). Then L_{Sym(Ω), J}^{=} contains no chains with > card(Ω) jumps. Hence the same is true of L_{G, J}^{=} for any group G embeddable in Sym(Ω).

Likewise, L_{Self(Ω), J}^{=} contains no chains with > card(Ω) jumps; hence the same is true of L_{M, J}^{=} for any monoid M embeddable in Self(Ω).

In particular, for G a group embeddable in Sym(Ω) or M a monoid embeddable in Self(Ω), the lattice L_{G, J}^{=}, respectively L_{M, J}^{=} contains no well-ordered or reverse-well-ordered chain of cardinality > card(Ω).

Proof. The assertions about chains in L_{Sym(Ω), J}^{=} and L_{Self(Ω), J}^{=} are clear from Corollary 5.2 and the continuity of our operations; it remains to deduce the corresponding statements for objects embeddable in Sym(Ω) and Self(Ω).

If G is a group embeddable in Sym(Ω), let us assume for notational convenience that it is a subgroup, and map L_{G, J}^{=} to L_{Sym(Ω), J}^{=} by sending each solution set S in G^{J} to the solution set in Sym(Ω)^{J} of the set of all equations (in a J-tuple of variables, with constants in G) that are satisfied on S. This map is easily seen to be an embedding of partially ordered sets, hence the result on chains in L_{Sym(Ω), J}^{=} implies the same conclusion for chains in L_{G, J}^{=}. The same argument works for monoids.

Some observations on the above proof: Given groups G < H, one cannot embed L_{G, J}^{=} in L_{H, J}^{=} by simply sending the solution set of every system of equations in G to the solution set of the same system in H. This does not give a well-defined function, since equations over G having the same solution set in G^{J} may have different solution sets in H^{J}. (Consider, for instance, centralizer subgroups of various sets in an abelian group, and of the same sets in a nonabelian overgroup.) The construction of the above proof does give an order-embedding of L_{G, J}^{=} into L_{H, J}^{=}, but in general this respects neither meets nor joins; the former because the set H^{J} is larger than G^{J}; the latter because the set of equations with constants in H is larger than the set of equations with constants in G. Another order-embedding of L_{G, J}^{=} in L_{H, J}^{=} is gotten by sending every S ∈ L_{G, J}^{=} to the set of elements of H^{J} satisfying all equations with constants in H satisfied on S; it also respects neither meets nor joins, in general.

For our first application of Theorem 5.4, note that the centralizer subgroups (26) in a group G form a complete lattice, which as a partially ordered set (and indeed, as a complete lower semilattice) is embedded in L_{G,1}^{=}. Hence we have

Corollary 5.5. No group having a chain of centralizer subgroups with > card(Ω) jumps is embeddable in Sym(Ω). In particular (McKenzie, [16]), if a group G contains, for some set I with card(I) > card(Ω), elements x_{i}, y_{i} (i ∈ I) satisfying (25), then G is not embeddable in Sym(Ω).

Proof. The first statement is clear from the first paragraph of Theorem 5.4. In the situation of the second statement, we may, by reindexing, assume I to be a cardinal κ > card(Ω). For each α ∈ κ, let X_{α} = {x_{β} | β > α}. The X_{α} form a descending chain of subsets, hence their centralizers C_{G}(X_{α}) form an ascending chain of centralizer subgroups. Note that each C_{G}(X_{α}) contains those elements y_{γ} with γ ≤ α and no other y_{γ}, hence the C_{G}(X_{α}) are distinct. Thus we have a well-ordered chain of centralizer subgroups of cardinality κ > card(Ω); hence G is not embeddable in Sym(Ω).

The cardinality conditions in the above result are sharp: If we take any set I of cardinality ≤ card(Ω), and any I-tuple G_{i} of nonabelian groups each of cardinality ≤ card(Ω), then their restricted direct product has cardinality ≤ card(Ω), hence is embeddable in Sym(Ω), though it contains elements x_{i}, y_{i} satisfying (25).

Turning to de Bruijn’s relations (22)-(24), note that for any index set I of cardinality ≤ card(Ω), if we take an element p_{0} ∈ Ω and an I-tuple of elements p_{i} ∈ Ω distinct from p_{0} and from each other, and for each i ∈ I let x_{i} ∈ Sym(Ω) be the transposition that interchanges p_{0} and p_{i} and fixes all other elements, then any product of n distinct elements x_{i} is an (n + 1)-cycle in Sym(Ω), from which we see that the I-tuple (x_{i})_{i∈I} satisfies (22)-(24). This shows that the cardinality conditions in the next result are sharp. That result, in fact, does without (22), at the small price of adding two sentences at the start of the proof.

Corollary 5.6 (cf. [7, Theorem 5.1]). No group G containing a family (x_{i})_{i∈I} of distinct elements satisfying (23) and (24), where card(I) > card(Ω), is embeddable in Sym(Ω).

Proof. If there are any pairs i ≠ i′ ∈ I such that x_{i} and x_{i′} are inverse to one another, then dropping one member of each such pair does not decrease card(I). Hence we may assume there are no such pairs.

Let us also assume, by reindexing, that I has the form κ × 2, where κ is a cardinal > card(Ω), so that our given elements have the form x_{β,i} (β ∈ κ, i = 0, 1). For each α ∈ κ, let us define the solution set S_{α} = {(y, z) ∈ G^{2} | (∀ β > α) (x_{β,0} x_{β,1} y z)^{5} = 1}. By (24), this set contains the pair (x_{γ,0}, x_{γ,1}) whenever γ ≤ α.

However, it contains no pair (x_{β,0}, x_{β,1}) with β > α. Indeed, if it did, we would have

(28) 1 = (x_{β,0} x_{β,1} x_{β,0} x_{β,1})^{5} = (x_{β,0} x_{β,1})^{10}.

But by (23), (x_{β,0} x_{β,1})^{3} = 1. Combining these equations we get x_{β,0} x_{β,1} = 1, contradicting our assumption that for i and i′ distinct, x_{i} and x_{i′} are not inverses.

Hence, the sets S_{α} are distinct, and so form a well-ordered chain of cardinality κ in L_{G, 2}^{=}, from which nonembeddability of G in Sym(Ω) follows by Theorem 5.4.

What about applications of Theorem 5.4 to monoids? Well, the monoid homomorphisms from a group G to a monoid M are the group homomorphisms from G to the group of invertible elements of M; hence the above two corollaries can also be viewed as giving monoids that are not embeddable in Self(Ω).

Here is a more genuinely monoid-theoretic application. Consider again an element p_{0} ∈ Ω and a family of distinct elements p_{i} ∈ Ω − {p_{0}} indexed by a set I of the same cardinality as Ω. Let y ∈ Self(Ω) be the map sending all elements to p_{0}, while for each i ∈ I, let x_{i} be the map sending everything except p_{i} to p_{0}, and fixing p_{i}. Then we see that

(29) for i, j ∈ I, x_{i}x_{j} = y if and only if i ≠ j.

This gives card(Ω) such elements x_{i}; but an application of Theorem 5.4, following the same pattern as the two preceding results, shows that we cannot get a family of > card(Ω) such elements; hence

Corollary 5.7. No monoid containing an element y, and a family of elements x_{i}, distinct from y, indexed by a set I of cardinality > card(Ω), and satisfying (29), is embeddable in Self(Ω).

In our examples of nonembeddability using the group conditions (23)-(24) and (25), and the monoid conditions (29), we could have asserted much more than the existence of a chain with card(I) jumps. For example, given an I-tuple of elements satisfying (25), distinct subsets of {x_{i} | i ∈ I} have centralizers containing distinct subsets of the y_{i} (indexed by the complementary subsets of I), so we in fact get a copy of the whole partially ordered set P(I) in L_{G,1}^{=}; and the corresponding observations hold for the other two examples.

However, there are examples that give large chains of solution sets without (as far as I can see) giving so much more as well. If we take the group or monoid presented by (10), respectively (11), with I a cardinal κ, then it will have a chain of centralizers, respectively fixed sets, order-isomorphic to κ (as well as one of the opposite order type), but there is no apparent reason why it should have, say, any large antichain of solution sets.

It is interesting that while the constructions of (10) and (11) with I = ℝ give, as we saw earlier, groups and monoids embeddable in Sym(ω), respectively Self(ω), the above paragraph shows that the contrary is true for the same constructions with I = card(ℝ) as a well-ordered set. We likewise get nonembeddability when I = ℝ×2 under lexicographic order (since it also has uncountably many jumps), and for ℝ×ℝ under lexicographic order (since this contains the preceding ordered set).

Here is another application of our observations on (10). For every real number c, let G_{c} be the group presented by generators x_{r}, y_{r} (r ∈ ℝ) and relations

(30) x_{r} y_{s} = y_{s} x_{r} for all r, s ∈ ℝ such that s ≥ r + c.

Clearly, each G_{c} is isomorphic to G_{0}, by an isomorphism that fixes the x_{r} and takes each y_{s} to y_{s−c}. But we have noted that (by Theorem 3.4) G_{0} is embeddable in Sym(ℵ_{0}); hence so is every G_{c}. Now let G_{0^{+}} denote the group with the same generators, but having for relations the union of the sets of relations defining G_{c} for all c > 0; in other words,

(31) x_{r} y_{s} = y_{s} x_{r} for all r, s ∈ ℝ with s > r,

and let us define therein, for every c ∈ ℝ, the centralizer subgroups

(32) S_{c} = {g ∈ G_{0^{+}} | (∀ s ≥ c) gy_{s} = y_{s} g}, S_{c^{+}} = {g ∈ G_{0^{+}} | (∀ s > c) gy_{s} = y_{s} g}.

I claim that these form a chain, with jumps S_{c} ⊂ S_{c^{+}}, and with inclusions S_{c^{+}} ⊂ S_{d} whenever c < d. Indeed, S_{c} ≠ S_{c^{+}} because x_{c} ∈ S_{c^{+}} − S_{c}, and similarly S_{c^{+}} ≠ S_{d} by considering x_{e} for any e with c < e < d. This chain is isomorphic to ℝ × 2, so G_{0^{+}} is not embeddable in Sym(ℵ_{0}), though it is a direct limit, via surjective homomorphisms, of the groups G_{c} (c > 0), which are so embeddable.

Though a positive answer seems implausible, let us ask

Question 5.8. Is the criterion of the first paragraph of Theorem 5.4 also sufficient for a group of cardinality ≤ 2^{card(Ω)} to be embeddable in Sym(Ω) ? If so, is it sufficient that it hold for all finite J ? For J = 1 ?

In an earlier version of this note, I asked the same questions for Self(Ω); but the possibility of an affirmative answer is now precluded by a result of Wehrung [19], showing that Self(Ω)^{op} cannot be embedded in Self(Ω); indeed, since the lattices L_{Self(Ω), J}^{=} and L_{Self(Ω)^{op}, J}^{=} are isomorphic, that result shows that no condition on the lattices L_{M, J}^{=} can be equivalent to embeddability of M in Self(Ω). Conceivably, however, one could construct lattices of solution sets not using all the sets S_{v=w}, but some subfamilies of these that are not invariant under reversing the orders of factors in the words u and v, such that conditions on these solution sets would characterize embeddability in Self(Ω).

It is easy to formally strengthen Theorem 5.4 in several ways. First, since the sets S_{v=w} of (27) are closed in the function topology, so are finite unions of such sets, which we might write

(33) S_{(v_{1}=w_{1})∨···∨(v_{n}=w_{n})} = S_{v_{1}=w_{1}} ∪ ⋯ ∪ S_{v_{n}=w_{n}}.

So if we let L_{Sym(Ω), J}^{=,∨}, denote the lattice of arbitrary intersections of families of finite unions (33), these will also satisfy the conditions on chains given by Theorem 5.4.

Secondly, the conclusion of Theorem 5.4 only states one particular consequence of embeddability of our lattice of solution sets in the lattice of closed sets of a topology generated by ≤ card(Ω) elements. We will examine the latter condition further in an appendix, §12. Meanwhile, we ask

Question 5.9. If the criteria of Theorem 5.4 are not sufficient for a group X of cardinality ≤ 2^{card(Ω)} to be embeddable in Sym(Ω), do they become so if we replace the lattices L_{X, J}^{=} of that theorem by the larger lattices L_{X, J}^{=,∨}, and/or strengthen the condition on jumps in chains to the condition that our lattice of solution sets be embeddable as a partially ordered set in the lattice of closed subsets of a topological space with a basis of cardinality ≤ card(Ω) (cf. §12)?

Do there, at least, exist groups whose embeddability in Sym(Ω) is precluded by one of these strengthened conditions, but not by the conditions of Theorem 5.4? Here we may ask the same question for embeddability of monoids in Self(Ω).

We mentioned (following Question 4.3) de Bruijn’s result that every abelian group of cardinality ≤ 2^{card(Ω)} is embeddable in Sym(Ω). However, not every commutative monoid of cardinality ≤ 2^{card(Ω)} embeds in Self(Ω) : the presentations (11) give commutative monoids, but we saw that for I a cardinal > card(Ω), the resulting monoid is not so embeddable. So we ask

Question 5.10. Which varieties V of monoids have the property that every monoid in V of cardinality ≤ 2^{card(Ω)} is embeddable in Self(Ω) ?

By de Bruijn’s result on abelian groups, this is true of every variety of commutative monoids satisfying an identity x^{n} = 1, since such monoids are essentially abelian groups of exponent n, hence embeddable in Sym(Ω) as groups. I don’t know any other examples.

Returning to groups, suppose we write Sym_{<}(Ω) ⊂ Sym(Ω) for the normal subgroup of permutations that move fewer than card(Ω) elements. De Bruijn [7, Theorem 4.4] showed that Sym(Ω) could be embedded in Sym(Ω)/Sym_{<}(Ω), while McKenzie [16, Corollary 3] showed that Sym(Ω)/Sym_{<}(Ω) contains a restricted direct product of > card(Ω) copies of itself, and hence, by Corollary 5.5, cannot be embedded in Sym(Ω).

Question 5.11. What restrictions does embeddability in Sym(Ω)/Sym_{<}(Ω) imply for a group of cardinality ≤ 2^{card(Ω)} ?

Under the assumption of the General Continuum Hypothesis, Jónsson [14] shows, inter alia, that for every uncountable cardinal κ there exists a group of cardinality κ which contains isomorphic copies of all groups of cardinality κ. We have seen that Sym(Ω) is not such a group for κ = 2^{card(Ω)}. Felgner and Haug [12] show that under certain set-theoretic hypothesis, neither is Sym(Ω)/Sym_{<}(Ω).

6 Restrictions on lattices embeddable in Equiv(Ω).

If we want to adapt the technique of the preceding section to get restrictions on lattices embeddable in the lattice Equiv(Ω) of equivalence relations on Ω, we must decide what topology on that lattice to use in place of the function topology. One approach is to regard binary relations on Ω as elements of P(Ω × Ω) = 2^{Ω×Ω}, i.e., as functions Ω × Ω → 2 = {0, 1}, and use the function topology on that set induced by the discrete topology on 2. A subbasis of open subsets of P(Ω × Ω) under this topology is given by the sets

(34) U_{p,q} = {R ∈ P(Ω × Ω) | (p, q) ∈ R} and cU_{p,q} = {R ∈ P(Ω × Ω) | (p, q) ∉ R}.

We see that each of these sets is clopen (closed and open) in the topology so defined, and that this subbasis has cardinality card(Ω).

By abuse of notation, in speaking of subsets of Equiv(Ω) let us write U_{p,q} for U_{p,q} ∩ Equiv(Ω) and cU_{p,q} for ^{c}U_{p,q} ∩ Equiv(Ω) (just as, in introducing the function topology on Self(Ω), we earlier wrote U_{p,q} for what we would now describe as U_{p,q} ∩ Self(Ω)).

In this topology, one finds that the meet operation, i.e., intersection as subsets of Ω × Ω, is continuous, but that the join operation is not. To see the first fact, note that under the map

(35) ∧ : Equiv(Ω) × Equiv(Ω) → Equiv(Ω),

the inverse image of every U_{p,q} is the open rectangle U_{p,q} × U_{p,q}, while the inverse image of ^{c}U_{p,q} is the union (^{c}U_{p,q} × Equiv(Ω)) ∪ (Equiv(Ω) × ^{c}U_{p,q}), and both these sets are open. Under the operation

(36) ∨ : Equiv(Ω) × Equiv(Ω) → Equiv(Ω),

the inverse image of U_{p,q} is still open: it is an infinite union of finite intersections of sets of the forms U_{r,s} × Equiv(Ω) and Equiv(Ω) × U_{r,s}, one such intersection for each finite chain of relations which, if they hold in a pair of equivalence relations on Ω, witness the conclusion that (p, q) belongs to the join of those equivalence relations. But the inverse image of ^{c}U_{p,q} becomes, by the same reasoning, an infinite intersection of clopen sets, which will not be open. (Essentially because no finite set of relations and negations of relations can witness the absence of (p, q) from the join of two equivalence relations.)

There are two ways to respond to this difficulty. One is to formulate a criterion in terms of words in the meet operation alone. This corresponds to regarding Equiv(Ω) as a meet-semilattice, Equiv(Ω)_{∧}. In the notation of Definition 5.3, we then look at the lattices L_{Equiv(Ω)_{∧}, J}^{=}, and get

Theorem 6.1. Let J be any set of cardinality ≤ card(Ω). Then L_{Equiv(Ω)_{∧}, J}^{=} contains no chains with > card(Ω) jumps. Hence for any lower semilattice A embeddable in Equiv(Ω)_{∧}, the lattice L_{A, J}^{=} contains no chains with > card(Ω) jumps. In particular, for any lattice A embeddable in Equiv(Ω), the lattice L_{A_{∧}, J}^{=} has no such chains.

Proof. This can be gotten by the same method as Theorem 5.4, or deduced therefrom using Lemma 4.6(ii).

The following application of this result shows that the meet-join asymmetry we have come up against is real; and the second statement gives the promised example showing that the analog of Lemma 4.6(ii) with Equiv(Ω)_{∨} in place of Equiv(Ω)_{∧} is false.

Proposition 6.2. The largest cardinality of a set I such that Equiv(Ω) contains an element z and elements x_{i} ≠ z (i ∈ I) satisfying

(37) x_{i} ∧ x_{j} = z for all distinct i, j ∈ I

is card(Ω).

However, Equiv(Ω) contains an element w and 2^{card(Ω)} elements y_{i} ≠ w such that

(38) y_{i} ∨ y_{j} = w for all distinct i, j ∈ I.

Proof. The upper bound in the first assertion follows from the preceding theorem, by the same reasoning used to get our corollaries to Theorem 5.4. To see without calling on Whitman’s Theorem that there does, however, exist such a family of cardinality card(Ω), let z be the discrete equivalence relation on Ω, choose an element p_{0} ∈ Ω and a family of card(Ω) distinct elements p_{i} ∈ Ω − {p_{0}}, and for each i, let x_{i} be the equivalence relation that relates p_{0} with p_{i}, but relates no other distinct elements of Ω.

To get the second assertion, let w be the indiscrete equivalence relation, and let the y_{i} be all the equivalence relations on Ω having exactly two equivalence classes.

The other way to deal with the fact that the join operation on Equiv(Ω) is not continuous in the topology with subbasis (34) is to weaken the topology. By the discussion following (34), both operations are continuous in the topology having the sets U_{p,q} as a subbasis of open sets. This topology is not T_{1}: for every x ∈ Equiv(Ω), we see that the closure of {x} is the set of all equivalence relations ≤ x.

As a consequence, the diagonal subset of Equiv(Ω) × Equiv(Ω) is not closed; hence, though arbitrary lattice words v and w with constants in Equiv(Ω) still induce continuous operations on Equiv(Ω), it does not follow that the sets S_{v=w} = {x ∈ Equiv(Ω) | v(x) = w(x)} are closed.

However, let us make

Definition 6.3. For any lattice A, any set J, any lattice word v in a J-tuple of variables with constants in A, and any element c ∈ A, let

(39) S_{v≤c} = {a = (a_{j})_{j∈J} ∈ A^{J} | v(a) ≤ c} ⊆ A^{J},

and let us call such sets principal lower solution sets in A^{J}. A lower solution set will mean the intersection of an arbitrary family of principal lower solution sets. We shall denote by L_{A, J}^{≤const} the lattice of all lower solution sets in A^{J}.

As in Definition 5.3, we allow the empty intersection, so that L_{A, J}^{≤const} is indeed a complete lattice.

Any principal lower solution set S_{v≤c} in Equiv(Ω)^{J} is the inverse image under the continuous map v : Equiv(Ω)^{J} → Equiv(Ω) of the closed set {d | d ≤ c} ⊆ Equiv(Ω), hence is closed, making Lemma 5.1 applicable. Thus we get

Theorem 6.4. Let J be any set of cardinality ≤ card(Ω). Then L_{Equiv(Ω), J}^{≤const} contains no chains with

> card(Ω) jumps. Hence for any lattice A embeddable in Equiv(Ω), L_{A, J}^{≤const} contains no such chains.

To get applications of this result that are not consequences of Theorem 6.1, one has to use sets S_{v≤c} determined by words v that involve both meets and joins; in fact, that involve meets of joins. For if v does not involve meets of joins, we can write v = ⋁_{r=1}^{m} ⋀_{s=1}^{n_{r}} a_{r,s}, where the a_{r,s} are variables and/or constants, and m, n_{1}, …, n_{m} are positive integers (some of which may be 1). Then we see that the relation v ≤ c is equivalent to the conjunction of the relations ⋀_{s=1}^{n_{r}} a_{r,s} ≤ c (r = 1, …, m), and each of these can be rewritten c ∧ ⋀_{s=1}^{n_{m}} a_{r,s} = ⋀_{s=1}^{n_{m}} a_{r,s}. Hence S_{v≤c} ∈ L_{Equiv(Ω)_{∧}, J}^{=}, and we are reduced to Theorem 6.1.

Perhaps workers in lattice theory will be able to see interesting applications of Theorem 6.4 that do not reduce to Theorem 6.1.

We remark that while Theorems 6.1 and 6.4 show that L_{Equiv(Ω)_{∧}, J}^{=} and L_{Equiv(Ω), J}^{≤const}, contain no wellordered chains of cardinality > card(Ω), the second paragraph of Proposition 6.2 shows that L_{Equiv(Ω), J}^{=} and L_{Equiv(Ω)_{∨}, J}^{=} do contain such chains.

7 Monoids embeddable in Rel(Ω).

In this section we return to monoids, but focus, not on Self(Ω), but on its “wild sibling” Rel(Ω), the monoid of all binary relations on Ω, under relational composition:

(40) x y = {(q, p) ∈ Ω × Ω | (∃ r ∈ Ω) (q, r) ∈ x, (r, p) ∈ y}.

Note that when specialized to functions, the above definition of composition, together with our convention that functions act on the left and are composed accordingly, requires that we identify each function f with the set of ordered pairs (f(p), p), rather than the more usual (p, f(p)).

Clearly, Rel(Ω) ≅ Rel(Ω)^{op}, and this monoid contains Self(Ω); hence it also contains an isomorphic copy of Self(Ω)^{op}. In fact, it is generated by Self(Ω) and the natural copy of Self(Ω)^{op}; for if R ∈ Rel(Ω) is nonempty, then since, as a subset of Ω × Ω, it has cardinality ≤ card(Ω), we can find maps f, g ∈ Self(Ω) such that R = {(f(p), g(p)) | p ∈ Ω}. Letting ḡ = {(p, g(p)) | p ∈ Ω} ∈ Self(Ω)^{op}, we easily verify that f ḡ = R. The empty relation, on the other hand, equals f̄g for any f and g having disjoint ranges.

The next result shows that monoids embeddable in Rel(Ω) are considerably less restricted than those embeddable Self(Ω) or Self(Ω)^{op}.

Proposition 7.1. Let w denote the indiscrete equivalence relation on Ω, and (as in the proof of Proposition 6.2) let y_{i} (i ∈ I) be the 2^{card(Ω)} distinct equivalence relations on Ω having exactly two equivalence classes. Then as members of Rel(Ω), these satisfy

(41) y_{i} y_{i} = y_{i} (i ∈ I),

(42) y_{i} y_{j} y_{i} = w (i ≠ j in I).

Hence L_{Rel(Ω),1}^{=} contains a well-ordered chain of cardinality 2^{card(Ω)}.

Proof. (41) is immediate. The verification of (42) is routine, but the reader may find the following way of visualizing it helpful. Given y_{i} and y_{j}, picture a Venn diagram for Ω, divided by a vertical line representing the partition into the two equivalence classes of y_{i} and a horizontal line representing the partition into the equivalence classes of y_{j}. Given (p, q) ∈ w = Ω × Ω, which we wish to show belongs to y_{i} y_{j} y_{i}, we may assume by adjusting our diagram that p lies in the upper left-hand box. Since y_{i} and y_{j} each have two equivalence classes, at least one of the lower boxes and at least one of the right-hand boxes are nonempty, and since y_{i} ≠ y_{j}, the lower right-hand box is not the only nonempty box other than the upper left-hand one. It is now easy to see that wherever q may lie in our diagram, we can get from p to it by crossing the vertical line at most once and the horizontal line at most once, hence that (p, q) lies in either y_{i} y_{j} or y_{j} y_{i}. In either case, it lies in y_{i} y_{j} y_{i}, as claimed.

However, (41) shows that y_{i} y_{i} y_{i} ≠ w, and the contrast between this inequality and (42) allows us to get, as in the proofs of Corollaries 5.5 and 5.6, a well-ordered chain of cardinality 2^{card(Ω)} in L_{Rel(Ω),1.}^{=}

The composition operation (40) of Rel(Ω) resembles the join operation of Equiv(Ω) in being continuous in the topology on Rel(Ω) with subbasis of open sets consisting of the sets U_{p,q} (defined in (34)), but not in the Hausdorff topology with subbasis of open sets U_{p,q} and ^{c}U_{p,q}. Indeed, though composition of relations is simpler to describe than the join of equivalence relations, it is still true that no specification of whether some finite number of pairs belong to each of two relations can tell us that (p, q) does not belong to their composite. For Rel(Ω), there is no analog of our ploy of restricting attention to the meet operation of Equiv(Ω); so let us go directly to the weaker topology. As in the case of Equiv(Ω), we can conclude that Lemma 7.2. For J any set of cardinality ≤ card(Ω), L_{Rel(Ω), J}^{≤const} contains no chains with > card(Ω) jumps.

Unfortunately, I don’t see how to use this result in studying the structures of monoids embeddable in the monoid Rel(Ω), for the definition of L_{Rel(Ω), J}^{≤const} makes use of the ordering of Rel(Ω) by inclusion, and, unlike the order relation on a lattice, this has no description in terms of its algebra operations. Of course, if we throw in order as additional structure, then Lemma 7.2 yields restrictions on embeddability. Let us record this and another consequence of Lemma 7.2, without looking for examples, then return to the question of embeddability as pure monoids.

By a partially ordered monoid (M, ≤), let us understand a monoid M given with a partial ordering ≤, such that for all x, y, z ∈ M,

(43) x ≤ y ⟹ xz ≤ yz, x ≤ y ⟹ zx ≤ zy.

An embedding of partially ordered monoids f : (M, ≤_{M}) → (N, ≤_{N}) will mean a monoid embedding f : M → N such that the partial ordering on M induced by ≤_{N} under f is precisely ≤_{M} . Clearly, Lemma 7.2 gives

Corollary 7.3. If a partially ordered monoid (M, ≤) is embeddable in (Rel(Ω), ⊆), then for any set J of cardinality ≤ card(Ω), the complete lattice L_{(M,≤), J}^{≤const} contains no chains with > card(Ω) jumps.

To formulate another consequence of Lemma 7.2, let us define, for M a monoid with a distinguished element z, J a set, and v any monoid word in a J-tuple of variables and arbitrary constants from M, the set S_{v=z} = {a = (a_{j})_{j∈J} ∈ M^{J} | v(a) = z} ⊆ M^{J}, and let L_{(M,z), J}^{=z} ⊆ P(M^{J}) denote the lattice of all intersections of families of sets of this sort. If (M, z) and (M′, z′) are such pairs, a homomorphism (M, z) → (M′, z′) will mean a monoid homomorphism M → M′ carrying z to z′.

Corollary 7.4. Let M be a monoid with a zero element z (an element satisfying zx = z = xz for all x ∈ M), such that (M, z) is embeddable in (Rel(Ω), ∅), and let J be a set of cardinality ≤ card(Ω). Then the complete lattice L_{(M,z), J}^{=z} contains no chains with > card(Ω) jumps.

Proof. In Rel(Ω)^{J}, any set of the form S_{v=∅} can clearly also be described as S_{v≤∅}, whence the assertion follows immediately from Lemma 7.2.

A way of getting restrictions on embeddability in Rel(Ω) without bringing in additional structure is to note, as we did in §5 for Self(Ω), that any monoid homomorphism from a group into Rel(Ω) will land in the group of invertible relations, which is again Sym(Ω). Hence our restrictions on groups embeddable in Sym(Ω) are also restrictions on the groups of invertible elements of monoids embeddable in Rel(Ω).

But in fact, we can use the group Sym(Ω) of invertible elements of Rel(Ω) in a way that brings in noninvertible elements as well. Note that the function topology on Self(Ω), and hence on Sym(Ω), is the restriction thereto both of the topology of (34), and of the weaker topology having only the sets U_{p,q} as subbasis of open sets. (In Self(Ω), the set ^{c}U_{p,q} can be written as ⋃_{p′≠p} U_{p′,q}, so the topology generated by the sets U_{p,q} also contains the complementary sets.) This immediately gives case (i) of the next lemma. Case (ii), the one we shall make use of, is more surprising. (We shall not use the final parenthetical strengthening of (ii).)

Lemma 7.5. The restrictions of the monoid multiplication of Rel(Ω) to maps

(44) Sym(Ω) × Rel(Ω) → Rel(Ω) and Rel(Ω) × Sym(Ω) → Rel(Ω)

are continuous if we put the function topology on Sym(Ω), and put on Rel(Ω) the topology with subbasis of open sets consisting either of

(i) the sets U_{p,q}, or (ii) the sets U_{p,q} and ^{c}U_{p,q}. (This remains true if we replace Sym(Ω) by Self(Ω) in the second map of (44), though not in the first.)

Proof. As noted, continuity in the topology determined by (i) follows from the continuity of the multiplication of Rel(Ω) in that topology. This also gives half of continuity in the topology specified in (ii), namely openness of the inverse images of the sets U_{p,q}. We shall prove the corresponding statement for ^{c}U_{p,q} for the second map in (44) with Sym(Ω) replaced by Self(Ω). The case where Sym(Ω) is left unchanged follows immediately, and the first statement of (44) then follows by reversing coordinates in ordered pairs.

Note that a necessary and sufficient condition for a composite xa (x ∈ Rel(Ω), a ∈ Self(Ω)) to lie in cU_{p,q}, i.e., not to contain (p, q), is that for the unique r ∈ Ω such that (r, q) ∈ a, we have (p, r) ∉ x. Hence the inverse image of ^{c}U_{p,q} under the above composition map is the union ⋃_{r∈Ω} (^{c}U_{p,r} × (U_{r,q} ∩ Self(Ω))). This set is open in Rel(Ω) × Self(Ω), as claimed.

To get the negative part of the final parenthetical assertion, assume without loss of generality that ω ⊆ Ω. For each n ∈ ω, let x_{n} ∈ Rel(Ω) be the partial function which sends 0 to n and does nothing else, and let a ∈ Self(Ω) be the function sending all elements to 0. Then for all n, a x_{n} = x_{0}, hence lim_{n→∞} a x_{n} = x_{0}. On the other hand, lim_{n→∞} x_{n} = ∅, the empty relation, which when left multiplied by a gives ∅ ≠ x_{0}. So composition is not continuous in the Hausdorff topology of (ii).

From the operations (44) and the group operations of Sym(Ω), we can form words in a mixture of Sym(Ω)- and Rel(Ω)-valued elements; but any such word can involve, at most, either one occurrence of a Rel(Ω)-valued variable or one occurrence of a non-Sym(Ω)-valued constant, since the operations (44) do not allow the multiplication of two non-Sym(Ω)-valued elements. (Here by a “Rel(Ω)-valued variable” I mean a variable that is allowed to range over all of Rel(Ω), taking on both invertible and noninvertible values. Constants, on the other hand, have specific values rather than ranges, so for these the relevant concept is that of a non-Sym(Ω)-valued constant, i.e., a noninvertible element of Rel(Ω).) By Lemma 7.5, if we take a family of such words, possibly involving many Rel(Ω)-valued variables and non-Sym(Ω)-valued constants altogether (though with at most one of these per word), and a set of equations in these words, then its solution set is closed in the Hausdorff topology defined by the subbasis (ii). Hence we can apply Lemma 5.1 and get restrictions on the lattice of such solution sets, which imply the same restrictions on the corresponding lattice obtained from any monoid embeddable in Rel(Ω).

It is not clear to me whether so allowing more than one Rel(Ω)-valued variable or constant in our system of equations actually contributes to the generality of this result. Note that if we have a system of equations in several such variables and constants, then any equation involving different Rel(Ω)-valued variables on the two sides, say x on the left and y on the right, will allow us to solve for y in terms of x and the Sym(Ω)-valued variables and constants (since the latter can all be inverted and brought to the left side of the equation); and we can then substitute the resulting expression for all occurrences of y in the remaining equations, and so eliminate y from the system. On the other hand, our interest is not in the solution set of a single system of equations but in the relation between solution sets of many such systems, and a variable that can be eliminated from one of these will not in general be eliminable from all of them. So if the consequences of our conditions on lattices of solution sets can indeed be reduced to the case where there is only one Rel(Ω)-valued variable, the argument by which this reduction is done may be nontrivial.

Leaving it to others to determine whether such a reduction is possible, I will, for simplicity, record here only the statements for systems with at most one Rel(Ω)-valued-variable.

Theorem 7.6. Let J be any set of cardinality ≤ card(Ω).

Let L denote the lattice of solution sets in Sym(Ω)^{J} × Rel(Ω) of systems of equations in a J-tuple of Sym(Ω)-valued variables, and a single Rel(Ω)-valued variable which appears at most once on each side of any equation, together with arbitrary Sym(Ω)-valued constants.

Let L′ similarly denote the lattice of solution sets in Sym(Ω)^{J} of systems of equations having on each side a word in a J-tuple of Sym(Ω)-valued variables, arbitrary Sym(Ω)-valued constants, and at most one occurrence of a Rel(Ω)-valued constant.

Then neither of these lattices contains a chain with > card(Ω) jumps. Hence for any monoid M embeddable in Rel(Ω), the corresponding restrictions hold, with the group U(M) of invertible elements of M taking the place of Sym(Ω).

Simple examples of equations of the sort arising above are stabilizer relations gx = x and xg = x (x ∈ M, g ∈ U(M)), and more generally, gxg′ = x (x ∈ M, g, g′ ∈ U(M)). Here is an example based on relations gx = x.

Recall that a left zero element in a monoid M means an element z satisfying zx = z for all x ∈ M.

Corollary 7.7. Let I be a set, let G be the restricted direct product of an I-tuple of copies of the group Z_{2}, with generators g_{i} (i ∈ I) (i.e., the additive group of the vector space with basis {g_{i} | i ∈ I} over the field of two elements), and let M be the monoid whose group of invertible elements is this group G, and whose other elements, denoted z_{i}, z′_{i} (i ∈ I), are left zero elements whose behavior under the left action of G is described by

(45) Left multiplication by g_{i} interchanges z_{i} and z′_{i}, and fixes all z_{j} and z′_{j} with j ≠ i.

Then M is embeddable in Rel(Ω) if and only if card(I) ≤ card(Ω).

Proof. It is straightforward to verify that the above operations define a monoid, which has cardinality ≤ max(card(I), ℵ_{0}), and so is embeddable in Self(Ω) ⊆ Rel(Ω) if card(I) ≤ card(Ω). To prove the “only if” part of the conclusion, assume I is a cardinal κ > card(Ω). For each α ∈ κ, let S_{α} = {x ∈ M | (∀ β > α) g_{β} x = x}. Note that z_{β} ∈ S_{α} if and only if β ≤ α, so the S_{α} form a well-ordered chain of cardinality κ > card(Ω). By the “L” case of Theorem 7.6 (with J = 0), this precludes embeddability in Rel(Ω).

In proving the above corollary we could, alternatively, have used the z_{α} as monoid-valued constants, and let the g in the relations g z_{α} = z_{α} be an invertible-element-valued variable, getting a system to which the “L′” case of Theorem 7.6 with J = 1 applied.

Question 7.8. Can one give stronger necessary conditions for embeddability of a monoid M of cardinality ≤ 2^{card(Ω)} in Rel(Ω) than those of Theorem 7.6?

In particular, suppose we define the left, right, and 2-sided stabilizers of an element x of a monoid M as {y ∈ M | yx = x}, {y ∈ M | xy = x}, and {(y, y′) ∈ M^{2} | yxy′ = x}. Does Rel(Ω) have any chains of intersections of such stabilizers with > card(Ω) jumps? What if we restrict y and y′ here to left invertible or to right invertible elements?

Are there any monoids of cardinality ≤ 2^{card(Ω)} having no invertible elements other than 1 (or having ≤ card(Ω) invertible elements) which are not embeddable in Rel(Ω) ?

For card(I) > card(Ω), is the monoid of Corollary 7.7 ever embeddable as a semigroup in Rel(Ω) ?

One kind of noninvertible elements one might look at in approaching these questions are the idempotents, since for e idempotent, the solution sets of xe = x and ex = x are particularly natural objects. Idempotents in Rel(Ω) come in more forms than one might expect. Obvious examples are equivalence relations, subsets of the identity relation, graphs of retractions of Ω onto subsets, and the opposites of such graphs; these four constructions can also be mixed in fairly natural ways. For less obvious examples, note that (i) for any partial ordering, ≤, on Ω with no jumps (e.g., the ordinary ordering on the set of rational numbers), the graph of the relation “<” is idempotent, though it has trivial intersection with the identity relation; and (ii) for any nondisjoint subsets X and Y of Ω, the set X × Y ⊆ Ω × Ω is an idempotent relation.

We have not written down the positive embeddability result analogous to Theorem 3.1, i.e., the embeddability in Rel(Ω) of monoids F (2^{card(Ω)}) for appropriate functors F, since this follows from Theorem 3.1 and the inclusion Self(Ω) ⊆ Rel(Ω). It would, of course, be of interest if one could get stronger results of this sort for Rel(Ω) than for Self(Ω). I also don’t know the answer to

Question 7.9. Is Rel(Ω) ∐Rel(Ω) embeddable as a monoid in Rel(Ω) ?

(If so, then by the usual argument, Rel(Ω) in fact contains a coproduct of 2^{card(Ω)} copies of itself.)

Here are some partial positive results on that question.

Let 1_{Ω} ∈ Rel(Ω) denote the identity element, that is, the diagonal subset of Ω × Ω. Let us say that elements g, h ∈ Rel(Ω) “differ off the diagonal” if g − 1_{Ω} ≠ h − 1_{Ω} (where “−” denotes set-theoretic difference); and for a subset X ⊆ Rel(Ω), let us say “the members of X are distinguishable off the diagonal” if every pair of distinct elements of X differs off the diagonal.

Lemma 7.10. There exists a monoid homomorphism f : Rel(Ω) ∐Rel(Ω) → Rel(Ω) with the property that whenever M and N are submonoids of Rel(Ω), each of which has the property that its members are distinguishable off the diagonal, then the restriction of f to a homomorphism M ∐N → Rel(Ω) is an embedding.

Proof. Let us understand a “relational action” of a monoid M on a set X to mean a homomorphism M → Rel(X). Paralleling the proof of Lemma 4.1(ii), we shall construct a relational action of Rel(Ω)∐Rel(Ω) on the disjoint union of a family of copies of Ω × ω, where the family is again indexed by the group Sym_{fin}(Ω × ω), such that the restriction of this action to any submonoid M ∐N as in the statement of the lemma is faithful.

Let the “natural relational action” of Rel(Ω) on Ω×ω be defined to take each g ∈ Rel(Ω) to the relation on Ω×ω consisting of all pairs ((q, k), (p, k)) with (q, p) ∈ g and k ∈ ω. Let α, β be the two coprojections Rel(Ω) → Rel(Ω)∐Rel(Ω). For each g ∈ Rel(Ω), let us send α(g) to the natural relational action of g on each copy of Ω × ω, while letting β(g) act on the copy of Ω × ω indexed by each t ∈ Sym_{fin}(Ω × ω) via the conjugated relation t g t^{−1}. To complete our proof, we need to show that for M and N as in the statement of the lemma, if (13) and (14) are distinct elements of M ∐N ⊆ Rel(Ω)∐Rel(Ω), then there exists t ∈ Sym_{fin}(Ω × ω) such that the two relations (15) on Ω × ω are distinct.

As in our previous argument, we assume that the length of (13), which we will call n, is at least the length of (14). Moreover, we assume that if these lengths are equal, and if αs and βs occur in the same positions in both expressions, then at the first position k from the right where (13) and (14) differ, g_{k} contains some nondiagonal ordered pair which does not lie in h_{k}. Since g_{k} and h_{k} differ off the diagonal, we can achieve this by interchanging (13) and (14) if necessary. We now choose, for each k ∈ {1, …, n}, a nondiagonal pair (q_{k}, p_{k}) ∈ g_{k} (which must exist, because g_{k} is not the identity, hence is distinguishable from the identity off the diagonal), using, when possible, a pair not also contained in h_{k}; and we define t as in (18), except that wherever (18) shows an element g_{k}(p_{k}), we now use q_{k}. The same considerations as in the proof of Lemma 4.1 show that the first product in (17), but not the second, contains the pair ((q_{n}, n+1), (p_{0}, 0)); so these two products are distinct relations on Ω × ω, completing the proof.

Here are some consequences.

Corollary 7.11. (i) Self(Ω) ∐Self(Ω)^{op} is embeddable in Rel(Ω).

(ii) Let Rel(Ω)_{≥1} ⊆ Rel(Ω) denote the submonoid of relations that contain the diagonal (the reflexive relations). Then Rel(Ω)_{≥1} ∐ Rel(Ω)_{≥1} is embeddable in Rel(Ω)_{≥1}. Hence the coproduct of 2^{card(Ω)} copies of Rel(Ω)_{≥1} is embeddable in Rel(Ω)_{≥1}.

(iii) Let Rel^{semi}(Ω) denote the underlying semigroup of Rel(Ω). Then the semigroup coproduct Rel^{semi}(Ω) ∐Rel^{semi}(Ω) is embeddable in Rel^{semi}(Ω). Hence the semigroup coproduct of 2^{card(Ω)} copies of Rel^{semi}(Ω) is embeddable in Rel^{semi}(Ω).

Proof. (i) is immediate from the lemma, since both Self(Ω) and the natural copy of Self(Ω)^{op} in Rel(Ω) (gotten by taking the opposite relations to all members of Self(Ω)) have the property that their members are distinguishable off the diagonal.

In (ii), Lemma 7.10 immediately gives embeddability of Rel(Ω)_{≥1} ∐Rel(Ω)_{≥1} in Rel(Ω). Moreover, we see that the construction of that lemma takes reflexive relations to reflexive relations, so the embedding lands in Rel(Ω)_{≥1}. The method of proof of Theorem 4.2 now allows one to work one’s way up to the coproduct of 2^{card(Ω)} copies.

To prove (iii) let us begin by constructing an embedding of Rel^{semi}(Ω) in the semigroup of relations on a set of the same cardinality as Ω, by relations that are distinguishable from each other and from the identity relation off the diagonal.

We first have to declaw the empty relation; so let z be an element not in Ω, and let us embed Rel(Ω) in Rel(Ω ∪ {z}) by sending each relation g to g ∪ {(z, z)}; this is an embedding of monoids whose image consists of nonempty relations.

We now map Rel^{semi}(Ω ∪ {z}) into Rel^{semi}((Ω ∪ {z}) × 2) by

(46) g ↦ {((q, i), (p, j)) | (q, p) ∈ g; i, j ∈ 2}.

This construction is easily seen to respect composition, and to take distinct nonempty relations to relations that differ off the diagonal both from each other and from 1_{Ω∪{z}}. The image of the composite map Rel^{semi}(Ω) → Rel^{semi}(Ω ∪ {z}) → Rel^{semi}((Ω ∪ {z}) × 2) is in particular a subsemigroup S ⊆ Rel^{semi}((Ω ∪ {z}) × 2) isomorphic to Rel^{semi}(Ω). Applying Lemma 7.10 with S ∪ {1} in the role of both M and N, we get an embedding of monoids (S ∪ {1})∐(S ∪ {1}) → Rel(Ω), which, restricted to the subsemigroup generated by the two copies of S, gives the desired embedding of semigroups. As before, the method of §4 allows us to push this up to an embedding of a 2^{card(Ω)}-fold coproduct of copies of Rel^{semi}(Ω) in Rel^{semi}(Ω).

It would be nice if we could carry the idea of part (iii) of the above corollary further. If we could find a monoid embedding φ : Rel(Ω) → Rel(Ω′) with card(Ω′) = card(Ω), such that images of distinct elements were distinguishable off the diagonal, then an application of Lemma 7.10 would give us our desired embedding Rel(Ω)∐Rel(Ω) → Rel(Ω). But when we attempt to construct such a φ, we run into difficulty trying to simultaneously

(a) make it carry the identity relation 1_{Ω} to 1_{Ω′},

(b) handle relations which are properly contained in 1_{Ω}, and

(c) handle relations which are both infinitely-many-to-one and one-to-infinitely-many. Part (iii) of the above corollary showed that we could get an embedding if we dropped the requirement (a). The following result (strengthening part (ii) of that corollary) shows the same if we instead drop (b), and the result after that will do the same for (c).

Lemma 7.12. There exists a monoid homomorphism f′ : Rel(Ω) ∐Rel(Ω) → Rel(Ω) with the property that whenever M and N are submonoids of Rel(Ω), neither of which contains a proper subrelation of 1_{Ω}, then the restriction of f′ to a homomorphism M ∐N → Rel(Ω) is an embedding.

Proof. Let φ : Rel(Ω) → Rel(Ω^{2}) take each g ∈ Rel(Ω) to {((p, p′), (q, q′)) | (p, q), (p′, q′) ∈ g}. It is straightforward to verify that this is a monoid homomorphism. We shall show that if g, h ∈ Rel(Ω) are distinct elements which are not both subrelations of 1_{Ω}, then φ(g) and φ(h) are distinguishable off the diagonal. This, together with Lemma 7.10, yields the desired result.

First, suppose g and h are themselves distinguishable off the diagonal. Then without loss of generality we may assume that (p, q) is contained in g but not h for some p ≠ q, and we see that ((p, p), (q, q)) belongs to φ(g) but not φ(h). On the other hand, if g and h are not distinguishable off the diagonal, then since they are not both subrelations of 1_{Ω}, there must be some (p, q) with p ≠ q that is contained in both of them. Also, since g ≠ h, some (r, r) (r ∈ Ω) will belong to one of them but not the other; say to g but not h. Then we see that ((p, r), (q, r)) is a nondiagonal element belonging to φ(g) but not φ(h).

Finally, let us see what we can get if we sacrifice (c).

Given g ∈ Rel(Ω) and X ⊆ Ω, let us define the “image” set

(47) gX = {q ∈ Ω | (∃ p ∈ X) (q, p) ∈ g},

and let

(48) Rel_{fin←1}(Ω) = {g ∈ Rel(Ω) | (∀ p ∈ Ω) g{p} is finite}.

The arrow points to the left to show that we are defining this set in terms of the left action (47). We can clearly also describe (48) as the set of g such that for every finite X ⊆ Ω, the set gX is again finite. This shows Rel_{fin←1}(Ω) to be a submonoid of Rel(Ω), and it clearly acts faithfully – by functions, not relations – on P_{fin}(Ω). This gives us an embedding Rel_{fin←1}(Ω) → Self(P_{fin}(Ω)) ≅ Self(Ω). Of course, we also have Self(Ω) ⊆ Rel_{fin←1}(Ω); so embeddability of a monoid in Rel_{fin←1}(Ω) and in Self(Ω) are equivalent. This is the first assertion of the next lemma, and by the results of §4 it implies the second.

Lemma 7.13. Rel_{fin←1}(Ω) and Self(Ω) are each embeddable in the other.

Hence Rel_{fin←1}(Ω) contains a coproduct of 2^{card(Ω)} copies of itself as a monoid.

Let me record here a curious construction which I thought, at one point, would give a more elegant proof of our semigroup-embedding result, Corollary 7.11(iii). This did not quite work; but perhaps it is nonetheless of interest.

Consider the map θ : Rel^{semi}(Ω) → Rel^{semi}(P_{fin}(Ω)) defined by

(49) θ(g) = {(t, s) ∈ (P_{fin}(Ω))^{2} | t ⊆ gs}.

It is easy to verify that θ is a semigroup homomorphism. Moreover, every θ(g) contains all pairs (∅, t) with t ∈ P_{fin}(Ω), and hence differs from 1_{P_{fin}(Ω)} off the diagonal. For most pairs of distinct g, h ∈ Rel(Ω), one finds that θ(g) and θ(h) differ in the nondiagonal pairs of one of the forms ({p}, {q}), ({p}, {p, q}), or ({p, q}, {p}) that they contain. There are exceptions, however; for instance, if p ∈ Ω and we take g = {p} × Ω, h = {p} × (Ω − {p}); then θ(g) and θ(h) differ only with regard to the diagonal pair ({p}, {p}). Hence this construction is not itself a substitute for the one used in proving Corollary 7.11(iii). We can cure the problem using the “Rel(Ω) → Rel(Ω∪{z})” trick that was used (to cure a different problem) in the existing proof of that statement (and after this is done, the images of any two relations in fact differ in the pairs ({p}, {q, z}) that they contain); but I wouldn’t call the resulting proof more elegant than the one we used.

We end this section with a different sort of self-embeddability question for Rel(Ω).

Question 7.14. If e ∈ Rel(Ω) is an idempotent, and we regard eRe = {x ∈ Rel(Ω) | exe = x} as a monoid with identity element e, is this monoid always embeddable in Rel(Ω) ? (Cf. remarks on idempotents following Question 7.8.)

8 Restrictions on K-algebras embeddable in End_{K}(V).

Recall that V denotes a vector space with basis Ω over a field K. Since the endomorphism algebra End_{K}(V) is a K-linear analog of the monoid Self(Ω), we would hope to get restrictions on associative unital K-algebras embeddable in End_{K}(V) parallel to our restrictions on monoids embeddable in Self(Ω). We can do this – except that, where we would like to bound the number of jumps in a chain of solution sets by card(Ω) = dim_{K}(V), I only know how to bound it by card(V) = max(card(Ω), card(K)). The following theorem is proved exactly like Theorem 5.4, using the fact that addition and composition of members of End_{K}(V), and multiplication of these maps by members of K, are continuous in the function topology on End_{K}(V), regarded as a subset of Self(V).

Theorem 8.1. Let J be any set of cardinality ≤ card(V). Then L_{End_{K}(V), J}^{=} contains no chains with > card(V) jumps. Hence for any K-algebra A embeddable in End_{K}(V), the lattice L_{A, J}^{=} contains no such chains; in particular, it contains no well-ordered or reverse-well-ordered chains of cardinality > card(V).

In the hope of reducing the bound card(V) to card(Ω), we might try replacing the function topology on End_{K}(V) by some topology with a smaller basis of open sets; say one that defines its subbasic open sets not by considering the values of elements of End_{K}(V) at arbitrary elements of V, but only at the elements of our basis Ω. Unfortunately, each of these images still has card(V) possible values. However, a linear restriction on these images corresponds to a proper subspace of the space V of possible values, suggesting that the vector space dimension should still bound lengths of chains. On the other hand, the conditions on the coordinates of our elements induced by ring-theoretic relations are not necessarily linear. Perhaps one should seek bounds on the lengths of chains of solution sets by methods of algebraic geometry. Or perhaps one can get stronger results for relations that are multilinear, such as centralizer and annihilator relations, than for general relations.

In another direction, if K is a topological field such as the real or complex numbers, perhaps we could use the topology of that field instead of the discrete topology on our coordinates, and replace card(V) in the above theorem by max(card(Ω), κ) where κ is the least cardinality of a basis for the topology of K. We record these problems as

Question 8.2. In Theorem 8.1, can the bound card(V) be lowered to card(Ω) ? If not in general, what if we restrict attention to the lattice determined by K-linear or K-affine relations? Can one at least improve the bound card(V) if K admits a structure of topological field with a basis of < 2^{card(Ω)} open sets?

For one sort of system of relations, we can indeed get the expected bound.

Lemma 8.3. Any set of nonzero pairwise orthogonal idempotent elements of End_{K}(V) has cardinality ≤ card(Ω). Hence the same is true in any K-algebra embeddable in End_{K}(V).

In particular, End_{K}(V) does not contain a direct product of > card(Ω) nontrivial K-algebras.

Proof. Given an infinite family S of nonzero pairwise orthogonal idempotents, the images of these as endomaps of V form a set of subspaces of V whose sum is direct. Hence the dimension of that sum is at least card(S); so card(S) ≤ dim(V) = Ω.

To see the final sentence, note that in a direct product of K-algebras ∏_{i∈I} A_{i}, if e_{i} denotes the element with i-component 1 and all other components 0, then these are pairwise orthogonal idempotents.

On the other hand, some ways in which the behavior of End_{K}(V) for K large is indeed different from that of Self(Ω) will be noted at the end of §10.

Wehrung, paralleling his result mentioned earlier that Self(Ω) cannot be embedded in Self(Ω)^{op}, also shows in [19] that that End_{K}(V) cannot be embedded in End_{K}(V)^{op}. In fact, he shows that Self(Ω) cannot be embedded in the underlying multiplicative semigroup of End_{K}(V)^{op}, yielding both results!

9 Other directions for generalization.

In this note, we have concentrated on questions of embeddability in a small number of objects: Sym(Ω), Self(Ω), End_{K}(V), Equiv(Ω) and Rel(Ω), with brief observations on a few more: Sym(Ω)/Sym_{<}(Ω), (Rel(Ω), ⊆), (Rel(Ω), ∅), Rel^{semi}(Ω), and objects which we could write Equiv^{0}(Ω), Equiv^{1}(Ω) and Equiv^{0,1}(Ω), i.e., Equiv(Ω) regarded as a member of the variety of lattices with least and/or greatest element. Similar questions for other objects of the same flavor, for example the groups of automorphisms of various structures considered in [9], [10] and [11], the lattices of congruences of these objects, etc., would also be of interest.

Above, I quoted results from McKenzie [16] only in the forms in which they were relevant to the questions considered here; but that paper in fact considers the group Sym(Ω, β) of all permutations of Ω moving < β elements, for a fixed cardinal β, and many of the restrictions proved there are in terms of β, rather than card(Ω). This, too, represents a direction in which the present results might be generalized.

The variant of the technique of §3 illustrated in Theorem 3.4, based on considering functors on the category T.ord of totally ordered sets, rather than on Set, also admits wide generalization. Note that any algebra-valued functor F on T.ord can be extended to the category Poset of partially ordered sets, though usually not uniquely. (For instance, by taking each partially ordered set P to the colimit of the algebras F (C) as C ranges over all chains in P; or to the limit of the algebras F (C) as C ranges over all quotientsets of P given with total orderings that make the quotient-map isotone.) Hence in stating Theorem 3.4 and seeking generalizations, we could just as well let F be a functor on Poset. Still more generally, why not let it be defined on arbitrary preordered sets? Or on sets with an arbitrary binary relation? Or several binary relations? And for such generalizations, what would be the “best” analog of (9)? Not knowing what the useful generalizations would be, I have merely given a sample result.

The referee notes that de Bruijn’s groups with presentation (22)-(24) are the values of a functor on the category whose objects are sets I, and whose morphisms are one-to-one set-maps; this also applies to several other examples for which we proved nonembeddability results. Hence that domain category is not good from the above point of view. A repeated use that we made of non-one-to-one maps in the arguments of §3 was in getting left inverses to one-to-one maps with nonempty domains. The fact that such inverses exist has the consequence (also pointed out by the referee) that our key condition (9) is equivalent to the condition that F respect direct limits.

A question I have not thought much about, but to which some of the techniques we have introduced above should be applicable, is

Question 9.1. What can be said about groups A embeddable in (∏_{n∈ω} Sym(n))^{Ω}, monoids A embeddable in (∏_{n∈ω} Self(n))^{Ω}, K-algebras A embeddable in (∏_{n∈ω} End_{K}(K^{n}))^{Ω}, and lattices A embeddable in (∏_{n∈ω} Equiv(n))^{Ω} ?

Clearly, such an A must be residually finite(-dimensional), and embeddable in Sym(Ω), Self(Ω), End_{K}(V), respectively Equiv(Ω). Are these conditions on an algebra A sufficient for it to be embeddable in the indicated object?

I record next a question which it would have been natural to give in [4], [5], or [6], but which occurred to me too late to include in those papers. (It is an instance of the direction for investigation suggested in the second sentence of [6, §10].) There are obvious variants and strengthenings, but for concreteness, I pose the question here for the object that has been most studied.

Question 9.2. Suppose G and H are subgroups of Sym(ω), which together generate that group. Must Sym(ω) be finitely generated over one of these subgroups?

We end this note with a few items that we have postponed.

10 Appendix: End_{K}(V) ∐End_{K}(V) can be embedded in End_{K}(V).

We shall now give the postponed proof of the above embeddability statement, Lemma 4.1(iii).

Suppose S and T are two nonzero K-algebras (as always, associative and unital), and we form their coproduct S ∐T in the variety of such algebras, calling the coprojection maps α : S → S ∐T and β : T → S ∐T. Recall [2, Corollary 8.2] that if B_{S}, B_{T} are K-vector-space bases for S and T, containing 1_{S} and 1_{T} respectively, then a K-vector-space basis for S ∐T is given by the set of finite products

(50) … α(b_{i}) β(b_{i−1}) α(b_{i−2}) β(b_{i−3}) …

where, as in (13), those b_{j} that are arguments of α (i.e., in (50), those with subscript j having the same parity as i) are taken from B_{S} − {1_{S}}, those that are arguments of β are taken from B_{T} − {1_{T} }, and the empty product is understood to give the identity element 1 = α(1_{S}) = β(1_{T}). As in (13), I have not shown the first and last terms, since each may be either an α-term or a β-term.

Letting S = T = End_{K}(V), and letting B be a K-basis for this algebra containing 1, a basis for End_{K}(V)∐End_{K}(V) is thus given by the words (50) with all b_{j} taken from B − {1}. To show End_{K}(V)∐End_{K}(V) embeddable in End_{K}(V), it will suffice to find a representation of End_{K}(V)∐End_{K}(V) by K-linear endomorphisms on a vector space of the same dimension as V, such that the images of the elements (50) are linearly independent. For this, in turn, it will suffice to find a family of ≤ card(Ω) representations of End_{K}(V)∐End_{K}(V) on such spaces, such that every nontrivial linear relation among elements (50) fails to hold in at least one of these representations, since then all such relations will fail in the direct sum of the representations.

The representations we use will each be on ⨁_{ω} V, a direct sum of countably many copies of V, with basis Ω × ω. For each k ∈ Ω we shall call the kth copy of V, i.e., the span of Ω × {k}, the “kth level” of ⨁_{ω} V, and, extending the notation we are using on its basis, we shall denote the element at the kth level corresponding to any v ∈ V by (v, k). We define the natural action of each f ∈ End_{K}(V) on the kth level of ⨁_{ω} V to be given by f(v, k) = (f(v), k), i.e., to mimic its action on V. The natural action on ⨁_{ω} V will mean the direct sum of these actions.

We now define our card(Ω) actions of End_{K}(V)∐End_{K}(V) on ⨁_{ω} V. They will be indexed by the set of those vector space automorphisms t of ⨁_{ω} V which have order 2, fix all but finitely many members of the basis Ω × ω, and take the remaining members of that basis to linear combinations of members of that basis with integer coefficients. The last two conditions insure there are only card(Ω) such t. For each such choice of t, we map End_{K}(V)∐End_{K}(V) to End_{K}(⨁_{ω} V) by sending each element α(f) (f ∈ End_{K}(V)) to the natural action of f on ⨁_{ω} V, which we denote by the same symbol f, while we send β(f) to t f t^{−1}.

For the remainder of the proof, let us fix a nonzero x ∈ End_{K}(V)∐End_{K}(V). If x ∈ K, then clearly x has nonzero action under all of our representations; so let us assume x ∉ K, and show how to construct a t such that the action of x on ⨁_{ω} V under the representation indexed by t is nonzero.

To do this, let us fix an arbitrary element r ∈ Ω, and note that End_{K}(V) will be the direct sum of the 1-dimensional subspace spanned by the identity map, and the subspace End_{K}(V)_{0} of consisting of those maps that take r to a linear combination of elements of Ω − {r}. Choosing, temporarily, an arbitrary basis B′ of End_{K}(V) consisting of 1 and elements of End_{K}(V)_{0}, let us express x as a linear combination of words of the form (50) with the b_{j} taken from B′ − {1}. Let n be the maximum of the lengths of the words occurring with nonzero coefficient in this expression. Let S ⊆ B′ be the set consisting of 1 and all those elements of B′ − {1} that occur (as arguments of α or β) in the expression for x. From the fact that the span of S is a finite dimensional subspace of End_{K}(V), it is not hard to see that there will exist a finite subset Σ ⊆ Ω containing the element r, such that, if we write P_{Σ} ∈ End_{K}(V) for the element that fixes all members of Σ and annihilates all members of Ω − Σ, then the linear operator on End_{K}(V) given by (51) f ↦ P_{Σ} f P_{Σ}

is one-to-one on the span of S. Let us fix such a set Σ ⊆ Ω.

We can now describe the basis B of End_{K}(V) in terms of which we will work for the rest of the proof. For all p, q ∈ Ω, let E(q, p) ∈ End_{K}(V) be the linear map that takes p to q, and all other members of Ω to 0. Since the typical member of End_{K}(V) has infinite-dimensional range, the elements E(q, p) do not span End_{K}(V); but their linear combinations do give all possible behaviors on our finite set Σ, which is what we will need. Let us choose B to consist of the identity operator 1, all the operators E(q, p) with p ∈ Σ (and q unrestricted) except for E(r, r), and the members of any basis of the space of those endomorphisms that annihilate Σ.

To see that an arbitrary f ∈ End_{K}(V) may be represented by a linear expression in members of B, first set the coefficient of 1 in this expression to be the coefficient of r in f(r). Subtracting from f that multiple of 1 gives a member of End_{K}(V)_{0}, whose behavior on the elements of Σ can be represented by a finite linear combination of the operators E(q, p) with p ∈ Σ and (p, q) ≠ (r, r). Subtracting this off, we are left with an operator annihilating Σ, which can be uniquely represented using the elements introduced in the last part of our definition of B. Clearly, this expression for f is unique.

We now take our earlier expression for x as a linear combination of words (50) with all b_{j} ∈ B′−{1}, and substitute for the b_{j} their expressions as linear combinations of elements of B − {1}, getting an expression for x, again as a combination of words (50), with the b_{j} now in B − {1}. Clearly, these words still have length ≤ n. I claim, moreover, that by our choice of Σ, the expression contains, with nonzero coefficient, at least one product (50) of length n in which all b_{j} have the form E(q, p) with p and q both in Σ (and by definition of B, with (p, q) ≠ (r, r)).

To see this, note that a consequence of our normal form for coproducts of associative K-algebras is that End_{K}(V)∐End_{K}(V) can be identified with a direct sum of iterated tensor products End_{K}(V)_{0} ⊗_{K} ⋯ ⊗_{K} End_{K}(V)_{0}, where the 0-fold tensor product, i.e., K, occurs once, and each higher tensor product occurs twice, corresponding to the two ways of labeling the tensor factors alternately with α and β. This identification maps any element of one of these direct summands (e.g., an element v_{1} ⊗ v_{2} ⊗ v_{3} in the summand labeled with α, β, α) to the corresponding sum of products of elements of α(End_{K}(V)_{0}) and β(End_{K}(V)_{0}) (e.g., α(v_{1})β(v_{2})α(v_{3}) in that example), and is therefore independent of choice of basis. (It does depend on our choice of linear complement End_{K}(V)_{0} for K in End_{K}(V), which depends on our choice of r, but we made that choice at the start and have not changed it.) I claim that the condition by which we chose the finite set Σ implies that if the K-linear map (51) is applied simultaneously to every tensor factor End_{K}(V)_{0} in every summand in the above expression for End_{K}(V)∐End_{K}(V), the element x continues to have nonzero components in all the degrees where x had them; in particular, in degree n. Indeed, the linear relations holding among a set of expressions in a tensor product of vector spaces depend only on the linear relations holding among the elements of the given spaces that occur in these expressions; and Σ was chosen so that (51) creates no new linear relations among the elements occurring in our original expression for x. Now in terms of our new basis B − {1} of End_{K}(V)_{0}, the map (51) acts by throwing out all basis elements other than the E(q, p) with p, q ∈ Σ. So since x continues to have nonzero component in degree n after the application of (51), the expression for x using the basis B − {1} does indeed involve at least one length-n word in such elements E(q, p) alone.

We now choose, subject to a restriction to be given in a moment, a particular length-n word of this sort occurring with nonzero coefficient in x,

(52) … α(E(q_{i}, p_{i})) β(E(q_{i−1}, p_{i−1})) α(E(q_{i−2}, p_{i−2})) β(E(q_{i−3}, p_{i−3})) …, where (q_{j}, p_{j}) ∈ Σ × Σ − {(r, r)} (j = 1, …, n).

To do this, let us work from the right, first choosing an α(E(q_{1}, p_{1})) or β(E(q_{1}, p_{1})) that occurs as a rightmost factor in some length-n word of the form (52) in our expression for x; then choosing for β(E(q_{2}, p_{2})) or α(E(q_{2}, p_{2})), as the case may be, an element of this form that occurs in second position from the right, immediately to the left of our first chosen factor, in at least one length-n word of that form; and so on. The one restriction we impose is that for each j = 1, …, n, (q_{j}, p_{j}) should satisfy q_{j} ≠ p_{j} if this is possible, i.e., if there is a factor satisfying q_{j} ≠ p_{j} which occurs, followed by the terms chosen so far, in the jth position of a length-n word occurring in x. Henceforth, (52) will denote the particular word so chosen.

The reason we avoid choices with q_{k} = p_{k} whenever possible is that it will not be as easy to make use of the fact that elements of the form E(p, p) are nonscalar as it will for other elements; but we will be able to do so if there are no elements E(q, p) with q ≠ p “in the vicinity”. The distinction between these cases is used in the next definition.

For k = 1, …, n, let us define elements p′_{k} ∈ V, by

(53)  p′_{k} = p_{k} ∈ Ω  if q_{k} ≠ p_{k},
p′_{k} = p_{k} + r ∈ V if q_{k} = p_{k}.

Note that in the second line above, the summands p_{k} and r are distinct members of Ω, for if q_{k} = p_{k}, we cannot have p_{k} = r, since E(r, r) ∉ B. For those values of k such that q_{k} = p_{k}, let us temporarily form a new basis of the kth level (the kth direct summand) of ⨁_{ω} V, by deleting from Ω × {k} the basis element (r, k) and inserting (p′_{k}, k) in its place, while for those k such that q_{k} ≠ p_{k}, let us keep the basis Ω × {k}. Thus, the union over k of these bases is a new basis of ⨁_{ω} V. Note that for every k, (p′_{k}, k) and (q_{k}, k) are distinct elements of our new basis.

We now define our automorphism t of ⨁_{ω} V to fix all elements of our new basis, except for the following 2(n + 1) elements, which we let it transpose in pairs as shown:

(54) (p_{1}, 0) ↔ (p′_{1}, 1), (q_{k−1}, k−1) ↔ (p′_{k}, k) (1 < k ≤ n), (q_{n}, n) ↔ (q_{n}, n+1).

This is where we need the second line of (53). It insures that even if q_{k} = p_{k}, the basis elements (p′_{k}, k) and (q_{k}, k) are distinct, so that the rules (q_{k−1}, k−1) ↔ (p′_{k}, k) and (q_{k}, k) ↔ (p′_{k+1}, k+1) do not give contradictory specifications of the action of t on the same basis element at the kth level.

As promised, t has order 2 and sends members of our original basis Ω × ω to linear combinations of members of that basis with integer coefficients. Having noted this, we shall now go back to using Ω × ω as the basis in terms of which we will compute with elements of ⨁_{ω} V, and shall think of the terms of (54) as expressions in those basis elements.

As sketched earlier, we now let h : End_{K}(V)∐End_{K}(V) → End_{K}(⨁_{ω} V) be the homomorphism which takes elements α(f) to f (acting by the natural action) and elements β(f) to t f t^{−1} = t f t.

The remainder of the proof follows closely the concluding steps of the proof of Lemma 4.1(ii). We want to show that h(x) ≠ 0. Clearly, this is equivalent to proving nonzero the element h(x)′ that we get on multiplying h(x) on the right by t if the rightmost term of (52) is α(E(p_{1}, q_{1})), while leaving that side unchanged if that term is β(E(p_{1}, q_{1})), and multiplying on the left by t if the leftmost term of (52) is α(E(p_{n}, q_{n})), while leaving that side unchanged if that term is β(E(p_{n}, q_{n})). To avoid cumbersome language, we shall call products of E(p, q)’s and ts occurring with nonzero K-coefficient in our expression for h(x)′ the “summands” in that expression (not counting the K-coefficients as parts of these “summands”). A consequence of our definition of h(x)′ is that the summand therein arising from the term (52) of h(x) has a t at each end, so we can now write it so as show those ends. Let us also give it a name:

(55) u = t E(q_{n}, p_{n}) t E(q_{n−1}, p_{n−1}) t … t E(q_{2}, p_{2}) t E(q_{1}, p_{1}) t.

The general summand in the expression for h(x)′ will likewise be an alternating product of t and elements of B − {1} (which we will call the “B-factors” of the summand), with at most n of the latter. We claim now that when we apply h(x)′ to (p_{1}, 0), the summand u shown in (55), and only that summand, leads to a nonzero component at the n+1st level of ⨁_{ω} V.

Since in each summand, the only factors that carry elements of ⨁_{ω} V from one level to the next are the factors t, and each of these moves elements by only one level, the only summands in h(x)′ that can possibly lead to components at the n+1st level in h(x)′(p_{1}, 0) are those which, like (55), have exactly n (rather than fewer) B-factors, and have a t at each end. Consider any such summand

(56) w = t b_{n} t b_{n−1} t … t b_{2} t b_{1} t,

where b_{k} ∈ B − {1} (k = 1, …, n). We shall show inductively for k = 1, …, n+1 that if we apply to (p_{1}, 0) the substring t b_{k−1} t b_{k−2} t … t b_{2} t b_{1} t of w, then the components of the result in levels higher than the kth are zero, the component in the kth level is a scalar multiple of (p′_{k}, k), and the scalar factor is nonzero if and only if our substring agrees exactly with the corresponding substring of u, i.e., if and only if b_{i} = E(q_{i}, p_{i}) for i = 1, …, k − 1.

The base case k = 1 is immediate: we are merely applying t to (p_{1}, 0), and by (54) the result is (p′_{1}, 1). (This rightmost factor t was important in distinguishing the action of u from actions of summands of h(x)′ not ending in t; but we have already used it to exclude such strings from consideration.)

Now let our inductive assumption hold for some k with 1 ≤ k ≤ n. If we do not have b_{i} = E(q_{i}, p_{i}) for all i < k, then by that inductive assumption, t b_{k−1} t … t b_{1} t (p_{1}, 0) has zero component at the kth and higher levels, so multiplication by b_{k} and then by t will not bring anything to the k+1st level or higher.

If the factors of w so far have agreed with those of u, then by inductive hypothesis, t b_{k−1} t … t b_{1} t (p_{1}, 0) has at the kth level a nonzero scalar multiple of (p′_{k}, k). When we apply b_{k} to this, if b_{k} = E(q_{k}, p_{k}) i.e., if this too agrees with the corresponding factor of u, then we see that, whether (p′_{k}, k) is equal to (p_{k}, k) or to (p_{k}, k) + (r, k), the factor E(q_{k}, p_{k}) will send it to (q_{k}, k); and the subsequent application of t will give us a term (p′_{k+1}, k+1) at the k+1st level, as desired.

If b_{k} ≠ E(q_{k}, p_{k}), there are several cases to consider. First, b_{k} might be one of the members of B belonging to the subspace of End_{K}(V)_{0} annihilating Σ. In that case, it annihilates (p′_{k}, k), leaving nothing at the kth level, and the subsequent application of t brings nothing to the k+1st level. Otherwise, we have b_{k} = E(q, p) for some (q, p) ≠ (q_{k}, p_{k}). Clearly, the only cases in which E(q, p) can fail to annihilate (p′_{k}, k) are

(a) if p = p_{k}, or

(b) if p′_{k} has the form p_{k} + r, and p = r.

In case (a), since we have assumed that E(q, p) ≠ E(q_{k}, p_{k}), we must have q ≠ q_{k}, so E(q, p)(p′_{k}, k) = (q, k) ≠ (q_{k}, k), and by (54), the subsequent application of t will not bring this up to the k+1st level.

In case (b), the assumption p′_{k} = p_{k} + r means, by (53), that E(q_{k}, p_{k}) = E(p_{k}, p_{k}). But recall that in choosing the term (52), we avoided this possibility whenever possible. A consequence is that since w was not chosen in preference to u, we must likewise have b_{k} = E(p, p). However, case (b) assumed p = r, so b_{k} = E(r, r), which is excluded by the definition of B. Hence case (b) does not occur.

We thus conclude that u is the unique summand in h(x)′ which, when applied to (p_{1}, 0), gives an element having nonzero component at the n+1st level. Hence h(x)′ (p_{1}, 0) ≠ 0, so h(x)′ ≠ 0, so h(x) ≠ 0, completing the proof that our action of End_{K}(V)∐End_{K}(V) is faithful.

Now for an unexpected bonus. We saw in §8 that when K had large cardinality, our tools for proving nonembeddability of algebras in End_{K}(V) gave weaker results than we expected from our results on groups, monoids and lattices. We shall now see that we also get stronger positive embeddability results in that situation. We need the following fact.

Lemma 10.1 (cf. [13, Exercise 1, p.248]). Let k be any commutative integral domain, and M the multiplicative monoid of k. Then the product k-algebra k^{ω} contains a subalgebra isomorphic to the monoid algebra kM. In particular, letting G denote the group of units of k, it contains a copy of the group algebra kG.

Proof. For each a ∈ k, let x_{a} ∈ k^{ω} denote the sequence of powers, (1, a, a^{2}, …). Clearly, a ↦ x_{a} is a monoid homomorphism from M into the multiplicative monoid of k^{ω}. Moreover, the elements x_{a} are k-linearly independent by the properties of the Vandermonde determinant. Hence they span a subalgebra of k^{ω} isomorphic to kM. The final assertion clearly follows.

Proposition 10.2. End_{K}(V) contains a coproduct of card(K) copies of itself as an associative K-algebra. (Hence, in view of Theorem 4.2(iii), it contains such a coproduct of max(2^{card(Ω)}, card(K)) copies of itself.)

Proof. For K finite, our main statement is weaker than Theorem 4.2(iii), so assume K infinite.

Since End_{K}(V) contains a subalgebra isomorphic to K^{ω}, the preceding lemma shows that it contains a copy of the group algebra K G on a group G of cardinality card(K − {0}) = card(K).

We have also just seen that it contains a copy of End_{K}(V)∐End_{K}(V); combining these observations, we conclude that it contains a copy of End_{K}(V)∐K G. For notational convenience, let us identify End_{K}(V) with the first factor in this coproduct, and G (which we regard as an abstract group, forgetting about its relation with K) with its image in the second factor. Then for each g ∈ G, we can form the conjugate algebra g End_{K}(V) g^{−1}, getting card(K) isomorphic copies of End_{K}(V). Moreover, from the linear independence of the elements of G in K G and the normal form for the coproduct End_{K}(V)∐K G, one sees that the subalgebra these generate will be their coproduct, so End_{K}(V) indeed contains a coproduct of card(K) copies of itself. (This is the ring-theoretic analog of the appearance of big free products inside smaller free products in the Kurosh Subgroup Theorem.) The final assertion clearly follows.

Corollary 10.3. End_{K}(V) contains a coproduct, as K-algebras, of max(2^{card(Ω)}, card(K)) copies of every K-algebra of dimension ≤ card(Ω).

Of course, these results lead to the questions:

Question 10.4. Can we prove a version of Theorem 3.2(iii) with F (2^{card(Ω)}) replaced by F (max(2^{card(Ω)}, card(K))) for a wider class of functors F than the “coproduct as K-algebras of I copies of A ” functors of Corollary 10.3?

An interesting test case would be that in which F is the functor taking I to the K-algebra presented by an I-tuple of commuting idempotents.

Remark: One can strengthen Proposition 10.2 so as to increase max(2^{card(Ω)}, card(K)) to card(K)^{card(Ω)}, which occasionally exceeds the former value; e.g., when card(K) has the form ℵ_{α+ω} and is > 2^{card(Ω)}. To do so, replace ω in Lemma 10.1 with the free abelian monoid A(Ω) on Ω, which has cardinality card(Ω), replace the maps x_{a} in the proof by all homomorphisms of A(Ω) into the multiplicative monoid M of k, apply the theorem on linear independence of characters to conclude that k^{A(Ω)} contains a copy of the monoid algebra k M^{Ω}, and use this version of the lemma to get the strengthened proposition. (One can’t raise the cardinal in the proposition higher than card(K)^{card(Ω)}, since dim_{K}(End_{K}(V)) = dim_{K}(V^{Ω}) ≤ dim_{K}((K^{Ω})^{Ω}) = dim_{K}(K^{Ω×Ω}) = dim_{K}(K^{Ω}) ≤ card(K^{Ω}) = card(K)^{card(Ω)}; cf. [13, p.247, Theorem 2].)

It is curious that the nonembeddability results we are able to prove become weaker than expected as soon as card(K) > card(Ω), but our positive results become stronger only when card(K) > 2^{card(Ω)}.

11 Appendix: another embedding of Sym(Ω) ∐Sym(Ω) in Sym(Ω).

Here is the alternative proof of Lemma 4.1(i) mentioned shortly before the statement of Lemma 4.1. As in the preceding appendix, we begin by recalling a structure theorem for coproducts, this time co-

products of groups. But we will make different assumptions (we won’t assume there are only two groups, but we will assume the groups are disjoint except for their identity elements, so that we do not have to write the coprojection maps explicitly), we will use the structure theorem, initially, for a different purpose (to motivate a somewhat bizarre action of the coproduct group), and we will consider for most of this section arbitrary groups (or sometimes, monoids) rather than a pair of copies of Sym(Ω), though that is the case to which we will ultimately apply our result.

Let (G_{i})_{i∈I} be any family of groups whose sets of nonidentity elements are pairwise disjoint. Recall that the general element of the coproduct group ∐_{i∈I} G_{i} can be written uniquely as

(57) g_{n} … g_{2} g_{1},

where n ≥ 0 and g_{n}, …, g_{1} ∈ ⋃_{i∈I} G_{i} − {1}, say with

(58) g_{r} ∈ G_{i_{r}} (r = 1, …, n),

and where successive indices i_{r}, i_{r+1} are distinct; i.e., two elements from the same group G_{i} never occur in immediate succession.

Suppose we are given a representation of each G_{i} by permutations of a nonempty set Ω_{i}, and we form the direct product ∏ Ω_{i}. Then starting at any point (x_{i})_{i∈I} ∈ ∏ Ω_{i}, an expression (57) allows us to construct a “path” in ∏ Ω_{i} : At the first step, we move from (x_{i}) to the point agreeing with (x_{i}) on all but the i_{1}-coordinate, which is moved by g_{1}; the next step takes us to the point whose i_{2}-coordinate has also been moved by g_{2}, etc.. This suggests that we make the set of “paths” in ∏ Ω_{i} in which each step involves changing just one coordinate, and two successive steps never change the same coordinate, into a ∐ G_{i}-set.

Some difficulties arise. Though, by assumption, no g_{r} in (57) is an identity element, some of these factors may lie in the stabilizers of the coordinates they are to be applied to. In such cases should we, as the above description might suggest, allow trivial “steps” in our path, where no coordinate is changed? It turns out that this would lead to difficulties; so we specify that in such cases, no step is added to our path. Also, for inverses to behave correctly, we must allow some elements to delete rather than adding steps to our paths.

The resulting construction is described in the next lemma. Note that it is not claimed that if the Ω_{i} are faithful G_{i}-sets, then the ∐ G_{i}-set ⊠_{i∈I}Ω_{i} described there is also faithful. Rather, we shall subsequently note additional conditions that ensure faithfulness.

Up to the step of achieving faithfulness, our construction works as well for arbitrary monoids as for groups, so the lemma below is stated in that context. As usual, we understand actions to be left actions.

Note that in the statement below, subscripts n and r do not correspond to the subscript i above; rather, each of the steps x_{r} (r = 1, …, n) in our “path” is itself an I-tuple x_{r} = (x_{r,i})_{i∈I}.

Lemma 11.1. Let (M_{i})_{i∈I} be a family of monoids, and for each i ∈ I let Ω_{i} be an M_{i}-set. Let ⊠_{i∈I}Ω_{i} be the set of all finite sequences (x_{1}, …, x_{n}) (n ≥ 1) where each x_{r} ∈ ∏_{i∈I} Ω_{i} (r = 1, …, n), every pair of successive terms x_{r}, x_{r+1} (1 ≤ r < n) differs in one and only one coordinate, and the coordinate at which x_{r+1} differs from x_{r} is not the same as the coordinate at which x_{r} differs from x_{r−1} (1 < r < n).

Then ⊠_{i∈I}Ω_{i} may be made a ∐_{i∈I} M_{i}-set (which we might call the “path product” of the M_{i}-sets Ω_{i}) by defining the action of each g ∈ M_{j} (j ∈ I) on x = (x_{1}, …, x_{n}) ∈ ⊠_{i∈I}Ω_{i} by the following rules:

(59) Let x′_{n} ∈ ∏_{i∈I} Ω_{i} denote the I-tuple obtained from x_{n} by modifying its j-coordinate via the action of g on that element of M_{j}. Then

(i) If x′_{n} = x_{n}, we define gx = x.

(ii) If x′_{n} ≠ x_{n}, then:

(ii.a) If either n = 1, or if n > 1 and the coordinate at which x_{n} differs from x_{n−1} is not the jth, we define gx = (x_{1}, …, x_{n}, x′_{n}), (ii.b) If n > 1 and the coordinate at which x_{n} differs from x_{n−1} is the jth, then: (ii.b.1) If x′_{n} ≠ x_{n−1}, we define gx = (x_{1}, …, x_{n−1}, x′_{n}), while (ii.b.2) If x′_{n} = x_{n−1}, we define gx = (x_{1}, …, x_{n−1}).

Proof. By the universal property of the coproduct ∐_{i∈I} M_{i}, an action of that monoid on the set ⊠_{i∈I}Ω_{i} will be defined if we verify that for each j ∈ I, the above conditions define an action of M_{j} on that set.

This could be done by brute force, dividing into cases according to which headings of the above definition the actions of two successive elements of M_{j} come under. But there is a trick that greatly simplifies this calculation (cf. [3, proof of Proposition 3.6.5]). For each j, we shall define a bijection φ_{j} between ⊠_{i∈I}Ω_{i} and a set (⊠_{i∈I}Ω_{i})_{(j)}, such that it will be easy to define an action of M_{j} on (⊠_{i∈I}Ω_{i})_{(j)}, and also easy to verify that when we transport this action from (⊠_{i∈I}Ω_{i})_{(j)} to ⊠_{i∈I}Ω_{i} via the bijection φ_{j}, the resulting action is described by (59). Roughly, elements of (⊠_{i∈I}Ω_{i})_{(j)}, like elements of ⊠_{i∈I}Ω_{i}, will represent “paths” in ∏ Ω_{i}, but in (⊠_{i∈I}Ω_{i})_{(j)} we require every such path to have a final step involving the j-coordinate, at the price of allowing this step (and only this step) to be trivial (i.e., to satisfy x_{n−1} = x_{n}).

Here is the precise description. We take the elements of (⊠_{i∈I}Ω_{i})_{(j)} to be sequences x = (x_{1}, …, x_{n}) of elements of ∏ Ω_{i}, this time with n always ≥ 2, such that

(i) (x_{1}, …, x_{n−1}) ∈ ⊠_{i∈I}Ω_{i},

(ii) x_{n−1} and x_{n} are either equal, or differ in the jth coordinate only.

(iii) If n > 2, the coordinate at which x_{n−2} and x_{n−1} differ is not the jth.

Note that none of these conditions constrains the jth coordinate of x_{n}. Hence a monoid action of M_{j} on (⊠_{i∈I}Ω_{i})_{(j)} may be defined by the rule

(60) g (x_{1}, …, x_{n−1}, x_{n}) = (x_{1}, …, x_{n−1}, x′_{n}),

where, as in the statement of the lemma, x′_{n} is obtained from x_{n} by modifying its jth coordinate by the action of g, and leaving all other coordinates unchanged.

Let us now define φ_{j} : ⊠_{i∈I}Ω_{i} → (⊠_{i∈I}Ω_{i})_{(j)} to leave unchanged all x = (x_{1}, …, x_{n}) ∈ ⊠_{i∈I}Ω_{i} with n > 1 in which the coordinate at which x_{n−1} and x_{n} differ happens to be the jth, while appending to every other element of ⊠_{i∈I}Ω_{i} a repetition of its final term. It is straightforward that this is a bijection, and easy to verify that the action of M_{j} on ⊠_{i∈I}Ω_{i} induced, via this bijection, by its action (60) on (⊠_{i∈I}Ω_{i})_{(j)}, is as described in (59), completing our proof.

We now want to use the above construction to get faithful actions. We shall see that we can do this if our monoids are right cancellative, in particular, if they are groups.

Let us call an action of a monoid M on a set Σ strongly faithful if for every finite family of distinct elements g_{1}, …, g_{n} ∈ M, there exists y ∈ Σ such that g_{1}y, …, g_{n}y are distinct. (The n = 0 case of this condition says that Σ is nonempty.) It is easy to see that if Σ is a faithful M-set, then the disjoint union 1 ∪ Σ ∪ Σ^{2} ∪ Σ^{3} ∪ … (indexed by the natural numbers, with each Σ^{n} given the product M-set structure) is strongly faithful, and that this construction does not increase infinite cardinalities. On the other hand, we have Lemma 11.2. Let (M_{i})_{i∈I} be a family of monoids, each having the right cancellation property

(61) ac = bc ⟹ a = b (a, b, c ∈ M_{i}),

and for each i ∈ I, let Ω_{i} be a strongly faithful left M_{i}-set. Then ⊠_{i∈I}Ω_{i}, defined and made a ∐_{i∈I} M_{i}-set as in Lemma 11.1, is a faithful ∐_{i∈I} M_{i}-set.

Proof. Given distinct elements g = g_{m} … g_{2} g_{1} and h = h_{n} … h_{2} h_{1} in ∐ M_{i}, we wish to find an x ∈ ⊠_{i∈I}Ω_{i} such that gx ≠ hx. We shall construct below such an element which is of length 1, i.e., a 1-tuple (x_{1}) with x_{1} ∈ ∏ Ω_{i}. To do this let us, for each j ∈ I, choose the j-coordinate of x_{1} as follows. Let r_{j,1} < ⋯ < r_{j,m_{j}} be the values of r for which g_{r} ∈ G_{j} and s_{j,1} < ⋯ < s_{j,n_{j}} the values s for which h_{s} ∈ G_{j}. Although the elements

(62) 1, g_{r_{j,1}}, g_{r_{j,2}}g_{r_{j,1}}, …, g_{r_{j,m_{j}}} ... g_{r_{j,2}}g_{r_{j,1}}, and 1, h_{s_{j,1}}, h_{s_{j,2}}h_{s_{j,1}}, …, h_{s_{j,n_{j}}} ... h_{s_{j,2}}h_{s_{j,1}}

of M_{j} need not all be distinct, successive elements of each of these lists will be so, by right cancellation. For each j ∈ I let us use strong faithfulness of M_{j} to choose, as the j-coordinate of x_{1}, an element of Ω_{j} whose images under distinct elements of the combined list (62) are distinct. (For some j, the m_{j} and n_{j} in (62) may both be zero, in which case this condition is vacuous.) Thus, the images of x_{1} under successive terms of each list in (62) are distinct.

It follows from this choice that each time we apply an element g_{r} or h_{r} in building up g_{m} … g_{1}x or h_{n} … h_{1}x, it in fact moves the coordinate of the term of g_{r−1} … g_{1}x, respectively h_{r−1} … h_{1}x to which it is applied, and successive steps move different coordinates. Thus, we are always in case (ii.a) of the definition of the action of M_{i_{r}}, so the final elements g_{m} … g_{1}x and h_{n} … h_{1}x reflect all the steps of this process. In particular, if m ≠ n, the elements gx and hx have different lengths, if m = n and the sequence of indices in I determined by g and h differ, then g_{m} … g_{1}x and h_{n} … h_{1}x are clearly different, while if m = n and these sequences are the same, then there must be some j ∈ M such that the sequences of elements of G_{j} differ; and if we look at the first terms where this occurs, then by right cancellativity, the corresponding terms of (62) will differ, and by our choice of x_{1,j}, the elements gx and hx will differ at that step.

(The above action will, in fact, be strongly faithful – we could have handled any finite set of elements of ∐_{i∈I} M_{i} as we did {g, h}; but we only need the two-element case, and it allowed simpler notation.)

Now letting G_{0}, G_{1} be two isomorphic copies of the group Sym(Ω), disjoint except for the identity, each represented naturally on Ω, we get as in the paragraph before Lemma 11.2 strongly faithful actions of G_{0} and G_{1} on 1 ∪ Ω ∪ Ω^{2} ∪ Ω^{3} ∪ …, which has cardinality card(Ω). Calling this set, regarded as a G_{0}-set Ω_{0}, and regarded as a G_{1}-set Ω_{1}, the above lemma tells us that the coproduct of G_{0} and G_{1} acts faithfully on Ω_{0} ⊠ Ω_{1}, which is also of cardinality card(Ω), completing our alternative proof of Lemma 4.1(i).

More generally, the submonoid of surjective endomaps of Ω satisfies (61), so the above construction embeds the coproduct of two copies of that monoid in Self(Ω).

On the other hand, if we delete the right cancellativity assumption (61) from the hypothesis of Lemma 11.2, there will in general be no choice of M_{i}-sets Ω_{i} making ⊠_{i∈I}Ω_{i} faithful. For if one of the monoids, say M_{1}, has elements a ≠ b and c satisfying ac = bc, and at least one other of the monoids is nontrivial, say M_{2}, with a nonidentity element d, then in ∐ M_{i} we find that adc and bdc are distinct elements having the same action on ⊠_{i∈I}Ω_{i} for any family of M_{i}-sets Ω_{i}.

12 Appendix: Some conditions on complete lattices.

We noted in the discussion preceding Question 5.9 that the conditions we had proved on chains of solution sets in Sym(Ω) and Self(Ω) were consequences of the stronger statement that the lattice of all such solution sets embeds in the system of closed sets of a topological space having a basis of ≤ card(Ω) open sets. The same observation holds for the results obtained in later sections on solution sets in Equiv(Ω), etc..

The next lemma compares these and related conditions. Here a κ-generated topological space means a topological space having a basis of open sets of cardinality ≤ κ; equivalently, having a subbasis of open sets of that cardinality; equivalently, having such a basis or subbasis of closed sets. An embedding of lattices, of complete lower semilattices, etc., means a one-to-one homomorphism of such structures; an embedding of partially ordered sets means a (necessarily one-to-one) map that preserves both the relations ≤ and ≰ .

Lemma 12.1. Let κ be an infinite cardinal, and A a complete lattice. Then of the following conditions, each implies the next, and conditions with the same roman numeral and different suffixes are equivalent.

(i.a) A is embeddable as a complete lower semilattice in P(κ).

(i.b) A is generated as a complete upper semilattice by a set of ≤ κ elements.

(ii.a) A is embeddable as a complete lower semilattice in a complete lower semilattice generated by ≤ κ elements.

(ii.b) A is embeddable as a partially ordered set in a complete lower semilattice generated by ≤ κ elements.

(ii.c) A is embeddable as a partially ordered set in P(κ).

(ii.d) A is embeddable as a complete lower semilattice in the system of closed subsets of a κ-generated topological space.

(ii.e) A is embeddable as a partially ordered set in the system of closed subsets of a κ-generated topological space.

(ii.a*)-(ii.e*) The duals of (ii.a)-(ii.e); i.e., the corresponding statements with “upper semilattice” replaced by “lower semilattice”, and “closed subsets” by “open subsets”, wherever applicable. (So, no change in (ii.c)).

(iii) Every chain in A has a dense subset of cardinality ≤ κ.

(iv.a) No chain in A has a family of > κ disjoint intervals.

(iv.b) No chain in A has > κ jumps.

(v) A contains no well-ordered or reverse-well-ordered chain of cardinality > κ.

Moreover, if for each family of conditions whose equivalence is asserted above, we denote the common condition using the corresponding roman numeral with suffixes dropped, then the implications (i) ⟹ (ii) ⟹ (iii) are irreversible for all κ, but are both reversible if A is restricted to be a chain; the implication (iv) ⟹ (v) is irreversible for κ = ℵ_{0}, while the reversibility of (iii) ⟹ (iv) for κ = ℵ_{0} is equivalent to Suslin’s Hypothesis, known to be independent of ZFC.

Proof. (i.a) ⟹ (i.b): Given a complete lower semilattice embedding f : A → P(κ), let us associate to each α ∈ κ the meet g(α) ∈ A of all elements x ∈ A satisfying α ∈ f(x). We see that g(α) will be the least y such that α ∈ f(y), and we deduce that every x ∈ A is the join in A of {g(α) | α ∈ f(x)}. So {g(α) | α ∈ κ} generates A as a complete upper semilattice.

(i.b) ⟹ (i.a): Given a generating set {g_{α} | α ∈ κ} for A as a complete upper semilattice, we find that an embedding A → P(κ) as complete lower semilattices is given by the map x ↦ {α | g_{α} ≤ x}.

(i.a) ⟹ (ii.c) is immediate.

To prove the equivalence of the versions of (ii), we shall show (ii.a) ⟹ (ii.d) ⟹ (ii.e) ⟹ (ii.b) ⟹ (ii.c) ⟹ (ii.a). Since (ii.c) is self-dual, it will follow that these conditions are also equivalent to their starred variants.

(ii.a) ⟹ (ii.d): It suffices to show that every complete lower semilattice A′ generated by a set {x_{α} | α ∈ κ} is embeddable as a complete lower semilattice in the system of closed subsets of a κ-generated topology. Given such an A′, define for each x ∈ A′ the “principal downset”

(63) D(x) = {y ∈ A′ | y ≤ x} ⊆ P(A′).

We see that these sets form a complete lower semilattice isomorphic to A′; hence if we define a topology on the underlying set of A′ using the D(x) as a subbasis of closed sets, A′ embeds as a complete lower semilattice in the complete lattice of closed sets of that topology. Moreover, the closed sets D(x_{α}) (α ∈ κ) also form a subbasis of closed sets for this topology, so it is κ-generated, as required.

(ii.d) ⟹ (ii.e) ⟹ (ii.b): Trivial.

(ii.b) ⟹ (ii.c): Suppose A is embeddable as partially ordered set in a complete lower semilattice A′ as in (ii.b). Thus, A′ satisfies the dual of (i.b). Hence it satisfies the dual of (i.a), hence A, being embeddable in A′ as a partially ordered set, satisfies (ii.c).

(ii.c) ⟹ (ii.a): Note that the map D of (63) (with A in the role of A′) is an embedding A → P(A) as complete lower semilattices. Hence it will suffice to show that (ii.c) implies that the image of A under D lies in a complete lower subsemilattice of P(A) generated by ≤ κ elements. Given an embedding f : A → P(κ) as in (ii.c), let us define for each α ∈ κ the set c_{α} = {x ∈ A | α ∉ f(x)} ∈ P(A). We see that for every x ∈ A, the D(x) of (63) is the intersection of those members of {c_{α} | α ∈ κ} ∪ {A} ⊆ P(A) that contain x, so D carries A into the complete lower subsemilattice of P(A) generated by these elements.

(ii) ≠⇒ (i): Let A be a lattice consisting of a least element 0, a greatest element 1, and 2^{κ} pairwise incomparable elements lying between these. Clearly it does not satisfy (i.b). To see that it satisfies (ii.d), recall that the product topology on P(κ) is κ-generated, and let us map A into the closed sets of that topology by sending 0 to ∅, 1 to the improper subset, and the 2^{κ} intermediate elements to the singletons {S} ⊆ P(κ) (S ⊆ κ). (Alternatively, one can show that A satisfies (ii.c) by noting that P(κ × 2) ≅ P(κ) has an antichain of cardinality 2^{κ}, consisting of the sets (s × {0}) ∪ (s^{c} × {1}) (s ⊆ κ).)

(ii.c) ⟹ (iii): It suffices to show that every chain C in P(κ) has a dense subset of cardinality ≤ κ. Let C be such a chain, and for each pair α, β ∈ κ such that some x ∈ C contains α but not β, choose such an element, x_{α,β}. This gives a family of ≤ κ elements which is easily seen to be dense.

(iii) ≠⇒ (ii): Take A as in the example used to show (ii)≠⇒(i), but this time with > 2^{κ} pairwise incomparable elements. This clearly satisfies (iii), but in view of its cardinality, cannot satisfy (ii.c).

On the other hand, the assertion that if A is a chain the implications (i) ⟹ (ii) ⟹ (iii) are reversible follows from the obvious implication (iii) ⟹ (i.b) in this case.

(iii) ⟹ (iv.a): Given any chain C in A and any dense set S of ≤ κ elements of C, we see that for every interval [x, y] in C, at least one element of S must belong to [x, y], showing that C cannot have > κ disjoint intervals.

Concerning the reverse implication, recall that Suslin’s Hypothesis says that every totally ordered set S having no uncountable family of disjoint intervals has a countable dense subset, and that this is independent of ZFC [18]. Assuming Suslin’s Hypothesis, we immediately get (iv.a) ⟹ (iii) for κ = ℵ_{0} by applying that statement to an arbitrary chain C in A.

In proving the converse assertion, note that (iv.a) and (iii) are statements about a complete lattice A (first sentence of the lemma); so we need to show that if S is any counterexample to Suslin’s hypothesis, we can obtain from it a complete lattice A that satisfies (iv.a) but not (iii). Given such an S, let A be its completion as a totally ordered set; I claim that A inherits the properties making S a counterexample to Suslin’s conjecture, and thus gives the desired example. Indeed, for any infinite dense subset D ⊆ A, if we take an element of S between every two distinct elements of D (and throw in the greatest and/or least element of S if these exist), we get a dense subset D′ of S of the same cardinality; so since S has no countable dense subset, neither does A. Likewise, if some chain C ⊆ A had an uncountable family of disjoint intervals, then for each of these intervals [x, y]_{C} we could choose x′, y′ ∈ S with x ≤ x′ < y′ ≤ y, getting an uncountable family of disjoint intervals [x′, y′]_{S} in S; so chains in A inherit from S the nonexistence of such families.

Since (iv.a) and (iv.b) are negative statements, we will prove their equivalence in contrapositive form: ¬(iv.a) ⟹ ¬(iv.b): If a chain C in A has a family of disjoint intervals [x_{α}, y_{α}] where α ranges over

some λ > κ, in then the subchain C′ = {x_{α}, y_{α} | α ∈ λ}, the pairs x_{α} < y_{α} will be jumps.

¬(iv.b) ⟹ ¬(iv.a): If C has > κ jumps, let us associate to each jump x < y the two-element interval [x, y]. There is the slight difficulty that distinct jumps may not yield disjoint intervals: the upper endpoint of one may equal the lower endpoint of the other. However, if we take a family of these intervals maximal for the property of being pairwise disjoint, is easy to verify that this still has cardinality > κ, giving the desired assertion.

(iv.b) ⟹ (v) is clear.

To show that for κ = ℵ_{0}, (v) ≠⇒ (iv.b), let A be ℝ × 2, lexicographically ordered. This has continuum many jumps (a jump (r, 0) < (r, 1) for each real number r), but has no uncountable well-ordered or reverse well-ordered subsets.

Some remarks on the above lemma:

It is, of course, condition (ii) and its consequences (iii)-(v) that are directly relevant to the results of preceding sections. I have included (i) for perspective.

(i) is the only condition in the lemma that is not equivalent to its dual. To show this inequivalence, let A ⊆ P(κ) consist of ∅ and all sets of cardinality κ. This clearly satisfies the dual of (i.a), but we claim it does not satisfy (nondualized) (i.b). Indeed, given a putative generating set {x_{α} | α ∈ κ} for A as a complete upper semilattice (where we allow repetitions in the indexing in case this set has cardinality < κ), one can construct by transfinite recursion an element y ∈ P(κ) having κ elements, but missing at least one element from each x_{α} ≠ ∅ in our family. We see that y will belong to A, but not to the complete upper subsemilattice generated by {x_{α}}.

We could have written (i.a*) and (i.b*) for the duals to (i.a) and (i.b), adding to the lemma their mutual equivalence and the implication (i*) ⟹ (ii); but so naming those conditions would have broken the convention that conditions beginning with the same roman numeral are equivalent.

Conditions (ii.d) and (ii.e) (and hence their duals), which refer to a κ-generated topological space, are equivalent to the formally stronger conditions referring to a κ-generated Hausdorff (and if we wish, totally disconnected) topological space. For given a topological space X as in one of those statements, which we may assume without loss of generality to be T_{0}, and which has a subbasis of ≤ κ closed sets, we can throw in the complements of those sets to get a stronger topology on X which is still κ-generated, but is now totally disconnected and Hausdorff, and whose lower semilattice of closed sets contains the lower semilattice of sets closed in the original topology.

It is curious that the example we gave for (ii)≠⇒(i) in the proof of the lemma is an instance of (37) with card(I) > κ. Thus, although the lattice A in question satisfies (ii), the lattice L_{A_{∧},1}^{=} does not even satisfy (v). The example given above satisfying the dual of (i.a), but not (i.b), similarly contains such an instance of (37), in view of Sierpiński’s result [17] that there exists a family of > κ subsets of κ, each having cardinality κ, but with pairwise intersections all of smaller cardinality. These observations suggest the first part of the next question. The second part is also natural, in view of the simpleminded example we used for (iii)≠⇒(ii).

Question 12.2. (a) If we add to the hypotheses of Lemma 12.1 the assumption that L_{A_{∧},1}^{=} satisfies (v), does this change the validity of the nonimplications shown? (If not, we might try imposing the stronger condition (iv) or (iii) on these lattices, and/or looking at L_{A_{∧}, J}^{=} for J of larger cardinality, up to κ.)

(b) If we add to the hypotheses of Lemma 12.1 the assumption that A has cardinality ≤ 2^{κ}, or that it has order-dimension ≤ κ (i.e., is embeddable as a partially ordered set in a direct product of ≤ κ totally ordered sets – both conditions being implied by (ii)), does this affect the validity of the assertion (iii) ≠⇒ (ii)?

Our final corollary, below, answers a couple of other questions suggested by that lemma. The formulation of statement (b.2) of that corollary uses implicitly the fact that in a complete upper semilattice A′ with least element, every subset has a greatest lower bound, so that A′ may be regarded as a complete lattice (though if A′ was obtained as a complete upper subsemilattice of a complete lattice A, the meet operation of A′, will not in general agree with that of A). Statement (b.2*) uses the dual observation.

Corollary 12.3. (a) For the conditions of Lemma 12.1 that treat A only as a partially ordered set, namely (ii.b), (ii.c), (ii.e), (ii.b*), (ii.c*), (ii.e*) and (iii)-(v), the implications stated in that lemma (for A the underlying partially ordered set of a complete lattice) in fact hold for any partially ordered set A.

(b) Let C be a complete lattice, and A a nonempty subset of C. Then the following conditions are equivalent. (b.1) As a partially ordered set, A forms a complete lattice. (b.2) A has a greatest element, and forms a complete lower subsemilattice of a complete upper subsemilattice B of C having a least element. (b.2*) A has a least element, and forms a complete upper subsemilattice of a complete lower subsemilattice B of C having a greatest element.

(Note: in (b.2) and (b.2*), the statement that A is a complete lower or upper subsemilattice of B means that it is closed under the relevant meet or join operations of B, not under those of C, which do not in general carry B into itself.)

Sketch of proof. (a): The versions of condition (ii) listed here all involve embeddings of A as a partially ordered set in a certain complete semilattice B, which, by adjoining a greatest or least element if necessary, can be assumed a complete lattice. The mutual equivalence of these conditions for complete lattices, applied to B, gives embeddings of B; these in turn lead to the embeddings of A as a partially ordered set that we want. The same method yields the implication (ii) ⟹ (iii). The proofs of the remaining implications were entirely order-theoretic, and go over unchanged.

(b): Clearly (b.2) ⟹ (b.1). On the other hand, if A satisfies (b.1), and one lets B denote the result of closing A in C under arbitrary joins and throwing in the least element, then one finds that arbitrary meets in A are still meets under the operation of B, so that B witnesses (b.2). Thus, (b.1) ⟺ (b.2), and by duality, (b.1) ⟺ (b.2*).

References

[1] R. Baer, Die Kompositionsreihe der Gruppe aller eineindeutigen Abbildungen einer unendlichen Menge auf sich, Studia Math. 4 (1934) 15–17.

[2] George M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978) 178–218. MR 81b:16001.

[3] 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.

[4] George M. Bergman, Generating infinite symmetric groups, J. London Math. Soc. 38 (2006) 429-440. MR 2007e:20004.

[5] George M. Bergman, Two statements about infinite products that are not quite true, pp.35–58 of Groups, Rings and Algebras (Proceedings of a conference in honor of Donald S. Passman), ed. W. Chin, J. Osterburg and D. Quinn, Contemporary Mathematics, v.420, 2006. MR 2279231.

[6] George M. Bergman and Saharon Shelah, Closed subgroups of the infinite symmetric group, Algebra Universalis 55 (2006) 137-173. MR 2280223.

[7] 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 [8], the result quoted from [14] at p.561, 6th paragraph should exclude the countable case, and the result quoted from [1] at p.566, 3rd from last paragraph, should include, when n = ℵ_{0}, the case of the infinite alternating group.)

[8] 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.

[9] R. M. Bryant and V. A. Roman’kov, The automorphism groups of relatively free algebras, J. Algebra 209 (1998) 713–723. MR 99k:20073.

[10] Manfred Droste and Rüdiger Göbel, Uncountable cofinalities of permutation groups, J. London Math. Soc. (2) 71 (2005) 335–344. MR 2006a:20008.

[11] Manfred Droste and W. Charles Holland, Generating automorphism groups of chains, Forum Math. 17 (2005) 699–710. MR 2006c:06023.

[12] Ulrich Felgner and Frieder Haug, The homomorphic images of infinite symmetric groups, Forum Math. 5 (1993) 505–520. MR 95e:20007.

[13] Nathan Jacobson, Lectures in abstract algebra. Volume II: Linear algebra, Van Nostrand, 1953, and Springer GTM, No. 31, 1975. MR 14,837e and MR 51#5614.

[14] Bjarni Jónsson, Universal relational systems, Math. Scand. 4 (1956) 193–208. MR 20#3091.

[15] Roger C. Lyndon and Paul E. Schupp, Combinatorial Group Theory, Springer-Verlag, Ergebnisse der Math. u. ihrer Grenzgebiete, v.89, 1977. MR 58#28182.

[16] Ralph McKenzie, A note on subgroups of infinite symmetric groups, Nederl. Akad. Wetensch. Proc. Ser. A74 = Indag. Math. 33 (1971) 53–58. MR 45#3545.

[17] W. Sierpiński, Sur une décomposition d’ensembles, Monatsh. Math. 35 (1928) 239–248. http://www. springerlink.com/index/G613664821643112.pdf

[18] R. M. Solovay and S. Tennenbaum, Iterated Cohen extensions and Souslin’s problem, Ann. of Math. (2) 94 (1971) 201–245. MR 45#3212.

[19] Friedrich Wehrung, Embedding monoids of self-maps, (in preparation, title tentative; July 2007 draft, 5 pp.).

[20] Friedrich Wehrung, Embedding coproducts of partition lattices, (in preparation, title tentative; July 2007 draft, 10 pp.).

[21] Philip M. Whitman, Lattices, equivalence relations, and subgroups, Bull. Amer. Math. Soc. 52 (1946) 507–522. MR 8,62b.

George M. Bergman Department of Mathematics University of California Berkeley, CA 94720-3840 USA gbergman@math.berkeley.edu