Ir al contenido

Número de Dedekind

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 15:06 13 nov 2019 por InternetArchiveBot (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.
contradicciónA y B y CA y BA y CB y C(A y B) o (A y C)(A y B) o (B y C)(A y C) o (B y C)ABC(A o B) y (A o C) y (B o C) <==> (A y B) o (A y C) o (B y C)(A o B) y (A o C)(A o B) y (B o C)(A o C) y (B o C)A o BA o CB o CA o B o Ctautología
Los retículos distributivos libres de funciones booleanas monótonas sobre 0, 1, 2 y 3 argumentos.

En combinatoria, los números de Dedekind son una sucesión entera de rápido crecimiento cuyo nombre se dio póstumamente en honor a Richard Dedekind, quien las definió por primera vez en 1897.[1]​ El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

Encontrar una expresión matemática de forma cerrada para M(n) se conoce como el Problema de Dedekind. Aunque existen aproximaciones asintóticas que estiman este número,[2][3][4]​ y una expresión exacta en forma de sumatoria,[5]​ el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 8.[6]

Ejemplo

Para n = 2, existen seis funciones booleanas monótonas y seis anticadenas de subconjuntos del conjunto de dos elementos {x,y}:

  • La función f(x,y) = falso, que ignora sus valores de entrada y siempre retorna falso, corresponde a la anticadena vacía Ø.
  • La conjunción lógica f(x,y) = xy corresponde a la anticadena { {x,y} }, que contiene al conjunto {x,y}.
  • La función f(x,y) = x, que ignora su segundo argumento y retorna el primero, corresponde a la anticadena { {x} } que contiene al conjunto {x}.
  • La función f(x,y) = y, que ignora su primer argumento y retorna el segundo, corresponde a la anticadena { {y} } que contiene al conjunto {y}.
  • La disyunción lógica f(x,y) = xy corresponde a la anticadena { {x}, {y} }, que contiene a los dos conjuntos {x} e {y}.
  • La función f(x,y) = verdadero, que ignora sus valores de entrada y siempre retorna verdadero, corresponde a la anticadena {Ø} que contiene sólo al conjunto vacío.

Valores conocidos

Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 8. La siguiente tabla muestra tales números, junto con el año y la publicación en que fueron calculados:

Gráfica de los números de Dedekind conocidos, donde se aprecia el crecimiento exponencial de la sucesión.
n Número M(n) Año
0 2 1940[1]
1 3 1940[1]
2 6 1940[1]
3 20 1940[1]
4 168 1940[1]
5 7581 1940[7]
6 7828354 1946[8]
7 2414682040998 1965[9]​ y 1976[10]
8 56130437228687557907788 1991[6]
(sucesión A000372 en OEIS)

Si n es un número par, entonces M(n) también debería serlo.[11]​ El cálculo de M(5) = 7581 fue el contraejemplo que desaprobó una conjetura realizada por Garrett Birkhoff que decía que M(n) es siempre divisible por (2n - 1)(2n - 2).[7]

Fórmula con sumatoria

Andrzej Kisielewicz en 1988 demostró la siguiente fórmula para los números de Dedekind:[5]

donde

Sin embargo, esta fórmula no es útil para el cómputo de los valores de M(n) para n grandes, debido al gran número de términos en la sumatoria.

Asíntotas

El logaritmo de los números de Dedekind puede ser estimado exactamente mediante las cotas

La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.[2]

A. D. Korshunov encontró en 1981 una estimación aún mejor:[12]

para n par, y

para n impar, donde

y

La principal idea detrás de estas estimaciones, es que en la mayoría de las anticadenas, todos los conjuntos tienen tamaños muy cercanos a n/2.[13]​ Para n = 2, 4, 6 y 8, la fórmula de Korshunov provee una estimación imprecisa por un factor de 9.8%, 10.2%, 4.1%, y -3.3%, respectivamente.[14]

Referencias

  1. a b c d e f Dedekind, Richard (1897), Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler 2, Gesammelte Werke, pp. 103-148 ..
  2. a b Kleitman, D.; Markowsky, G. (1975), «On Dedekind's problem: the number of isotone Boolean functions. II», Transactions of the American Mathematical Society 213: 373-390, MR0382107 ..
  3. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
  4. Kahn, Jeff (2002), «Entropy, independent sets and antichains: a new approach to Dedekind's problem», Proceedings of the American Mathematical Society 130 (2): 371-378, doi:10.1090/S0002-9939-01-06058-0, MR1862115 ..
  5. a b Kisielewicz, Andrzej (1988), «A solution of Dedekind's problem on the number of isotone Boolean functions», Journal für die Reine und Angewandte Mathematik 386: 139-144, doi:10.1515/crll.1988.386.139, MR936995 ..
  6. a b Wiedemann, Doug (1991), «A computation of the eighth Dedekind number», Order 8 (1): 5-6, doi:10.1007/BF00385808, MR1129608 ..
  7. a b Church, Randolph (1940), «Numerical analysis of certain free distributive structures», Duke Mathematical Journal 6: 732-734, MR0002842 ..
  8. Ward, Morgan (1946), «Note on the order of free distributive lattices», Bulletin of the American Mathematical Society 52: 423 ..
  9. Church, Randolph (1965), «Enumeration by rank of the free distributive lattice with 7 generators», Notices of the American Mathematical Society 11: 724 .. Citado por Wiedemann, 1991.
  10. Berman, Joel; Köhler, Peter (1976), «Cardinalities of finite distributive lattices», Mitt. Math. Sem. Giessen 121: 103-124, MR0485609 ..
  11. Yamamoto, Koichi (1953), «Note on the order of free distributive lattices», Science Reports of the Kanazawa University 2 (1): 5-6, MR0070608 ..
  12. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
  13. Zaguia, Nejib (1993), «Isotone maps: enumeration and structure», en Sauer, N. W.; Woodrow, R. E.; Sands, B., eds., Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421-430, MR1261220 ..
  14. Brown, K. S., Generating the monotone Boolean functions, archivado desde el original el 18 de diciembre de 2010, consultado el 3 de octubre de 2010 ..