Please describe direct products in the category Rel.
Direct products in the category Rel
-
4As a set it's the [disjoint union](http://en.wikipedia.or$g$/wiki/Category_of_relations), according to Wikipedia. Doesn't seem too hard to verify. – 2012-07-25
1 Answers
As Dylan has already mentioned, the category-theoretic product in $\textbf{Rel}$ is the disjoint union of sets. We can verify this by hand: \begin{align} \textbf{Rel}(X, Y \amalg Z) & = \mathscr{P}(X \times (Y \amalg Z)) \\ & \cong \mathscr{P}((X \times Y) \amalg (X \times Z)) \\ & \cong \mathscr{P}(X \times Y) \times \mathscr{P}(X \times Z) = \textbf{Rel}(X, Y) \times \textbf{Rel}(X, Z) \end{align} This isn't too surprising, since $\textbf{Rel}$ is isomorphic to $\textbf{Rel}^\textrm{op}$ and behaves a bit like what one expects for the category of (free) vector spaces over the field of one element.
There is a categorical description of the cartesian product of sets within $\textbf{Rel}$, however. To avoid confusion, let us now write $X \otimes Y$ for the cartesian product of $X$ and $Y$. It's not hard to check that this makes $\textbf{Rel}$ into a symmetric monoidal category. Moreover, $\textbf{Rel}(X, Y) = \mathscr{P}(X \otimes Y)$, hence, $\textbf{Rel}(X \otimes Y, Z) \cong \textbf{Rel}(X, Y \otimes Z)$ so $\textbf{Rel}$ is even a monoidal closed category! Of course, this means $\textbf{Rel}$ is enriched over itself, with the internal hom being given, confusingly, by the cartesian product. (Note that the representable functor $\textbf{Rel}(1, -)$ is not the forgetful functor!) Thus, we may characterise the cartesian product as follows: it is the unique monoidal product on $\textbf{Rel}$ that has unit $1$ and admits an internal hom. (This is because every set is a coproduct of copies of $1$.)
[But how does one characterise $1$...? It's not the terminal object anymore!]
-
0@magma: the truth semiring has two elements $\top$ (true) and $\bot$ (false). Addition is given by OR and multiplication is given by AND (so this is not the finite field $\mathbb{F}_2$, where addition is given by XOR). This is a semiring because addition has no additive inverse, but that doesn't matter; semirings support enough structure that you can talk about matrix multiplication over them, and matrix multiplication over the truth semiring is precisely composition of relations (exercise). – 2012-08-01