# Products in the category of sets and (left-)total relations

By a total (or left-total) relation I mean a binary relation $R \subseteq X \times Y$ where there is, for each $x \in X$, at least one $y \in Y$ with $(x,y) \in R$. Equivalently stated, I mean relations under which the projection to the first coordinate is a surjection.

I would now like to look at the category where

• the objects are all sets,
• the morphisms between two sets $X,Y$ are all total relations $R \subseteq X \times Y$ and
• the composition of two total relations $R \subseteq X \times Y$ and $S \subseteq Y \times Z$ is given as follows: $S \circ R := \{(x,z) \mid \exists y \in Y: (x,y) \in R, (y,z) \in S\}$.

What is the product of two sets in this category (if it exists at all)? I know that it would be the disjoint union if one took ALL relations as morphisms, but I think that this is not the case here.

Can anyone help?

-

By definition, if a product $X \otimes Y$ exists in your category $\textbf{Rel}_\textrm{l.t.}$, then it must give a bijection $$\textbf{Rel}_\textrm{l.t.}(Z, X \otimes Y) \cong \textbf{Rel}_\textrm{l.t.}(Z, X) \times \textbf{Rel}_\textrm{l.t.}(Z, Y)$$ Consider the case $Z = 1$.To give a left-total relation $Z \to X$ is the same thing as to give a non-empty subset of $X$. So, if $X$ and $Y$ are finite sets of cardinality $n$ and $m$, respectively, the RHS has cardinality $(2^n - 1)(2^m - 1)$. But, assuming $n > 1$ and $m > 1$, $$(2^2 - 1)(2^2 - 1) = 2^{n+m} - 2^n - 2^m + 1 \equiv 1 \not\equiv -1 \pmod 4$$ so there is no chance of $X \otimes Y$ existing in this case. (On the other hand, $1 \otimes X \cong X$ and $0 \otimes X \cong 0$.)