# $(A\cap B)\cup C = A \cap (B\cup C)$ if and only if $C \subset A$

I have a set identity: $(A \cap B) \cup C = A \cap (B \cup C)$ if and only if $C \subset A$.

I started with Venn diagrams and here is the result:

It is evident that set identity is correct. So I started to prove it algebraic:

1) According to distributive law: $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$

2) ...

I stuck a little. Because $C$ is a subset of $A$. I thought of pulling out: $(B \cup C)$ but it seems wrong step to me.

How to prove this identity having in mind that $C \subset A$?

Updated

Venn diagram for $C ⊈ A$

• In addition to the answers: Your Venn diagrams are not entirely correct, for all of $C$ should be green. – Lord_Farin Oct 29 '13 at 11:53

It’s a little easier to go the other way: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$, and you’d like to show that this equals $(A\cap B)\cup C$ if and only if $C\subseteq A$.

• Suppose first that $C\subseteq A$; how can you simplify $A\cap C$?
• Now suppose that $C\nsubseteq A$; then there is some $c\in C\setminus A$. Show that this $c$ is an element of $(A\cap B)\cup C$ but not of $(A\cap B)\cup(A\cap C)$, so that these two sets cannot be equal.

Your Venn diagrams show what happens when $C\subseteq A$, so they’re useful in proving one direction of the desired result: if $C\subseteq A$, then the two sets are equal. To see how you might prove the other direction, i.e., that if $C\nsubseteq A$, then the two sets are not equal, you’d do better to look at a Venn diagram showing $C\nsubseteq A$.

• I added diagram for case when C ⊈ A, but this way this identity is incorrect. So I think I should make an assumption that C is a full subset of A. Or I didn't catch the idea :( – Dragon Oct 29 '13 at 12:11
• @Dragon: That’s exactly the point: you want to show that when $C\nsubseteq A$, the identity fails. That’s the only if half of the proof. What may be throwing you off is that I’ve replaced identity implies $C\subseteq A$ with its (logically equivalent) contrapositive, $C\nsubseteq A$ implies failure of identity. – Brian M. Scott Oct 29 '13 at 12:13
• So one can say, if suppose that C ⊈ A this identity fails. Otherwise it is correct. To simplify A∩C... according to commutative law A∩C = C∩A or A \ -C. But this isn't simplification, isn't it? – Dragon Oct 29 '13 at 12:33
• @Dragon: No, $A\cup C=A$; $A\cap C=C$, the smaller of the two sets. (It may feel a bit like an exam, but the more I can get you to work out on your own, the better you’ll understand it.) – Brian M. Scott Oct 29 '13 at 12:56
• @Dragon: Let $p$ be the statement that $(A\cap B)\cup C=A\cap(B\cup C)$, and let $q$ be the statement that $C\subseteq A$. You’re supposed to prove that $p\leftrightarrow q$. In both of your arguments you’ve assumed $q$, that $C\subseteq A$, so both of your arguments show that $q\to p$. Neither of them shows that $p\to q$, the other direction of the if and only if ($\leftrightarrow$). My suggestion is that instead of trying to prove $p\to q$ directly, by assuming $p$ and somehow deducing $q$, you try instead to prove $\neg q\to\neg p$; this is logically equivalent and easier to do. – Brian M. Scott Oct 29 '13 at 15:11

Here is a full algebraic proof. Let's first expand the definitions:

\begin{align} & (A \cap B) \cup C = A \cap (B \cup C) \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & \langle \forall x :: x \in (A \cap B) \cup C \;\equiv\; x \in A \cap (B \cup C) \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$ and $\;\cap\;$, both twice"} \\ & \langle \forall x :: (x \in A \land x \in B) \lor x \in C \;\equiv\; x \in A \land (x \in B \lor x \in C) \rangle \\ \end{align}

Now we have a choice to make: do we distribute $\;\lor\;$ over $\;\land\;$ in the left hand side, or $\;\land\;$ over $\;\lor\;$ in the right hand side? Since this expression is completely symmetric, we arbitrarily choose to distribute on the left hand side, and continue our logical simplification after that:

\begin{align} \equiv & \;\;\;\;\;\text{"distribute $\;\lor\;$ over $\;\land\;$ on left hand side"} \\ & \langle \forall x :: (x \in A \lor x \in C) \land (x \in B \lor x \in C) \;\equiv\; x \in A \land (x \in B \lor x \in C) \rangle \\ \equiv & \;\;\;\;\;\text{"extract common conjunct out of $\;\equiv\;$"} \\ & \langle \forall x :: x \in B \lor x \in C \;\Rightarrow\; (x \in A \lor x \in C \equiv x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"simplify one way of rewriting $\;\Rightarrow\;$"} \\ & \langle \forall x :: x \in B \lor x \in C \;\Rightarrow\; (x \in C \Rightarrow x \in A) \rangle \\ \equiv & \;\;\;\;\;\text{"combine both antecedents"} \\ & \langle \forall x :: (x \in B \lor x \in C) \land x \in C \;\Rightarrow\; x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"simplify antecedent: use $\;x \in C\;$ in other side of $\;\land\;$"} \\ & \langle \forall x :: x \in C \;\Rightarrow\; x \in A \rangle \\ \end{align}

Now we only have to wrap up:

\begin{align} \equiv & \;\;\;\;\;\text{"definition of $\;\subseteq\;$"} \\ & C \subseteq A \\ \end{align}

By Distributivity,

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

Suppose $C \subset A$, then $A \cup C = A$ by definition. Therefore $(A \cap B) \cup C = A \cap (B \cup C )$

Conversely, suppose $(A \cup C) \cap (B \cup C ) = A \cap (B \cup C )$. We show $C \subset A$. But, by the equality, it is obvious that $A \cup C = A$. In other words, $C$ must be inside $A$

• Hm... "it is obvious" is always a tricky phrase. E.g. this observation wouldn't work if we'd replace $B\cup C$ by $\varnothing$. – Lord_Farin Oct 29 '13 at 11:52