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

Legal proof that set of Rational numbers is countable?

  1. Mar 24, 2010 #1
    Hello,

    Just wondering if this is a correct way to say the set of RATIONAL numbers is countable:

    Rationals (Q) is countable , because for every Q = p/q , such that p & q are positive INTS (Z)

    and since the set of positive INTs (Z) is countable ( a 1:1 correspondence) Q is countable because it is a SUBSET of a countable set.....

    it can be listed by listing those Q's with
    denominator q = 1 in the first row of a listing matrix
    denominator q =2 in the second row and so on...
    with p1 = 1 , p2 =2, etc... for each row...

    will eventually cover ALL rationals


    REMARK:
    Ive seen the little N x N matrix and path listing for each rational...but I would like to know...
    How would you show this as a mapped 1:1 function?? such that A ---> B showing f(a) = some b??


    Thanks for any input...
     
    Last edited: Mar 24, 2010
  2. jcsd
  3. Mar 24, 2010 #2
    You might be asking for an onto function. 1:1 means if f(a)=f(b), then a = b.
     
  4. Mar 25, 2010 #3
    Thanks for the reply...
    However, when I said
    I shouldve said:
    A 1:1 correspondence function or a bijective function...
     
  5. Mar 25, 2010 #4

    mathman

    User Avatar
    Science Advisor
    Gold Member

    The standard proof (Cantor) is as follows: Let a(i,j)=i/j. Then the order to show countable is a(1,1), a(2,1), a(1,2), a(3,1), [a(2,2)], a(1,3), a(4,1), a(3,2), a(2,3), a(1,4),.... skipping terms in [] since these are not in lowest terms.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook