# Proof that for binary relation following is true or prove statement is false.

## 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?

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