Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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


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.