Le neuvième nombre de Dedekind

2 86 386 577 668 298 411 128 469 151 667 598 498 812 366. Voilà le plus grand nombre de Dedekind connu à ce jour ! Et ce n’est que le neuvième (ou le dixième si l’on compte celui de rang 0). Cette suite incroyable, répertoriée sous le matricule A000372 dans l’OEIS, l’Encyclopédie en ligne des suites d’entiers de Neil Sloane, donne du fil à retordre à tous les calculateurs depuis plus d’un siècle. Pourtant, plusieurs points de vue variés permettent de définir cette suite numérique et on la croise dans des domaines au premier abord bien différents.

Le point de vue initial consiste à étudier les fonctions logiques croissantes. Une fonction logique prend en entrée des booléens, c’est-à-dire des variables qui prennent la valeur « Vrai » ou « Faux », et renvoie un booléen.

Comment définir un sens de variation ici ? Eh bien, le plus simple est d’attribuer la valeur 0 à « Faux » et la valeur 1 à « Vrai ». Nos fonctions sont donc définies sur des n-uplets de 0 et de 1 et les images valent soit 0, soit 1. Prenez deux n-uplets, x = (x₁, x₂… x_n) et y = (y₁, y₂… y_n) tels que x₁ ≤ y₁, x₂ ≤ y₂… x_n ≤ y_n. On dira que la fonction logique f est croissante si, dans ce cas, f(x) ≤ f(y), ce qui n’est évidemment pas sans rappeler l’idée que l’on se fait d’une fonction croissante en analyse. Avec un peu d’attention, on se rend compte que cela revient à considérer une fonction définie sur {0, 1}ⁿ telle que, si l’un des booléens donnés en entrée passe de « Faux » à « Vrai », alors l’image ne peut pas passer de « Vrai » à « Faux ».

En 1897, le mathématicien allemand Richard Dedekind s’est demandé combien il existait de telles fonctions pour un entier n donné. Et il s’est vite aperçu qu’il risquait d’y en avoir beaucoup ! En effet, il y a 2ⁿ n-uplets à prendre en compte. Définir une fonction logique sur cet ensemble, c’est attribuer la valeur 0 ou 1 à chacun de ces n-uplets. Nous voilà donc avec un total de