Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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 ?

share|cite|improve this question
@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.

Your second proof is correct.

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.

share|cite|improve this answer
This is okay, but the proof given by the OP has more elegance (not your fault). – drhab May 27 '14 at 18:36
@drhab: Well, it is missing a step or two. The first proof doesn't use any property of the product. If one expands the argument into a full proof, I think it will lose the apparent elegance? – copper.hat May 27 '14 at 18:37
I was talking about the contrapositive proof given by the OP. Nothing lacks there. – drhab May 27 '14 at 18:45
@drhab: Yes, there is an 'asymmetry' in my proof above that is not pretty. – copper.hat May 27 '14 at 18:59
@user254665: I agree, 'missing some detail' was a bit of an understatement. – copper.hat May 20 at 5:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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