# Practical Foundations of Mathematics

## 5.6  Kernels, Quotients and Coequalisers

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

EXAMPLES 5.6.2

(a)
Any map f is a mono iff ker0f = ker1f = \idA (Proposition 5.2.2(a)).

(b)
In Set, Kerf = {x,y|f(x) = f (y)} Ì A2 is just an equivalence relation.

(c)
In  Mod(L), where L is a single- sorted algebraic theory, Ker f is also a subalgebra of Ax A. For example in Lat,

• the constants ^ = ^,^ and T = T,T are in Ker f because it's reflexive, or because f  preserves them,

• if x,y and u,v are in Ker f then so are xÚ u,  yÚv and xÙu,  yÙv, because f is a homomorphism,

• for theories with unary operations ( eg logical and arithmetical negation), Ker f is closed under them as well, and likewise under operations of arbitrary arity.

A fortiori , the operations on Ker f also satisfy the laws of L.

(d)
In the category of groups, the subset N = {x|f(x) = 1} Ì A suffices to define the kernel pair, as K = {x,y|x;y-1 Î N}. N is the equaliser of f with the trivial (constantly 1) homomorphism. It is characterised as a normal subgroup, ie a subgroup satisfying "x, n:A.n Î NÞ x-1 ;n;x Î N.

(e)
Similarly in the category of vector spaces (or modules for a ring) the subspace or submodule U = {x|f(x) = 0} determines the kernel pair by K = {x,y|x-y Î U}. Again U is the equaliser with the zero map, but this time every submodule arises in this way.

(f)
The kernel pair for rings has yet another representation peculiar to that category, as a (two-sided) ideal I = {x|f(x) = 0}, Example 2.1.3(b). The kernel pair can be recovered in the same way as for vector spaces, but I is not an equaliser or subring unless B is the trivial ring; it has the property that "x, i:A.i Î IÞ xi,ix Î I.

(g)
In a many-sorted algebraic theory, kernels are constructed for each sort independently of the others, as the inclusion Mod( L) Ì SetS creates pullbacks ( Definition 4.5.10(c)), where S is the set of sorts.

(h)
Let M be a module for a commutative ring R. Then a kernel consists of an ideal I Ì R and a submodule U Ì M, with the additional condition that IM Ì U. So the sorts do interact, and the general case is more complicated than this example.

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.

 omitted diagram environment omitted diagram environment

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.

Quotients

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.

(a)
If a map A® Q is the coequaliser of some pair W \rightrightarrows A then it is also the coequaliser of its kernel pair. It is called a regular epi.

(b)
If K\rightrightarrows A is the kernel pair of some map A® Q then it is also the kernel pair of its coequaliser.

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

(a)
quotients (regular epis out) of A, cf Sub(A ) in Remark 5.2.5, with \idA as the least element and !:A® 1 as the greatest, and

(b)
congruences on A, with the diagonal as least element (the discrete congruence) and AxA as greatest (the indiscriminate one). []

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:

(a)
u;f = |;f:W® Q

(b)
m;\;p0;f = m;\; p1;f:R® Q;

(c)
\;p0;f = \;p1;f:K® Q.

If the quotient q:A\twoheadrightarrow A/K exists, it is also equivalent that

(d)
f factor through q, ie there be a unique map p such that f = q;p.

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

 Q = {a|"x.u(x) £ aÛ v(x) £ a} Ì A
and observe that it is closed under all meets in A. Using Theorem  3.6.9, Q is a complete join-semilattice, and the inclusion j:Q\hookrightarrow A has a (join-preserving) left adjoint, e\dashv j. In fact

e (a) = Ù{q|a £ q}    and    ÚiQ \argqi = e (ÚiA \argqi).

Then

 e (u(x)) = Ù {q|u(x) £ q} = Ù {q|v (x) £ q} = e(v(x)).
Now given f:A® Q preserving joins and such that fou = fov, define p:Q® Q by p(q) = f(q); since eoj = \idQ this is the unique function with poe = f. Using the above formula for joins in Q, we see that p preserves them. []

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.