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 = (x1, x2… xn ) et y = (y1, y2… yn ) tels que x1 ≤ y1, x2 ≤ y2… xn ≤ yn. On dira que la fonction logique f est croissante ...
Lire la suite