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:

\(\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

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

Retrieved from "https://proofwiki.org/w/index.php?title=Union_with_Intersection_equals_Intersection_with_Union_iff_Subset&oldid=416800"