Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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