# Induction proof involving sets

Suppose $A_1,A_2,...A_n$ are sets in some universal set $U$, and $n\geq2$. Prove that $\overline{A_1 \cup A_2 \cup ... \cup A_n}$ = $\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_n}$

• This is my first time doing a proof involving sets like this using induction. Not really sure how to approach it. – Wilson Jul 22 '14 at 19:55

Prove the base case for $n=2$. So we have $\overline{A_1 \cup A_2} = \overline{A_1} \cap \overline{A_2}$. Assume it is true for $n=m$; i.e., $\overline{A_1 \cup A_2 \cup \ldots A_m}$ $=\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m}$.

Now, let $B = \overline{A_1 \cup A_2 \cup \ldots A_m}$. Then, $B =\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m}$ (by assumption).

So, $\overline{A_1 \cup A_2 \cup \ldots A_m \cup A_{m+1}}$ $= \overline{B \cup A_{m+1}}$ $= \overline{B} \cap \overline{A_{m+1}}$ (by the base case)

$=\overline{A_1 \cup A_2 \cup \ldots A_m} \cap \overline{A_3}$

$=\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m} \cap \overline{A_3}$

Proving base case is easy:

$x \in \overline{A_2 \cup A_2}$ $\iff x \notin A_1 \cup A_2$ $\iff x\notin A_1 \wedge x\notin A_2$ $\iff x \in \overline{A_1} \wedge x \in \overline{A_2}$ $\iff x \in \overline{A_1} \cap \overline{A_2}$