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$}\]