Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please describe direct products in the category Rel.

share|improve this question
4  
As a set it's the disjoint union, according to Wikipedia. Doesn't seem too hard to verify. –  Dylan Moreland Jul 25 '12 at 18:11
add comment

1 Answer

up vote 10 down vote accepted

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

share|improve this answer
    
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. –  Qiaochu Yuan Jul 25 '12 at 19:18
    
@QiaochuYuan what is the "truth semiring"? –  magma Aug 1 '12 at 13:26
    
@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). –  Qiaochu Yuan Aug 1 '12 at 13:41
    
Thank you @QiaochuYuan –  magma Aug 1 '12 at 13:43
add comment

Your Answer

 
discard

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.