De l’unicité du graphe de Rado et des nombres univers

Fermeture

Dans l’article Un graphe universel et singulier de la rubrique « Logique et calcul » du numéro 493 de Pour la science (), Jean-Paul Delahaye présente le graphe de Rado, un graphe infini satisfaisant une propriété particulière appelée « propriété d’extension ». Il introduit cet objet à l’aide de la notion apparemment plus simple des nombres univers, qui satisfont des propriétés semblables dans la suite de leurs décimales.

Entre autres propriétés, si on supprime un nombre fini de sommets du graphe de Rado (et les arêtes attenantes), le sous-graphe obtenu est isomorphe au graphe initial. Une telle propriété n’est pas rare pour des structures infinies. L’ensemble N des entiers naturels non nuls est une partie stricte de N, mais elle est équipotente, c’est-à-dire qu’elle a autant d’éléments, ou plus formellement que son cardinal est le même infini (oui, car il existe des infinis différents). On peut même montrer que N est isomorphe à N en tant qu’ensemble ordonné. De même, l’ensemble des entiers naturels pairs est une partie stricte de N mais qui lui est isomorphe en tant que structure additive (monoïde).

L’auteur de l’article identifie le graphe de Rado avec ses sous-graphes cofinis : le graphe d’une modification est le graphe lui-même : enlever des morceaux finis ne le change pas (p. 83). Ce léger abus de langage m’interpelle par opposition aux nombres univers. Si on supprime un nombre fini de décimales d’un nombre univers, on obtient encore un (autre) nombre univers. N’y a-t-il pas moyen de considérer que tous les nombres univers sont isomorphes ?

Relation entre suites de décimales

On définit des transformations sur la suite des décimales d’un nombre pour pouvoir écrire que tous les nombres univers sont isomorphes. On se cantonne ici à la partie fractionnaire, donc à une suite infinie de chiffres. La définition est valable que l’on prenne en compte ou non les développements décimaux impropres (c’est-à-dire dont tous les chiffres valent 9 à partir d’un certain rang).

La seule permutation des décimales (toutes présentes une infinité de fois) permet de passer de n’importe quel suite des décimales d’un nombre univers à un autre. Mais ces permutations permettent aussi d’obtenir le nombre rationnel avec un développement périodique de période 0123456789. Il faut donc une notion de transformation plus stricte.

On dit alors que deux développements décimaux sont en relation s’ils admettent une partition commune de leurs décimales en séquences 2 à 2 distinctes. Autrement dit, on peut découper le premier développement décimal en sous-suites finies deux à deux distinctes et réarranger celles-ci pour recomposer le deuxième développement décimal.

Cette relation est clairement réflexive (on peut décomposer n’importe quel développement décimal en sous-suites de longueurs deux à deux distinctes) et symétrique. Sa clôture transitive est donc une relation d’équivalence.

Vérification de la relation entre les nombres univers

Soit x et y deux développements décimaux de nombres univers. On construit par récurrence une suite croissante d’ensembles (Sn) telle que pour tout nN, l’ensemble Sn est composé de n suites finies de chiffres, dont une concaténation donne le début de x si n est pair et donne le début de y si n est impair.

On pose S0 = ∅ et S1 contient la première décimale de y.

Soit kN. Supposons qu’il existe deux ensembles S2k et S2k+1 satisfaisant les conditions. On note m la somme des longueurs des éléments de S2k, et on note s le seul élément de S2k+1S2k. La suite finie s apparait une infinité de fois au delà du rang m dans x, donc il existe une occurrence avant laquelle les décimales au delà du rang m forment une suite finie tabsente de S2k+1. On pose alors S2k+2 = S2k+1 ∪ {t}. On construit de même S2k+3 à l’aide des occurrences de t dans y.

La réunion croissante de tous les ensembles Sk permet de reconstruire à la fois x et y par des réarrangements.

Spécificité des nombres univers

Il reste à vérifier qu’avec la relation précédemment définie, un nombre univers ne peut être en relation qu’avec un (autre) nombre univers.

Soit x le développement décimal d’un nombre univers et y un développement avec qui il est en relation. Soit t une suite finie de chiffres. La suite x contient une infinité de fois la séquence doublée s = tt or elle est découpée en sous-suites qui sont toutes de longueur supérieure à celle de s (sauf un nombre fini d’entre elles). Il existe donc au moins une séquence qui n’est découpée qu’une seule fois dans une sous-suite, donc il existe une sous-suite qui contient au moins une fois le motif t, qui se retrouve donc dans y. Donc y est bien aussi un nombre univers.