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


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.

  • 2
    $\begingroup$ 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 ... $\endgroup$ – Did May 5 '17 at 5:48
  • $\begingroup$ Great, I see it now. Just matching the variables to the definition. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ FWIW, it would be more convenient to draw A and B and B in this order, to draw arrows from A to the first copy of B and from the first copy of B to the second copy of B, and then to follow the arrows. $\endgroup$ – Did May 5 '17 at 6:36
  • $\begingroup$ Not sure,which approach is better but they both makes sense. $\endgroup$ – Squanchinator May 5 '17 at 6:47

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.