# Induction for $(A_1 \cap A_2 \cap … \cap A_n)^c = A^c_1 \cup A^c_2 \cup … \cup A^c_n$.

I need to do induction on this problem: $$(A_1 \cap A_2 \cap ... \cap A_n)^c = A^c_1 \cup A^c_2 \cup ... \cup A^c_n$$. Induction is new to me and this problem is hard to understand. The base case here I'm guessing is just that $$A^c_1 = A^c_1$$. Since this works we can go to the inductive hypothesis. Then I think we have to prove that $$(A_1 \cap A_2 \cap ... \cap A_k)^c \cap A_{k+1} = A^c_1 \cup A^c_2 \cup ... \cup A^c_k \cup A^c_{k+1}$$. I am not sure if these are the right steps and if so how to finish the proof.

• Put $A_{k+1}$ inside the brackets and there you go – tommy1996q Sep 3 '19 at 19:50
• Also, for the future, remember this. Induction doesn’t let you conclude for infinity. It does for arbitrarely large numbers, but NOT infinity. Try to think about a counterexample. Maybe you already knew this, but better safe then sorry – tommy1996q Sep 3 '19 at 19:52

The base case is $$(A_1\cap A_2)^c = A_1^c\cup A_2^c$$. To see this, we have \begin{align} x \in (A_1\cap A_2)^c &\iff x\notin A_1\cap A_2\\ &\iff x\notin A_1 \vee x\notin A_2\\ &\iff x\in A_1^c \vee x\in A_2^c\\ &\iff x\in A_1^c\cup A_2^c, \end{align} where $$\vee$$ denotes logical disjunction (OR). For the induction step, suppose that $$\left(\bigcap_{i=1}^n A_i\right)^c = \bigcup_{i=1}^n A_i^c$$ for some $$n\geqslant2$$. Then \begin{align} \left(\bigcap_{i=1}^{n+1} A_i\right)^c &= \left(A_{n+1}\cap\bigcap_{i=1}^n A_i\right)^c\\ &= A_{n+1}^c \cup\left(\bigcap_{i=1}^n A_i\right)^c\\ &= A_{n+1}^c \cup \bigcup_{i=1}^n A_i^c\\ &= \bigcup_{i=1}^{n+1} A_i^c. \end{align}