<<

. 57
( 60 .)



>>

d
dc

T
commutes.
The concept of free triple on R is clearly analogous to the concept of free
monoid on a set, with composition of functors playing the role of Cartesian prod-
uct of sets. In one special situation, we can construct the free triple on R in
very much the same way as for the free monoid. If C has countable sums and R
preserves them, let T = id + R + R —¦ R + R —¦ R —¦ R + · · ·. Then T —¦ T ∼ T , and
=
with the identity map and the obvious map onto the ¬rst summand serving as µ
and · respectively, one obtains a triple which is easily seen to be the free triple
generated by R. (See Exercise 1).
To get a more general construction, we form the category which will be C T .
Let (R: C ) denote the category whose objects are pairs (C, f ) where C is an
object of C and f : RC ’ C. A morphism f : (A, a) ’ (A , a ) in (R: C ) is an
’ ’
arrow f : A ’ A for which

RfE
RA RA

Uf
c c
EA
A
commutes. This is a (non-full) subcategory of the comma category (R, C ). If R
should happen to be the functor part of a triple, then the category of algebras
for the triple is a full subcategory of (R: C ).
The canonical underlying functor U : (R: C ) ’ C takes (A, a) to A and

f to f .
Proposition 1. The underlying functor U:(R: C ) ’ C satis¬es the condition

of the PTT except possibly for the existence of a left adjoint. Thus if it has a left
adjoint, it is tripleable.
Proof. It is clear that U re¬‚ects isomorphisms. If
d0
(A, a) ’ ’ (B, b)
’’
’’
’’
d1
9.4 Free Triples 311
lies over a contractible coequalizer

’’ ’d
A ’’ B ←’ C
’’
←’ ’
s t
then c = d —¦ b —¦ Rt is a structure on C for which d is a morphism in (R: C ) which
is the required coequalizer.
Proposition 2. Let R: C ’ C be a functor and T = (T, ·, µ) a triple on

C . Then there is a one to one correspondence between natural transformations
from R to T and functors ¦: C T ’ (R: C ) which commute with the underlying

functors.
Proof. Given a natural transformation ±: R ’ T , de¬ne ¦ to take an algebra

(A, a: T A ’ A) to (A, a —¦ ±A), and a morphism to itself. It is easy to see that

this gives a functor.
Going the other way, let ¦ be given. Since (T A, µA) is a T-algebra, ¦(T A, µA) =
(T A, φA) for some arrow φA: RT A ’ T A. Now given f : A ’ B, T f : (T A, µA)
’ ’
’ (T B, µB) is a morphism between (free) algebras, so ¦T f = T f : (T A, φA)

’ (T B, φB) must be a morphism in (R: C ). It is immediate from the de¬nition

that this is the same as saying that φ: RT ’ T is a natural transformation,

whence so is ± = φ —¦ R·: R ’ T .

We must show that this construction is inverse to the one in the preceding
paragraph. For this we need
Lemma 3. Any functor ¦: C T ’ (R: C ) which commutes with the underlying

functors preserves the coequalizers of U T -contractible coequalizer pairs.
Proof. Such a functor clearly takes a U T -contractible coequalizer pair to a U -
contractible coequalizer pair, where U : (R: C ) ’ C is the canonical underlying

functor. Then by Proposition 1 and the fact that U T is tripleable, ¦ must preserve
the coequalizer.
Now suppose that ¦ is given, ± is constructed as above, and ¦ is constructed
from ±. We must show that ¦ and ¦ agree on T-algebras; to do this, we use the
standard technique of showing they agree on free algebras, so that by Lemma 3
they must agree on coequalizers of U -contractible diagrams of free algebras; but
those are all the algebras by Proposition 4 of Section 3.3.
A free algebra has the form (T A, µA), and µ: (T 2 A, µT A) ’ (T A, µA) is a

2
T-algebra morphism. Thus µ: (T A, φT A) ’ (T A, φA) is a morphism in (R: C ),

whence φ —¦ Rµ = µ —¦ φT . Then
¦ (T A, µA) = (T A, µA —¦ ±T A) = (T A, µA —¦ φT A —¦ R·T A)
= (T A, φA —¦ RµA —¦ R·T A) = (T A, φA) = ¦(T A, µA)
312 9 More on Triples
Thus ¦ and ¦ agree on free algebras, and so since both U T and U preserve
coequalizers, ¦ and ¦ must agree on all algebras. (Since both U T and U create
coequalizers of U -contractible coequalizer pairs, ¦ and ¦ do not merely take an
algebra to isomorphic objects of (R: C ), but are actually the same functor.)
Conversely, suppose we start with a natural transformation ±, construct a
functor ¦, and then from ¦ construct a natural transformation ± . As before, let
¦(T A, µA) = (T A, φA). Since by de¬nition ¦(T A, µA) = (T A, µA —¦ ±T A), we
have φ = µ —¦ ±T ). Then

± = φ —¦ R· = µ —¦ ±T —¦ R· = µ —¦ T · —¦ ± = ±


Theorem 4. If U : (R: C ) ’ C has a left adjoint F , then the resulting triple

is the free triple generated by R.
Proof. The comparison functor (R: C ) ’ C T is an equivalence, so its inverse

corresponds via Proposition 2 to a morphism ·: R ’ T . If »: R ’ T is a natural
’ ’
transformation, the composite of the corresponding functor with the comparison
functor yields a functor from C T to C T which by Theorem 3 of Section 3.6
corresponds to natural transformation ±: T ’ T . Since ± —¦ · corresponds to the

same functor from C T to (R: C ) as », they must be equal.
The converse of Theorem 4 is true when C is complete:
Proposition 5. Let C be a complete category and R an endofunctor on C
which generates a free triple T. Then U : (R: C ) ’ C has a left adjoint and the

Eilenberg-Moore category C T is equivalent to (R: C ).
Proof. To construct the left adjoint we need a lemma.
If C is complete, then (R: C ) is complete.
Lemma 6.
Proof. The proof is the same as that of Theorem 1 of Section 3.4, which does not
require the existence of an adjoint.
Now let B be any set of objects of (R: C ). Let B # be the full subcategory
of (R: C ) consisting of all subobjects of products of objects in B. Then the
composite B # ’ (R: C ) ’ C has an adjoint F by the Special Adjoint Functor
’ ’
Theorem, the objects of B being the solution set.
¯
Now form B from B # by adding any object (B, b) for which there is a mor-
phism (B0 , b0 ) ’ (B, b) for which B0 ’ B is a split epi. If a map C ’ B in
’ ’ ’
9.4 Free Triples 313
C is given, it lifts via the splitting to a unique map C ’ B0 for which

EB
C
d  
d  
d  

d  
©
B0
commutes. This lifts to the unique map F C ’ (B0 , b0 ) given by the de¬nition

of left adjoint. Composition with B0 ’ B gives a map F C ’ (B, b), and this se-
’ ’
quence of constructions gives an injection from HomC (C, B) to HomB (F C, (B, b)).
¯
The fact that B0 ’ B is split makes it surjective, so that we have shown that

¯¯’
the underlying functor U : B ’ C has a left adjoint.
If
(B , b ) ’ (B, b)

’’
¯
is a U -contractible coequalizer diagram with both algebras in B, then it has
¯
a coequalizer (B , b ) in (R: C ) which by de¬nition belongs to B. Thus since
U : (R: C ) ’ C satis¬es the requirements of PTT except for having a left adjoint,

¯
and U is a restriction of U to a subcategory which has the requisite coequalizers,
¯
U must be tripleable. Let T = (T , · , µ ) be the resulting triple.
The inclusion C T ’ (R: C ) corresponds to a natural transformation R ’
’ ’
T which by the de¬nition of free triple gives a morphism T ’ T of triples which

makes
ET
R
d  
d  
d  

‚©
T
commute, the top transformation being the one given by the de¬nition of free
triple. By the correspondence between morphisms of triples and morphisms of
triple algebras (Theorem 3 of Section 3.6), this yields the commutative diagram
W V
E E (R: C )
T
CT
B
s
dd  
T
d
d  
d
d  
d
d   (—)
F T d dU T F T UT  U
d
d  
d
d  
d
d  
dd
‚ c
 
©
C
314 9 More on Triples
in which the top row is the inclusion.
¯
Thus every object and every map of B is in the image of C T . Since we began
with any set of objects, it follows that V is surjective on objects and maps.
¯
Now take an object B of (R: C ) and a B contained in (R: C ) as constructed
above which contains B. We have, in the notation of diagram (—),
Hom(V F T C, B) ∼ Hom(V F T C, V W B) ∼ Hom(F T C, W B)
= =
∼ Hom(C, U T B) ∼ Hom(C, U B),
= =
which proves that U has a left adjoint.
The last statement in the proposition then follows from Proposition 1 and
Theorem 4.
Proposition 7. Let C be complete and have ¬nite colimits and colimits of
countable chains. Let R be an endofunctor of C which commutes with colimits of
countable chains. Then R generates a free triple.
Proof. By Theorem 4, we need only construct a left adjoint to U : (R: C ) ’ C .

Let C be an object of C . Form the sequence
T e0 E T e1 E E ···
RC0 RC1 RC2

c1 c2 e3
c c c
E C1 E C2 E C2 E ···
C = C0 e0 e1 e3
in which each square is a pushout and C1 = C0 + RC0 . Let C = colim Cn . Then
RC = colim RCn and there are induced maps e: C ’ C and c : RC ’ C .
’ ’
Lemma 8. For any diagram
B
g
c
EC
A
f
there is an arrow f : C ’ B for which

Rf E
RC RB

b
c
c c
f EB
C
s

<<

. 57
( 60 .)



>>