Union with Intersection equals Intersection with Union iff Subset

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

$\paren {A \cap B} \cup C = A \cap \paren {B \cup C} \iff C \subseteq A$


Proof

Necessary Condition

Let $C \subseteq A$.

We have:

\(\displaystyle C\) \(\subseteq\) \(\displaystyle A\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle A \cap C\) \(=\) \(\displaystyle C\) Intersection with Subset is Subset‎
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {A \cap B} \cup \paren {A \cap C}\) \(=\) \(\displaystyle \paren {A \cap B} \cup C\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle A \cap \paren {B \cup C}\) \(=\) \(\displaystyle \paren {A \cap B} \cup C\) Intersection Distributes over Union


and another way:

\(\displaystyle C\) \(\subseteq\) \(\displaystyle A\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle A \cup C\) \(=\) \(\displaystyle A\) Union with Superset is Superset‎‎
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {A \cup C} \cap \paren {B \cup C}\) \(=\) \(\displaystyle A \cap \paren {B \cup C}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {A \cap B} \cup C\) \(=\) \(\displaystyle A \cap \paren {B \cup C}\) Intersection Distributes over Union

Thus:

$C \subseteq A \implies \paren {A \cap B} \cup C = A \cap \paren {B \cup C}$

$\Box$


Sufficient Condition

Let $\paren {A \cap B} \cup C = A \cap \paren {B \cup C}$.


Aiming for a contradiction, suppose $\exists x \in C: x \notin A$.

From Set is Subset of Union:

$C \subseteq \paren {A \cap B} \cup C$

and so by definition of subset:

$x \in \paren {A \cap B} \cup C$


From Intersection is Subset:

$A \cap \paren {B \cup C} \subseteq A$

and so (indirectly) by definition of subset:

$x \notin A \cap \paren {B \cup C}$


Hence by definition of subset:

$\paren {A \cap B} \cup C \nsubseteq A \cap \paren {B \cup C}$

that is:

$\paren {A \cap B} \cup C \ne A \cap \paren {B \cup C}$

This contradicts our initial assertion.


Hence by Proof by Contradiction:

$\neg \exists x \in C: x \notin A$

From Assertion of Universality:

$\forall x \in C: x \in A$

and so $C \subseteq A$ by definition of subset.

$\blacksquare$


Sources