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.
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.
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
|
|
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.
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.