*Note to moderators: The following problem is a duplicate, but my question is not.
I have trouble understanding the following problem from Velleman's book $-$ How to prove it, 3rd edition $-$ on introduction to proofs. More specifically, problem 15, from ch 4.1 (on Relations). It asks if the proof of a putative theorem is correct:
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$.
Proof: Suppose $A \times B \subseteq C \times D$. Let $a \in A$ and $b \in B$. Then $(a,b) \in A \times B$, so since $A \times B \subseteq C \times D$, $ (a,b) \in C \times D$, thus, by the definition of Cartesian Product, $a \in C$ and $b \in D$. Therefore $A \subseteq C$ and $B \subseteq D$.
Now, the theorem is clearly false, as indicated by the basic counterexample: $A=\emptyset$, $B=\{1\}$, $C=\{2\}$ and $D=\{3\}$. Clearly and vacuously $A \times B \subseteq C \times D$, and $A \subseteq C$ but $B \not\subseteq D$. However, the way the proof approaches the problem gives me some doubts about all the fundamentals of proving set-related identities.
Firstly, can one even make an assumption which might as well be false (for the sake of a conditional proof)?? Doesn't assuming that $a \in A$ effectively prevents $A = \emptyset $. If this is not the case, then we're basically saying "Assume $a \in A$ but this might not be true" or "Assume that $n$ is odd, but it might be even". Accordingly, vacuous cases $-$ or in this case, allowing for sets to be empty $-$ need to be treated separately, within an exhaustive proof by cases, since one can't start a proof by saying "Suppose $x \in \emptyset$".
Secondly, it appears that the author implicitly complies with such an assumption regarding the empty set. This is seen on page $175$, where he states: "Because $p \in A \times (B \cap C)$ means $\exists x \exists y ( x \in A \land y \in B \cap C \land p=(x,y))$...". Thus we can deduce the following: $$ \text{If }p\in A \times B \text{, then } \exists x \exists y ( x \in A \land y \in B \land p=(x,y)). $$ So returning to the proof, when claiming $a \in A$ and $b \in B$ then, by the definition of Cartesian Product, $(a,b) \in A \times B$, but then $p=(a,b)\in A \times B$, so $-$ by the above proposition $-$ there is an $x$ in $A$ and a $y$ in $B$. Therefore $A$ and $B$ can't be empty. But since $A \times B \subseteq C \times D$, $C$ and $D$ can't be empty.
All in all, I think the part where the proof fails is the fact that it doesn't treat any any sets $A$, $B$, $C$ and $D$, rather just sets which are non-empty. And therefore there's nothing really wrong with the body of the proof, apart for that small implicit assumption. However, I know I'm wrong, but I can't put my finger on it.
The theorem is false as you correctly show.
Where is the problem in the proof?
To prove $A \subset C$, we have to show that $a \in A$ implies $a \in C$. If $A = \emptyset$, this is of course vacously true. But if $A \ne \emptyset$, the argument requires the existence of an element $b \in B$, i.e. needs the additional assumption $B \ne \emptyset$.
In other words, the author proves
Let $A \times B \subset C \times D$. If $A = \emptyset$ or $B \ne \emptyset$, then $A \subset C$. If $B = \emptyset$ or $A \ne \emptyset$, then $B\subset D$.
As you say, we can consider an element $p \in A \times B$. Provided such $p$ exists, we see that there exist $a \in A$ and $B \in B$ such that $p = (a,b)$. But if no such $p$ exists, we do not know anything about the existence of elements $a \in A$ and $b \in B$. And, by the way, to show that $A \subset C$ it is not a good approach to consider some $p \in A \times B$. We have to consider $a \in A$ - but such $a$ might not exist which is a trivial case.
The empty set often plays a special and has to be treated separately, but sometimes authors forget to do this and obtain invalid results. But usually this can easily be detected by the reader.