Induction: the complement A1 U A2 … U An is the intersection of Ac 1, Ac 2, …, Ac n

Question

Prove by induction that the complement of $ A1 \cup A2...An = A1^c \cap A2^c ...\cap An^c$

My approach: basic step is true, $\overline A1 = A1^c$,

then assume $ A1 \cup A2...Ak = A1^c \cap A2^c ...\cap Ak^c$, prove the case of $k+1$ is true. How should I do that?

Answer 1

Hint: Your basic step must be $n=2$. Then since $$\overline{\bigcup_{i=1}^{n}A_i}=\overline{\left(\bigcup_{i=1}^{n-1}A_{i}\right)\cup A_n}$$ you can use the case $n=2$ and the induction hypothesis.

Answer 2

The basic structure is to show

1) $(A_1 \bigcup A_2 \ldots A_k \bigcup A_{k+1})^c \subset A_1^c \cap A_2^c \ldots A_k^c \cap A_{k+1}^c$

and

2) $ A_1^c \cap A_2^c \ldots A_k^c \cap A_{k+1}^c \subset (A_1 \bigcup A_2 \ldots A_k \bigcup A_{k+1})^c $

Let $x \in (A_1 \bigcup A_2 \ldots A_k \bigcup A_{k+1})^c$. Then $x \notin A_1 \bigcup A_2 \ldots A_k \bigcup A_{k+1}$. This implies $x \notin A_1 \bigcup A_2 \ldots A_k$ and $x \notin A_{k+1}$. Then use the induction, etc. and this accomplishes #1. Then do a similar thing for #2.