Introduction to Category Theory/Products and Coproducts

Product

One of the features of category theory is how it unifies very disparate phenomena. The product construction comprises for example both the cartesian product of sets, and the greatest lower bound (meet) of posets and lattices. Here's a definition:

Definition

Universal property of product.

The product of objects A and B is an object P together with the morphisms $\pi _{1}:P\to A$ and $\pi _{2}:P\to B$ that satisfy the following universal property:

• If $X$ is any object in the category, and $f_{1}:X\to A$ and $f_{2}:X\to B$ are any morphisms, then there exists a unique morphism $g:X\to P$ such that $f_{1}=\pi _{1}\circ g$ and $f_{2}=\pi _{2}\circ g$. In other words there is one and only one morphism g such that both triangles in the diagram commute.

The universal property has two parts:

1. There exists a morphism g.
2. The morphism g is unique.

The object P alone isn't a product. The product consists of the object P and two morphisms $\pi _{1}\;$ and $\pi _{2}\;$. Often these morphisms are clear from the context, and we simply say let $A\times B$ be the product of A and B without specifying the morphisms.

Category without the product AxB.

Not every category has products for all pairs of objects (i.e. 'has all products'). For example in the category with 3 objects and 2 arrows (+identity arrows) shown at right, the product of A and C is the object A together with morphisms $1_{A}\;$ and $A\to C$. But this category has no product $A\times B$ (why?).

The following proposition allows us to speak of the product of A and B.

Proposition. The product of any two objects is unique up to isomorphism.

Proof. If $(P,\pi _{1},\pi _{2})\;$ and $(X,f_{1},f_{2})\;$ are both products of $A$ and $B$, then by the first part of universal property there are morphisms $g:X\to P$ and $h:P\to X$ such that

${\begin{cases}f_{1}=\pi _{1}\circ g\\f_{2}=\pi _{2}\circ g\end{cases}}$ and ${\begin{cases}\pi _{1}=f_{1}\circ h\\\pi _{2}=f_{2}\circ h\end{cases}}$

Therefore

${\begin{cases}f_{1}\circ 1_{X}=f_{1}=\pi _{1}\circ g=f_{1}\circ h\circ g\\f_{2}\circ 1_{X}=f_{2}=\pi _{2}\circ g=f_{2}\circ h\circ g\end{cases}}$

and by the uniqueness part of the universal property of X, we must have $1_{X}=h\circ g$. By similar argument $1_{P}=g\circ h$ by the universal property of P. Thus g and h are inverses of each other, and P and X are isomorphic. $\Box$

Here is an alternative definition, where we leverage our earlier work on terminal objects, and define the product as a terminal object in a spinoff category. If you compare the two closely, you'll see that they're really not very different at all, just different packaging of the same ideas.

We say that a category 'has products' when there is a product for every pair of objects in the category. It is possible for a category to have products for some but not all pairs of objects. We say that a category has 'designated products' when there is some specific technique for manufacturing the product from the objects of the pair. Cartesian products of sets, discussed in the examples section below, provide an example of designated products.

Examples

Proposition. The cartesian product of non-empty sets is a product in the category of sets.

Proof. Let A and B be any non-empty sets, $A\times B$ their cartesian product set, and $\pi _{1},\pi _{2}\;$ the canonical coordinate projection maps. We must prove that $A\times B$ satisfies the universal property of product.

Let X be any set and let $f_{1}:X\to A$ and $f_{2}:X\to B$ be any functions. We construct the function $g:X\to A\times B$ by setting $g(x)=(f_{1}(x),f_{2}(x))\;$ for every element x in X. This satisfies the first part of universal property:

$(\pi _{1}\circ g)(x)=\pi _{1}(g(x))=\pi _{1}(\ (f_{1}(x),f_{2}(x))\ )=f_{1}(x)$ and

$(\pi _{2}\circ g)(x)=\pi _{2}(g(x))=\pi _{2}(\ (f_{1}(x),f_{2}(x))\ )=f_{2}(x)$.

We must prove that if $h:X\to A\times B$ is another function with $\pi _{1}\circ h=f_{1}$ and $\pi _{2}\circ h=f_{2}$, then g=h. Let x be any element in X, then h(x) is an element (a,b) in AxB, for some a in A and b in B. An easy computation shows

$f_{1}(x)=(\pi _{1}\circ h)(x)=\pi _{1}(h(x))=\pi _{1}((a,b))=a$ and

$f_{2}(x)=(\pi _{2}\circ h)(x)=\pi _{2}(h(x))=\pi _{2}((a,b))=b$.

Therefore $h(x)=(a,b)=(f_{1}(x),f_{2}(x))=g(x)\;$ for every x in X, and h=g is the unique function required by the second part of universal property. $\Box$

Note that the proposition remains true if we consider empty sets. The product $A\times \emptyset$ is $\emptyset$. Exercise: Check that the universal property holds - there are not very many sets with a map $f_{2}$ to the empty set.

More on this example below

Proposition. Intersection of subsets is a product in the powerset poset.

Proof. Let X be any set, and let A and B be any subsets of X. We must prove that the intersection $A\cap B$ has the universal property.

Let C be any subset of X such that there are arrows $C\to A$ and $C\to B$. By the definition of powerset poset, there's an arrow from C to A if and only if C is a subset of A, in other words if every element of C is an element of A. So every element of C is an element of both A and B. The definition of intersection says that an element x belongs to the intersection $A\cap B$ if and only if x belongs to both A and B. Thus C is a subset of $A\cap B$ and there is an arrow $C\to A\cap B$. Uniqueness and composition property follow from the fact that in any poset there is at most one arrow between any two objects. $\Box$

Proposition. Least common multiple lcm() is a product in the divisibility poset of positive integers.

Proof. Let a and b be positive integers. We must prove that the least common multiple of a and b, denoted lcm(a,b), has the universal property.

Let c be any positive integer divisible by both a and b. There are integers q and r (quotient and remainder), such that $c=q*{\text{lcm}}(a,b)+r\;$ with $q>0\;$ and $0\leq r<lcm(a,b)$. (Why is q positive and not zero?) Since c and lcm(a,b) are both divisible by a and b, also r must be divisible by them. But r is smaller than lcm(a,b), so r must be zero or otherwise lcm isn't the least common multiple. Thus c = q*lcm(a,b) and c is divisible by lcm(a,b). By the definition of poset there is at most one arrow between any two objects, so the uniqueness part is trivial. $\Box$

Proposition. Greatest lower bound in a poset, when it exists for two elements, is a (actually the unique, not just up to isomorphism) product of those two elements. This provides lots of examples where products might exist for some, all, or no pairs of elements in a category,

Proof. Exercise.

Products and Elements

The unique map $g\,$ above, from $C\,$ to $A\times B$, is often notated as $<f,g>\,$, using the standard ordered pair notation from set-theory. This is motivated by the special case in the category ${\mathcal {S}}et$ where $C=1$. In this case, $f\,$ and $g\,$ will be categorical 'elements', and effectively the same thing as set-theoretical elements, since a function from a one-element set picks out a unique element from its codomain. Now $<f,g>\,$ will be a categorical element of $A\times B$, that is, essentially the same thing as a set-theoretical element of $A\times B$, that is, an ordered pair whose first member is from $A\,$ and second from $B\,$.

This point is often dramatized by using variable letters such as $x,y\,$ when discussing categorical elements.

Something we get from the categorical formulation of cartesian products and ordered pairs is explicit recognition of the fact that it doesn't matter what actual construction we use to produce the ordered pairs - all that matters is the existence of the projections and the universal property, which can be seen as saying that the ordered pair must contain just enough information for the projections to extract the first components, and no more.

You can see an interactive demonstration of universality here. Clicking the "generate a product and demonstrate its universality" button will generate a product in the category of finite sets. It will also generate another object, and show the universal arrow from this to the product.

This demonstration also shows that it doesn't matter what construction we use to produce the product. Clicking the "generate a product to show that many products exist" button will generate a product that is not a set of ordered pairs, and will show its projections.

Alternative Definition

Here is an alternative definition of product, which procedes by way of a spinoff category. If it seems too hard to understand, feel free to ignore it (comments about whether it is useful would be welcome).

For any pair of objects $A,B\,$, define the 'product-maker' category $\Pi (A,B)\,$ as follows:

• the objects of $\Pi (A,B)\,$ are triples of the form $(C,f,g)\,$ where $f:C\rightarrow A$ and $g:C\rightarrow B$
• the arrows of $\operatorname {Hom} ((C,f,g),(C',f',g'))$ are the arrows $h\,$ of $\operatorname {Hom} (C,C')$ such that:
  • $f=f'\circ h$
  • $g=g'\circ h$

If you draw the commutative diagram for these equations, you'll see that, except for some of the names, it looks just like the diagram for the product, and the reason for this will become evident shortly, if you haven't seen it already. But first, you might want to work throught the details of why the product-maker for $A,B\,$ is a category (or maybe not, if the point seems obvious enough).

And so, the point of all this is the following: $A\times B$ is the/a terminal object of $\Pi (A,B)\,$.

A benefit of defining products in this way is that we don't have to bother to prove that they are unique up to isomorphism, since this is already known as a property of terminal objects. On the other hand we had to prove that the product-maker is a category.

You can see an interactive demonstration of terminality here. Clicking the "Terminality" button will generate a product object in the category of finite sets, and another object in the product-maker category, and show the arrow from that to the product.

Associativity of Product

Proposition. Product is associative, in other words if A, B, and C are objects in a category with products, then $(A\times B)\times C\cong A\times (B\times C)$. Technically, this is a 'weak' rather than 'strict' form of associativity, since we require only isomorphism, not full identity. In category theory, the weak versions of notions such as associativity are usually more important that the strict ones (although these are not always irrelevant).

Proof. The following diagram shows products and their projection morphisms. We will prove that there exist morphisms g and i that are inverses of each other.

3-product diagram.

By the universal property of the product of B and C there exists morphism f such that

${\begin{cases}q_{1}\circ f=p_{2}\circ r_{1}\\q_{2}\circ f=r_{2}\end{cases}}$

By the universal property of the product of A and BxC there exists morphism g such that

${\begin{cases}s_{1}\circ g=p_{1}\circ r_{1}\\s_{2}\circ g=f\end{cases}}$

Similarly there exists morphisms h and i such that

${\begin{cases}p_{1}\circ h=s_{1}\\p_{2}\circ h=q_{1}\circ s_{2}\end{cases}}$

${\begin{cases}r_{1}\circ i=h\\r_{2}\circ i=q_{2}\circ s_{2}\end{cases}}$

A straightforward calculation shows

${\begin{cases}q_{1}\circ s_{2}\circ g\circ i=q_{1}\circ f\circ i=p_{2}\circ r_{1}\circ i=p_{2}\circ h=q_{1}\circ s_{2}\\q_{2}\circ s_{2}\circ g\circ i=q_{2}\circ f\circ i=r_{2}\circ i=q_{2}\circ s_{2}\end{cases}}$

By the uniqueness part of the universal property of BxC it follows that $s_{2}\circ g\circ i=s_{2}$.

$s_{1}\circ g\circ i=p_{1}\circ r_{1}\circ i=p_{1}\circ h=s_{1}$

and by the universal property of Ax(BxC) we conclude that $g\circ i=1_{A\times (B\times C)}$. Similarly reader can verify that $i\circ g=1_{(A\times B)\times C}$.

Corollary 1. Cartesian product of sets is associative, that is if A, B, and C are sets, then $(A\times B)\times C\cong A\times (B\times C)$.

Proof. We have showed that cartesian product of sets is product in the category of sets, thus claim follows by abstract nonsense.

Corollary 2. Intersection of subsets is associative, that is if A, B, and C are subsets of some set X, then $(A\cap B)\cap C=A\cap (B\cap C)$.

Proof. We have showed that intersection of subsets is product in the powerset poset, and we also know that only isomorphisms in a poset are identity morphisms, thus claim follows by abstract nonsense. (But this associativity is strict rather than weak, which our present level of abstract nonsense, at least, does not suffice to prove).

Corollary 3. Least common multiple is associative, that is if a, b, and c are positive integers, then lcm(lcm(a,b), c) = lcm(a, lcm(b,c)). (strictly or weakly?)

Proof. We have showed that least common multiple is product in the divisibility poset, thus claim follows by abstract nonsense.

Remark. A preorder is a poset without the antisymmetry property. We can define a divisibility preorder that also has negative numbers. In this case n is divisible by -n for every integer n. It follows that n is isomorphic to -n, and product in preorder is associative up to isomorphism, in other words lcm(lcm(a,b), c) = ± lcm(a, lcm(b,c)).

Corollary 4. In a poset, products are strictly associative.

Proof. Exercise

Ternary and n-ary Products

What we did for pairs of objects can be carried through for triples, n-tuples or even 0-tuples. Suppose we have objects $A_{1},A_{2},A_{3}\,$, along with an object $P\,$ and arrows $\pi _{1},\pi _{2},\pi _{3}\,$ from $P\,$ to $A_{1},A_{2},A_{3}\,$, respectively. $(P,\pi _{1},\pi _{2},\pi _{3})\,$ constitutes a ternary product of $A_{1},A_{2},A_{3}\,$ iff, for any object $C\,$ and arrows $f_{1},f_{2},f_{3}\,$ from $C\,$ to $A_{1},A_{2},A_{3}\,$, respectively, there is a unique arrow $h=<f_{1},f_{2},f_{3}>:C\rightarrow P\,$such that $f_{i}=\pi _{i}\circ h$ for $i=1,2,3\,$ [DIAGRAM TO COME]

We can do likewise for any $n>1$, although the result, when written out, is one of those things that is harder to read than to compose for yourself, so is relegated to the Hints and Details section. What about the case where $n=1$, 'unary products'? If you write out the appropriate diagram (try to do this before looking), you can see that any object $A\,$ will serve as its own unary product, with the identity morphism $1_{A}\,$ as the projection. So unlike the other cases, unary products exist for all objects in any category.

So, finally, what if $n=0\,$? You might think about this and see what you come up with before reading on.

By a natural extension of the preceeding definitions, a 0-ary product in a category ${\mathcal {C}}\,$ will be some object $P\,$ of ${\mathcal {C}}$ such that for any object $C\,$ of ${\mathcal {C}}\,$, there will be a unique arrow $h:C\rightarrow P$ (no involved objects, therefore no projections, and no composition of $h\,$ with any projections). This is just a terminal object of ${\mathcal {C}}$

We are not aware of any notion of n-ary product for negative n.

Finite Products

If a category has products for all non-negative integers n, we say that it has finite products. Happily, when true, this is relatively easy to prove, because all we have to do is show that the category has terminal objects and binary products: as noted above, a terminal object is a 0-ary product, and all categories have unary products (for each object). And n-ary products for $n>2$ can be obtained by iterating binary products. For example, $(A\times B)\times C$, with the associated projections, is a fine trinary product of $A\,$, $B\,$ and $C\,$. To formulate and prove this in generality is conceptually easy, but involves a fairly high level of notational masochism, which we won't indulge in.

A category with finite products is called a cartesian category, and by now you should be able to appreciate this essay

Coproduct

Any categorical notion has a 'dual', obtained by reversing the direction of the relevant arrows. If we do this with the product, we get the co-product, defined ab initio as follows:

Definition

[DIAGRAM TO COME] Object $P\,$ and morpisms $\iota _{1}:A\rightarrow P$, $\iota _{2}:B\rightarrow P$ are the/a co-product of $A\,$ and $B\,$ iff, for any object $C\,$ and arrows $f_{1}:A\rightarrow C,f_{2}:B\rightarrow C$, there is a unique arrow $g:P\rightarrow C$ such that:

• $f_{1}=g\circ \iota _{1}$
• $f_{2}=g\circ \iota _{2}$

The coproduct object is usually written $A+B$, and the unique induced arrow $g:P\rightarrow C$ as $[f,g]\,$. The arrows $\iota _{1},\iota _{2}\,$ to the coproduct object are called injections.

You can see an example of a coproduct and its injections in this interactive demonstration. Clicking the "generate a coproduct and demonstrate its universality" will generate an example of a coproduct, with its injections.

Just as the product can be defined as a terminal object in a spinoff category, so can the co-product be defined as an initial object in such a category.

The relevant spinoff category, which I'll notate as $\coprod (A_{1},A_{2})$ has as objects triples of the form $(B,f_{1},f_{2})\,$, where $f_{i}:A_{i}\rightarrow B$. And, for arrows, the arrows of $\operatorname {Hom} ((B,f_{1},f_{2}),(C,g_{1},g_{2}))$ are those arrows $h\,$ of $\operatorname {Hom} (B,C)$ such that $g_{i}=h\circ f_{i}$ for $i=1,2\,$. Now $A+B\,$ is the/a initial object in this category.

Consequences

It follows from the above that a co-product is a product in the opposite category, which delivers many results with no additional work, such as:

• co-products are unique up to isomorphism
• co-products are associative up to isomorphism
• if there are binary co-products for all pairs of objects, there are n-ary co-products for all $n>0$

N-ary coproducts are denoted either $\bigoplus _{1\leq i\leq n}A_{i}$ or $\coprod _{1\leq i\leq n}A_{i}$.

What about 0-ary co-products? Clearly, to maintain duality, we need to define the 0-ary co-product as an initial object, and eveything then works out.

Examples

• In a poset, a co-product is a least upper bound
• A bounded lattice is a poset with finite products.
• In the category of sets, the coproduct is the disjoint union, formed from two sets by processing the members of each differently, so that the results can't overlap, and then taking the ordinary union. This coproduct is meaty enough to get more discussion below, and can be seen as the motivation for the use of the $+\,$ notation for co-products (which are, unsurprisingly, also sometimes called sums).

Disjoint Unions

Suppose we have two sets $A\,$ and $B\,$, and we wish to form a coproduct of these. We can't just take their union, with the mappings $x\mapsto x$ from $A\,$ to $A\cup B$ and $B\,$ to $A\cup B$ because they might have some elements in common, which would make it possible to come up with functions $f:A\rightarrow C$ and $g:B\rightarrow C$ such that there can't be any $[f|g]:A\cup B\rightarrow C$ meeting the conditions for a co-product (Hint). But since we're doing category theory, where we usually regard isomorphic objects as equivalent, we can in this case just grab two sets $A'\,$ and $B'\,$ which don't overlap, and are isomorphic to $A\,$ and $B\,$, respectively. Their union $A'\cup B'$, will now provide a coproduct for $A\,$ and $B\,$.

Exercises:

• what are the injections for the coproduct we've just made
• show that if we added some additional elements to $A'\cup B'$, we'd no longer satisfy the conditions for a coproduct,

Now to demonstrate the ${\mathcal {S}}et$ indeed has coproducts, we need to show that it is always possible to do this, which is typically done by a construction that maps the members of $A\,$ and $B,$ into ordered pairs with different first members, such as 0 and 1, respectively. So, formally, we might have:

• $A'=\{0\}\times A$
• $B'=\{1\}\times B$
• $\iota _{1}=a\mapsto \langle 0,a\rangle :A\rightarrow A'\cup B'$
• $\iota _{2}=b\mapsto \langle 1,b\rangle :B\rightarrow A'\cup B'$

Thanks to the role of isomorphism in category theory, we don't care whether we actually use this or any other systematic method for producing disjoint unions; this construction simply shows that there's always one to be found (proving that it works would be a drill in basic set theory).

And of course the motivation for the use of $+,$ to represent co-products is that for finite sets, if $A\,$ has $m\,$ members and $B\,$ $n\,$, then $A+B$ has $m+n$ members.

All this might be taken as pointing to one of the major basic failures of the 'new math' in the mid-to-late 20th century. I (AA) recall being told in perhaps third grade about sets and how they were the basis for everything, but they didn't seem to be able to do a decent job of explaining addition, due to the problem of what if the two sets being added overlapped? Third graders are, I believe, not generally capable of understanding disjoint unions, co-products, and the benefits of regarding isomorphic objects as identical (and I'd have my doubts about the teachers), so for people at that level, trying to present sets as the basis for everything is just a distraction from actually learning anything about numbers.

Exercise: In ${\mathcal {S}}et$, what is $1+1\,$? (naturally, it's called $2\,$, but what is it?)

Cartesian Categories and Deduction

An elementary but somewhat extended example of products (and coproducts) is logical conjunction (and) and disjunction (or). We develop this example in stages. It's a more relaxed presentation of material from Lambek & Scott (1986) Introduction to Categorical Logic Cambridge University Press.

[STILL IN NEED OF SOME CRACKFILLING, ETC]

Proofs as Morphisms

A basic idea of logic is that of logical consequence, whereby we have a conviction that, if we accept some proposition $A\,$, we should also accept some proposition $B\,$. For example, if we accept Bert is happy and Grover is sad, we should also accept Bert is happy. Logic gets going when we can begin to individuate these convictions into distinct patterns of argument, and give them names, so that solid arguments that will survive extensive criticism can be systematically identified and distinguished from delusions. The pattern of argument we just called for can be called 'case 1 of conjunction elimination', and basically says that if we accept a proposition of the form $A\,$ and $B\,$, we should also accept one of the form $A\,$. Aside from the details of what basic patterns of argument there are, two rather plausible logical principles are:

• given $A\,$, we can conclude $A\,$ (for every proposition $A\,$, there is an identity deduction $1_{A}\,$ of that proposition from that proposition)
• if there is a deduction $f\,$ of $B\,$ from $A\,$, and $g\,$ of $C\,$ from $B\,$, then there is a deduction $g\circ f$ of $C\,$ from $A\,$ (transitivity of deduction)

This is getting close to constituting a category, where the propositions are the objects and the deductions the arrows, but to go all the way, we need to impose some equivalences, in particular those for the identities, and associativity. Let $f:A\rightarrow B$ mean that we have a deduction (proof) of $B\,$ from $A\,$. Then we require:

• $1_{B}\circ f=f=f\circ 1_{A}$
• $(h\circ g)\circ f=h\circ (g\circ f)$

which are just the basic equations of category theory.

If we consider the deductions to be actual arrangements of marks on a medium such as paper or a chalkboard, this equivalences might hold 'automatically' (for example by pieces of deductions being combined without parentheses or other delimiters), or by conventions to the effect that certain combinations of symbols are deemed identical. Be this as it may, Lambek and Scott (1986) call a system with composition and identities a 'deductive system', which will be a category if the equations above are obeyed.

Conjunction as Products

Logic doesn't get very far without connectives, that is, means for combining propositions and perhaps ingredients of propositions to make more propositions. One of the more basic connectives is 'and', which, in terms of deductions, intuitively obeys these three rules (among others):

• if we accept $A\,$ and $B\,$, we feel compelled to accept $A\,$.
• if we accept $A\,$ and $B\,$, we feel compelled to accept $B\,$.
• if we feel compelled to accept $A\,$ on the basis of $C\,$, and $B\,$ on the basis of $C\,$, then we feel compelled to accept $A\,$ and $B\,$ on the basis of $C\,$.

We can formalized these intuitions as part of a deductive system by introducing a connective $\wedge$ for propositions, and assuming the following principles for constructing deductions:

• For propositions $A,B\,$, there exist the following two deductions:
  • $\pi _{A,B}^{1}\colon A\wedge B\rightarrow A$ (the first projection/case of conjunction elimination).
  • $\pi _{A,B}^{2}\colon A\wedge B\rightarrow B$ (the second projection/case of conjunction elimination).
• If there are deductions $f\colon C\rightarrow A$ and $g\colon C\rightarrow B$, then there is a deduction $\langle f,g\rangle \colon C\rightarrow A\wedge B$.

These deductions can exist independently of whether or not the identity and associative equations hold; we'll call a deductive system where they exist a 'conjunction system' (almost a conjunction calculus in the sense of Lambek and Scott, but this latter notion requires some more ingredients).

So you can perhaps perceive the looming idea that if the deductive system is a category, conjunction and the projections might constitute a product. But for this to be the case, some equations will have to hold. These are:

For all $f\colon C\rightarrow A$, $g\colon C\rightarrow B$, $h\colon C\rightarrow A\wedge B$:

• $\pi _{A,B}^{1}\circ \langle f,g\rangle =f$ (ProjEq1).
• $\pi _{A,B}^{2}\circ \langle f,g\rangle =g$ (ProjEq2).
• $\langle \pi _{1}\circ h,\pi _{2}\circ h\rangle =h$ (PairEq).

In the first two equations I've included the subscripts to the projections, while in the last, I've left them out; you should be able to write them in on the basis of the environment.

These equations are sufficient for $(A\wedge B,\pi _{A,B}^{1},\pi _{A,B}^{2})$ to constitute a product.

Proof: Suppose we have a conjunction system such that the above equations hold, and we have some $D\,$ such that there are deductions $f\colon D\rightarrow A$ and $g\colon D\rightarrow B$. We need to show that there is a unique deduction $h\colon D\rightarrow A\wedge B$ such that $f=\pi ^{1}\circ h$ and $g=\pi ^{2}\circ h$; we'll call these two equations the 'factoring requirements', the other requirement on $h\,$ being the uniqueness requirement.

Now by the rules for a conjunction system, we have $\langle f,g\rangle \colon D\rightarrow A\wedge B$, and from the equations ProjEq1 and ProjEq2, it follows that $\langle {f,g}\rangle \,$ satisfies the factoring requirements for $h\,$. Now suppose we also have $k\colon D\rightarrow A\wedge B$ that satisfies the factoring requirements. Then we have:

• $\langle {f,g}\rangle =\langle {\pi ^{1}\circ k,\pi ^{2}\circ k}\rangle =k$

which proves uniqueness. $\Box$

Exercise: Prove that 'conjunction is commutative', in the sense that in a conjunction system, there is a deduction of $B\wedge A$ from $A\wedge B$.

Exercises

1. Explain following diagram and prove that $h_{f}=h_{g}\$.
2. Prove that $(A\cap B)\cup (A\cap C)\subseteq A\cap (B\cup C)$.
3. Prove that gcd(lcm(a,b), lcm(a,c)) is divisible by lcm(a, gcd(b,c)) for any positive integers a,b,c.
4. Let $A_{1},A_{2},A_{3},\ldots \;$ be objects in category ${\mathcal {C}}$ with all finite products. Prove by induction that $\prod _{1\leq i\leq n}A_{i}$ is isomorphic to $(((A_{1}\times A_{2})\times A_{3})\ldots )\times A_{n}$ for all positive integers n.

   

   Hint: Set $B_{n}:=(((A_{1}\times A_{2})\times A_{3})\ldots )\times A_{n}$ and $C_{n}:=\prod _{1\leq i\leq n}A_{i}$.

   • Prove that $B_{1}\cong C_{1}$.
   • Assume you have proved $B_{n}\cong C_{n}\;$, and prove that $B_{n+1}\cong C_{n+1}\;$.

Hints and Details

formulation of n-ary product

for $n>0$: An n-ary product of $A_{1},\ldots ,A_{n}$ is an object $P\,$ and arrows $\pi _{1},\ldots \pi _{n}$ from $P\,$ to $A_{1},\ldots ,A_{n}$, respectively, such that for any object $C\,$ and arrows $f_{1},\ldots ,f_{n}$ from $C\,$ to $A_{1},\ldots ,A_{n}$, respectively, there is a unique arrow $h=<f_{1},\ldots ,f_{n}>:C\rightarrow P$ such that $f_{i}=\pi _{i}\circ h$, for $i=1,\ldots n$.

unary product diagram

[TO COME]

union problem

Let $f\,$and $g\,$ return different values for some member of $A\cap B$.

Related resources

• w:Product (category theory)
• w:Coproduct
• w:Distributive category
• Jocelyn Paine's interactive demonstrations about products and coproducts in the category of finite sets