----- > [!proposition] Proposition. ([[De Morgan's Laws]]) > Let $X$ be a set. Let $A,B\subset X$. Then we have $\begin{align} X - (A \cup B) = & (X-A) \cap (X - B) \\ \text{ and } & \\ X - (A \cap B) = & (X-A) \cup (X-B). \end{align}$ > [!proof]- Proof. ([[De Morgan's Laws]]) > **Distribution over union.** First, let $x \in X - A\cup B$. Then $x \notin A$, so $x \in X - A$, and $x \notin B$, so $x \in X - B$. Hence $x \in X - A$ and $x \in X - B$ so we have $x \in (X-A) \cap (X-B)$. For the reverse inclusion, let $x \in (X-A) \cap (X-B)$. Then $x \notin A$ and $x \notin B$. So $x \notin A \cup B$. > **Distribution over intersection.** First, let $x \in X-(A \cap B)$. Then it is not the case that $x \in A$ and $x \in B$, i.e., either >- $x \in A$ with $x \notin B$, implying $x \in X-B$; >- or $x \notin A$ with $x \in B$, implying $x \in X-A$; >- or $x \notin A$ with $x \notin B$, implying $x \in X-A$ and $x \in X-B$. > Thus $x \in (X-B) \cup (X-A)$. For the reverse inclusion, let $x\in (X-B) \cup (X-A)$. Then $x \notin B$ or $x \notin A$, therefore $x \notin A \cap B$. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```