## Fundamentals

June 2020

**Problem 1: Check the distributive laws for \(\cup\) and \(\cap\), and DeMorgan's laws.**

Starting with the first distributive law,

\[A \cap (B \cup C) = (A \cap B) \cup (A\cap C)\]

\[x \in A \cap (B \cup C) \iff x \in A \ \textrm{and} \ (x \in B \ \textrm{or} \ x \in C)\]

\[\iff (x \in A \ \textrm{and} \ x \in B) \ \textrm{or} \ (x \in A \ \textrm{and} \ x \in C) \iff (A \cap B) \cup (A\cap C)\]

Very similar logic applies to the second distributive law, \(A \cup (B \cap C) = (A \cup B) \cap (A\cup C)\)

Next, we have DeMorgan's first law (to be honest, I'm not sure what the order is),

\[A - (B \cup C) = (A - B)\cap (A-C)\]

\[x \in A - (B \cup C) \iff x \in A \ \textrm{and} \ x \not\in B \ \textrm{and} \ x \not\in C\]

\[\iff x \in A - B \ \textrm{and} \ x \in A - C \iff (A-B) \cap (A-C) \]

Once again, similar logic applies to DeMorgan's other law,

\[A - (B \cap C) = (A-B) \cup (A - C)\]

\[\tag*{$\blacksquare$}\]

**Problem 9: Formulate and prove DeMorgan's laws for arbitrary unions and intersections**

Starting with the law for unions, we must prove that, for some collection \(\mathcal{B}\) (a set of sets)

\[A - \left(\bigcup\limits_{B \in \mathcal{B}} B\right) = A - \left(B_1 \cup \cdots \cup B_n \right) = (A - B_1) \cap \cdots \cap (A - B_n) = \bigcap\limits_{B \in \mathcal{B}} (A - B)\]

\[A - \left(\bigcup\limits_{B \in \mathcal{B}} B\right) \iff x \in A \ \textrm{and} \ x \not\in \bigcup\limits_{B \in \mathcal{B}} B \iff x \in A \ \textrm{and} \ x \not\in B_1 \ \textrm{and} \ \cdots \ \textrm{and} \ x \not\in B_n\]

\[\iff x \in A - B_1 \ \textrm{and} \ \cdots \ \textrm{and} \ x \in A - B_n \iff x \in \bigcap\limits_{B \in \mathcal{B}} (A - B) \ \ \ QED\]

Once again, a very similar process can be used to prove DeMorgan's law for arbitrary intersections, \(A - \left(\bigcap\limits_{B \in \mathcal{B}} B\right) = \bigcup\limits_{B \in \mathcal{B}} (A - B)\)

\[\tag*{$\blacksquare$}\]