Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks a lot. I'm still trying to wrap my head around the relation composition mechanics. :) –  LavaScornedOven Jan 19 '13 at 3:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.