A numeration system is a triple $N=(b,\Sigma,d)$ , where $b>1$ is a positive integer, $\Sigma$ is a non-empty alphabet, and $d$ is a one-to-one function from $\Sigma$ to the set of non-negative integers $\mathbb{N}\cup \lbrace 0\rbrace$ . Order elements of $\Sigma$ so that their values are in increasing order:

$\Sigma=\lbrace a_1,\ldots, a_k\rbrace$ , where $d(a_i)< d(a_{i+1})$ for $i=1,\ldots, k-1$ .

Given a numeral word $u=c_1\cdots c_m$ with $c_j\in \Sigma$ , the integer non-negative $n$ is said to be represented by $u$ if $$n= c_1 b^{m-1} + \cdots + c_j b^{m-j} + \cdots + c_m.$$ An integer $n$ is said to be representable in $N$ if there is a numeral word $u$ representing $n$ .

Examples.

• The most common numeration system is the decimal system: $$D=(10,\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace, d)$$ where $d(i)=i$ is the identity function.
• Just as common is the binary digital system: $B=(2,\lbrace 0,1\rbrace,d)$ where $d$ again is the identity function.
• In fact, any digital system is a numeration system $(n,\Sigma,d)$ , where $\Sigma=\lbrace a_0,\ldots,a_{n-1}\rbrace$ and $d(a_i)=i$ .
• Consider the system $B_1=(2,\lbrace 1\rbrace,d)$ , where $d(1)=1$ . Since any word over $\lbrace 1\rbrace$ is just a string of $1$ 's, $n$ consecutive strings of $1$ represent $1+2+\cdots +2^{n-1} = 2^{n-1}$ . We conclude that the integers representable by $N$ have the form $2^n-1$ for any positive integer $n$ .
• Consider the system $$D_1=(10,\lbrace [0],[1],\ldots,[9],[10],[100],[1000],[10000],[10000000],[10000000000]\rbrace,d)$$ where $d([i])=i$ . It is easy to see that every integer is representable by $D_1$ . However, some integers may be represented by more than one numeral words. For example, $$[1000]=[100][0]=[10][0][0]=[1][0][0][0].$$ The numeration system $D_1$ is used by the Chinese.
• Consider the system $N=(3,\lbrace [1],[2],[4]\rbrace,d)$ where $d([i])=i$ . Then $[2][1][4][1] = 2\times 3^3 + 1\times 3^2 + 4\times 3 + 1 = 184$ . Notice that $0$ can not be represented $N$ . Also, note that $[4]=4=1\times 3+1 = [1][1]$ .

A numeration system $N$ is said to be complete if every non-negative integer has at least one representation in $N$ ; and unambiguous if every non-negative integer has at most one representation in $N$ . $N$ is ambiguous if $N$ is not unambiguous. Every digital system is complete and unambiguous. In the examples above, $D_1$ is complete but ambiguous; $B_1$ is unambiguous but not complete; $N$ is neither complete nor unambiguous.

Remark. Representation non-negative integers by a numeration system can be extended to rational numbers. The corresponding concepts of completeness and ambiguity may be defined similarly.

Bibliography

1

A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).