Représentation monotone

Les chiffres sont naturellement ordonnés, par l'ordre des nombres qu'ils représentent. Le langage de la repésentation est donc également ordonné. En effet, chaque langage dont l'alphabet est ordonné admet l'ordre suivant, appelé parfois ordre généalogique: pour des mots $w$ et $w'$, $w<w'$ si $\vert w\vert<\vert w'\vert$ ou si $\vert w\vert=\vert w'\vert$ et la première lettre par laquelle ils diffèrent est plus petite dans $w$ que dans $w'$.

Ainsi, si l'alphabet comporte deux lettres, $a,b$, et si $a<b$, alors $a^3bab^2<b^2a^3b^5$ car le premier est plus court que le second, et $abab^3<ab^2a^2b$ car la première lettre par laquelle ils diffèrent est $a$ pour le premier et $b$ pour le second.

Proposition 0.1.3   Lorsque le langage $L$ de la numération associée à une suite strictement croissante d'entiers ${\bf U}=\{U_n,\ n\in{\rm I\!R}\}$, avec $U_0=1$, est muni de l'ordre généalogique, la fonction $r_{\bf U}:{\rm I\!N}\to L$ est strictement croissante.

Preuve. Nous allons vérifier que si $w=r_{\bf U}(n)<w'=r_{\bf U}(n')$ alors $n<n'$.

Si $r=\vert w\vert<s=\vert w'\vert$, alors $n<U_r\leq U_{s-1}\leq n'$ puisque les nombres dont la représentation est de longueur $t$ sont compris dans l'intervalle $[U_{t-1},U_t[$.

Supposons ensuite que $w$ et $w'$ soient de même longueur $r$. Les lettres $a, a'$ les plus à gauche de ces mots sont les quotients entiers par défaut respectifs de $n$ et $n'$ par $U_{r-1}$: il existe $b, b'<U_{r-1}$ tels que $n=aU_{r-1}+b$ et $n'=a'U_{r-1}+b'$. On a $a\leq a'$.

Si $a<a'$ alors

$$n=aU_{r-1}+b<(a+1)U_{r-1}\leq a'U_{r-1}\leq a'U_{r-1}+b'=n'.$$

Sinon, $a=a'$ et on peut écrire $w=a0^iu$ et $w'=a'0^ju'$, où $i\geq j$ et où les mots $u$ et $u'$ ne commencent pas par 0(^0.7). Ce sont les représentations respectives de $b$ et $b'$. Ils vérifient $u<u'$. On peut alors conclure, par exemple par récurrence sur $\vert w'\vert$, que $b<b'$ et donc que $n<n'$ (^0.8).$\qed$