# Composition of Relations

I'm in a bit confusion of understanding "Composition of Relations ". can someone help me up with an example.

i have basic knowledge about relations, good explanation from some expert on this topic would get me through this topic.

-
Have you tried wikipedia:en.wikipedia.org/wiki/Composition_of_relations. Exactly what is you are unable to understand ? – pritam Jul 26 '12 at 5:18
Here's an example: the relation "uncle" is the composition of "brother" and "parent", in the sense that your uncle is a brother of one of your parents. – Rahul Jul 26 '12 at 6:18

If $A$ and $B$ are sets, then a relation on $(A,B)$ is merely a subset of $A \times B$.

Suppose that $A$, $B$, and $C$ are three sets. Let $R \subset A \times B$ and $S \subset B \times C$ be binary relations on $(A,B)$ and $(B,C)$ respectively. Then $S \circ R \subset X \times Z$ a relation on $(X,Z)$ defined by

$S \circ R = \{(a,c) : (\exists b \in B)((a,b) \in R \text{ and } (b,c) \in S)\}$

Note that that $A$ and $B$ are functions, then $B \circ A$ defined above correspond to the usual function composition.

-

One example I find helpful is the notion of "multi-valued functions". Define a multi-valued function $f$ to be one which just satisfies $(\forall x)(\exists y)f(x) = y$ and not necessarily $(\forall x)(\forall y, y')f(x) = y$ and $f(x) = y'$ implies $y = y'$. Just as in the case of normal functions we can associate $f$ with its graph $G(f)$. Then the composition of relations $G(f) \circ G(g)$ corresponds to the multi-valued function $h$ where $h(x) = y$ if there is some intermediate $z$ with $g(x) = z$ and $f(z) = y$.

-

Consider three sets $X,Y,Z$ with relations $R \subset X \times Y$ and $S \subset Y \times Z$. We want to construct a new relation, $S \circ R$, between $X$ and $Z$. For motivation, let's take an example where $X$ is the set of lines in the plane, $Y$ the set of points, and $Z$ the set of closed circles with their interiors. Then we can set $(l,p) \in R$ or $l R p$ if $p$ is a point on $l$ and $(p,c) \in S$ if $p$ is in c. What's the natural candidate for $S \circ R$? Surely we want to say $(l,c)\in S \circ R$ if $l$ intersects $c$-that is, if $l$ contains $p$ in $c$.

The example says it all: we define the composition of morphisms by $(x,z) \in S \circ R$ if $\exists y: (x,y) \in R, (y,z) \in S$. In particular this is how we set up the category $Rel$ of relations. Note that with this definition in hand we can reformulate some of the central definitions of relation theory. For instance, a relation is transitive just if it's equal to its composition with itself.

Here's a simpler formulation, since I see by your comment this was confusing. Let's try composing the relation $<$ with itself of the natural numbers 1,2,3,... Call the new relation $<^2$. We say for two numbers $m,n$ that $m <^2 n$ if there's some third number $p$ with $m < p$ and $p < n$. So, what do we have? $<^2$ is just the relation between numbers at least two apart. So $1 <^2 3$ and $100 <^2 110,$ but we don't have $3 <^2 4$. For some relations, composition doesn't change anything: for instance, if two lines are both parallel to a third, then the two lines are parallel to each other.

We can also compose two different relations. Think about the two relations: (1) a line is perpendicular to another line and (2) a line intersects a circle. The composition of these relations is: a line is perpendicular to some line intersecting a circle.

-
thnks guys but the things is i'm more confuse with R⊂X×Y stuff. can you guys use example with simple english & numbers – user1419170 Jul 26 '12 at 5:25
@user1419170 $X \times Y$ is just the set of all order pairs $(a,b)$ such that $a \in A$ and $b \in B$. If $X$ is the even integers and $Y$ is the odd integers, then $(a,b) \in X \times Y$ if and only if $a$ is an even integer and $b$ is an odd integer. $R \subset X \times Y$ just states that $R$ is a subset of the set of $X \times Y$. Perhaps more familar to you, you can say that $(a,b) \in R$ then you can write $a R b$. For instance if $X = Y = \mathbb{R}$ and $R = \{(a,b) : a < b\}$, then $a R b$ is just $a < b$. So ordering is an example of a relation. – William Jul 26 '12 at 5:38
@user1419170, I added a less technical version of my answer. Hope this helps. – Kevin Carlson Jul 26 '12 at 5:40