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.


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.


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.