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!

Analysis and countable sets

  1. Sep 22, 2009 #1
    1. The problem statement, all variables and given/known data

    Definition:. Let A and B be sets. The Cartesian product AXB of A and B is the set of ordered pairs (a, b)

    (3) Assume that A and B are countable sets. Prove that the Cartesian product A x B is countable.

    2. Relevant equations

    3. The attempt at a solution

    I know that to prove that something is countable, you need to check if the function is a bijection, which I know how to do. However, I am having a little trouble understanding what the function for this question would be. Would it be:

    f:AxB------>AxB where
  2. jcsd
  3. Sep 22, 2009 #2
    Since each set is countable, they can be put into 1-1 correspondence with the naturals. That is, you can 'label' each element using the naturals. One proof for this exercise uses a diagonal argument - that is you can arrange all the elements into a grid and show correspondence between diagonal entries. This is not very intuitive but it is used often so you can ask your prof or consults a real analysis book for further discussion.
    Another exercise that is useful is to show that the finite product of countable sets is countable. This proof makes use of the fundamental theorem of arithmetic
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook