numeration system

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

$\mathrm{\Sigma }=\{a_1,\mathrm{\dots },a_k\}$, where for $i=1,\mathrm{\dots },k-1$.

$b$ is called the base of numeration system $N$, and the elements $a_1,\mathrm{\dots },a_k$ the digits of $N$. Words over $\mathrm{\Sigma }$ are called numeral words.

Given a numeral word $u=c_1\mathrm{\cdots }{c}_m$ with $c_j\in \mathrm{\Sigma }$, the integer non-negative $n$ is said to be represented by $u$ if

$$n=c_1{b}^{m-1}+\mathrm{\cdots }+c_j{b}^{m-j}+\mathrm{\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,\{0,1,2,3,4,5,6,7,8,9\},d)$$

  where $d(i)=i$ is the identity function.

• Just as common is the binary digital system: $B=(2,\{0,1\},d)$ where $d$ again is the identity function.

• In fact, any digital system is a numeration system $(n,\mathrm{\Sigma },d)$, where $\mathrm{\Sigma }=\{a_0,\mathrm{\dots },a_{n-1}\}$ and $d(a_i)=i$.

• Consider the system $B_1=(2,\{1\},d)$, where $d(1)=1$. Since any word over $\{1\}$ is just a string of $1$’s, $n$ consecutive strings of $1$ represent $1+2+\mathrm{\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,\{[0],[1],\mathrm{\dots },[9],[10],[100],[1000],[10000],[10000000],[10000000000]\},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,\{[1],[2],[4]\},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.

Title	numeration system
Canonical name	NumerationSystem
Date of creation	2013-03-22 18:57:46
Last modified on	2013-03-22 18:57:46
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 11A67
Synonym	numeral system
Synonym	number system
Related topic	Base3
Defines	base
Defines	digit
Defines	complete numeration system
Defines	unambiguous numeration system
Defines	ambiguous numeration system