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.

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

I first fix some notation: the objects are given by Ob Rel = Ob Set. The morphisms are given by $\hom(A,B)= \mathcal{P}(A \times B)$. Let $R \colon A \to B$ and $S \colon B \to C$. Composition is given by $(a,c) \in S \circ R \iff \exists b ~ \text{s.t.} ~ (a,b) \in R ~ \text{and} ~ (b,c) \in S$.

This category, correct me if I am wrong, is semi-additive with both product and coproduct given by disjoint union.

I wish to know if it is additive. Can one enrich the hom-sets with a group structure bilinear with respect to composition? I propose the following group structure:

$R+S := (R \cup S) - (R \cap S)$

share|cite|improve this question
I don't believe so. Composition preserves $\cup$ but not $\cap$. – Zhen Lin Jun 8 '13 at 16:58
Yep, I found a counter-example already in $\mathrm{End}(\{1,2\})$. Does this mean no group structure exists that makes $\mathrm{Rel}$ pre-additive though? – Aaron McBride Jun 8 '13 at 17:29
up vote 5 down vote accepted

You can think about morphisms in $\text{Rel}$ as being matrices over a particular semiring, namely the truth semiring $\{ 0, 1 \}$. This is the semiring of subsets of a one-element set, with addition given by union (not symmetric difference!) and multiplication given by intersection. Equivalently, it's the semiring $\text{End}(1)$ in $\text{Rel}$.

This semiring is manifestly not a ring, since its addition operation is not cancellative, so there's no reason to expect additivity. The same reasoning applies to categories of matrices over more general semirings.

share|cite|improve this answer

Given a category $\mathcal{C}$ with a zero object and a biproduct (i.e. coproduct canonically isomorphic to product), there is (up to isomorphism) at most one additive structure on $\mathcal{C}$. Indeed, given $f, g : X \to Y$, we must have: $$f + g = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} f & 0 \\ 0 & g \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \nabla \circ (f \oplus g) \circ \Delta$$ In particular, for $\mathbf{Rel}$, this gives $\cup$ as the binary operation on hom-sets. This is not cancellative, so there is no way of making $\mathbf{Rel}$ into an additive category.

share|cite|improve this answer
Do you have a good reference for this statement? I don't know what the triangle symbols represent, and I would like to look into it in more detail. – Aaron McBride Jun 9 '13 at 18:50
$\Delta : X \to X \times X$ is the diagonal morphism, and $\nabla : X \amalg X \to X$ is the codiagonal morphism. – Zhen Lin Jun 9 '13 at 19:45
@Aaron: the only place I know where this material is written up is… (but I am sure it exists in a real book somewhere). The uniqueness statement follows from the corollary which states that a functor between semiadditive categories is enriched iff it preserves biproducts. – Qiaochu Yuan Jun 10 '13 at 18:16

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.