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
    $\begingroup$ This is not a proof by counterexample. That would require you to find particular explicit relations for which you could show the claimed inclusion is false. (I haven't checked what you actually wrote.) $\endgroup$ – Ethan Bolker May 9 at 16:54
  • $\begingroup$ In addition to the correct comment by @EthanBolker I'd add that your assertion that $\{\langle w,y\rangle\}\cap\{\langle z,y\rangle\}$ is empty presupposes $w\neq z$. $\endgroup$ – Andreas Blass May 9 at 17:05
  • $\begingroup$ @EthanBolker Could you suggest solution to this? $\endgroup$ – Tuki May 9 at 17:08
  • $\begingroup$ Rather than work with formal statements about sets, think about creating examples to test the inequality. If you use sets $A$, $B$ and $C$ with just two or three elements each you can write down many simple binary relations to play with. Then you will either stumble on an explicit counterexample or gain some intuition about why the assertion is true. $\endgroup$ – Ethan Bolker May 9 at 17:24

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.


Your Answer

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

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