Let $A$ and $B$ be sets, and let $C$ be a non-empty set. Prove that

$$A\cap B=\varnothing ⟺(A\times C)\cap (B\times C)=\varnothing .$$

---

Solution

In order to prove the biconditional, we first prove sufficiency, then necessity.

• $(\Rightarrow )$: Let $A\cap B=\varnothing$. Assume for contradiction that $(A\times C)\cap (B\times C)\ne \varnothing$. Then, there exists $x$ in $(A\times C)\cap (B\times C)$. Since $C\ne \varnothing$ and by definition of set intersection, we further observe that $x=(u,v)$ for some $u\in A\cap B$ and $v\in C$. The fact that $u\in A\cap B$ is a contradiction to the assumption that $A\cap B=\varnothing$. Therefore, $(A\times C)\cap (B\times C)=\varnothing$ by contradiction.

• $(\Leftarrow )$: Let $(A\times C)\cap (B\times C)=\varnothing$. Assume for contradiction that $A\cap B\ne \varnothing$. Then, there exists $x$ in $A\cap B$. Further, since $C\ne \varnothing$ by assumption, then there exists $c$ in $C$. Thus, $(x,c)$ is an element of $(A\cap B)\times C$. We also observe that

  $$(A\cap B)\times C=(A\times C)\cap (B\times C),$$

  hence $(x,c)\in (A\times C)\cap (B\times C)$ which is a contradiction to the assumption that $(A\times C)\cap (B\times C)=\varnothing$. Therefore, $A\cap B=\varnothing$ by contradiction.