if A × B ⊆ C × D then how to prove that A ⊆ C or B ⊆ D. Suppose $A,B,C,D$ are sets such that $A \times B \subseteq C \times D$. How do I prove that $A \subseteq C$ or $B \subseteq D$?
I am only arriving at $(x,y)$ belongs to $A \times B\to (x,y)$ belongs to $C \times D\to x$ belongs to $C$ and $Y$ belongs to $D\to A\subseteq C$ and $B\subseteq D$. 
 A: If either $A$ or $B$ is an empty set, then $\emptyset\subseteq C$ and $\emptyset \subseteq D$, so we know the statement is true.
Let's assume that none of the sets $A,B$ is empty, i.e. there exists $a\in A, b\in B$. Take any $x\in A$. Then, because $b\in B$, we know that $(x,b)\in A\times B$, and because $A\times B\subseteq C\times D$, we know that $(x,b)\in C\times D$.
From $(x,b)\in C\times D$, we know that $x\in C$. Therefore, any element of $A$ is also an element of $C$, so $A\subseteq C$. Similarly, you show that $B\subseteq D$.
Bottom line:
If $A$ and $B$ are nonempty, then $A\subseteq C$ and $B\subseteq D$. If one, for example $B$, is empty, then $B\subseteq D$, however, in that case, $A\subseteq C$ need not be true.
A: Suppose $A\not\subseteq C$ and $B\not\subseteq D$. Then you have an $x\in A$ such that $x\not\in C$ and a $y\in B$ such that $y\not\in D$. Then $(x,y)\in A\times B$, and $(x,y) \not\in C\times D$, that is : $A\times B\not\subseteq C\times D$, which is a contradiction.
A: Proving $p \Rightarrow q$ by proving $\neg q \Rightarrow \neg p$:
If $A, B, C, D$ are sets with
$$
A \not\subseteq C \wedge B \not\subseteq D
$$
then we can choose $a^* \in A$ and $b^* \in B$ with $a^* \not\in C$ and $b^* \not\in D$. 
Note that: $A \not\subseteq C$ implies $A \ne \emptyset$ (otherwise violation of $\emptyset \subseteq M$ for any set $M$) and $C \ne \emptyset$  (otherwise violation of $M \subseteq \emptyset \Rightarrow M = \emptyset$) thus some $a \in A$ and some $c \in C$ exist and the existence of at least one $a \in A$ with $a \not\in C$ (otherwise violation of $A \neq C$).
Then $(a^*, b^*) \in A \times B$ but $(a^*, b^*) \not\in C \times D$, this means $A \times B \not\subseteq C \times D$.
