En matemáticas , un retículo completo es un conjunto parcialmente ordenado en el que todos los subconjuntos tienen tanto un supremo ( join ) como un ínfimo ( meet ). Un retículo condicionalmente completo satisface al menos una de estas propiedades para subconjuntos acotados. A modo de comparación, en un retículo general , solo los pares de elementos necesitan tener un supremo y un ínfimo. Todo retículo finito no vacío es completo, pero los retículos infinitos pueden ser incompletos.
Los retículos completos aparecen en muchas aplicaciones de las matemáticas y la informática . Tanto la teoría del orden como el álgebra universal los estudian como una clase especial de retículos.
Los retículos completos no deben confundirse con los órdenes parciales completos (CPO), una clase más general de conjuntos parcialmente ordenados. Los retículos completos más específicos son las álgebras de Boole completas y las álgebras de Heyting completas (locales). [ cita requerida ]
Una red completa es un conjunto parcialmente ordenado ( L , ≤) tal que cada subconjunto A de L tiene tanto un límite inferior máximo (el ínfimo o encuentro ) como un límite superior mínimo (el supremo o unión ) en ( L , ≤).
El encuentro se denota por , y la unión por .
En el caso especial en que A es el conjunto vacío , el punto de encuentro de A es el mayor elemento de L. Asimismo, el punto de encuentro del conjunto vacío es el menor elemento de L. Entonces, los retículos completos forman una clase especial de retículos acotados .
Una subred M de una red completa L se denomina subred completa de L si para cada subconjunto A de M los elementos y , tal como se definen en L , están realmente en M . [1]
Si el requisito anterior se reduce para requerir que solo los encuentros y uniones no vacíos estén en M , la subred M se denomina subred cerrada de L.
Los términos semirretículo de encuentro completo o semirretículo de unión completo son otra forma de referirse a retículos completos, ya que los encuentros arbitrarios se pueden expresar en términos de uniones arbitrarias y viceversa (para más detalles, consulte completitud ).
Otro uso de "semilattice de encuentro completo" se refiere a un semirretículo de encuentro que es completo y acotado y un orden parcial completo . Este concepto es posiblemente la noción "más completa" de un semirretículo de encuentro que aún no es un retículo (de hecho, solo puede faltar el elemento superior).
Ver semirredes para una discusión más detallada entre ambas definiciones.
Se dice que una red es " condicionalmente completa " si satisface una o ambas de las siguientes propiedades: [2]
Se dice que un retículo completo L es localmente finito si el supremo de cualquier subconjunto infinito es igual al elemento supremo. Denotando este elemento supremo "1", la condición es equivalente a que el conjunto sea finito para cualquier . Esta notación puede entrar en conflicto con otra notación, como en el caso del retículo ( N , |), es decir, los números enteros no negativos ordenados por divisibilidad . En este retículo localmente finito, el elemento infimo denotado "0" para la teoría de retículos es el número 1 en el conjunto N y el elemento supremo denotado "1" para la teoría de retículos es el número 0 en el conjunto N .
Los morfismos tradicionales entre retículos completos, tomando los retículos completos como los objetos de una categoría , son los homomorfismos completos (u homomorfismos de retículo completo ). Estos se caracterizan por ser funciones que conservan todas las uniones y todos los encuentros. Explícitamente, esto significa que una función f: L→M entre dos retículos completos L y M es un homomorfismo completo si
para todos los subconjuntos A de L . Tales funciones son automáticamente monótonas , pero la condición de ser un homomorfismo completo es de hecho mucho más específica. Por esta razón, puede ser útil considerar nociones más débiles de morfismos, como aquellas que solo se requieren para preservar todas las uniones (dando una categoría Sup ) o todos los encuentros (dando una categoría Inf ), que son de hecho condiciones no equivalentes. Estas nociones también pueden considerarse como homomorfismos de semirretículos de encuentro completos o semirretículos de unión completos, respectivamente.
Además, los morfismos que preservan todas las uniones se caracterizan de manera equivalente como la parte adjunta inferior de una conexión de Galois única . Para cualquier par de preórdenes X e Y , una conexión de Galois está dada por un par de funciones monótonas f y g de X a Y tales que para cada par de elementos x de X e y de Y
donde f se denomina adjunto inferior y g se denomina adjunto superior . Por el teorema del funtor adjunto , una función monótona entre cualquier par de preórdenes conserva todas las uniones si y solo si es un adjunto inferior y conserva todos los encuentros si y solo si es un adjunto superior.
Como tal, cada morfismo que preserva las uniones determina un único adjunto superior en la dirección inversa que preserva todos los encuentros. Por lo tanto, considerar retículos completos con morfismos de semirretículo completos (de cualquier tipo, que preservan las uniones o que preservan los encuentros) se reduce a considerar las conexiones de Galois como los morfismos de retículo de uno. Esto también produce la idea de que las tres clases de morfismos discutidas anteriormente básicamente describen solo dos categorías diferentes de retículos completos: uno con homomorfismos completos y otro con conexiones de Galois que capturan tanto las funciones que preservan los encuentros (adjuntos superiores) como sus aplicaciones duales que preservan las uniones (adjuntos inferiores).
Una clase particularmente importante de casos especiales surge entre redes de subconjuntos de X e Y , es decir, los conjuntos potencia y , dada una función de X a Y . En estos casos, los mapas de imagen directa e imagen inversa inducidos por entre los conjuntos potencia son adjuntos superiores e inferiores entre sí, respectivamente.
La construcción de objetos libres depende de la clase de morfismos elegida. Las funciones que conservan todas las uniones (es decir, las conexiones de Galois adjuntas inferiores) se denominan semirretículos de unión completos libres .
La definición estándar del álgebra universal establece que una red completa libre sobre un conjunto generador es una red completa junto con una función , de modo que cualquier función desde hasta el conjunto subyacente de alguna red completa se puede factorizar de forma única mediante un morfismo desde hasta . Esto significa que para cada elemento de , y ese es el único morfismo con esta propiedad. Por lo tanto, hay un funtor desde la categoría de conjuntos y funciones hasta la categoría de redes completas y funciones que preservan la unión que es adjunto izquierdo al funtor olvidadizo desde redes completas hasta sus conjuntos subyacentes.
De este modo, se pueden construir redes completas libres de modo que la red completa generada por algún conjunto sea simplemente el conjunto potencia , el conjunto de todos los subconjuntos de ordenados por inclusión de subconjuntos . La unidad requerida asigna cualquier elemento de al conjunto singleton . Dado un mapeo como el anterior, la función se define por
Luego transforma las uniones en supremas y así preserva las uniones.
Estas consideraciones también producen una construcción libre para morfismos que preservan encuentros en lugar de uniones (es decir, adjuntos superiores de conexiones de Galois). Lo anterior se puede dualizar : los objetos libres se dan como conjuntos de potencia ordenados por inclusión inversa, de modo que la unión de conjuntos proporciona la operación de encuentro, y la función se define en términos de encuentros en lugar de uniones. El resultado de esta construcción se conoce como semirretículo de encuentro completo libre . Se puede notar que estas construcciones libres extienden aquellas que se usan para obtener semirretículos libres , donde se deben considerar conjuntos finitos.
La situación de los retículos completos con homomorfismos completos es más intrincada. De hecho, los retículos completos libres generalmente no existen. Por supuesto, se puede formular un problema verbal similar al del caso de los retículos , pero la colección de todas las palabras (o "términos") posibles en este caso sería una clase propia , porque las reuniones y uniones arbitrarias comprenden operaciones para conjuntos de argumentos de cada cardinalidad .
Esta propiedad en sí no es un problema: como muestra el caso de los semirretículos completos libres antes mencionado, bien puede ser que la solución del problema verbal deje solo un conjunto de clases de equivalencia. En otras palabras, es posible que las clases propias de todos los términos tengan el mismo significado y, por lo tanto, se identifiquen en la construcción libre. Sin embargo, las clases de equivalencia para el problema verbal de los retículos completos son "demasiado pequeñas", de modo que el retículo completo libre seguiría siendo una clase propia, lo cual no está permitido.
Ahora bien, todavía se podría esperar que existan algunos casos útiles en los que el conjunto de generadores sea lo suficientemente pequeño como para que exista una red libre y completa. Desafortunadamente, el límite de tamaño es muy bajo y tenemos el siguiente teorema:
Johnstone da una prueba de esta afirmación. [3] El argumento original se atribuye a Alfred W. Hales ; [4] véase también el artículo sobre redes libres .
Si se genera libremente un retículo completo a partir de un conjunto parcial dado que se utiliza en lugar del conjunto de generadores considerados anteriormente, entonces se habla de una compleción del conjunto parcial. La definición del resultado de esta operación es similar a la definición anterior de objetos libres, donde los "conjuntos" y las "funciones" se reemplazan por "conjuntos parciales" y "asignaciones monótonas". De la misma manera, se puede describir el proceso de compleción como un funtor desde la categoría de conjuntos parciales con funciones monótonas hasta alguna categoría de retículos completos con morfismos apropiados que se dejan adjuntos al funtor olvidadizo en la dirección inversa.
Siempre que se consideren las funciones que preservan el encuentro o la unión como morfismos, esto se puede lograr fácilmente a través del llamado proceso de compleción Dedekind-MacNeille . Para este proceso, los elementos del conjunto parcial se asignan a cortes (Dedekind) , que luego se pueden asignar a los conjuntos parciales subyacentes de redes completas arbitrarias de la misma manera que se hizo para los conjuntos y las redes (semi)completas libres mencionadas anteriormente.
El resultado antes mencionado de que no existen retículos completos libres implica que tampoco es posible una construcción libre correspondiente a partir de un conjunto parcial. Esto se ve fácilmente al considerar conjuntos parciales con un orden discreto, donde cada elemento solo se relaciona consigo mismo. Estos son exactamente los conjuntos parciales libres en un conjunto subyacente. Si existiera una construcción libre de retículos completos a partir de conjuntos parciales, entonces ambas construcciones podrían estar compuestas, lo que contradice el resultado negativo anterior.
El libro Lattice Theory de G. Birkhoff contiene un método de representación muy útil. Asocia un retículo completo a cualquier relación binaria entre dos conjuntos mediante la construcción de una conexión de Galois a partir de la relación, lo que luego conduce a dos sistemas de clausura dualmente isomorfos . [5] Los sistemas de clausura son familias de conjuntos cerrados por intersección. Cuando se ordenan por la relación de subconjunto ⊆, son retículos completos.
Un ejemplo especial de la construcción de Birkhoff parte de un conjunto arbitrario (P,≤) y construye la conexión de Galois a partir de la relación de orden ≤ entre P y sí mismo. El retículo completo resultante es la compleción de Dedekind-MacNeille . Cuando esta compleción se aplica a un conjunto que ya es un retículo completo, entonces el resultado es isomorfo al original. Así, encontramos inmediatamente que todo retículo completo está representado por el método de Birkhoff, salvo isomorfismo.
La construcción se utiliza en el análisis formal de conceptos , donde se representan datos del mundo real mediante relaciones binarias (llamadas contextos formales ) y se utilizan los retículos completos asociados (llamados retículos conceptuales ) para el análisis de datos. Por lo tanto, las matemáticas detrás del análisis formal de conceptos son la teoría de retículos completos.
Otra representación se obtiene de la siguiente manera: un subconjunto de una red completa es en sí mismo una red completa (cuando está ordenada con el orden inducido) si y sólo si es la imagen de una autoaplicación creciente e idempotente (pero no necesariamente extensiva). La aplicación identidad tiene estas dos propiedades. Por lo tanto, se dan todas las redes completas.
Además de los resultados de representación anteriores, hay otras afirmaciones que se pueden hacer sobre redes completas, o que toman una forma particularmente simple en este caso. Un ejemplo es el teorema de Knaster-Tarski , que establece que el conjunto de puntos fijos de una función monótona en una red completa es a su vez una red completa. Se ve fácilmente que esto es una generalización de la observación anterior sobre las imágenes de funciones crecientes e idempotentes.
