Hacker News Reader

Comment by neunhoef | Hacker News Reader

Silly solution: The rationals are countable. Just use any bijective mapping of the natural numbers to the rationals and then use the scheme for the natural numbers. (I know, a mathematician's answer! :-) )

View on HN

That would imply the mapping preserved ordering, which doesn't seem possible.

You are of course right. My mistake.

It's not possible, since between any two rationals there exists another: (a+b)/2.

Wait, do the natural numbers and rational numbers have the same ordinality? It seems not because of the whole 'a number in between every 2 rational numbers'. But then what is the ordinality of the rational numbers?

They have the same cardinality, but there is no order-preserving bijection.

The standard argument for showing that they have the same cardinality is to consider the matrix (let's see if I can render this):

    1/1  2/1  3/1  4/1 ...
    1/2  2/2  3/2  4/2 ...
    1/3  2/3  3/3  4/3 ...
    ...

You can traverse each SW-NE diagonal, producing the sequence 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, ...

This will eventually hit every positive rational (several representations, in fact). If you want, you can start with 0 and insert -q when you hit q.

Reply on news.ycombinator.com