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


by student34
Tags: countable, numbers, rational
student34
student34 is offline
#1
Jan29-13, 02:36 AM
P: 250
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.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
CompuChip
CompuChip is offline
#2
Jan29-13, 02:44 AM
Sci Advisor
HW Helper
P: 4,301
The definition of countable means, that you can assign a natural number to each of them.
Well, here's one way to count them:

NemoReally
NemoReally is offline
#3
Jan29-13, 02:47 AM
P: 194
Quote Quote by student34 View Post
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.
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.

Interestingly, you can't do the same with real numbers. Look up Cantor's diagonal method.

student34
student34 is offline
#4
Jan29-13, 03:23 AM
P: 250

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


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

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?
Fredrik
Fredrik is offline
#5
Jan29-13, 03:52 AM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 8,990
Quote Quote by student34 View Post
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?
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.
NemoReally
NemoReally is offline
#6
Jan29-13, 04:04 AM
P: 194
Quote Quote by student34 View Post
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?
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



CompuChip
CompuChip is offline
#7
Jan29-13, 04:34 AM
Sci Advisor
HW Helper
P: 4,301
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.
cragar
cragar is offline
#8
Jan29-13, 06:22 AM
P: 2,453
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.
CompuChip
CompuChip is offline
#9
Jan29-13, 08:01 AM
Sci Advisor
HW Helper
P: 4,301
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.


Register to reply

Related Discussions
Set of all rational sequences countable? Calculus 2
Set of irrational numbers between 9 and 10 are countable Calculus & Beyond Homework 3
Is this correct? (sum of two rational numbers is rational) Precalculus Mathematics Homework 8
Legal proof that set of Rational numbers is countable? Set Theory, Logic, Probability, Statistics 3
Irrational numbers depends on rational numbers existence General Math 0