Bien fondé, ou pas

1. $(\mathbb{N},\le )$ : bien fondé. C'est le cas de base, et c'est celui qui justifiait tous les variants du chapitre chap:algo-prog : une suite d'entiers positifs strictement décroissante perd au moins $1$ à chaque pas et ne peut donc dépasser $x_0$ termes.

2. $(\mathbb{Z},\le )$ : non. Contre-exemple : $0>-1>-2>\cdots$. C'est la raison pour laquelle un variant doit être positif, et non seulement décroissant — une exigence qu'on prend souvent pour une précaution de rédaction, et qui est le cœur du théorème.

3. $({\mathbb{Q}}_{+},\le )$ : non, alors même que tous les éléments sont positifs. Suite mesurée :

$$1>\frac{1}{2}>\frac{1}{4}>\frac{1}{8}>\frac{1}{16}>\frac{1}{32}>\cdots$$

strictement décroissante et infinie. C'est le contre-exemple le plus instructif du lot : la positivité ne suffit pas, il faut que les valeurs ne puissent pas s'accumuler. Un « variant » à valeurs rationnelles ne prouve donc rien.

4. $({\mathbb{N}}^{\ast },\mid )$ : bien fondé. Si $a\mid b$ et $a\ne b$ avec $a,b\ge 1$, alors $a<b$ comme entiers. Toute suite strictement décroissante pour la divisibilité l'est donc pour $\le$ sur $\mathbb{N}$, et ces suites sont finies. Le minimum est $1$.

5. L'ordre lexicographique sur les mots : NON, et c'est le piège.

$$b\succ ab\succ aab\succ aaab\succ aaaab\succ \cdots$$

Vérification mesurée sur les douze premiers termes, et la construction est claire : le mot $a^{k}b$ et le mot $a^{k+1}b$ coïncident sur les $k$ premières lettres, puis le premier porte $b$ là où le second porte $a$ — donc $a^{k+1}b\prec a^{k}b$. La suite se prolonge indéfiniment.

Où est le piège. L'ordre lexicographique sur ${\mathbb{N}}^k$ à $k$ fixé est bien fondé, et le cours s'en sert pour Ackermann. Sur les mots, la longueur n'est pas bornée, et c'est cela qui casse : on peut insérer indéfiniment de nouveaux termes entre deux mots.

La réparation, mesurée elle aussi. L'ordre « longueur d'abord, puis lexicographique » — l'ordre militaire — est bien fondé : une suite décroissante y décroît en longueur, ou reste à longueur constante, et les mots d'une longueur donnée sont en nombre fini. Sur la même suite $b,ab,aab,\dots$, cet ordre-là est croissant, vérification faite. Le même ensemble, deux ordres, deux conclusions opposées : « bien fondé » est une propriété de l'ordre, jamais de l'ensemble.