# 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$. Sep 9, 2014 at 13:10
• +1 This is an excellent problem - it took me a while to figure out what was wrong with it! Sep 9, 2014 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). Sep 10, 2014 at 11:18

## 4 Answers

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. Sep 9, 2014 at 13: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. Sep 9, 2014 at 16:49
• I see what you're saying, but I disagree that the problem in the proof is that $B$ isn't asserted to be nonempty. None of the actual steps in the proof are actually wrong - it's more that the result shown isn't the right result. Think of it this way - suppose you want to prove that $A \cap B \subset A$. One way to do that is to consider an arbitrary element $x \in A \cap B$, then to say that this element must belong to $A$ because it belongs to $A \cap B$. This proof is valid even if $A \cap B$ is empty, even though "choose an arbitrary $x \in A \cap B$" isn't qualified. (continued...) Sep 9, 2014 at 21:10
• 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. Sep 9, 2014 at 21:11
• @templatetypedef That's because your example has an implicit if A∩B is empty conclusion is trivial, otherwise take arbitrary a.... OP's case cannot say that the case of B being empty (with element from A already chosen) is trivial. Sep 10, 2014 at 11:04

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.

• 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))$$. Sep 10, 2014 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. Sep 10, 2014 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? Sep 10, 2014 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. Sep 10, 2014 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)." Sep 10, 2014 at 18:04