Can't find mistake in an easy proof.

Question

Consider the following theorem.

$\textbf{Theorem:}$ for any sets $A, B, C, D$, if $A \times B \subseteq C \times D$ then $A \subseteq C$ and $B \subseteq D$.

Then the following proof is given. $\textbf{Proof:}$ Suppose $A \times B \subseteq C \times D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an arbitrary element of $B$. Then $(a,b) \in A\times B$. so since $A\times B \subseteq C \times D$, $(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$. QED.

I know that the theorem is not correct, because there is a counterexample $A = \left\lbrace 1 \right\rbrace$, $B = C = D = \emptyset$. Notice that $A \times B \subseteq C \times D \sim \emptyset \subseteq \emptyset$ but $A \nsubseteq C$. So, clearly, this is an invalid proof, but I cannot figure out which step is wrong.

Answer 1

They write "let $b$ be an arbitrary element of $B$" without checking whether $B$ actually has elements.

Addendum: The proof is otherwise essentially OK assuming that we require $A,B\neq\emptyset$, but I would write it a bit differently: Let $a$ be an arbitrary element of $A$. As $B$ is not empty, we can find a $b\in B$ and thus $(a,b)\in A\times B$. This implies $(a,b)\in C\times D$ and thereby $a\in C$. That proves $A \subseteq C$ and we can likewise prove $B \subseteq D$.

Answer 2

The logic inside the proof is sound and does indeed prove something, but it doesn't prove the statement that's given by the theorem.

You want to prove that $A \subseteq C$ and that $B \subseteq D$. To do this, you need to prove this statement:

$$(\forall a. (a \in A \rightarrow a \in C)) \land (\forall b. (b \in B \rightarrow b \in D))$$

Therefore, you need to prove that for any choice of $a$ that if $a \in A$, then $a \in C$ and, independently, that for any choice of $b$ that if $b \in B$, then $b \in D$. A proof of this form would need to handle these independently, with the choices of $a$ and $b$ not interacting with one another.

However, in the proof given above, the proof begins by starting with an arbitrary choice of $a$ and an arbitrary choice of $b$, then shows that if $a \in A$ and $b \in B$, then $a \in C$ and $b \in D$. In other words, you've proven this statement:

$$\forall a. \forall b. (a \in A \land b \in B \rightarrow a \in C \land b \in D)$$

This statement is absolutely true - if you can find an $a \in A$ and a $b \in B$, then you know that $a \in C$ and $b \in D$. However, it's not logically equivalent to the statement that you want to prove, as evidenced by your counterexample.

Answer 3

Since this is an exercise 12 in Section 4.1 of Velleman's book "How To Prove It", lets see what the author himself thinks about it.

He writes on page 137 of Daniel J. Velleman, Variable declarations in natural deduction / Annals of Pure and Applied Logic 144 (2006) 133-146, available as pdf at http://www.sciencedirect.com/science/article/pii/S0168007206000649 :

Where did the proof go wrong? The problem is that the proof that $A \subseteq C$ improperly makes use of the arbitrary element $b$ of $B$, and the proof that $B \subseteq D$ improperly makes use of the arbitrary element $a$ of $A$. The author of the proof has tried to take a shortcut by proving $A \subseteq C$ and $B \subseteq D$ simultaneously. If we eliminate the shortcut and structure the proof properly, then we must prove that $A \subseteq C$ by letting $a$ be an arbitrary element of $A$ and proving that $a \in C$, and then we must prove that $B \subseteq D$ by letting $b$ be an arbitrary element of $B$ and proving that $b \in D$. In neither part of the proof can the arbitrary object from the other part be used.

This proof illustrates that the dependencies among assertions, assumptions, and introductions of variables can be quite subtle, and catching errors resulting from improper dependencies can be difficult. The safest policy is the one that I believe mathematicians generally follow: once an assumption or a declaration that a variable stands for an arbitrary object is retracted, nothing that has appeared in the proof since the assumption or declaration can be used.

Answer 4

My two cents:

Let a be an arbitrary element of A and let b be an arbitrary element of B.

In most proofs you can get away with this imprecision, but since you're considering two elements at once the slipperiness fools you.

You want to show two independent statements that need to be proved one at a time:

$$\forall a \in A, a \in C$$ $$\forall b \in B, b \in D$$

So let $a$ be an arbitrary element of $A$. This is how you prove a "for all" statement. This is your only assumption you make to prove the first "for all" statement. "Now there exists a corresponding $b\in B$" is an assertion, and a generally false one at that.