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

Question

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.

Answer 1

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}