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: Countable union Proof

  1. Feb 4, 2012 #1
    1. The problem statement, all variables and given/known data
    If [itex] A_1,A_2.....A_n [/itex] are countable sets. Then the union
    [itex] A_1 \cup A_2\cup ......\cup A_n [/itex] is countable.
    3. The attempt at a solution
    Since we know there are an infinite amount primes I will assign each element in
    [itex] A_1 [/itex] to the first prime. I will take every element in [itex] A_1 [/itex]
    and raise this element to [itex] 2^x [/itex] where x is the ith element of the first set.
    then I will map all the elements in the second set the second prime.
    so the nth set will go to the nth prime.
    since these will all be natural numbers, the union of these sets is countable.
    Last edited: Feb 4, 2012
  2. jcsd
  3. Feb 4, 2012 #2


    User Avatar
    Gold Member

    It's easier than this, for A_1, align them to the set that of numbers 1 mod n, A_2 to the set of numbers 2 mod n, ..., A_n to sets of numbers of 0 mod n.
    each such set is enumarable and this is self evident a bijection from the union of A_i to N.

  4. Feb 4, 2012 #3
    ok, ya thats a good way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook