Proof that for binary relation following is true or prove by counterexample.

49 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

Try a concrete example.

Suppose A is the set of polynomials $\mathbb C[x]$, B is $\mathbb C$, and C is $\mathbb R$. Let $R$ be "this complex number is a root of this polynomial", $S$ be "this real number is the real part of this complex number", and $T$ be "this real number is the imaginary part of this complex number". Figure out what $R\circ S$, $R\circ T$, and $R\circ (S\cap T)$ mean in this situation, and what that means for your statement.