# Proving relationship between set complement, intersection and union

Show that $S_1 \cup S_2 = \overline{\overline{S_1}\cap \overline{S_2}}$.

So we want to show that the union of $S_1$ and $S_2$ is equal to the compliment of the intersection of the compliments of $S_1$ and $S_2$. I hope that makes sense!

I created some finite sets with some random values. Here's what I have so far but I'm stuck!

\begin{align*} S_1 &= \{1, 2, 3, 4\}\\ S_2 &= \{2, 3, 4, 5, 6\}\\ S_1 \cup S_2 &= \{1, 2, 3, 4, 5, 6\}\\ \overline{S_1} &= \{5, 6\} &\text{(everything in S_2 but not in S_1)}\\ \overline{S_2} &= \{1\} &\text{(everything in S_1 but not in S_2)} \end{align*} I don't see a way to intersect $\overline{S_1}$ and $\overline{S_2}$, can someone point me in the right direction please? Am I on the right track, or way off?

## migrated from cs.stackexchange.comSep 3 '15 at 8:46

This question came from our site for students, researchers and practitioners of computer science.

• Trying some finite sets with random values isn't "proof". You have to take the formal definitions and reason from them. What do you think the intersection of $S_1$ and $S_2$ (and their complements) is in your example? – Tom van der Zanden Sep 3 '15 at 8:41
• You need to check the definitions. The complement of $S_1$ is not "everything in $S_2$ but not in $S_1$" and you don't need a "way to intersect" two sets, any more than you need "a way to add two numbers": you just do what the definition tells you to do. Overall, no, you're not really on the right track. To prove an identity for general sets, it's not enough to prove that it works for some specific case: you must prove that it always works. What you have so far is OK as a first step towards understanding what's going on but it's a lot like proving that the product of two positive numbers... – David Richerby Sep 3 '15 at 8:41
• ... is always positive by saying, "Well, $2\times 3=6$, which is positive." – David Richerby Sep 3 '15 at 8:42

Let $x\in S_1\cup S_2$ $\Rightarrow$ $x\in S_1$ or $x\in S_1$ $\Rightarrow$ $x\notin S_1^c$ or $x\notin S_1^c$ $\Rightarrow$ $x\notin S_1^c\cap S_2^c$$\Rightarrow$ $x\in (S_1^c\cap S_2^c)^c$.
Hence $S_1\cup S_2\subset (S_1^c\cap S_2^c)^c$.
P.S. $A^c$ it's a complement of set $A$.
Strictly speaking you have to do complementation relative to another (super)set $V$. Then it will be easy to realize that $S_1 \cup S_2 = \{x\in V|x \in S_1 \lor x \in S_2\}$ and $\overline{\overline S_1 \cap \overline S_2} = \{x\in V| \neg( x \notin S_1 \land x \notin S_2 )\}$, but $x \in S_1 \lor x \in S_2 \Leftrightarrow \neg(x \notin S_1 \land x \notin S_2)$, so the sets are equal.