De Morgan's Laws

133. De Morgan's Laws

Allows going back and forth between unions and intersections

{(⋂_{𝑛} 𝑆_{𝑛})}^{𝑐} = ⋃_{𝑛} 𝑆_{𝑛}^{𝑐}

{(⋃_{𝑛} 𝑆_{𝑛})}^{𝑐} = ⋂_{𝑛} 𝑆_{𝑛}^{𝑐}

{(𝑆 \cap 𝑇)}^{𝑐} = 𝑆^{𝑐} \cup 𝑇^{𝑐}

𝑥 \in {(𝑆 \cap 𝑇)}^{𝑐} \Leftrightarrow 𝑥 \notin 𝑆 \cap 𝑇 \Leftrightarrow {\begin{cases} 𝑥 \notin 𝑆 \\ \lor \\ 𝑥 \notin 𝑇 \end{cases} \Leftrightarrow {\begin{cases} 𝑥 \in 𝑆^{𝑐} \\ \lor \\ 𝑥 \in 𝑇^{𝑐} \end{cases} \Leftrightarrow 𝑥 \in 𝑆^{𝑐} \cup 𝑇^{𝑐}

𝑆^{𝑐} \cap 𝑇^{𝑐} = {(𝑆 \cup 𝑇)}^{𝐶}

We start with the first De Morgan’s Law:

{(𝑆 \cap 𝑇)}^{𝑐} = 𝑆^{𝑐} \cup 𝑇^{𝑐}

and substitute:

\begin{aligned} 𝑆 & \to 𝑆^{𝑐} \\ 𝑆^{𝑐} & \to 𝑆 \\ 𝑇 & \to 𝑇^{𝑐} \\ 𝑇^{𝑐} & \to 𝑇 \end{aligned}

to obtain:

{(𝑆^{𝑐} \cap 𝑇^{𝑐})}^{𝑐} = 𝑆 \cup 𝑇

take the compliment of both sides:

{({(𝑆^{𝑐} \cap 𝑇^{𝑐})}^{𝑐})}^{𝑐} = {(𝑆 \cup 𝑇)}^{𝑐}

since the compliment of a compliment is the set itself:

𝑆^{𝑐} \cap 𝑇^{𝑐} = {(𝑆 \cup 𝑇)}^{𝐶}