0
$\begingroup$

This is a question given in the book How to Prove It: A Structured Approach (2nd Edition) by Daniel J. Velleman (chapter 4, section 4.1, Problem 12). The proof I've come up with is:

Assume $A \times B \subseteq C \times D$. Suppose some arbitrary $x, y$ such that $x \in A$ and $y \in B$. Therefore there is a $p = (x, y)$ such that $p \in A \times B$. But since it's given that $A \times B \subseteq C \times D$ we have $p \in C \times D$. This means $(x, y) \in C \times D$ and therefore $x \in C$ and $y \in D$. Since $x$ and $y$ are arbitrary, we have $A \subseteq C$ and $B \subseteq D$.

Now this theorem is incorrect when empty sets come into picture, for example if $A = \{1\}, B = C = D = \emptyset$.

My question is related to proof technique I've used above. I start with the conclusion: $$A \subseteq C and B \subseteq D$$

which can be written as: $$\forall x (x \in A \rightarrow x \in C) \land \forall y (y \in B \rightarrow y \in D)$$

Now I assume some arbitrary $x \in A$ and $y \in B$ and we have to prove $x \in C$ and $y \in D$ using the premises. I've solved many proofs that rely on this technique. For example, look at this theorem. It's proved using similar technique. But nowhere is it concerned about the fact that $A$ or $B$ could be empty.

But in my proof above, I can't use the fact that $x \in A$ and $y \in B$ because $A$ or $B$ could be empty.

Does this mean that in each proof that involve working with an arbitrary member of some set (proofs of the form $\forall x P(x)$), it is also required to test the theorem for empty sets? In the linked example above, if $A$ is empty, $x \in A$ becomes false. Does this not make the proof incorrect? If it does, should the proof not involve a separate statement about the possibility of empty set?

$\endgroup$
1
$\begingroup$

If I want to prove that $A\times B\subseteq C\times D$ implies e.g. $A\subseteq C$ then automatically I run into trouble. It is okay to start with $x\in A$ with the aim to show that $x\in C$. No check needed here, because if there is no such $x$ then $x\in A\implies x\in C$ is true vacuously, and I am ready.

But in order to make progression what I really need now is an arbitrary element of $B$ so that I can go on with $\langle x,y\rangle\in A\times B\subseteq C\times D$ hence $x\in C$. Here a check is needed: do we have any reason to believe that $B$ is not empty?

If $B$ is empty then such an element $y$ does not exist, and since it is not excluded that $B$ is empty my effort to prove $A\subseteq C$ stops fruitlessly.

$\endgroup$
  • $\begingroup$ So I think my mistake is that I am considering both conclusions together. These are $A \subseteq C$ and $B \subseteq D$. And I assume $x \in A$ and $y \in B$ together giving me $(x, y) \in A \times B$. But if the conclusions are taken one at a time, no assumption about $y \in B$ can be made. Does that mean in order to prove a conjunction $P \land Q$, $P$ and $Q$ must be proved separately so as to avoid mixing up their assumptions? $\endgroup$ – abhink Aug 20 '17 at 12:04
  • $\begingroup$ Sort of, yes. In order to prove $A\subseteq C$ on base of $A\times B\subseteq C\times D$ you need $B\neq\varnothing$ and in order to prove $B\subseteq D$ you need $A\neq\varnothing$. If $P\wedge Q$ must be proved on base of $R$ then it is quite well possible that in $R\implies P$ we use other aspects of $R$ than in $R\implies Q$. Of course there are also situations in which their is no actual difference. So "must be proved separately"...no, the word "must" is too heavy in this context. $\endgroup$ – drhab Aug 20 '17 at 12:14
0
$\begingroup$

In the linked example we use the fact that the empty set is a subset of every set.

So the linked theorem can be proved by cases where $A,C$ are both non-empty or at least one of them is empty.

If $A \subseteq B$ and $C \subseteq D $ and $A= \emptyset$

Then $A \cap C =\emptyset \subseteq B \cap D$

Now your proof works if they are non-empty but in the case where we have empty sets involved your proof cannot be correct.

So this theorem is not true in general because does not hold for every set.

$\endgroup$
0
$\begingroup$

Technically it would make the proof incorrect (Since without any conditions it assumes that the proof works for any sets whatsoever)

Usually in every proof ever written, there's an assumption beforehand that the sets aren't empty or something similar. I'd say the writer might have forgotten to add a necessary condition first.

To fix the proof, it is enough to add the condition that

C=∅ → A=∅ and D=∅ → B=∅

$\endgroup$
  • $\begingroup$ It's more of an illustrative question that aims to allow the reader to work out that the sets could be empty and the theorem is incorrect. The problem is that I have a proof that works when the sets are not empty, but until now, I've been using similar proof technique without considering the fact that sets could be empty. $\endgroup$ – abhink Aug 20 '17 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.