Finding a mistake in the incorrect proof for $(S\setminus T)\circ R\subseteq (S\circ R)\setminus(T\circ R)$

136 Views Asked by At

This is from Velleman's "How to Prove It", exercise 4.2.11.b). The exercise requires finding a mistake in the proof, but everything looks good to me. Must be that I'm missing some important fact, but any pointers are well appreciated.

$R$ is relation from $A$ to $B$, and $S$ and $T$ are relations from $B$ to $C$.

Proof. Suppose $(a,c)\in (S\setminus T)\circ R$. Then we can chose some $b\in B$ such that $(a,b)\in R$ and $(b,c)\in S\setminus T$, so $(b,c)\in S$ and $(b,c)\not\in T$. Since $(a,b)\in R$ and $(b,c)\in S$, $(a,c)\in S\circ R$. Similarly, since $(a,b)\in R$ and $(b,c)\not\in T$, $(a,c)\not\in T\circ R$.Therefore $(a,c)\in (S\circ R)\setminus(T\circ R)$. Since $(a,c)$ was arbitrary, this shows that $(S\setminus T)\circ R\subseteq(S\circ R)\setminus(T\circ R)$.

What am I missing here?

P.S. The author does not imply that the proposition is true, so I cannot say if there actually is a proof for this.

1

There are 1 best solutions below

1
On BEST ANSWER

The error occurs at the claim "since $(a,b)\in R$ and $(b,c)\notin T, (a,c)\notin T\circ R$." This is not necessarily true. Note that $(a,c)\in T\circ R$ if and only if there is some $b^\prime\in B$ such that $(a,b^\prime)\in R$ and $(b^\prime,c)\in T$. Thus, even if your "initial" element $b\in B$ does not satisfy the condition $(b,c)\in T$, perhaps another element $b^\prime\in B$ do satisfy the desired condition.