# Cartesian Product Proof

I was in class the other day when I got a problem presented to me to that I had to figure out.

The problem was "If A X B is a subset of C X D, then A is a subset of C and B is a subset of D. Prove this is true or give a counterexample to show it is false."

If $A\times B \subseteq C \times D$, then $A\subseteq C$ and $B\subseteq D$. Prove this is true or give a counterexample to show it is false.

I'm almost positive that this is false but I'm not sure how to go about disproving it.

If anyone could help me out at all I'd appreciate it.

Thanks a lot.

-
So why exactly do you believe it's false? Anyway, hint: Assume there is an element in A that is not in C... (It might also help to visualize the two products as e.g. rectangles in $\mathbb{R}^2$.) – anon Sep 27 '11 at 10:44
@BleuCheese I've added LaTeXed version of your formula. If you are satisfied with the result, you can edit the post ant leave the LaTeX-ed version there. (Or make further edits, if needed.) For more about writing math at this site see here or here. – Martin Sleziak Jun 27 '12 at 14:13
@BleuCheese You may want to look at my related answer math.stackexchange.com/a/406068/11994, where the counterexample ($A=\emptyset\lor B=\emptyset$) automatically falls out of the calculation. – Marnix Klooster May 30 '13 at 6:14

Well this is true if A and B are not empty sets and false in general. If $A=\emptyset$, $B=\{1,2\}$, $C=\{1\}$, $D=\{2\}$ then $B\not\subseteq D$ but $A\times B=\emptyset\subseteq C\times D$.
If $A$ and $B$ are not empty the proof is simple enough.
If $A\times B \subseteq C\times D$ then $\forall a\in A, b\in B, (a,b)\in C\times D$ and so $\forall a\in A, a\in C$ and $\forall b\in B, b\in D$ so $A\subseteq C$ and $B\subseteq C$. This is a rather informal sketch but you should figure out where we need the assumption that A and B are not empty sets.