En matemáticas , los números de Dedekind son una secuencia de números enteros que crece rápidamente y llevan el nombre de Richard Dedekind , quien los definió en 1897. El número de Dedekind M ( n ) cuenta el número de funciones booleanas monótonas de n variables. De manera equivalente, cuenta el número de antichains de subconjuntos de un conjunto de n elementos, el número de elementos en una red distributiva libre con n generadores o el número de complejos simpliciales abstractos con n elementos.
Se conocen estimaciones asintóticas precisas de M ( n ) y una expresión exacta como suma . [1] [2] Sin embargo, el problema de Dedekind de calcular los valores de M ( n ) sigue siendo difícil: no se conoce ninguna expresión de forma cerrada para M ( n ) y los valores exactos de M ( n ) se han encontrado solo para n ≤ 8 . [3]
Definiciones
Una función booleana es una función que toma como entrada n variables booleanas (es decir, valores que pueden ser falsos o verdaderos, o valores binarios equivalentes que pueden ser 0 o 1) y produce como salida otra variable booleana. Es monótono si, para cada combinación de entradas, cambiar una de las entradas de falso a verdadero solo puede hacer que la salida cambie de falso a verdadero y no de verdadero a falso. El número de Dedekind M ( n ) es el número de diferentes funciones booleanas monótonas en n variables.
Un antichain de conjuntos (también conocido como familia Sperner ) es una familia de conjuntos, ninguno de los cuales está contenido en ningún otro conjunto. Si V es un conjunto de n variables booleanas, un antichain A de subconjuntos de V define una función booleana monótona f , donde el valor de f es verdadero para un conjunto dado de entradas si algún subconjunto de las entradas verdaderas af pertenece a A y falso de lo contrario. A la inversa, cada función booleana monótona define de esta manera un antichain, de los subconjuntos mínimos de variables booleanas que pueden forzar que el valor de la función sea verdadero. Por lo tanto, el número de Dedekind M ( n ) es igual al número de diferentes antichains de subconjuntos de un conjunto de n elementos. [4]
Una tercera forma equivalente de describir la misma clase de objetos utiliza la teoría de celosía . De cualquiera de las dos funciones booleanas monótona f y g podemos encontrar otras dos funciones booleanas monótonas f ∧ g y f ∨ g , su conjunción lógica y disyunción lógica respectivamente. La familia de todas las funciones booleanas monótonas en n entradas, junto con estas dos operaciones, forma una red distributiva , la red dada por el teorema de representación de Birkhoff a partir del conjunto parcialmente ordenado de subconjuntos de las n variables con inclusión de conjuntos como orden parcial. Esta construcción produce la red distributiva libre con n generadores. [5] Por lo tanto, los números de Dedekind cuentan el número de elementos en redes distributivas libres. [6]
Los números de Dedekind también cuentan (uno más que) el número de complejos simpliciales abstractos en n elementos, familias de conjuntos con la propiedad de que cualquier subconjunto de un conjunto en la familia también pertenece a la familia. Cualquier antichain determina un complejo simplicial, la familia de subconjuntos de miembros antichain y, a la inversa, los simplices máximos en un complejo forman un antichain. [7]
Ejemplo
Para n = 2, hay seis funciones booleanas monótonas y seis antichains de subconjuntos del conjunto de dos elementos { x , y }:
- La función f ( x , y ) = false que ignora sus valores de entrada y siempre devuelve falso corresponde al antichain Ø vacío .
- La conjunción lógica f ( x , y ) = x ∧ y corresponde al antichain {{ x , y }} que contiene el conjunto único { x , y }.
- La función f ( x , y ) = x que ignora su segundo argumento y devuelve el primer argumento corresponde al antichain {{ x }} que contiene el conjunto único { x }
- La función f ( x , y ) = y que ignora su primer argumento y devuelve el segundo argumento corresponde al antichain {{ y }} que contiene el conjunto único { y }
- La disyunción lógica f ( x , y ) = x ∨ y corresponde al antichain {{ x }, { y }} que contiene los dos conjuntos { x } e { y }.
- La función f ( x , y ) = true que ignora sus valores de entrada y siempre devuelve true corresponde al antichain {Ø} que contiene solo el conjunto vacío.
Valores
Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 8:
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (secuencia A000372 en la OEIS ).
Los primeros seis de estos números son dados por Church (1940) . M (6) fue calculado por Ward (1946) , M (7) fue calculado por Church (1965) y Berman & Köhler (1976) , y M (8) por Wiedemann (1991) .
Si n es par, entonces M ( n ) también debe ser par. [8] El cálculo del quinto número de Dedekind M (5) = 7581 refutó una conjetura de Garrett Birkhoff de que M ( n ) siempre es divisible por (2 n - 1) (2 n - 2). [9]
Fórmula de suma
Kisielewicz (1988) reescribió la definición lógica de antichains en la siguiente fórmula aritmética para los números de Dedekind:
dónde es el th bit del número, que se puede escribir usando la función de piso como
Sin embargo, esta fórmula no es útil para calcular los valores de M ( n ) para n grande debido a la gran cantidad de términos en la suma.
Asintóticos
El logaritmo de los números de Dedekind se puede estimar con precisión a través de los límites
Aquí la desigualdad de la izquierda cuenta el número de antichains en los que cada conjunto tiene exactamente elementos, y la desigualdad correcta fue probada por Kleitman y Markowsky (1975) .
Korshunov (1981) proporcionó estimaciones aún más precisas [10]
para incluso n , y
para n impar , donde
y
La idea principal detrás de estas estimaciones es que, en la mayoría de los antichains, todos los conjuntos tienen tamaños muy cercanos a n / 2. [10] Para n = 2, 4, 6, 8, la fórmula de Korshunov proporciona una estimación que es inexacta en un factor de 9,8%, 10,2%, 4,1% y -3,3%, respectivamente. [11]
Notas
- ^ Kleitman y Markowsky (1975) ; Korshunov (1981) ; Kahn (2002) .
- ^ Kisielewicz (1988) .
- ^ Wiedemann (1991) .
- ^ Kahn (2002) .
- ^ La definición de celosías distributivas libres que se utiliza aquí permite como operaciones de celosía cualquier encuentro y unión finitos, incluidos el encuentro vacío y la unión vacía. Para el retículo distributivo libre en el que solo se permiten encuentros y uniones por pares, se deben eliminar los elementos del retículo superior e inferior y restar dos de los números de Dedekind.
- ^ Iglesia (1940) ; Iglesia (1965) ; Zaguia (1993) .
- ^ Kisielewicz (1988) .
- ↑ Yamamoto (1953) .
- ^ Iglesia (1940) .
- ↑ a b Zaguia (1993) .
- ^ Brown, KS, Generando las funciones booleanas monótonas
Referencias
- Berman, Joel; Köhler, Peter (1976), "Cardinalidades de celosías distributivas finitas", Mitt. Matemáticas. Sem. Giessen , 121 : 103-124, MR 0485609.
- Church, Randolph (1940), "Análisis numérico de ciertas estructuras distributivas libres", Duke Mathematical Journal , 6 : 732–734, doi : 10.1215 / s0012-7094-40-00655-x , MR 0002842.
- Church, Randolph (1965), "Enumeración por rango de la red distributiva libre con 7 generadores", Notices of the American Mathematical Society , 11 : 724. Como lo cita Wiedemann (1991) .
- Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler", Gesammelte Werke , 2 , págs. 103-148.
- Kahn, Jeff (2002), "Entropía, conjuntos independientes y antichains: un nuevo enfoque al problema de Dedekind", Proceedings of the American Mathematical Society , 130 (2): 371-378, doi : 10.1090 / S0002-9939-01-06058 -0 , MR 1862115.
- Kisielewicz, Andrzej (1988), "Una solución del problema de Dedekind sobre el número de funciones booleanas isotónicas", Journal für die Reine und Angewandte Mathematik , 386 : 139-144, doi : 10.1515 / crll.1988.386.139 , MR 0936995
- Kleitman, D .; Markowsky, G. (1975), "Sobre el problema de Dedekind: el número de funciones booleanas isotónicas. II", Transactions of the American Mathematical Society , 213 : 373–390, doi : 10.2307 / 1998052 , MR 0382107.
- Korshunov, AD (1981), "El número de funciones booleanas monótonas", Problemy Kibernet. , 38 : 5–108, MR 0640855.
- Ward, Morgan (1946), "Nota sobre el orden de las celosías distributivas libres", Boletín de la American Mathematical Society , 52 : 423, doi : 10.1090 / S0002-9904-1946-08568-7.
- Wiedemann, Doug (1991), "Un cálculo del octavo número de Dedekind", Orden , 8 (1): 5–6, doi : 10.1007 / BF00385808 , MR 1129608.
- Yamamoto, Koichi (1953), "Note on the order of free distributive retices", Science Reports of the Kanazawa University , 2 (1): 5–6, MR 0070608.
- Zaguia, Nejib (1993), "Mapas isotónicos: enumeración y estructura", en Sauer, NW; Woodrow, RE; Sands, B. (eds.), Combinatoria finita e infinita en conjuntos y lógica (Proc.NATO Advanced Study Inst., Banff, Alberta, Canadá, 4 de mayo de 1991) , Kluwer Academic Publishers, págs. 421–430, MR 1261220.