\problemdata
{sets}
{S00 ps3}

\begin{problem}
Consider the following putative theorem and the accompanying proof.

\begin{theorem*}
  For any sets $A$, $B$, $C$, and $D$, if $A \times B \subseteq C
  \times D$ then $A \subseteq C$ and $B \subseteq D$.
\end{theorem*}

\begin{proof}
  Suppose $A \times B \subseteq C \times D$.  Let $a$ be an arbitrary
  element of $A$, $b$ be an arbitrary element of $B$, and $(a, b) \in
  A \times B$.  Since $A \times B \subseteq C \times D$, it follows
  that $(a, b) \in C \times D$.  Therefore, $a \in C$ and $b \in D$.
  Since $a$ and $b$ were arbitrary elements of $A$ and $B$,
  respectively, this shows that $A \subseteq C$ and $B \subseteq D$.
\end{proof}

Is the proof correct?  If so, what proof strategies does it use?  If
not, can it be fixed?  Is the theorem correct?

\solution{
    The problem lies in the statement \emph{``let $a$ be an arbitrary
      element of $A$''} (and without loss of generality, $b$ an
    arbitrary element in $B$).  Namely, if $A = \emptyset$, $B = \{1,
    2, 3\}$, $C = \{1, 2\}$, and $D = \{3, 4\}$, then $A \times B
    \subseteq C \times D$ ($\emptyset \subseteq E$ for any set $E$),
    but $B \not\subseteq D$.  This is an example of the proof failing
    at a boundary case.%

}
\end{problem}