Representing a finite set as a real number

67 Views Asked by At

Given a finite set of integers, is it possible to encode them as a real number?

I have come up with a way of doing this, which I think produces a real number which can be decoded properly (decodes back to the original set).

Here is a non-formal description of the algorithm:

  1. *Find the binary representation of every number in the set (for negative numbers use two's complement)
  2. Let $k$ be the maximum number of bits required to represent a number from the set
  3. For every number in the set which has less than $k$ bits in the representation add leading zeros
    so the total number of bits equals $k$
  4. Concatenate all binary representations into one single number - this will be the fractional part
    of the real number representation
  5. The integer part of the real number representation is the number $k$ also coded in base 2

So the final real number will be: $k.(a_1 ^\frown a_2 ^\frown a_3 ^\frown...^\frown a_n )$ ("$.$" marks the decimal point and "$^\frown$" the concatenation operation)
* - There is nothing special about base 2, this could be done in any base, I chose base 2 because complement representation is commonly used for base two and is thus natural.
I should note that this does not produce the shortest possible representation, this could probably be obtained by using Huffman coding. I am not interested in minimizing length just in whether this algorithm produces a unique coding, and is it formally correct - can we claim this for any finite set of integers.

Also I think it might be possible to encode this as an integer (without using the decimal point "hack") by introducing "escape" and "end" integers.