Union with Intersection equals Intersection with Union iff Subset

From ProofWiki
Jump to navigation Jump to search


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


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


Necessary Condition

Let $C \subseteq A$.

We have:

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

and another way:

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


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


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.