1
$\begingroup$

Is $(A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D)$ true for all sets $A, B, C$ and $ D?$

I tried to wrap my head around this, but I have absolutely no idea what is going on here. How could I possibly go about trying to prove this? Or disprove it?

Any help or guidance would be appreciated.

$\endgroup$
  • $\begingroup$ What examples did you try? How about $A=\{a\},B=\{b\},C=\{c\},D=\{d\}$? $\endgroup$ – bof Apr 15 '15 at 8:41
  • 3
    $\begingroup$ dave, please do not vandalize your post. $\endgroup$ – André 3000 Apr 15 '15 at 11:59
11
$\begingroup$

No, take $A=D=\{1\}$ and $B=C=\{2\}$.

$$\begin{array}{c} \begin{array}{c|cc} 2&\bullet&\bullet\\ 1&\bullet&\bullet\\ \hline &1&2\\ \end{array}\\\\ (A\cup C)\times(B\cup D) \end{array} \qquad\qquad \begin{array}{c} \begin{array}{c|cc} 2&\bullet&\\ 1&&\bullet\\ \hline &1&2 \end{array}\\\\ (A\times B)\cup(C\times D) \end{array}$$

$\endgroup$
  • 2
    $\begingroup$ I took the liberty of adding a diagram; feel free to delete it if you prefer. $\endgroup$ – Brian M. Scott Apr 15 '15 at 14:32
  • $\begingroup$ @BrianM.Scott no it's great (and very esthetic), thank you very much :). $\endgroup$ – Surb Apr 15 '15 at 14:33
10
$\begingroup$

Proof without words

Let $A=[0,1]=B$ and $C=[1,2]=D$

Here the first figure represents $(A\times B) \cup (C\times D)$ while the second one represents $(A\cup C) \times (B\cup D).$

$\endgroup$
3
$\begingroup$

Comment: I thought this problem looked familiar--I encountered it some time ago at the beginning of a real analysis class (surveying proof techniques, basic set theory, etc.). Although you may have encountered this problem elsewhere, it is problem 1.9.25 in Witold Kosmala's book A Friendly Introduction to Analysis. There, it occurs as a review problem where you are supposed to label the statement as true or false. "If a statement is true, prove it. If not, (i) given an example of why it is false, and (ii) if possible, correct it to make it true, and then prove it." I thought I would provide you with what I vaguely recall having answered with (both the counterexample and corrected statement with a proof).


Original claim: If $A,B,C,D$ are any sets, then $(A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)$.

[False] Counterexample. Let $A = \{ 1 \}, B = \{ 2 \}, C = \{ 3 \}, D = \{ 4 \}$. Then

  • $A \cup C = \{1,3\}$;
  • $B \cup D = \{2,4\}$;
  • $(A\cup C) \times (B \cup D) = \{(1,2),(1,4),(3,2),(3,4)\}$;
  • $A \times B = \{(1,2)\}$;
  • $C\times D = \{(3,4)\}$;
  • $(A \times B) \cup (C \times D) = \{(1,2),(3,4)\}$.

From this example, it is clear that $(A \times B) \cup (C \times D) \subseteq (A\cup C) \times (B \cup D)$, but there is not mutual subset inclusion, for $(A\cup C) \times (B \cup D) \nsubseteq (A \times B) \cup (C \times D)$.


Corrected claim: $(A \times B) \cup (C \times D) \subseteq (A\cup C) \times (B \cup D)$.

[True] Proof. Denote $\phi \colon (A \times B) \cup (C \times D)$ and $\sigma \colon (A\cup C) \times (B \cup D)$. Suppose $(p,q) \in \phi$. Then $(p,q)\in A\times B$ or $(p,q) \in C \times D$. Thus, $p \in A$ or $p \in C$; i.e., $p \in A \cup C$. Also, $q \in B$ or $q \in D$; i.e., $q \in B \cup D$. Thus, $(p,q) \in (A \cup C) \times (B \cup D)$, and, consequently, $(A \times B) \cup (C \times D) \subseteq (A\cup C) \times (B \cup D)$. $\blacksquare$

$\endgroup$
2
$\begingroup$

Actually, the equality is very rarely true. It's simple to see what is happening if you imagine $A,B,C,D$ as intervals in $\mathbb R^3$. For example, take $A=B=[0,1]$ and $C=D=[1,2]$. Then, $(A\cup C)\times (B\cup D) = [0,2]\times [0,2]^2$, i.e. the whole square.

On the other hand, $(A\times B)\cup (C\times D) = [0,1]^2\cup [1,2]^2$.

$\endgroup$
0
$\begingroup$

It is not always true. The actual truth is (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D) To proof that (A × B) ∪ (C × D) ≠ (A ∪ C) × (B ∪ D), you can take A,B as null sets, then it would be easy.

$\endgroup$

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.