Can't find mistake in an easy proof.

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.

• I think the proposition and proof is valid for non-empty sets $A$ and $B$. – Steven Van Geluwe Sep 9 '14 at 13:10
• +1 This is an excellent problem - it took me a while to figure out what was wrong with it! – templatetypedef Sep 9 '14 at 16:41
• If you have a proof and a counterexample to the same statement, there is an easy procedure to figure out where things went wrong. Apply each general statement in the proof to the particular case of the counterexample; supposedly at the beginning (the hypotheses) you are getting true statements, and at the end a false statement. Somewhere in between you must be deriving a false conclusion from true assumptions and that step must be wrong (supposing only one step is wrong you could find it by binary search; this might be useful if your proof is very long). – Marc van Leeuwen Sep 10 '14 at 11:18

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$.

• It is not his proof. It is the proof he finds puzzling. Not that it matters much. – almagest Sep 9 '14 at 13:41
• @almagest: Ah, sorry, I hadn't seen that. I'll correct my answer. – Frunobulax Sep 9 '14 at 13:47
• @Frunobulax I don't actually think that this is the problem with the proof. There's nothing wrong with saying "let $b$ be an arbitrary element of $B$" without having to stipulate that such a $b$ actually exists. Typically, if you do something like that, you'll end up with a result that's true, but may be vacuously true if there isn't a choice of $b$ to make. I think that the issue is with the overall logical structure of the proof; can you check my answer and see if it makes sense? – templatetypedef Sep 9 '14 at 16:41
• @templatetypedef: It makes sense if you insist on a formal proof, but I'm not sure if it really helps in understanding. If you write the proof the way I did (i.e. if you prove $A\subseteq C$ and $B \subseteq D$ "one at a time") you'll end up at a point where you'll need some $b\in B$ and you'll "see" that you need $B$ to be non-empty. – Frunobulax Sep 9 '14 at 16:49
• There's nothing wrong per se with saying to choose an arbitrary element from a set if you're trying to prove a universally-quantified statement. I think that the real issue is that the proof is a valid proof of a result other than the one that's trying to be proven. – templatetypedef Sep 9 '14 at 21:11

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.

• I guess the second formula is not what you wanted to write. – Frunobulax Sep 9 '14 at 16:50
• @Frunobulax corrected now. – Ari Brodsky Sep 9 '14 at 18:44
• The proof in OP gives you $$(\forall a. ((a \in A \land \exists b.(b \in B))\rightarrow a \in C)) \land (\forall b. ((b \in B \land \exists a.(a \in A))\rightarrow b \in D))$$. – Taemyr Sep 10 '14 at 13:18

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.

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.

• The problem is not with doing two things "at once"; the problem is that neither of the two things is actually doable! You can't choose an arbitrary element a of A unless set A actually has elements. – Quuxplusone Sep 10 '14 at 6:05
• @Quuxplusone so each time we try to prove something like the statement above, should we explicitly state that we are interested in a nonempty set? – Fazzolini Sep 10 '14 at 14:48
• @Quuxplusone No. In a "for all" statement, the hypothesis is "If there is an element of A, [then it has property P.]" So in proving a forall statement you do exactly that. You might say "if the hypothesis is false then the statement is vacuously true," but this is getting too philosophical for me. – djechlin Sep 10 '14 at 15:58
• @Fazzolini, not necessarily; but every time in the proof you write something like "Choose an element a of A," you should explicitly state "...or, if A is empty, do <some other thing> instead." Sometimes that other thing is "conclude that the conjecture is vacuously true," but in the particular case of your conjecture, the other thing is "fail to prove the conjecture (namely because it's false when either A or B is empty)." – Quuxplusone Sep 10 '14 at 18:04