I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint:
$(A \times B \cap C \times D = \emptyset) \to (A \cap C = \emptyset \lor B \cap D = \emptyset)$
I've tried proving by direct proof by assuming the left side, but I don't know how to deal with the equals sign and the $\emptyset$. I also tried defining disjoint as an implication itself, so that the left side is this:
$(x, y) \in A \times B \to (x, y) \not\in C\times D$
But then when assuming the left side, I don't know how to deal with the $\to$. I was only able to get this far:
$x \in A \land y \in B \to x \not\in C \lor y \not\in D$
Any ideas on how to prove this?