** Products and sums**

**5.2 Notation for and properties of products**

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

### 5.2 Notation for and properties of products

5.2.1 Consider setsS ={1,2,3},T ={1,2} andU ={1,2,3,4,5,6}.
De-fine proj_{1}:U −→S and proj_{2}:U −→T by this table:

u proj_{1}(u) proj_{2}(u)

Since the middle and right columns give every possible combination of a
number 1, 2 or 3 followed by a number 1 or 2, it follows thatU, together
with proj_{1} and proj_{2}, is a product of S and T. For example, ifq1:V −→S
andq2:V −→T are given functions and q1(v) = 1, q2(v) = 2 for somev in
V, then the unique functionq:V −→U satisfying 5.1.3 must take vto 5.

In effect, proj_{1}and proj_{2}code the ordered pairs inS×T into the setU.
As you can see, any choice of a six-element set U and any choice of proj_{1}
and proj_{2}which gives a different element ofU for each ordered pair inS×T
gives a product ofS andT.

This example shows that the categorical concept of product gives a more general construction than the cartesian product construction for sets. One cannot talk about ‘the’ product of two objects, but only of ‘a’ product.

However, the following theorem says that two products of the same two objects are isomorphic in a strong sense.

5.2.2 Theorem LetC be a category and letAandB be two objects ofC.

are both product diagrams. Then there is an arrow, and only one, fromCto D such that

commutes and this arrow is an isomorphism.

5.2 Properties of products 159 The proof we give is quite typical of the kind of reasoning common in category theory and is worth studying, although not necessarily on first reading.

Proof. Let the projections be p1 :C −→A, p2:C −→B, q1 :D −→A and q2:D−→B. In accordance with 5.1.3, there are unique arrows p:C−→D andq:D−→C for which

p1^{◦}q = q1

p2^{◦}q = q2

q1^{◦}p = p1

q2^{◦}p = p2

(5.6)

Thus we already know there is exactly one arrow (namely p) making Dia-gram (5.5) commute; all that is left to prove is that p is an isomorphism (with inverseq).

The arrowq^{◦}p:C−→Csatisfies

p1^{◦}q^{◦}p=q1^{◦}p=p1=p1^{◦}idC

p2^{◦}q^{◦}p=q2^{◦}p=p2=p2^{◦}idC

and by the uniqueness part of 5.1.3, it follows thatq^{◦}p= idC. If we exchange
thep’s andq’s, we similarly conclude thatp^{◦}q= idD and hence thatpand
qare isomorphisms which are inverse to each other.

The following proposition is a converse to Theorem 5.2.2. Its proof is left as an exercise.

5.2.3 Proposition Let

A B

C
proj_{1} ¡

¡¡

ª @ proj_{2}

@@R

be a product diagram, and suppose that an objectD is isomorphic to C by an isomorphismi:D−→C. Then

A B

D
proj_{1}^{◦}i ¡

¡¡

ª @ proj_{2}^{◦}i

@@R

is a product diagram.

5.2.4 Categorists specify the product of two sets by saying that all they care about an element of the product is what its first coordinate is and what its second coordinate is. Theorem 5.2.2 says that two structures satisfying this specification are isomorphic in a unique way.

The name ‘(s, t)’ represents the element of the product with first coor-dinatesand second coordinate t. In a different realization of the product,

‘(s, t)’ represents the element of that product with first coordinate s and second coordinate t. The isomorphism of Theorem 5.2.2 maps the repre-sentation in the first realization of the product into a reprerepre-sentation in the second. Moreover, the universal property of product says that any name

‘(s, t)’ with s∈S andt∈T represents an element of the product: it is the
unique elementx∈S×T with proj_{1}(x) =sand proj_{2}(x) =t.

In traditional approaches to foundations, the concept of ordered pair (hence the product of two sets) is defined by giving a specific model (or what a computer scientist might call an implementation) of the specification.

Such a definition makes the product absolutely unique instead of unique up to an isomorphism. We recommend that the reader read the discussion of this point in [Halmos, 1960], Section 6, who gives a beautiful discussion of (what in present day language we call) the difference between a specification and an implementation.

In categories other than sets there may well be no standard implemen-tation of products, so the specification given is necessary. In Chapter 15, we will discuss a category known as the category of modest sets in which any construction requires the choice of a bijection betweenNandN×N. There are many such, and there is no particular reason to choose one over another.

5.2.5 Notation for products It is customary to denote a product of objectsAandB of a category asA×B. Precisely, the nameA×B applied to an object means there is a product diagram

A B

A×B
proj_{1} ¡

¡¡

ª @ proj_{2}

@@R (5.7)

Using the name ‘A×B’ implies that there are specific, but unnamed, pro-jections given for the product structure.

IfA=B, one writes A×A=A^{2} and calls it the cartesian squareof
A.

The notations A×B and A^{2} may be ambiguous, but because of
The-orem 5.2.2, it does not matter for categorical purposes which product the
symbol refers to.

5.2 Properties of products 161 Even in the category of sets, you do not really know which setA×Bis unless you pick a specific definition of ordered pair, and the average mathematician does not normally need to give any thought to the definition because what really matters is the universal property that says that an ordered pair is determined by its values under the projections.

5.2.6 Binary operations Abinary operationon a setS is a function fromS×S toS. An example is addition on the natural numbers, which is a function + :N×N−→N. This and other familiar binary operations are usually written in infix notation; one writes 3 + 5 = 8, for example, instead of +(3,5) = 8. In mathematics texts, the value of an arbitrary binary operation mat a pair (x, y) is commonly denotedxy, without any symbol at all.

Using the concept of categorical product, we can now define the concept of binary operation on any objectSof any category provided only that there is a productS×S: abinary operationonS is an arrowS×S−→S.

The associative law (xy)z=x(yz) can be described using a commutative diagram as illustrated in 4.1.11. In that section, the diagram is a diagram in Set, but now it has a meaning in any category with products. (The meaning of expressions such as mult×S in arbitrary categories is given in 5.2.17 below.)

The more general concept of function of two variables can now be defined
in a categorical setting: an arrowf :A×B−→C can be thought of as the
categorical version of a function of two variables. This has the consequence
that a categorist thinks of a function such as f :R×R −→R defined by
f(x, y) =x^{2}+y^{2}as a function ofone variable, but that variable is a
struc-tured variable (an ordered pair). The notation we have been using would
suggest that one write this asf((x, y)) instead off(x, y), but no one does.

5.2.7 Suppose we are given a product diagram (5.7). For each pair of arrows f :C −→A and g : C −→ B requirement 5.1.3 produces a unique q:C−→A×B making the following diagram commute.

A¾ A×B

In other words, it produces a function

πC: HomC(C, A)×HomC(C, B)−→HomC(C, A×B) Thusq=πC(f, g).

5.2.8 Proposition The functionπC is a bijection.

Proof. πC is injective, since if (f, g) and (f^{0}, g^{0}) are elements of
Hom_{C}(C, A)×Hom_{C}(C, B)

both of which produce the same arrow q making Diagram (5.8) commute,
thenf = proj_{1}^{◦}q=f^{0}, and similarlyg=g^{0}.
inter-nally represents thepair of arrows (f, g) of the categoryC. Proposition 5.2.8
says that the representation is good in the sense thathf, giand (f, g) each
determine the other. Proposition 5.2.14 below says that the notationhf, gi
is compatible with composition.

We have already used the notation ‘hf, gi’ in the category of sets in 1.2.8.

5.2.10 In the case of two products for the same pair of objects, the iso-morphism of 5.2.2 translates the arrow namedhf, gifor one product into the arrow namedhf, gifor the other, in the following precise sense.

5.2.11 Proposition Suppose

are two product diagrams andφ:C−→D is the unique isomorphism given by Theorem 5.2.2. Let f :E −→A and g :E −→B be given and let u:E

−→C, v :E −→D be the unique arrows for which p1^{◦}u=q1^{◦}v =f and
p2^{◦}u=q2^{◦}v=g. Then φ^{◦}u=v.

5.2 Properties of products 163 Note that in the statement of the theorem, bothuandvcould be called

‘hf, gi’, as described in 5.2.9. The ambiguity occurs because the pair notation does not name which product ofAandBis being used. It is rare in practice to have two different products of the same two objects under consideration at the same time.

Proof. By 5.2.2,pi=qi ^{◦}φ, i= 1,2. Using this, we have q1^{◦}φ^{◦}u=p1 ^{◦}

u=f and similarlyq2^{◦}φ^{◦}u=g. Sincev is the unique arrow which makes
q1^{◦}v=uandq2^{◦}v=g, it follows thatφ^{◦}u=v.

This theorem provides another point of view concerning elements (s, t) of a productS×T. As described in 2.7.19, the elementsmay be represented by an arrows: 1−→S, and similarlytbyt: 1−→T. Then the arrowhs, ti: 1

−→S×T represents the ordered pair (s, t) whichever realization ofS×T is chosen.

5.2.12 The switch map Our notation A×B means that A×B is the vertex of a product cone with base the discrete diagramD withD(1) =A andD(2) =B. ThenB×A denotes the product given by the diagram

B A

B×A
p_{1} ¡

¡¡

ª @ p_{2}

@@R (5.10)

where we usep_{1} andp_{2}to avoid confusing them with the arrows proj_{1} and
proj_{2} of Diagram (5.7). (Of course, this is anad hoc solution. If one had to
deal with this situation a lot it would be necessary to introduce notation
such as proj^{A,B}_{1} and proj^{B,A}_{1} .) Then this is a product diagram:

A B

B×A p2 ¡

¡¡

ª @ p1

@@R (5.11)

It follows from Theorem 5.2.2 that there is an isomorphismhp2, p1i:B×A

−→A×B(called theswitch map) that commutes with the projections. Its
inverse ishproj_{2},proj_{1}i:A×B −→B×A.

5.2.13 To show that the notationhq1, q2iis compatible with composition,
we will show that the arrowsπCdefined in 5.2.7 are the components of a
nat-ural isomorphism. To state this claim formally, we need to make Hom_{C}(C, A)×
Hom_{C}(C, B) into a functor. This is analogous to the definition of the
con-travariant hom functor. Aand B are fixed and the varying object is C, so
we define the functor Hom_{C}(−, A)×Hom_{C}(−, B) as follows:

(i) [HomC(−, A)×HomC(−, B)](C) = HomC(C, A)×HomC(C, B), the set of pairs (g, h) of arrowsg:C−→Aandh:C−→B.

(ii) Forf :D−→C, let HomC(f, A)×HomC(f, B) be the arrow
Hom_{C}(C, A)×Hom_{C}(C, B)−→Hom_{C}(D, A)×Hom_{C}(D, B)
that takes a pair (g, h) to (g^{◦}f, h^{◦}f).

Now we can state the proposition.

5.2.14 Proposition

πC: Hom_{C}(C, A)×Hom_{C}(C, B)−→Hom_{C}(C, A×B)
constitutes a natural isomorphism

π: Hom(−, A)×Hom(−, B)−→Hom(−, A×B)

Proof. We give a proof in detail of this proposition here, but you may want to skip it on first reading, or for that matter on fifteenth reading. We will not always give proofs of similar statements later (of which there are many).

LetPA,B denote the functor Hom(−, A)×Hom(−, B). The projections
p1:A×B−→Aandp2:A×B−→Bfrom the product form a pair (p1, p2)∈
P_{A,B}(A×B).

5.2.15 Lemma The pair(p1, p2)is a universal element for PA,B.
Proof. The pair fits the requirements of Proposition 4.5.12 by definition of
product: if (q1, q2)∈PA,B(V), in other words ifq1:C−→Aandq2:C−→B,
there is a unique arrow q:C −→A×B such that pi^{◦}q=qi for i= 1, 2.

By 5.2.13(ii),PA,B(q)(p1, p2) = (q1, q2) as required.

Note that this gives an immediate proof of Theorem 5.2.2. See 13.2.3 for another point of view concerning (p1, p2).

Continuing the proof of Proposition 5.2.14, from Equation (4.33) it
fol-lows that the natural isomorphismαfrom HomC(−, A×B) toPA,Binduced
by this universal element takesq:V −→A×B to (p1^{◦}q, p2^{◦}q), which is
P_{A,B}(q)(p_{1}, p_{2}). Then by definition ofπ we have thatαC= (πC)^{−}^{1}, so that
πis the inverse of a natural isomorphism and so is a natural isomorphism.

It is not hard to give a direct proof of Proposition 5.2.14 using Propo-sition 5.2.8 and the definition of natural transformation. That definition

5.2 Properties of products 165 requires that the following diagram commute for each arrowf :C−→D:

Hom(D, A)×Hom(D, B) -Hom(D, A×B) πD

Hom(C, A)×Hom(C, B) πD-Hom(C, A×B)

6 6

(5.12)

In this diagram, the left arrow is defined as in Section 5.2.13 and the right arrow is defined as in Section 3.1.21. We leave the details as Exercise 3.

5.2.16 Iff :C−→D andq1:D−→Aandq2:D−→B determinehq1, q2i: D−→A×B, then the commutativity of (5.12) says exactly that

hq1^{◦}f, q2^{◦}fi=hq1, q2i^{◦}f (5.13)
In this sense, thehf, ginotation is compatible with composition.

Category theorists say that the single arrowhq1, q2iis theinternalpair of arrows with first coordinateq1and second coordinateq2. The idea behind the word ‘internal’ is that the categoryC is the workspace; inside that workspace the arrowhq1, q2iis the pair (q1, q2).

When you think ofC as a structure and look at it from the outside, you would say that the arrowq represents theexternal pair of arrows (q1, q2).

5.2.17 The cartesian product of arrows The cartesian product con-struction 1.2.9 for functions in sets can also be given a categorical definition.

Suppose that f : S −→S^{0} and g : T −→T^{0} are given. Then the composite
arrowsf ^{◦}proj_{1} :S×T −→S^{0} and g^{◦}proj_{2} :S×T −→T^{0} induce, by the
definition of product, an arrow denotedf×g:S×T −→S^{0}×T^{0}such that

S^{0}¾ S^{0}×T^{0}
proj_{1}

S¾proj_{1} S×T

? f

T^{0}
-proj_{2}

-T
proj_{2}

? g

?

f×g (5.14)

commutes. Thus f×g =hf ^{◦}proj_{1}, g^{◦} proj_{2}i. It is characterized by the
properties

proj_{1}^{◦}(f×g) =f ^{◦}proj_{1}; proj_{2}^{◦}(f×g) =g^{◦}proj_{2}

Note that we use proj_{1} and proj_{2} for the product projections among
different objects. This is standard and rarely causes confusion since the
do-mains and cododo-mains of the other arrows determine them. We will later call
themp_{1} andp_{2}, except for emphasis.

When one of the arrows f or g is an identity arrow, say f = id_{S}, it is
customary to writeS×gfor id_{S}×g.

An invariance theorem similar to Proposition 5.2.11 is true of cartesian products of functions.

5.2.18 Proposition Suppose the top and bottom lines of each diagram be-low are product cones, and that m and nare the unique arrows making the diagrams commute. Letψ:P −→Qandφ:C−→Dbe the unique

The first equality is the property ofφgiven by Theorem 5.2.2, the second by
definition of product applied toC, and the third is the defining property of
ψ. It follows thatφ^{◦}m^{◦}ψ^{−}^{1} is the unique arrow determined byh_{1}^{◦}s_{1}:Q

−→Aand h2^{◦}s2:Q−→B and the fact thatD is a product. But nis that
arrow, so thatφ^{◦}m^{◦}ψ^{−1}=n, whence the theorem.

5.2.19 Products and composition LetC be a category with products,
and supposefi:Ai−→Biand gi:Bi−→Ci fori= 1, 2, so thatg1^{◦}f1 and

5.2 Properties of products 167 and

proj_{2}^{◦}((g1^{◦}f1)×(g2^{◦}f2)) = (g2^{◦}f2)^{◦}proj_{2}
Because Diagram (5.14) commutes, we have

proj_{1}^{◦}(g_{1}×g_{2})^{◦}(f_{1}×f_{2}) = g_{1}^{◦}proj_{1}^{◦}(f_{1}×f_{2})

= g_{1}^{◦}f_{1}^{◦}proj_{1}:A_{1}×A_{2}−→C_{1}
and similarly

proj_{2}^{◦}(g1×g2)^{◦}(f1×f2) =g2^{◦}f2^{◦}proj_{2}:A1×A2−→C2

so the result follows from the uniqueness of (g1^{◦}f1)×(g2^{◦}f2).

This fact allows us to see that the product of two objects is the value of a functor. Define− × −:C ×C −→C as follows: choose, for each pair A andB ofC, a product object A×B, and let (− × −)(A, B) =A×B and (− × −)(f, g) =f ×g. Equation (5.16) shows that this mapping preserves composition and identities.

Another useful equation is the following, where we assume f :A−→C, g:B−→D,u:X−→Aandv:X −→B.

(f×g)^{◦}hu, vi=hf ^{◦}u, g^{◦}vi (5.17)
The proof is left as an exercise.

5.2.20 Proposition Let C and D be any categories. If D has products, then the functor categoryFunc(C,D)also has products.

Proof. The product is constructed by constructing the product at each value
F(C) andG(C). Precisely, given two functorsF, G:C −→D, the product in
Func(C,D) ofF andGis the functorF×Gdefined as follows. For an object
CofC, (F×G)(C) =F(C)×G(C), the product of the setsF(C) andG(C)
inD. For an arrowf :C−→D, (F×G)(f) =F(f)×G(f), the product of
the arrows as defined in 5.2.17. The projectionπ1:F×G−→F is the natural
transformation whose component atC isπ_{1}C=p_{i}:F(C)×G(C)−→F(C),
the product projection inD. For anyf :C−→D inC, the diagrams

F D×GD -F D p1

F C×GC p-_{1} F C

? F(f)×G(f)

? F(f)

F D×GD -GD p2

F C×GC p-_{2} GC

? F(f)×G(f)

? G(f)

(5.18)

commute by definition ofF(f)×G(f) (5.2.17), so thatπ1andπ2are natural transformations as required.

Given natural transformations α: H −→F and β :H −→ G, we must define hα, βi : H −→ F×G. For an object C, the component hα, βiC = hαC, βCi:H(C)−→F(C)×β(C). To see thathα, βiis a natural transforma-tion, we must show that for any arrowf :C−→D, this diagram commutes:

H(D) -F(D)×G(D) hα, βiD

H(C) hα, βiC-F(C)×G(C)

? H(f)

?

F(f)×G(f) (5.19)

This follows from the following calculation:

(F(f)×G(f))^{◦}hα, βiC = (F(f)×G(f))^{◦}hαC, βCi

= hF(f)^{◦}αC, G(f)^{◦}βCi

= hαD^{◦}H(f), βD^{◦}H(f)i

= hαD, βDi^{◦}H(f)

= hα, βiD^{◦}H(f)

in which the first and last equalities are by definition ofhα, βi, the second is by Equation (5.17), the third becauseαandβ are natural transformations, and the fourth by Equation (5.13).

Categorists say that this construction shows that Func(C,D) has ‘pointwise products’. This is the common terminology, but it might be better to say it has

‘objectwise products’.

5.2.21 Corollary The category of models of a linear sketch has products constructed pointwise.

This follows from the fact that the category of models of a linear sketch S is equivalent to the functor category Func(Th(S),Set) (see 4.6.11).

5.2.22 Exercises

1. Give explicitly the isomorphism claimed by Theorem 5.2.2 betweenS×T and the set {1,2,3,4,5,6} expressed as the product of {1,2,3} and {1,2} using the projections in 5.2.1.

2. Given a two-element set A and a three-element set B, in how many ways can the set{1,2,3,4,5,6}be made into a productA×B? (This refers to 5.2.1.)