1
$\begingroup$

Let $A$, $B$, $C$, and $D$ be nonempty sets.

Does $(A\cup B)\cap(C\cup D)=(A\cap C)\cup(B\cap D)$?

It seems to be true by looking at Venn diagram, but I'm getting mixed up with the proof.

  • 2
    Let $B=C=A^c$ the complement of $A$ and let $D=A$. Is it true?2012-09-19
  • 1
    An exhaustive search for a counterexample only needs to consider 16 possible cases. One of those (at least) is a counterexample. See my answer below.2012-09-19
  • 1
    It is not hard to show that the right-hand side is a subset of the left-hand side. However, if you draw a Venn Diagram, you will see that "in general" the left-hand side has extra stuff.2012-09-19

2 Answers 2

5

No. Suppose $A=D=\emptyset$. Then $(A\cup B)\cap (C\cup D)=B\cap C$, but $(A\cap C)\cup (B\cap D)=\emptyset$.

This is still false if you require the sets to be nonempty. Let $A=D=\{0\}$. Then the first set is $(B\cap C)\cup \{0\}$ and the second is at most $\{0\}$, which are not equal in general.

  • 0
    Sorry, I meant to say nonempty sets. I will edit the question.2012-09-19
  • 1
    @GradEwnder It doesn't matter. Let $A=D=\{0\}$. Then the first set is $(B\cap C)\cup \{0\}$ and the second is $\{0\}$.2012-09-19
  • 1
    @AlexBecker: the second can even be empty if $0 \not \in B$, for example.2012-09-19
  • 0
    @RossMillikan Good point.2012-09-19
6

You could fill in this whole truth table. If there is one row in which the last two columns disagree, then that answers your question. $$ \begin{array}{|c|c|c|c|c|c|} \hline x\in A & x\in B & x\in C & x\in D & x\in(A\cup B)\cap(C\cup D) & x\in(A\cap C)\cup(B\cap D) \\ \hline T & T & T & T & \cdots & \cdots \\ T & T & T & f & \cdots & \cdots \\ T & T & f & T & \cdots & \cdots \\ T & f & T & T & \cdots & \cdots \\ f & T & T & T & \cdots & \cdots \\ T & T & f & f & \cdots & \cdots \\ T & f & T & f & \cdots & \cdots \\ f & T & T & f & T & f \\ T & f & f & T & \cdots & \cdots \\ f & T & f & T & \cdots & \cdots \\ f & f & T & T & \cdots & \cdots \\ T & f & f & f & \cdots & \cdots \\ f & T & f & f & \cdots & \cdots \\ f & f & T & f & \cdots & \cdots \\ f & f & f & T & \cdots & \cdots \\ f & f & f & f & \cdots & \cdots \\ \hline \end{array} $$