I can't seem to wrap my head around composite relations. According to Grimaldi in "Discrete and Combinatorial Mathematics", it is defined as:

If $A, B$ and $C$ are sets with $R_1 \subseteq A \times B$ and $R_2 \subseteq B \times C$, then the composite relation $R_1 \circ R_2$ is a relation from $A$ to $C$ defined by $R_1 \circ R_2 = \{(x,z)\mid x\in A, z\in C\}$, and there exists $y\in B$ with $(x,y)\in R_1, (y,z)\in R_2$.

However, in Rosen's "Discrete Mathematics and its Applications", composite relations are defined as:

Let $R$ be a relation from a set $A$ to a set $B$ and $S$ a relation from $B$ to a set $C$. The composite of $R$ and $S$ is the relation consisting of ordered pairs $(a,c)$, where $a\in A, c\in C$, and for which there exists an element $b\in B$ such that $(a,b)\in R$ and $(b,c)\in S$. We denote composite of $R$ and $S$ by $S \circ R$.

Are these two definitions not contradicting?


Yes, they have different order. If we take first definition, then notation in second definition should be $R\circ S$ and not $S\circ R$. If you are reading first book then stick to definition in that book and if you reading second one then stick definition in that book.

| cite | improve this answer | |
  • $\begingroup$ In fact you even occasionally see composition of functions in the opposite order. Writing $x^\sigma$ for function $\sigma$ applied to element $x$, we want to define the composition $\sigma\circ\tau$ so that $x^{\sigma\circ\tau} = (x^\sigma)^\tau$. You may see this in some branches of algebra. $\endgroup$ – GEdgar Feb 23 '19 at 14:27
  • $\begingroup$ So this was no help to you? $\endgroup$ – Aqua Jun 14 at 13:53

Your Answer

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

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