Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.