# How to Prove it 4.1 ex.10

Prove that for any sets A, B, C, and D, if A × B and C × D are disjoint, then either A and C are disjoint or B and D are disjoint.

Proof(someones).
Suppose (A X B) and (C X D) are disjoint. Let (x,y) be an arbitrary ordered pair of (A X B), it follows that $(x,y) \notin (C X D)$. So either $x \notin C$ or $y \notin D$. Since x,y are arbitrary, Thus either A and C are disjoint or B and D are disjoint.

I think the above proof is wrong since it assumes (x,y) is an arbitrary ordered pair of (A X B) without any logical justification(no existential instantination).

My Proof.(Contrapositive)

Suppose $A\cap C \ne \emptyset$ and $B\cap D \ne \emptyset$. It follows that there exist an element $a\in A\cap C$ and $b\in B\cap D$. Since $a\in A$ and $b\in B$ then $(a,b)\in A× B$ and since $a\in C$ and $b\in D$ then $(a,b)\in C×D$. So $(a,b)\in A×B \cap C×D$. So A × B and C × D not disjoint.

As for the first proof I can understand the "Suppose (A X B) and (C X D) are disjoint" part. But I cant understand the logical justification of assuming an element (x,y) in AXB since by making this assumption you are also assuming that A or B are not $\emptyset$ which makes the proof invalid as you are assuming something not given. Also A,B,C,D are supposed to be arbitrary sets.

My questions here are:

1) Is the first one correct ? If it is what is its logical justification.

2)Is my proof correct ? If not, what is my mistake ?

-
@copper.hat but Assuming AxB and CxD are disjoint means the "someones" proof didn't proceed using the contrapositive strategy. –  Nameless May 27 '14 at 18:00
¬Q amounts to assuming that A∩C≠∅ $\land$ B∩D≠ ∅. –  Nameless May 27 '14 at 18:07
Your proof is correct. The first proof is not. It does not exclude the possibility that for $i=1,2$ you can have ordered pairs $\left(x_{i},y_{i}\right)\in A\times B$ with $x_{1}\notin C$ and $y_{1}\in D$ and with $x_{2}\in C$ and $y_{2}\notin D$. Then $x_{2}\in A\cap C$ and $y_{1}\in B\cap D$ so that both sets are not empty. –  drhab May 27 '14 at 18:11
I added a version of the first proof and am deleting my previous irrelevant comments. –  copper.hat May 27 '14 at 18:35
Velleman's book ? –  grayQuant May 27 '14 at 18:59

Your first proof is missing some detail. I have elaborated below.

Suppose $A\times B$ and $C \times D$ are disjoint.
If $A \cap C$ is empty, we are finished, so suppose $A \cap C$ is non-empty, and let $a \in A \cap C$. We have $\{a\} \times B \subset A \times B$, and $\{a\} \times D \subset C \times D$. Since $A\times B$ and $C \times D$ are assumed disjoint, we must have that $\{a\} \times B$ and $\{a\} \times D$ are disjoint, which implies that $B$ and $D$ are disjoint.
That is, either $A \cap C$ is empty or $B \cap D$ is empty.