Hispanopedia Wiki
Articulo de referencia

Finalización de Dedekind-MacNeille

El diagrama de Hasse de un conjunto parcialmente ordenado (izquierda) y su completación de Dedekind-MacNeille (derecha). En matemáticas , específicamente en teoría del orden , l...

Hispanopedia WikiContenido en espanolLectura gratuita
El diagrama de Hasse de un conjunto parcialmente ordenado (izquierda) y su completación de Dedekind-MacNeille (derecha).

En matemáticas , específicamente en teoría del orden , la completación de Dedekind-MacNeille de un conjunto parcialmente ordenado es el retículo completo más pequeño que lo contiene. Recibe su nombre de Holbrook Mann MacNeille, cuyo artículo de 1937 la definió y construyó por primera vez, y de Richard Dedekind porque su construcción generaliza los cortes de Dedekind utilizados por este para construir los números reales a partir de los racionales . También se la conoce como completación por cortes o completación normal . [ 1 ]

Incrustaciones de órdenes y completaciones de retículos

Un conjunto parcialmente ordenado (poset) consiste en un conjunto de elementos junto con una relación binaria x ≤ y entre pares de elementos que es reflexiva ( x ≤ x para todo x ), transitiva (si x ≤ y e y ≤ z , entonces x ≤ z ) y antisimétrica (si se cumplen ambas condiciones , x ≤ y e y ≤ x , entonces x = y ). Los ordenamientos numéricos usuales sobre los enteros o los números reales satisfacen estas propiedades; sin embargo, a diferencia de los ordenamientos sobre los números, un orden parcial puede tener dos elementos incomparables : ni x ≤ y ni y ≤ x se cumplen. Otro ejemplo conocido de ordenamiento parcial es el ordenamiento de inclusión ⊆ sobre pares de conjuntos. [ 2 ]

Si S es un conjunto parcialmente ordenado, una completación de S significa un retículo completo L con una incrustación de orden de S en L. [ 3 ] Un retículo completo es un retículo en el 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 tal manera que cada par de elementos en S tiene el mismo orden en L que en S. La recta real extendida (números reales junto con +∞ y −∞) es una completació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 tiene una cota superior mínima racional, pero en los números reales tiene la cota superior mínima π . [ 4 ]

Un conjunto parcialmente ordenado dado puede tener varias completaciones diferentes. Por ejemplo, una completación de cualquier conjunto parcialmente ordenado S es el conjunto de sus subconjuntos cerrados hacia abajo ordenados por inclusión . S se incrusta en este retículo (completo) mapeando cada elemento x al conjunto inferior de elementos que son menores o iguales a x . El resultado es un retículo distributivo 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 completación de S. [ 5 ] Entre todas las posibles completaciones de retículos, la completación de Dedekind-MacNeille es el retículo completo más pequeño con S incrustado en él. [ 6 ]

Definición

Para cada subconjunto A de un conjunto parcialmente ordenado S , sea A u el conjunto de cotas superiores de A ; es decir, un elemento x de S pertenece a A u siempre que x sea mayor o igual que cualquier elemento de A. Simétricamente, sea A ℓ el conjunto de cotas inferiores de A , los elementos que son menores o iguales que cualquier elemento de A. Entonces, la completación de Dedekind-MacNeille de S consiste en todos los subconjuntos A para los cuales

( A u ) ℓ = A ,

ordenado por inclusión: A ≤ B en la compleción si y solo si A ⊆ B como conjuntos. [ 7 ]

Un elemento x de S se incrusta en la completación 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 ) ℓ = ↓ x , lo que demuestra que ↓ x es efectivamente un miembro de la completación. La aplicación de x a ↓ x es una incrustación de orden. [ 7 ]

A veces se utiliza una definición alternativa de la completació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, definimos un corte como un par de conjuntos ( A , B ) para los cuales A u = B y A = B ℓ . Si ( A , B ) es un corte, entonces A satisface la ecuación ( A u ) ℓ = A , y recíprocamente , si ( A u ) ℓ = 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 inverso de la relación de inclusión en el conjunto superior), da una definición equivalente de la completación de Dedekind-MacNeille. [ 9 ]

Con la definición alternativa, tanto la operación de unión como la de intersección del retículo completo tienen descripciones simétricas: si ( A i , B i ) son los cortes en cualquier familia de cortes, entonces la intersección de estos cortes es el corte ( L , L u ) donde L = ∩ i A i , y la unión es el corte ( U ℓ , U ) donde U = ∩ i B i . [ 9 ]

Ejemplos

SiQ{\displaystyle \mathbb {Q} }es el conjunto de números racionales , visto como un conjunto totalmente ordenado con el orden numérico usual, entonces cada elemento de la completación de Dedekind-MacNeille deQ{\displaystyle \mathbb {Q} }puede considerarse un corte de Dedekind y la finalización de Dedekind-MacNeille deQ{\displaystyle \mathbb {Q} }es el orden total en los números reales , junto con los dos valores adicionales±∞{\displaystyle \pm \infty }. [ 10 ]

Si S es una anticadena (un conjunto de elementos que no son comparables entre sí), entonces la completación de Dedekind-MacNeille de S consiste en S mismo junto con dos elementos adicionales, un elemento inferior que está por 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 son los objetos y los 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 completación de Dedekind-MacNeille de S se conoce como retículo de conceptos y desempeña un papel central en el campo del análisis formal de conceptos . [ 12 ] 

Propiedades

La completación de Dedekind-MacNeille de un conjunto parcialmente ordenado S es el retículo completo más pequeño con S incrustado en él, en el sentido de que, si L es cualquier completación de retículos de S , entonces la completación de Dedekind-MacNeille es un subconjunto parcialmente ordenado de L. [ 6 ] Cuando S es finito, su completación también es finita y tiene el menor número de elementos entre todos los retículos completos finitos que contienen a S. [ 12 ]

El conjunto parcialmente ordenado S es denso en uniones y denso en encuentros en la completación de Dedekind-MacNeille; es decir, cada elemento de la completación es la 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 completación de Dedekind-MacNeille se caracteriza entre las completaciones de S por esta propiedad. [ 14 ]

La completación de Dedekind-MacNeille de un álgebra booleana es un álgebra booleana 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 completación de Dedekind-MacNeille de un retículo residuado es un retículo residuado completo. [ 16 ] Sin embargo, la completación de un retículo distributivo no tiene por qué ser distributiva, y la completación de un retículo modular puede no seguir siendo modular. [ 17 ]

La completación de Dedekind-MacNeille es autodual: la completación del dual de un orden parcial es la misma que el dual de la completación. [ 18 ]

La completación de 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, los retículos completos forman los objetos inyectivos para las incrustaciones de orden , y la completación de Dedekind-MacNeille de S es la envoltura inyectiva de S. [ 20 ] 

Algoritmos

Varios investigadores han estudiado algoritmos para construir la completación de Dedekind-MacNeille de un conjunto parcialmente ordenado finito. La completación de Dedekind-MacNeille puede ser exponencialmente mayor que el orden parcial del que proviene, [ 12 ] y los límites de tiempo para dichos algoritmos generalmente se expresan de 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 completación.

Construyendo el conjunto de cortes

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 completitud del orden parcial más pequeño se expande para formar la completitud del orden parcial más grande. En su método, la completitud 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 usar su método para añadir un solo elemento a la completitud 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 completitud de un orden parcial dado es O ( cn²w ) = O( cn³ ) . [ 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, el de enumerar todas las anticadenas maximales 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 se corresponden uno a uno con las anticadenas maximales en Q : los elementos en el conjunto inferior de un corte se corresponden con los elementos con subíndice 0 en una anticadena, y los elementos en el conjunto superior de un corte se corresponden con 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 listar todos los cortes en P , toma un tiempo O ( c ( nw + w 3 )) , una mejora del 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 grafo de comparabilidad de Q , o una camarilla máxima en el complemento del grafo de comparabilidad, por lo que los algoritmos para el problema de la camarilla o el problema del conjunto independiente también se pueden aplicar a esta versión del problema de completación de Dedekind-MacNeille. [ 22 ]

Construcción del grafo de cobertura

El grafo de reducción transitiva o grafo de recubrimiento de la completación de Dedekind-MacNeille describe la relación de orden entre sus elementos de forma 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 . Así, el grafo de recubrimiento tiene c vértices y como máximo cn /2 vecinos, un número que puede ser mucho menor que las c² entradas de una matriz que especifica todas las comparaciones por pares entre elementos. Nourine y Raynaud (1999) muestran cómo calcular este grafo de recubrimiento de forma eficiente; más generalmente, si B es cualquier familia de conjuntos, muestran cómo calcular el grafo de recubrimiento del retículo de uniones de subconjuntos de B. En el caso del retículo de Dedekind-MacNeille, B puede tomarse como la familia de conjuntos complementos 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 , formar su unión con todas las uniones generadas previamente), representar la familia de conjuntos resultante 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; esto toma un tiempo O ( cn² ) . 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 ]

Notas

  1. ↑ Davey y Priestley (2002 , pág. 166) ; Schröder (2003 , pág. 119) .  
  2. ↑ Romano (2007) .
  3. ↑ Schröder (2003) , definición 5.3.1, p. 119.
  4. ↑ O'Leary (2015) .
  5. ↑ Carpineto, Claudio; Romano, Giovanni (2004), Análisis de datos conceptuales: teoría y aplicaciones , John Wiley and Sons, pág.  10, ISBN 978-0-470-85055-8.
  6. 1 2 Bishop (1978) ; Schröder (2003) , Teorema 5.3.8, pág. 121.
  7. 1 2 MacNeille (1937) , Lema 11.8, pág. 444; Davey y Priestley (2002) , Lema 3.9(i), pág. 166.
  8. ↑ Esta es la definición utilizada originalmente por MacNeille (1937) , por ejemplo.
  9. 1 2 MacNeille (1937) .
  10. ↑ Davey y Priestley (2002) , Ejemplo 7.44(1), pág. 168; Schröder (2003) , Ejemplo 5.3.3(2), pág. 120.
  11. ↑ Davey y Priestley (2002) , Ejemplo 7.44(2), pág. 168.
  12. ^ Ganter y Kuznetsov ( 1998 ) .
  13. ↑ Schröder (2003) , Proposición 5.3.7, p. 121.
  14. ↑ Schmidt (1956) .
  15. ↑ Birkhoff (1995) , Teorema 27, pág. 130.
  16. ↑ Gabbay, Shehtman y Skvortsov (2009) .
  17. ↑ Cotlar (1944) ; Funayama (1944) .
  18. ↑ Birkhoff (1995) .
  19. ↑ Este resultado se atribuye frecuentemente a una tesis de honor inédita de 1961 de la Universidad de Harvard, escrita por KA Baker, titulada "Dimensión, independencia de unión y amplitud en conjuntos parcialmente ordenados". Fue publicada por Novák (1969) .
  20. ↑ Banaschewski y Bruns (1967) .
  21. ↑ Jourdan, Rampon y Jard (1994) .
  22. ↑ Para la equivalencia entre algoritmos para anticadenas en órdenes parciales y para conjuntos independientes en grafos de comparabilidad, véase Cameron (1985) , pág. 251.
  23. ↑ Nourine y Raynaud (2002) .

Referencias

  • Banaschewski, B.; Bruns, G. (1967), "Caracterización categórica de la completación de MacNeille", Archiv der Mathematik , 18 (4): 369–377 , doi : 10.1007/BF01898828 , MR 0221984 , S2CID 121216988  .
  • Birkhoff, Garrett (1995), "VI.9 Completación por cortes", Teoría de retículos , Publicaciones del Coloquio, vol.  25 (3.ª  ed.), Sociedad Matemática Americana, págs. 126–128 , ISBN  978-0-8218-1025-5.
  • Bishop, Alan A. (1978), "Una caracterización de mapeo universal de la completitud por cortes", Algebra Universalis , 8 (3): 349–353 , doi : 10.1007/bf02485405 , MR 0469839 , S2CID 121624631  .
  • Cameron, Kathie (1985), "Secuencias de anticadenas", Order , 2 (3): 249– 255, doi : 10.1007/BF00333130 , MR 0824698 
  • Cotlar, Mischa (1944), "Un método de construcción de estructuras y su aplicación a espacios topológicos y aritmética abstracta", Univ. Nac. Tucumán. Revista A. , 4 : 105– 157, MR 0014062 .
  • Davey, BA; Priestley, Hilary A. (2002), "7.38 La finalización de Dedekind–MacNeille" , Introducción a las redes y el orden (2.ª  ed.), Cambridge University Press , pág.  166, ISBN 978-0-521-78451-1, Zbl 1002.06001 .
  • Funayama, Nenosuke (1944), "Sobre la completitud mediante cortes de retículos distributivos", Actas de la Academia Imperial, Tokio , 20 : 1–2 , doi : 10.3792/pia/1195573210 , MR 0014063 , Zbl 0063.01484  .
  • Gabbay, Dov M.; Shehtman, Valentin; Skvortsov, Dimitrij (2009), "3.4.12 La completación de Dedekind-MacNeille de un retículo residuado", Cuantificación en lógica no clásica, Volumen 1 , Estudios en lógica y fundamentos de las matemáticas, vol.  153, Elsevier, pp. 177-178 , ISBN  978-0-444-52012-8, Zbl 1211.03002 .
  • Ganter, Bernhard; Kuznetsov, Sergei O. (1998), "Construcción por pasos de la completación de Dedekind-MacNeille", Actas de la 6.ª Conferencia Internacional sobre Estructuras Conceptuales: Teoría, Herramientas y Aplicaciones (ICCS98) , Lecture Notes in Computer Science, vol.  1453, Springer-Verlag, pp. 295–302 , doi : 10.1007/BFb0054922 , MR 1673860 , Zbl 0928.06004   .
  • Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), "Cálculo en línea de la retícula de anticadenas máximas de conjuntos parcialmente ordenados" (PDF) , Order , 11 (3): 197–210 , doi : 10.1007/BF02115811 , MR 1308475 , S2CID 120755660 , Zbl 0814.06004   .
  • MacNeille, HM (1937), "Conjuntos parcialmente ordenados", Transactions of the American Mathematical Society , 42 (3): 416– 460, doi : 10.2307/1989739 , JFM 63.0833.04 , JSTOR 1989739 , MR 1501929 , Zbl 0017.33904    .
  • Nourine, Lhouari; Raynaud, Olivier (1999), "Un algoritmo rápido para construir retículos", Information Processing Letters , 71 ( 5–6 ): 199–204 , CiteSeerX 10.1.1.502.3181 , doi : 10.1016/S0020-0190(99)00108-8 , MR 1726978 , Zbl 0998.06005   .
  • Nourine, Lhouari; Raynaud, Olivier (2002), "Un algoritmo incremental rápido para la construcción de retículos", Journal of Experimental and Theoretical Artificial Intelligence , 14 (2): 217– 227, doi : 10.1080/09528130210164152 , S2CID 38160433 , Zbl 1022.68027  .
  • Novák, Vítězslav (1969), "Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle", Mathematische Annalen , 179 : 337– 342, doi : 10.1007/BF01350778 , MR 0240010 , S2CID 120963245  .
  • O'Leary, Michael L. (2015), Un primer curso de lógica matemática y teoría de conjuntos , John Wiley & Sons, pág.  276, ISBN 978-0-470-90588-3
  • Roman, Steven (2007), Álgebra lineal avanzada , Textos de posgrado en matemáticas, vol.  135 (3.ª  ed.), Springer, pp. 10–11 , ISBN  978-0-387-72831-5
  • Schmidt, Jürgen (1956), "Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle", Archiv der Mathematik (en alemán), 7 : 241– 249, doi : 10.1007/BF01900297 , SEÑOR 0084484 
  • Schröder, Bernd SW (2003), "5.3 Incrustaciones/The Dedekind/MacNeille Completion", Conjuntos ordenados: Introducción , Birkhäuser, págs. 119-122 , ISBN  978-1-4612-6591-7.