<<

. 20
( 60 .)



>>

to F · —¦ F = id, respectively. The associative identity
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

<<

. 20
( 60 .)



>>