# 5. Product, Coproduct, Exponential¶

## 5.1. Product¶

There is also a categorical version of the Cartesian product of sets. This is another example of a *universal property*.

Given two objects \(A\) and \(B\) a **product** of \(A\) and \(B\) is an object \(P\) with morphisms \(p_1\colon P\to A\) and \(p_2\colon P\to B\) such that for every object \(X\) and all morphisms \(x_1\colon X\to A\) and \(x_2\colon X\to B\) there exists a unique morphism \(h\colon X\to P\) such that \(p_1\circ h=x_1\) and \(p_2\circ h=x_2\).

If the identities \(p_1\circ h=x_1\) and \(p_2\circ h=x_2\) hold, we say, “the diagram in the figure *commutes*” or “is a commuting diagram” (verb form), or “is commutative” (when we prefer an adjective).

We will make the notions *diagram* and *commutative diagram* precise later, once we have acquired the tools necessary to do so. For now, suffice it to adopt the following informal understanding of commuting diagrams.

A **commutative diagram** is a diagram with the following property: for all objects \(C\) and \(D\), all paths from \(C\) to \(D\) yield the same morphism.

More precisely, a diagram commutes iff \(\forall x \in C\), \(\varphi(x) = \psi(x)\) whenever \(\varphi = f_1 \circ \dots \circ f_m \colon C \to D\) and \(\psi = g_1 \circ \dots \circ g_n \colon C \to D\) are compositions of morphisms in the diagram with the same source and target.

Claim: | The product (if it exists) is unique up to isomorphism. |
---|---|

Proof: | Suppose that \((P,p_1,p_2)\) and \((Q,q_1,q_2)\) are two products of \(A\) and \(B\). We exhibit an isomorphism between \(P\) and \(Q\). |

Since \(P\) is a product there exists a unique morphism \(h\colon Q\to P\) such that \(p_1\circ h=q_1\) and \(p_2\circ h=q_2\). Similarly, since \(Q\) is a product there exists a unique morphism \(k\colon P\to Q\) such that \(q_1\circ k=p_1\) and \(q_2\circ k=p_2\). See the figure below.

We now show that \(h\) and \(k\) are inverses of one another. That is, we show \(h\circ k=\operatorname{id}_P\) and \(k\circ h=\operatorname{id}_Q\).

Define \(\varphi = h\circ k\). Then, since

the following diagram is commutative:

On the other hand, taking \(\varphi = \operatorname{id}_P\) obviously results in a commuting diagram as well.

Therefore, by uniqueness of \(\varphi\), we obtain \(h\circ k=\operatorname{id}_P\).

Of course, the same argument with the roles of \(P\) and \(Q\) exchanged yields \(k\circ h=\operatorname{id}_Q\) also holds.

We write \(A\times B\) to denote the product of \(A\) and \(B\). We usually use \(\pi_1 \colon A\times B \to A\) and \(\pi_2 \colon A \times B \to B\) to denote the projections and \(\left\langle x_1, x_2 \right\rangle\) for the unique map \(h\colon X\to A\times B\).

In the category \(\mathbf{Rel}\) of relational structures, the product is the **disjoint union**. We will return to this example below, once we define the *coproduct*.

## 5.2. Coproduct¶

The dual notion to the product is the *coproduct*.

Given two objects \(A\) and \(B\) in a category \(\mathcal C\) the **coproduct** (or **sum**) of \(A\) and \(B\) is denoted \(A+B\) and defined to be the object in \(\mathcal C\) with morphisms from \(A\) and \(B\) into itself that satisfy the following universal property:

If these morphisms are denote by \(\mathrm{inl} : A → A + B\) and \(\mathrm{inr} : B → A + B\), then for every object \(X\) and all morphisms \(u : A → Y\) and \(v : B → Y\) there exists a unique morphism \([u,v] : A + B → Y\) such that \([u,v] ∘ \mathrm{inl} = u\) and \([u,v] ∘ \mathrm{inr} = v\), as illustrated in the diagram below.

In \(\mathbf{Set}\) the sum is the disjoint union. That is, \(A+B=A\uplus B\).

In \(\mathbf{Rel}\) sums are also disjoint unions. This follows from \(\mathbf{Rel}\) being self-dual.

The morphisms \(\mathrm{inl}\) and \(\mathrm{inr}\) attach to each element of \(A + B\) with a tag that tells us from which object, \(A\) or \(B\), did the element come.

For instance, if \(x : A + B\), then either \(x\) denotes an element from \(A\), say, \(a :A\), in which case \(x = \mathrm{inl} a\), or else \(x\) denotes an element \(b : B\), in which case \(x = \mathrm{inr} b\).

This is important especially in case we wish to form a disjoint union of, say, two sets that have some elements in common. For example, Let \(A = \{0,1,2\}\) and \(B = \{2, 3\}\). Even though these sets are not disjoint, since \(A ∩ B = \{2\}\), we can still form the disjoint union.

More generally given two objects \(A\) and \(B\) in a category \(\mathcal C\), the coproduct of \(A\) and \(B\) is the object

For some categories the coproduct is the product. As we mentioned above, this is the case for the category \(\mathbf{Rel}\) of relational structures. Indeed, here is a diagram illustrating the (co)product in \(\mathbf{Rel}\).

The figure above displays the commutative diagram. The unique morphism that makes this diagram commute is \({\left\langle r,s \right\rangle}=\{(x,\mathrm{inl} a) : x\mathrel{r} a\}\cup \{(x,\mathrm{inr} b) : x\mathrel{s} b\}\).

## 5.3. Exponential¶

### 5.3.1. Internal reflection¶

Given two objects \(A\) and \(B\) in a category, consider the object \(B^A\).

This “represents internally” the class of all morphisms from \(A\) to \(B\).

(Some authors denote \(B^A\) by \(A \Rightarrow B\), or even \(A \to B\).)

Let \(\mathcal C\) be a category with (binary) products and let \(f_1 \colon A_1 \to B_1\) and \(f_2 \colon A_2 \to B_2\) be morphisms.

The **product morphism** of \(f_1\) and \(f_2\) is denoted by \(f_1 \times f_2 : A_1 \times A_2 \to B_1 \times B_2\) and defined by

The product of \(f_1\) and \(f_2\) is diagramed as follows:

Again, let \(\mathcal C\) be a category where all binary products exist.

Given two objects \(A\) and \(B\) from \(\mathcal C\), an object \(C\) is called an **exponential from** \(A\) **to** \(B\) iff there exists a morphism \(eval^A_B\colon C\times A\to B\) satisfying the following condition:

- for every object \(X\) and morphism \(f\colon X\times A\to B\) there is a unique morphism \(\lambda f\colon X\to C\) such that \(eval^A_B\circ(\lambda f\times\mathrm{id}_A)=f\) (so the diagram at right in the figure below commutes).

In \(\mathbf{Set}\), the exponential is just the set of functions from \(A\) to \(B\):

where \(eval : B^A \times A \to B\) is defined for each \((g, a) \in B^A \times A\) by

\[eval(g, a) = g(a)\]

and \(\lambda f : X \to B^A\) is defined for each \(X\) and \(f : X \times A \to B\) by

\[\lambda f x : a \mapsto f(x,a)\]

The category \(\mathbf{Pos}\) of partially ordered sets (or “posets”) has exponential objects. Given posets \(P\) and \(Q\) we define

In categories whose objects are sets with extra structure the exponentials are often defined by taking the set of morphisms between two objects and giving it a structure inherited from the codomain. (What happens if one tries to do this in \(\mathbf{Mon}\)?)

In the category \(\mathbf{Grph}\) the exponential is not just the set of morphisms from one object to another.

Given two graphs \(\mathcal G\) and \(\mathcal H\) the **exponential graph** \(\mathcal H^{\mathcal G}\) has

**Vertices**. \(V = V_{\mathcal G} \to V_{\mathcal H}\) (all maps from the vertices of \(\mathcal G\) to the vertices of \(\mathcal H\));**Edges**. An edge \(\alpha\) from a vertex \(f\) to a vertex \(g\) in \(\mathcal H^{\mathcal G}\) is a function \(\alpha\colon E_{\mathcal G}\to E_{\mathcal H}\) such that for every edge \((a,b)\in E_{\mathcal G}\) we have \((f(a),g(b))\in E_{\mathcal H}\).

If \(f \colon \mathcal K \times \mathcal G \to \mathcal H\), define \(\lambda f \colon \mathcal K \to \mathcal H^{\mathcal G}\) as in the following diagram:

## 5.4. Cartesian closed category¶

We now have the language to discuss a special kind of category.

A **Cartesian closed category** (CCC) is a category with a terminal object, binary products, and exponentials.

Note that we have already done the work to show that \(\mathbf{Set}\), \(\mathbf{Pos}\), and \(\mathbf{Grph}\) are Cartesian closed.

For all CCCs we have the following result.

In a Cartesian closed category \(\mathcal C\), for each triple of objects, \(A\), \(B\), \(C\), we have the following isomorphism of hom-sets:

(Here \(\cong\) simply denotes bijection of sets; i.e., \(\mathbf{Set}\)-isomorphism.)

From left to right, the isomorphism is given by the \(\lambda\) operation of exponentials.

From right to left, the isomorphism is given by **application** morphism \(ap \colon\mathrm{Hom}_{\mathcal C}(C,B^A)\to\mathrm{Hom}_{\mathcal C}(C\times A,B)\). This is the map that takes each \(g \in \mathrm{Hom}_{\mathcal C}(C, B^A)\), to the morphism \(ap(g)\colon C \times A \to B\) defined by \(ap(g) = eval \circ(g\times\mathrm{id}_A)\).

We then have

so the morphisms from \(A\) to \(B\) are in one-to-one correspondence with the global points of \(B^A\).

In \(\mathbf{Set}\) this says that the elements of \(B^A\) are the functions from \(A\) to \(B\), as expected.

In \(\mathbf{Grph}\) this says that the morphisms from the graph \(A\) to the graph \(B\) are the loops of \(\mathcal B^{\mathcal A}\)!

## 5.5. Solutions¶

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Fix \(f\) a morphism of Set. To prove \(Kf\) is a morphism of Mon, we must show that, as a function from \(KA = A^∗\) to \(KB = B^∗\), \(Kf\) preserves the monoid structure. That is, if \(w, w' \in A^\ast \).

Indeed, if \(w = a_0 \cdots a_n\) and \(w' = a'_0\cdots a'_n\), then

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).

Solution (to do).