En matemáticas , una red completa es un conjunto parcialmente ordenado en el que todos los subconjuntos tienen tanto un supremo (unión) como un mínimo (encuentro). Una red que satisface al menos una de estas propiedades se conoce como red condicionalmente completa . A modo de comparación, en una red general , sólo los pares de elementos necesitan tener un supremo y un mínimo. Toda red finita no vacía está completa, pero las redes infinitas pueden estar incompletas.
Las redes completas aparecen en muchas aplicaciones en matemáticas e informática . Al ser un caso especial de celosías , se estudian tanto en teoría del orden como en álgebra universal .
Las redes completas no deben confundirse con los órdenes parciales completos ( cpo s), que constituyen una clase estrictamente más general de conjuntos parcialmente ordenados. Las redes completas más específicas son las álgebras booleanas completas y las álgebras completas de Heyting ( locales ).
Un conjunto parcialmente ordenado ( L , ≤) es una red completa si cada subconjunto A de L tiene un límite inferior máximo (el mínimo , también llamado encuentro ) y un límite superior mínimo (el supremo , también llamado unión ) en ( L , ≤).
El encuentro se denota por y la unión por .
En el caso especial donde A es el conjunto vacío , el encuentro de A será el mayor elemento de L. Asimismo, la unión del conjunto vacío produce el menor elemento . Dado que la definición también asegura la existencia de encuentros y uniones binarias, las redes completas forman una clase especial de redes acotadas .
En el artículo sobre propiedades de completitud en la teoría del orden se analizan más implicaciones de la definición anterior .
En la teoría del orden, las reuniones arbitrarias se pueden expresar en términos de uniones arbitrarias y viceversa (para más detalles, consulte integridad (teoría del orden) ). En efecto, esto significa que es suficiente requerir la existencia de todos los encuentros o de todas las uniones para obtener la clase de todas las redes completas.
Como consecuencia, algunos autores utilizan los términos semiretícula de encuentro completo o semiretícula de unión completa como otra forma de referirse a celosías completas. Aunque similares en objetos, los términos implican diferentes nociones de homomorfismo , como se explicará en la siguiente sección sobre morfismos.
Por otro lado, algunos autores no utilizan esta distinción de morfismos (especialmente porque los conceptos emergentes de "morfismos semirreticulares completos" también pueden especificarse en términos generales). En consecuencia, las semirrejillas de encuentro completas también se han definido como aquellas semirrejillas de encuentro que también son órdenes parciales completas . Este concepto es posiblemente la noción "más completa" de una semirretícula de encuentro que aún no es una red (de hecho, es posible que solo falte el elemento superior). Esta discusión también se encuentra en el artículo sobre semiredes .
Una subred M de una red completa L se llama subred completa de L si para cada subconjunto A de M los elementos y , como se define en L , están realmente en M. [1]
Si el requisito anterior se reduce para requerir que solo las reuniones y uniones no vacías estén en M , la subred M se llama subred cerrada de L.
Se dice que una red es " condicionalmente completa " si satisface una o ambas de las siguientes propiedades: [2]
Se dice que una red completa L es localmente finita si el supremo de cualquier subconjunto infinito es igual a 1, o equivalentemente, el conjunto es finito para cualquier . La red ( N , |) es localmente finita. En esta red, el elemento generalmente denominado "0" es en realidad 1 y viceversa.
Los morfismos tradicionales entre redes completas son los homomorfismos completos (u homomorfismos de red completos ). Éstas se caracterizan por ser funciones que preservan todas las uniones y todas las reuniones. Explícitamente, esto significa que una función f: L→M entre dos redes completas 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, que solo se requieren para preservar todas las uniones (dando una categoría Sup ) o todos los encuentros (dando una categoría Inf ), que de hecho son condiciones no equivalentes. Esta noción puede considerarse como un homomorfismo de semirrejillas de encuentro completas o semirrejillas de unión completas, 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 pedidos anticipados P y Q , estos están dados por pares de funciones monótonas f y g tales que
donde f se llama adjunto inferior y g se llama adjunto superior . Según el teorema del functor adjunto , un mapa monótono entre cualquier par de pedidos anticipados conserva todas las uniones si y sólo si es un adjunto inferior, y conserva todos los encuentros si y sólo si es un adjunto superior.
Como tal, cada morfismo que preserva la unión determina un adjunto superior único en la dirección inversa que preserva todas las coincidencias. Por lo tanto, considerar redes completas con morfismos de semired completos se reduce a considerar las conexiones de Galois como morfismos. Esto también produce la idea de que los morfismos introducidos básicamente describen solo dos categorías diferentes de redes completas: una con homomorfismos completos y otra con funciones que preservan las reuniones (adjuntos superiores), duales a la que tiene asignaciones que preservan las uniones (adjuntos inferiores).
Un caso especial particularmente importante es el de las redes de subconjuntos P(X) y P(Y) y una función de X a Y. En este caso, los mapas de imagen directa e imagen inversa entre los conjuntos de potencia son adjuntos superior e inferior entre sí, respectivamente.
Como es habitual, la construcción de objetos libres depende de la clase de morfismos elegida. Consideremos primero funciones que preservan todas las uniones (es decir, adjuntos inferiores de conexiones de Galois), ya que este caso es más simple que la situación para homomorfismos completos. Usando la terminología antes mencionada, esto podría denominarse semirrejilla de unión completa y libre .
Usando la definición estándar del álgebra universal , una red completa libre sobre un conjunto generador S es una red completa L junto con una función i : S → L , tal que cualquier función f desde S hasta el conjunto subyacente de alguna red completa M puede ser factorizado únicamente a través de un morfismo f ° de L a M . Dicho de otra manera, para cada elemento s de S encontramos que f ( s ) = f °( i ( s )) y que f ° es el único morfismo con esta propiedad. Básicamente, estas condiciones equivalen a decir que 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 se deja adjunto al funtor olvidadizo desde las redes completas hasta sus conjuntos subyacentes.
En este sentido, se pueden construir muy fácilmente redes completas libres: la red completa generada por algún conjunto S es simplemente el conjunto potencia 2 S , es decir, el conjunto de todos los subconjuntos de S , ordenados por inclusión de subconjuntos . La unidad requerida i : S →2 S asigna cualquier elemento s de S al conjunto singleton { s }. Dada una aplicación de f como la anterior, la función f °:2 S → M se define por
Entonces f ° transforma las uniones en supremas y así preserva las uniones.
Nuestras 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). De hecho, simplemente tenemos que dualizar lo que se dijo anteriormente: los objetos libres se dan como conjuntos de potencias ordenados por inclusión inversa, de modo que la unión de conjuntos proporciona la operación de encuentro, y la función f ° se define en términos de encuentros en lugar de uniones. El resultado de esta construcción podría denominarse un encuentro-semirrejilla libre y completo . También hay que señalar cómo estas construcciones libres extienden las que se utilizan para obtener semiredes libres , donde sólo necesitamos considerar conjuntos finitos.
La situación para redes completas con homomorfismos completos es obviamente más compleja. De hecho, generalmente no existen redes completas libres. Por supuesto, se puede formular un problema similar al del caso de las redes , pero la colección de todas las palabras (o "términos") posibles en este caso sería una clase adecuada , porque los encuentros y uniones arbitrarios comprenden operaciones para el argumento. -conjuntos de cada cardinalidad .
Esta propiedad en sí misma no es un problema: como muestra el caso de semiredes completas libres anterior, 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 la clase de todos los términos tengan el mismo significado y, por tanto, se identifiquen en la construcción libre. Sin embargo, las clases de equivalencia para el problema verbal de redes completas son "demasiado pequeñas", de modo que la red completa libre seguiría siendo una clase adecuada, lo cual no está permitido.
Ahora bien, todavía se podría esperar que haya algunos casos útiles en los que el conjunto de generadores sea lo suficientemente pequeño como para que exista una red completa y libre. 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] ver también el artículo sobre celosías libres .
Si se genera libremente una red completa a partir de un poset dado utilizado en lugar del conjunto de generadores considerados anteriormente, entonces se habla de una finalización del poset. La definición del resultado de esta operación es similar a la definición anterior de objetos libres, donde "conjuntos" y "funciones" se reemplazan por "posets" y "mapeos monótonos". Asimismo, se puede describir el proceso de finalización como un funtor de la categoría de posets con funciones monótonas a alguna categoría de redes completas con morfismos apropiados que se deja junto al funtor olvidadizo en la dirección inversa.
Siempre que se consideren las funciones que preservan encuentros o uniones como morfismos, esto se puede lograr fácilmente mediante la llamada terminación de Dedekind-MacNeille . Para este proceso, los elementos del poset se asignan a cortes (Dedekind-) , que luego se pueden asignar a los posets subyacentes de redes completas arbitrarias de manera muy similar a como se hace para los conjuntos y (semi)redes completas libres anteriores.
El resultado mencionado anteriormente de que no existen redes completas libres implica que tampoco es posible una construcción libre correspondiente a partir de un poset. Esto se ve fácilmente al considerar posets con un orden discreto, donde cada elemento sólo se relaciona consigo mismo. Estos son exactamente los posets libres en un conjunto subyacente. Si se construyeran libremente redes completas a partir de posets, entonces se podrían componer ambas construcciones, lo que contradice el resultado negativo anterior.
El libro Lattice Theory de G. Birkhoff [5] [ página necesaria ] ya contiene un método de representación muy útil. Asocia una red completa a cualquier relación binaria entre dos conjuntos mediante la construcción de una conexión de Galois a partir de la relación, que luego conduce a dos sistemas de cierre dualmente isomórficos . Los sistemas de cierre son familias de conjuntos cerradas en intersección. Cuando están ordenados por la relación de subconjunto ⊆, son redes completas.
Un ejemplo especial de la construcción de Birkhoff parte de un poset arbitrario (P,≤) y construye la conexión de Galois a partir de la relación de orden ≤ entre P y él mismo. La red completa resultante es la terminación de Dedekind-MacNeille . Cuando esta terminación se aplica a un poset que ya es una red completa, entonces el resultado es isomorfo al original. Así encontramos inmediatamente que cada red completa está representada por el método de Birkhoff, hasta el isomorfismo.
La construcción se utiliza en el análisis de conceptos formales , donde se representan datos de palabras reales mediante relaciones binarias (llamadas contextos formales ) y se utilizan las redes completas asociadas (llamadas redes de conceptos ) para el análisis de datos. Por lo tanto, la matemática detrás del análisis formal de conceptos es la teoría de redes completas.
Otra representación se obtiene de la siguiente manera: un subconjunto de una red completa es en sí misma una red completa (cuando está ordenada con el orden inducido) si y sólo si es la imagen de un automapa creciente e idempotente (pero no necesariamente extenso). El mapeo de identidad obviamente tiene estas dos propiedades. Así se producen todas las redes completas.
Además de los resultados de la representación anterior, se pueden hacer algunas otras afirmaciones sobre redes completas, o que en este caso toman una forma particularmente simple. 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 nuevamente 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, ya que son ejemplos del teorema.
