Theory and Applications of Categories, Vol. 22, No. 20, 2009, pp. 509–541.

ALGEBRAIC CATEGORIES WHOSE PROJECTIVES ARE EXPLICITLY FREE

MATÍAS MENNI

Abstract. Let M = (M, m, u) be a monad and let (MX, m) be the free M-algebra on the object X. Consider an M-algebra (A, a), a retraction r : (MX, m) → (A, a) and a section t : (A, a) → (MX, m) of r. The retract (A, a) is not free in general. We observe that for many monads with a ‘combinatorial flavor’ such a retract is not only a free algebra (MA_{0}, m), but it is also the case that the object A_{0} of generators is determined in a canonical way by the section t. We give a precise form of this property, prove a characterization, and discuss examples from combinatorics, universal algebra, convexity and topos theory.

1. Introduction

Let {a_{i} ∈ ℕ}_{i≥0} be a sequence obtained by counting the number of elements/figures of a given object A. Why is it the case that, for some {b_{i}}_{i≥0}, we have:

1. ∑_{n≥0} a_{n} \frac{x^{n}}{n!} = e^{G} where G = ∑_{n≥0} b_{n} \frac{x^{n}}{n!} , or

2. a_{n} = ∑_{i∈ℕ} b_{i} \binom{n}{i} or

3. a_{n} = ∑_{i∈ℕ} b_{i} S(n, i) where S(n, i) is the Stirling number of the second kind?

The reason is that A can be given the structure of a free algebra for a monad related to the type of series involved. (There is a monad associated to e^{( )}, one associated to the assignment \{b_{i}\}_{i≥0} ↦ ∑_{i≥0} b_{i} \binom{x}{i} and one to the assignment \{b_{i}\}_{i≥0} ↦ ∑_{i≥0} b_{i} S(x, i).) The investigation of this observation lead us to the study of Kleisli categories which turned out to have more limits than is usual for a category of free algebras. In particular, idempotents split in all examples. In other words, projectives are free. The relation between projective and free objects is well-explained in Proposition III.3.2 of [4]. Let G : C → D have a left adjoint F and denote by C_{G} the class of maps f in C such that Gf is split epi. An object of C is C_{G}-projective if and only if it is a retract of an object in the image of F.

Under mild completeness hypotheses on the base category D, every retract t : A → F X of a free algebra determines a subobject U → A in D. We study monads for which A is free on U. That is, projectives are free and moreover, there is an explicit way to calculate the object of generators.

Research funded by Conicet, ANPCyT and Lifia.

Received by the editors 2009-02-23 and, in revised form, 2009-11-09.

Transmitted by F. W. Lawvere. Published on 2009-11-17.

2000 Mathematics Subject Classification: 18C20, 05A19, 08B30.

Key words and phrases: monads, combinatorics, projective objects, free objects.

\begin{matrix}c \\ ◯ \end{matrix} Matías Menni, 2009. Permission to copy for private use granted.

In Section 2 we formulate the precise form of the property suggested in the previous paragraph and call it the Explicit Basis property. For brevity, monads that satisfy this property are called EB. For example, the category of compact convex sets is algebraic over the category of compact Hausdorff spaces and, in Section 3, we show that the associated monad is EB. A characterization of EB monads is proved in Section 4, and applied in Sections 5 to 11 in order to discuss more examples. The relation with combinatorics is informally discussed in Section 12. In Section 13, we explain why most of the monads we use have a conservative underlying functor. It is also curious that our examples satisfy that canonical presentations of algebras have at most one section. Section 14 explains why this is the case, when the base category is Heyting.

The following terminology will be used throughout the paper. Let M be a monad, (A, a) an M-algebra and f : U → A a morphism in the base category. The composition a(Mf) : MU → A underlies a morphism (MU, m) → (A, a) of algebras. The map f is called independent (w.r.t. the algebra (A, a)) if the induced map a(Mf) : MU → A is mono. Similarly, f is called spanning if a(Mf) : MU → A is regular epi. Finally, f is called a basis for the M-algebra (A, a) if it is both independent and spanning. We will usually apply these definitions to a subobject U → A.

2. The Explicit Basis property

Let M = (M, u, m) be a monad on a category D. Every algebra (A, a) has a canonical presentation given by a : (MA, m) → (A, a). Each section s : (A, a) → (MA, m) of the canonical presentation induces a Unity and Identity of Opposites

\xymatrix{A \ar[r]^{u} \ar[r]_{s} & MA \ar[l]|{a}}

in the base category D, with a : MA → A as a common retraction of the subobjects u and s. As observed in [8], “The existence of a common retraction implies a striking property not shared by most pairs of subobject inclusions with a common codomain: the intersection of the subobjects is given by the equalizer of the inclusions!”

In the particular coreflexive pairs we are considering, oppositeness is manifested by the fact that one of the inclusions is an algebra morphism and the other is very much not so. It will be useful to introduce the following terminology.

2.1. Definition. For a Unity and Identity of Opposites as above, the canonical restriction of the section s : (A, a) → (MA, m) is the map \overline{s} : A_{s} → A in D such that the square on the left below

\xymatrix{A_{s} \ar[d]_{\overline{s}} \ar[r]^{\overline{s}} & A \ar[d]^{u} & A_{s} \ar[r]^{\overline{s}} & A \ar[r]^{u} \ar[r]_{s} & MA \\ A \ar[r]_{s} & MA}

is a pullback and, equivalently, the fork on the right is an equalizer.

(Canonical restrictions need not exist. But we will always, tacitly or explicitly, assume that they do. Clearly, if the base D has finite limits, as in most of our examples, canonical restrictions exist.)

A key fact in the proof of the main result in [13] is that every retract of a free object in Alg_{M} induces a Unity and Identity of Opposites of the restricted kind discussed above. More explicitly, let r : (MX, m) → (A, a) be a map in Alg_{M} with a section t : (A, a) → (MX, m). Applying the free algebra functor to the composition ru_{X} : X → A, and pre-composing the result with t, we obtain an algebra map

\xymatrix{(A, a) \ar[r]^{t} & (MX, m) \ar[r]^{Mu} & (MMX, m_{M}) \ar[r]^{Mr} & (MA, m)}

that we denote by [t; r] : (A, a) → (MA, m).

2.2. Lemma. The map [t; r] : (A, a) → (MA, m) is a section of the canonical presentation a : (MA, m) → (A, a).

Proof. The commutative diagram below, with [t; r] appearing in the top row,

\xymatrix{A \ar[r]^{t} & MX \ar[dr]_{id} \ar[r]^{Mu} & MMX \ar[d]_{m} \ar[r]^{Mr} & MA \ar[d]^{a} \\  &  & MX \ar[r]_{r} & A}

shows that a[t; r] = rt = id.

2.3. Lemma. The following are equivalent:

1. for every morphism r : (MX, m) → (A, a) with a section t : (A, a) → (MX, m), the canonical restriction \overline{[t; r]} : A_{[t;r]} → A is a basis for (A, a).

2. for every algebra (A, a) and section s : (A, a) → (MA, m) of a : (MA, m) → (A, a), the canonical restriction \overline{s} : A_{s} → A is a basis for (A, a).

Proof. The second item trivially implies the first. To prove the converse, notice that for any s and a as in the second item,

[s; a] = (Ma)(Mu)s = (M(au))s = s

so the first item implies the second.

We state the main definition in its full generality and consider, in this section, a couple of examples and results that do not necessarily have a base with finite limits.

2.4. Definition. The monad M satisfies the Explicit Basis property if canonical restrictions exist and the equivalent conditions of Lemma 2.3 hold.

A section s : (A, a) → (MA, m) of the canonical presentation of (A, a) induces a ‘putative basis’ for the algebra (A, a). The Explicit Basis property requires these ‘putative bases’ to be actual bases. For brevity, a monad satisfying the Explicit Basis property will be called an EB monad.

The first item of Lemma 2.3 makes it clear that the Explicit Basis property is a condition about projectives in the category of algebras. The second item is the formulation we will use in practice.

2.5. Proposition. Assume that idempotents split in D. If M is EB then idempotents split in the Kleisli category Kl_{M}.

Proof. Let e : (MX, m) → (MX, m) be an idempotent in Kl_{M}. As idempotents split in the base, we can consider the splitting of e in Alg_{M}. Let e = tr be a splitting of e with r : (MX, m) → (A, a) and t : (A, a) → (MX, m) a section of r. By hypothesis, the canonical restriction \overline{[t; r]} : A_{[t;r]} → A is a basis for (A, a). So the composition

\xymatrix{M(A_{[t;r]}) \ar[r]^{M\overline{[t;r]}} & MA \ar[r]^{a} & A}

is an iso. That is, the splitting of e lies in the Kleisli category.

We now consider some examples and non-examples. The identity monad on any category is EB. This trivial observation is also a particular case of the following.

2.6. Lemma. Every idempotent monad satisfies the Explicit Basis property.

Proof. If s : (A, a) → (MA, m) is a section for the canonical presentation of (A, a) then sa = m(Ms). As m is an iso and Ms is mono, a is mono. Since it is also split epi, a is an iso. So it has a unique section and this implies that s = u. The canonical restriction \overline{s} : A_{s} → A determined by s is id : A → A. It is a basis for (A, a) because a is an iso.

A simple example of a different type is the algebraic category of pointed sets. The canonical functor 1/Set → Set is algebraic and the resulting monad on Set satisfies the Explicit Basis property. It is easy to check this fact directly, but it is also worth looking at it from a more general perspective.

Assume that D has finite coproducts and let D be an object in D. The canonical functor D/D → D is algebraic and the resulting monad M = (M, u, m) has underlying functor M = D + ( ) : D → D, unit u_{X} = in_{1} : X → D + X given by right injection, and multiplication given by the codiagonal m_{X} = ∇ + X : D + D + X → D + X. If D is extensive, pullbacks along injections exist and so, canonical restrictions exist.

2.7. Proposition. If D is extensive then the monad induced by D/D → D is EB.

Proof. We identify an algebra with a pair (A, a) where A is an object of D and a : D → A. The canonical presentation of such an algebra is given by the map [a, id] : D + A → A as in the commutative diagram below

\xymatrix{ & D \ar[dl]_{in_{0}} \ar[dr]^{a} \\ D + A \ar[rr]_{[a,id]} &  & A}

where in_{0} : D → D + A is the free algebra on A. Consider a section of the canonical presentation. That is, a map s : A → D + A such that sa = in_{0} and [a, id]s = id : A → A. The square on the right below

\xymatrix{D \ar[d]_{id} \ar[r]^{a} & A \ar[d]_{s} & A_{s} \ar[l]_{\overline{s}} \ar[d]^{\overline{s}} \\ D \ar[r]_{in_{0}} & D + A & A \ar[l]^{in_{1}}}

is a pullback by definition of canonical restriction. On the other hand, the left square above commutes because s is a morphism of algebras. Moreover, the square is a pullback because s is mono. As D is extensive, the cospan

\xymatrix{D \ar[r]^{a} & A & A_{s} \ar[l]_{\overline{s}}}

is a coproduct diagram. It follows that [a, \overline{s}] : D + A_{s} → A is an iso. This means that \overline{s} : A_{s} → A is a basis for (A, a).

Let us look at some non-examples. By Proposition 2.5, any monadic category over Set with some non-free regular projective provides a non-example.

2.8. Example. Consider the category cHaus of compact Hausdorff spaces. The functor cHaus → Set is monadic . Its left adjoint is given by the Stone-Cech compactification (restricted to discrete spaces). The characterization of projective objects in cHaus as extremally disconnected spaces [4], implies that there are projectives which are not free.

Another source of non-examples is the following.

2.9. Proposition. [G. Janelidze] Let R be a ring. The monad on Set determined by the algebraic category of R-modules is EB if and only if R is trivial.

Proof. If R is trivial then so is the monad and the trivial monad is EB. Conversely, assume that the monad is EB, consider R with its canonical module structure and take the free module, denoted by MR, on R. Then consider the linear map s : R → MR defined by sx = x(\overline{0} + \overline{1}) where \overline{0} and \overline{1} are the elements 0 and 1 seen as generators in MR. It is easy to see that s is a section for the canonical presentation of R and that the subset \overline{s} : R_{s} → R is empty. Indeed, if we identify the elements of MS as functions f : S → R where fx ≠ 0 for only a finite number of elements of S then ux has value 1 at exactly one point. On the other hand, s0 is 0 everywhere and for x ≠ 0, (sx)0 = x = (sx)1 so cannot be ux if 0 ≠ 1. This shows that ∅ → R is the subobject \overline{s} : R_{s} → R determined by s. But R is not free on 0 generators.

(The referee pointed out that Proposition 2.9 also holds for R a rig, in the sense of [14]. Notice that it follows, from this more general result, that the monad on Set determined by the algebraic category of commutative monoids is not EB.)

When discussing Proposition 2.9 with some colleagues I found that they saw the result as suggesting that the Explicit Basis property was probably of little interest. It is true that the EB property is quite restrictive, but there are more examples than what Proposition 2.9, and its generalization to rigs, may suggest. Before looking at more examples let us make a general remark.

We can split the EB property into an ‘independent part’ and a ‘spanning part’. Proposition 2.11 below shows that the independent part is ‘easier’ than the spanning one.

2.10. Lemma. If s : (A, a) → (MA, m) then sa(M\overline{s}) = M\overline{s} : MA_{s} → MA.

Proof. The diagram below

\xymatrix{MA_{s} \ar[r]^{M\overline{s}} & MA \ar[d]_{Mu} \ar[d]^{Ms} \ar[r]^{a} & A \ar[d]^{s} \\  & MMA \ar[r]_{m} & MA}

shows that sa(M\overline{s}) = m(Mu)(M\overline{s}) = M\overline{s}.

Using this observation we obtain a useful characterization of independence.

2.11. Proposition. If s : (A, a) → (MA, m) then the canonical restriction \overline{s} : A_{s} → A is independent if and only if M\overline{s} is mono.

Proof. If a(M\overline{s}) is mono, M\overline{s} is mono. For the converse, notice that sa(M\overline{s}) = M\overline{s} by Lemma 2.10 so, as M\overline{s} is mono, a(M\overline{s}) is also mono.

We will mostly concentrate on examples where the following is applicable.

2.12. Corollary. Let D have finite limits and M preserve monos. Then the monad M is EB if and only if for every algebra (A, a) and section s : (A, a) → (MA, m) of a : (MA, m) → (A, a), the canonical restriction \overline{s} : A_{s} → A is spanning for (A, a).

More briefly, M is EB iff canonical restrictions are spanning.

3. Compact convex sets

The example discussed in this section was suggested by Lawvere who observed that the idea of a canonical subobject of generators was similar to the relation between a compact convex set and its subset of extreme points.

By a compact convex set we mean a compact convex subset of a locally convex Hausdorff real vector space. The set of extreme points of a compact convex set K is denoted by ∂_{e}K. Let cConv be the category of compact convex sets and continuous affine functions between them. The underlying space functor cConv → cHaus is monadic ([17] and 23.7.2 in [16]). The left adjoint assigns to a compact Hausdorff space X the convex set PX of probability measures on X. Let us denote the resulting monad by (P, u, m). The unit u : X → PX assigns to each x in X the Dirac measure δ_{x} on X at x. The unit also coincides with the subset ∂_{e}(PX) → PX equipped with the subspace topology (VII in [15]).

3.1. Lemma. The functor P : cHaus → cHaus is conservative.

Proof. The functor is faithful because the unit u : Id → P is mono. As cHaus is balanced, it follows that P reflects isos.

If K is a compact convex set then there is a continuous affine function 𝔯 : PK → K which assigns to each probability measure on K its centroid or barycenter (23.4.2 in [16]). The map 𝔯 is, of course, the canonical presentation of K as a P-algebra. We will need the following characterization of extreme points (Corollary 23.8.3 in [16]).

3.2. Lemma. For K in cConv, x ∈ ∂_{e}K if and only if for every μ ∈ PK, 𝔯μ = x implies μ = δ_{x}.

The key to the proof that P is EB is the relation between canonical restrictions and subsets of extreme elements.

3.3. Lemma. Let K be a free P-algebra and let s : K → PK in cConv be a section of 𝔯 : PK → K. Then the canonical restriction \overline{s} : K_{s} → K coincides with ∂_{e}K → K.

Proof. The facts recalled before Lemma 3.1 imply that ∂_{e}K is a compact Hausdorff space and that ∂_{e}K → K is a basis for K. We claim that the following diagram

\xymatrix{∂_{e}K \ar[r] & K \ar[r]^{u} \ar[r]_{s} & PK}

commutes. To prove the claim, let x ∈ ∂_{e}K. Since 𝔯(sx) = x, Lemma 3.2 implies that sx = δ_{x}, so sx = ux. The commutative diagram implies that ∂_{e}K → K factors through the canonical restriction \overline{s} : K_{s} → K. Let j : ∂_{e}K → K_{s} be the unique map making the diagram on the left below

\xymatrix{∂_{e}K \ar[d]_{j} \ar[dr] &  & P(∂_{e}K) \ar[d]_{Pj} \ar[r] & PK \ar[dr]^{𝔯} \\ K_{s} \ar[r]_{\overline{s}} & K & P(K_{s}) \ar[r]_{P\overline{s}} & PK \ar[r]_{𝔯} & K}

commute. We then have a diagram as on the right above with top-right composition an iso. It follows that Pj is mono. As P preserves monos (see 23.7.2 and 18.3.4 in [16]), \overline{s} is independent by Proposition 2.11. That is, the bottom line of the diagram on the right above is mono. It follows that Pj is also split epi and hence an iso. But P reflects isos (Lemma 3.1). So j : ∂_{e}K → K_{s} is an iso.

Idempotents split in the Kleisli category for (P, u, m). Indeed, Theorem 6 in [15] proves that every retract K of a simplex S is again a simplex. It also shows that if S is regular (i. e. the subset ∂_{e}S → S is closed) then K is also regular. Theorem 23.7.1 in [16] proves that regular simplexes coincide with free P-algebras.

3.4. Proposition. The monad determined by cConv → cHaus is EB.

Proof. Let s : K → PK be a section of 𝔯 : PK → K in cConv. As idempotents split in the Kleisli category, K is free and so ∂_{e}K → K is a basis. But then \overline{s} : K_{s} → K is a basis by Lemma 3.3.

The composition cConv → cHaus → Set is monadic. This is proved in [17] using a variation of a ‘tripleability criterion’ due to Linton. The left adjoint is the Stone-C̆ech compactification β : Set → cHaus followed by P. The monad determined by the composition cConv → Set does not satisfy the Explicit Basis property, though. This can easily be seen as follows. Let βS be the free compact Hausdorff space on the set S and consider a retract s : X → βS in cHaus. The space X is extremally disconnected but need not be of the form βS′ for a set S′. Applying P : cHaus → cConv we obtain a retract PX of P(βS). But PX is not a free (Pβ)-algebra. So idempotents do not split in the Kleisli category for the monad (Pβ) and hence the monad is not EB. It seems relevant to remark, though, that Theorem 9 in [15] proves that the retracts of compact convex sets of the form P(βS) are always of the form PX for an extremally disconnected space X.

Proposition 23.1.7 in [16] states that for morphisms s, t : K → K′ in cConv, if the diagram below

\xymatrix{∂_{e}K \ar[r]^{⊆} & K \ar[r]^{s} \ar[r]_{t} & K′}

commutes in Set then s = t. Some of this ‘denseness’ phenomenon is present at a more general level.

3.5. Proposition. Let s, t : (A, a) → (MA, m) be sections of the canonical presentation of (A, a). If their canonical restrictions coincide and are spanning then s = t.

Proof. Let A_{s} = B = A_{t} and \overline{s} = \overline{t} : B → A. Then calculate with the aid of Lemma 2.10: sa(M\overline{s}) = M\overline{s} = M\overline{t} = ta(M\overline{t}). Since a(M\overline{s}) = a(M\overline{t}) is epi by hypothesis, s = t.

If the Explicit Basis property holds, canonical restrictions are spanning.

3.6. Corollary. Let M be an EB monad and let s, t be sections of a : (MA, m) → (A, a). If their canonical restrictions coincide then s = t.

4. A characterization of intersection-preserving EB monads

In this section we let the base category D have finite limits.

4.1. Lemma. For any s : A → MA in D, the morphism m(Ms) : (MA, m) → (MA, m) is idempotent in Kl_{M} if and only if the following diagram

\xymatrix{A \ar[r]^{s} & MA \ar[rr]^{id} \ar[r]_{Ms} & MMA \ar[r]_{m} & MA}

commutes in D.

If the equivalent conditions of Lemma 4.1 hold then we say that s : A → MA is a Kleisli-idempotent. Notice that commutativity of the diagram in the statement is equivalent to the commutativity of the one below.

\xymatrix{A \ar[r]^{s} & MA \ar[r]^{Mu} \ar[r]_{Ms} & MMA \ar[r]^{m} & MA}

We will find it convenient to introduce a strengthening of this concept.

4.2. Definition. A morphism s : A → MA in D is called a strong Kleisli-idempotent if the following diagram

\xymatrix{A \ar[r]^{s} & MA \ar[r]^{Mu} \ar[r]_{Ms} & MMA}

commutes.

Clearly, every strong Kleisli-idempotent is a Kleisli-idempotent.

4.3. Lemma. Let s : (A, a) → (MA, m) be a section of the canonical presentation of (A, a). If \overline{s} : A_{s} → A is spanning then s : A → MA is a strong Kleisli-idempotent.

Proof. The morphism a(M\overline{s}) : MA_{s} → A is epi by hypothesis. So it is enough to check that (Mu)s(a(M\overline{s})) = (Ms)s(a(M\overline{s})). Consider the following diagram

\xymatrix{MA_{s} \ar[r]^{M\overline{s}} & MA \ar[d]_{a} \ar[r]^{Mu} \ar[r]_{Ms} & MMA \ar[d]^{m} \\  & A \ar[r]_{s} & MA \ar[r]^{Mu} \ar[r]_{Ms} & MMA}

where the small square commutes because s is an algebra map. The top fork commutes by definition of \overline{s} and, as m(Mu) = id, the problem reduces to the equality (Mu)(M\overline{s}) = (Ms)(M\overline{s}), which holds by definition of \overline{s}.

We say that M preserves intersections if, for every pullback diagram of monos in D as on the left below,

\xymatrix{U ∩ V \ar[d]_{π_{0}} \ar[r]^{π_{1}} & V \ar[d]^{v} & M(U ∩ V) \ar[d]_{Mπ_{0}} \ar[r]^{Mπ_{1}} & MV \ar[d]^{Mv} \\ U \ar[r]_{u} & X & MU \ar[r]_{Mu} & MX}

the square on the right is also a pullback.

4.4. Lemma. Let s : (A, a) → (MA, m) be a section of a : (MA, m) → (A, a). If M preserves intersections then \overline{s} : A_{s} → A is spanning if and only if s : A → MA is a strong Kleisli-idempotent.

Proof. One direction is proved in Lemma 4.3. For the converse, assume that s : A → MA is a strong Kleisli-idempotent. As M preserves intersections, the following diagram

\xymatrix{MA_{s} \ar[r]^{M\overline{s}} & MA \ar[r]^{Mu} \ar[r]_{Ms} & MMA}

is an equalizer. So, as s is a strong Kleisli idempotent, the map s : A → MA factors through the subobject M\overline{s} : MA_{s} → MA. But then, trivially, as = id : A → A factors through a(M\overline{s}). So a(M\overline{s}) is split epi and hence, \overline{s} : A_{s} → A is spanning.

Notice that, if M preserves intersections then it preserves monos. So, by Lemma 4.4, we obtain the following variation of Corollary 2.12.

4.5. Proposition. If M preserves intersections then M is EB if and only if for every algebra (A, a), and section s : (A, a) → (MA, m) of a : (MA, m) → (A, a), the Kleisliidempotent s : A → MA is strong.

(Incidentally, observe that the same result holds if we replace preservation of intersections with the awkward hypothesis ‘preserves monos and equalizers’. Preservation of monos implies that independence is easy and preservation of equalizers allows to prove Lemma 4.4. But it is the explicit consideration of UIOs which suggests the much cleaner hypothesis stated in Proposition 4.5. Again, I would like to thank Lawvere for the suggestion to take advantage of the intersection/equalizer coincidence for opposites in a UIO.)

So far, we have only used finite limits in D to construct canonical restrictions. Further exploiting the assumption of finite limits in the base, it is possible to characterize intersection preserving EB monads without mentioning algebras.

4.6. Lemma. Let s : A → MA be a Kleisli-idempotent in the category D. If the idempotent m(Ms) : (MA, m) → (MA, m) splits (in Alg_{M}) as a retraction r : (MA, m) → (B, b) followed by a section t : (B, b) → (MA, m) then the following hold:

1. The map s is mono if and only if the composition ru : A → B is mono.

2. The diagram below

\xymatrix{A \ar[d]_{s} \ar[r]^{u} & MA \ar[r]^{r} & B \ar[d]^{[t;r]} \\ MA \ar[r]_{Mu} & MA \ar[r]_{Mr} & MB}

commutes.

Proof. The diagram below

\xymatrix{A \ar[d]_{s} \ar[r]^{u} & MA \ar[d]^{Ms} \ar[r]^{r} & B \ar[d]^{t} \\ MA \ar[rr]_{id} \ar[r]^{u_{M}} & MMA \ar[r]^{m} & MA}

shows that tru = s. Hence, s is mono if and only if ru is. To prove the second item, recall (Lemma 2.2) that [t; r] is the composition (Mr)(Mu)t : B → MB. Then calculate using the diagram above: [t; r]ru = (Mr)(Mu)tru = (Mr)(Mu)s.

4.7. Proposition. If M preserves intersections then the following are equivalent:

1. M satisfies the Explicit Basis property,

2. every monic Kleisli-idempotent is strong.

Proof. The second item in the statement implies the first by Proposition 4.5. So we need only show the converse. Assume that the monad is EB and that s : A → MA is a monic Kleisli-idempotent. We need to show that it is strong. As D has finite limits, the idempotent m(Ms) : (MA, m) → (MA, m) splits in Alg_{M}. Let t : (B, b) → (MA, m) together with r : (MA, m) → (B, b) be a splitting of the idempotent. So that rt = id_{B} and tr = m(Ms) : MA → MA. The Kleisli idempotent [t; r] : B → MB is strong by Proposition 4.5. So the bottom fork of the diagram below commutes. If we denote the composition ru by i : A → B then the diagram below

\xymatrix{A \ar[d]_{i} \ar[r]^{s} & MA \ar[d]_{Mi} \ar[r]^{u} \ar[r]_{Ms} & MMA \ar[d]^{MMi} \\ B \ar[r]_{[t;r]} & MB \ar[r]^{u} \ar[r]_{M[t;r]} & MMB}

commutes by Lemma 4.6. To prove that the top fork commutes it is enough to show that MMi is mono. But M preserves monos and i = ru is mono by Lemma 4.6.

In many cases it will be possible to apply the following sufficient condition.

4.8. Corollary. If M preserves pullbacks and every Kleisli-idempotent is strong then M is EB.

5. Categories and reflexive graphs

Let Δ_{1} be the three-element monoid of all order-preserving endos of the two-element linearly ordered set, and consider the presheaf topos Δ̂_{1} of ‘reflexive graphs’ [7]. There is an obvious ‘underlying graph’ functor Cat → Δ̂_{1} where Cat denotes the category of small categories and functors between them. Consider its left adjoint F : Δ̂_{1} → Cat. Each object G in Δ̂_{1} has ‘identity’ edges and ‘non-identity’ edges. The category F G has, as objects, the nodes of G. For each pair (x, x′) of nodes, the morphisms from x to x′ correspond to sequences [f_{1}, …, f_{n}] of non-identity edges appearing as in a diagram below

\xymatrix{x \ar[r]_{f_{n}} & · \ar[r]_{f_{n−1}} & · . . . · \ar[r]_{f_{2}} & · \ar[r]_{f_{1}} & x′}

in G. For each node x, the empty sequence [] in (F G)(x, x) acts as the identity morphism of the object x. Denote the resulting monad on Δ̂_{1} by M = (M, u, m). The unit u : G → MG maps each node to itself, each identity edge to the corresponding empty sequence and each non-identity f in G to the morphism (f) in F G. The multiplication MMG → MG maps a sequence of sequences to the obvious ‘flattened’ sequence.

We show that M is EB using Proposition 4.7. This example also shows that Corollary 4.8 is not always applicable. One reason is the following.

5.1. Example. [M does not preserve pullbacks.] The functor M preserves the terminal object. So, to show that it does not preserve pullbacks in general, it is enough to show that it does not preserve products. Consider the total order 2 with two elements, seen as a reflexive graph. Since there are no composable non-identity arrows, it follows that M2 = 2. To confirm that M does not preserve products compare M(2 × 2) with (M2) × (M2) = 2 × 2.

On the other hand, it is straightforward to prove the following.

5.2. Lemma. The functor M : Δ̂_{1} → Δ̂_{1} preserves intersections.

It is clear that Corollary 4.8 is still valid if we weaken the hypothesis to an intersectionpreserving M. This stronger result is not applicable either to our present M.

5.3. Example. [A non-strong Kleisli-idempotent.] Consider the reflexive graph G with one node and two non-identity loops, say, a and b. Let s : G → MG be the graph morphism determined by sa = [a, b] and sb = []. To check that s is a Kleisli-idempotent notice that, trivially, m(Ms)(s id) = m(Ms)[] = [] = s id where id denotes the unique identity in G. We also have that m(Ms)(sb) = m(Ms)[] = [] = sb. Finally, to check that m(Ms)(sa) = sa, notice first that

(Ms)[a, b] = [sa, sb] = [sa][sb] = [[a, b]][] = [[a, b]] ∈ MMG

and so,

m((Ms)(sa)) = m((Ms)[a, b]) = m[[a, b]] = [a, b] = sa

which completes the verification that s is a Kleisli idempotent. On the other hand, (Mu)(sa) = (Mu)[a, b] = [[a], [b]] but (Ms)(sa) = (Ms)[a, b] = [[a, b]]. So s is not strong.

So we rely on Proposition 4.7 to prove the following.

5.4. Corollary. The monad on Δ̂_{1} induced by the forgetful Cat → Δ̂_{1} is EB.

Proof. Let G be a reflexive graph and let s : G → MG be a monic Kleisli-idempotent. We need to show that (Mu)s = (Ms)s : G → M(MG). The first thing to notice is that, as s is monic, sf = [] implies f is an identity edge. Also, if f is an identity edge, then (Mu)(sf) = [] = (Ms)(sf) so we can concentrate on the case when f is not an identity. Let sf = [f_{1}, …, f_{n}] with all f_{i} non-identities in G and n ≥ 1. Let sf_{i} = [g_{i,1}, …, g_{i,k_{i}}] with k_{i} ≥ 1. As s is a Kleisli idempotent we have that

[f_{1}, …, f_{n}] = sf = m((Ms)[f_{1}, …, f_{n}]) = m[sf_{1}, …, sf_{n}] = [g_{1,1}, …, g_{1,k_{1}}, g_{2,1}, …, g_{n,k_{n}}]

in MG. But since, k_{i} ≥ 1 for all i, then we must have that k_{i} = 1 and that g_{i,1} = f_{i}. So that sf_{i} = [f_{i}] and it follows that (Mu)(sf) = (Ms)(sf).

Non-reflexive graphs also generate free categories. The forgetful U : Cat → Set^{⇉} assigns, to each small category, its underlying non-reflexive graph. Denote its left adjoint by F : Set^{⇉} → Cat. For each G in Set^{⇉}, the objects of F G are the nodes of G. For each pair (x, x′) of nodes, the morphisms from x to x′ correspond to ‘paths’ [f_{1}, …, f_{n}] of edges as in the previous case, but in the present case there is no distinction between ‘identity’ and ‘non-identity’ edges. Denote the resulting monad on Set^{⇉} by M = (M, u, m). The unit u : G → MG maps an edge f in G to the morphism [f]. In contrast with the previous case, the identities of F G are not in the image of u. Despite the similarities, the toposes Δ̂_{1} and Set^{⇉} are quite different [7]. So the following qualitative distinction is not surprising.

5.5. Example. [Cat is not EB over Set^{⇉}.] Consider the monoid (ℕ, +, 0) as a category and let ℕ in Set^{⇉} be its underlying graph. The free category F ℕ coincides with the free monoid (ℕ^{∗}, ∗, []) seen as a category. The canonical presentation (ℕ^{∗}, ∗, []) → (ℕ, +, 0) assigns to each sequence [n_{1}, …, n_{k}] in ℕ^{∗}, the sum n_{1} + … + n_{k}. The assignment 1 ↦ [0, 1] extends to a unique monoid morphism s : (ℕ, +, 0) → (ℕ^{∗}, ∗, ()). It is clearly a section for the canonical presentation. But its canonical restriction is the empty subobject 0 → ℕ, which is not spanning.

6. Presheaves on reduced categories

Let C be a small category and let ι : C_{0} → C be the discrete subcategory determined by all the objects of C. Precomposition with ι determines a monadic functor ι^{∗} : Ĉ → Ĉ_{0} between the presheaf toposes Ĉ and Ĉ_{0}. Its left adjoint is denoted by ι_{!} : Ĉ_{0} → Ĉ. Let M = (M, u, m) be the induced monad on Ĉ_{0} with M = ι^{∗}ι_{!}. We characterize the categories C such that M is EB. The left adjoint ι_{!} : Ĉ_{0} → Ĉ can be explicitly described as follows. For P in Ĉ_{0} and C in C, (ι_{!}P)C = ∑_{D∈C} P D × C(C, D). This explicit description allows a direct proof that ι_{!} preserves pullbacks. (We discuss an alternative proof in Section 9.) The unit u : P → MP assigns, to each x ∈ P C, the element (x, id_{C}) ∈ (MP)C.

A category C is reduced if every idempotent in C is an identity. (See p. 294 in [7].)

6.1. Lemma. If C is reduced then every Kleisli-idempotent in Ĉ_{0} is strong.

Proof. Let P be a presheaf in Ĉ_{0} and let s : P → MP be such that m(Ms)s = s. Fix an x ∈ P C. Let sx = (y, g) with g : C → D and sy = (z, h) with h : D → E. Now calculate:

(y, g) = sx = m((Ms)(y, g)) = m((z, h), g) = (z, hg)

and conclude that g = hg and y = z. It follows that sy = (y, h) and so, the following calculation

(y, h) = sy = m((Ms)(y, h)) = m(sy, h) = m((y, h), h) = (y, hh)

implies that h is idempotent. As C is reduced, h = 1. So sy = (y, 1) = uy.

We have already observed that ι_{!} preserves pullbacks. Its right adjoint obviously preserves limits. So M = ι^{∗}ι_{!} preserves pullbacks. Corollary 4.8 together with Lemma 6.1 imply that M is EB. The characterization below states that the converse also holds.

6.2. Proposition. The monad M on Ĉ_{0} is EB if and only if C is reduced.

Proof. Denote the representable C_{0}( , B) by y_{0}B in Ĉ_{0}. Notice that

(M(y_{0}B))C = ∑_{D∈C} C_{0}(D, B) × C(C, D) ≅ C(C, B)

so each endo h : B → B in C induces a monic natural transformation \underline{h} : y_{0}B → M(y_{0}B) in Ĉ_{0} that maps id_{B} in (y_{0}B)B = C_{0}(B, B) to (id, h) ∈ (M(y_{0}B))B. If h is idempotent then \underline{h} is a (monic) Kleisli-idempotent. If the Explicit Basis property holds, \underline{h} is strong by Proposition 4.7. Using this fact in the middle of the calculation below

((id, id), h) = (Mu)(id, h) = (Mu)(\underline{h} id_{B}) = (M\underline{h})(\underline{h} id_{B}) = (M\underline{h})(id, h) = ((id, h), h)

we obtain that ((id, id), h) = ((id, h), h), so (id, id) = (id, h) and hence, h = id.

As a byproduct we obtain some EB monads on Set. (We say that an algebraic category V is EB if the monad on Set determined by the algebraic functor V → Set is EB.)

6.3. Corollary. Let N be a monoid. The category N̂ of right-N-actions is EB if and only if N is reduced. Moreover, in this case, every Kleisli idempotent is strong.

6.4. Corollary. [Janelidze] The algebraic category of G-sets is EB for every group G.

Corollary 6.4 was one of the first sources of examples of EB monads over Set. The referee suggested that the result could be extended from groups to a certain class of monoids. At the same time, Lawvere pointed out that many EB monads are induced by essential surjections between toposes. These observations naturally led to Proposition 6.2. Essential surjections will be discussed in more generality in Section 9, where the following description of the Kleisli category for the monad on Ĉ_{0} induced by C_{0} → C will be needed.

6.5. Lemma. The Yoneda embedding C → Ĉ = Alg factors through Kl → Alg and the factorization C → Kl coincides with the coproduct completion of C.

Proof. Let y_{0}C = C_{0}( , A) ∈ Ĉ_{0} and yC = C( , C) ∈ Ĉ. As ι : C_{0} → C is the discrete subcategory of objects of C, ι_{!}(y_{0}A) = yA. Since Ĉ_{0} is the coproduct completion of C_{0}, the Kleisli category for M = ι^{∗}ι_{!} coincides with the coproduct completion of C.

It follows that if every map in C is epi, then Kl → Alg = Ĉ factors through the subcategory (Ĉ)_{d} → Ĉ of decidable objects of Ĉ.

6.6. Lemma. If C is a finite ordinal then the embedding Kl → (Ĉ)_{d} is an equivalence.

Proof. First notice that for P in Ĉ_{0}, (ι_{!}P)m = ∑_{n≥m} P n. Now, for D in (Ĉ)_{d}, and x ∈ Dm, there exists a largest n such that there is y ∈ Dn with (D(m ≤ n))y = x. As D is decidable, the pair (n, y) is unique. Define s : D → MD to be the unique morphism that maps each x in Dm to the corresponding (n, y) ∈ (MD)m. It is easy to check that s is a Kleisli idempotent. The explicit basis property implies that D is free.

Notice that finiteness is not really needed. The same argument works for (ℕ, ≥).

7. Free Algebraic Theories

Every algebraic theory induces a monad on Set. For brevity we say that an algebraic theory is EB if the corresponding monad satisfies the Explicit Basis property. For example, Proposition 2.9 shows that the theory of R-modules is not EB unless R is trivial. Corollary 6.3 characterizes EB-theories of monoid actions. The theory of pointed sets is EB by Proposition 2.7.

Let T be the category of algebraic theories. There is a forgetful functor T : T → Set^{ℕ} which assigns, to each algebraic theory, its set of operations indexed by their arity (see Section II.2 in [9]). In this context, an object of Set^{ℕ} may be thought of as a set of ‘operations’ indexed by their arity. That is, as a presentation without equations. The functor T has a left adjoint F : Set^{ℕ} → T that produces the free theory out of an indexed set of operations.

7.1. Proposition. Free algebraic theories are EB.

Proof. We use Corollary 4.8. Let P be an object in Set^{ℕ} and let M = (M, u, m) be the monad determined by the free theory generated by P. The functor M : Set → Set can be described as assigning, to each set S, the set MS of terms built from elements of S and using the operations in the presentation P. As there are no equations, there is no quotienting involved in the construction of the free algebra. So two elements of the free algebra are equal if and only if they are ‘syntactically’ equal. It is then not difficult to prove that M preserves pullbacks. Let s : S → MS be a Kleisli-idempotent. Let v ∈ S and sv = t(v_{1}, …, v_{n}) with t(x_{1}, …, x_{n}) a term with {x_{1}, …, x_{n}} as its set of free variables and v_{1}, …, v_{n} ∈ A. As s is a Kleisli-idempotent, we can calculate as follows

t(v_{1}, …, v_{n}) = sv = m((Ms)t(v_{1}, …, v_{n})) = m(t(sv_{1}, …, sv_{n})) = t(sv_{1}, …, sv_{n})

so, as equality in MA is syntactic equality, it must be the case that sv_{i} = v_{i} for every i. This means that s is strong as a Kleisli-idempotent.

Proposition 7.1 was motivated by an observation due to G. Janelidze, who noticed that algebraic categories presented using only nullary operations are EB, and that the key to the proof is that sections for canonical presentations are unique. For example, the theory of pointed sets. A different example is the theory of ‘discrete dynamical systems’ which can be freely presented by a single unary operation.

The algebraic categories of monoid actions discussed in Corollary 6.3 show that we can add some equations to a presentation and still get an EB theory. We leave the characterization of EB theories as an open problem. But before leaving this section we mention one more example.

7.2. Example. [The theory of monoids is not EB] Same argument used in Example 5.5.

In contrast with Example 7.2, the next section shows that some categories of monoids do induce EB monads.

8. The Exponential Principle

The symmetric-monoidal completion !1 of the trivial group has, as underlying category, the groupoid B of finite sets and bijections. The monoidal structure on !1 induces, via Day’s convolution, a symmetric monoidal structure on Set^{B} that we denote by Joy = (Set^{B}, ·, I). As explained in [6], every object F of Joy has an associated ‘power series’ F (x) = ∑_{n≥0} ♯(F [n])\frac{x^{n}}{n!} and the assignment F ↦ F (x) ‘preserves multiplication’.

Define a functor E : Set^{B} → Set^{B} by the formula

(EF)U = ∑_{π} ∏_{p∈π} F U_{p}

where the sum ranges over partitions of U. Notice that (EF)∅ = 1. The notation reflects the fact that (EF)(x) = e^{F (x)}. There is a natural transformation u : Id → E defined, for every F, as follows. When U is ∅, u is the unique F ∅ → 1. When U is not empty, u : F U → (EF)U maps an element x of F U to the unique partition of U with one element together with x. There is also a transformation m : EE → E whose explicit definition relies on the operation that takes a partition π of U together with a partition σ_{p} of p for each p in π and builds the evident, finer, partition of U given by the union of the σ_{p}’s.

Algebras for the monad E correspond to monoids F in Joy such that F ∅ = 1. Free E-algebras can be characterized as monoids satisfying certain pullback condition [11]. But, even without this characterization, an application of Corollary 4.8 proves the following.

8.1. Lemma. The monad (E, u, m) on Joy is EB.

The above discussion can be generalized by replacing 1 with a small groupoid G. So that the presheaf category ˆ!G is equipped with a symmetric monoidal structure and a monad E. In particular, the discrete groupoid with two elements induces a symmetric monoidal structure Joy_{2} = (Set^{B×B}, ·, I). Each object F ∈ Joy_{2} in Joy_{2} has an associated power series

F (x, y) = … + ♯F ([n], [m])\frac{x^{n}y^{m}}{n!m!} + …

in two variables x and y. (See Section 5 in [6].) The functor E : Set^{B×B} → Set^{B×B} can be defined using the formula for E : Set^{B} → Set^{B}, but adjusting the notion of partition. A partition π of (U, V) in B × B is a finite collection {(U_{i}, V_{i})}_{i∈I} with U_{i} or V_{i} nonempty for each i and such that {U_{i}}_{i∈I} is a pairwise disjoint family with union U (notice that some components may be empty) and similarly for {V_{i}}_{i∈I} in relation to V. So that (EF)(U, V) = ∑_{π} ∏_{(U_{i},V_{i})∈π} F (U_{i}, V_{i}) for F in Joy_{2}. The generalized version of Lemma 8.1 implies that the monad E on Joy_{2} is EB.

Let Y be the object of Joy_{2} which has value 0 at each (U, V) except for Y (0, 1) = 1. Its associated series Y (x, y) is just y. For any G in Joy, let G_{x} in Joy_{2} be defined by G_{x}(U, V) = GU if V = 0 and empty otherwise. Its associated series is

G_{x}(x, y) = G0 + (G1)x + … + (Gn)\frac{x^{n}}{n!} + …

so the series associated to Y · G_{x} is

(G0)y + (G1)yx + (G2)\frac{yx^{2}}{2} + … + (Gn)\frac{yx^{n}}{n!} + …

because (Y · G_{x})(U, 1) = GU and (Y · G_{x})(U, V) = 0 if V ≠ 1.

For any G in Joy such that G∅ = ∅ define ΘG in Joy_{2} as follows:

(ΘG)(U, V) = {{x_{p}}_{p∈π} ∈ (EG)U | π = {p_{v}}_{v∈V} }

so that, (ΘG)(U, V) is the set of elements of (EG)U with ♯V components.

8.2. Corollary. For any G in Joy with G∅ = ∅ there is an iso E(Y · G_{x}) → ΘG in Joy_{2}.

Proof. Joining disjoint families induces an E-algebra a : E(ΘG) → ΘG in Joy_{2}. Define the morphism s : ΘG → E(ΘG) which, at stage (U, V), takes a collection {x_{p}}_{p∈π} in (EG)U such that π = {p_{v}}_{v∈V}, and produces the partition {(p_{v}, {v})}_{v∈V} of (U, V) together with the collection (indexed by V) of elements in (ΘG)(p_{v}, {v}) given by the x_{p} ∈ GU_{p}. It is easy to check that s is an algebra morphism and a section, and that its canonical restriction is Y · G_{x} → ΘG. Since E : Joy_{2} → Joy_{2} is EB, the result follows.

The coefficient in the term c_{i,j}x^{i}y^{j} of the series (ΘG)(x, y) is the number of families, with j components, of elements of G with labels in a set of size i. Corollary 8.2 implies that (ΘG)(x, y) = e^{yG(x)}. See [11] for a different combinatorial proof.

9. Essential surjections

A geometric morphism f : F → E between toposes is a surjection if f^{∗} : E → F is faithful. Equivalently, E is comonadic over F for the comonad induced by f^{∗} ⊣ f_{∗}. If the surjection is essential (with f_{!} : F → E denoting the left adjoint to f^{∗}) then, a well-known result due to Eilenberg and Moore implies that f^{∗} : E → F is monadic. Lawvere observed that many examples of EB monads appear in this guise and suggested to consider this type of example explicitly. The characterizations proved in Section 4, lead us to pay particular attention to essential surjections such that f_{!} : F → E preserves pullbacks.

Every functor f : A → X between small categories induces an essential geometric morphism f : Â → X̂, between the associated presheaf toposes, such that the inverse image f^{∗} : X̂ → Â is pre-composition with f : A → X. This geometric morphism is a surjection if and only if every object of X is a retract of an object in the image of f (A4.2.7(b) in [5]). The functor f_{!} preserves pullbacks if and only if for each object X in X, the category (X ↓ f) is weakly cofiltered (Example A4.1.10 and Remark B2.6.9 in [5]). That is, (X ↓ f) satisfies the right Ore condition and every parallel pair of maps in (X ↓ f) can be equalized.

For example, for any small category C, the inclusion C_{0} → C of the discrete subcategory of objects induces an essential surjection Ĉ_{0} → Ĉ with pullback preserving f_{!}. Proposition 6.2 characterizes those C that determine an EB monad in this way. We now discuss a different type of example.

9.1. Factorization monads. Let C be an essentially small category equipped with an (E, M)-factorization system. The inclusion ι : M → C is bijective on objects, so it induces an essential surjection ι : M̂ → Ĉbetween presheaf toposes. The resulting monad on M̂ is called the factorization monad associated to (E, M), and we denote it by M = (M, u, m).

9.2. Lemma. If every map in E is epi, the functor ι_{!} : M̂ → Ĉ preserves pullbacks.

Proof. We need to prove that, for each object X in C, the category (X ↓ ι) is weakly cofiltered. Consider a parallel pair of maps in (X ↓ ι) as on the left below

\xymatrix{X \ar[d]_{f} \ar[dr]^{g} &  &  & X \ar[dl]_{e} \ar[d]^{f} \ar[dr]^{g} \\ Y \ar[r]^{m} \ar[r]_{n} & Z & X′ \ar[r]_{j} & Y \ar[r]^{m} \ar[r]_{n} & Z}

with m, n ∈ M are considered as maps from the object f to the object g in (X ↓ ι). Let f = je with e ∈ E and j ∈ M. We can extend the diagram in (X ↓ ι) as on the right above. Since e is epi, the bottom fork commutes. So every parallel pair of maps can be equalized. The right Ore condition is left for the reader.

The special type of inclusion that we are considering implies that the definition of ι_{!} in terms of coends can be simplified as follows. (See [3] for details.) For X in C,

(ι_{!}P)X = ∫ ^{M∈M} P M × C(X, M) ≅ ∫ ^{I∈I} P I × E(X, I)

where I denotes the subgroupoid of isos of C. If f : X → Z factors as e : X → Y in E followed by m : Y → Z in M, then z ⊗f = z ⊗(me) = (z · m) ⊗e, where z · m denotes (P m)z. So, an element of (ι_{!}P)X will typically be denoted by y ⊗e where e : X → Y is a map in E and y ∈ P Y. Moreover, if z ⊗d with d : X → Z is also an element of (ι_{!}P)X with d in E, then y ⊗e = z ⊗d if and only if there is an iso j : Y → Z such that je = d as below

\xymatrix{ & X \ar[dl]_{e} \ar[dr]^{d} \\ Y \ar[rr]_{j} &  & Z}

and z · j = y. The canonical cover MF → F maps x ⊗f to x · f.

9.3. Proposition. If every map in E is epi then M is EB.

Proof. Since M preserves pullbacks by Lemma 9.2, it is enough to show that every Kleisli-idempotent is strong (Corollary 4.8). Let s : P → MP be such that m(Ms)s = s. To prove that (Ms)s = (Mu)s, let x ∈ P X, sx = y ⊗e with e : X → Y in E and sy = z ⊗d with d : Y → Z in E. By hypothesis, sx = y ⊗e = z ⊗(de). This means that there is an iso j : Y → Z such that je = de and z · j = y. As e is epi by hypothesis, j = d. So sy = z ⊗j = (z · j) ⊗id = y ⊗id = uy. This implies that s is strong.

We have been unable to characterize the functors f : A → X, between small categories, such that the induced monad f^{∗}f_{!} on Â is EB. If f_{!} preserves pullbacks then it is possible to give a simple description of the equivalence relation on ∑_{A} P A × X (X, A) whose quotient is the coend (f_{!}P)X = ∫^{A∈A} P A × X (X, A). (Not as simple as that in the case of factorization monads but simple enough.) It is also possible to device a restricted notion of functor that has C_{0} → C and M → C as particular cases and that, together with a variation of the condition ‘without idempotents’, implies that the induced monad is EB. The details are too awkward to state and do not suggest interesting further examples. We therefore omit them.

9.4. The smallest subtopos through which f_{!} factors. Surjections f : F → E between toposes are orthogonal to inclusions. So there is no non-trivial subtopos of E through which f_{∗} factors. On the other hand, if f is essential, the smallest subtopos of E through which f_{!} factors may be non-trivial. I don’t know a satisfactory explanation for this phenomenon. But some examples appear in the context where f^{∗}f_{!} is an EB monad, so we briefly mention them here.

Let C be a small category and let ι : C_{0} → C be its discrete subcategory of objects. Consider the monad on Ĉ_{0} induced by the essential surjection Ĉ_{0} → Ĉ as in Section 6. If the embedding Kl → Alg is a topos inclusion then, trivially, this subtopos is the smallest through which ι_{!} : Ĉ_{0} → Ĉ factors. We prove that the toposes that appear as Kleisli categories in this way are the atomic toposes in the sense of [1]. As a corollary of this result it follows that all the monads involved are EB.

Recall that an atomic site is a category equipped with a Grothendieck topology such that a sieve covers if and only if it is non-empty. In order for C to admit such a topology, it is necessary and sufficient that any pair of maps with common codomain can be completed to a commutative square. That is, that C satisfies the right Ore condition.

A morphism e : A → B is a strict epi if it is the common coequalizer of all pairs of maps that it coequalizes. The atomic topology on C is subcanonical if and only if every map in C is a strict epi. If C is an atomic site, we denote the associated topos of sheaves by Shv(C). The coproduct completion of C is denoted by FamC.

9.5. Lemma. If FamC is a topos then C is a subcanonical atomic site and FamC is equivalent to the atomic topos Shv(C).

Proof. As C is essentially small, FamC is atomic (see e.g. Corollary 1.3 in [12]). The image of the embedding C → FamC is characterized as the indecomposables, so C is the category of atoms of FamC. Inspection of the proof of Theorem A in [1] shows that for every atomic topos, the full subcategory of atoms is a canonical atomic site and that the category of sheaves on this site is equivalent to the given topos.

9.6. Proposition. For the monad on Ĉ_{0} determined by the inclusion C_{0} → C, the embedding Kl → Alg = Ĉ is a subtopos inclusion if and only if FamC is a topos. In this case, the monad is EB, C is an atomic site and Kl = Shv(C).

Proof. The Kleisli category coincides with FamC by Lemma 6.5. So one direction is trivial. The other follows from Lemma 9.5. As every map in an atomic site is epi, its underlying category is reduced and so, the monad is EB by Proposition 6.2.

This result provides many examples of essential surjections such that f_{!} factors through a non-trivial subtopos. In contrast, consider the following.

9.7. Corollary. Let C be a finite category whose idempotents split. Then the least subtopos of Ĉ through which ι_{!} : Ĉ_{0} → Ĉ factors is Ĉ itself.

Proof. The hypotheses on C imply that subtoposes of Ĉ are in correspondence with the full subcategories of C. By Lemma 6.5, the Kleisli category contains all the representables in Ĉ. So the least subtopos of Ĉ containing Kl must be Ĉ → Ĉ.

Since idempotents split trivially in a reduced category, the corollary above can be applied to the essential surjections inducing EB monads characterized in Proposition 6.2.

We end this section with two examples involving factorization monads.

9.8. Example. Let X be the category resulting from splitting the monoid with a unique idempotent. By Proposition 9.3, the inclusion 2 → X determined by the unique nonidentity mono in X induces an essential surjection f : ˆ2 → X̂ such that f^{∗}f_{!} is an EB factorization monad. For this monad, the inclusion Kl → Alg is an equivalence.

Finally, one of the main examples of the paper.

9.9. Example. [The Schanuel topos.] Let I be the category of finite sets and injections and B → I be its subgroupoid of isos. The essential surjection Set^{B} → Set^{I} determines an EB monad on Set^{B} by Proposition 9.3. Results in [3] imply that Kl → Alg = Set^{I} coincides with the subcategory Sch → Set^{I} of pullback-preserving functors.

I presented some of the results in [3] at the CT2004 conference. After the talk, Lawvere suggested that the equivalence between Sch and a Kleisli category for a monad on Set^{B} had to be related with Myhill’s theory of combinatorial functions which, in fact, was Schanuel’s original motivation. In the next section, I present some details of the relation between Sch and Myhill’s theory. This is done both because of its historical interest and because Myhill’s notion of combinatorial operator suggested the Explicit Basis property.

10. The Schanuel topos and Myhill’s combinatorial functions

Let M = (M, u, m) be the monad on Set^{B} presented in Example 9.9. It is instructive to give a more concrete description of M. If C is an object of Set^{B} then, for each finite set U, (MC)U = ∑_{V ⊆U} CV. Assume for a moment that CU is finite for each U. If we let c_{i} denote the cardinality ♯(CV) of the set CV for any set V with ♯V = i, then it is clear that ♯((MC)U) = ∑_{i=0}^{n} c_{i}\binom{n}{i} where n = ♯U. So, regardless of cardinality, we will picture C as a sequence \{c_{i}\}_{i∈ℕ} of coefficients and the free algebra MC as a ‘series’ ∑_{i≥0} c_{i}\binom{x}{i}.

Sch is usually presented as a topos of continuous actions or as the topos of sheaves for the atomic topology on I^{op}. It is curious that its role as a Kleisli category is probably the closest to its original motivation. Schanuel’s work on the category of pullback-preserving functors I → Set was motivated by the wish to understand some results in Tamhankar’s thesis (involving identities about binomial coefficients) and Myhill’s conceptual account of such identities in terms of combinatorial functions. Schanuel’s idea was to organize the combinatorial objects that give rise to combinatorial functions into a category. He conjectured that the objects of this new category were uniquely sums of quotients of representables, and Lawvere suggested that the idea sounded like an ‘atomic topos’, a notion Barr had just sent him a preprint about. The above must have occurred during the second part of the 70’s. (According to the UB Library Catalog, Tamhankar’s thesis was published in 1976. The paper [1] on atomic toposes was published in 1980.) The classifying role of the resulting topos is due to Lawvere and Schanuel. The term ‘Schanuel topos’ probably first appeared in [7]. I am grateful to Lawvere and Schanuel who informed me of the historical details.

10.1. Combinatorial functions. The brief summary that follows is based on [2]. In order to introduce the class of combinatorial functions Dekker observes that, as a special case of Newton’s approximation theorem, for every function f : ℕ → ℕ there exists a unique function c : ℕ → ℤ such that for every n ∈ ℕ, fn = ∑_{i=0}^{n} c_{i}\binom{n}{i}. Most of [2] is then devoted to give combinatorial meaning to the subclass of functions f for which c_{i} is non-negative for all i.

Let Q be the set of finite sets of natural numbers and define an operator to be a function Q → Q. An operator ϕ is called numerical if for a and b in Q of the same cardinality, ϕa and ϕb have the same cardinality. Clearly, every numerical operator induces a function ℕ → ℕ. For a numerical operator ϕ let ϕ^{ε} = ⋃{ϕa | a ∈ Q}.

10.2. Definition. A numerical operator ϕ is combinatorial if there exists a ϕ^{−1} : ϕ^{ε} → Q such that x ∈ ϕa if and only if ϕ^{−1}x ⊆ a.

A function f : ℕ → ℕ is called combinatorial if it is induced by a combinatorial operator. The fundamental result relating these ideas is the following.

10.3. Theorem. [First part of T4 in [2].] If f : ℕ → ℕ is a function with fn = ∑_{i=0}^{n} c_{i}\binom{n}{i} then: f is combinatorial if and only if c_{i} ≥ 0 for every i ≥ 0.

Proof. An important part of the proof consists of building a combinatorial operator out of the c_{i}’s. This is done using enumerations of ℕ × ℕ and of the set Q of finite subsets of the natural numbers. We will not go into the details.

10.4. Corollary. If f and g are combinatorial functions then so are the functions n ↦ (fn) · (gn) and n ↦ f(gn).

That is, combinatorial functions are closed under product and composition. Corollary 10.4 may be shown without introducing combinatorial operators, but these enable Dekker “to prove these closure conditions without the algebraic complications which arise from substitution involving expressions” of the form ∑_{i=0}^{n} c_{i}\binom{n}{i}. (See Section 7 in [2].)

10.5. Definition. A numerical operator Ψ : Q → Q is dispersive if it maps distinct sets onto disjoint sets, i.e. if α ≠ β implies Ψα ∩ Ψβ = ∅.

For each combinatorial operator Φ : Q → Q, the operator Φ_{0} : Q → Q defined by

Φ_{0}α = (Φα) − ∪{Φγ | γ ⊂ α}

is dispersive. On the other hand, for each dispersive operator Ψ : Q → Q, the operator Φ_{Ψ} : Q → Q defined by Φ_{Ψ}α = ∪{Ψγ | γ ⊆ α} is combinatorial. These constructions form the explicit proof of the following result.

10.6. Theorem. [T3 in [2].] There is a natural one-to-one correspondence between the family of all combinatorial operators and the family of all dispersive operators.

The connection with the coefficients c_{i} in a combinatorial function is the following.

10.7. Corollary. [Second part of T4 in [2].] If fn = ∑_{i=0}^{n} c_{i}\binom{n}{i} is a combinatorial function induced by the combinatorial operator Φ then c_{( )} is induced by Φ_{0}.

Before leaving this brief summary, let us note another important fact, which implies that every combinatorial function is monotone increasing.

10.8. Theorem. [T2 in [2].] For a combinatorial operator Φ, α ⊆ β implies Φα ⊆ Φβ.

10.9. The Schanuel topos as a category of combinatorial operators. The concrete description of free algebras for the factorization monad M = (M, u, m) discussed in Section 10 immediately suggests the connection with combinatorial functions. Instead of numerical operators use objects of Set^{B}. The functor M is analogous to the construction Φ_{( )}, defined immediately before Theorem 10.6, that produces a combinatorial operator out of a dispersive one. But notice that the explicit definition of M needs nothing like a “dispersivity” condition of Definition 10.5. The new ‘elbow room’ provided by working with objects of Set^{B}, instead of numerical operators, allows to avoid the obscurities that inevitably arise when working with enumerations.

Notice that when looked at from this perspective, Theorem 10.8 can be seen as a pale reflection of the fact that combinatorial operators are M-algebras (i.e. functors I → Set). But what is the connection with the definition of combinatorial operator? We understand Definition 10.2 as providing a numerical operator ϕ with an M-algebra structure together with a section for its canonical presentation. In this way, Theorem 10.6 and Corollary 10.7 are approximations to the fact that M is EB. The construction of the canonical restriction of a section s : A → MA is analogous to the construction Φ ↦ Φ_{0} which produces a dispersive operator out of a combinatorial one. As evidence to support this analogy, consider the following examples suggested by those treated in [2]. Example (A) in Section 6 of [2] shows that the function n ↦ n! is combinatorial.

10.10. Example. Let 𝔊 in Set^{B} be the object that assigns to each finite set U, the set of permutations on U. There is an algebra structure a : M𝔊 → 𝔊 which, at stage U, takes a subset V of U together with a permutation π on V and produces the permutation on U which is the extension of π by leaving the elements in U/V fixed. Now consider the morphism s : 𝔊 → M𝔊 which, at stage U, takes a permutation π of U and produces the subset V of U given by the elements of U that are not fixed by π, together with the restriction of π to V. It is easy to check that s is a morphism of algebras and that it is a section of a. It follows that 𝔊 is a free M-algebra. The canonical restriction \overline{s} : 𝔊_{s} → 𝔊 coincides with the object of derangements, that is, the fixpoint-free permutations. The numerical reflection of this is that n! = ∑_{i=0}^{n} d_{i}\binom{n}{i} where d_{i} is the number of derangements on a set of cardinality i.

Example (B) in Section 6 of [2] shows that, for any t ∈ ℕ, the function n ↦ n^{t} is combinatorial.

10.11. Example. Fix a set T and consider the object ( )^{T} in Set^{B} such that U^{T} is the set of functions of T → U. There is an algebra structure a : M(( )^{T}) → ( )^{T} such that for every finite U, a : ∑_{V ⊆U} V^{T} → U^{T} simply post-composes with the inclusion V ⊆ U. On the other hand, there is a morphism s : ( )^{T} → M(( )^{T}) such that s_{U} : U^{T} → ∑_{V ⊆U} V^{T} assigns to a function f its surjection-inclusion factorization. The equalizer of s and u is given by surjections. So ( )^{T} is the free M-algebra generated by the object of surjections T → ( ). At the numerical level, this says that n^{♯T} = ∑_{i=0}^{n} su(i, ♯T)\binom{n}{i}.

Example (A) in Section 7 of [2] shows that combinatorial operators are closed under product. The reader is invited to prove this by showing that for every X and Y in Set^{B}, MX × MY is free. A section s : MX × MY → M(MX × MY) for the canonical presentation of the M-algebra MX × MY does all the work.

Example (B) in Section 7 of [2] shows that combinatorial operators are closed under composition. Again, the reader is invited to prove this using the Explicit Basis property.

11. Möbius inversion

We assume familiarity of [10]. Let C be a Möbius category in the sense of Leroux. If we let C_{1} be the set of maps of C, we denote the incidence category of C by (Cat(C_{1}, Set_{f}), ∗, δ). The category Cat(C_{1}, Set_{f}) is extensive, has a terminal object ζ and distinguished objects Φ_{+} and Φ_{−}. One of the main results loc. cit. presents an explicit isomorphism δ + ζ ∗ Φ_{−} → ζ ∗ Φ_{+}. This iso is the main combinatorial ingredient to prove the general Möbius inversion principle in incidence algebras. We sketch an alternative proof.

The object Φ_{+} is equipped with a monoid structure which induces a monad Ev on the functor ( ) ∗ Φ_{+} : Cat(C_{1}, Set_{f}) → Cat(C_{1}, Set_{f}).

11.1. Corollary. The monad Ev on Cat(C_{1}, Set_{f}) is EB.

Proof. Use Proposition 4.7. The concrete details are very similar to those in Section 5.

To exhibit the explicit iso δ + ζ ∗ Φ_{−} → ζ ∗ Φ_{+}, first equip the object δ + ζ ∗ Φ_{−} with an Ev-algebra structure. Then find a section s : δ + ζ ∗ Φ_{−} → Ev(δ + ζ ∗ Φ_{−}) for its canonical presentation. Finally, show that the canonical restriction of s is a subobject ζ → δ + ζ ∗ Φ_{−}. Corollary 11.1 implies that the induced map

ζ ∗ Φ_{+} = Evζ → Ev(δ + ζ ∗ Φ_{−}) → δ + ζ ∗ Φ_{−}

is an isomorphism.

12. Combinatorics and the Explicit Basis property

Consider a ‘combinatorial’ construction given by a monad M = (M, u, m) on a category D and an object A whose elements/figures we need to count. By a solution for this counting problem we mean the exhibition of an object C together with an isomorphism MC → A. This information explains the number of figures of A in terms of the ‘simpler’ C and the construction M.

Put differently, a solution to a counting problem as posed above says that A is the underlying object of a free M-algebra. So, given such a ‘combinatorial’ monad, a good understanding of free M-algebras (or better yet, of the whole Kleisli category Kl_{M}) would help to solve combinatorial problems.

For example, consider the Schanuel topos and the examples in Section 10.9. Let (A, a : MA → A) be an M-algebra and let a_{n} = A{1, …, n}. If we show that (A, a) is iso to a free algebra then we can conclude that there is a sequence of coefficients {b_{i}}_{i∈ℕ} such that a_{n} = ∑_{i=0}^{n} b_{i}\binom{n}{i}.

If M satisfies the Explicit Basis property then, to find a solution for the counting problem for A, it is enough to find an M-algebra structure (A, a) on A and a section s for its canonical presentation. Then \overline{s} : A_{s} → A is a basis. So A_{s}, together with the iso a(M\overline{s}) : MA_{s} → A, solves the counting problem.

Why should an algebra structure and a section for its canonical presentation be easier to find than an explicit iso MC → A? We do not have a precise answer to this question. In practice, the algebra structure comes up very naturally as an ‘obvious’ way of combining elements of A. The section A → MA then arises as an operation which, given an element x of A, produces the ‘deconstruction’ of x in terms of its simplest components. The canonical restriction \overline{s} : A_{s} → A is the subobject of ‘simplest’ elements of A. The Exponential principle of Corollary 8.2, the examples with combinatorial functions in Section 10.9 and the Möbius inversion example in Section 11 are clear instances of this type of argument. In practice, we have found that the section is more difficult to identify than the algebra structure. But, under certain hypotheses, the section is not only just a ‘natural’ operation but is actually unique (see Section 14).

Of course, we do not mean to suggest that the Explicit Basis property is a substitute for a more explicit understanding of particular Kleisli categories. For example, the characterization of free compact convex sets as Choquet simplexes is used in [16] regardless of the fact that the monad determined by cConv → cHaus is EB. As another example, the description of the Schanuel topos as the category of pullback preserving functors I → Set allows a simple proof that combinatorial functions are closed under product and composition. Indeed, if F, G : I → Set preserve pullbacks then so does F × G. Also, if G is valued on finite sets then, clearly, U ↦ F (GU) also preserves pullbacks. (The extraction of ‘generators’, though, would require some extra analysis.) Finally, see [11] for an alternative proof of Corollary 8.2 using a more explicit description of E-algebras.

13. Conservative EB monads

All our examples of EB monads, except E : Joy → Joy, share the property that their underlying functors are conservative (i. e. faithful and iso-reflecting). In this section we explain this phenomenon in terms of a condition on canonical restrictions. Let M = (M, u, m) be a monad on a category D.

The canonical presentation m : (MMA, m_{M}) → (MA, m) of the free algebra (MA, m) has a distinguished section Mu : (MA, m) → (MMA, m_{M}). Assume that its canonical restriction \overline{Mu} : (MA)_{(Mu)} → MA exists. Naturality implies that u : A → MA factors through \overline{Mu} : (MA)_{(Mu)} → MA as in the diagram on the left below

\xymatrix{A \ar[dr]_{u} \ar@{.>}[r] & (MA)_{(Mu)} \ar[d]^{\overline{Mu}} & A \ar[r]^{u} & MA \ar[r]^{u_{M}} \ar[r]_{Mu} & MMA \\  & MA}

This factorization is an iso (for every A) if and only if the commutative diagram on the right above is an equalizer for every A. The so-called equalizer condition has received considerable attention. In particular, by computer scientists following the work of Moggi. The next result may be folklore, but I have not found it in the literature.

13.1. Lemma. If the equalizer condition holds then M is conservative.

Proof. That M is faithful follows from the fact that u is (a natural) mono. To check that M reflects isos, assume that for f : A → B, Mf : MA → MB is an iso, say, with inverse j : MB → MA. Since u is a natural mono, f is clearly mono. The following diagram

\xymatrix{B \ar[r]^{u} & MB \ar[dr]_{id} \ar[r]^{j} & MA \ar[d]_{Mf} \ar[r]_{Mu} \ar[r]^{u_{M}} & MMA \ar[d]^{MMf} \\  &  & MB \ar[r]_{Mu} \ar[r]^{u_{M}} & MMB}

shows that

(MMf)u_{MA}ju_{B} = u_{MB}u_{B} = (Mu_{B})u_{B} = (MMf)(Mu_{A})ju_{B}

and, as MMf is an iso, we can conclude that u_{MA}ju_{B} = (Mu_{A})ju_{B}. Since the equalizer condition holds, there exists a unique i : B → A such that the diagram on the left below

\xymatrix{B \ar@{.>}[d]_{i} \ar[r]^{u} & MB \ar[d]^{j} &  & B \ar[d]_{u} \ar[r]^{i} & A \ar[d]^{u} \ar[r]^{f} & B \ar[d]^{u} \\ A \ar[r]_{u} & MA \ar[r]_{Mu} \ar[r]^{u_{M}} & MMA & MB \ar[rr]_{id} \ar[r]^{j} & MA \ar[r]^{Mf} & MB}

commutes. That is, u_{A}i = ju_{B}. The diagram on the right above shows that u_{B}fi = u_{B} and, as u is mono, that fi = id. So f is split epi. Since it is also mono, it is an iso.

Lemma 13.1 can be turned into a characterization as follows.

13.2. Proposition. M satisfies the equalizer condition if and only if the following hold:

1. M reflects isos and

2. the canonical restriction (MA)_{(Mu)} → MA exists and is independent for every A.

Moreover, in the case these hold, M is conservative.

Proof. To ease the notation we denote \overline{Mu} : (MA)_{(Mu)} → MA by α : A_{0} → MA. By Proposition 2.11, the independence condition is equivalent to Mα mono. First assume that the equalizer condition holds. Then α = u and so, Mα = Mu which is (split)mono. Lemma 13.1 implies that M is conservative. Conversely, assume that Mα is mono and that M reflects isos. As u_{M}u = (Mu)u, there exists a unique map j : A → A_{0} such that αj = u : A → MA. We must prove that j is an iso. As M reflects isos it is enough to show that Mj is an iso. We immediately have that (Mα)(Mj) = Mu and then Mj is mono. We now prove that Mj : MA → MA_{0} is split-epi. The following diagram

\xymatrix{MA_{0} \ar[r]^{Mα} & MMA \ar[d]_{Mu} \ar[d]^{MMu} \ar[r]^{m} & MA \ar[dr]_{Mu} \ar[r]^{Mj} & MA_{0} \ar[d]^{Mα} \\  & MMMA \ar[rr]_{m} &  & MMA}

shows that (Mα)(Mj)m(Mα) = m_{M}(Mu_{M})(Mα) = Mα. As Mα is a monomorphism, (Mj)m(Mα) = id. That is, Mj is split-epi.

If M is EB, the second item of Proposition 13.2 holds.

13.3. Corollary. If M is EB then it satisfies the equalizer condition if and only if M reflects isos. Moreover, if this is the case, M is conservative.

The same argument used in Lemma 3.1 shows that, over a balanced category, M is conservative if and only if the unit of M is mono. This fact can be used to verify that M is conservative in most of our examples.

14. The subobject of extreme elements

This section is analogous to the previous one. It provides an explanation of why, in most of our examples, each canonical presentation has at most one section. Let M = (M, u, m) be a monad on a Heyting category D.

14.1. Definition. The subobject of extreme elements associated with an M-algebra (A, a) is the subobject of A given by

{x ∈ A | (∀v ∈ MA)(av = x ⇒ v = ux)} → A

We denote this subobject by a_{⋆} : ⌊A, a⌋ → A.

(To avoid a possible confusion we stress that, although the arguments used in this section are similar to those in Section 3, the subset of extreme points of a compact convex set is not a particular case of Definition 14.1. For K in cConv, the subset ∂_{e}K → K coincides, by Lemma 3.2, with {x ∈ UK | (∀v ∈ U(PK))(av = x ⇒ v = ux)} → UK where U : cHaus → Set is the underlying set functor. So it is an instance of a generalization of Definition 14.1 involving a monad M on a category D equipped with functor U : D → H to Heyting category H.)

We say that M has extreme unit if u_{A} : A → MA factors through ⌊MA, m⌋ → MA for every A. Most of our examples have extreme unit.

14.2. Proposition. If M is EB and has extreme unit then every canonical presentation has at most one section. Moreover, if s : (A, a) → (MA, m) is such a section then the canonical restriction \overline{s} : A_{s} → A coincides with a_{⋆} : ⌊A, a⌋ → A.

In order to prove Proposition 14.2 we need an external characterization of the maps X → A that factor through ⌊A, a⌋ → A. The interpretation of “av = x” is the equalizer ⟨id, a⟩ : MA → MA × A of the pair of maps aπ_{0}, π_{1} : MA × A → A. Similarly, the interpretation of “v = ux” is the equalizer ⟨u, id⟩ : A → MA × A of π_{0}, uπ_{1} : MA × A → MA. So the subobject a_{⋆} : ⌊A, a⌋ → A equals ∀_{π_{1}}(⟨id, a⟩ ⇒ ⟨u, id⟩) where π_{1}^{∗} ⊣ ∀_{π_{1}}.

14.3. Lemma. A morphism f : X → A factors through a_{⋆} : ⌊A, a⌋ → A if and only if the following diagram

\xymatrix{X \ar[d]_{id} \ar[r]^{f} & A \ar[r]^{u} & MA \ar[d]^{a} \\ X \ar[rr]_{f} &  & A}

is a pullback.

Proof. The map f : X → A factors through ∀_{π_{1}}(⟨id, a⟩ ⇒ ⟨u, id⟩) → A if and only if id × f : MA × X → MA × A factors through (⟨id, a⟩ ⇒ ⟨u, id⟩) → MA × A. In turn, this holds if and only if for every diagram as on the left below

\xymatrix{V \ar[d]_{⟨v_{0},v_{1}⟩} \ar[r] & MA \ar[d]^{⟨id,a⟩} & V \ar[d]_{⟨v_{0},v_{1}⟩} \ar[r] & A \ar[d]^{⟨u,id⟩} \\ MA × X \ar[r]_{id×f} & MA × A & MA × A \ar[r]_{id×f} & MA × A}

there exists a map V → A making the diagram on the right above commute. This is equivalent to the fact that commutativity of the diagram on the left below

\xymatrix{V \ar[d]_{v_{1}} \ar[r]^{v_{0}} & MA \ar[d]^{a} & X \ar[r]^{f} & A \ar[d]^{u} \\ X \ar[r]_{f} & A & V \ar[u]^{v_{1}} \ar[r]_{v_{0}} & MA}

implies commutativity of the diagram on the right above. In turn, this is equivalent to the fact that the diagram in the statement is a pullback.

The basic relation between extreme elements and canonical restrictions is the following.

14.4. Lemma. For any algebra (A, a) and any section s : (A, a) → (MA, m) of the canonical presentation of (A, a), the subobject a_{⋆} : ⌊A, a⌋ → A factors through the canonical restriction \overline{s} : A_{s} → A.

Proof. The diagram on the left below

\xymatrix{⌊A, a⌋ \ar[d]_{id} \ar[r]^{a_{⋆}} & A \ar[r]^{u} & MA \ar[d]^{a} & ⌊A, a⌋ \ar[d]_{id} \ar[r]^{a_{⋆}} & A \ar[r]^{s} & MA \ar[d]^{a} \\ ⌊A, a⌋ \ar[rr]_{a_{⋆}} &  & A & ⌊A, a⌋ \ar[rr]_{a_{⋆}} &  & A}

is a pullback by Lemma 14.3. The diagram on the right above commutes because s is a section of a. The universal property of the pullback on the left implies that the fork

\xymatrix{⌊A, a⌋ \ar[r]^{a_{⋆}} & A \ar[r]^{u} \ar[r]_{s} & MA}

commutes. This implies that a_{⋆} : ⌊A, a⌋ → A factors through \overline{s} : A_{s} → A.

Alternatively, we could have argued informally in the internal logic as follows. Since s is a section of a, x = a(sx) for every x in A. So, if x is in the subobject of extreme elements, ux = sx. That is, x ∈ ⌊A, s⌋ implies x ∈ A_{s}.

14.5. Lemma. Assume that u : A → MA is extreme and let (A, a) be an algebra. If s : (A, a) → (MA, m) is a section for the canonical presentation of (A, a) then the factorization ⌊A, a⌋ → A_{s} of Lemma 14.4 is an isomorphism.

Proof. To show that the factorization ⌊A, a⌋ → A_{s} is an iso, it is enough to show that \overline{s} : A_{s} → A factors through a_{⋆} : ⌊A, a⌋ → A. That is, by Lemma 14.3, that the diagram on the left below

\xymatrix{A_{s} \ar[d]_{id} \ar[r]^{\overline{s}} & A \ar[r]^{u} & MA \ar[d]^{a} & A_{s} \ar[d]_{id} \ar[r]^{\overline{s}} & A \ar[r]^{u} & MA \ar[d]^{a} \ar[r]^{Ms} & MMA \ar[d]^{m} \\ A_{s} \ar[rr]_{\overline{s}} &  & A & A_{s} \ar[rr]_{\overline{s}} &  & A \ar[r]_{s} & MA}

is a pullback. As s is a split mono, it is enough to prove that the extended diagram on the right above is a pullback. Applying naturality of u and the equality s\overline{s} = u\overline{s}, our present task reduces to prove that the diagram below

\xymatrix{A_{s} \ar[d]_{id} \ar[r]^{\overline{s}} & A \ar[d]^{id} \ar[r]^{u} & MA \ar[r]^{u_{M}} & MMA \ar[d]^{m} \\ A_{s} \ar[r]_{\overline{s}} & A \ar[rr]_{u} &  & MA}

is a pullback. But the square on the left is a pullback trivially and the rectangle on the right is a pullback because u is extreme (by hypothesis). So the pasting lemma implies that the subobjects ⌊A, a⌋ → A and A_{s} → A coincide.

We can now prove the main result of the section.

Proof of Proposition 14.2. Let (A, a) be an algebra and let s, t : (A, a) → (MA, m) be sections for the canonical presentation of (A, a). Lemma 14.5 implies that the subobjects A_{s} → A and A_{t} → A coincide with ⌊A, a⌋ → A. So s = t by Corollary 3.6.

A variation of the argument used in Proposition 3.4 can be used in the present context.

14.6. Proposition. Let M have extreme unit and M preserve monos. Then M is EB if and only if idempotents split in Kl_{M}.

Proof. If M is EB, idempotents split in Kl_{M} by Proposition 2.5. So consider the converse. As M preserves monos, it is enough to show that canonical restrictions are spanning (Corollary 2.12). Let s : (A, a) → (MA, m) be a section for the canonical presentation of (A, a). Since idempotents split in Kl_{M} by hypothesis, (A, a) ≅ (MB, m) for some B, and we can assume that s : (MB, m) → (MMB, m_{M}) is a section of the canonical presentation of (MB, m). As the unit is extreme, Lemma 14.5 implies that the canonical restriction (MB)_{s} → MB of s coincides with ⌊MB, m⌋ → MB. But ⌊MB, m⌋ → MB is spanning because the unit is extreme. So (MB)_{s} → MB is spanning.

14.7. Examples of subobjects of extreme elements. Without awareness of the characterization of extreme points of compact convex sets (and using different terminology), subobjects of extreme elements in the sense of Definition 14.1 were defined in [11] for the monads E discussed in Section 8. In this context, the assignment (A, a) ↦ ⌊A, a⌋ behaves like a ‘logarithm’. (See Section 2.6 loc. cit.)

Let D be an extensive Heyting category and consider the monad induced by the algebraic functor D/D → D where D is a fixed object of D. We use the notation in Proposition 2.7 to state and prove the next result.

14.8. Lemma. For any algebra (A, a : D → A) the following hold:

1. a_{⋆} : ⌊A, a⌋ → A coincides with the subobject ¬(∃_{a}D) → A,

2. a_{⋆} : ⌊A, a⌋ → A is spanning if and only if ∃_{a}D → A is complemented and

3. a_{⋆} : ⌊A, a⌋ → A is independent if and only if a is mono.

Proof. Let f : X → A be a map in D. By Lemma 14.3, f factors through a_{⋆} : ⌊A, a⌋ → A if and only if the diagram on the left below

\xymatrix{X \ar[d]_{id} \ar[r]^{f} & A \ar[r]^{in_{1}} & D + A \ar[d]^{[a,id]} & 0 \ar[d] \ar[r] & D \ar[d]^{a} \\ X \ar[rr]_{f} &  & A & X \ar[r]_{f} & A}

is a pullback. Since D is extensive this is equivalent to the square on the right above being a pullback. In turn, this holds if and only if f factors through ¬(∃_{a}D) → A. To prove the second item notice that the following diagram

\xymatrix{D + ¬(∃_{a}D) \ar[r] & D + A \ar[r]^{[a,id]} & A}

is a regular epi if and only if the subobject ∃_{a}D ∨ ¬(∃_{a}D) → A is an iso. For the third item, observe that the same diagram is mono if and only if a is mono.

In particular, notice that the unit is extreme. But moreover, for each A in D, the subobject of extreme elements of the free algebra (D + A, in_{1}) coincides with the unit.

Consider now a functor f : A → X between small categories inducing an essential surjection f : Â → X̂ as in Section 9.

14.9. Lemma. Let T be a presheaf on X. An element x ∈ (f^{∗}T)A is extreme if and only if for every v : V → A in A, b : V → B in X and y ∈ T B, y · b = x · v implies y ⊗b = (y · b) ⊗id.

Proof. The element x : A( , A) → f^{∗}T is extreme if and only if the following diagram

\xymatrix{A( , A) \ar[d]_{id} \ar[r]^{x} & f^{∗}T \ar[r]^{u} & M(f^{∗}T) \ar[d]^{·} \\ A( , A) \ar[rr]_{x} &  & f^{∗}T}

is a pullback. That is, for every v : V → A in A and y ⊗b ∈ (M(f^{∗}T))V with b : V → B in X and y ∈ T B, y · b = x · v implies y ⊗b = (x · v) ⊗id.

Applying Lemma 14.9 to the essential surjection induced by an inclusion ι : C_{0} → C as in Section 6, we obtain that x ∈ (ι^{∗}T)A is extreme if and only if for every b : A → B in C and y ∈ T B, y · b = x implies B = A and b = id.

On the other hand, for the factorization monad on M̂ induced by an inclusion M → C as in Section 9.1, x ∈ (ι^{∗}T)A is extreme if and only if for every m : V → A in M, b : V → B in E and y ∈ T B, y · b = x · v implies b is an iso. So, for factorization monads, extreme elements are closely related to the E-minimal elements used in [3] to prove that free algebras for certain factorization monads are pullback preserving functors.

Acknowledgments

Lawvere informed me of the connection between the Schanuel topos and Myhill’s combinatorial functions in 2004. More recently, he suggested the example of convex sets, the example of categories over graphs and the consideration of essential surjections. He also suggested many conceptual improvements which allowed to clarify and extend results in a preliminary version of the paper. G. Janelidze quickly provided the first examples and non-examples of EB monads over Set. The referee pointed out two important generalizations of results in the original submission (Proposition 2.9 and Corollary 6.4 in the final version). I would also like to thank A. Carboni, J. Carette, S. Schanuel, C. Smith and the Library of the Institute of Mathematics of the Polish Academy of Sciences.

References

[1] M. Barr and R. Diaconescu. Atomic toposes. Journal of Pure and Applied Algebra, 17:1–24, 1980.

[2] J. C. E. Dekker. Myhill’s theory of combinatorial functions. Modern Logic, 1(1):3–21, 1990.

[3] M. Fiore and M. Menni. Reflective Kleisli subcategories of the category of Eilenberg-Moore algebras for factorization monads. Theory and Applications of Categories, 15(18):40–65, 2005. A special volume of articles from the CT2004 Conference.

[4] P. T. Johnstone. Stone spaces. Cambridge University Press, 1982.

[5] P. T. Johnstone. Sketches of an elephant: a topos theory compendium, volume 43-44 of Oxford Logic Guides. The Clarendon Press Oxford University Press, New York, 2002.

[6] A. Joyal. Une théorie combinatoire des séries formelles. Advances in mathematics, 42:1–82, 1981.

[7] F. W. Lawvere. Qualitative distinctions between some toposes of generalized graphs. Contemporary mathematics, 92:261–299, 1989. Proceedings of the AMS Boulder 1987 Symposium on categories in computer science and logic.

[8] F. W. Lawvere. Unity and identity of opposites in calculus and physics. Applied categorical structures, 4:167–174, 1996.

[9] F. W. Lawvere. Functorial semantics of algebraic theories and some algebraic problems in the context of functorial semantics of algebraic theories. Repr. Theory Appl. Categ., 2004(5):1–121, 2004.

[10] F. W. Lawvere and M. Menni. The Hopf algebra of Möbius intervals. Submitted for publication, 2009.

[11] M. Menni. Symmetric monoidal completions and the exponential principle among labeled combinatorial structures. Theory and applications of categories, 11:397–419, 2003.

[12] M. Menni. Cocomplete toposes whose exact completions are toposes. Journal of Pure and Applied Algebra, 210:511–520, 2007.

[13] R. Rosebrugh and R. J. Wood. Split structures. Theory Appl. Categ., 13:No. 12, 172–183, 2004.

[14] S. H. Schanuel. Negative sets have Euler characteristic and dimension. Category theory, Proc. Int. Conf., Como/Italy 1990, Lect. Notes Math. 1488, 379-385 (1991).

[15] Z. Semadeni. Free compact convex sets. Bulletin de l’Academie Polonaise des Sciences, XIII(2), 1965.

[16] Z. Semadeni. Banach spaces of continuous functions, volume 55 of Monografie Matematyczne. PWN - Polish Scientific Publishers, 1971.

[17] T. Świrszcz. Monadic functors and convexity. Bulletin de l’Académie Polonaise des Sciences, XXII(1):39–42, 1974.

C. C. 11 (1900) La Plata Argentina

Email: matias.menni@gmail.com

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

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

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

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

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

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

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc.: valeria@cuill.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Tom Leinster, University of Glasgow, T.Leinster@maths.gla.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca