4 ms·
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.
by Mjark 9y ago
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 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 https://github.com/NegativeMjark/lexical-binary )
- neunhoef 9y agoSilly 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! :-) )
- Veedrac 9y agoThat would imply the mapping preserved ordering, which doesn't seem possible.
- neunhoef 9y agoYou are of course right. My mistake.
- bmm6o 9y agoIt's not possible, since between any two rationals there exists another: (a+b)/2.
- deleted 9y ago[deleted]
- rocqua 9y agoWait, 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?
- Veedrac 9y agoThey have the same cardinality, but there is no order-preserving bijection.
- bmm6o 9y agoThe 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.