David Madore's WebLog: Le lemme de Higman expliqué aux enfants

Je commence par présenter le contexte.

On va d'abord parler de mots, et je vais expliquer exactement ce que j'entends par là. Un mot est une succession (finie) de lettres de l'alphabet. Par exemple : abracadabra est un mot (d'une longueur de 11 lettres, mais peu importe, j'ai dit qu'il n'était pas nécessaire de savoir compter). Un mot n'est pas obligé d'avoir un sens en français ou dans une quelconque autre langue : kvtyeohegwnfth est un mot valable. Un mot peut être arbitrairement long : anticonstitutionnellementologiepouettruc est un mot valable. Il peut aussi être arbitrairement court : a est un mot. On va même autoriser le mot, appelé mot vide, qui n'a aucune lettre dedans (de longueur zéro) : il y a juste un petit problème pour l'écrire parce qu'il ne se voit pas, d'où l'intérêt de mettre des guillemets autour pour qu'on le voie quand même : (est le mot vide). Une lettre peut être répétée autant de fois qu'on veut : aaaaaaaaaaaaaa est un mot parfaitement valable (et différent de aaaaaaaaaaaaa).

En revanche, on n'a pas le droit à autre chose que des lettres : pouet42truc n'est pas autorisé. Ou du moins il ne l'est pas si on est convenu à l'avance que l'alphabet est formé des lettres ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’ et ‘z’ à l'exclusion de toute autre : en fait, le lemme de Higman marchera tout aussi bien si je veux ajouter les chiffres dans l'alphabet, ou les caractères accentués, ou les majuscules ; ou si je prends l'alphabet grec, ou russe, ou sanskrit, ou tous les caractères chinois : la seule chose qui importe est que l'alphabet soit fini et décidé à l'avance et qu'on n'y touche plus (et on pourra toujours appeler lettres les choses qu'on a mises dans l'alphabet) ; mais pour fixer les idées dans cette explication, on va dire qu'il s'agit de l'alphabet latin minuscule, c'est-à-dire exactement des — 26 mais peu importe — caractères que je viens d'énumérer.

✻

Ce concept étant (j'espère) clair, on va jouer à un petit jeu (à seul ou à plusieurs) consistant à écrire des mots les uns à la suite des autres.

La seule règle du jeu est la suivante : une fois qu'un mot a été écrit, il n'est plus autorisé d'écrire un mot qui s'obtient en ajoutant des lettres dans le mot en question (au début, à la fin, n'importe où au milieu, ou tout ça à la fois). Par exemple, si le mot truc a été joué, on ne peut plus jouer trucage, mais pas non plus trouc ni structure ni autruche ni tirebouchon (eh oui, dans tirebouchon il y a truc, voyez : tirebouchon) ni introductif (idem : introductif), ni cturtutrcu (cherchez bien, il y a moyen de retrouver truc dans cet ordre en retirant les bonnes lettres : cturtutrcu). Et, bien sûr, on ne peut pas rejouer truc lui-même. Si le mot a a été joué, on ne peut plus jouer aucun mot comportant un ‘a’ n'importe où. (Et si le mot vide a été joué, plus aucun mot n'est jouable et le jeu doit s'arrêter.) • Pour parler de façon plus concise, un mot qui s'obtient à partir d'un autre en ajoutant des lettres s'appellera un sur-mot, et inversement, l'autre (qui s'obtient en retirant des lettres n'importe où) s'appellera un sous-mot : donc truc est un sous-mot de tirebouchon et tirebouchon est un sur-mot de truc (et tout mot contenant la lettre ‘a’ est un sur-mot de a, et tout mot est un sur-mot du mot vide). On convient que tout mot est un sur-mot et un sous-mot de lui-même. La règle du jeu est donc : on ne peut pas jouer un mot dont un sous-mot a déjà été joué, ou encore, jouer un mot « grille » (consomme, interdit, bannit) définitivement tous ses sur-mots. C'est là la seule règle.

Évidemment, si on veut vraiment faire un jeu intéressant à partir de l'histoire, il faudra ajouter des règles décidant qui gagne (par exemple, en disant que celui qui joue le mot vide perd — si on décide qu'il gagne, le jeu n'est vraiment pas bien palpitant ; en fait, même si on décide qu'il perd, il y a une stratégie gagnante très facile). Mais ce n'est pas tellement ça qui va m'intéresser.

Pour que la règle soit claire, voici une petite application bricolée en JavaScript qui doit l'appliquer (on entre des mots en bas, il vérifie qu'ils sont bien des mots sur l'alphabet latin ‘a’–‘z’ et qu'ils n'ont pas un sous-mot déjà joué) :

✻

Tout ceci ayant été expliqué, que dit ce fameux lemme de Higman ? C'est très simple : il affirme que quoi qu'on fasse, le jeu terminera toujours au bout d'un nombre fini de mots (au sens où on ne pourra plus rien jouer). Autrement dit, en principe, quoi que vous tapiez dans le petit gadget JavaScript ci-dessus, en théorie, il arrivera forcément un moment où vous ne pourrez plus rien jouer (auparavant, il arrivera un moment où vous ne pourrez plus rien jouer sauf le mot vide, et une fois celui-ci joué, plus rien n'est possible du tout).

Ou, pour dire les choses autrement : si on prend une liste infinie de mots (sur l'alphabet latin ‘a’–‘z’), quelle que soit la manière dont ils sont générés, il y a toujours un mot dans la liste qui a un sous-mot en amont dans la liste, ou de façon équivalente, il y a toujours un mot qui a un sur-mot en aval (rendant la liste illégale dans le jeu que j'ai exposé). C'est généralement sous cette forme que le lemme est énoncé, mais je trouve plus clair de décrire le petit jeu qui interdit de jouer un mot qui a un sous-mot en amont, et d'énoncer le résultat sous la forme le jeu s'arrête forcément.

✻

C'est assez théorique, bien sûr. Si on expérimente avec l'application ci-dessus, on se rend compte qu'il est très facile de jouer longtemps… très longtemps. Et on n'a pas vraiment l'impression que ça doive s'arrêter. Il faut dire que déjà avec les mots de trois lettres on a beaucoup de possibilités (17 576 mais peu importe), donc rien qu'en jouant tous les mots de trois lettres un par un (dans l'ordre alphabétique, par exemple : aaa puis aab, puis aac et ainsi de suite jusqu'à zzz), on peut tenir très longtemps — car un mot de trois lettres ne peut jamais avoir un autre mot de trois lettres comme sous-mot si ce n'est le même. Et la même chose vaut avec quatre lettres, donc en jouant les mots de quatre lettres à la place de trois, on peut tenir encore plus longtemps (456 976 pour être exact, mais peu importe ; par contre, pour que les choses soient claires, si on a déjà joué tous les mots de trois lettres, il est trop tard pour jouer ceux de quatre, ils ont tous un sous-mot de trois lettres déjà joué, donc sont eux-mêmes injouables).

C'est l'occasion de souligner la différence en mathématiques entre forcément fini et borné : on ne peut pas dire a priori, combien de temps le jeu durera (ce serait ça qu'on appellerait borné : si on pouvait mettre une borne a priori sur le nombre de mots). Si on joue le mot vide au premier coup, le jeu s'arrête immédiatement. Si on se met à énumérer tous les mots de mille lettres systématiquement, il durera très longtemps. Le lemme de Higman dit juste que quoi qu'on fasse, même si on essaye d'augmenter la longueur des mots, on finira par tomber à court de mots à jouer — il ne dit rien sur le temps que ça durera.

J'aurais d'autres commentaires à faire sur le lemme de Higman, et sur la question de savoir s'il est intuitif ou non, mais je vais garder ça pour une autre fois.

✻

Maintenant je vais essayer de présenter une démonstration du lemme de Higman qui soit compréhensible sans aucune connaissance mathématique particulière. Comme je le disais initialement, je vais aussi rédiger la démonstration sans utiliser aucune notation mathématique, uniquement en français (je la re-rédigerai juste après avec des notations mathématiques, pour permettre de comparer).

Mon but est de montrer qu'il n'y a pas moyen de produire une suite (=liste) infinie de mots qui respecte la règle du jeu que j'ai énoncée plus haut, autrement dit, dans laquelle aucun mot ne soit un sous-mot d'un mot ultérieur. Pour dire les choses de façon plus concise, j'appellerai miraculeuse une telle suite de mots : une suite miraculeuse est donc une partie infinie (=qui ne termine jamais) du jeu expliqué ci-dessus. L'objectif est de montrer qu'il n'existe pas de suite miraculeuse. Pour ça, je vais utiliser une technique utilisée raisonnement par l'absurde dans laquelle je suppose que mon objet existe (ou plus généralement, que la conclusion que je veux atteindre est fausse), j'en tire des conclusions jusqu'à arriver à quelque chose de manifestement impossible, et j'en conclus que puisque l'existence de mon objet est absurde, c'est qu'il n'existe pas.

Supposons donc « par l'absurde » qu'il existe une suite miraculeuse. Maintenant, pour arriver à une contradiction, mon plan va être le suivant : je vais construire une suite miraculeuse « minimale » (et expliquer ce que j'entends par minimale), puis je vais montrer que je peux trouver une autre suite miraculeuse qui contredit sa minimalité parce qu'elle est en un certain sens plus petite (là aussi, il faut expliquer ce que ça veut dire).

Puisque j'ai fait l'hypothèse (dont je cherche à prouver l'absurdité…) qu'il existe une suite miraculeuse, il y a certains mots qui peuvent apparaître comme premier mot d'une suite miraculeuse, c'est-à-dire qu'en jouant un tel mot en premier on peut continuer à jouer indéfiniment ; il y en a aussi d'autres qui ne peuvent pas, c'est-à-dire qu'en jouant un tel mot en premier le jeu sera forcément bloqué : de tels mots existent, parce que le mot vide en est un (si on joue le mot vide, on est immédiatement bloqué, donc il ne peut apparaître nulle part dans une suite miraculeuse, et en particulier, pas en premier).

Considérons un mot qui peut commencer (=apparaître en premier dans) une suite miraculeuse : essayons de lui retirer sa première lettre : soit il peut encore commencer une suite miraculeuse (éventuellement complètement différente), soit non ; si oui, on retire encore sa première lettre ; et on continue à à retirer la première lettre du mot jusqu'à ce qu'en se faisant on arrive à un mot qui ne commence aucune suite miraculeuse (comme je l'ai dit, cela va forcément se produire, parce que le mot vide ne commence pas une suite miraculeuse). Arrêtons-nous juste avant : on a ainsi fabriqué un mot qui commence une suite miraculeuse, mais qui est tel que si on retire sa première lettre ce ne soit plus le cas. (Par exemple, peut-être qu'il existe une suite miraculeuse qui commence par abracadabra, et encore une, peut-être complètement différente mais peu importe, qui commence par bracadabra et encore une qui commence par racadabra, par acadabra, par cadabra mais pas par adabra : alors on s'arrêtera au mot cadabra, qui commence une suite miraculeuse mais tel que si on retire sa première lettre ce ne soit plus le cas ; c'est-à-dire, si on joue cadabra en premier il est possible de jouer indéfiniment, mais si on joue adabra en premier ce n'est pas possible.) Écrivons le mot qu'on a obtenu (dans mon exemple, cadabra), et on ne va plus y toucher : ce sera le premier mot de la « suite miraculeuse minimale » qu'on essaie de construire progressivement.

Maintenant, on va faire pareil en cherchant les suites miraculeuses qui commencent par le mot qu'on vient d'écrire, et en considérant le mot suivant (i.e., juste après dans la suite). On sait qu'il y a une suite miraculeuse qui commence par le mot qu'on a écrit (dans mon exemple, c'était cadabra) : il est donc possible de mettre un second mot après qui permette de jouer indéfiniment, i.e., de former une suite miraculeuse (peut-être izebulon). On va de nouveau retirer sa première lettre jusqu'à ce que ce ne soit plus le cas, et s'arrêter juste avant (donc par exemple, peut-être qu'il y a façon de jouer indéfiniment après les deux mots cadabra, izebulon et aussi après cadabra, zebulon, mais plus après cadabra, ebulon : dans ce cas, on s'arrête à zebulon). Écrivons le mot qu'on a obtenu (dans mon exemple, zebulon) : on a maintenant deux mots, on sait qu'en jouant ces deux mots on peut jouer indéfiniment, mais si on retire la première lettre du premier il n'y a pas moyen de jouer indéfiniment en commençant comme ça, et pareil, après avoir joué le premier, si on retire la première lettre du deuxième. (Dans mon exemple, il y a une suite miraculeuse commençant par cadabra, zebulon, mais aucune qui commence par cadabra, ebulon, ni par adabra.)

On continue le procédé de la même manière : quand on a écrit un certain nombre de mots, qui à chaque fois peuvent commencer une suite miraculeuse, on cherche un mot qu'on peut mettre après eux et qui permette de jouer indéfiniment (i.e., après les précédents, il commence une suite miraculeuse), et on retire sa première lettre jusqu'à ce que ça ne commence plus une suite miraculeuse, et on s'arrête juste avant. On obtient ainsi une suite infinie de mots.

La suite que j'ai écrite est elle-même miraculeuse : en effet, si on peut la compléter à partir de n'importe quel point en une suite miraculeuse, c'est-à-dire si le jeu n'est jamais perdu, c'est bien que la suite elle-même est miraculeuse, c'est-à-dire que la règle du jeu n'est jamais enfreinte. En revanche, si on jouait les premiers mots de la suite puis le un mot qui vient juste après privé de sa première lettre, on se retrouverait forcément bloqué après. C'est cette suite que j'appelle une suite miraculeuse minimale : une suite miraculeuse telle qu'en retirant la première lettre d'un quelconque de ses mots, je ne puisse pas compléter à partir de là pour obtenir une suite miraculeuse.

À ce stade-là de la démonstration, j'ai donc montré l'existence de cette suite miraculeuse minimale à partir de la seule existence d'une suite miraculeuse, je n'ai pas eu besoin d'autre hypothèse (s'il existe une suite miraculeuse, il en existe une minimale, et j'ai expliqué comment la fabriquer ; on ne peut pas dire que j'aie donné un « algorithme » pour obtenir ma suite miraculeuse minimale, parce que j'ai dû faire certaines choses qui sont algorithmiquement impossibles, mais j'ai bien montré son existence).

Maintenant on va fabriquer une nouvelle suite à partir de la suite miraculeuse minimale. (Je l'appellerai toujours la nouvelle suite dans ce qui vient.)

Pour construire cette nouvelle suite, regardons la première lettre de chacun des mots de ma suite miraculeuse minimale. Comme il y a une infinité de mots dans la suite, et qu'il n'y a qu'un nombre fini de lettres dans l'alphabet, il y en a forcément (au moins !) une qui revient infiniment souvent comme première lettre. (En effet, si chacune des lettres n'apparaissait qu'un nombre fini de fois comme première lettre, ça ne ferait qu'un nombre fini de mots au total, or nos suites sont infinies.) Choisissons une lettre qui revient infiniment souvent comme première lettre des mots de ma suite miraculeuse minimale, et appelons cette lettre lettre-clé.

Maintenant, on va considérer une nouvelle suite formée à partir de la suite miraculeuse minimale : cette nouvelle suite est formée de (a) tous les mots qui viennent dans la suite miraculeuse minimale (strictement) avant le premier mot commençant par la lettre-clé, et (b) tous les mots de la suite miraculeuse minimale commençant par la lettre-clé, mais auxquels on a retiré la première lettre en question. (Par exemple, si ma suite miraculeuse minimale était quelque chose comme cadabra, zebulon, mumble, zork, corge, zygmund, zazie… et qu'il y a une infinité de mots commençant par ‘z’ et que j'ai décidé de la prendre pour lettre-clé, je vais construire la suite cadabra, ebulon, ork, ygmund, azie… : j'ai gardé (a) tous les mots venant avant le premier mot commençant par ‘z’, et (b) à partir de lui, seulement les mots commençant par ‘z’ moins leur lettre initiale.)

Maintenant, pour arriver à la contradiction, je vais expliquer deux choses : primo, ma nouvelle suite est aussi miraculeuse ; et secundo, elle ne peut pas être miraculeuse. Bref, une contradiction.

Pourquoi ma nouvelle suite est-elle miraculeuse ? Imaginons au contraire qu'un mot de la nouvelle suite soit un sous-mot d'un mot ultérieur. Alors (vais-je expliquer) c'est forcément aussi le cas dans la suite suite miraculeuse minimale : en effet, on obtient des mots de la suite suite miraculeuse minimale en ajoutant peut-être la lettre-clé au début des mots correspondants de la nouvelle suite ; peut-être, c'est-à-dire, si elle avait été supprimée, c'est-à-dire, si on était dans le cas (b) ci-dessus. Mais des deux mots en question, soit ils sont tous les deux dans le cas (a) (i.e., ce sont des mots de la suite miraculeuse minimale qui ne commençaient pas par la lettre-clé), auquel cas il n'y a rien à rajouter et le premier est bien un sous-mot du second ; soit ils sont tous les deux dans le cas (b) (i.e., ils commençaient par la lettre-clé, elle a été retirée), auquel cas en remettant la lettre-clé au début, le premier est bien encore un sous-mot du second ; soit le premier est dans le cas (a) et le second dans le cas (b), auquel cas le premier est bien un sous-mot du second a fortiori quand on remet la lettre-clé au début du second ; et ce n'est pas possible que le premier soit dans le cas (b) et le second dans le cas (a) car le premier doit venir avant le second. Bref, dans tous les cas, si un mot de la nouvelle suite était sous-mot d'un mot ultérieur, ce serait encore le cas dans la suite miraculeuse minimale : or on sait que ce n'est pas le cas pour celle-ci (précisément parce qu'elle est miraculeuse), donc ce n'est pas non plus le cas pour celle-là, qui est donc elle-même miraculeuse.

Mais inversement, la nouvelle suite ne peut pas être miraculeuse : ceci résulte de la minimalité de la suite miraculeuse minimale ; en effet, considérons le premier mot de la suite miraculeuse minimale qui commence par la lettre-clé : ce mot avait justement été choisi de sorte qu'en retirant la première lettre il n'y ait aucune suite miraculeuse qui commence de la sorte ; mais la nouvelle suite est justement une suite qui commence de la sorte. Donc elle n'est pas miraculeuse.

Donc contradiction.

Donc il n'y a pas de suite miraculeuse du tout.

Et on a donc prouvé le lemme de Higman !

✻

Voici comment on dirait cette démonstration en langage plus mathématique, et surtout avec les notations qui vont avec, donc c'est un peu moins verbeux, mais sans doute plus difficile à lire pour un non-mathématicien :

Notons w≼w′ pour w est un sous-mot de w′. On veut montrer par l'absurde que pour toute suite (infinie) w_i de mots, il existe i₁≤i₂ tels que w_i₁≼w_i₂ : appelons miraculeuse une suite qui vérifie le contraire, et supposons par l'absurde qu'il en existe une.

Soit w₀ un mot qui commence une suite miraculeuse mais tel qu'en retirant la première lettre ce ne soit plus le cas (un tel mot w₀ existe bien, comme on le voit en retirant successivement les premières lettres jusqu'à tomber sur le mot vide). Et par récurrence sur i, si les w_j pour j<i sont déjà définis, soit w_i tel que les w_j pour j≤i commencent une suite miraculeuse mais que ce ne soit plus le cas en retirant la première lettre de w_i (un tel w_i existe pour la même raison que w₀). On définit ainsi une suite w_i, qui est manifestement elle-même miraculeuse (puisque quel que soit i, les w_j pour j≤i commencent une suite miraculeuse : autrement dit, quel que soit i il n'existe pas i₁≤i₂≤i tels que w_i₁≼w_i₂) ; de plus, elle est telle qu'en retirant la première lettre de w_i sans changer les précédents, il n'y ait pas moyen de choisir les termes >i pour former une suite miraculeuse à partir de là.

Soit x une lettre qui commence un nombre infini des w_i (une telle lettre existe car l'alphabet est fini et que l'ensemble d'indices est infini), disons que w_ki soit le i-ième terme de la suite w_j commençant par x. Notamment, k₀ est le plus petit indice tel que w_k commence par x. Définissons v_i par v_i=w_i si i<k₀, et sinon, v_i est obtenu en retirant le x initial du terme w_j pour j=k_(i−k₀) (c'est-à-dire du (i−k₀)-ième terme de la suite w_j commençant par x), bref, w_j=xv_i pour j=k_(i−k₀).

Montrons que la suite (v_i) est miraculeuse. S'il existe i₁≤i₂ tels que v_i₁≼v_i₂, alors soit i₁≤i₂<k₀, auquel cas w_i₁=v_i₁ et w_i₂=v_i₂ d'où w_i₁≼w_i₂, ce qui n'est pas ; soit k₀≤i₁≤i₂, auquel cas w_j₁=xv_i₁ et w_j₂=xv_i₂ (pour j₁=k_{(i₁−k₀)} et j₂=k_{(i₂−k₀)} qui vérifient j₁≤j₂) d'où w_j₁≼w_j₂, ce qui n'est pas ; soit i₁<k₀≤i₂, auquel cas w_i₁=v_i₁ et w_j₂=xv_i₂ (pour j₂=k_{(i₂−k₀)} qui vérifie i₁≤j₂) d'où w_i₁≼w_j₂, ce qui n'est pas. La suite est donc bien miraculeuse.

Mais ceci contredit la minimalité de (w_i) : en effet, w_k₀ était censé être choisi tel qu'en en retirant la première lettre (ce qui donne v_k₀), aucune suite miraculeuse ne puisse commencer ainsi, i.e., aucune suite miraculeuse ne peut commencer par les v_i pour i≤k₀.

Là j'ai laissé tous les détails. Dans un vrai article de maths, on en omettrait un certain nombre, et ce serait encore environ deux fois plus court. Généralement, la démonstration est plutôt écrite en prenant w_i de longueur minimale plutôt que minimale pour l'opération de retirer la première lettre : c'est plus court à écrire, mais c'est inutilement fort, et peut-être plus difficile à expliquer au non-mathématicien, donc j'ai préféré utiliser la construction que j'ai faite. (Par ailleurs, la terminologie standard dans cette démonstration est plutôt de parler de mauvaises séquences pour celles que j'ai qualifiées de merveilleuses, mais mon esprit se rebelle contre cette terminologie : ce qui n'existe pas, c'est justement le merveilleux, pas le mauvais.)

✻

Je voudrais encore essayer d'expliquer une ou deux conséquences du lemme de Higman qui aident peut-être à voir en quoi il est intéressant. Pour ça, il faut que je définisse encore un concept, celui de langage : mathématiquement, un langage est juste un ensemble de mots, mais le terme d'ensemble n'étant pas forcément le plus intuitif, je devrais peut-être plutôt le présenter comme une propriété qu'un mot peut ou ne pas avoir ; par exemple, être un mot français est une propriété, qu'on peut identifier au langage [ensemble des mots] français ; l'ensemble des mots se terminant par un ‘z’ est aussi un langage, qu'on peut identifier à la propriété se terminer par un ‘z’ ; et ainsi de suite. (Aux deux extrêmes, il y a aussi l'ensemble de tous les mots, ou propriété « trivialement vraie », c'est-à-dire toujours vérifiée, et l'ensemble vide, ou propriété « trivialement fausse », c'est-à-dire jamais vérifiée.)

Donné un langage, on peut construire un nouveau langage qu'on appelle langage des sur-mots du langage de départ, et qui est formé, tout à fait logiquement, des mots qui sont un sur-mot d'un mot du premier langage (i.e., qui ont un sous-mot dans le langage en question). Par exemple, le langage des sur-mots du français est l'ensemble des mots tels qu'en retirant certaines lettres on obtienne un mot français (utfnrcraripbjbubmne en est un, par exemple parce qu'il contient le mot français tribun ou plus simplement parce qu'il contient le mot a, lui aussi français). Si on réfléchit un peu, on peut se convaincre qu'en refaisant cette opération (i.e., si on part d'un premier langage, qu'on considère son langage des sur-mots, et qu'on considère le langage des sur-mots de ce langage-là), la deuxième fois ne sert à rien : le langage des sur-mots du langage des sur-mots est juste le langage des sur-mots ; un langage de cette sorte est appelé clos par sur-mots, c'est-à-dire qu'il s'agit d'une propriété des mots qui, quand elle est vérifiée par un mot, est vérifiée par tous ses sur-mots.

Une conséquence du lemme de Higman est le fait suivant : tout langage clos par sur-mots est le langage des sur-mots d'un nombre fini de mots. Autrement dit, si je prends n'importe quel ensemble de mots (=langage) et que je considère tous leurs sur-mots (=langage des sur-mots), en fait je pouvais obtenir le même résultat en partant d'un ensemble fini de mots. Pourquoi ? Parce que je peux lister tous les mots de mon langage de départ (dans un ordre quelconque), et retirer de cette liste tous ceux qui sont un sur-mot d'un mot antérieur, c'est-à-dire exactement ceux qui étaient interdits dans le jeu par lequel j'ai expliqué le lemme de Higman ; en ce faisant, je ne change pas le langage des sur-mots (puisque si un mot est un sur-mot d'un mot de la liste qui est lui-même un sur-mot d'un mot antérieur, le premier mot est directement un sur-mot du mot antérieur de la liste), mais je ne garde qu'un nombre fini de mots puisque le lemme de Higman me dit que toute suite vérifiant la règle du jeu est forcément finie.

Pour ceux qui ont manipulé des outils informatiques comme grep, cela veut dire, aussi, que tout langage clos par sur-mots est rationnel (=définissable par une expression régulière, ou de façon équivalente, par un automate fini), ou ce qui revient au même, qu'en partant de n'importe quel langage et en prenant le langage de ses sur-mots, on obtient toujours un langage rationnel. (Pour faire le lien avec ce que j'ai dit juste avant, si on a un nombre fini de mots, disons corge, grault et flarp, le langage de leurs sur-mots peut se définir par l'expression régulière .*c.*o.*r.*g.*e.*|.*g.*r.*a.*u.*l.*t.*|.*f.*l.*a.*r.*p.* donc il est bien rationnel.)

Ce qui est amusant, c'est qu'à peu près la même chose marche aussi pour les sous-mots. Je prends la peine de l'écrire, parce que j'ai dû me gratter la tête pour retrouver ça (j'étais tout embrouillé par le fait que des gens écrivissent tout langage clos par sur-mots est rationnel et d'autres tout langage clos par sous-mots est rationnel — il s'avère que les deux sont vrais) :

On appelle langage des sous-mots d'un langage celui qui est formé, tout à fait logiquement, des mots qui sont un sous-mot d'un mot du langage donné (i.e., qui ont un sur-mot dans le langage donné). Par exemple, le langage des sous-mots du français est l'ensemble des mots tels qu'en ajoutant certaines lettres on obtienne un mot français (rbn en est un, par exemple parce qu'il est un sous-mot du mot tribun). De même que pour le langage des sur-mots, on peut se convaincre qu'en refaisant cette opération (i.e., si on part d'un premier langage, qu'on considère son langage des sous-mots, et qu'on considère le langage des sous-mots de ce langage-là), la deuxième fois ne sert à rien : le langage des sous-mots du langage des sous-mots est juste le langage des sous-mots ; un langage de cette sorte est appelé clos par sous-mots, c'est-à-dire que c'est une propriété des mots qui, quand elle est vérifiée par un mot, est vérifiée par tous ses sous-mots.

Par ailleurs, le complémentaire d'un langage est la propriété contraire : c'est-à-dire, les mots qui n'appartiennent pas au langage donné. (Ainsi, le complémentaire du [langage des mots] français est l'ensemble des mots qui ne sont pas français.) Fait : le complémentaire d'un langage clos par sous-mots est clos par sur-mots (pourquoi ? parce qu'un sous-mot d'un mot du complémentaire ne peut pas être dans le langage de départ, sinon le mot de départ, qui en est un sur-mot, y serait aussi, or justement il est dans le complémentaire).

Du coup, n'importe quel langage clos par sous-mots a un complémentaire qui est l'ensemble des sur-mots d'un nombre fini de mots : cela signifie que pour n'importe quel langage clos par sous-mots, il existe un nombre fini de mots tels que les mots du langage initial sont exactement ceux qui ne sont pas des sur-mots d'aucun des mots de cette liste finie. Ce n'est peut-être pas très parlant dit comme ça, mais, de nouveau, si on sait ce qu'est un langage rationnel, cela signifie que tout langage clos par sous-mots est rationnel : et ça, c'est vraiment loin d'être évident.

✻

Je pourrais en dire encore énormément sur le lemme de Higman, sur ses généralisations (par exemple au cas où l'alphabet n'est plus fini mais bel-ordonné ; ou aux mots parenthésés, ce qui revient plus ou moins au théorème de Kruskal sur les arbres ; ou encore au monumental théorème de Robertson-Seymour), mais je vais m'arrêter là, au moins pour le moment.

Mais s'il y a des gens qui veulent réfléchir à des problèmes de ce genre, en voici un dont j'aimerais bien avoir la réponse.