# Prove$\overline{(A \cap B \cap C)} = \overline{A} \cup \overline{B} \cup \overline{C}$ By Subsets

This problem I am trying to solve is one I alluded to in this thread: Proving By Subsets

I am having difficulty with proof by subsets, so I am aware that I am missing steps; I would certainly appreciate it if someone could help me with this.

Suppose that $x \in \overline{(A \cap B \cap C)}$; for $x$ to be in this set, $x$ can't be in $(A \cap B \cap C)$, that is, $X \notin (A \cap B \cap C)$. This means that $x$ can't be in $A$, $B$, and $C$ ; however, by this fact, $x$ can be in $\overline{A}$, $\overline{B}$, or $\overline{C}$. Thus, when $x \in \overline{(A \cap B \cap C)}$, $x$ is also in $\overline{A} \cup \overline{B} \cup \overline{C}$, further implying that $x \in \overline{(A \cap B \cap C)} \subseteq \overline{A} \cup \overline{B} \cup \overline{C}$

Now, suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$, then $x$ can't be in $A$, $B$, or $C$, which means that $x$ can be in everything else, or, $x$ can be in $\overline{(A \cap B \cap C)}$. This shows that $\overline{A} \cup \overline{B} \cup \overline{C} \subseteq \overline{(A \cap B \cap C)}$

As I said, it just seems as though steps are missing and reasons why I am able to conclude the various things that I do in my proof.

-
@Mack A better description than proof by subsets would be proof by double inclusion. –  Git Gud Mar 17 '13 at 15:28
You second argument is wrong (the second suppose paragraph). It will become clear if you draw a venn diagram. –  Patrick Li Mar 17 '13 at 15:30

Personally, I would write this down as a calculation using set extensionality: given sets $A$, $B$, and $C$, for every $x$ \begin{align*} & x \in \overline{(A \cap B \cap C)} \\ \equiv & \;\;\;\;\; \text{"definition of set complement"} \\ & \lnot (x \in A \cap B \cap C) \\ \equiv & \;\;\;\;\; \text{"definition of \cap, twice"} \\ & \lnot (x \in A \land x \in B \land x \in C)) \\ (*) \equiv & \;\;\;\;\; \text{"logic: De Morgan, i.e., distribute \lnot over \land"} \\ & \lnot (x \in A) \lor \lnot (x \in B) \lor \lnot (x \in C) \\ \equiv & \;\;\;\;\; \text{"definition of set complement, three times"} \\ & x \in \overline{A} \lor x \in \overline{B} \lor x \in \overline{C} \\ \equiv & \;\;\;\;\; \text{"definition of \cup, twice"} \\ & x \in \overline{A} \cup \overline{B} \cup \overline{C} \\ \end{align*}

and therefore the given two sets are equal.

Note how this translates set notation to logic notation, does essentially the same transformation in the key step $(*)$, and translates back.

(Yes, I know this is not a proof by subsets / double inclusion-- but in this case I don't see how that technique would lead to a clearer proof.)

-

Now suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$, then $x$ can't be in $A,B$ or $C$, is wrong, you only have $x$ can't be in $A,B$ and $C$.

Because $x \in \overline{A} \cup \overline{B} \cup \overline{C}$ is true iff $$x\in \overline A \vee x\in \overline{B} \vee x\in \overline{C}$$

-

We have $x\in \bar{A}\cup\bar{B}\cup\bar{C}$ then $x\in\bar{A}$ or $x\in\bar{B}$ or $x\in\bar{C}$ then $x\notin A$ or $x\notin B$ or $x\notin C$ which implies $x\notin A\cap B\cap C$

(otherwise, if $x\in A\cap B\cap C$ this will contradicts the fact that $x\in\bar{A}$ or $x\in\bar{B}$ or $x\in\bar{C}$)

which implies that $x\in\overline{A\cap B\cap C}$

Remark: in fact if you proved that $\overline{A\cap B}=\overline{A}\cup \overline{B}$ then you can show using induction that $$\displaystyle\overline{\bigcap_{i=1}^{n}A_i}=\bigcup_{i=1}^{n}\overline{A_i},$$ for any $n\in\Bbb N .$

-