# Find $S\circ R$ for some given relations $S$ and $R$

Suppose that $A =\left\{1,2,3\right\}$ , $B=\left\{4,5,6\right\}$

$R= \left\{(1,4),(1,5),(2,5),(3,6)\right\}$ and $S= \left\{(4,5),(4,6),(5,4),(6,6)\right\}$

Notice that that $R$ is a relation from $A$ to $B$, and $S$ is a relation from $B$ to $B$.

Find $S\circ R$

I know the definition should be something like this

$S\circ R = \left\{(a,b) A \times B \mid \exists c \in C((a,c) \in R \land (c,b) \in S)\right\}$

The answer set in back of the book is

$\left\{(1,4),(1,5),(1,6),(2,4),(3,6)\right\}$

but I am having a hard time visualizing or figuring out how they got the answer since i am assuming $c$ must equal $b$ which is an element of $B$. I tried drawing the relations with pictures but still can't make sense of it. Any help in understanding how I should be thinking would come in handy.

• In your case, $S\circ R = \left\{(a,b) A \times B \mid \exists c \in B,\,(a,c) \in R,\, (c,b) \in S\right\}$ hence if $a=1$ then $c$ can be ... hence ... – Did May 5 '17 at 5:48
• Great, I see it now. Just matching the variables to the definition. – Squanchinator May 5 '17 at 6:30

Draw $6$ nodes and label them $\{1,2,\ldots\}$. Represent $R$ by drawing an arrow joining node $x$ to $y$ for any $(x,y)$ in $R$. Do the same for $S$.
The composite relation $S\circ R$ is formed by all pairs $(x,z)$ where you start at $x$, follow an arrow to reach $y$ and then follow another arrow to reach $z$.