Products and sums
5.1 The product of two objects in a category
Products and sums
This chapter introduces products, which are constructions allowing the defi-nition of operations of arbitrary arity, and sums, which allow the specification of alternatives. InSet, the product is essentially the cartesian product, and the sum is disjoint union.
Sections 5.1 through 5.3 introduce products, and Section 5.4 introduces sums. These ideas are used to define the important concept of natural num-bers object in Section 5.5. Section 5.6 describes a way to regard formal languages and formal deductive systems as categories. Products and sums then turn out to be familiar constructions. Thus in programming languages products are records with fields, and in deductive systems product becomes conjunction. Finally, Section 5.7 discusses distributive categories (roughly, categories in which products distribute over sums), which are categories with properties that one would expect deductive systems to have.
Except for the last two sections, all the sections of this chapter are used in many places in the rest of the book. The concepts from the last two sections are used only in examples. The last three sections of this chapter are independent of each other.
5.1 The product of two objects in a category
5.1.1 Definition If S and T are sets, the cartesian productS×T is the set of all ordered pairs with first coordinate inS and second coordinate inT; in other words,S×T ={(s, t)|s∈S andt∈T}. The coordinates are functions proj1:S×T −→S and proj2:S×T −→T called thecoordinate projections, or simplyprojections.
We give a specification of product of two objects in an arbitrary category which will have the cartesian product inSet as a special case. This speci-fication is given in terms of the coordinate projections, motivated by these two facts:
(i) you know an element ofS×T by knowing what its two coordinates are, and
153
(ii) given any element of S and any element of T, there is an element of S×T with the given element of S as first coordinate and the given element ofT as second coordinate.
5.1.2 The product of two objects Let A and B be two objects in a category C. By a (not the) product of A and B, we mean an object C together with arrows proj1 : C −→A and proj2 :C −→B that satisfy the following condition.
5.1.3 For any objectD and arrowsq1:D−→A andq2:D−→B, there is a unique arrowq:D−→C:
A¾ C
proj1 -B
proj2 D q1
¡¡
¡¡
ª ?
q q2
@@
@@R (5.1)
such that proj1◦q=q1and proj2◦q=q2.
5.1.4 Product cones The specification above gives the product asC to-gether with proj1and proj2. The corresponding diagram
A B
C proj1 ¡
¡¡
ª @ proj2
@@R (5.2)
is called aproduct diagram orproduct cone, and the arrows proji are called theprojections. These projections are indexed by the set{1,2}. The baseof the cone is the diagramD:I −→C, whereI is the discrete graph with two nodes 1 and 2 and no arrows. This amounts to saying that the base of the cone is the ordered pair (A, B). The diagram
B A
C proj1 ¡
¡¡
ª @ proj2
@@R (5.3)
is regarded as a different product cone since its base is the diagramD with D(1) =B andD(2) =A.
5.1 The product of two objects in a category 155 By a type of synecdoche, one often says that an object (such asCabove)
‘is’ a product of two other objects (hereA and B), leaving the projections implicit, but the projections are nevertheless part of the structure we call
‘product’.
Products can be based on discrete graphs with other shape graphs, hav-ing more elements (Section 5.3) or havhav-ing other sets of nodes, for example attributes of a data base such as{NAME,SALARY} (see 5.3.14). In this case the projections would be projNAME and projSALARY.
The existence of the unique arrowq with the property given in 5.1.3 is called theuniversal mapping propertyof the product. Any object con-struction which is defined up to a unique isomorphism (see Theorem 5.2.2) in terms of arrows into or out of it is often said to be defined by a universal mapping property.
5.1.5 Products in Set If S and T are sets, then the cartesian product S×T, together with the coordinate functions discussed in 5.1.1, is indeed a product ofS andT in Set. For suppose we have a setV and two functions q1:V −→S andq2:V −→T. The functionq:V −→S×T defined by
q(v) = (q1(v), q2(v))
forv∈V is the unique function satisfying 5.1.3. Since proji(q(v)) =qi(v) by definition,qmakes (5.1) commute withU =S×T, and it must be the only such function since the commutativity of (5.1) determines that its value at vmust be (q1(v), q2(v)).
We discuss products inReland inPfn in 5.4.7.
5.1.6 Products in categories of sets with structure In many, but not all, categories of sets with structure, the product can be constructed by endowing the product set with the structure in an obvious way.
5.1.7 Example IfS andT are semigroups, then we can makeS×T into a semigroup by defining the multiplication
(s1, t1)(s2, t2) = (s1s2, t1t2) We verify associativity by the calculation
[(s1, t1)(s2, t2)](s3, t3) = (s1s2, t1t2)(s3, t3)
= ((s1s2)s3,(t1t2)t3)
= (s1(s2s3), t1(t2t3))
= (s1, t1)(s2s3, t2t3)
= (s1, t1)[(s2, t2)(s3, t3)]
(5.4)
Furthermore, this structure together with the coordinate projections satisfies the definition of product in the category of semigroups. To see this requires showing two things:
(a) The arrows proj1:S×T −→Sand proj2:S×T −→Tare homomorph-isms of semigroups.
(b) If q1 and q2 are semigroup homomorphisms, then so is the arrow q determined by 5.1.3.
It is necessary to show both because the definition of product in a category C requires that the arrows occurring in Diagram (5.1) be arrows of the category, in this case,Sem.
Requirement (a) follows from this calculation:
proj1((s1, t1)(s2, t2)) = proj1(s1s2, t1t2) =s1s2
= proj1(s1, t1) proj1(s2, t2) and similarly for proj2.
As for requirement (b), letRbe another semigroup andq1:R−→S and q2:R−→T be homomorphisms. Then
hq1, q2i(r1r2) = (q1(r1r2), q2(r1r2)) = (q1(r1)q1(r2), q2(r1)q2(r2))
= (q1(r1), q2(r1))(q1(r2), q2(r2))
=hq1, q2i(r1)hq1, q2i(r2)
A construction for products similar to that for semigroups works for most other categories of sets with structure. Also, the product of categories as defined in 2.6.6 is the product of the categories inCat. One example of a category of sets with structure which lacks products is the category of fields.
We discuss this in 8.2.3.
5.1.8 Products in posets We have already seen in 2.3.1 that any poset (partially ordered set) has a corresponding category structureC(P). LetP be a poset and xand y two objects of C(P) (that is, elements of P). Let us see what, if anything, is their product. A product must be an elementz together with a pair of arrowsz−→xandz−→y, which is just another way of saying thatz≤xandz≤y. The definition of product also requires that for anyw∈P, given an arroww−→xand one w−→y, there is an arroww
−→z.
This translates to
w≤xandw≤y impliesw≤z
5.2 Properties of products 157 which, together with the fact thatz≤xand z≤y, characterizes z as the infimumofxandy, often denotedx∧y. Thus the existence of products in such a category is equivalent to the existence of infimums. In particular, we see that products generalize a well-known construction in posets. Note that a poset that lacks infimums provides an easy example of a category without products.
5.1.9 Exercises
1. Show that the product of two categories, as in 2.6.6, is the product in the category of categories and functors.
2. Describe the product of two monoids in the category of monoids and monoid homomorphisms.
3. Describe the product of two posets in the category of posets and monotone functions.
4. Let G and H be two graphs. Show that the product G ×H in the category of graphs and homomorphisms is defined as follows: (G ×H)0= G0×H0. An arrow from (g, h) to (g0, h0) is a pair (a, b) with a: g−→ g0 in G and b:h−→h0 in H. The projections are the usual first and second projections.
5. Show that ifAis an object in a category with a terminal object 1, then
1 A
A hi ¡
¡¡
ª idA
@@@R
is a product diagram.
6. Give an example of a product diagram in a category in which at least one of the projections is not an epimorphism.