Need easy explanation of the result of a composition.

Question

I'm going trough Velleman's book "How to Prove it" (pg 189 - 2019 edition).

I have this exercise:

Suppose

A = {1, 2, 3}
B = {4, 5, 6}
R = {(1,4), (1,5), (2,5), (3,6)}
S = {(4,5), (4,6), (5,4), (6,6)}

Note that R is a relation from A to B and S is a relation from B to B. Find the following relation:

a) $S \circ R$
b) $S \circ S^{-1}$

I need an explanation of how to get to these answers:

a) {(1,4),(1,5),(1,6),(2,4),(3,6)}
b) {(4,4),(5,5),(5,6),(6,5),(6,6)}

There's gotta be some steps to be done before getting to these answers. At the moment, I don't even understand which steps I should take.

Thanks.

Answer 1

Take the definition of '$\circ$', the composition of relations. You have a relation $R$, which is a subset of $A\times B$, and a relation $S$, which is a subset of $B\times B$. So their composition is a subset of $A\times B$. Now check which elements of $A\times B$ are in the relation $S\circ R$; there are only $9$ pairs to check.

Do the same for $S\circ S^{-1}$; first make explicit for yourself what $S^{-1}$ is, then do the same as before.

Answer 2

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

Note that $$S\circ R (1)$$ is simply $$S(R(1))=S(4)=5$$

That explains $(1,4)$ in the $S\circ R$

Also $$S\circ R (1)$$ is $$S(R(1))=S(5)=4$$

That explains $(1,5)$ in the $S\circ R$

You can take it from here.