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!

Union of countable sets is countable

  1. May 18, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that a finite union of countable sets is also countable. Is an infinite union of countable sets also countable?

    2. Relevant equations
    A set S is countable if and only if there exists an injection from S to N.

    3. The attempt at a solution
    I will attempt prove it for the case of 2 sets. Proving it for a finite collection of sets follows analogously. Suppose the countable sets are A and B. Then there are injections [itex] f_{A} [/itex] and [itex] f_{B} [/itex] from A to N and B to N respectively. We need to show the existence of an injection from {A+B} to N where + denotes union.

    Since {A+B} is the union of A and B, certainly it contains an element that is in at least A or in B (or in both A and B). Then each element of {A+B} has an injective mapping to N, since each element of {A+B} is in A or in B.

    Does this complete the proof? Is this rigorous?

    And what about the case for an infinite union?

    Last edited: May 18, 2013
  2. jcsd
  3. May 18, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi BiP! :smile:
    Sorry, but that doesn't make any sense :redface:

    Why don't you try to construct a mapping? :wink:
  4. May 19, 2013 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need a mapping that avoids mapping an element of A-B and an element of B-A to the same element in N.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted