If $A1, A2,...., A_m$ are each countable sets then $A1\cup A2\cup.... \cup A_m$ is countable. Why can't we use induction to prove that if $A_n $ is countable for all n then $\bigcup_{n=1}^\infty A_n$ is countable.


This is a common mistake. Induction can be used to show that a statement $P(n)$ is true for infinitely many $n$ (like $n=1, 2, 3, \ldots$), but this does NOT mean that $P(\infty)$ is true (or that it even makes sense).

For a related but more severe example, let $A_n = \{n\}$ for $n=1, 2, 3, \ldots$. Now prove by induction that $\bigcup_{i=1}^n A_i$ is finite. (This is obviously true without induction, since the union is just $\{1, 2, \ldots, n\}$.) But by your approach, you would be able to argue that $\bigcup_{i=1}^\infty A_i$ is finite, which is really false.

| cite | improve this answer | |
  • $\begingroup$ I don't understand what is $\;P(\infty)\;$ supposed to mean, in particular because ordinary induction (weak or strong) actually means that under this and that assumption, the claim is true for all the naturals (or all the naturals beginning with some of them and up). $\endgroup$ – DonAntonio Feb 15 '19 at 19:49
  • 1
    $\begingroup$ It means "naively plug in $\infty$ for $n$ in the statement" which is of course nonsense (and the root of OP's problem). $\endgroup$ – Randall Feb 15 '19 at 19:50
  • $\begingroup$ (No offense to OP. It's a common misconception.) $\endgroup$ – Randall Feb 15 '19 at 20:15
  • $\begingroup$ Thanks for the clarification $\endgroup$ – pinaki nayak Feb 16 '19 at 5:33

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.