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

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