Mistake in $A \times B \subseteq C \times D \rightarrow A \subseteq C \wedge B \subseteq D$

Question

I am currently going through Velleman's How to prove it and I am trying to understand exercise 12 from chapter 4.1. The exercise asks to show whether the theorem in the title is correct. It is obviously incorrect as you can provide a counter example in the form of $A = \{ 1 \}$ and $B = C = D = \emptyset $, however I do not particularly understand the formal reason why the following proof might not work:

Suppose $A \times B \subseteq C \times D$. Suppose $x \in A$ and $y \in B$, thus $(x,y) \in A \times B$. Therefore, since $A \times B \subseteq C \times D$, it follows that $(x,y) \in C \times D$, so $x \in C$ and $y \in D$. $x \in A$ and $y \in B$ arbitrary, so we conclude that $A \subseteq C$ and $B \subseteq D$.

I understand, empirically why it does not hold for empty sets, but I cannot find the formal mistake in the logic, since we are only applying universal instantiation to $x$ and $y$, much like we would prove $(A \subseteq B \wedge B \subseteq C) \rightarrow A \subseteq C$. There we would be supposing $x$ were an arbitrary element of $A$ regardless of whether $A$ is empty or not:

Suppose $A \subseteq B \wedge B \subseteq C$ and suppose $x \in A$. etc. etc.

So my question is why does it work in the second example and not in the first one. Is there some formal definition of membership to a cartesian product which I am missing? Maybe something involving an existential quantifier? And if so, how is it different from the second proof?

Answer 1

The problem seems to be that you're trying to prove $A\subseteq C$ and $B\subseteq D$ simultaneously when you write "Suppose $x\in A$ and $y\in B$".

However, this won't work, because there is nothing in the shape of your conclusion that allows you to assume that you can make both these suppositions at the same time.

If you're proving $A\subseteq C$ alone, you can start by saying "suppose $x\in A$" because if there are no such $x$ to choose, you're already done with proving everything you want about $A$'s elements.

But when you try to make both assumptions at once, then there might be an $x\in A$ that you need to handle, and then attempting to also choose a $y\in B$ (which is irrelevant for $A\subseteq C$) before you proceed will derail the proof if $B$ happens to be empty.

---

Written symbolically, you want to prove $$ (\forall x. x\in A\to x\in C)\land(\forall y. y\in B\to y\in D)$$ You're allowed to pull the quantifiers out in front and instead prove $$ \forall x.\forall y.((x\in A \to x\in C)\land(y\in B \to y\in D)) $$ but you cannot, as you do, go further and join the two assumptions $x\in A$ and $y\in B$ into an assumption for a single combined $\to$. This is a matter of propositional logic: $$ (P\to Q)\land(R\to S) \quad\not\equiv\quad (P\land R)\to(Q\land S)$$

Answer 2

When you say that $y \in B,$ you're implicitly assuming that $B \neq \emptyset.$ There is no $y\in B,$ and so the proof has the hidden assumption that there is some $y \in B.$ In general, whenever you say "let $y \in B,$" you need to be careful that there actually is some $y \in B$ for you to pick!

Answer 3

We have only the assumption $$A \times B \subseteq C \times D\tag{1}$$

and we want to show $A \subseteq C$ (and also $B \subseteq D$). So pick $x \in A$, and we want to show $x \in C$ for the inclusion. To use $(1)$, we need a point of $A \times B$. We already have one in $A$, so pick $b \in B$ (here we use $B$ is non-empty!!), then $(x,b) \in A \times B$ by definition and by the inclusion $(1)$ we know $(x,b) \in C \times D$ and from that (!) we can trivially conclude that $x \in C$ and we're done. We need the point in $B$ to be able to use the inclusion $(1)$ and likewise to show $B \subseteq D$ we need some point $a \in A$ as well.

To prove the single inclusions we have only one coordinate in the product, and we need another one. The counterexample shows we cannot omit it.