Coequalisers in Set, like coproducts, behave very differently from their duals. The construction is very complicated in the general case: only quotients of equivalence relations have a straightforward description in Zermelo type theory, although it is much simpler for Abelian categories. The method extends to congruences for finitary algebraic theories, and is used to impose laws (Example 4.6.3(j), Section 7.4).
Kernels We begin by using pullbacks to code Definition 1.2.3.
DEFINITION 5.6.1 The kernel pair or level of a morphism f:A® B in a category with pullbacks is the pullback square
omitted diagram environment
A fortiori , the operations on Ker f also satisfy the laws of L.
The trick in (d)-(f) does not work for other theories such as lattices, but needs division or subtraction to translate everything to the origin. However, the kernel pair of a homomorphism of complete semilattices can also be represented as a subset, which is order-isomorphic to its quotient: see Lemma 5.6.14 below and Exercises 5.39 and 5.41.
Congruences The kernel pair of any map, where it exists in a category, is an equivalence relation (Definition 1.2.3), which we express in the style of Remark 5.2.8. For an algebraic theory L, we can regard the following diagrams as being in Set, SetS or Mod(L), since Mod(L)® SetS creates limits.
DEFINITION 5.6.3 A mono K\hookrightarrow Ax A (or the pair K\rightrightarrows A) for which these diagrams exist is called a congruence. (This loosely agrees with Definition 1.2.12 in that it transfers algebraic properties.)
In Set a congruence is just an equivalence relation; in Mod(L) it is also a subalgebra of AxA.
PROPOSITION 5.6.4 In a category with pullbacks, kernel pairs satisfy the reflexive, symmetric and transitive laws, in the sense defined by the following diagrams.
|
PROOF: The mediator, x® x,x, of the diagram on the left expresses reflexivity, whilst that on the right, x,y® y,x, expresses symmetry. The bottom and right faces of the cube represent the hypotheses for the transitive law: f(x) = f(y) and f(y) = f(z). The back face forms their conjunction, and the front the conclusion; since this is a pullback and the cube commutes, the mediator exists and states the entailment. []
omitted diagram environment
The other two faces are also pullbacks (by Lemma 5.1.2 ), and in fact the eighth vertex is the ternary pullback of the first three edges, and also the limit of the first three faces. See Exercise 5.40 for an alternative proof.
DEFINITION 5.6.5 The coequaliser of a parallel pair u,|:R\rightrightarrows A is the universal map q:A® Q with u;q = |;q.
omitted diagram environment
So, for any other map f:A® Q with u;f = |;f, there is a unique mediator p:Q® Q such that f = q;p. As usual, coequalisers are unique up to unique isomorphism. We shall concentrate on congruences since they are easier to handle than general pairs, but also because of
LEMMA 5.6.6 Let S be a category with kernel pairs and coequalisers.
PROOF: Consider the relation (W\rightrightarrows A)^(A®Q) that the composites are equal; this induces a Galois connection (Proposition 3.8.14) between the class of pairs of maps into A and that of single maps out, or between the double slice S¯ A,A (Lemma 4.5.16) and the coslice A¯ S. Then the kernel pair of A® Q is the terminal object of \orthl (A® Q), whilst the coequaliser of W\rightrightarrows A is initial in \orthr (W\rightrightarrows A). The result follows from the idempotence of Galois connections. []
DEFINITION 5.6.7 We want to use equivalence relations to specify that pairs of elements are to be identified. The coequaliser q:A\twoheadrightarrow Q of a congruence K\rightrightarrows A is known as its quotient and written Q = A/K. It is said to be effective if K is the kernel pair of q, ie the quotient identifies the specified pairs and no more.
PROPOSITION 5.6.8 In Set, every congruence has an effective quotient.
PROOF: Let Q Ì P(A) be the set of equivalence classes. Example 2.1.5 showed that Q is the coequaliser (the mediator p is unique since A\twoheadrightarrow Q is surjective). This is effective because [x] = [y]Û x,y Î K. []
THEOREM 5.6.9 Let L be a finitary algebraic theory. Then the category Mod(L) also has effective quotients of congruences.
PROOF: We begin with semilattices, as a typical single-sorted finitary algebraic theory. The constant T in the quotient is the equivalence class [T]. Similarly [a]Ù[b] = [aÙb], which we must show to be well defined with respect to choices of representatives: the equation [a] = [a¢] means that a,a¢ Î K; if also b,b¢ Î K, then aÙb,a¢Ùb¢ Î K since it's a subalgebra, so [aÙb] = [a¢Ùb¢].
The same applies to any finitary operation-symbol \typeX1,¼,\typeXk\vdash r:Y.
Categorically, the two squares from \relK[( X)\vec] to \typeAY exist as K is a subalgebra; indeed they are pullbacks and \relK[( X)\vec] is a congruence on \typeA[( X)\vec]. But in order to define the dotted map, the top row must be a coequaliser. It is, because the product functors preserve coequalisers. quote omitted diagram environment
The laws of L are inherited from A, again by choosing representatives . They may be expressed diagrammatically as pairs of derived operations u,v:[(X)\vec]\rightrightarrows Y; if these are equal for A then they are also equal for A/K since [(q)\vec] is epi. []
It is essential here that the functors (-)k preserve regular epis. In the next chapter we shall extend some of the methods of universal algebra to infinitary theories: the theory may have infinitely many sorts or laws without causing difficulty. But this will be at the cost of the ability to treat laws in general; the problem lies in the above result, though this obstacle can be removed by brute force (the axiom of choice). By finitary we really do mean that the arity k has to be finitely enumerated (Definition 6.6.2(a)). This is not finitist dogma: the condition may be formulated abstractly, and is called projectivity, Remark 5.8.4(e).
COROLLARY 5.6.10 In a category with pullbacks and effective quotients of congruences, the Galois connection used to prove Lemma 5.6.6 reduces to an order-isomorphism between
General coequalisers It remains to convert an arbitrary parallel pair into a congruence, using zig-zags (Lemma 1.2.4).
LEMMA 5.6.11 In the following diagram in a category with kernel pairs, suppose that u = e;m;\;p0 and
| = e;m;\;p1, the maps are epi and mono as marked and K is the smallest congruence containing R.
omitted diagram environment
Then the following are equivalent:
If the quotient q:A\twoheadrightarrow A/K exists, it is also equivalent that
Hence A/K is the coequaliser of u and |.
PROOF: [aÞ b]: e is epi. [bÞ c]: R Ì Ker f, so K Ì Ker f by hypothesis. [cÞ d]: by definition of A/K. The converses hold by composition. []
COROLLARY 5.6.12 Set has coequalisers for all parallel pairs, as does the category Mod(L) of algebras for any finitary algebraic theory L.
PROOF: Put R = {x0,x1|$y.u(y) = x0Ùu(y) = x1}, and let K be its congruence closure. In Set this is the set of zig-zags. []
Note that to find e and m from u and | in Lemma 5.6.11 uses the image factorisation, which we shall discuss in the next section.
REMARK 5.6.13 In the case of the category of algebras for a many-sorted algebraic theory, the congruence (\relKX Ì \typeAXx\typeAX)X Î S has to be generated for all of the sorts and operation-symbols together, because operation-symbols with results of one type may make use of arguments of any of the other types. Treating it as a subset of ÈX Î S(\typeAXx\typeAX), the reflexive, symmetric and transitive laws, and each operation-symbol (with respect to which the inclusion must be a homomorphism ), give rise to a closure condition (Example 3.7.5(a)).
Colimits by duality Although this way of constructing coequalisers is not in general available for infinitary operations, most of those of interest (meets, joins, limits and colimits) are defined by universal properties. We can use our knowledge of adjunctions to make the necessary choices canonically. Indeed in some categories it is much easier to find colimits in this way than it is in Set by the combinatorial technique.
For example, since the category of complete join-semilattices is self-dual, ie CSLat º CSLatop, its colimits follow immediately from its limits. The next result was, of course, discovered by unwinding this corollary, but it is instructive as an example of a construction which does not simply work by symbol-pushing.
LEMMA 5.6.14 CSLat has coequalisers.
PROOF: We are given u,v:X\rightrightarrows A, which preserve all joins. Put
|
e (a) = Ù{q|a £ q} and ÚiQ \argqi = e (ÚiA \argqi).
Then
|
Although SLat, AbGp, Vsp and categories of modules for rings are not quite self-dual, a similar technique applies. The particular case of the coequaliser of a linear map u with the zero map v = 0 (Example 5.4.4) is called its cokernel.
Section 6.4 uses coequalisers to interpret loops, and Sections 6.5 and 7.4 consider laws in algebras. The rest of this chapter shows how limits and monos interact with colimits and epis.