Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$
State and prove the base case for an inductive proof, meaning that the identity is true when $n=2$.
State and prove the inductive step, where one shows that the identity is true for general $n>2$, assuming it is true for $n−1$.
I proved for the base case but I am having a hard time for the inductive step can anyone please help me out.
Best Answer
We show that if the result holds for $n=k$, where $k\ge 2$, then it holds for $n=k+1$.
Note that $$\bigcap_{i=1}^{k+1} A_i =\left(\bigcap_1^k A_i\right) \cap A_{k+1}.\tag{$1$}$$ For simplicity write $B$ for $\bigcap_{i=1}^k A_i$.
Thus we are trying to find an alternate expression for $\left(\bigcap_{i=1}^{k+1} A_i\right)^c$, that is, for $(B\cap A_{k+1})^c$.
By the base case $n=2$, $(B\cap A_{k+1})^c=B^c \cup A_{k+1}^c$.
By the induction hypothesis, $B^c=\bigcup_{i=1}^k A_i^c$.
But $$\left(\bigcup_{i=1}^k A_i^c \right)\cup A_{k+1}=\bigcup_{i=1}^{k+1} A_i^c,$$ and we are finished.