En matemáticas , específicamente en teoría del orden , la terminación de Dedekind-MacNeille de un conjunto parcialmente ordenado es la red completa más pequeña que lo contiene. Lleva el nombre de Holbrook Mann MacNeille , cuyo artículo de 1937 lo definió y construyó por primera vez, y de 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 le llama terminación por cortes o terminación normal . [1]
Un conjunto parcialmente ordenado (poset) consta de un conjunto de elementos junto con una relación binaria x ≤ y sobre pares de elementos que es reflexiva ( x ≤ x para cada x ), transitiva (si x ≤ y e y ≤ z entonces x ≤ z ), y antisimétrico (si se cumplen tanto x ≤ y como y ≤ x , entonces x = y ). Los ordenamientos numéricos habituales de los números enteros o reales satisfacen estas propiedades; sin embargo, a diferencia del ordenamiento de 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 ordenamiento parcial es el ordenamiento de inclusión ⊆ en pares de conjuntos. [2]
Si S es un conjunto parcialmente ordenado, una finalización de S significa una red completa L con un orden de inclusión de S en L. [3] Una red completa es una red en la que cada subconjunto de elementos de L tiene un mínimo 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 distintos elementos de S a distintos elementos de L de modo que cada par de elementos en S tiene el mismo orden en L que en S. La recta de números reales extendida (números reales junto con +∞ y −∞) es una compleción 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 no tiene un límite superior mínimo racional, pero en los números reales tiene el límite superior mínimo π . [4]
Un determinado conjunto parcialmente ordenado puede tener varias terminaciones diferentes. Por ejemplo, una terminación de cualquier conjunto parcialmente ordenado S es el conjunto de sus subconjuntos cerrados hacia abajo ordenados por inclusión . S está incrustado en esta red (completa) asignando cada elemento x al conjunto inferior de elementos que son menores o iguales que 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 terminación de S. [5] Entre todas las terminaciones de celosía posibles, la terminación de Dedekind-MacNeille es la celosía completa más pequeña con S incrustado en ella. [6]
Para cada subconjunto A de un conjunto parcialmente ordenado S , sea Au u el conjunto de límites superiores de A ; es decir, un elemento x de S pertenece a Au siempre que x sea mayor o igual a cada elemento de A. Simétricamente, denotemos por Al el conjunto de límites inferiores de A , los elementos que son menores o iguales a cada elemento de A. Entonces la compleción de Dedekind-MacNeille de S consta de todos los subconjuntos A para los cuales
se ordena por inclusión: A ≤ B en la compleción si y sólo si A ⊆ B como conjuntos. [7]
Un elemento x de S incorpora en la terminación como su ideal principal , el conjunto ↓ x de elementos menores o iguales a x . Entonces (↓ x ) u es el conjunto de elementos mayor o igual a x , y ((↓ x ) u ) l = ↓ x , lo que demuestra que ↓ x es de hecho un miembro de la compleción. El mapeo de x a ↓ x es una inclusión de orden. [7]
A veces se utiliza una definición alternativa de terminación de Dedekind-MacNeille que se parece más a la definición de 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 ordenados por inclusión en el conjunto inferior del corte (o al revés de la relación de inclusión en el conjunto superior), da una definición equivalente de la terminación de Dedekind-MacNeille. [9]
Con la definición alternativa, tanto las operaciones de unión como 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 terminación de Dedekind-MacNeille puede verse como un corte de Dedekind , y la terminación de Dedekind-MacNeille es el orden total de los números reales , junto con los dos valores adicionales . [10]
Si S es una anticadena (un conjunto de elementos de los cuales no hay dos comparables), entonces la terminación de Dedekind-MacNeille de S consta del propio S junto con dos elementos adicionales, un elemento inferior que está debajo de cada elemento en S y un elemento superior que está por encima de cada elemento en S . [11]
Si O es un conjunto finito de objetos y A es un 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 sean los objetos y los atributos, y en cual x ≤ y cuando x es un objeto que tiene el atributo y . Para un orden parcial definido de esta manera, la compleción de S de Dedekind-MacNeille se conoce como red de conceptos y juega un papel central en el campo del análisis formal de conceptos . [12]
La terminación de Dedekind-MacNeille de un conjunto parcialmente ordenado S es la red completa más pequeña con S incrustado en ella, en el sentido de que, si L es cualquier terminación de red de S , entonces la terminación de Dedekind-MacNeille es un subconjunto parcialmente ordenado de L. [6] Cuando S es finito, su compleción también es finita y tiene el menor número de elementos entre todas las redes finitas completas que contienen S. [12]
El conjunto parcialmente ordenado S es denso en unión y denso en encuentro en la terminación de Dedekind-MacNeille; es decir, cada elemento de la compleción es una unión de algún conjunto de elementos de S , y también es la unión de algún conjunto de elementos en S. [13] La terminación de Dedekind-MacNeille se caracteriza entre las terminaciones de S por esta propiedad. [14]
La finalización de Dedekind-MacNeille de un álgebra booleana es un álgebra booleana completa ; este resultado se conoce como teorema de Glivenko-Stone , en honor a Valery Ivanovich Glivenko y Marshall Stone . [15] De manera similar, la terminación de Dedekind-MacNeille de una red residual es una red residual completa. [16] Sin embargo, la terminación de una red distributiva no necesita ser en sí misma distributiva, y la terminación de una red modular puede no seguir siendo modular. [17]
La compleción de Dedekind-MacNeille es autodual: la compleción del dual de un orden parcial es la misma que la compleción del dual. [18]
La terminación de Dedekind-MacNeille de S tiene la misma dimensión de orden que el propio S. [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 incrustaciones de orden , y la terminación de Dedekind-MacNeille de S es el casco inyectivo de S. [20]
Varios investigadores han investigado algoritmos para construir la terminación de Dedekind-MacNeille de un conjunto finito parcialmente ordenado. La finalizació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 , y sobre el número c de elementos de su finalizació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 finalización del orden parcial más pequeño se expande para formar la finalización del orden parcial más grande. En su método, la finalización está representada por una lista explícita de cortes. Cada corte del orden parcial aumentado, excepto aquel cuyos dos conjuntos se cruzan 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 anterior. orden parcial, por lo que su algoritmo solo necesita probar pares de conjuntos de esta forma para determinar cuáles son cortes. El tiempo para usar su método para agregar un solo elemento para completar un pedido parcial es O ( cnw ) , donde w es el ancho del pedido parcial, es decir, el tamaño de su anticadena más grande . Por lo tanto, el tiempo para calcular la finalización de un pedido 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 sólo si x < y y yo < j . Entonces los cortes en P corresponden uno por 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. describen un algoritmo para encontrar anticadenas máximas que, cuando se aplica al problema de enumerar todos los cortes en P , toma tiempo O ( c ( nw + w 3 )) , una mejora con respecto al algoritmo de Ganter y 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 pueden se aplicará a esta versión del problema de terminación de Dedekind-MacNeille. [22]
La reducción transitiva o gráfico de cobertura de la terminación de Dedekind-MacNeille describe la relación de orden entre sus elementos de 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 gráfico 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 eficientemente este gráfico de cobertura; De manera más general, si B es cualquier familia de conjuntos, muestran cómo calcular el gráfico 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 de conjuntos resultante en un trie y usar la representación trie para probar ciertos pares candidatos de conjuntos para adyacencia en la relación de cobertura; lleva tiempo O ( cn 2 ) . En trabajos posteriores, los mismos autores demostraron que el algoritmo podía hacerse completamente incremental (capaz de agregar elementos al orden parcial uno a la vez) con el mismo límite de tiempo total. [23]
