📂Set Theory

Proof of De Morgan's Laws

Theorem ¹

• [1] De Morgan’s Laws: $$ \lnot (p \land q) \iff \lnot p \lor \lnot q \\ \lnot(p \lor q) \iff \lnot p \land \lnot q $$
• [2] De Morgan’s Theorem: $$ (A \cup B)^{c} = A^{c} \cap B^{c} \\ (A \cap B)^{c} = A^{c} \cup B^{c} $$

Description

De Morgan’s Laws and De Morgan’s Theorems refer to propositions and sets, respectively, but in everyday language, they are often not distinguished. Whether it’s called a law or a theorem, attaching De Morgan- means that by negating or taking the complement, the propositions or sets and symbols inside the parenthesis ‘flip’, that’s how it is understood.

Meanwhile, according to mathematical induction, not only is the following generalization possible, but it can also be extended to index families. $$ \begin{align*} \begin{matrix} \displaystyle \left( \bigcup_{i=1}^{\infty} X_{i} \right)^{c} = \bigcap_{i=1}^{\infty} (X_{i})^{c} \\ \displaystyle \left( \bigcap_{i=1}^{\infty} X_{i} \right)^{c} = \bigcup_{i=1}^{\infty} (X_{i})^{c} \end{matrix} &\qquad \& \begin{matrix} \displaystyle\left( \bigcup_{\alpha \in \forall } X_{\alpha} \right)^{c} = \bigcap_{\alpha \in \forall} (X_{\alpha})^{c} \\ \displaystyle \left( \bigcap_{\alpha \in \forall} X_{\alpha} \right)^{c} = \bigcup_{\alpha \in \forall } (X_{\alpha})^{c} \end{matrix} \end{align*} $$

Proof

[1]

Proven by truth tables.

Part 1. $\lnot (p \land q) \iff \lnot p \lor \lnot q$

---

Part 2. $\lnot(p \lor q) \iff \lnot p \land \lnot q$

■

[2]

Part 1. $(A \cup B)^{c} = A^{c} \cap B^{c}$

$$\begin{align*} x \in (A \cup B)^{c} \iff & \lnot (x \in A \cup B) \\ \iff & \lnot ( x \in A \lor x \in B ) \\ \iff & \lnot ( x \in A ) \land \lnot ( x \in B ) \\ \iff & x \in A^{c} \land x \in B^{c} \\ \iff & x \in ( A^{c} \cap B^{c} ) \end{align*} $$

---

Part 2. $(A \cap B)^{c} = A^{c} \cup B^{c}$

$$\begin{align*} x \in (A \cap B)^{c} \iff & \lnot (x \in A \cap B) \\ \iff & \lnot ( x \in A \land x \in B ) \\ \iff & \lnot ( x \in A ) \lor \lnot ( x \in B ) \\ \iff & x \in A^{c} \lor x \in B^{c} \\ \iff & x \in ( A^{c} \cup B^{c} ) \end{align*} $$

■