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}$

  • $\begingroup$ This is my first time doing a proof involving sets like this using induction. Not really sure how to approach it. $\endgroup$ – 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.