Looking back: De Morgan’s Laws

It’s Spring Quarter, which means roughly 20 students at Seattle University are taking MATH-310 (our “introductions to proof” class). The class is offered once a year with the goal of preparing students for higher math (such as Real Analysis and Abstract Algebra). The material varies pretty wildly depending on who is teaching it, but one thing is for sure: students learn about proofs in propositional and first-order logic, and they learn about sets (from the naive approach).

In logic, we have these two way-important rules:

$\neg\left(a \lor b\right) = \left(\neg a\right) \land \left(\neg b \right)$
$\neg\left(a \land b\right) = \left(\neg a\right) \lor \left(\neg b \right)$

In set theory, we have these two way-important rules:

$\left(A \cap B\right)^c = A^c \cup B^c$
$\left(A \cup B\right)^c = A^c \cap B^c$

Both pairs of rules are called “De Morgan’s law.” So what, did De Morgan just go around making statements about what we intuitively think of as “negation?”

Nope. This is just an examle of the same thing in different form. The set-theoretic statements can be produced from the logic, which we will now do.

Assume De Morgan’s laws in logic. Let $A,B,S$ be sets such that $A,B \subseteq S$ , and define propositions $P_A(\cdot), P_B(\cdot)$ on $S$ by

$P_A(s) = \begin{cases} \text{True} & \text{ if } s \in A \\ \text{False} & \text{ if } s \not\in A \text{,}\end{cases} \text{ and } P_B(s) = \begin{cases} \text{True} & \text{ if } s \in B \\ \text{False} & \text{ if } s \not\in B \text{.}\end{cases}$

Then
$\left(A \cap B\right)^c = \left\lbrace s \in S : s \not\in A \cap B \right\rbrace$
$= \left\lbrace s \in S : \neg\left(P_A(s) \land P_B(S)\right) \right\rbrace$
$= \left\lbrace s \in S : \neg P_A(s) \lor \neg P_B(s) \right\rbrace$
$= A^c \cup B^c \mathrm,$
which is what we wanted to show.