Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
Convincing answer. Thank you very much. – Cyrus Aug 28 '12 at 11:58
@Cyrus and/or Zhen, does this argument work in the category of relations that are both left-total and right-total? I was thinking the product and coproduct in this case might be the usual Cartesian product. – goblin Apr 24 '13 at 11:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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