1 Answer | Add Yours
The rationals are denumerable. See the first link for an explanation of how to set up a one-to-one correspondence between the natural numbers and the rationals.
The idea is to list the rationals in such a way that you're guaranteed to get every one. If you first list all the rationals whose numerator and denominator add to 1, then the rationals whose numerator and denominator add to 2 (I'll skip ones whose numerator is zero because it will already be listed), and so on, you get the following list:
0/1, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, ...
The list is just a one dimensional version of the two dimensional array in the link. If you can list the numbers in a set, then it's denumerable.
Another, similar but more general, proof would use the fact that if `A` is denumerable, then so is the Cartesian Product `AxxA` . Since `NN` is denumerable by definition, then so is `NNxxNN` .The rationals can be idenitified with a subset of `NNxxNN` and any subset of a denumerable set is denumerable.
We’ve answered 319,199 questions. We can answer yours, too.Ask a question