Finite products

3. Prove that Diagram (5.12) commutes.

4. Prove Proposition 5.2.3.

5. Let f :A −→C, g :B −→ D, u: X −→A and v :X −→ B. Show that (f ×g)^◦hu, vi=hf ^◦u, g^◦vi.

5.3 Finite products

Products of two objects, as discussed in the preceding sections, are called binary products. We can define products of more than two objects by an obvious modification of the definition.

For example, ifA, BandCare three objects of a category, a product of them is an objectA×B×C together withthree arrows:

A B C

for which, given any other diagram

A B C diagram(or ternary product cone). The general definition of product follows the same pattern.

5.3.1 Definition Aproductof a list A₁, A₂, . . . , A_nof objects (not nec-essarily distinct) of a category is an object V together with arrows p_i :A

−→A_i, fori= 1, . . . , n, with the property that given any objectBand arrows f_i:B −→A_i, i= 1, . . . , n, there is a unique arrowhf₁, f₂, . . . , f_ni:B−→A for whichpi^◦hf1, f2, . . . , fni=fi,i= 1, . . . , n.

A product of such a listA1, A2, . . . , Anis called ann-ary productwhen it is necessary to specify the number of factors. Such a product may be denotedA1×A2× · · · ×An or^Qn_i=1Ai.

The following uniqueness theorem for general finite products can be proved in the same way as Theorem 5.2.2.

5.3.2 Theorem Suppose A1, A2, . . . , An are objects of a category C and thatA, with projections pi:A−→Ai, and B, with projectionsqi:B−→Ai, are products of these objects. Then there is a unique arrow φ:A−→B for whichq_i^◦φ=p_i for i= 1, . . . , n. Moreover,φis an isomorphism.

Propositions 5.2.3, 5.2.11 and 5.2.18 also generalize in the obvious way ton-ary products.

5.3.3 Binary products give ternary products An important conse-quence of the definition of ternary product is that in any category with binary products, and any objectsA, B and C, either of (A×B)×C and

Recall thathf, giis the unique arrow making

A¾ A×B

5.3 Finite products 171

The fact that (a) through (c) hold can be read directly off these diagrams.

For example, for (a),p1^◦q1^◦u=p1^◦hf, gi=f.

Finally, if u⁰ were another arrow making (a) through (c) hold, then we would have p1^◦q1^◦ u⁰ =f and p2^◦ q1 ^◦u⁰=g, so by uniqueness of v as defined by (5.21),v =q1 ^◦u⁰. Sinceq2^◦u⁰ must be h, the uniqueness of u in (5.22) means thatu⁰=u.

A generalization of this is stated in Proposition 5.3.10 below.

5.3.4 It follows from the discussion in 5.3.3 that the two objects (A×B)× CandA×(B×C) are pairwise canonically isomorphic (to each other and to any other realization of the ternary product) in a way that preserves the ternary product structure.

In elementary mathematics texts the point is often made that ‘cartesian prod-uct is not associative’. When you saw this you may have thought in your heart of hearts that (A×B)×CandA×(B×C) are nevertheless really the same.

Well, now you know that they are really the same in a very strong sense: they satisfy thesame specification and so carry exactly the same information. The only difference is inimplementation.

5.3.5 If all the factors in ann-ary product are the same objectA, the n-ary productA×A× · · · ×Ais denotedAⁿ. This suggests the possibility of defining thenullary product A⁰and theunary productA¹.

5.3.6 For nullary products, the definition is: given no objects of the cate-goryC, there should be an object we will temporarily callT, with no arrows from it, such that for any other objectB and no arrows fromB, there is a unique arrow fromB toT subject to no commutativity condition.

When the language is sorted out, we see that a nullary product inC is simply an objectT with the property that every other object of the category has exactly one arrow to T. That is, T must be a terminal object of the category, normally denoted 1. Thus, for any object A of the category, we takeA⁰= 1. (Compare 4.1.6.)

5.3.7 A unary productA¹of a single objectAshould have an arrowp:A¹

−→Awith the property that given any objectB and arrowq:B−→Athere is a unique arrowhqi:B −→A¹for which

B hqi-A¹ q

@@

@@R A

?

p (5.23)

commutes. The identity id :A−→A satisfies this specification for p; given the arrowq:B−→A, we lethqi=q:B −→A. The fact that id^◦hqi=qis evident, as is the uniqueness ofhqi. It follows thatA¹ can always be taken to beAitself, with the identity arrow as the coordinate arrow.

It is straightforward to show that in general an object B is a unary product ofAwith coordinatep:B −→Aif and only ifp is an isomorphism (Exercise 1.b).

There is therefore a conceptual distinction between A¹ and A. In the category of sets,Aⁿ is often taken to be the set of strings of elements ofA of length exactlyn. As you may know, in some computer languages, a string of characters of length one is not the same as a single character, mirroring the conceptual distinction made in category theory.

5.3.8 Definition A category hasbinary productsif the product of any two objects exists. It hascanonical binary productsif a specific product diagram is given for each pair of objects. Thus a category with canonical binary products is a category with extra structure given for it. Precisely, a canonical binary products structure on a category C is a function from C0×C0to the collection of product diagrams inC which takes a pair (A, B) to a diagram of the form (5.2).

The fact thatAand idAcan be taken as a product diagram for any object Aof any category means that every category can be given a canonical unary product structure. This is why the distinction betweenAandA¹can be and often is ignored.

5.3.9 Definition A category hasfinite productsor is acartesian cat-egory if the product of any finite number of objects exists. This includes nullary products – in particular, a category with finite products has a ter-minal object. The category hascanonical finite products if every finite list of objects has a specific given product.

The following proposition is proved using constructions generalizing those of 5.3.3. (See Exercises 1.c and 6.)

5.3 Finite products 173 5.3.10 Proposition If a category has a terminal object and binary prod-ucts, then it has finite products.

5.3.11 Set,GrfandCatall have finite products. In fact, a choice of defi-nition for ordered pairs inSetprovides canonical products not only forSet but also forGrf andCat, since products in those categories are built using cartesian products of sets.

5.3.12 Products and initial objects The notation A⁰, A¹, A² and so on that we have introduced, plus isomorphisms such as A×B ∼=B×A (5.2.12) and (A×B)×C∼=A×(B×C) (5.3.4), suggest that other algebraic laws may hold for products. One candidate is A×0∼= 0, where 0 denotes the initial object. This is false in general. For example, inMon the initial object is the one-element monoid (which is also the terminal object), and its product with any monoidM isM by Exercise 5 of Section 5.1.

It is important in such areas as programming language semantics and categorical logic that a category have the propertyA×0∼= 0. It is equivalent to another property, as the following proposition states. We include its proof here because it uses several ideas we have introduced.

We denote an initial object by 0 and the unique map to an objectA is denoted ! : 0−→A. As before, a terminal object is denoted 1 and the unique map from an objectAis denotedhi:A−→1.

5.3.13 Proposition LetC be a category with products and an initial object.

Then the following two statements are equivalent.

(i) For every object A, if there is an arrow u:A −→ 0, then A is iso-morphic to0.

(ii) For every objectA,0×Ais isomorphic to 0.

In any category, if the initial object has this property, it is called astrict initial object.

Proof. If (i) is true, the mapp1: 0×A−→0 serves to force 0×A∼= 0. If (ii) holds, the following must be a product diagram.

0 A

0 id₀ ¡

¡¡

ª @ !

@@R

(Since 0×Ais isomorphic to 0, there has to be such a product diagram with 0 as vertex, and there is only one possible arrow for each projection.) That

means this diagram must commute:

0¾ 0

id0 -A

! A u ¡

¡¡

ª u? idA

@@@R (5.24)

The commutativity of the right triangle says thatuis a split monic. Since any arrow to an initial object is epimorphic, the result follows from Propo-sition 2.9.10.

5.3.14 Record types To allow operations depending on several variables in a functional programming languageL(as discussed in 2.2.1), it is reason-able to assume that for any typesAandB the language has a record type P and two field selectorsP ^◦A:P −→A and P ^◦B :P −→B. If we insist that the data inP be determined completely by those two fields, it follows that for any pair of operationsf :X −→Aandg:X−→B there ought to be a unique operationhf, gi:X −→P with the property thatP ^◦A^◦hf, gi=f andP ^◦B^◦hf, gi=g. This would makeP the product ofAandB with the selectors as product projections.

For example, a record type PERSON with fields NAME and AGE could be represented as a product cone whose base diagram is defined on the discrete graph with two nodesNAMEand AGE. If HUMANis a variable of typePERSON, then the field selectorHUMAN.AGE implements the coordinate projection in-dexed byAGE. This example is closer to the spirit of category theory than the cone in Diagram (5.2); there, the index graph has nodes 1 and 2, which suggests an ordering of the nodes (and the projections) which is in fact spurious.

Thus to say that one can always construct record types in a functional programming languageLis to say that the corresponding categoryC(L) has finite products. (See Poign´e, [1986].)

5.3.15 Functors that preserve products LetF :A −→Bbe a functor between categories. Suppose that

A₁ A₂

A p1

¡¡

¡¡ ª

p2

@@

@@R

(5.25)

5.3 Finite products 175 is a (binary) product diagram inA. We say thatF preserves the product if

is a product diagram inB. It is important to note thatF must preserve the diagram, not merely the objectA. It is possible forF to takeAto an object which is isomorphic to a product, but do the wrong thing on projections (Exercise 4).

F preserves canonical productsifA andBhave canonical products andF preserves the canonical product diagrams.

Similar definitions can be made about a product diagram of any family of objects. A functor is said topreserve finite products, respectivelyall productsif it preserves every finite product diagram, respectively all prod-uct diagrams. Preserving canonical prodprod-uct diagrams is defined analogously (but note Exercise 5.b).

We have a proposition related to Proposition 5.3.10.

5.3.16 Proposition If a functor preserves terminal objects and binary products, it preserves all finite products.

Two important examples of this is given by Propositions 5.3.17 and 5.3.18 below.

5.3.17 Proposition Any covariant hom functor preserves products.

Proof. A covariant hom functor preserves terminal objects by Exercise 11 of Section 3.3. Now suppose

A B

A×B

p1¡ª¡ @@Rp2 (5.26)

is a product diagram. We must show that for any objectC,

Hom(C, A) Hom(C, B)

is a product diagram inSet. In 5.2.7, we defined the function πC: Hom(C, A)×Hom(C, B)−→Hom(C, A×B)

which is a bijection that takes (f, g) tohf, gi. Letq1: Hom(C, A)×Hom(C, B)

−→Hom(C, A) be the first coordinate function (f, g)7→f in Set, and simi-larly forq2. Then

Hom(C, p1)hf, gi=p1^◦hf, gi=f =q1(f, g)

and similarly Hom(C, p2)hf, gi=q2(f, g), sopi^◦πC=qi fori= 1,2. Hence Diagram (5.27) is a product diagram inSetby Proposition 5.2.3.

IfF is a functor that preserves products, then any functor isomorphic to it preserves products (Exercise 7), so that it follows from Proposition 5.3.17 that any representable functor preserves products.

5.3.18 Proposition The second Yoneda embedding J :C −→Func(C^op,Set) (see 4.5.5) preserves products.

Proof. By definition,J(C) = Hom(−, C) for an objectC ofC, and iff :C

−→D,J(f) = Hom(−, f) : Hom(−, C)−→Hom(−, D). For each X inC,

Hom(X, A) Hom(X, B) Hom(X, A)×Hom(X, B)

p1 ¡

¡¡

ª @ p2

@@R

(wherep1 and p2 are the ordinary projections inSet) is a product cone in Set. Letπ1: Hom(−, A)×Hom(−, B)−→Hom(−, A) be the natural trans-formation whose component atX isp1, and similarly defineπ2. Then by the proof of Proposition 5.2.20,

Hom(−, A) Hom(−, B) Hom(−, A)×Hom(−, B)

π1 ¡

¡¡

ª @ π2

@@R

is a product cone inFunc(C^op,Set). It is easy to show that the diagram Hom(−, A)×Hom(−, B) π- Hom(−, A×B)

Hom(−, A) π1

@@

@@@R

Hom(−, p1)

¡¡

¡¡

¡ ª

5.3 Finite products 177 commutes, whereπ1 is an instance of the natural transformation defined in Proposition 5.2.14. A similar diagram forπ2 also commutes. It now follows from Proposition 5.2.3 that

Hom(−, A) Hom(−, B) Hom(−, A×B) Hom(−, p1) ¡

¡¡

ª @ Hom(−, p2)

@@R

is a product diagram inFunc(C^op,Set), which is what is required to show thatJ preserves binary products. It is easy to show that it preserves terminal objects.

5.3.19 Infinite products There is no difficulty in extending the defini-tion of products to allow infinitely many objects. SupposeIis an arbitrary set and{A_i}, i∈Iis an indexed set of objects of the categoryC. (See 2.6.11.) A product of the indexed set is an objectP ofA together with an indexed set of arrowsp_i:P −→A_i, i∈I, such that given any objectAofA together with arrowsq_i:A−→A_i, fori∈I, there is a unique arrowq=hq_ii:A−→P such thatpi^◦q=qi, for all i∈I. The product P is denoted by^Q_i∈IAi or simply^QAi.

5.3.20 Exercises

1. a.Show that assumingB×C andA×(B×C) (along with the required projections) exist, then the latter with appropriately defined projections is a ternary productA×B×C.

b. Show thatp:B−→Ais a unary product diagramif and only if p is an isomorphism.

c.Show that a category which has binary products and a terminal object has finite products.

2. LetC be a category with the following properties.

(i) For any two objects A and B there is an object A×B and arrows p1:A×B−→Aandp2:A×B−→B.

(ii) For any two arrows q1 :X −→A and q2: X −→B there is an arrow hq1, q2i:X −→A×B.

(iii) For any arrows q1 :X −→A and q2 :X −→B, p1^◦hq1, q2i=q1 and p2^◦hq1, q2i=q2.

(iv) For any arrowh:Y −→A×B,hp1^◦h, p2^◦hi=h.

Prove thatC has binary products. (This exercise shows that the property of having binary products can be expressed using rewrite rules.)

3. Show that the underlying functorU :Cat−→Grf defined in 3.1.10 pre-serves products.

4.† Give an example of categories C and D with products and a functor F :C −→D which does not preserve products, but for which nevertheless F(A×B)∼=F(A)×F(B) for all objects A and B of C. (Hint: Consider the category whose objects are countably infinite sets and arrows are all functions between them.)

5. a.Show that a functor which preserves terminal objects and binary prod-ucts preserves finite prodprod-ucts.

b.Give an example of categoriesC andDwith canonical finite products and a functorF:C −→D which preserves canonical binary products which does not preserve canonical finite products.

6. LetN be the set of nonnegative integers with the usual ordering. Show that the category determined by (N,≤) has all binary products but no ter-minal object.

7. LetF, G:C −→Dbe naturally isomorphic functors and suppose

A B

P p2 ¡

¡¡

ª @ p1

@@R

is a product diagram inC. Show that if either of the diagrams

F(A) F(B)

F(P) F(p1) ¡

¡¡

ª @ F(p2)

@@R

G(A) G(B)

G(P) G(q1) ¡

¡¡

ª @ G(q2)

@@R

is a product diagram inDthen so is the other. (Hence if a functor preserves products then so does any functor isomorphic to it.)

5.4 Sums

A sum in a category is a product in the dual category. This definition spells that out:

5.4.1 Definition The sum, also called the coproduct, A+B of two objects in a category consists of an object calledA+Btogether with arrows

5.4 Sums 179

The arrowsi1 andi2are called thecanonical injectionsor the inclu-sions even in categories other than Set. These arrows need not be mono-morphisms (Exercise 5).

5.4.2 More generally, one can define the sum of any finite or infinite in-dexed set of objects in a category. The sum of a familyA1, . . . , Anis denoted P_n

i=1Anor^`n_i=1An(the latter symbol is the one typically used by those who call the sum the ‘coproduct’). Theorems such as Theorem 5.2.2 and Propo-sitions 5.2.3, 5.2.11 and 5.3.2 are stateable in the opposite category and give uniqueness theorems for sums (this depends on the fact that isomorphisms are isomorphisms in the opposite category). The functor represented by the sum ofAandB is Hom(A,−)×Hom(B,−) and the universal element is the pair of canonical injections. (Compare Proposition 5.2.14 and the discussion which follows.)

5.4.3 Definition A binary discrete cocone in a category C is a dia-gram of the form

5.4.4 The notions of a category having sums or of having canonical sums, and that of a functor preserving sums, are defined in the same way as for products. The notion corresponding tof×gfor two arrowsfandgis denoted f+g(Exercise 1).

5.4.5 Sums in Set In the category of sets, one can find a sum of two sets in the following way. IfS andT are sets, first consider the case thatS andT are disjoint. In that case the setS∪T, together with the inclusion

functions S −→S∪T ←−T is a sum cocone. Given f : S −→C and g :T

−→C, thenhf|gi(s) =f(s) for s∈S andhf|gi(t) =g(t) for t∈T. In this case, the graph ofhf|giis the union of the graphs off andg.

In the general case, all we have to do is find setsS⁰andT⁰isomorphic to SandT, respectively, that are disjoint. The union of those two sets is a sum ofS⁰andT⁰ which are the same, as far as mapping properties, asS andT. The usual way this is done is as follows: let

S⁰=S0={(s,0)|s∈S} and T⁰=T1={(t,1)|t∈T}

These sets are disjoint since the first is a set of ordered pairs each of whose second entries is a 0, while the second is a set of ordered pairs each of whose second entries is a 1. The arrow i1:S −→S⁰∪T⁰ takes s to (s,0), and i2

takes t to (t,1). If f :S−→C andg :T −→C, then hf|gi(s,0) =f(s) and hf|gi(t,1) =g(t).

Note that it will not do to write S0=S× {0} andT1 =T × {1} since our specification of products does not force us to use ordered pairs and, in fact,S is itself a possible product ofSwith either{0}or{1}.

Our notationS+T for the disjoint union of two sets inSetconflicts with a common usage in whichS andT are sets of numbers andS+T denotes the set of all their sums. For this reason, many use the notationSqT for what we callS+T. We will use the notationS+T here but will remind you by referring to it as the disjoint union.

5.4.6 Sums and products in posets Theleast upper boundor su-premumof two elementsxandyin a poset is an elementzwith the property that x≤z, y ≤z (z is thus an upper bound) and if for some element w, x≤wandy≤w, then necessarilyz≤w(zis the – necessarily unique – least upper bound). In the category corresponding to the poset, the supremum of two elements is their categorical sum. We have already seen the dual idea of greatest lower bound or infimum in 5.1.8.

A poset whose corresponding category has all finite sums is called asup semilattice or an upper semilattice. The sup of s and t is generally denoted s∨t and the minimum element (initial object) is denoted 0. In this situation, the minimum element is often called ‘bottom’. A poset with all finite products is similarly an inf semilattice or lower semilattice.

A homomorphism of sup semilattices is a function such thatf(s∨t) = f(s)∨f(t). Such a function is monotone because ifs≤t thent=s∨t.

A poset with both finite sups and finite infs is a lattice. Some authors assume only binary sups and infs so that a lattice need not have a maximum or minimum element. A good source for the theory of lattices is [Davey and Priestley, 1990].

In document 1 MICHAELBARRANDCHARLESWELLS CATEGORYTHEORYFORCOMPUTINGSCIENCE (Stránka 189-200)