assume that U (x) = c. Finally, (e) we show that x is also the coequalizer of

(d0 , d1 ). It follows easily from the fact that U re¬‚ects isomorphisms that U takes

this coequalizer to an arrow isomorphic to c, as required.

(a) It follows from the identities for a contractible coequalizer that c coequal-

izes U d0 —¦ U p0 and U d0 —¦ U p1 . Let w be the unique map (by virtue of (q 0 , q 1 ) being

the kernel pair of c) for which q 0 —¦ w = U d0 —¦ U p0 and q 1 —¦ w = U d0 —¦ U p1 .

(b) To see that w is a split epi (surjective on elements), suppose that (b0 , b1 ) ∈U B—U B

C ; then s —¦ c —¦ b0 = s —¦ c —¦ b1 , so U d1 —¦ t —¦ b0 = U d1 —¦ t —¦ b1 , which means that

(t —¦ b0 , t —¦ b1 ) ∈ U R (U p0 and U p1 are the kernel pair of U d1 ). We claim that

w(t —¦ b0 , t —¦ b1 ) = (b0 , b1 ). The ¬rst coordinate is

q 0 —¦ w(t —¦ b0 , t —¦ b1 ) = U d0 —¦ U p0 (t —¦ b0 , t —¦ b1 ) = U d0 —¦ t —¦ b0 = b0

and similarly the second coordinate is b1 , as required. Hence w is a split epi.

(c) Since e0 and e1 form the separator of d0 —¦ p0 and d0 —¦ p1 and U preserves

limits, U e0 and U e1 are the separator of U d0 —¦ U p0 and U d0 —¦ U p1 . It is straight-

forward to calculate, using the fact that q 0 and q 1 are jointly monic, that the

kernel pair of w is the intersection of the kernel pairs of U d0 —¦ U p0 and U d0 —¦ U p1 .

Hence U e0 and U e1 are the kernel pair of w.

(d) Because e0 and e1 form the kernel pair of d0 —¦ p0 and d0 —¦ p1 , they coequalize

e0 and e1 , so for i = 0, 1 there are induced maps ui for which ui —¦ v = d0 —¦ pi . Then

q i —¦ w = U (d0 —¦ pi ) = U (ui ) —¦ U (v) = U (ui ) —¦ w

so because w is epi, U (ui ) = q i .

To complete the proof, we must show (e) that x, which by de¬nition is the

coequalizer of u0 and u1 is also the coequalizer of d0 and d1 . Now c = U x is the

coequalizer of U d0 and U d1 , so by Exercise 6 of Section 1.8, U d0 and U d1 is the

kernel pair of c. Hence by Lemma 4, d0 and d1 form the kernel pair of x. Since

x is a regular epi, it is the coequalizer of d0 and d1 as required.

296 9 More on Triples

Variation on Duskin™s theorem

The following version of Duskin™s theorem is the form in which it is most often

used.

Proposition 5. If

(i) B has separators,

(ii) C has kernel pairs of split epis,

(iii) U : B ’ C has an adjoint F ,

’

(iv) U re¬‚ects isomorphisms and preserves regular epis, and

(v) U -contractible equivalence pairs in B are e¬ective and have coequalizers,

then U is tripleable.

Proof. All that is necessary is to show that under these hypotheses, U pre-

serves coequalizers of U -contractible equivalence pairs. If such an equivalence

pair (d0 , d1 ) has coequalizer x and is the kernel pair of y, then by Exercise 6 of

Section 1.8, x has kernel pair (d0 , d1 ). Since U preserves kernel pairs, U x is a

regular epi which has (U d0 , U d1 ) as kernel pair. Again using Exercise 6, U x is

therefore the coequalizer of (d0 , d1 ).

Tripleability over Set

If X is a set and G is an object in a cocomplete category, we write X · G

for the coproduct of X copies of G. In particular, if A is another object, there

is an obvious induced map Hom(G, A) · G ’ A (the arrow from the copy of G

’

corresponding to f is f ).

An object P of a category is a regular projective if whenever f : A ’ B is

’

a regular epi then the induced map Hom(P, A) ’ Hom(P, B) is surjective. (If

’

this is true for all epis then P is a projective.) An object G is a generator if

for each object A, the induced map Hom(G, A) · G ’ A is an epi. If the induced

’

map is a regular epi, then G is a regular generator. P is a regular projective

generator if it is both a regular projective and a regular generator. If it is both

a generator and a projective then it is a projective generator. The dual of

“projective” is “injective”.

Theorem 6. A category C is tripleable over Set if and only if it is regular, has

e¬ective equivalence relations and has a regular projective generator P for which

X · P exists for all sets X.

9.1 Duskin™s Tripleability Theorem 297

Proof. If U : C ’ Set is tripleable, then F (1) is a regular projective generator

’

(Exercise 4). Then for any set X, F (X) = X · F (1) because X = X · 1 in Set and

F preserves colimits. (Compare Theorem 1(a), Section 8.4.)

For the converse, the functor which is tripleable is U = Hom(P, ’), which has

a left adjoint taking X to X · P (Exercise 3).

U re¬‚ects isomorphisms: Suppose f : A ’ B and U f is an isomorphism. The

’

top arrow in this diagram

E UB · P

UA · P

c c

EB

A

f

is an isomorphism and the vertical arrows are regular epis, so f is a regular epi.

On the other hand, in this diagram

d0

e

E ’’ X ’ ’ A ’ B

’’

’ ’

’’

’’

1

d

let (d0 , d1 ) be the kernel pair of f and e the equalizer of d0 and d1 . Since U f is

an isomorphism, U d0 = U d1 , so that U e is an isomorphism. Hence by the ¬rst

part of this argument, e is epi, whence d0 = d1 and so f is an isomorphism.

Now suppose e0 , e1 : A ’ B is a U -contractible equivalence relation. Since

’

equivalence relations are e¬ective, there is a coequalizer/kernel pair diagram

e0 c

A ’ ’ B ’’ C

’’ ’

’’

’’

e1

U e0 and U e1 become the kernel pair of U c because U preserves limits. U c is epi

because P is a regular projective generator, so because we are in Set, U c is the

coequalizer of U e0 and U e1 , as required.

As an application of Theorem 5, observe that the Tietze Extension Theorem

says that the unit interval I is an injective cogenerator in CptHaus. Thus it is

a projective generator in the opposite category; in fact it is a regular projective

generator since every monomorphism in CptHaus is regular (take two copies of

the codomain and amalgamate the subspace).

Hom(’, I): CptHausop ’ Set is tripleable.

Corollary 7. ’

Proof. The only complicated thing to prove is that CptHaus has e¬ective coequiv-

alence relations. We leave the rest of the veri¬cations to the reader.

298 9 More on Triples

Suppose

d0

X ’’ Y

’’

’’

’’

d1

is a coequivalence relation. Then there is a map r: Y ’ X for which r —¦ d0 =

’

1

r —¦ d . (In fact, that is the only property of coequivalence relations we use. See

Exercise 5.) Let d: Z ’ X be the equalizer of d0 and d1 . We must show that d0

’

1

and d form the cokernel pair of d. We do this by showing that the map X +Z X

’ Y is bijective. It is clearly surjective because [d0 , d1 ]: X + X ’ Y is. For

’ ’

j

j = 0, 1, d is injective because it has a left inverse r. It follows that if (for j = 0 or

1) [d0 , d1 ](ij x) = [d0 , d1 ](ij x ), then x = x . Clearly if [d0 , d1 ](i0 x) = [d0 , d1 ](i1 x ),

then x = x , hence d0 x = d1 x so that the map from X +Z X to Y is injective as

well as surjective, and so is an isomorphism.

Exercises 9.1

1. Show that if f : A ’ B is a map, then the kernel pair of f is the the separator

’

of f and f . Show that if f, g: A ’ B, then the separator of f and g is kerp(f ) ©

’

kerp(g).

2. Show that if g is a split epi and (h, k) is its kernel pair, then h, k and g form

a contractible coequalizer diagram.

3. Show that if C is a category with a regular projective generator P , then

Hom(P, ’) has a left adjoint taking a set X to the sum X · P (assuming that sum

exists).

4. Show that if U : C ’ Set is tripleable, then F (1) is a regular projective

’

generator in C .

5. A single-sorted equational theory is called a Mal™cev theory if there is in the

theory a ternary operation µ satisfying the equations µ(a, a, c) = c and µ(a, b, b) =

a. A theory which includes a group operation is automatically a Mal™cev theory

for one can de¬ne µ(a, b, c) = ab’1 c. Thus the dual of the category of sets is the

category of algebras for a Mal™cev theory, since Setop is equivalent to the category

of complete atomic Boolean algebras which, like any rings, include the group

operation of addition. See Exercise 3 of Section 5.6 for an example that doesn™t

arise from a group (or any other binary) operation. Show that in the category of

algebras for a Mal™cev theory every re¬‚exive relation is an equivalence relation.

The converse is also true. The construction of µ in such a category can be

sketched as follows. On the free algebra on two generators which we will denote

9.2 Distributive Laws 299

by 0 and 1 consider the relation generated by (0, 0), (1, 1) and (0, 1) which is the

image of a map from the free algebra on three generators (the map taking the

three generators to the three above mentioned elements). This image is a re¬‚exive

relation which is hence an equivalence relation. In particular it is symmetric

which means there is an element µ in the free algebra on three generators that

maps to (1, 0). Given the correspondence between n-ary operations and elements

of the free algebra on n elements developed in Section 4.3 (see Exercise 3), this

element corresponds to a ternary operation which (you will have no doubt already

guessed) is the required Mal™cev operation. Remarkably, one need only assume

that every re¬‚exive relation is symmetric to derive the conclusion.

These operations were ¬rst studied (you will have no doubt also guessed) by

Mal™cev [1954] who derived most of their interesting properties, not including

what was probably their most interesting property: every simplicial object in a

category of algebras for a Mal™cev theory satis¬es Kan™s condition.

9.2 Distributive Laws

It is not ordinarily the case that when T1 = (T1 , ·1 , µ1 ) and T2 = (T2 , ·2 , µ2 ) are

triples on the same category, there is a natural triple structure on T2 —¦ T1 . But that

does happen; for example, the free ring triple is the composite of the free monoid

triple followed by the free Abelian group triple. The concept of distributive law

for triples was formulated by Jon Beck to formalize the fact that the distribution

of multiplication over addition explains this fact about the free ring triple.

Another way of seeing the distributive law in a ring is that it says that mul-

tiplication is a homomorphism of the Abelian group structure. This underlies

the concept of a lifting of a triple, which we will see is equivalent to having a

distributive law.

Distributive laws

Using the notation above, a distributive law of T1 over T2 is a natural

transformation »: T1 —¦ T2 ’ T2 —¦ T1 for which the following diagrams commute.

’

We omit the “—¦” to simplify notation.

T1

d

T1 ·2 d · 2 T1 (D1)

d

© d

‚

E T2 T1

T1 T2

»

300 9 More on Triples

T2

d

·1 T2 d T2 · 1 (D2)

d

©

d

‚

E T2 T1

T1 T2

»

»T2E T2 »E

2 2

T1 T2 T2 T1 T2 T2 T1

(D3)

T1 µ 2 µ2 T1

c c

E T2 T1

T1 T2

»

»T2E T2 »E

2 2

T1 T2 T1 T2 T1 T2 T1

(D4)

T1 µ 2 µ2 T1

c c

E T2 T1

T1 T2

»

For example, when T1 is the free monoid triple on Set and T2 is the free

Abelian group triple, we have a distributive law »: T1 —¦ T2 ’ T2 —¦ T1 which takes

’

an element of T1 T2 X of the form

( ±1 (x) · x)( ±2 (x) · x) · · · ( ±m (x) · x)

(each sum only having the integer ±i (x) nonzero for a ¬nite number of terms) to

±1 (x1 )±2 (x2 ) · · · ±m (xm ) · (x1 x2 · · · xm )

the sum over all strings of length m in elements of X.

Another example in Set has T1 the free semigroup triple and T2 de¬ned by

T2 (X) = 1 + X (the disjoint union”see Example 3 of Section 3.1) Then T2 —¦ T1

is the free monoid triple. The distributive law » takes

1 + X + (1 + X)2 + (1 + X)3 + · · · = 1 + X + 1 + X + X + X 2