## 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}$