Munkres - Fundamentals

Adar Kahiri
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) \ \ \ QED\] 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) \ \ \ QED\] Once again, similar logic applies to DeMorgan's other law, \[A - (B \cap C) = (A-B) \cup (A - C)\]

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)\]