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

How can the set of the rational numbers be countable if there is no

  1. Jan 29, 2013 #1
    rational number to count the next rational number from any rational number?

    We can count the next natural number, but we can't count the next rational numer.
     
  2. jcsd
  3. Jan 29, 2013 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    The definition of countable means, that you can assign a natural number to each of them.
    Well, here's one way to count them:

    fraction_grid2.gif
     
  4. Jan 29, 2013 #3
    Starting with, say, 1/1, write down all the rational numbers in whichever order you like. Label the starting number as Rational Number 1. As you generate the next rational number, write it down (as a / b) and then write the next natural number down next to it. Continue until you run out of either rational numbers or natural numbers ...

    Actually, you won't run out of either. They are in a one-to-one correspondence. The difference from the normal way of thinking about finite counting lies in the fact that you will never run out of natural numbers. This concept underlies many mathematical ideas but it may hurt your brain until you get the idea. :smile:

    Interestingly, you can't do the same with real numbers. Look up Cantor's diagonal method.
     
  5. Jan 29, 2013 #4
    If we really can assign a natural number to each of them, can you assign a natural number to the very next rational number from the number 1?
     
  6. Jan 29, 2013 #5

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes. This is what CompuChip's picture is showing. The first 11 positive rational numbers (when they are ordered as in that picture) are

    1. 1
    2. 1/2
    3. 2
    4. 3
    5. 1/3 (We're skipping 2/2, since it's equal to 1, which is already on the list).
    6. 1/4
    7. 2/3
    8. 3/2
    9. 4
    10. 5
    11. 1/5 (We're skipping 4/2, 3/3 and 2/4, since they are equal to numbers that are already on the list).

    The only problem with that picture is that it only deals with positive rational numbers. You can however easily imagine a similar picture that includes the negative ones.
     
  7. Jan 29, 2013 #6
    In principle, yes. You just keep extending the table of rational numbers, labelling each one with a natural number, until you reach the "very next" rational number from 1. The trick lies in recognizing that (physical limitations aside), there is always another rational number between the "very next" rational number and 1, so you'll never actually do it, but if you keep trying you will always be able to assign a natural number to each one.

    eg, halving the difference ...

    label '1' as number 1 in your list. Start with 3/2 (1+1/2) and label it '2'. Then the "next" rational number (number '3') will be 5/4 ((1+3/2)/2), the next 9/8 (number '4') and so on. You can keep dividing by 2 and incrementing the label indefinitely - you will never run out of natural numbers or rational numbers that keep getting closer to 1

    https://www.physicsforums.com/attachment.php?attachmentid=55160&stc=1&d=1359454296

    https://www.physicsforums.com/attachment.php?attachmentid=55159&stc=1&d=1359453948
     
    Last edited: Jan 29, 2013
  8. Jan 29, 2013 #7

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Of course, if you want to be very precise: there are duplicates in the tabulation of the rationals (for example, it contains 1/2, 2/4, 3/6, 34672/69344, etc). So technically you are not really making a one-to-one mapping, but you are overcounting.

    In other words, you are proving that the cardinality of the rationals is at most the same as that of the natural numbers. However, since we clearly also have at least as many rationals as natural numbers (the natural numbers are precisely the first column of the grid), you can convince yourself that the cardinalities are equal.
     
  9. Jan 29, 2013 #8
    another way to map the rationals to the naturals is take the
    positive rationals of the form [itex] \frac{p}{q} [/itex] and map them to
    [itex] 2^p3^q [/itex] and then map the negative rationals to
    [itex] 5^{|-p|}7^{|-q|}[/itex] and then map zero to some other prime.
    In fact we are mapping all the rationals to a proper subset of the naturals.
     
  10. Jan 29, 2013 #9

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I also wanted to get back to your remark about "the next" rational number from 1... note that the rationals are dense in the real numbers. That implies that there is a rational number between any two given rationals, and therefore it is not possible to write them down in "ascending" order (i.e. write down a sequence an such that every rational is in the sequence and 0 = a0 < a1 < a2 < ...).

    This may be flaw in your way of picturing the rationals that makes their countability, perhaps, a bit counter-intuitive.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How can the set of the rational numbers be countable if there is no
  1. Countable sets (Replies: 12)

  2. Countable Sets (Replies: 9)

Loading...