3
$\begingroup$

Problem

Let $ R \subseteq A \times B $ and $ S,T \subseteq B \times C $. Proof following for combined binary relation or show that statement is false

$$ (R \circ S) \cap (R \circ T) \subseteq R \circ (S \cap T) $$

Attempt to proof

Let $ \langle x,y \rangle \in (R \circ S) \cap (R \circ T) $

$$ \iff (\langle x, y \rangle \in R \circ S) \wedge (\langle x ,y \rangle \in R \circ T) $$

$$ \iff (\exists w: \langle w,y \rangle \in S) \wedge (\exists z : \langle z, y \rangle \in T) $$

$$ \iff (\langle x , w \rangle \in R) \wedge (\langle x , z \rangle \in R) $$ $$ \iff \langle x , y \rangle \in R \circ (S \cap T) $$


Is my proof correct? I'm not quite sure if this is right.

EDIT:

Incase using $\langle x,y \rangle$ is not common notation. This means $ \langle x ,y \rangle \iff xRy $, relation $R$ maps $x$ to $y$.


Attempt to prove by counterexample

Let $ \langle x,y \rangle \in (R \circ S) \cap (R \circ T) $

$$ \iff (\langle x, y \rangle \in R \circ S) \wedge (\langle x ,y \rangle \in R \circ T) $$

$$ \iff (\exists w: \langle w,y \rangle \in S) \wedge (\exists z : \langle z, y \rangle \in T) $$

$$ \iff \{ \langle x, w \rangle, \langle x, z \rangle \} \in R $$

$$ \iff \{ \langle w, y \rangle \} \cap \{ \langle z , y \rangle \} = S \cap T = \emptyset $$

$$ \iff \langle x , y \rangle \not\in R \circ (S \cap T) $$

$$ \iff (R \circ S) \cap (R \circ T) \not\subseteq R \circ (S \cap T) $$


Is my proof by counterexample valid?

$\endgroup$
  • $\begingroup$ I don't see how the last equivalence holds $\endgroup$ – Akiva Weinberger May 9 at 13:35
  • $\begingroup$ @AkivaWeinberger Any suggestions how it should be? $\endgroup$ – Tuki May 9 at 13:35
  • $\begingroup$ I'm honestly not sure that the statement is true $\endgroup$ – Akiva Weinberger May 9 at 13:50
  • $\begingroup$ @AkivaWeinberger It might be false too. My intuition would tell me the statement is true. $\endgroup$ – Tuki May 9 at 13:51
  • $\begingroup$ Try to find or construct a counterexample $\endgroup$ – Akiva Weinberger May 9 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.