Please describe direct products in the category Rel.

  • 4
    $\begingroup$ As a set it's the disjoint union, according to Wikipedia. Doesn't seem too hard to verify. $\endgroup$ Jul 25, 2012 at 18:11

1 Answer 1


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!]

  • $\begingroup$ What is "the forgetful functor"? In any case, I wouldn't call $\text{Rel}$ the category of vector spaces over $\mathbb{F}_1$; it's closer to the category of "vector spaces" over the truth semiring. $\endgroup$ Jul 25, 2012 at 19:18
  • $\begingroup$ @QiaochuYuan what is the "truth semiring"? $\endgroup$
    – magma
    Aug 1, 2012 at 13:26
  • $\begingroup$ @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). $\endgroup$ Aug 1, 2012 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.