Direct limits and fixed point sets ⋆

George M. Bergman

University of California, Berkeley, CA 94720-3840, USA gbergman@math.berkeley.edu

Abstract

For which groups G is it true that whenever one forms a direct limit of left G-sets, \underrightarrow{lim}_{i∈I} X_{i}, the set of its fixed points, (\underrightarrow{lim}_{I} X_{i})^{G}, can be obtained as the direct limit \underrightarrow{lim}_{I}(X_{i}^{G}) of the fixed point sets of the given G-sets? An easy argument shows that this is the case if and only if G is finitely generated.

If we replace “group G” by “monoid M”, the answer is the less familiar condition that the improper left congruence on M be finitely generated; equivalently, that M be finitely generated under multiplication and “right division”.

Replacing our group or monoid with a small category E, the concept of a set on which G or M acts with that of a functor E → Set, and the fixed point set of an action with the limit of a functor, a criterion of a similar nature is proved. Specialized criteria are obtained in the cases where E has only finitely many objects and where E is a (generally infinite) partially ordered set.

If one allows the codomain category Set to be replaced with other categories, and/or allows direct limits to be replaced with other classes of colimits, one enters a vast area open to further investigation.

Key words: action of a group or monoid on a set; set-valued functor on a category; commutativity of limits with direct limits (filtered colimits); partially ordered set.

1 Introduction.

Although the next three sections, concerning fixed point sets of group and monoid actions, require no familiarity with category theory, I will (with apolo-

⋆ 2000 Mathematics Subject Classifications. Primary: 18A30. Secondary: 06A06, 18B05, 18B35, 18B45, 20A99, 20M30. Preprint versions: http://math.berkeley.edu/ ∼gbergman/papers/dirlimfix.{tex,dvi,ps}, arXiv:math.CT/0306127.

Preprint submitted to Elsevier Science 23 August 2005

gies to the non-categorical reader) frame this introduction in category-theoretic terms.

It is a familiar observation that “left universal constructions respect left universal constructions and right universal constructions respect right universal constructions” [1, §§7.7-7.8]. Thus, when one takes a limit of limits, or a colimit of colimits (in a context where the relevant limits or colimits all exist), one can reverse the order of the two limit operations, or of the two colimit operations, without changing the result. In contrast, left and right universal constructions do not in general respect one another. (For instance, the free group on a direct product set X × Y is not isomorphic to the direct product of the free group on X and the free group on Y).

But there are classes of cases where, anomalously, certain limits commute with certain colimits. For instance, given directed systems of sets (X_{i})_{I} and (Y_{i})_{I} indexed by the same partially ordered set I, one finds that \underrightarrow{lim}(X_{i} × Y_{i}) ≅ (\underrightarrow{lim}X_{i}) × (\underrightarrow{lim}Y_{i}). Indeed, the fact that we can construct a direct limit of algebras by putting an algebra structure on the direct limit of their underlying sets is a consequence of this fact, given that algebra operations on X are set maps X× ⋯ ×X → X.

This note investigates the question of which small categories E have the property that limits of functors from E to Set always commute with direct limits, that is, with colimits over directed partially ordered sets. It has been observed [15, Thm. IX.2.1, p.211], [12, Thm. 4.73, p.72] that this happens if E is a finite category, i.e., has only finitely many objects and finitely many morphisms. More generally, it occurs whenever E has finitely many objects and finitely generated morphism-set ([1, Prop. 7.9.3] = Corollary 8 below). The result of §2 (first paragraph of the above abstract) is equivalent to the statement that if E is a one-object category whose morphisms form a group, this finite generation condition is necessary as well as sufficient.

In a general one-object category E, the morphisms form a monoid M. By the result noted above, finite generation of M is sufficient for the construction of limits over E (i.e., fixed-point sets of M-sets) to commute with that of direct limits, but in this case it is not necessary. In §4 we obtain two criteria each of which is necessary as well as sufficient. We find in §5 that one of these, finite generation of the improper left congruence on M, when reformulated as finite presentability of the trivial M-set, generalizes to arbitrary small categories E, while the other, finite generation of M under multiplication and “right division”, generalizes nicely to categories E with finitely many objects.

In §7 we examine the case where E is the category J_{cat} induced by a partially ordered set J, and translate our general criterion into a condition on J. Half of the condition we get can be stated in familiar language: It says that the set of minimal elements of J is finite, and every element lies above a minimal element. (This is in fact necessary and sufficient for the comparison maps associated with our limits and colimits to be injective in all cases; it is also necessary for them always to be surjective.) The remaining condition appears to be new. In language which we shall define, it says that the set of elements of J “critical” with respect to the minimal elements is finite, and that these critical elements “gather” all minimal elements under every element of J.

Note that the results of this paper only concern limits and colimits of functors to Set; the behavior of functors to other categories can be strikingly different. For instance [1, Exercise 7.9.5], in Set^{op}, direct limits do not in general commute with equalizers, though equalizers are limits over a certain finite category; but they do commute with not necessarily finite small products; so we have both negative and positive deviations from the behavior of Set-valued functors. Clearly, it would be interesting to investigate more classes of cases of commutativity between limits and colimits: for functors with codomains other than Set, and for colimits over categories other than directed partially ordered sets. If we fix one of the three variables – the small category over which we take limits, the small category over which we take colimits, and the codomain category – then we get a Galois connection [1, §5.5] on the other two, and can study the resulting closure operators. The exercises in [15, §IX.2] and the results and exercises at the end of [1, §7.9] give scattered results along these lines, but for the most part, the topic seems wide open for study!

I am indebted to Birge Huisgen-Zimmermann and Ken Goodearl for organizing the gathering at which I first spoke about some of these results, to Max Kelly, Arthur Ogus, and Boris Schein for references to the literature, and to the referee for several helpful corrections and suggestions.

The present note has various possible audiences, ranging from any mathematician who uses direct limits, to the specialist in semigroups or categories or partially ordered sets. I hope the reader will be patient with my reviewing details that may be familiar to him or her, and also with my following, in §3, a somewhat leisurely path of motivation to the results on monoids.

2 Direct limits and group actions.

Recall that a partially ordered set (I, ≤) is said to be directed if for every pair of elements i, j ∈ I, there exists k ∈ I majorizing both, i.e., satisfying k ≥ i and k ≥ j. A directed system of sets means a family of sets (X_{i})_{i∈I} indexed by a nonempty directed partially ordered set I, and given with connecting maps α_{i,j}: X_{i} → X_{j} (i ≤ j) such that each α_{i,i} is the identity map of X_{i}, and whenever i ≤ j ≤ k, one has α_{i,k} = α_{j,k} α_{i,j}. (So a more complete notation for the directed system is (X_{i}, α_{i,j})_{i,j∈I}.)

In this situation one has the concept of the direct limit of the given system. This is constructed by forming the disjoint union ⨆_{I} X_{i}, and dividing out by the least equivalence relation ∼ such that x ∼ α_{i,j}(x) whenever x ∈ X_{i} and i ≤ j. Denoting the resulting set \underrightarrow{lim}_{I} X_{i}, and writing [x] for the equivalence class therein of x ∈ ⨆_{I} X_{i}, we get, for each j ∈ I, a map α_{j,∞}: X_{j} → \underrightarrow{lim}_{I} X_{i} taking x ∈ X_{j} to [x]. The characterization of \underrightarrow{lim}_{I} X_{i} that we will use here is that it is a set given with maps α_{j,∞}: X_{j} → \underrightarrow{lim}_{I} X_{i} for each j ∈ I, such that every element of \underrightarrow{lim}_{I} X_{i} is of the form α_{j,∞}(x) for some j ∈ I, x ∈ X_{j}, and such that

(1) α_{i,∞}(x) = α_{j,∞}(y) if and only if there exists k ≥ i, j such that α_{i,k}(x) = α_{j,k}(y).

Property (1) is easily deduced from the above construction of \underrightarrow{lim}_{I} X_{i}, using the directedness of I. Note that it includes the relations

(2) α_{i,∞}(x) = α_{j,∞}(α_{i,j}(x)) (i ≤ j ∈ I, x ∈ X_{i})

corresponding to the generators of the equivalence relation in that construction.

If G is a group, then a directed system of left G-sets means a directed system (X_{i}, α_{i,j})_{i,j∈I} of sets, such that each X_{i} is given with a left action of G, and each of the connecting maps α_{i,j} is a morphism of G-sets (a G-equivariant map). Henceforth we will generally omit the qualifier “left”. Given such a directed system, it is easy to verify that \underrightarrow{lim}_{I} X_{i} admits a unique G-action making the maps α_{i,∞} morphisms of G-sets, i.e., such that

(3) g α_{i,∞}(x) = α_{i,∞}(gx) (g ∈ G, i ∈ I, x ∈ X_{i}).

For any G-set X, let us write

X^{G} = {x ∈ X | (∀g ∈ G) gx = x}

for the fixed-point set of the action. If (X_{i}, α_{i,j})_{i,j∈I} is a directed system of G-sets, we see that each map α_{i,j} carries the fixed set X_{i}^{G} into X_{j}^{G}. Writing β_{i,j} for the restriction of α_{i,j} to a map X_{i}^{G} → X_{j}^{G}, we thus get a directed system of sets (X_{i}^{G}, β_{i,j}), and we can form its direct limit \underrightarrow{lim}_{I} X_{i}^{G}.

It is now straightforward to verify that one has a map

(4) ι : \underrightarrow{lim}_{I} X_{i}^{G} ⟶ (\underrightarrow{lim}_{I} X_{i})^{G}, defined by ι(β_{i,∞}(x)) = α_{i,∞}(x) (x ∈ X_{i}^{G}).

Theorem 1 If G is a group, I a directed partially ordered set, and (X_{i}, α_{i,j})_{i,j∈I} a directed system of G-sets, then the set-map ι of (4) is one-to-one.

Moreover, for any group G, the following conditions are equivalent:

(5) For every directed partially ordered set I and directed system (X_{i}, α_{i,j})_{i,j∈I} of G-sets, the set-map ι of (4) is bijective.

(6) G is finitely generated.

PROOF. The assertion of the first sentence follows from (1) and the fact that the maps β_{i,j} are restrictions of the α_{i,j}.

To see that (6) implies (5), let {g_{1}, …, g_{n}} be a finite generating set for G, and consider any element of (\underrightarrow{lim}_{I} X_{i})^{G}, which we may write α_{i,∞}(x) for some i ∈ I and x ∈ X_{i}. The element x ∈ X_{i} may not itself be fixed under G, but by assumption, for every g ∈ G we have g α_{i,∞}(x) = α_{i,∞}(x), in other words, α_{i,∞}(gx) = α_{i,∞}(x). By (1) this means that for each g ∈ G there exists k(g) ≥ i in I such that α_{i,k(g)}(gx) = α_{i,k(g)}(x).

Since I is directed, we can find a common upper bound k for k(g_{1}), …, k(g_{n}), and we see from the G-equivariance of the maps α_{k(g_{j}),k} that α_{i,k}(x) will be invariant under all of {g_{1}, …, g_{n}}, hence will belong to X_{k}^{G}. The element β_{k,∞}(α_{i,k}(x)) is thus an element of \underrightarrow{lim}_{I} X_{i}^{G}, and (2) shows that it is mapped by (4) to the given element α_{i,∞}(x) ∈ (\underrightarrow{lim}_{I} X_{i})^{G}, as required.

Conversely, if G is a non-finitely-generated group, let I be the set of finitely generated subgroups of G, partially ordered by inclusion; this is clearly a directed partially ordered set. For each H ∈ I, let X_{H} be the transitive G-set G/H, and define connecting maps by α_{H_{1},H_{2}}(gH_{1}) = gH_{2} for H_{1} ≤ H_{2}; this gives a directed system. Since each H ∈ I is a proper subgroup of G, each of the G-sets X_{H} satisfies (X_{H})^{G} = ∅, so \underrightarrow{lim}_{I} (X_{H})^{G} = ∅. On the other hand, any two elements g_{1}H_{1} ∈ X_{H_{1}} and g_{2}H_{2} ∈ X_{H_{2}} have the same image in X_{H_{3}} for any H_{3} containing H_{1}, H_{2}, and g_{1}^{−1}g_{2} , so \underrightarrow{lim}_{I} X_{H} is the one-point G-set. Thus (\underrightarrow{lim}_{I} X_{H})^{G} ≠ ∅, and (5) fails. □

Digression. One may ask whether (5) is equivalent to the corresponding statement with I restricted to be the set ℕ of natural numbers with the usual ordering ≤, this being the kind of direct limit one generally first learns about. If we call this weakened condition (5_{ℕ}), I claim the proof of Theorem 1 may be adapted to show that (5_{ℕ}) is equivalent to

(6_{ℕ}) Every chain H_{0} ≤ H_{1} ≤ … of subgroups of G indexed by ℕ and having union G is eventually constant.

Indeed, suppose G is a group for which (5_{ℕ}) fails, so that we have a directed system (X_{i})_{i∈ℕ} and an element α_{j,∞}(x) ∈ (\underrightarrow{lim}_{ℕ} X_{i})^{G} which is not in the image of ι. Then no α_{j,k}(x) lies in X_{k}^{G}, and letting H_{i} be the isotropy subgroup of α_{j,j+i}(x) for each i, it is easy to see that these subgroups give a counterexample to (6_{ℕ}). Conversely, if we have a counterexample to (6_{ℕ}), then setting X_{i} = G/H_{i} gives a counterexample to (5_{ℕ}).

But are there any groups that satisfy (6_{ℕ}) and not (6)? Clearly (6_{ℕ}) cannot hold in any countable non-finitely-generated group. It will also fail in any group which admits a homomorphism onto a group in which it fails, from which one can show that it fails in any non-finitely-generated abelian group [2, paragraph following Question 8]. However, examples are known of uncountable nonabelian groups that satisfy (6_{ℕ}): Infinite direct powers of nonabelian simple groups [13], full permutation groups on infinite sets [16,2], and others [5,6,19,20].

(Groups satisfying (6_{ℕ}) but not (6) are said to be of “uncountable cofinality”. The same condition on modules has been studied under a surprising variety of names [8, p.895, top paragraph].)

3 Monoid actions – initial observations.

If we replace the group G of the preceding section with a general monoid M, a large part of the discussion goes over unchanged. Given a directed system (X_{i}, α_{i,j})_{i,j∈I} of left M-sets, we get an M-set structure on \underrightarrow{lim}_{I} X_{i}, and there is a natural map

(7) ι : \underrightarrow{lim}_{I} X_{i}^{M} ⟶ (\underrightarrow{lim}_{I} X_{i})^{M} given by ι(β_{i,∞}(x)) = α_{i,∞}(x) (x ∈ X_{i}^{M}),

which is always one-to-one; and again we may ask for which M it is true that

(8) For every directed partially ordered set I and directed system (X_{i}, α_{i,j})_{i,j∈I} of M-sets, the set-map ι of (7) is bijective.

The argument used in the proof of Theorem 1, (6) ⟹ (5), shows that a sufficient condition is

(9) M is finitely generated.

Attempting to reproduce the converse argument, we can say, as before, that if M is not finitely generated its finitely generated submonoids N form a directed partially ordered set; however, there is no concept of factor-M-set M/N, as would be needed to continue the argument.

And in fact, there exist non-finitely-generated monoids for which (8) holds. For instance, let M be the multiplicative monoid of any field F; note that 0 ∈ M. Given an element α_{j,∞}(x) ∈ (\underrightarrow{lim}_{I} X_{i})^{M}, we have α_{j,∞}(x) = 0 α_{j,∞}(x) = α_{j,∞}(0x), hence there exists k ∈ I such that α_{j,k}(x) = α_{j,k}(0x). We now observe that for every u ∈ M we have

u α_{j,k}(x) = u α_{j,k}(0x) = α_{j,k}((u 0)x) = α_{j,k}(0x) = α_{j,k}(x),

so α_{j,k}(x) ∈ X_{k}^{M}, so the arbitrary element α_{j,∞}(x) ∈ (\underrightarrow{lim}_{I} X_{i})^{M} is in the image of (7).

Recalling that an element z of a monoid M is called a right zero element if uz = z for all u ∈ M, we see that the above argument shows that a sufficient condition for (8) to hold, clearly independent of (9), is

(10) M has at least one right zero element.

With a little thought, one can come up with a common generalization of (9) and (10). Recall that a left ideal of a monoid means a subset L closed under left multiplication by all elements of M. Combining the ideas of the two preceding arguments, one can show that (8) holds if

(11) M has a nonempty left ideal L which is finitely generated as a semigroup.

But we can generalize this still further. We don’t need left multiplication by every element of M to send every element of L into L. We claim it suffices to assume that

M has a finitely generated subsemigroup S such that {a ∈ M | aS ∩ S ≠ ∅} generates M.

Indeed, assuming the above holds, and given as before a directed system (X_{i})_{i∈I} of M-sets and an element α_{j,∞}(x) ∈ (\underrightarrow{lim}_{I} X_{i})^{M}, choose k ≥ j such that for all elements g of a finite generating set for S, we have g α_{j,k}(x) = α_{j,k}(x); thus α_{j,k}(x) is invariant under the action of S. Writing α_{j,k}(x) = y, note that for any a ∈ M such that aS ∩ S ≠ ∅, if we take s, t ∈ S such that as = t, and apply the two sides of this equation to y, we get ay = y, showing that y is fixed under the action of each such element a. Since such elements generate M, we can conclude that y ∈ X_{k}^{M}, from which (8) follows as before.

In the condition just considered, nothing is lost if we replace the semigroup S by the monoid S ∪ {1}. (The same was not true of (11), where the property of being an ideal would have been lost.) So let us formulate that condition in the more natural form (12) M has a finitely generated submonoid M_{0} such that {a ∈ M |

aM_{0} ∩ M_{0} ≠ ∅} generates M.

To see that this is strictly weaker than (11), consider the monoid presented by infinitely many generators x_{n} (n ∈ ℕ) and y, and the relations saying that all the elements x_{n}y (n ∈ ℕ) are equal. Then (12) holds with M_{0} the submonoid generated by {y, x_{0}y}, but one can verify that there is no left ideal L as in (11). (In particular, the left ideal My is not finitely generated as a semigroup: the infinitely many elements x_{n}x_{0}y (n ∈ ℕ) cannot be obtained using finitely many elements of that ideal.)

Note that in condition (12), one obtains the elements of M_{0} from a finite generating set using arbitrarily many multiplications; then gets each element a in the set-bracket expression from two elements of M_{0} by an operation of “right division”, and then obtains the general element of M from these by again using arbitrarily many multiplications. Looked at this way, it would be more natural to allow arbitrary sequences of multiplications and right divisions; i.e., to consider the condition

(13) There exists a finite subset S ⊆ M such that the least subset N ⊆ M satisfying (i) S ∪ {1} ⊆ N, (ii) a, b ∈ N ⟹ ab ∈ N and (iii) ab, b ∈ N ⟹ a ∈ N, is M itself.

We shall see in the next section that this, too implies (8). That (13) is weaker than (12) may be seen by considering the monoid with presentation

M = ⟨x_{n}, y_{n}, z, w (n ∈ ℕ) | x_{n}y_{n}z = z, y_{n}w = w⟩.

Namely, one can show that given a finitely generated submonoid M_{0} ⊆ M, only finitely many of the elements x_{n} can satisfy x_{n}M_{0} ∩ M_{0} ≠ ∅, hence not all x_{n} will appear in the set-expression shown in (12), so, as these elements are irreducible, (12) cannot hold. However, starting with the finite set {z, w}, the “right division” process of (13) gives us all elements of the forms x_{n}y_{n} and y_{n}, another application of right division gives all elements x_{n}, and from the y_{n}, the x_{n}, and the original two elements z and w, closure under multiplication produces all of M.

4 Left congruences, and a precise criterion.

To approach more systematically the problem of characterizing monoids that satisfy (8), let us recall a useful heuristic for generalizing results about groups G and G-sets to monoids M and M-sets:

(14) Groups : normal subgroups : subgroups : :

monoids : congruences : left congruences.

Normal subgroups N of a group G classify the homomorphic images f(G) of G, by listing the elements that fall together with 1 under f. To determine the structure of a homomorphic image f(M) of a monoid M, it is not sufficient to consider elements that fall together with 1; instead one must look at the set of all pairs of elements that fall together, C = {(a, b) ∈ M×M | f(a) = f(b)}. Sets C that arise in this way are called congruences on M; these are precisely the subsets C ⊆ M×M such that

(15) C is an equivalence relation which is closed under left and right translation by elements of M.

When we study the structures of left G-sets X for G a group, the key concept is the set G_{x} of elements of G fixing a given x ∈ X, which may be any subgroup. For M a monoid and x an element of a left M-set, the analogous entity is the set C_{x} = {(a, b) ∈ M×M | ax = bx}. This can be any subset C ⊆ M×M satisfying

(16) C is an equivalence relation closed under left translation by all elements of M.

Such a set is called a left congruence on M.

For G a group, every G-set is a disjoint union of orbits Gx ≅ G/H. There is no such simple structure theorem for a set X on which a monoid M acts. Nevertheless, such an X is, of course, a union of orbits Mx ≅ M/C_{x}, and this fact will allow us to reduce (8) to a condition on left congruences.

(Aside: We have mentioned 2-sided congruences, i.e., sets satisfying (15), only for perspective. Right actions of monoids lead to a third concept, that of a right congruence, left-right dual to (16). But since right actions of M are equivalent to left actions of the opposite monoid, we lose no generality by restricting attention in this note to left M-sets.)

Given a monoid M and a subset R ⊆ M×M, there is a least left congruence C containing R, the left congruence generated by R, obtained by closing R under the obvious operations (one each to obtain reflexivity, symmetry, transitivity, and left translation by each element of M). Thus, one can speak of a left congruence being finitely generated.

The whole set M×M constitutes the improper left congruence on M. We shall now show that the necessary and sufficient condition on a monoid M for (8) to hold is (17) The improper left congruence on M is finitely generated.

Moreover, we will find that the final condition (13) of the preceding section is also equivalent to this.

The reader who is inclined to skip the proof below as straightforward should note that the step (8) ⟹ (17) involves an unexpected hiccup; I therefore recommend reading at least that step.

Theorem 2 If M is a monoid, I a directed partially ordered set, and (X_{i}, α_{i,j})_{i,j∈I} a directed system of M-sets, then the set-map ι of (7) is oneto-one.

Moreover, for any monoid M, the following implications hold among the conditions introduced above:

(9)

⇓

(10) ⟹ (11) ⟹ (12) ⟹ (13) ⟺ (8) ⟺ (17).

PROOF. The first assertion and the implications through (13) have already been noted. (Moreover, none of those implications is reversible; examples were given where this was not obvious.) We shall complete the proof by showing (13) ⟹ (8) ⟹ (17) ⟹ (13).

Given a finite set S as in (13) and an element α_{j,∞}(x) ∈ (\underrightarrow{lim}_{I} X_{i})^{M}, let us take k ∈ I such that the finitely many relations s α_{j,k}(x) = α_{j,k}(x) (s ∈ S) all hold, and let y = α_{j,k}(x). Then it is easy to check that the set N = {s ∈ M | sy = y} satisfies conditions (i)-(iii) of (13), hence is all of M. Thus y is an element of X_{k}^{M} mapping to the given element α_{j,∞}(x) of (\underrightarrow{lim}_{I} X_{i})^{M}, proving (8).

The proof that (8) ⟹ (17) starts like the corresponding argument for groups: If the improper left congruence on M is not finitely generated, let I be the set of all finitely generated left congruences on M, partially ordered by inclusion. The M-sets X_{C} = M/C (C ∈ I) will form a directed system such that \underrightarrow{lim}_{I} X_{C} is the 1-element M-set; hence (\underrightarrow{lim}_{I} X_{C})^{M} ≠ ∅; but we claim that each set X_{C}^{M} (C ∈ I) is empty.

For assume, on the contrary, that X_{C}^{M} were nonempty. If M were a group, that would make X_{C} a singleton, hence it would make C the improper left congruence, a contradiction. For M a general monoid, we can only conclude that some equivalence class [a] ∈ X_{C} is fixed under the action of M. However, given such an [a], let C′ be the left congruence on M generated by C and the one additional pair (a, 1). Then in M/C′ the generating element [1] = [a] is M-fixed, so C′ is the improper left congruence, this time indeed contradicting the assumption that the latter is not finitely generated.

Finally, to show (17) ⟹ (13), suppose {(a_{1}, b_{1}), …, (a_{n}, b_{n})} is a finite generating set for the improper left congruence on M. Let S = {a_{1}, …, a_{n}, b_{1}, …, b_{n}}, let N be the set constructed from S as in (13), and let U ⊆ M×M be the set of ordered pairs which can be written (as, at) with a ∈ M and s, t ∈ N. By the closure properties of N we see that each (as, at) ∈ U either has both components in N (if a ∈ N, by (13)(ii)) or neither (if a ∉ N, by (13)(iii)). It follows that the least equivalence relation C containing U will not relate elements in N with elements not in N. Moreover, U is closed under left translation by members of M, hence so is C, i.e., C is a left congruence on M. But C contains {(a_{1}, b_{1}), …, (a_{n}, b_{n})}, so by choice of this set, C must be the improper left congruence; hence as it does not relate elements in N with elements not in N, we must have N = M, establishing (13). □

We remark that none of conditions of the above theorem except (9) is rightleft symmetric. Indeed, let M consist of the identity element and an infinite set S of right-zero elements. Then M satisfies (10), hence satisfies all these conditions other than (9), but I claim that the opposite monoid M^{op} does not satisfy (17), hence does not satisfy any of the conditions shown. For any equivalence relation on the underlying set of a monoid respects both left multiplication by the identity and left multiplication by any left zero element; hence every equivalence relation on M^{op} is a left congruence; but the improper equivalence relation on an infinite set is not finitely generated.

Incidentally, there is a simpler example for monoids than for groups showing that (8) can fail but the analogous statement (8_{ℕ}) on direct limits indexed by the natural numbers hold; equivalently, that the improper left congruence may be non-finitely generated, yet not expressible as the union of a countable chain of proper left congruences. Let M = ω_{1}, the first uncountable ordinal, made a monoid under the commutative binary operation sup. Every left congruence on M corresponds to a decomposition into disjoint convex sets (i.e., intervals); let us associate to each proper left congruence C the least α ∈ ω_{1} such that (0, α) ∉ C. By considering the sequence of ordinals associated in this way with a countable ascending chain of such left congruences, we see that its union cannot be the improper left congruence.

Before leaving the topic of monoids and their left congruences, let me mention a tantalizing open question of Hotzel [11] (slightly restated): If a monoid M has ascending chain condition on left congruences, must M be finitely generated? An affirmative answer has been proved under the assumption of ascending chain condition on both right and left congruences [14]. For some further observations see [17, Problem 1].

5 Functors on small categories.

As noted in the introduction, a monoid M can be regarded as the system of morphisms of a one-object category E. An M-set X is then equivalent to a functor E → Set, and the fixed-point set of the action of M on X is the limit of that functor. In the remaining sections, we shall extend the ideas of the preceding section by replacing fixed-point sets of monoid actions with limits of set-valued functors on a general small category.

If E is a small category we shall, to maintain parallelism with preceding sections, call a covariant functor E → Set an “E-set”, and denote such functors by X and neighboring letters. Objects of E will generally be denoted E, F, … and morphisms of E by letters a, b, …. For E, F ∈ Ob(E), the set of morphisms E → F will be written E(E, F). We will assume that E(E, F) and E(E′, F′) are disjoint unless E = E′ and F = F′. If α : X → X′ is a morphism of E-sets, its component set-maps will be denoted α(E) : X(E) → X′(E) (E ∈ Ob(E)).

We recall that if X is an E-set, then \underleftarrow{lim}_{E} X can be constructed as the set of Ob(E)-tuples x = (x_{E})_{E∈Ob(E)}, with x_{E} ∈ X(E) for each E ∈ Ob(E), which satisfy the “compatibility” conditions

(18) (∀ E, F ∈ Ob(E), a ∈ E(E, F)) X(a)(x_{E}) = x_{F} .

By a directed system of E-sets we shall mean a family of E-sets (X_{i})_{i∈I} indexed by a nonempty directed partially ordered set I, and given with morphisms of E-sets α_{i,j}: X_{i} → X_{j} (i ≤ j ∈ I) such that each α_{i,i} is the identity morphism of the E-set X_{i}, and for i ≤ j ≤ k ∈ I, one has α_{i,k} = α_{j,k} α_{i,j}.

Given such a system, we see that for each E ∈ Ob(E), the sets X_{i}(E) (i ∈ I) and set-maps α_{i,j}(E): X_{i}(E) → X_{j}(E) form a directed system of sets. If we take the direct limit of each of these systems, functoriality of the direct limit construction yields, for each morphism a ∈ E(E, F), a set-map \underrightarrow{lim}_{i∈I} X_{i}(E) → \underrightarrow{lim}_{i∈I} X_{i}(F) which we shall write (\underrightarrow{lim}_{i∈I} X_{i})(a), and whose action on elements is described by

(19) (\underrightarrow{lim}_{i∈I} X_{i})(a)(α_{j,∞}(E)(y)) = α_{j,∞}(F)(X_{j}(a)(y)) (y ∈ X_{j}(E)).

These maps together make the family of direct-limit sets (\underrightarrow{lim}_{i∈I} X_{i}(E))_{E∈Ob(E)} into an E-set, which we shall denote \underrightarrow{lim}_{i∈I} X_{i}. (It is not hard to show that this E-set is in fact the direct limit, i.e., colimit [15, p.67], [1, §§7.5-7.6], of the directed system (X_{i})_{i∈I} in the category of E-sets, though we shall not need that fact.) As with any E-set, we can take its category-theoretic limit, getting a set

\underleftarrow{lim}_{E} (\underrightarrow{lim}_{i∈I} X_{i}).

On the other hand, starting with our original directed system (X_{i})_{i∈I} of Esets, we can take the limit over E of each E-set X_{i}, getting a system of sets (\underleftarrow{lim}_{E} X_{i})_{i∈I}. The functoriality of this limit construction yields connecting maps which we may denote

\underleftarrow{lim}_{E} α_{i,j}: \underleftarrow{lim}_{E} X_{i} → \underleftarrow{lim}_{E} X_{j} (i ≤ j ∈ I),

so we may form the direct limit of these sets, getting a set

\underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}).

And once again there is a natural set-map connecting these constructions,

(20) ι : \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}) ⟶ \underleftarrow{lim}_{E} (\underrightarrow{lim}_{i∈I} X_{i}).

To describe ι explicitly, consider an element of \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}), written as α_{i,∞}(x) for some i ∈ I and x ∈ \underleftarrow{lim}_{E} X_{i}. Since x is an Ob(E)-tuple (x_{E}) satisfying (18), we can apply α_{i,∞}(E) to each component x_{E}, getting an Ob(E)- tuple of elements of the sets \underrightarrow{lim}_{i∈I} X_{i}(E) (E ∈ Ob(E)). The compatibility conditions (18) on the components x_{E} of the given element (x_{E}) imply the compatibility of the components of the resulting family (α_{i,∞}(E)(x_{E}))_{E∈Ob(E)}, so that this becomes an element of \underleftarrow{lim}_{E} (\underrightarrow{lim}_{i∈I} X_{i}), which is easily shown to be independent of the choice of expression α_{i,∞}(x) for our given element of \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}).

This time, however, even injectivity of ι is not automatic. To obtain a criterion for it to hold, we will use a lemma on partially ordered sets. Recall that a subset D of a partially ordered set J is called a downset (or “order ideal”) if s < t ∈ D ⟹ s ∈ D. We shall regard the set of downsets of any partially ordered set as ordered by inclusion. A partially ordered set is called downward directed (the dual of “directed”) if for any two elements u, v of the set, there is an element w majorized by both of them.

Lemma 3 Let J be a partially ordered set. Then the following conditions are equivalent:

(21) There exists a finite subset A ⊆ J such that every element of J majorizes at least one element of A .

(22) J has only finitely many minimal elements, and every element of J majorizes a minimal element.

(23) Every set S of nonempty downsets of J which is nonempty and downward directed under inclusion has nonempty intersection.

PROOF. Clearly (22) ⟹ (21). To show (21) ⟹ (23), let A be as in (21), let S be as in the hypothesis of (23), and for each a ∈ A which does not belong to all the elements of S, choose an element s(a) ∈ S not containing a. Since A is finite and S is downward directed, we can find some s ∈ S which is majorized by (i.e., is a subset of) all these sets s(a). Being a nonempty downset, s must contain some element of A by (21), and by choice of s that element belongs to all members of S, proving (23).

Finally, assuming (23) we will prove (22). On the one hand, (23), applied to chains S and combined with Zorn’s Lemma (used upside down) shows that every nonempty downset contains a minimal nonempty downset, which must be a singleton consisting of a minimal element; hence every element of J majorizes a minimal element. Moreover, if the set of minimal elements were infinite, then the set S of cofinite subsets of that set would be a counterexample to (23); so there are indeed only finitely many minimal elements. □

We can now get a criterion for the injectivity of the set-maps ι, and a little more.

Proposition 4 If E is a small category, the following conditions are equivalent:

(24) For every directed partially ordered set I and directed system (X_{i}, α_{i,j})_{i,j∈I} of E-sets, the set-map ι of (20) is one-to-one.

(25) There exists a finite family A of objects of E such that every object of E admits a morphism from one of the objects of A.

Moreover, condition (25) is also necessary for the map ι to be surjective for all directed systems.

PROOF. First, assume (25), and let us be given two elements α_{j,∞}(x) and α_{j′,∞}(y) in \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}) (where x = (x_{E})_{E∈Ob(E)} and y = (y_{E})_{E∈Ob(E)}), having the same image in \underleftarrow{lim}_{E} (\underrightarrow{lim}_{i∈I} X_{i}). Thus, the images of these two Ob(E)-tuples agree in each component \underrightarrow{lim}_{i∈I} X_{i}(E) (E ∈ Ob(E)). By the directedness of I we can find k majorizing both j and j′ and such that for each of the finitely many objects E ∈ A, α_{j,k}(E)(x_{E}) and α_{j′,k}(E)(y_{E}) coincide. Now by assumption, every F ∈ Ob(E) admits a morphism from one of the objects E ∈ A, so the conditions (18) on the Ob(E)-tuples α_{j,k}(x_{E}) and α_{j′,k}(y_{E}) show that the F-components of these tuples coincide as well. Hence α_{j,k}(x) = α_{j′,k}(y); hence α_{j,∞}(x) = α_{j′,∞}(y), proving (24).

To get the converse, let us define a preordering on Ob(E) by writing E ≤ F if there exists a morphism from E to F, and let J be the partially ordered set obtained by dividing Ob(E) by the equivalence relation “E ≤ F ≤ E ”. If (25) fails, this says that J does not satisfy (21), hence by the preceding lemma we can find a downward directed set S of nonempty downsets in J having empty intersection. We shall now construct a directed system of E-sets indexed by the (upward) directed partially ordered set S^{op}.

Given s ∈ S, let us say that an object E ∈ Ob(E) “belongs to” s if the equivalence class of E in J is a member of s. For each s ∈ S, we define an E-set X_{s} by letting X_{s}(E) be the two-element set {−1, +1} if E belongs to s, and the one-element set {0} otherwise. Given a morphism a ∈ E(E, F), we let X_{s}(a) be the identity on {−1, +1} if E and F both belong to s; as s is a downset, the remaining possibilities all have F not belonging to s, in which case we let X_{s}(a) be the unique map X_{s}(E) → X_{s}(F) = {0}.

If s ⊇ t are members of S, then we define the map α_{s,t}: X_{s} → X_{t} to act as the identity at objects E ∈ Ob(E) belonging either to both s and t or to neither, and as the unique map {−1, +1} → {0} on elements belonging to s but not to t; these maps clearly make (X_{s}, α_{s,t})_{s,t∈S} a directed system indexed by S^{op}. Now because S has empty intersection, we see that at each E ∈ Ob(E), the sets X_{s}(E) become singletons for sufficiently large s ∈ S^{op}, so \underrightarrow{lim}_{S^{op}} X_{s} is an E-set all of whose components are singletons; hence the set \underleftarrow{lim}_{E} (\underrightarrow{lim}_{S^{op}} X_{s}) is a singleton.

On the other hand, for each s ∈ S we can construct (at least) two distinct elements of \underleftarrow{lim}_{E} X_{s}; an element x^{+} which takes value +1 at every E belonging to s (and, necessarily, value 0 at all other E), and an element x^{−} which takes value −1 at all E belonging to s. The maps \underleftarrow{lim}_{E} α_{s,t}: \underleftarrow{lim}_{E} X_{s} → \underleftarrow{lim}_{E} X_{t} (s ⊇ t) take x^{+} to x^{+} and x^{−} to x^{−}; thus we get distinct elements x^{+} and x^{−} in \underrightarrow{lim}_{S^{op}} (\underleftarrow{lim}_{E} X_{s}). Hence the map (20) cannot be one-to-one.

The final assertion of the proposition is proved by a construction exactly like the preceding, with ∅ used in place of {−1, +1}. In that case we get \underrightarrow{lim}_{S^{op}} (\underleftarrow{lim}_{E} X_{s}) empty, and \underleftarrow{lim}_{E} (\underrightarrow{lim}_{S^{op}} X_{s}) again a singleton, so that (20) is not surjective. □

To formulate a criterion for (20) to be bijective for all directed systems of Esets, let us define a congruence C on an E-set X to be a family (C_{E})_{E∈Ob(E)}, where each C_{E} is an equivalence relation on X(E), and which is functorial, in the sense that

(26) (s, t) ∈ C_{E}, a ∈ E(E, F) ⟹ (X(a)(s), X(a)(t)) ∈ C_{F} .

If, more generally, we define a “binary relation” R on an E-set X to mean a family R = (R_{E})_{E∈Ob(E)}, where each R_{E} is a binary relation on X(E), and no functoriality is assumed, then for every such relation R we can define the congruence generated by R to be the least congruence C such that for each E ∈ Ob(E), R_{E} ⊆ C_{E}. It is not hard to verify a more explicit description for this congruence C: for each E ∈ Ob(E), C_{E} is the equivalence relation on X(E) generated by the union, over all F ∈ Ob(E) and a ∈ E(F, E), of the image in X(E) × X(E) of R_{F} ⊆ X(F) × X(F) under X(a) × X(a). We will call a congruence on X finitely generated if it is generated by a binary relation R such that ∑_{E∈Ob(E)} card(R_{E}) < ∞. (Since we cannot assume the sets X(E) disjoint, it is not sufficient to say that card( ⋃ R_{E}) is finite.) The improper congruence on an E-set X will mean the congruence whose value at each E is the improper equivalence relation on X(E).

For any object E of E, the covariant hom-functor E(E, −) : E → Set may be regarded as an E-set, which we will denote H_{E}. Since we have assumed that distinct pairs of objects have disjoint hom-sets, these E-sets will be disjoint, and we can form the union of any set of them. We can now state and prove

Theorem 5 Let E be a small category satisfying (25), and A a finite set of objects of E as in that condition, i.e., such that every object of E admits at least one morphism from an object of A. Let H denote the E-set ⋃_{E∈A} H_{E}. Then the following conditions are equivalent:

(27) For every directed partially ordered set I and directed system (X_{i}, α_{i,j})_{i,j∈I} of E-sets, the set-map ι: \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}) → \underleftarrow{lim}_{E} (\underrightarrow{lim}_{i∈I} X_{i}) of (20) is bijective.

(28) The improper congruence on H is finitely generated.

PROOF. Since (25) is equivalent to injectivity of the maps (20), what we must prove is that under that assumption, surjectivity of all such maps is equivalent to (28).

First assume (28), and suppose we are given a directed system (X_{i})_{i∈I} of Esets, and an element x = (x_{E}) ∈ \underleftarrow{lim}_{E}(\underrightarrow{lim}_{i∈I} X_{i}). Each coordinate x_{E} of x can be written α_{j_{E},∞}(y_{E}), where j_{E} ∈ I is an index depending on E, and y_{E} ∈ X_{j_{E}}(E). We shall only use finitely many of these elements, namely those with E ∈ A. By the directedness of I we can find an index j that majorizes all the j_{E} with E ∈ A; we thus get a family of elements of X_{j}, namely y′_{E} = α_{j_{E},j}(y_{E}) ∈ X_{j}(E) (E ∈ A). These will generate a sub-E-set Y ⊆ X_{j}, whose F-component, for each F ∈ Ob(E), consists of all elements X_{j}(a)(y′_{E}) (E ∈ A, a ∈ E(E, F)).

Let us map the E-set H = ⋃_{E∈A} H_{E} onto Y by sending each a ∈ H_{E}(F) = E(E, F) (where E ∈ A, F ∈ Ob(E)) to X_{j}(a)(y′_{E}) ∈ X_{j}(F). (This can be thought of as an application of Yoneda’s Lemma to each of the sub-E-sets H_{E} (E ∈ A) of H.)

By choice of the y_{E}, the image in \underrightarrow{lim}_{i∈I} X_{i} of the sub-E-set Y ⊆ X_{j} has in each coordinate F only a single element, namely x_{F} . Thus by applying the morphism α_{j,k} for large enough k, we can make any given pair of elements in any coordinate fall together. But the fact that Y is an image of H and that the improper congruence on H is finitely generated means that some finite family of these collapses imply all of them. Thus, we can find some k ≥ j such that the image of Y in X_{k} has just one element in each coordinate. The Ob(E)-tuple of elements of X_{k} so determined will be an element z ∈ \underleftarrow{lim}_{E} X_{k} which maps to x in \underleftarrow{lim}_{E}(\underrightarrow{lim}_{i∈I} X_{i}). Taking the image of this element z in \underrightarrow{lim}_{i∈I} (\underleftarrow{lim}_{E} X_{i}) we get an element of the latter set that maps to x under ι, proving (27).

The proof of the converse will also follow that of the corresponding result for monoid actions, though this time the “hiccup” will involve adjoining card(A) additional pairs, rather than just one, to a certain finitely generated congruence. Assuming (27), let I be the directed partially ordered set of all finitely generated congruences on H, and for each C ∈ I, let X_{C} be the E-set H/C. Then we see that \underrightarrow{lim}_{C∈I} X_{C} is an E-set with just one element in each component, hence \underleftarrow{lim}_{E}(\underrightarrow{lim}_{C∈I} X_{C}) is a singleton. Hence by (27) the same is true of \underrightarrow{lim}_{C∈I} (\underleftarrow{lim}_{E} X_{C}), so least one of the sets \underleftarrow{lim}_{E} X_{C} (C ∈ I) is nonempty. Say x = (x_{E}) ∈ \underleftarrow{lim}_{E} X_{C} for some C ∈ I. For each E ∈ Ob(E) the element x_{E} will be the C-congruence class [a_{E}] of some element a_{E} ∈ E(F_{E}, E) ⊆ H(E), where F_{E} ∈ A. If for every F ∈ A we adjoin to C the additional pair (id_{F} , a_{F}), we get a congruence C′ on H which is still finitely generated, and which I claim is the improper congruence. Indeed, the compatibility conditions (18), which by assumption hold for the components x_{E} = [a_{E}] of x, now hold also for all translates [a] (a ∈ E(F, E)) of the images [id_{F}] of the generators id_{F} of H. This establishes (28). □

The following terminology provides a useful way of looking at this result.

Definition 6 Let E be a small category. By the trivial E-set we will mean the functor T that associates to every object of E a 1-element set (with the only possible behavior on morphisms). If E satisfies (25) and (for H constructed as in Theorem 5 from a set A as in (25)), also (28), we will say that the trivial E-set is finitely presented.

Note that for T the trivial E-set defined above, and X any E-set, the set \underleftarrow{lim}_{E} X can be identified with the hom-set Set^{E}(T, X). From this point of view, Theorem 5 is an instance of the general observation that for an algebraic structure S (in this case, T), the covariant hom-functor determined by S respects direct limits if and only if S is finitely presented.

(We have, for simplicity, not defined the general concept of a presentation of an E-set. Briefly, this may be done as follows. A representable functor H_{E} (E ∈ Ob(E)) can be considered an E-set X “free on one generator in X(E)”, namely id_{E}. A disjoint union of E-sets of this form (with repetitions allowed), modulo the congruence generated by a given set of ordered pairs, can be regarded as the E-set presented using the images of the elements id_{E} ∈ H_{E} as generators and the given ordered pairs as relations. Incidentally, the reader may have noted that Definition 6 has the formal defect that the condition on E as stated depends on the choice of A. But Theorem 5 shows that it is in fact independent of A; and, indeed, for E-sets as for other finitary algebraic objects, if an object is finitely generated, one can show that the property of finite relatedness is independent of one’s choice of finite generating set.)

Though Theorem 5 is elegant, it does not give convenient conditions analogous to (9)-(13) of Theorem 2. These, too, may be generalized to arbitrary small categories E, but the statements are simplest when E has only finitely many objects. I will develop the generalization of (13) to that case below, and at the end of the next section will state and sketch the proof of the corresponding result for general E.

Let us call a subcategory E_{0} of a category E right division-closed if for any two morphisms a, b of E whose composite ab is defined, we have

(29) ab, b ∈ E_{0} ⟹ a ∈ E_{0}.

Proposition 7 Let E be a category with only finitely many objects. Then the following conditions are equivalent:

(30) E satisfies the equivalent conditions of Theorem 5.

(31) There exists a finite set S of morphisms of E, such that the smallest subcategory E_{0} of E which has the same object-set as E, and contains S, and is right division-closed in E, is E itself.

PROOF. Assuming (30), take for A as in Theorem 5 the full object-set of E, so that H is the union of the E-sets H_{E} associated with all the objects of E, and let R be a finite generating set for the improper congruence on H. Let S be the set of all elements occurring as first or second components of members of R, and let E_{0} ⊆ E be constructed from S as in (31). Let U be the set of all pairs (as, at) with s ∈ E_{0}(E, F), t ∈ E_{0}(E′, F), a ∈ E(F, G), E, E′, F, G ∈ Ob(E). As in the last paragraph of the proof of Theorem 2, each element of U either has both components or neither component in E_{0}. Hence the equivalence relation C generated by U also has this property. Moreover, U, and hence C, is closed under left composition with morphisms of E, hence C is a congruence on H, and it contains all members of the generating set R, hence it is the improper congruence. Now for every morphism a ∈ E(E, F) of E, the improper congruence on H contains (id_{F} , a), and id_{F} ∈ E_{0}, hence by our “both or neither” property of C, a ∈ E_{0}. So E_{0} = E, proving (31).

Conversely, suppose S is a finite set of morphisms for which the conclusion of (31) holds, and consider the congruence C on H generated by all pairs (a, id_{F}) where a ∈ S ∩ E(E, F) (E, F ∈ Ob(E)).

For each E, F ∈ Ob(E), let E_{1}(E, F) denote {a ∈ E(E, F) | (a, id_{F}) ∈ C}. I claim this gives the morphism-set of a right division closed subcategory E_{1} ⊆ E with object-set Ob(E). It is immediate that it contains all identity morphisms; now suppose a: F → G and b: E → F are morphisms of E, with b ∈ E_{1}. The latter relation means (b, id_{F}) ∈ C, hence as C is a congruence, we also have (ab, a) ∈ C, hence (ab, id_{G}) ∈ C ⟺ (a, id_{G}) ∈ C, i.e., ab ∈ E_{1} ⟺ a ∈ E_{1}, proving both closure under composition and right division closure. Hence since S was chosen as in (31), E_{1} must be all of E. This says that C contains all pairs (a, id_{F}) with a ∈ E(E, F), E, F ∈ Ob(E), so by transitivity, C is the improper congruence on H, which is thus finitely generated, proving (30). □

6 Digression: four corollaries.

A case of Proposition 7 which has been noted before is

Corollary 8 ( = [1, Prop. 7.9.3], cf. [15, Thm. IX.2.1, p.211], [12, Thm. 4.73, p.72]) If E is a category with only finitely many objects, and whose morphism-set is finitely generated under composition, then on directed systems (X_{i})_{i∈I} of E-sets, the operations \underleftarrow{lim}_{E} and \underrightarrow{lim}_{I} commute; i.e., (27) holds. □

This note is in fact the result of pondering how to improve on the above result from [1]. (Incidentally, in the statement in [1], I assumed the category E nonempty, but allowed direct limits over possibly empty directed partially ordered sets. In this note I have made the opposite choices, requiring in the definition that direct limits have nonempty index sets, but not so restricting E. As observed in [1, Exercise 7.9:2], the result holds if either the category or the directed partially ordered set is required to be nonempty, but fails when they are both empty.)

Let us record next a pair of results implicit in the proofs of Theorem 2 and Proposition 7, along with their duals. (The proofs, and that of the final result of this section, will just be sketched; they will not be used in the remainder of this note.) We will use for monoids as well as for categories the term “right division-closed” introduced above, and define “left division-closed” for both sorts of structures dually. (The terms used by semigroup theorists, e.g. in [4,18], are “left, respectively, right unital”, though in [7], where the conditions were first introduced, they were “left, respectively, right simplifiable”.) For a an element of a monoid M and Y_{0} a subset of an M-set Y, we shall in Corollary 9(iii*) write a^{−1}Y_{0} for the inverse image of Y_{0} ⊆ Y under the map Y → Y given by the action of a; and we shall similarly use inverse image notation in Corollary 10(iii*) in connection with the set-maps Y (a) forming the structure of an E-set Y. Note that in Corollary 9(iii*), “M-set” still means left M-set, despite the dualization being carried out.

The first half of the next result is due to Schein [18, Theorem 2].

Corollary 9 (to proof of Theorem 2; cf. [18]) Let M be a monoid, and N a subset of M. Then the following conditions are equivalent:

(i) N is a right division-closed submonoid of M.

(ii) N is the equivalence class of 1 under some left congruence on M.

(iii) There exist an M-set X, and an element x ∈ X, such that N = {a ∈ M | ax = x}.

Likewise, the following conditions are equivalent:

(i*) N is a left division-closed submonoid of M.

(ii*) N is the equivalence class of 1 under some right congruence on M.

(iii*) There exist an M-set Y, and a subset Y_{0} of Y, such that N = {a ∈ M | a^{−1}Y_{0} = Y_{0}}. (I.e., N is the set of elements a ∈ M which carry both Y_{0} and its complement into themselves.)

Sketch of proof. Assuming (i), let C be the equivalence relation on M generated by {(as, at) | a ∈ M, s, t ∈ N}, and observe as in the proof of Theorem 2, (17) ⟹ (13), that C is a left congruence and relates elements of N only with elements in N, establishing (ii). The implications (ii) ⟹ (iii) ⟹ (i) are straightforward.

The second half of the result will follow from the first by left-right dualization if we can establish that (iii*) is equivalent to the existence of a right M-set X with an element x such that N = {a ∈ M | xa = x}. Now given a left M-set Y and a subset Y_{0} such that N = {a ∈ M | a^{−1}Y_{0} = Y_{0}}, the contravariant power functor yields a right M-set X = P(Y), in which the element x = Y_{0} indeed satisfies N = {a ∈ M | xa = x}. Conversely, given a right M-set X with an element x satisfying this relation, it is easy to verify that in the left M-set Y = P(X), the subset Y_{0} = {S ⊆ X | x ∈ S} satisfies N = {a ∈ M | a^{−1}Y_{0} = Y_{0}}. □

We can now see the significance of condition (13) in Theorem 2. Although, as noted at the beginning of §4, a general left congruence on a monoid is not determined by the set of elements congruent to 1, the improper left congruence is clearly determined by that set. Condition (13) translates finite generation of the improper left congruence into finite generation of M as a set that can occur as the equivalence class of 1 under a left congruence.

The analogous result for small categories is

Corollary 10 (to proof of Proposition 7) Let E be a small category, and for every pair of objects E, F ∈ Ob(E) let E_{0}(E, F) be a subset of E(E, F). Then the following conditions are equivalent:

(i) The sets E_{0}(E, F) are the morphism-sets of a right division-closed subcategory E_{0} ⊆ E with the same object-set as E.

(ii) There exists a congruence C on the E-set ⋃_{E∈Ob(E)} H_{E}, such that for all E, F ∈ Ob(E), E_{0}(E, F) = {a ∈ E(E, F) | (a, 1_{F}) ∈ C}.

(iii) There exist an E-set X, and for each E ∈ Ob(E) an element x_{E} ∈ X(E), such that for all E, F ∈ Ob(E), E_{0}(E, F) = {a ∈ E(E, F) | ax_{E} = x_{F} }.

Likewise, the following conditions are equivalent (where for E ∈ Ob(E), H^{E} denotes the contravariant hom functor E(−, E)) :

(i*) The sets E_{0}(E, F) are the morphism-sets of a left division-closed subcategory E_{0} ⊆ E with the same object-set as E.

(ii*) There exists a congruence C on the right E-set (contravariant Setvalued functor) ⋃_{E∈Ob(E)} H^{E} such that for all E, F ∈ Ob(E), E_{0}(E, F) = {a ∈ E(E, F) | (a, 1_{E}) ∈ C}.

(iii*) There exist a (left) E -set Y, and for each E ∈ Ob(E) a subset Y_{0}(E) ⊆ Y (E), such that for all E, F ∈ Ob(E), E_{0}(E, F) = {a ∈ E(E, F) | Y (a)^{−1}Y_{0}(F) = Y_{0}(E)}.

Sketch of proof. Analogous to the proof of Corollary 9. So, for instance, to get (i) ⟹ (ii), we use E_{0} as in the proof of Proposition 7 to construct on H a binary relation U, and from that, the congruence C. □

Since this relation between right division-closed subcategories and congruences on H holds for arbitrary E, why does Theorem 5 need the hypothesis that E have only finitely many objects? Because when it has infinitely many objects, the E-set ⋃_{E∈Ob(E)} H_{E} is not finitely generated, so the statement that its quotient by the improper congruence is finitely presented does not mean that the latter congruence is finitely generated. However, with this viewpoint in mind, one can come up with a generalization of that theorem to arbitrary E.

Corollary 11 (to Theorem 5 and proof of Proposition 7) Let E be a small category satisfying (25), and A a finite set of objects of E as in that condition. Let S_{0} be a set of morphisms of E which, for each F ∈ Ob(E) − A, contains exactly one morphism from a member of A to F, and which contains no elements other than these. Then E satisfies the equivalent conditions of Theorem 5 if and only if it satisfies

(32) There exists a finite set S_{1} of morphisms of E such that the smallest subcategory E_{0} of E which has the same object-set as E, and contains S_{0} ∪S_{1}, and is right division-closed in E, is E itself.

Sketch of proof. (32) is equivalent to the statement that the pairs (a, id_{F}), where a ∈ S_{0} ∪ S_{1} and F is the codomain of a, generate the improper congruence on ⋃_{E∈Ob(E)} H_{E}. Now those pairs with a taken from S_{0} simply serve to “eliminate” the generators id_{F} of ⋃_{E∈Ob(E)} H_{E} with F ∈ Ob(E)−A; i.e., dividing out by the congruence generated by those pairs alone gives the E-set H of Theorem 5. Thus, (32) is equivalent to the statement that the improper congruence on that E-set is generated by a finite set of pairs, which is the desired condition (28).

To set up a formal proof, for each F ∈ Ob(E) − A, let a_{F} ∈ E(E_{F} , F) (where E_{F} ∈ A) be the corresponding element of S_{0}, while for F ∈ A let us set E_{F} = F, a_{F} = id_{F} . Then given S_{1} as in (32), one shows that the improper congruence on H is generated by the finite set of pairs (ba_{F} , a_{F′}) for b : F → F′ in S_{1}, while conversely, given a finite generating set R for that improper congruence, one can take S_{1} to be the set of components of members of R. □

An easy class of examples are categories E having an initial object E_{init}. Then if one takes A = {E_{init}}, there is a unique set S_{0} as in the statement of the above theorem, and letting S_{1} be the empty set, one finds that (32) holds.

7 Posets.

Groups and monoids, with which we began this note, are categories where “all the structure is in the morphisms”, and essentially none in the class of objects and the way morphisms connect them. In this section we will consider the opposite extreme, the case of partially ordered sets J regarded as categories.

If J is a poset, we shall write E = J_{cat} for the category having for objects the elements of J, and having, for each E, F ∈ J, one morphism λ(E, F) : E → F if E ≤ F, and no morphisms E → F otherwise. (We write E, F, … for elements of J for consistency with the notation of the last two sections.)

From Proposition 4 we know that a necessary condition for Set-valued limits over such a category E to respect direct limits is that the set A of minimal elements of J be finite, and every element of J lie above an element of A. Note that the E-set H constructed as in Theorem 5 from this set A associates to each E ∈ J the set {λ(F, E) | F ∈A, F ≤ E}. By that theorem, to strengthen our necessary condition to a necessary and sufficient one, we need to know for which J the improper congruence on this E-set H is finitely generated.

For an instructive example of an infinite poset for which this congruence is finitely generated, let the underlying set of J consist of all real numbers ≥ 1, ordered in the usual way, together with two elements 0_{1} and 0_{2} which are less than all other elements, and mutually incomparable. Thus, A = {0_{1}, 0_{2}}, and for all E other than these two elements, we have H(E) = {λ(0_{1}, E), λ(0_{2}, E)}. It is easy to see that the improper congruence on H is generated by the single pair (λ(0_{1}, 1), λ(0_{2}, 1)). On the other hand, if we delete the element 1 and consider the corresponding functor on (J − {1})_{cat}, it is not hard to see that the improper congruence on this functor is no longer finitely generated.

The element 1 ∈ J is what we shall call a “critical element” with respect to the subset {0_{1}, 0_{2}}. In the example above, it served to “gather” the strands of H emanating from 0_{1} and 0_{2}. Let us give precise meanings to these terms.

Definition 12 Let J be a partially ordered set. For E ∈ J we shall write down(E) for {F ∈ J | F ≤ E} (the “principal downset” generated by E).

Given E ∈ J and subsets A, B ⊆ J, we shall write R(A, B, E) for the equivalence relation on A ∩ down(E) generated by the union over all F ∈ B∩ down(E) of the improper equivalence relations on the sets A ∩ down(F). We shall say that B gathers A under E if R(A, B, E) is the improper equivalence relation on A ∩ down(E).

Given a subset A ⊆ J and an element E ∈ J, we note that {E} always gathers A under E. We shall call E A-critical if J − {E} does not gather A under E.

It is straightforward to verify the transitivity relation

(33) If A, B_{1}, B_{2} are subsets of J and E an element of J, such that B_{1} gathers A under every element of B_{2} and B_{2} gathers A under E, then B_{1} gathers A under E.

Also, the next-to-last sentence of Definition 12 implies the reflexivity condition:

(34) If A, B are subsets of J, then B gathers A under every E ∈ B.

Note that in the next lemma, we do not assume that every element of J majorizes some member of A (though we will add that assumption when we apply the lemma).

Lemma 13 Let J be a partially ordered set and A ⊆ J a finite subset. Let us write E for J_{cat}, and H for the union, over all E ∈ A, of the covariant hom-functors H_{E}. Then the following conditions are equivalent:

(35) There exists a finite subset B ⊆ J which gathers A under every E ∈ J.

(36) The set of A-critical elements of J is finite, and gathers A under every E ∈ J.

(37) The improper congruence on the E-set H is finitely generated.

PROOF. (36) ⟹ (35) is immediate. To get the converse, take B as in (35) and let B′ denote the set of A-critical elements of J. Applying (35) to an element E ∈ B′, we see, from the definition of the statement that E is Acritical, that E ∈ B. Hence B′ ⊆ B, so in particular B′ is finite; it remains to show that for any E ∈ J, B′ gathers A under E. In doing so we may assume inductively that B′ gathers A under every F ∈ J such that the number of elements of B that are < F is smaller than the number that are < E, or such that these numbers are equal but the number ≤ F is smaller than the number ≤ E.

If E ∉ B, the former assumption shows that B′ gathers A under each element of B ∩ down(E), hence (33), with B′ and B ∩ down(E) in the roles of B_{1} and B_{2}, shows that B′ gathers A under E, as desired. On the other hand, if E ∈ B, the inductive assumptions show that B′ gathers A under every element of J that is < E. Now if E is not A-critical, we can apply (33) with B′ and down(E) − {E} in the roles of B_{1} and B_{2} respectively, and again conclude that B′ gathers A under E. On the other hand, if E is A-critical, then it belongs to B′, and (34) (with B′ in the role of B) yields the same conclusion.

(35) ⟺ (37): Note that for any E ∈ J, the definition of H(E) shows that this set is in bijective correspondence with down(E) ∩ A, via λ(A, E) ↦ A, and that for any set B, the equivalence relation R(A, B, E) on down(E) ∩ A corresponds to the restriction to H(E) of the congruence generated by the improper equivalence relations on the sets H(F) (F ∈ B ∩ down(E)). It follows that given B as in (35), the improper congruence on H is generated by the finite set of pairs {(λ(F, E), λ(F′, E)) | E ∈ B; F, F′ ∈ A ∩ down(E)}. Conversely, assuming (37), we may take a finite generating set S for the improper congruence on H and let B = {E | (∃ F, F′ ∈ A) (λ(F, E), λ(F′, E)) ∈ S}, and we see that this B witnesses (35). □

The above lemma, combined with Theorem 5, yields necessary and sufficient conditions for a category of the form J_{cat} to have the property we are interested in (last paragraph of theorem below). We can also get from it some necessary conditions for this to be true of an arbitrary small category (first paragraph).

Theorem 14 Let E be a small category, and J the partially ordered set whose elements are the equivalence classes of objects of E under the equivalence relation that relates E and F if there exist morphisms from E to F and from F to E (cf. proof of Proposition 4). Let A denote the set of minimal elements of J, and B the set of A-critical elements. Then necessary conditions for limits over E to respect direct limits of E-sets are (i) A is finite, (ii) every element of J lies above an element of A, (iii) B is finite, and (iv) B gathers A under every element of J.

If E is in fact a category formed from a partially ordered set by the construction ( )_{cat} (equivalently, if E ≅ J_{cat}), then the conjunction of these four conditions is sufficient as well as necessary.

PROOF. The final assertion is immediate from Proposition 4, Theorem 5, and Lemma 13.

To get the assertion of the first paragraph, suppose that limits over E respect direct limits of E-sets. Conditions (i) and (ii) follow from Proposition 4. Let us write the set of minimal elements of J more distinctively as A^{(J)}, let A^{(E)} ⊆ Ob(E) be a set of representatives of these elements, and let H^{(J_{cat})} and H^{(E)} denote the J_{cat}-set and the E-set determined by these respective sets of objects. Then by Theorem 5 our assumption implies that the trivial congruence on H^{(E)} is finitely generated, while by Lemma 13, the conclusions (iii) and (iv) that we want to prove are equivalent to saying that the same is true of the trivial congruence on H^{(J_{cat})}.

Now there is an obvious functor R: E → J_{cat} taking each object of E to its equivalence class in J. It is easy to see that the composite functor H^{(J_{cat})}∘R: E → J_{cat} → Set admits a surjective homomorphism H^{(E)} → H^{(J_{cat})}∘R; hence as the improper congruence on H^{(E)} is finitely generated, the same is true of the improper congruence on H^{(J_{cat})}∘R, and hence, as R is surjective on objects, of the improper congruence on H^{(J_{cat})}, as required. □

8 Remarks

As noted in the introduction, given a directed system of algebras (A_{i})_{I}, understood to be finitary, one can construct its direct limit by taking the direct limit of underlying sets and putting an appropriate algebra structure on this set, essentially because direct limits respect finite products of sets, and an algebra structure is given by maps on such product sets. On the other hand, direct limits do not in general respect infinite products; indeed, such a product can be thought of as a limit over J_{cat} where J is an infinite antichain, and such a J does not satisfy condition (i) of Theorem 14. So direct limits of infinitary algebras cannot be constructed as in the finitary case. An example is

Example 15 A directed system of algebras with one ℵ_{0}-ary operation, such that the algebra structure cannot be extended to the direct limit set in any natural way.

Details. For each positive real number a let A_{a} be the closed interval [0, a] ⊆ ℝ, given with the ℵ_{0}-ary supremum operation (x_{0}, x_{1}, …) ↦ sup(x_{0}, x_{1}, …). These sets form a directed system under inclusion, but the operation sup clearly does not extend in a natural way to their direct limit, [0, ∞). For instance, one has no natural definition of sup(0, 1, 2, …), because the map ι : \underrightarrow{lim}_{a∈ℝ}(A_{a}^{ℕ}) → (\underrightarrow{lim}_{a∈ℝ}A_{a})^{ℕ} does not have (0, 1, 2, …) in its image. It is not hard to show that no extension of sup to [0, ∞) makes this set the direct limit of the algebras A_{a}. (The uncountability of ℝ is not necessary to this example; one may replace ℝ with ℕ. I just felt that the supremum function on real numbers was the more “important” example.)

We also noted in the introduction that the results of this paper are specific to Set-valued functors, and fail for functors with other codomains, e.g., Set^{op}. For another example, let Metr be the category of metric spaces, with distance-nonincreasing maps as morphisms. Then one has

Example 16 A directed system of Z_{2}-sets X_{0} → X_{1} → ⋯, in Metr such that the map ι : \underrightarrow{lim}_{i}(X_{i})^{Z_{2}} → (\underrightarrow{lim}_{i}X_{i})^{Z_{2}} is not surjective.

Details. For each i, let X_{i} be the set {0, 1}, with d(0, 1) = 1/(i + 1), and with Z_{2} acting by switching 0 and 1, and let all connecting morphisms be the identity on underlying sets. Each of the sets X_{i}^{Z_{2}} is empty, so \underrightarrow{lim}_{I} X_{i}^{Z_{2}} = ∅. However, from the metric space axiom d(x, y) = 0 ⟹ x = y one sees that the direct limit of this directed system is the 1-point metric space, on which Z_{2} acts trivially; thus, (\underrightarrow{lim}_{I} X_{i})^{Z_{2}} is nonempty.

A type of question related to that considered in this note arises in sheaf theory. A sheaf of sets on a topological space V is a certain sort of functor (o(V)^{op})_{cat} → Set, where o(V) is the set of open subsets of V, partially ordered by inclusion; and an analog of the question we have considered is, “When does the global-sections functor commute with direct limits of sheaves?” But that problem is not actually a case of the problem considered above, because of the nontrivial form that the direct limit construction takes for sheaves. A class of situations where that commutativity holds is obtained in [10, Exercise II.1.11], and in greater generality in [9, Proposition 3.6.3].

References

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

[2] George M. Bergman, Generating infinite symmetric groups, to appear, J. London Math. Soc.. Preprint version, 9 pp.: http://math.berkeley.edu/ ∼ gbergman/papers/Sym Omega:1.{tex,dvi,ps}, arXiv:math.GR/0401304 .

[3] Stephen Bigelow, Supplements of bounded permutation groups, J. Symbolic Logic 63 (1998) 89–102. MR 99b:20007.

[4] A. H. Clifford and G. B. Preston, The algebraic theory of semigroups, v. II., Mathematical Surveys No. 7, American Mathematical Society, 1967, xv + 350 pp.. MR 36#1158.

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

[6] Manfred Droste and W. Charles Holland, Generating automorphism groups of chains, Forum Mathematicum 17 (2005) 699–710.

[7] Paul Dubreil, Contribution à la théorie des demi-groupes, Mém. Acad. Sci. Inst. France (2) 63 (1941) 52 pp.. MR 8,15a.

[8] Robert El Bashir, Tomáš Kepka and Petr Němec, Modules commuting (via Hom) with some colimits, Czechoslovak Math. J. 53 (128) (2003) 891–905. MR 2004i:16002.

[9] Alexander Grothendieck, Sur quelques points d’algèbre homologique, Tôhoku Math. J. 9 (1957) 119–221. MR 21#1328.

[10] Robin Hartshorne, Algebraic geometry, Springer Graduate Texts in Mathematics, No. 52, 1977. MR 57#3116.

[11] E. Hotzel, On semigroups with maximal conditions, Semigroup Forum 11 (1975/76) 337–362. MR 52#10921.

[12] Gregory Maxwell Kelly, Basic Concepts of Enriched Category Theory, London Mathematical Society Lecture Note Series, v.64, 1982. MR 84e:18001. Readable at http://www.tac.mta.ca/tac/reprints/articles/10/tr10abs.html .

[13] Sabine Koppelberg and Jacques Tits, Une propriété des produits directs infinis de groupes finis isomorphes, C. R. Acad. Sci. Paris Sér. A 279 (1974) 583–585. MR 51#13058.

[14] I. B. Kozhukhov, Semigroups with certain conditions on congruences, J. Math. Sci. (N.Y.) 114 (2003) 1119–1126. MR 2004b:20087.

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

[16] H. D. Macpherson and Peter M. Neumann, Subgroups of infinite symmetric groups, J. London Math. Soc. (2) 42 (1990) 64–84. MR 92d:20006. (Note: As pointed out in [3], Theorem 1.2 of this paper requires additional set-theoretic hypotheses for some κ.)

[17] Open problems discussed at a conference in honor of Walter Taylor at the University of Colorado, 15-18 August, 2004, 7 pp., http://math.berkeley.edu/ ∼ gbergman/papers/WTq.{tex,dvi,ps,pdf}.

[18] B. M. Schein, Stationary subsets, stabilizers and transitive representations of semigroups, Dissertationes Math. Rozprawy Mat. 77 1970, 38 pp.. MR 44#4129.

[19] Saharon Shelah, On a problem of Kurosh, Jónsson groups, and applications, pp. 373–394 in Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math. 95, North-Holland, 1980. MR 81j:20047.

[20] Simon Thomas, The cofinalities of the infinite-dimensional classical groups, J. Algebra 179 (1996) 704–719. MR 96k:20005.