Multi- and Polymorphisms
Multipmorphism and binary product
For each two objects in a category there exists a product that combines them, for example a deck of poker-cards represents the cartesian product of ranks
$$R={2,3,4,5,6,7,8,9,10,J,K,Q,A}$$
and colors
$$C=\{\heartsuit,\diamondsuit,\spadesuit,\clubsuit\}$$
Every combination of these sets represents exactly one card in the deck. The set of poker-cards is written as \(R\times F\). An alternative example can be found in the world of databases, in which SELECT * FROM A,B represents the cartesian product of tables A and B. The most important property of these products is that there are two morphisms \(p_1:A\times B\rightarrow A\) and \(p_2:A\times B\rightarrow B\). These morphisms map a product to its components, in the case of poker cards these would be \(r:R\times C\rightarrow R\) and \(c:R\times C\rightarrow C\) that map from a card to its rank/color.
Based on these morphisms, we can now define the multimorphism as follows:
Definition
Let \(A\) and \(B\) be objects in the category \(\mathcal{C}\). The product \(A\times B\) is given by two morphisms \(p_1:A\times B\rightarrow A\) and \(p_2:A\times B\rightarrow B\) that satisfy the following property. For all Objects \(Z\) with morphisms \(f: Z\rightarrow A\) and \(g:Z\rightarrow B\) there exists a morphism \(\langle f,g\rangle :Z\rightarrow A\times B\) with \(f=p_1\circ\langle f,g\rangle\) and \(g=p_2\circ\langle f,g\rangle\). The morphism \(\langle f,g\rangle\) is then called the multimorphism.
For a better understanding take a look at the commutating diagram.
Relating the definition to the example with poker-cards this means that, if there exist morphisms from an object \(Z\), which map from this object to the set of ranks \(R\) and respectively the set of colors \(C\). It follows that the combination of these morphisms results in a multimorphism that maps from \(Z\) directly to a card. Let \(Z={x\in\mathbb{N}:1\leq x\leq 52}\) and let \(c\) and \(g\) be defined as:
$$c: x\mapsto \begin{cases}2 & x\equiv_{13}1\\3 & x\equiv_{13}2\\\vdots\\A & x\equiv_{13}0\end{cases}$$
$$g:x\mapsto \begin{cases}
\heartsuit & 1\leq x\leq 13\\
\diamondsuit & 14\leq x\leq 26\\
\spadesuit & 27\leq x\leq 39\\
\clubsuit & 40\leq x\leq 52\end{cases}$$
The resulting multimorphism \(\langle c,g\rangle\) is trivially equivalent to \(\langle c,g\rangle: x\mapsto (c(x),g(x))\). So the morphism that maps a number from \(Z\) to the pair of rank and color – which defines a card. The prerequisite that \(p_1\) and \(p_2\) map the resulting card back to the original color \(c\) and rank \(g\) is obviously given.
Polymorphism and binary coproduct
In category theory it is possible to construct a commutating diagram that is dual to another diagram by just reversing all contained arrows. Starting from the diagram of binary products this leads to the diagram of the binary coproduct.
Definition
Let \(A\) and \(B\) be objects in the category \(\mathcal{C}\). The coproduct \(A+B\) is given by two morphisms \(q_1: A\rightarrow A+B\) and \(q_2: B\rightarrow A+B\) that satisfy the following property. For all objects \(Z\) with morphisms \(f:A\rightarrow Z\) and \(g:B\rightarrow Z\) there is a morphism \([f,g]:A+B\rightarrow Z\) with \(f=[f,g]\circ q_1\) and \(g=[f,g]\circ q_2\). The morphism \([f,g]\) is called polymorphism or co-multimorphism.
Even though it looks remarkably simmilar the coproduct is entirely different from the product. Given two sets the coproduct would represent the disjoint union of the sets. If the sets are disjoint -- meaning they have no common elements -- this is equivalent to the regular union of the sets \(A\cup B\). If however the sets have common elements, it is necessary to 'mark' these elements in order to trace their origin (\(x_A \neq x_B\))
The coproduct of \(R\) and \(C\) would be
$$R+C=\{2,3,4,5,6,7,8,9,10,J,Q,K,A,\heartsuit,\diamondsuit,\spadesuit,\clubsuit\}$$
A very special object on the other hand is the polymorphism \([f,g]: A+B\rightarrow Z\). As the dual concept to the multimorphism its domain is the disjoint union of \(f\) and \(g\). Because of this, the polymorphism is capable to map elements from both these domains to its codomain. Its definition is analogous to a if/else-statement:
$$[f,g]: x\mapsto \begin{cases}
f(x) & x\in A\\
g(x) & x\in B
\end{cases}$$
so \([f,g](x)\) is identical to \(f(x)\) if \(x\) is from \(A\) and identical to \(g(x)\) if \(x\) is from \(B\).
Preview
Next time we'll talk about product and coproduct morphisms and how to parallelize computations.
