Hacker News Reader

Comment by Mjark | Hacker News Reader

This looks like a similar problem to providing a lexicographic binary encoding for the integers, and the technique given here reminds me of Exp-Golomb encoding.

A more fun problem is extending this scheme to support rational numbers. http://www.imada.sdu.dk/~kornerup/papers/lcf.ps.gz gives a neat scheme using continued fractions. (I've had a go at using it to implement a sort order preserving encoding that works for all the rationals at https://github.com/NegativeMjark/lexical-binary )

View on HN

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! :-) )

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