As is well known, composition of relations is defined as $$R\circ S = \{(a,b):\exists x: (a,x)\in S \land (x,b)\in R\} \tag 1$$ This is formally the very same definition as for function composition. However there's a difference: With functions, for any pair $(a,b)$ there exists at most one such $x$. For general relations, there can be any number of such $x$. Yet the definition of composition only distinguishes the two cases that there exists one or that there exists none.

Therefore it seems to me that the natural result of the composition of relations would not be a normal relation, but a multiset relation: A multiset of pairs (where arbitrary cardinalities are allowed as multiplicities). Then the multiplicity of the pair (a,b) would be the cardinality of the set of values $x$ in (1).

The natural next question would be what should be the composition of multiset relations. I think the natural extension would be to replace the "and" condition by a multiplication of multiplicities. For normal relations (where the multiplicity is either $0$ or $1$) this would reduce to the "and" condition.

Now my question is: Has anyone ever considered this sort of composition rule? Does it have any disadvantages compared to the standard definition?

  • $\begingroup$ The issue I see is that in Set theory, the target is to build sets from sets. And a multiset is not a set, right? $\endgroup$ – mathcounterexamples.net Jul 8 '15 at 21:25
  • $\begingroup$ Are you aware that this is matrix multiplication of the integer matrices corresponding to $R$ and $S$ (where each entry is $1$ if the corresponding pair is in the relation, $0$ otherwise)? $\endgroup$ – joriki Jul 8 '15 at 21:31
  • $\begingroup$ @mathcounterexamples.net: If multisets are not sets, then functions are neither, because multisets are defined as functions. $\endgroup$ – celtschk Jul 8 '15 at 21:43
  • $\begingroup$ @joriki: I wasn't aware of that. Interesting point. $\endgroup$ – celtschk Jul 8 '15 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.