2
$\begingroup$

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: enter image description here

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$ enter image description here

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

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$.

$\endgroup$
  • $\begingroup$ 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 :( $\endgroup$ – Dragon Oct 29 '13 at 12:11
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 29 '13 at 12:13
  • $\begingroup$ 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? $\endgroup$ – Dragon Oct 29 '13 at 12:33
  • 1
    $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Oct 29 '13 at 12:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 29 '13 at 15:11
2
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Lord_Farin Oct 29 '13 at 11:52

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.