6
$\begingroup$

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?

1 Answers 1

1

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$.)

Perhaps it's possible that products exist for infinite sets, but I have no idea what they should be.

  • 0
    Convincing answer. Thank you very much.2012-08-28