Counterexample in relations: $(S \setminus T) \circ R \subseteq (S \circ R) \setminus (T \circ R)$

114 Views Asked by At

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from $B$ to $C$. Can anyone produce a counterexample to $(S \setminus T) \circ R⊆(S \circ R) \setminus (T \circ R)$?

2

There are 2 best solutions below

0
On

Let $R$ be the full relation (that relates every element of $A$ to every element of $B$), and let $S$ and $T$ be two different bijections between $B$ and $C$. Then both $S\circ R$ and $T\circ R$ are the full relation from $A$ to $C$, so their difference is the empty relation, whereas the left-hand side is not the empty relation since $S\neq T$.

0
On

Take $A=\{a\}$, $B=\{b_1, b_2\}$ and $C=\{c\}$ for the sets.

And $R=\{(a,b_1),(a,b_2)\}$, $S=\{(b_1,c)\}$ and $T=\{(b_2,c)\}$ for the relations.

Then $S \circ R=\{(a,c)\}$, $T \circ R=\{(a,c)\}$ and $S \setminus T=S$. Hence $(S◦R) \setminus (T◦R)= \emptyset$ while $(S \setminus T)◦R=\{(a,c)\}$.