(related to Proposition: De Morgan's Laws (Sets))

- Suppose that $A$ and $B$ are sets.
- We want to show that for the set intersection "$\cap$", set union "$\cup$" and set complent "$^C$", the laws $(A\cap B)^C=(A^C)\cup (B^C)$ and $(A\cup B)^C=(A^C)\cap (B^C)$ hold.

- Let $x\in (A\cap B)^C$.
- According to the definition of complent, we have $x\not\in (A\cap B)$.
- According to the definition of set intersection, if $x\in (A\cap B)$, then $x\in A \wedge x\in B$, which is negated, i.e. $\neg (x\in A \wedge x\in B).$
- According to the De Morgan's laws for logic, this means that $x\not\in A\vee x\not\in B.$
- According to the definition of complent, we get $x\in A^C\vee x\in B^C.$
- According to the definition of union, we get $x\in (A^C)\cup (B^C).$
- It follows from the definition of subsets $(A\cap B)^C\subseteq (A^C)\cup (B^C).$

- Let $x\in (A^C)\cup (B^C)$.
- According to the definition of union, we get $x\in (A^C)\vee x\in (B^C).$
- According to the definition of complent, we have $x\not\in A\vee x\not\in B$.
- According to the De Morgan's laws for logic, this means that $\neg(x\in A\wedge x\in B).$
- According to the definition of set intersection, we get $\neg (x\in (A\cap B)).$
- According to the definition of negation, this is equivalent to $x\not\in (A\cap B).$
- By the definition of complent, we get $x\in(A\cap B)^C.$
- It follows from the definition of subsets $(A^C)\cup (B^C)\subseteq (A\cap B)^C.$

- From both steps of Part 1 and the equality of sets it follows that $(A\cap B)^C=(A^C)\cup (B^C).$

- Let $x\in (A\cup B)^C$.
- According to the definition of complent, we have $x\not\in (A\cup B)$.
- According to the definition of set union, if $x\in (A\cup B)$, then $x\in A \vee x\in B$, which is negated, i.e. $\neg (x\in A \vee x\in B).$
- According to the De Morgan's laws for logic, this means that $x\not\in A\wedge x\not\in B.$
- According to the definition of complent, we get $x\in A^C\wedge x\in B^C.$
- According to the definition of intersection, we get $x\in (A^C)\cap (B^C).$
- It follows from the definition of subsets $(A\cup B)^C\subseteq (A^C)\cap (B^C).$

- Let $x\in (A^C)\cap (B^C)$.
- According to the definition of intersection, we get $x\in (A^C)\wedge x\in (B^C).$
- According to the definition of complent, we have $x\not\in A\wedge x\not\in B$.
- According to the De Morgan's laws for logic, this means that $\neg(x\in A\vee x\in B).$
- According to the definition of set union, we get $\neg (x\in (A\cup B)).$
- According to the definition of negation, this is equivalent to $x\not\in (A\cup B).$
- By the definition of complent, we get $x\in(A\cup B)^C.$
- It follows from the definition of subsets $(A^C)\cap (B^C)\subseteq (A\cup B)^C.$

- From both steps of Part 2 and the equality of sets it follows that $(A\cup B)^C=(A^C)\cap (B^C).$∎

**Kane, Jonathan**: "Writing Proofs in Analysis", Springer, 2016