If $(A\times B) \cap (C\times D)=\varnothing$ then either $A\cap C=\varnothing$ or $B\cap D=\varnothing$.

Question

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 ?

Answer 1

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.

Answer 2

Your proof is correct. The first proof is incorrect, but not really for the reason you state. There is no harm in supposing $(x,y)\in A\times B$, because the argument is trying to make a statement for all $(x,y)\in A\times B$ (and if $A\times B$ is empty, that statement is just vacuously true).

However, the statement the first proof is proving is not the statement you are trying to prove. It shows that if $x\in A$ and $y\in B$, then either $x\not\in C$ or $y\not\in D$. This does not immediately imply that $A\cap C=\emptyset$ or $B\cap D=\emptyset$. Indeed, it only proves that for all $x$ and $y$, either $x\not\in A\cap C$ or $y\not\in B\cap D$. What you want to prove is that either (for all $x$, $x\not\in A \cap D$) or (for all $y$, $y\not\in B\cap D$). This is a different statement, since we have moved the quantifiers inside the disjunction.

Answer 3

This is not a direct answer to your question (you have already two of those), but I'd like to show an alternative style of proof.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

You are asked to prove, for arbitrary sets $\;A,B,C,D\;$, that $$ \tag 0 (A \times B) \cap (C \times D) = \varnothing \;\then\; A \cap C = \varnothing \;\lor\; B \cap D = \varnothing $$

Let's start at the most complex side, and investigate what members the set $\;(A \times B) \cap (C \times D)\;$ has: for every $\;p\;$, $$\calc p \in (A \times B) \cap (C \times D) \op=\hint{definition of $\;\cap\;$} p \in A \times B \;\land\; p \in C \times D \op=\hint{definition of $\;\times\;$, twice} \langle \exists x,y : p = (x,y) : x \in A \land y \in B \rangle \\&\land\; \langle \exists x,y : p = (x,y) : x \in C \land y \in D \rangle \op=\hints{logic: merge the two quantifications}\hint{-- to bring $\;A,C\;$ and $\;B,D\;$ together} \langle \exists x,y : p = (x,y) : x \in A \land y \in B \;\land\; x \in C \land y \in D \rangle \op=\hints{definition of $\;\cap\;$, twice -- this introduces}\hint{the sets we're interested in} \langle \exists x,y : p = (x,y) : x \in A \cap C \;\land\; y \in B \cap D \rangle \op=\hint{definition of $\;\times\;$} p \in (A \cap C) \times (B \cap D) \endcalc$$

So by extensionality this proves that $\;\cap\;$ and $\;\times\;$ "distribute over each other": $$ \tag 1 (A \times B) \cap (C \times D) \;=\; (A \cap C) \times (B \cap D) $$

Now to complete our proof, we must investigate what happens when the right hand side of $\Ref 1$ is empty. Comparing the shapes of the right hand sides of $\Ref 1$ and $\Ref 0$, it seems reasonable to try and investigate more generally $\;V \times W = \varnothing\;$, for any sets $\;V,W\;$. Therefore we calculate as follows: $$\calc V \times W = \varnothing \op=\hint{basic property of $\;\varnothing\;$} \langle \forall p :: p \not\in V \times W \rangle \op=\hint{definition of $\;\times\;$} \langle \forall p :: \lnot \langle \exists x,y : p = (x,y) : x \in V \land y \in W \rangle \rangle \op=\hints{logic: DeMorgan, i.e. $\;\lnot\exists \equiv \forall\lnot\;$;}\hint{merge quantifications} \langle \forall p,x,y : p = (x,y) : x \not\in V \lor y \not\in W \rangle \op=\hint{logic: one-point rule for $\;p\;$} \langle \forall x,y :: x \not\in V \lor x \not\in W \rangle \op=\hints{logic: simplify by splitting quantification}\hint{over two separate variables} \langle \forall x :: x \not\in V \rangle \;\lor\; \langle \forall y :: y \not\in W \rangle \op=\hint{basic property of $\;\varnothing\;$, twice} V = \varnothing \;\lor\; W = \varnothing \endcalc$$

This proves $$ \tag 2 V \times W = \varnothing \;\equiv\; V = \varnothing \;\lor\; W = \varnothing $$

And it is now clear that $\Ref 0$ follows directly from $\Ref 1$ and $\Ref 2$.

---

For me, there are three nice things about this style of designing and writing proofs.

First, notice how all of the steps in the above calculations are either taken to make progress (like expanding definitions), or driven by the desire to simplify (like merging quantifications), or taken to introduce specific expressions (like $\;A \cap C\;$). In other words, by choosing the correct starting point, most every step was forced, or at least reasonably to try.

Second, this calculational style makes it easier to directly prove an equivalence, instead of having to prove both directions separately with similar arguments. In this specific case our proof actually proves a stronger version of $\Ref 0$, since we proved both sides to be equivalent.

Finally, we were able to cleanly separate two different concepts: $\Ref 1$ is about distributing $\;\times\;$ and $\;\cap\;$ over each other, and $\Ref 2$ is about emptyness of $\;\times\;$.