U U F FE

UFUFUF UFUF

(3)

UFU F UF

c c

E UF

UFUF

UF

3.1 De¬nition and Examples 101

is U applied to the following diagram, which is then evaluated at F :

F UE

FUFU FU

(4)

FU

c c

E Id

FU

At an object Y , this last diagram has the form

XE

FUX X

FUf f (5)

c c

EY

FUY

Y

(for X = F U Y and f = Y ) which commutes because is natural. (This is an

example of part (a) of Exercise 6 of Section 1.3).

The group triple of example (vi) of course arises from the adjunction of the

underlying set functor and the free group functor. We will see in Section 3.2 that

in fact every triple arises from an adjoint pair (usually many di¬erent ones).

The factorization in the case of the triple for sheaves we began to construct

above is T = RU , where U : Sh(X) ’ Set/|X| has U (F ) = Fx and R: Set/|X|

’

’ Sh(X) is the functor de¬ned previously. Then R is left adjoint to U and

’

produces a triple T = (T, ·, U R).

Cotriples

A cotriple in a category B is a triple in B op . Thus G = (G, , δ) (this is

standard notation) is a cotriple in B if G is an endofunctor of B, and : G ’ id,

’

δ: G ’ G2 are natural transformations satisfying the duals to the diagrams (1)

’

above. (Thus a cotriple is the opposite of a triple, not the dual of a triple. The

dual of a triple”in other words, a triple in Catop ”is a triple.)

Proposition 2. Let U : B ’ C have a left adjoint F : C ’ B with adjunction

’ ’

morphisms ·: id ’ U F and : F U ’ id. Then G = (FU, , F·U) is a cotriple

’ ’

on B.

Proof. This follows from Theorem 1 and the observation that U is left adjoint to

F as functors between B op and C op with unit and counit ·.

102 3 Triples

Exercises 3.1

1. Let P denote the functor from Set to Set which takes a set to its powerset and

a function to its direct image function (Section 1.2). For a set X, let ·X take an

element of X to the singleton containing x, and let µX take a set of subsets of

X (an element of PX) to its union. Show that (P, ·, µ) is a triple in Set. (Hint:

compare Exercise 6 of Section 1.9).

2. Let R be any commutative ring. For each set X, let T X be the set of

polynomials in a ¬nite number of variables with the variables in X and coe¬cients

from R. Show that T is the functor part of a triple (µ is de¬ned to “collect

terms”).

3. An ordered binary rooted tree (OBRT) is a binary rooted tree (assume trees

are ¬nite in this problem) which has an additional linear order structure (referred

to as left/right) on each set of siblings. An X-labeled OBRT (LOBRT/X) is one

together with a function from the set of terminal nodes to X. Show that the

following construction produces a triple in Set: For any set X, T X is the set of

all isomorphism classes of LOBRT/X. If f : X ’ Y , then T f is relabeling along

’

f (take a tree in T X and change the label of each node labeled x to f (x)). ·X

takes x ∈ X to the one-node tree labeled x, and µX takes a tree whose labels are

trees in T X to the tree obtained by attaching to each node the tree whose name

labels that node.

4. Let B be the category of sets with one binary operation (subject to no

conditions) and functions which preserve the binary operation.

(a) Show that the triple of Exercise 3 arises from the underlying set functor

B ’ Set and its left adjoint.

’

(b) Give an explicit description of the cotriple in B induced by the adjoint

functors in (a).

5. Give an explicit description of the cotriple in Grp induced by the underlying

set functor and the free group functor.

6. Let M be a monoid and G = Hom(M, ’): Set ’ Set. If X is a set and f : M

’

’ X, let X(f ) = f (1) and [δX(f )](m)(n) = f (mn) for m, n ∈ M . Show that

’

δ and are natural transformations making (G, , δ) a cotriple in Set.

7. Show that if T is any triple on C and A is an object of C , and there is at

least one mono A ’ T A, then ·A is monic. (Hint: If m is the monic, put T m

’

into a commutative square with · and use a unitary identity.)

3.2 The Kleisli and Eilenberg-Moore Categories 103

8. Prove that ·F as de¬ned in the section on sheaves is monic.

9. Complete the proof that R, de¬ned in the section on sheaves, is a functor.

10. Show that the functors R and U constructed in the section on sheaves have

the properties that R is left adjoint to U and that if F is an R-module in the

category of sheaves of sets over the underlying space, then so is T F .

11. Show that the following three statements about a sheaf F on a topological

space X are equivalent:

(i) Every ¬ber of F is an Abelian group in such a way that the structure

maps (addition, negation and picking out 0) are continuous in the total space of

F.

(ii) For every open U of X, F U is an Abelian group in such way that all the

restriction maps are homomorphisms.

(iii) F is an Abelian group object in the category Sh(X). (See Section 1.7.)

3.2 The Kleisli and Eilenberg-Moore Categories

After Huber proved Theorem 1 of Section 3.1, P. J. Hilton conjectured that

every triple arises from an adjoint pair. The answer was provided more or less

simultaneously, using two distinct constructions, by Eilenberg and Moore [1965]

and by H. Kleisli [1965].

Theorem 1. Let T = (T, ·, µ) be a triple on C . Then there is a category B and

an adjoint pair F : C ’ B, U : B ’ C, such that T = U F , ·: id ’ U F = T is

’ ’ ’

the unit and µ = U F where is the counit of the adjunction.

Proof. Construction 1 (Kleisli). The insight which makes this construction work

is that if a category B and an adjoint pair F : C ’ B , U : B ’ C exist with

’ ’

T = U F , then the full subcategory B of B of objects of the form F A for A an

object of C must, by de¬nition, have the property that

HomB (F A, F B) ∼ HomC (A, U F B) = HomC (A, T B)

=

This is the clue that enables us to de¬ne B in terms of the given data C and T.

The category B will have the same objects as C . For arrows, set HomB (A, B) =

HomC (A, T B). If f : A ’ T B ∈ HomB (A, B) and g: B ’ T C ∈ HomB (B, C),

’ ’

then we let g —¦ f ∈ HomB (A, C) be the composite

f Tg µC

A ’ ’ T B ’ ’ T 2C ’ ’ ’ T C

’ ’’ ’’

104 3 Triples

The identity arrow on an object A is ·A. It is an elementary exercise, using the

associative and unitary identities (and naturality) to see that these de¬nitions

make B a category.

The functor U : B ’ C is de¬ned by U A = T A; if f : A ’ B ∈ HomB (A, B),

’ ’

then U f is de¬ned to be

Tf µB

’’ T 2 B ’ ’ ’ T B

T A ’’ ’’

F is de¬ned by F A = A; if f : A ’ B ∈ HomC (A, B), F f is the composite

’

·A Tf

A ’ ’ T A ’’

’’ ’’ T B

which is the same as

f ·B

A ’ ’ B ’’

’ ’’ T B

The required equivalence HomC (A, U B) ∼ HomB (F A, B) is the same as HomC (A, T B) ∼

= =

HomB (A, B), which is true by de¬nition. The rest is left as an exercise.

Observe that Kleisli™s category is in some sense as small as it could be be-

cause it makes F surjective on objects. This observation can be made precise

(Proposition 2 below and Exercise 5).

The Kleisli category is denoted K (T).

Construction 2 (Eilenberg-Moore). The category constructed by Eilenberg

and Moore is in e¬ect all the possible quotients of objects in Kleisli™s category.

Of course, we have to say this using only the given ingredients, so the de¬nition

is in terms of a map a: T A ’ A which is to be thought of as underlying the

’

quotient map:

A T-algebra is a pair (A, a) where A is an object of C and a: T A ’ A an

’

arrow of C subject to the condition that these two diagrams commute:

·AE T aE

T 2A

A TA TA

d

(1)

idAd a a

µA

d

‚

dc c c

EA

A TA a

The arrow a is the structure map of the algebra.

3.2 The Kleisli and Eilenberg-Moore Categories 105

A map f : (A, a) ’ (B, b) of B is a map f : A ’ B of C for which

’ ’

TfE

TA TB

a (2)

b

c c

EB

A

f

commutes.

The category of T-algebras and T-algebra maps is denoted C T . De¬ne U T : C T

’ C by U T (A, a) = A and U T f = f , and F T : C ’ C T by F T A = (T A, µA),

’ ’

F T f = T f . Most of the proof that this produces a pair of adjoint functors

for which the conditions of the theorem hold is straightforward. The required

adjunction

±: HomC T ((U F C, µC), (C , c )) ’ HomC (C, C )

’

takes a morphism h: U F C ’ C of algebras to h —¦ ·C and its inverse takes g: C

’

’ C to c —¦ U F g .

’

It is worthwhile to examine the de¬nition when T is the group triple. Here, a

is a set map from the underlying set of the free group on A to A. The de¬nition

xy = a([xy]), where x and y are elements of A, so that [xy] is an element of

T A, gives a multiplication on A which in fact makes A a group”this follows

with some diagram-chasing from the diagrams in (1) (Exercise 3). The identity

element is a([ ]). Observe that associativity does not follow from the right hand

diagram in (1): associativity is built into the de¬nition of T A as consisting of

strings of elements. The right diagram in (1) says that if you take a string

of free-group elements, in other words a string of strings, then you can either

multiply each string out using the multiplication of the group A, then multiply

the resulting elements together, or you can ¬rst erase parentheses, making one

long string, and then multiply it out”either way gives you the same result.

In other words, substitution commutes with evaluation, which is the essence of

algebraic manipulation.

Conversely, in the case of the group triple, every group can be represented as

an algebra for the triple: For a group G, use the quotient map U F G ’ G which

’

takes a string to its product in G.

As suggested by the discussion in the proof of the theorem, we have a sim-

ple description of the Kleisli category. In this proposition we use the common

convention of describing as an embedding any functor which is faithful and takes

non-isomorphic objects to non-isomorphic objects (a much stronger condition

than merely re¬‚ecting isomorphisms; the underlying functor from groups to sets

106 3 Triples

re¬‚ects isomorphisms without having that property). This convention exempli¬es

the categorical imperative that the actual identity of the objects is irrelevant.

K (T) is embedded in C T as the full subcategory generated by

Proposition 2.

the image of F .

Proof. The embedding is ¦: K (T) ’ C T de¬ned by ¦(A) = (T A, µA), and for

’

f : A ’ T B, ¦(f ) is the composite

’

Tf µB

’’ T 2 B ’ ’ ’ T B

T A ’’ ’’

The Eilenberg-Moore comparison functor