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

Countably infinite sets

  1. Dec 10, 2009 #1

    I was wondering if two sets are disjoint countably infinite sets why is their Cartesian product also countably infinite?

  2. jcsd
  3. Dec 10, 2009 #2
    You can order your two sets a_1,a_2,a_3,.... and b_1,b_2,b_3 mapping them onto the set of natural numbers.

    Then, you can form a triangular mapping recursively (like you do to prove that the set of rational numbers is countably infinite)... so:
    (a_1,b_1) maps to 1,
    (a_1,b_2) maps to 2,
    (a_2,b_1) maps to 3,
    (a_1,b_3) maps to 4,
    (a_2,b_2) maps to 5, etc. etc.
  4. Dec 12, 2009 #3
    Another way to think about the problem...

    Since we have two countably infinite sets call them A , B we can define two bijections:

    [tex]\alpha[/tex]: N [tex]\rightarrow[/tex] A and [tex]\varphi[/tex]: N [tex]\rightarrow[/tex] B.

    We can then define another function [tex]\zeta[/tex]: N [tex]\rightarrow[/tex] A X B as [tex]\zeta[/tex](n) = ( [tex]\alpha[/tex](n) , [tex]\varphi[/tex](n) ).

    [tex]\zeta[/tex] is a bijection since [tex]\alpha[/tex] and [tex]\varphi[/tex] are bijections and therefore A X B is countable.
  5. Dec 12, 2009 #4
    CharmedQuark, what you said isn't exactly correct, since your constructed function from N to AxB won't be surjective.
  6. Dec 12, 2009 #5


    User Avatar
    Science Advisor

    Good point, in fact, it is very badly non surjective!

    For example, if [itex]\alpha(2)= p[/itex] and [itex]\beta(2)= q[/itex], then [itex]\zeta(2)= (p, q)[/itex] but there is NO other [itex]\zeta(n)[/itex] giving a pair having p as its first member nor is there any other n so that [itex]\zeta(n)[/itex] is pair having q as its second member.
  7. Dec 12, 2009 #6
    Yeah I wrote it last night and wasn't paying attention to what I was writing. The function should instead be a function from N X N [tex]\rightarrow[/tex] A X B. Other than that little error the principle is the same. [tex]\zeta[/tex]( n[tex]_{1}[/tex] , n[tex]_{2}[/tex] ) = ( [tex]\alpha[/tex]( n[tex]_{1}[/tex] ) , [tex]\varphi[/tex]( n[tex]_{2}[/tex] ) ). This function is a bijection and N X N is countable so any cartesian product of two countably infinite sets is countable.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook