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:

  1. \neg\left(a \lor b\right) = \left(\neg a\right) \land \left(\neg b \right)
  2. \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:

  1. \left(A \cap B\right)^c = A^c \cup B^c
  2. \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.

Advertisements
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: