If R and S are two relations on a set A.

Then which is the correct way to denote the composition of R and S

a) R o S or b) S o R

One author has suggested (a) and the other has suggested (b).

I am confused. Which the correct one. Please reply.(Hi)

Printable View

- Dec 7th 2009, 04:49 AMsudeepmansh[SOLVED] Composition of two relations
If R and S are two relations on a set A.

Then which is the correct way to denote the composition of R and S

a) R o S or b) S o R

One author has suggested (a) and the other has suggested (b).

I am confused. Which the correct one. Please reply.(Hi) - Dec 7th 2009, 06:53 AMPlato
Not to be too flippant about, it depends on which author wrote your textbook.

Actually, the phrase “the composition of R and S” is much too vague to really answer that question.

If you know that $\displaystyle R:A\mapsto B~\&~ S:B\mapsto C $ the domains demand that it be written $\displaystyle S \circ R :A\mapsto C$.

On the other hand, if it were $\displaystyle R:A\mapsto A~\&~ S:A\mapsto A $ the vagueness of the phrase would allow for either. - Dec 7th 2009, 09:21 AMemakarov
I agree that it is a matter of convention. When $\displaystyle R\subseteq A\times B$ and $\displaystyle S\subseteq B\times C$, then the composition of $\displaystyle R$ and $\displaystyle S$ is a subset of $\displaystyle A\times C$, and $\displaystyle (x,z)$ is in the composition if for some $\displaystyle y\in B$, $\displaystyle (x,y)\in R$ and $\displaystyle (y,z)\in S$. So to speak, $\displaystyle R$ is "applied" first and $\displaystyle S$ second, even though $\displaystyle R$ and $\displaystyle S$ are not functions and we cannot use the term "applied" in the same way we use it for functions. So far there is no ambiguity.

However, with all this, we may agree to denote the composition of $\displaystyle R$ and $\displaystyle S$ by $\displaystyle R\circ S$ or by $\displaystyle S\circ R$. This is just a notation, and as as long as we use it consistently and understand what it means, we can get away with it.

To give an illustration, in Genovia it may be an old tradition to denote 2 to the power 3 as $\displaystyle 3^2$, while the rest of the world writes $\displaystyle 2^3$. This by itself would not make the collaboration between Genovian and American mathematicians impossible because each of them understands what they are talking about. E.g., Genovians have laws like $\displaystyle x^z\times y^z=(x+y)^z$, which are exactly the same as in the rest of the world, only written in a weird way.

That said, for functions it is pretty standard to denote $\displaystyle g(f(x))$ as $\displaystyle (g\circ f)(x)$. We say "the composition of $\displaystyle f$ and $\displaystyle g$" because $\displaystyle f$ is applied first, but we write $\displaystyle g\circ f$ to remind ourselves about $\displaystyle g(f(x))$. I would say that anybody who uses a different convention intentionally tries to confuse people.

Now, functions are just special kinds of relations, so to keep the notation consistent, the composition of $\displaystyle R\subseteq A\times B$ and $\displaystyle S\subseteq B\times C$ should be denoted by $\displaystyle S\circ R$.

TL;DR: read the last paragraph.