1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction- countably infinite sets

  1. Sep 25, 2008 #1


    User Avatar

    1. The problem statement, all variables and given/known data

    I have to prove by induction that the union of any finite set of countably infinite sets is countably infinite.

    2. Relevant equations

    I have already proven, in a previous problem, that the union of any 2 countably infinite sets is countably infinite.

    3. The attempt at a solution

    I think for the basis I should use the fact that I have already proven that the union of 2 such sets is countably infinite. And I have an intuitive understanding of how the proof should go from there. The set can be denoted as M={A1,A2,A3,...} where An is countably infinite but M is finite. I figure the from my earlier proof, I can go through and say A1 union A2 is countably infinite, and that quantity union A3 is countably infinite, and so on. But I'm not very good at formalizing this, and I'm not very familiar at all with inductive proofs.
  2. jcsd
  3. Sep 25, 2008 #2
    You're pretty much there. The induction step should be:

    (1) Assume that the union of N countably infinite sets is countably infinite
    (2) Show this implies that the union of N+1 countably infinite sets is countably infinite.

    Well, if you have a union of N countably infinite sets that is countably infinite, and you take the union of that set with one more, then you've proved it.
  4. Sep 25, 2008 #3


    User Avatar
    Science Advisor

    Suppose it is true that, for k countably infinite sets, A1 A2, ..., Ak, [itex]B= \cup_{i=1}^k A_i[/itex] is countably infinite. Now, suppose you have A1, A2, ..., Ak, Ak+1 countably infinite sets. What can you say about [itex]B\cup A_{k+1}[/itex]?
  5. Sep 25, 2008 #4


    User Avatar

    Okay, I've figured it out now. I was just having trouble understanding the procedure for an inductive proof. Thanks a lot!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Proof induction countably Date
Proof by Induction? May 24, 2017
Is my short induction proof correct? Apr 3, 2017
Proof by induction, ##(n!)^{2} \le (2n)!##. Mar 1, 2017
Induction Problem (Polya) Jul 3, 2016
Proving an equality using induction proof not working Jan 3, 2016