Número de Dedekind

En combinatòria, els números de Dedekind són una successió sancera de ràpit creiximent el nom del qual es va donar póstumamente en honor a Richard Dedekind, qui les va definir per primera volta en 1897. El número de Dedekind M(n) correspon, equivalentement, a lo següent:

• El número de funcions booleanas monòtones de n variables.
• El número d'anticadenas de subconjunts d'un conjunt de n elements.
• El número d'elements en un retícul distributivo lliure en n generadors.
• El número de jocs simples irredundantes definibles sobre n jugadors.
• El número d'hipergrafos minimales complets, definibles sobre un conjunt base de cardinalidad n.
• El número de famílies de Sperner sobre un conjunt de n elements.

Trobar una expressió matemàtica de forma tancada per a M(n) es coneix com el Problema de Dedekind. Encara que existixen aproximacions asintòtiques que estimen este número, i una expressió exacta en forma de sumatoria, el còmput de M(n) seguix sent ineficiente, i els seus valors exactes només es coneixen para valores n ≤ 9.

Eixemple

Per a n = 2, existixen sis funcions booleanas monòtones i sis anticadenas de subconjunts del conjunt de dos elements {x,i}:

• La funció f(x,i) = fals, que ignora els seus valors d'entrada i sempre retorna fals, correspon a l'anticadena buida Ø.
• La conjunció llògica f(x,i) = x ∧ i correspon a la anticadena { {x,i} }, que conté al conjunt {x,i}.
• La funció f(x,i) = x, que ignora el seu segon argument i retorna el primer, correspon a la anticadena { {x} } que conté al conjunt {x}.
• La funció f(x,i) = i, que ignora el seu primer argument i retorna el segon, correspon a la anticadena { {i} } que conté al conjunt {i}.
• La disjunció llògica f(x,i) = x ∨ i correspon a la anticadena { {x}, {i} }, que conté als dos conjunts {x} i {i}.
• La funció f(x,i) = verdader, que ignora els seus valors d'entrada i sempre retorna verdader, correspon a la anticadena {Ø} que conté només al conjunt buit.

Valors coneguts

Els valors exactes dels números de Dedekind es coneixen per a 0 ≤ n ≤ 9. La següent taula mostra tals números, junt en l'any i la publicació en que varen ser calculats:

Archiu:Numeros Dedekind.jpg

Gràfica dels números de Dedekind fins a n = 8, a on s'aprecia el creiximent exponencial de la successió.

n	número M(n)	Any
0	2	1940
1	3	1940
2	6	1940
3	20	1940
4	168	1940
5	7 581	1940
6	7 828 354 $\approx 7.83\times 10^6$	1946
7	2 414 682 040 998 $\approx 2.41\times 10^{12}$	1965 i 1976
8	56 130 437 228 687 557 907 788 $\approx 5.61\times 10^{22}$	1991
9	286 386 577 668 298 411 128 469 151 667 598 498 812 366 $\approx 2.86\times 10^{41}$	2023
Plantilla:OEIS

Si n és un número par, llavors M(n) també deuria ser-ho. El càlcul de M(5) = 7581 va ser el contraeixemple que va desaprovar una conjectura realisada per Garrett Birkhoff que dia que M(n) és sempre divisible per (2n - 1)(2n - 2).