Set equality negation

Question

I am a first year computer science student, learning discrete mathematics. Let p denote the statement:

p: for all sets A, B, C, D,

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

I would like to write down the negation of p by building a counter example. Hence, I did:

$A = \{a\},\ B = \{b\},\ C = \{c\},\ D = \{d\}$

$\{a, b\}\cap\{c, d\} = \emptyset\cup \emptyset$

$\emptyset = \emptyset$

I totally missed the target. My lack experience in the field still prevents me from finding a different approach. Any hint would be highly appreciated.

Answer 1

We need an example for either $$(A\cup B)\cap(C\cup D)\not\subseteq(A\cap C)\cup(B\cap D)\tag1$$ or $$(A\cup B)\cap(C\cup D)\not\supseteq(A\cap C)\cup(B\cap D)\tag2$$ Let's try for (1) first; if that doesn't work we'll try (2). (Or you may already have observed that $(A\cup B)\cap(C\cup D)\supseteq(A\cap C)\cup(B\cap D),$ so (1) is the only way to go.)

We need an element $x$ which belongs to LHS but not RHS. For $x\in\text{LHS}$, we need $x\in A\cup B$ and $x\in C\cup D.$

For $x\in A\cup B$ we need $x\in A$ or $x\in B.$ By symmetry, one choice is as good as another, so let's decide on $x\in A.$

Next we need $x\in C$ or $x\in D.$ The symmetry has been broken, so we have to choose wisely. If we put $x\in C$ then we have $x\in A\cap C\subseteq\text{RHS},$ which we don't want; so we put $x\in D.$

Now, with $x$ in $A$ and $D$ (and nothing else), we have $x\in\text{LHS}$ and $x\notin\text{RHS}.$ That is, with $A=D=\{x\}$ and $B=C=\emptyset,$ we have $$(A\cup B)\cap(C\cup D)=\{x\}$$ and $$(A\cap C)\cup(B\cap D)=\emptyset.$$ By the way, for a problem like this, we can always get our counterexample by setting each set-variable equal to $\emptyset$ or to $\{x\}.$

Answer 2

Make $A$ and $C$ and $B$ and $D$ disjoint. We get the emptyset on the right. Make sure that $A \cup B = C \cup D \neq \emptyset$ as well.

Answer 3

That isn't a counterexample; you're looking for an example where you don't have equality.

What's the statement $(A\cup B)\cap(C\cup D)=(A\cap C)\cup (B\cap D)$ saying? You can translate it to saying that for any element $x$,

$x$ is in A or B and $x$ is in C or D

if and only if

$x$ is in A and C or $x$ is in B and D.

Now this isn't true, because another way for $x$ to satisfy the first statement is if $x$ is in A and D. So try to build a counterexample where some element is in A and D (but not B or C).

Answer 4

$A=\{a,b,c\}$, $B=\{d\}$, $C=\{d\}$, $D=\{a,e\}$, then $LHS=\{a,d\}$ and $RHS$ is the empty set.