En matemáticas , específicamente en teoría del orden , la compleción de Dedekind-MacNeille de un conjunto parcialmente ordenado es la red completa más pequeña que lo contiene. Recibe su nombre en honor a Holbrook Mann MacNeille , cuyo artículo de 1937 lo definió y construyó por primera vez, y en honor a Richard Dedekind porque su construcción generaliza los cortes de Dedekind utilizados por Dedekind para construir los números reales a partir de los números racionales . También se denomina compleción por cortes o compleción normal . [1]
Un conjunto parcialmente ordenado (poset) consiste en un conjunto de elementos junto con una relación binaria x ≤ y en pares de elementos que es reflexiva ( x ≤ x para cada x ), transitiva (si x ≤ y e y ≤ z entonces x ≤ z ) y antisimétrica (si tanto x ≤ y como y ≤ x se cumplen, entonces x = y ). Los ordenamientos numéricos habituales en los números enteros o reales satisfacen estas propiedades; sin embargo, a diferencia de los ordenamientos en los números, un orden parcial puede tener dos elementos que son incomparables : ni x ≤ y ni y ≤ x se cumplen. Otro ejemplo familiar de un ordenamiento parcial es el ordenamiento de inclusión ⊆ en pares de conjuntos. [2]
Si S es un conjunto parcialmente ordenado, una completitud de S significa una red completa L con una incrustación de orden de S en L . [3] Una red completa es una red en la que cada subconjunto de elementos de L tiene un ínfimo y un supremo ; esto generaliza las propiedades análogas de los números reales . Una incrustación de orden es una función que asigna elementos distintos de S a elementos distintos de L de modo que cada par de elementos en S tiene el mismo orden en L que en S . La línea de números reales extendida (números reales junto con +∞ y −∞) es una completitud en este sentido de los números racionales: el conjunto de números racionales {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} no tiene un límite superior mínimo racional, pero en los números reales tiene el límite superior mínimo π . [4]
Un conjunto parcialmente ordenado dado puede tener varias compleciones diferentes. Por ejemplo, una compleción de cualquier conjunto parcialmente ordenado S es el conjunto de sus subconjuntos cerrados hacia abajo ordenados por inclusión . S se incrusta en esta red (completa) al mapear cada elemento x al conjunto inferior de elementos que son menores o iguales a x . El resultado es una red distributiva y se utiliza en el teorema de representación de Birkhoff . Sin embargo, puede tener muchos más elementos de los necesarios para formar una compleción de S . [5] Entre todas las compleciones de red posibles, la compleción de Dedekind-MacNeille es la red completa más pequeña con S incrustado en ella. [6]
Para cada subconjunto A de un conjunto parcialmente ordenado S , sea A u el conjunto de límites superiores de A ; es decir, un elemento x de S pertenece a A u siempre que x sea mayor o igual que cada elemento de A . Simétricamente, sea A l el conjunto de límites inferiores de A , los elementos que son menores o iguales que cada elemento de A . Entonces, la compleción de Dedekind-MacNeille de S consiste en todos los subconjuntos A para los cuales
Se ordena por inclusión: A ≤ B en la completitud si y sólo si A ⊆ B como conjuntos. [7]
Un elemento x de S se incorpora en la completitud como su ideal principal , el conjunto ↓ x de elementos menores o iguales a x . Entonces (↓ x ) u es el conjunto de elementos mayores o iguales a x , y ((↓ x ) u ) l = ↓ x , lo que demuestra que ↓ x es de hecho un miembro de la completitud. La aplicación de x a ↓ x es una incorporación de orden. [7]
A veces se utiliza una definición alternativa de la compleción de Dedekind–MacNeille que se asemeja más a la definición de un corte de Dedekind. [8] En un conjunto parcialmente ordenado S , defina un corte como un par de conjuntos ( A , B ) para los cuales A u = B y A = B l . Si ( A , B ) es un corte, entonces A satisface la ecuación ( A u ) l = A , y a la inversa, si ( A u ) l = A , entonces ( A , A u ) es un corte. Por lo tanto, el conjunto de cortes, parcialmente ordenado por inclusión en el conjunto inferior del corte (o el reverso de la relación de inclusión en el conjunto superior), da una definición equivalente de la compleción de Dedekind–MacNeille. [9]
Con la definición alternativa, tanto la operación de unión como la de encuentro de la red completa tienen descripciones simétricas: si ( A i , B i ) son los cortes en cualquier familia de cortes, entonces el encuentro de estos cortes es el corte ( L , L u ) donde L = ∩ i A i , y la unión es el corte ( U l , U ) donde U = ∩ i B i . [9]
Si es el conjunto de números racionales , visto como un conjunto totalmente ordenado con el orden numérico habitual, entonces cada elemento de la completitud de Dedekind–MacNeille de puede verse como un corte de Dedekind , y la completitud de Dedekind–MacNeille de es el ordenamiento total de los números reales , junto con los dos valores adicionales . [10]
Si S es una anticadena (un conjunto de elementos en el que no hay dos comparables), entonces la completitud Dedekind-MacNeille de S consiste en el propio S junto con dos elementos adicionales, un elemento inferior que está debajo de cada elemento en S y un elemento superior que está encima de cada elemento en S. [11 ]
Si O es cualquier conjunto finito de objetos, y A es cualquier conjunto finito de atributos unarios para los objetos en O , entonces se puede formar un orden parcial de altura dos en el que los elementos del orden parcial son los objetos y atributos, y en el que x ≤ y cuando x es un objeto que tiene el atributo y . Para un orden parcial definido de esta manera, la compleción de Dedekind-MacNeille de S se conoce como red de conceptos , y juega un papel central en el campo del análisis formal de conceptos . [12]
La completitud de Dedekind-MacNeille de un conjunto parcialmente ordenado S es la red completa más pequeña con S incluido en ella, en el sentido de que, si L es cualquier completitud de red de S , entonces la completitud de Dedekind-MacNeille es un subconjunto parcialmente ordenado de L . [6] Cuando S es finito, su completitud también es finita, y tiene el menor número de elementos entre todas las redes completas finitas que contienen a S . [12]
El conjunto parcialmente ordenado S es denso en uniones y en encuentros en la completitud Dedekind–MacNeille; es decir, cada elemento de la completitud es una unión de algún conjunto de elementos de S , y también es el encuentro de algún conjunto de elementos en S . [13] La completitud Dedekind–MacNeille se caracteriza entre las completitudes de S por esta propiedad. [14]
La compleción de Dedekind-MacNeille de un álgebra de Boole es un álgebra de Boole completa ; este resultado se conoce como el teorema de Glivenko-Stone , en honor a Valery Ivanovich Glivenko y Marshall Stone . [15] De manera similar, la compleción de Dedekind-MacNeille de una red residual es una red residual completa. [16] Sin embargo, la compleción de una red distributiva no necesita ser distributiva en sí misma, y la compleción de una red modular puede no seguir siendo modular. [17]
La completitud de Dedekind-MacNeille es autodual: la completitud del dual de un orden parcial es la misma que la del dual de la completitud. [18]
La compleción Dedekind-MacNeille de S tiene la misma dimensión de orden que S mismo. [19]
En la categoría de conjuntos parcialmente ordenados y funciones monótonas entre conjuntos parcialmente ordenados, las redes completas forman los objetos inyectivos para las incrustaciones de orden , y la compleción de Dedekind-MacNeille de S es la envoltura inyectiva de S. [20]
Varios investigadores han estudiado algoritmos para construir la compleción de Dedekind-MacNeille de un conjunto parcialmente ordenado finito. La compleción de Dedekind-MacNeille puede ser exponencialmente mayor que el orden parcial del que proviene, [12] y los límites de tiempo para tales algoritmos generalmente se establecen de una manera sensible a la salida , dependiendo tanto del número n de elementos del orden parcial de entrada como del número c de elementos de su compleción.
Ganter y Kuznetsov (1998) describen un algoritmo incremental, en el que el orden parcial de entrada se construye añadiendo un elemento a la vez; en cada paso, la compleción del orden parcial más pequeño se expande para formar la compleción del orden parcial más grande. En su método, la compleción se representa mediante una lista explícita de cortes. Cada corte del orden parcial aumentado, excepto aquel cuyos dos conjuntos se intersecan en el nuevo elemento, es un corte del orden parcial anterior o se forma añadiendo el nuevo elemento a uno u otro lado de un corte del orden parcial anterior, por lo que su algoritmo solo necesita probar pares de conjuntos de esta forma para determinar cuáles son cortes. El tiempo para utilizar su método para añadir un único elemento a la compleción de un orden parcial es O ( cnw ) donde w es el ancho del orden parcial, es decir, el tamaño de su anticadena más grande . Por lo tanto, el tiempo para calcular la compleción de un orden parcial dado es O ( cn 2 w ) = O( cn 3 ) . [12]
Como observan Jourdan, Rampon y Jard (1994), el problema de enumerar todos los cortes en un conjunto parcialmente ordenado puede formularse como un caso especial de un problema más simple, de enumerar todas las anticadenas máximas en un conjunto parcialmente ordenado diferente. Si P es cualquier conjunto parcialmente ordenado, sea Q un orden parcial cuyos elementos contienen dos copias de P : para cada elemento x de P , Q contiene dos elementos x 0 y x 1 , con x i < y j si y solo si x < y e i < j . Entonces los cortes en P corresponden uno a uno con las anticadenas máximas en Q : los elementos en el conjunto inferior de un corte corresponden a los elementos con subíndice 0 en una anticadena, y los elementos en el conjunto superior de un corte corresponden a los elementos con subíndice 1 en una anticadena. Jourdan et al. describe un algoritmo para encontrar anticadenas máximas que, cuando se aplica al problema de listar todos los cortes en P , toma tiempo O ( c ( nw + w 3 )) , una mejora del algoritmo de Ganter & Kuznetsov (1998) cuando el ancho w es pequeño. [21] Alternativamente, una anticadena máxima en Q es lo mismo que un conjunto independiente máximo en el gráfico de comparabilidad de Q , o una camarilla máxima en el complemento del gráfico de comparabilidad, por lo que los algoritmos para el problema de camarilla o el problema de conjunto independiente también se pueden aplicar a esta versión del problema de completitud de Dedekind–MacNeille. [22]
El grafo de reducción transitiva o grafo de cobertura de la compleción de Dedekind–MacNeille describe la relación de orden entre sus elementos de una manera concisa: cada vecino de un corte debe eliminar un elemento del orden parcial original del conjunto superior o inferior del corte, por lo que cada vértice tiene como máximo n vecinos. Por lo tanto, el grafo de cobertura tiene c vértices y como máximo cn /2 vecinos, un número que puede ser mucho menor que las c 2 entradas en una matriz que especifica todas las comparaciones por pares entre elementos. Nourine y Raynaud (1999) muestran cómo calcular este grafo de cobertura de manera eficiente; de manera más general, si B es cualquier familia de conjuntos, muestran cómo calcular el grafo de cobertura de la red de uniones de subconjuntos de B . En el caso de la red de Dedekind–MacNeille, B puede tomarse como la familia de conjuntos complementarios de ideales principales, y las uniones de subconjuntos de B son complementos de los conjuntos inferiores de cortes. La idea principal de su algoritmo es generar uniones de subconjuntos de B de forma incremental (para cada conjunto en B , formando su unión con todas las uniones generadas previamente), representar la familia resultante de conjuntos en un trie y usar la representación del trie para probar ciertos pares de conjuntos candidatos para la adyacencia en la relación de cobertura; lleva tiempo O ( cn 2 ) . En trabajos posteriores, los mismos autores demostraron que el algoritmo podría hacerse completamente incremental (capaz de agregar elementos al orden parcial uno a la vez) con el mismo límite de tiempo total. [23]
