
\problemdata     
{S01-PS3-2}           
{Cartesian products, disjoint, direct proof}
{Velleman 4.1.8}              
{S00, S01-PS3} 		
{S01 Karger}        	





\begin{problem} 

Prove that for any sets $A$, $B$, $C$, and $D$, if 
$A \times B$ and $C \times D$ 
are disjoint, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint.

\solution{
We will prove the contrapositive.  In other words,
\newline 
prove: 
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset] 
\implies [(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
assume:
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset]$
\newline
$\therefore \exists a (a \in A \land a \in C) \land 
\exists b (b \in B \land b \in D)$.
\newline
then, $(a, b) \in A \times B$   by definition of Cartesian product, 
Velleman 158.
\newline
and, $(a, b) \in C \times D$   by definition of Cartesian product, 
Velleman 158.
\newline
$\therefore (a, b) \in [(A \times B) \intersect (C \times D)]$ so 
$[(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
$QED$
}

\end{problem}
