Explain why induction cannot be used to prove that : $$ (\cup_{n=1}^{\infty} A_n )^c= \cap _{n=1}^{\infty} (A_n) ^c $$

I don't think statement is true for infinite sets


$ A_1= {1,2,3,4,...} $

$ A_2 ={2,3,4,...}$

$A_3= {3,4,5,...}$

Now Consider the statement as
$ (\cup_{n=1}^{\infty} A_n ^c )^c= \cap _{n=1}^{\infty} (A_n) $ (Just assuming it to be true and replaced $A_n$ by its complement)

Now LHS is just empty set whilst RHS has infinite elements. Is this right ?

How do I do this ?

  • $\begingroup$ First you need to explain what the $A_n$ are, and in which context you use the notation $(-)^c$. Then you need a statement which depends on a (natural) number $n$, and if you want to prove that the statements holds for all such numbers, then you can use induction. The statement you want to prove is not of this form: there is nothing to do induction over. If you want to show an equality of sets you can take an element on the left and show that it also belongs on the right, and vice versa. $\endgroup$ – LetGBeTheGraph Aug 8 '19 at 8:22
  • $\begingroup$ They are subsets of real numbers $\endgroup$ – ReadThyOwnBook Aug 8 '19 at 8:29
  • 2
    $\begingroup$ Both the LHS and the RHS are empty in your example. Any candidate number $n$ is not in $A_{n+1}$, so it can't be in $\bigcap_{n=1}^{\infty}A_n$. $\endgroup$ – Bungo Aug 8 '19 at 8:32

Someone correct me if I'm wrong, but I believe the issue here is that while induction can prove

$$\left(\bigcup_{n=1}^{N}A_{n}\right)^{c} = \bigcap_{n=1}^{N}(A_{n})^{c}$$

for any positive integer $N$, it cannot be used to prove the infinite union and infinite intersection are equal. The result however is in fact true in general, even for uncountable unions and intersections - this is called DeMorgan's Law. $$\left(\bigcup_{i\in I}A_{i}\right)^{c} = \bigcap_{i\in I}A^{c}_{i}$$ A proof can be seen here https://math.stackexchange.com/a/660687

  • $\begingroup$ why induction can't be used for infinite unions is the question ? $\endgroup$ – ReadThyOwnBook Aug 9 '19 at 0:13
  • $\begingroup$ @ReadThyOwnBook Induction in general can't take you from the finite case to the infinite case. For example, "the intersection of two open sets is open" is a true statement, and induction allows us to conclude that "the intersection of any finite number of open sets is open." But induction does not allow us to conclude that "the intersection of a countably infinite number of open sets is open", and in fact it's not true. $\endgroup$ – Bungo Aug 9 '19 at 4:59
  • $\begingroup$ why not ? because we are going towards infinity anyhow i.e if we assume statement is true for n then prove it for n+1 then this process can be kept on $\endgroup$ – ReadThyOwnBook Aug 9 '19 at 5:07
  • $\begingroup$ @ReadThyOwnBook Sure, so that will get you to any finite $n$. But as my example shows, that's not the same as getting to infinity. $\endgroup$ – Bungo Aug 9 '19 at 5:54

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.