Consider the problem of representing a number in computer memory, which is idealized as a sequence of zeros and ones. The binary number system is a well-known solution to this problem — for example, the sequence “01101” represents . But there’s a problem: You don’t expect the entire computer to just be used to represent one number; you expect it to have other things stored afterwards. So how do you tell where the number ends? If the sequence begins does this represent the number or or ?

The solution to this problem most commonly used in practice is to declare in advance a fixed number of bits that will be used to represent the number, usually 32 bits or 64 bits. For example, if we fix a 5-bit representation the always means that the number is and represents other stuff in memory. This works well enough in practice, but it has a problem: The number of bits you set aside for storing the number forces an upper limit on how big the number can be. For example, you cannot store any number bigger than in 64 bits. If the computer ever needs to store a bigger number than can be represented with space set aside then the computer fails.

I’ll introduce some terminology. The condition that a system of representing numbers is unambiguous can be phrased formally by saying the this method is a *prefix-free code*. A prefix-free code consists of a set of *codewords*, which are sequences of bits, such that no codeword is a prefix of another. A continuing stream of bits can be interpreted as a codeword by taking an initial segment that is a codeword, and by prefix-free property at most one such interpretation is possible. Since we want this code to represent numbers we also want a map from the codewords to the natural numbers (by which I mean including zero, naturally)

The fixed-width codes I mentioned earlier are examples of prefix-free codes whose code words map to a finite subset of the natural numbers. The simplest prefix-free code that can represent every natural number is the unary number system: A number is represented by that number of repeating ones followed by a zero. So “0” is 0, “10” is 1, “110” is 2, et cetera.

This system is extremely inefficient: It takes bits to represent the number . In contrast, the simple (non-prefix-free) binary representation takes bits. A more efficient system is what I’ll call the level 1 binary system: A number is represented by a number in unary concatenated by a -bit representation of the number. This takes bits to represent the number . That’s much more efficient than the unary system, but is still a factor of two less efficient than the simple binary system. A more efficient system is the level 2 binary system: First represent a number in unary, then a -bit number , and then the number is represented as a -bit number.

Asymptotically this should be efficient enough for any purpose, but the way it is constructed naturally inspires the generalization to a level binary system for all . The level 3 system shaves off bits, the level 4 system another bits, and so on. After all of these comes the level binary system: A number is given in unary, followed by a representation of a number in the level binary system. Here’s a particularly elegant reformulation of this system: “0” is a codeword representing 0. If is a codeword representing and is a -bit string, then is a codeword representing the number which has as its binary representation. Within this formulation the system has the property that every number has a unique code for it. This trick where the bit-string represents the binary number can also be applied to the level binary systems for finite , which results in a modified system where number has a unique code.

All of the prefix-free codes I described have the following additional property: If we restrict only to codewords that represent a number in the shortest possible way than one codeword is lexicographically less than another codeword if and only if the corresponding number is smaller. It follows that for any bit-string , the set of numbers whose shortest codeword starts with is either an interval or a ray. For example, in the unary system the string of consecutive ones is a prefix for all numbers in the ray of numbers greater or equal to . In the level 1 binary system, the prefix is used to represent any 9-bit number whose first three bits are , i.e., numbers in the range from to . In other words, the prefix gives a scientific-notation-like approximation for the corresponding number as .

Similarly, in the level binary system, if the sequence denotes the number and are bits, then the prefix begins the representation of any number that is represented as in binary scientific notation. What about the prefix ? If the representation of a number begins with this sequence, then the fragment must denote a truncation of a representation of the number of bits of . Then is approximately , and so is approximately . Similarly the prefix represents a number approximately equal to . Every bit-sequence that is a prefix of a valid level codeword takes one of these forms.

In conclusion, truncating the level binary system representation of a number provides information on the approximate value of the number in a manner generalizing scientific notation. Moreover, this information remains efficient and useful as long as the number is no longer than a small tetration. In contrast, plain scientific notation ceases to be useful for numbers larger than an exponentiall whose exponent is too large to be written in full.

The suggestive terms “level ” and “level ” should inspire you to wonder whether there are level systems for larger ordinals . For example, the level system would represent a number using a unary representation of a number , followed by a -bit number , followed by the number represented in the level binary number system. Truncations of such representations could describe the approximate value of a number like truncations of the level system except with bigger ordinals there will be an even larger range that these truncations can usefully describe. Hopefully this can combine the power of ordinal-based function hierarchies for describing large numbers with the precision of scientific notation. Indeed such a system can be defined. I will describe a particularly elegant formulation:

Let be a countable ordinal. Let . Define a *cofinal sequence system* on to be a sequence of functions such that for all . The name for this concept is my own invention; I’m sure this concept has been studied before but I have not bothered to look up the standard terminology. Given such a system define by if is a successor ordinal and if is a limit ordinal. Define a partial order by is can be obtained from by iterating a finite number of times. Then define the cofinal sequence system to be *progressive* if for all , .

Let be a progressive cofinal sequence system, with associated order . A function is said to have *good support* if is finite and linearly ordered by . For example, the Kronecker delta function if and if has good support. For each function with good support I will define an associated prefix-free code.

To define this prefix-free code, first decompose as where is the largest element of and (so that every element of is strictly -less than ). If set . The definition of the prefix-free code associated to depends on the cofinality of :

- If (and so ) the empty string is the only valid codeword and is associated to the number .
- If is a successor ordinal then the codewords are where is a bit and is a codeword for the prefix-free code of with the same associated number.
- If is a limit ordinal then the codewords of are the codewords of , with the same associated numbers.

These codes satisfy the following properties:

- The set of numbers that can be represented in each code is a closed interval.
- Each number is represented by at most one codeword in each code.
- Each code maps the lexicographic ordering of the codewords into the standard order of the corresponding numbers.
- If has good support and is the largest element of then the smallest element that can be represented with the code associated to is one greater than the largest number that can be represented with the code associated to .

These properties can be proven by induction on the largest element of .

Finally define the level prefix-free code to have codewords where is a codeword for . Every number can be represented uniquely by this code, and lexicographically greater codewords map to bigger numbers.

In particular, take . Define a progressive cofinal sequence system on by , . Then the level prefix-free code is exactly identical to the level binary number system I defined earlier.

Reblogged this on Gentzen translated and commented:

Very nice. I like that the ordinal based construction allows for quite some freedom, while still ensuring that every number can be represented uniquely, and that lexicographically greater codewords map to bigger numbers.

Allowing non-binary digits would provide even more freedom. I guess the only thing which would change in the ordinal based construction is that (2n-1+b) would be replaced by (rn-r+1+d), where d is an r-ary digit. And the encoding of would have to be adapted too.

I wonder what motivated you to write this post. Was it just the obvious motivation to construct a connection between ordinals and natural number representations?

Thanks. My inspiration was seeing other discussions of what I called the level binary system. I believe this was in a paper implementing it in binary lambda calculus, but I can’t bother to find it again. I was thinking about nice properties of this representation system and trying to generalize it.