# Is $\mathbf{Rel}$ pre-additive?

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

-
I don't believe so. Composition preserves $\cup$ but not $\cap$. –  Zhen Lin Jun 8 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 at 17:29

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.

-
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.
$\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 at 19:45