Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cartesian product of a family of countable sets is countable!

  1. Sep 13, 2009 #1
    Proposition: Let [tex] \{A_n\}_{n\in I}[/tex] be a family of countable sets. Prove that

    [tex] \bigotimes_{i=1}^n A_i[/tex]

    is a countable set.

    Proof:

    Since [tex] \{A_n\}_{n\in I}[/tex]

    are countable, there are 1-1 functions

    [tex] f_n:A_n->J[/tex]

    (J, the set of positive integers)

    Now let us define a function

    [tex] h:\bigotimes_{i=1}^n A_i->J[/tex]

    such that

    [tex] h(a_1,a_2,...,a_n)=(p_1)^{f_1(a_1)}*(p_2)^{f_2(a_2)}*...*(p_n)^{f_n(a_n)}[/tex]


    Where p_i are prime numbers such that

    [tex] 2\leq p_1<p_2<...<p_n[/tex]

    Now from the Fundamental Theorem of Arithmetic,it is clear that h is a 1-1 function. So, based on some previous theorems, we conclude that

    [tex]\bigotimes_{i=1}^n A_i[/tex]

    is a countable set.

    Is this correct?
     
  2. jcsd
  3. Sep 13, 2009 #2
    Your topic title should include the word finite (you have written it up as such in your proposition, though)

    That is pretty much the proof I have always seen for the theorem, although you may have to explain the 'previous theorems' you mentioned
     
  4. Sep 13, 2009 #3
    THe previous theorem(s) are basically that every infinite subset of J is countable. And also that every subset of a countable set is countable.

    The reason i posted this is that i've only seen a theorem that proves for the case of only two sets A, B, so i wanted to generalize on the idea. THe motvation behind this came from another problem i was working on. It looked like i needed to prove this proposition before could tackle that problem...and it worked out fine.
     
  5. Sep 14, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    In fact, it is true that a the union of countable collection of countable sets is countable:
    Imagine writing the sets in a row and the members of each set is a column below the set. Now, "zig-zag" through the array.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cartesian product of a family of countable sets is countable!
Loading...