1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Put $A_{k+1}$ inside the brackets and there you go $\endgroup$ – tommy1996q Sep 3 at 19:50
  • $\begingroup$ 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 $\endgroup$ – tommy1996q Sep 3 at 19:52
1
$\begingroup$

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}

$\endgroup$

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.