Practical Foundations of Mathematics

5.4  Coproducts and Pushouts

The universal property of products and coproducts was formulated by Saunders Mac Lane in his study of categories of modules in homological algebra (1950). The resulting description of Abelian categories put too much emphasis on the duality of the axioms [ML88, p. 338]: although the definitions are precisely opposite, colimits behave very differently from limits in most other categories of interest. Distributivity for lattices treats meets and joins symmetrically, but this too fails for the category of sets. Example 7.3.4(c), calculating colimits, is perhaps the one useful application of the literal analogy between Set and Setop.

We aim to redress the balance in our survey, which illustrates several other important themes in mathematics (more particularly in topology, but this may be a historical accident). Coproducts are very simple in Set - they are called disjoint unions and interpret conditionals - but get more complicated as algebraic operations are added. In universal algebra coproducts and pushouts were called free products and free compositions respectively, because of the way they are constructed for groups.

DEFINITION 5.4.1

(a)
An object 0 is an initial object if for each Q ö obS there is exactly one morphism 0Û Q.

(b)
Let N,Y ö obS. An object C together with maps n0:NÛ C and n1:YÛ C is a coproduct if for each object Q and pair of maps Nf Û Qg ˜ Y there is a unique map p:CÛ Q such that n0;p = f and n1;p = g . We usually write N+Y for C and [f ,g ] for p. In the case Y = N = Q = X and f = g = id, we write îX:X+XÛ X for the codiagonal.

omitted diagram environment

In a poset, the initial object is the least element and the coproducts are joins (Definition 3.2.4); in particular they are falsity and disjunction for formulae under the provability order.

Disjoint unions   These are discussed more fully in the next section.

EXAMPLES 5.4.2

(a)
The empty set, ó, is the initial object of Set, Pos, Preord, Dcpo, Sp, Cat and  Gpd, by Proposition 2.1.9(a).

(b)
The coproduct in Set was constructed in Example  2.1.7 and is called the disjoint union. Exercise 2.13 showed how to find the mediator p = [f ,g ]:N+YÛ Q, and that it is unique.

(c)
Coproducts in Pos, Preord, Dcpo, Pfn, Sp, Gpd and Cat are computed as in Set, where in the first three cases ni(x) È nj(y) iff i = j and x È y ö \typeXi.

(d)
The Boolean type is the coproduct 2 = 1 +1 in Set. The inclusions are called yes and no and the coproduct mediator is the conditional.

(e)
More generally, a variant field in a record consists of a tag i ö I and a data assignment x ö \typeXi. See Exercise 5.36 for how switch is typically implemented.

(f)
JAVA allows constructors with the same name and result type but different arities; the source of such a constructor is effectively the coproduct of the arities.

(g)
JAVA and ML provide idioms for exception- handling, which amount to returning a result of coproduct type, cf Remark 2.7.9.

Abelian categories   In categories of vector spaces and modules for rings, finite products coincide with the corresponding coproducts.

DEFINITION 5.4.3 An object of a category which is both terminal (1) and initial ( 0) is known as a zero object. In Vsp, the zero object is the space consisting only of the zero vector, and in general the singleton is the zero algebra for any single-sorted theory which has exactly one definable constant ( ie every expression of the form r(c,c,¥) must also be provably equal to c), for example Mon, CMon, SLat, CSLat, HSL, Gp and  AbGp. On the other hand, ó is the zero object in Rel and  Pfn.

The composite XÛ 1 = 0Û Y is called the zero map 0:XÛ Y.

EXAMPLE 5.4.4 The coproduct in the category of commutative monoids agrees with the product, in which n0:NÛ N+Y ¤ NxY is xÛ x,0, n1:yÛ 0,y and [f ,g ]: x,yÛ f (x)+g (y). In particular

 Nx(N+N) ¤ N3     but    (NxN)+(NxN) ¤ N4.
The common construction is known as the biproduct or direct sum, written NéY. Since morphisms
 \typeX1é···é\typeXnÛ \typeY1é ···é\typeYm
may be seen as going from the coproduct to the product, they are determined by an (nxm) matrix of maps \typeXiÛ \typeYj. Composition is matrix multiplication, in which we take composition of homomorphisms between components as the notion of ``scalar multiplication.''

Conversely, any category with a zero object and biproducts is CMon-enriched, ie the hom-sets carry a commutative monoid structure for which composition is linear in each argument separately (Exercise  5.20). The categories AbGp, Vsp, SLat, Rel and CSLat are CMon-enriched (Exercise  5.22); in the last three cases ``addition'' means join or union. []

REMARK 5.4.5 Homological algebra was the progenitor of category theory. Generalising Leonhard Euler's formula f+v = e+2 for the faces, vertices and edges of a convex polyhedron, Enrico Betti defined numerical invariants of spaces by formal addition and subtraction of faces of various dimensions; Henri Poincaré formalised these and introduced homology. Emmy Noether stressed the fact that these calculations go on in Abelian groups, and that the operation Ñn taking a face of dimension n to the alternating sum of faces of dimension n-1 which form its boundary is a homomorphism, and it also satisfies Ñn·Ñn+1 = 0. There are many ways of approximating a given space by polyhedra, but the quotient Hn = KerÑn/imÑn+1 is an invariant, the homology group. Since Noether, the groups have been the object of study instead of their dimensions, which are the Betti numbers [ Die88].

The categories used for homology are AbGp-enriched (additive) - but more. It emerged in the 1950s that one could argue in them by chasing diagrams involving kernels and cokernels instead of elements. (Kernels and their quotients are the subject of the later parts of this chapter.) David Buchsbaum axiomatised ``Abelian'' categories, in his thesis (under Sammy Eilenberg's supervision, but without knowing about Mac Lane's work) and in [CE56, appendix]. Alexander Grothendieck, again independently, showed that sheaves of vector spaces and modules also form Abelian categories (1957). We defer to Definition  5.8.1(d) discussion of the extra condition which an AbGp-enriched category must satisfy in order to be Abelian, since it also applies to sets and other algebraic theories. Abelian categories are covered thoroughly in [Fre64], [ML71], [FS90] and in any modern homology text.

In domain theory, Dana Scott (1970) discovered an analogous infinitary property, that certain filtered colimits coincide with cofiltered limits. This may be used to find domains satisfying equations such as X ¤ XX. Michael Smyth (1982) showed that it arises in Dcpo-enriched categories. For a treatment of more general diagrams, see [ Tay87]. More recently, Peter Freyd [ Fre91] has emphasised the coincidence of initial algebras and final coalgebras for certain functors.

Stone duality   For certain algebraic theories - the ones with which the discipline of universal algebra, despite its name, is mainly concerned - Mod(L)op has a spatial flavour: the lattices of congruences of groups, rings and modules are modular, and for lattices they are distributive (Exercise 3.49). This suggests viewing their quotients as monos in the opposite category. Marshall Stone (1937) showed how any Boolean algebra arises as the lattice of clopen ( ie both open and closed) subsets of some compact Hausdorff totally disconnected topological space. This was the first real theorem linking logic to the mainstream of mathematics, and dualities like this are explored in [ Joh82]. In particular, coproducts of certain algebras signify topological products.

EXAMPLES 5.4.6

(a)
The two-element lattice is the initial object of DLat , BA and  Heyt.

(b)
Z is the initial ring.

(c)
There is no initial field, but Q is initial in the full subcategory of fields of characteristic zero.

(d)
The coproduct of two commutative rings R,S ö obCRng is given by their tensor product RáZ S as Abelian groups or Z-modules;

(e)
in particular the coproduct of Z/(2) and Z/(3) is the trivial ring (with 0 = 1), so the ``inclusions'' are not mono.

(f)
More generally, any homomorphism TÛ R of commutative rings makes R into a T-module; then the pushout of TÛ R and TÛ S is the tensor product RáTS of T-modules (Example 7.4.7).

(g)
The initial object of Frm is W, and its coproducts and pushouts can also be found by a tensor product construction (Example 3.9.10(e)).

Free (co)products and van Kampen's theorem   Coproducts of algebras in general tend to be rather chaotic, Mon being typical.

EXAMPLE 5.4.7 By Corollary 2.7.11, List(X) is the free monoid on a set X. Then List(N+SetY) ¤ List(N)+MonList(Y) and in particular N+MonN ¤ List(2) consists of words in the letters a and b, so

omitted eqnarray* environment

Elements of such monoids have normal forms in which we choose the first representative in lexicographic (dictionary) order. The situation for algebraic theories with more operations gets progressively worse.

Coproducts of monoids are clearly relevant to formal languages, but one might think that the only other value of this construction is in universal algebra. The following famous result shows that, on the contrary, it is also of interest to the geometric tradition. These topological intuitions were already present in Section 4.2.

We only intend to give a sketch of the algebraic idea in its simplest topological form. It is not necessary that both maps be open inclusions, but there are some topological counterexamples which we do not want to consider. The interested reader should see eg [Bro88, Section 6.7].

Those not familiar with topology may ignore the compactness and open sets, considering finite networks instead. Indeed the edges of the network may be oriented, in which case there is a category but no meaningful group(oid) of paths. For example the paths in an oriented figure of 8 beginning and ending at the cross-over form the monoid List(2).

THEOREM 5.4.8 Let X be a topological space and U,V ä X be open subspaces with UàV = X. Put W = UúV, so the diagram shown is (both a pullback and) a pushout in  Sp, and also in Set.

omitted diagram environment

Then the functor p1 which assigns the fundamental groupoid (Exercise 4.43) to any space preserves this pushout (it trivially preserves ó).

PROOF: As obp1(X) is by definition the underlying set of the space X, it is the pushout of obp1(U) and obp1(V) from obp1(W), so we must consider the morphisms (paths). Let F:p1(U)Û C and G:p1(V)Û C be functors which agree on p1(W).

In order to define [F,G](s) for any path s:IÛ X (with I = [0,1] ä R), s must be expressed as a composite of paths in U and V. The open sets s-1(U),s-1(V) ä I are each unions of open intervals; altogether they cover I, but this is compact so finitely many suffice. Hence the path s is \arga1;\argb1;\arga2;\argb2;···;\argan;\argbn where each \argai is a path in U and each \argbi is a path in V (so the changeover points lie in W = UúV).

By a similar argument using compactness of IxI, any homotopy between composites s and t of this form may be decomposed into a (rectangular) patchwork whose cells each lie wholly in either U or V (so the boundaries between cells of different kinds are in W). Since F and G are defined on homotopy classes, they map each of these cells to a commutative square in C (Example 4.8.16(g)). By composing this array of commutative squares, [F,G](s) = [F,G](t). Hence [F,G]:p1(X)Û C is well defined, and it preserves identities and composition. []

The group of endo-paths of a point a ö X is known as a fundamental group of X and written p1(X,a). When U and V are path-connected and W is contractible (so in particular every path is homotopic to a point, and the fundamental groupoid of W is trivial), the theorem reduces to saying that the fundamental group for X is the coproduct (in Gp) of those for U and V. This special case is commonly attributed to Edgar van Kampen (1935), though Herbert Seifert proved an earlier result for simplicial complexes. Van Kampen stated his result using generators and relations (Section 7.4), so the proof is very difficult to follow. Ronald Brown (1967) proved the groupoid form, and Richard Crowell formulated it in terms of a universal property with a modern proof.

Van Kampen wanted to find the fundamental groups of the complements of algebraic curves in C2. The case where W is not connected is needed even in the simplest example of the fundamental group of a circle (or the complement of a point in R2). His results may be deduced from the group oid form, but not solely from the result for groups.

We did not need to construct the pushout of groupoids, because p1(X) already has this property. Yet the fundamental groups of a wide range of spaces of traditional interest in geometric topology (such as a many-handled torus) may be deduced from this theorem, starting from the easy case of contractible spaces. This illustrates the power of categorical methods, both for producing the ``right'' object for algebraic study, and for manipulating constructions with it.

These examples show that coproducts in Set, AbGp, Mon and CRng behave very differently from one another. For coproducts in general algebraic theories we must resort to generators and relations (Lemma 7.4.8). The next section considers coproducts in Set, Frmop and CRngop.