En el área matemática de la teoría del orden , las propiedades de completitud afirman la existencia de ciertos ínfimos o supremos de un conjunto parcialmente ordenado (poset) dado. El ejemplo más conocido es la completitud de los números reales . Un uso especial del término se refiere a órdenes parciales completos o retículos completos . Sin embargo, existen muchas otras nociones interesantes de completitud.
La motivación para considerar las propiedades de completitud se deriva de la gran importancia de suprema (límites superiores mínimos, uniones , " ") e ínfima (límites inferiores máximos, encuentros , " ") para la teoría de órdenes parciales. Encontrar un supremo significa seleccionar un elemento menor distinguido del conjunto de límites superiores. Por un lado, estos elementos especiales a menudo incorporan ciertas propiedades concretas que son interesantes para la aplicación dada (como ser el mínimo común múltiplo de un conjunto de números o la unión de una colección de conjuntos). Por otro lado, el conocimiento de que ciertos tipos de subconjuntos están garantizados para tener suprema o ínfima nos permite considerar la evaluación de estos elementos como operaciones totales en un conjunto parcialmente ordenado. Por esta razón, los conjuntos parciales con ciertas propiedades de completitud a menudo pueden describirse como estructuras algebraicas de cierto tipo. Además, estudiar las propiedades de las operaciones recién obtenidas produce otros temas interesantes.
Todas las propiedades de completitud se describen siguiendo un esquema similar: una describe una cierta clase de subconjuntos de un conjunto parcialmente ordenado que deben tener un supremo o un ínfimo. Por lo tanto, cada propiedad de completitud tiene su dual , que se obtiene invirtiendo las definiciones dependientes del orden en el enunciado dado. Algunas de las nociones normalmente no están dualizadas, mientras que otras pueden ser autoduales (es decir, equivalentes a sus enunciados duales).
El ejemplo más sencillo de un supremo es el vacío, es decir, el supremo del conjunto vacío . Por definición, este es el elemento menor entre todos los elementos que son mayores que cada miembro del conjunto vacío. Pero este es solo el elemento menor de todo el conjunto parcial, si tiene uno, ya que el subconjunto vacío de un conjunto parcial P se considera convencionalmente acotado tanto por arriba como por abajo, siendo cada elemento de P un límite superior e inferior del subconjunto vacío. Otros nombres comunes para el elemento menor son inferior y cero (0). La noción dual, el límite inferior vacío, es el elemento mayor , superior o unidad (1).
Los conjuntos parciales que tienen un fondo se denominan a veces puntiagudos, mientras que los conjuntos parciales con un techo se denominan unitales o con techo. Un orden que tiene tanto un elemento mínimo como un elemento máximo está acotado. Sin embargo, esto no debe confundirse con la noción de completitud acotada que se presenta a continuación.
Otras condiciones de completitud simples surgen de la consideración de todos los conjuntos finitos no vacíos . Un orden en el que todos los conjuntos finitos no vacíos tienen tanto un supremo como un ínfimo se llama retículo . Basta con exigir que existan todos los supremos e ínfimos de dos elementos para obtener todos los finitos no vacíos; un argumento de inducción sencillo muestra que cada supremo/ínfimo finito no vacío se puede descomponer en un número finito de supremos/ínfimos binarios. Por lo tanto, las operaciones centrales de los retículos son los supremos e ínfimos binarios . Es en este contexto que los términos encontrarse para y unirse para son más comunes.
Por lo tanto, un conjunto parcial en el que solo se sabe que existen supremas finitas no vacías se denomina semirretículo de unión . La noción dual es semirretículo de encuentro .
La forma más fuerte de completitud es la existencia de todos los supremos y todos los ínfimos. Los conjuntos parciales con esta propiedad son los retículos completos . Sin embargo, utilizando el orden dado, se puede restringir a otras clases de subconjuntos (posiblemente infinitos) que no dan esta completitud fuerte de inmediato.
Si todos los subconjuntos dirigidos de un conjunto parcial tienen un supremo, entonces el orden es un orden parcial dirigido-completo (dcpo). Estos son especialmente importantes en la teoría de dominios . La noción dual de un dcpo, que rara vez se considera, es el conjunto parcial filtrado-completo. Los dcpos con un elemento mínimo ("dcpos puntiagudos") son uno de los posibles significados de la frase orden parcial completo (cpo).
Si cada subconjunto que tiene algún límite superior también tiene un límite superior mínimo, entonces el conjunto parcial respectivo se llama completo acotado . El término se usa ampliamente con esta definición que se centra en suprema y no hay un nombre común para la propiedad dual. Sin embargo, la completitud acotada se puede expresar en términos de otras condiciones de completitud que se dualizan fácilmente (ver más abajo). Aunque los conceptos con los nombres "completo" y "acotado" ya se definieron, es poco probable que se produzca confusión ya que rara vez se hablaría de un "conjunto parcial acotado completo" cuando se quiere decir un "cpo acotado" (que es simplemente un "cpo con el mayor elemento"). Del mismo modo, "retículo completo acotado" es casi inequívoco, ya que uno no enunciaría la propiedad de acotación para los retículos completos, donde está implícita de todos modos. Observe también que el conjunto vacío normalmente tiene límites superiores (si el conjunto parcial no está vacío) y, por lo tanto, un conjunto parcial acotado-completo tiene un mínimo de elementos.
También se pueden considerar los subconjuntos de un conjunto parcial que están totalmente ordenados , es decir, las cadenas . Si todas las cadenas tienen un supremo, el orden se denomina cadena completa . Nuevamente, este concepto rara vez se necesita en la forma dual.
Ya se observó que los encuentros/uniones binarios dan como resultado todos los encuentros/uniones finitos no vacíos. Asimismo, muchas otras (combinaciones) de las condiciones anteriores son equivalentes.
Como se explicó anteriormente, la presencia de ciertas condiciones de completitud permite considerar la formación de ciertos supremos e ínfimos como operaciones totales de un conjunto parcialmente ordenado. Resulta que en muchos casos es posible caracterizar la completitud únicamente considerando estructuras algebraicas apropiadas en el sentido del álgebra universal , que están equipadas con operaciones como o . Al imponer condiciones adicionales (en forma de identidades adecuadas ) a estas operaciones, uno puede entonces de hecho derivar el orden parcial subyacente exclusivamente a partir de tales estructuras algebraicas. Los detalles sobre esta caracterización se pueden encontrar en los artículos sobre las estructuras "similares a retículos" para las que esto se considera típicamente: ver semirretículo , retículo , álgebra de Heyting y álgebra de Boole . Nótese que las últimas dos estructuras extienden la aplicación de estos principios más allá de los meros requisitos de completitud al introducir una operación adicional de negación .
Otra forma interesante de caracterizar las propiedades de completitud se proporciona a través del concepto de conexiones de Galois (monótonas) , es decir, adjunciones entre órdenes parciales. De hecho, este enfoque ofrece conocimientos adicionales tanto sobre la naturaleza de muchas propiedades de completitud como sobre la importancia de las conexiones de Galois para la teoría del orden. La observación general en la que se basa esta reformulación de la completitud es que la construcción de ciertos suprema o ínfima proporciona partes adjuntas izquierdas o derechas de conexiones de Galois adecuadas.
Consideremos un conjunto parcialmente ordenado ( X , ≤). Como primer ejemplo simple, sea 1 = {*} un conjunto de un elemento especificado con el único ordenamiento parcial posible. Hay una aplicación obvia j : X → 1 con j ( x ) = * para todo x en X . X tiene un elemento menor si y solo si la función j tiene un adjunto inferior j * : 1 → X . De hecho, la definición de conexiones de Galois produce que en este caso j * (*) ≤ x si y solo si * ≤ j ( x ), donde el lado derecho obviamente se cumple para cualquier x . Dualmente, la existencia de un adjunto superior para j es equivalente a que X tenga un elemento mayor.
Otra aplicación sencilla es la función q : X → X × X dada por q ( x ) = ( x , x ). Naturalmente, la relación de ordenación prevista para X × X es simplemente el orden de producto habitual . q tiene un adjunto inferior q * si y solo si existen todas las uniones binarias en X. A la inversa, la operación de unión : X × X → X siempre puede proporcionar el adjunto inferior (necesariamente único) para q . Dualmente, q permite un adjunto superior si y solo si X tiene todos los encuentros binarios. Por lo tanto, la operación de encuentro , si existe, siempre es un adjunto superior. Si existen y y, además, también es un adjunto inferior, entonces el conjunto poset X es un álgebra de Heyting , otra clase especial importante de órdenes parciales.
Se pueden obtener más afirmaciones de completitud explotando procedimientos de completitud adecuados . Por ejemplo, es bien sabido que la colección de todos los conjuntos inferiores de un conjunto poset X , ordenados por inclusión de subconjuntos , produce una red completa D ( X ) (la red downset). Además, hay una incrustación obvia e : X → D ( X ) que asigna cada elemento x de X a su ideal principal { y en X | y ≤ x }. Una pequeña reflexión ahora muestra que e tiene un adjunto inferior si y solo si X es una red completa. De hecho, este adjunto inferior asignará cualquier conjunto inferior de X a su supremo en X . Al componer este adjunto inferior con la función que asigna cualquier subconjunto de X a su clausura inferior (de nuevo una adjuntación para la inclusión de conjuntos inferiores en el conjunto potencia ), se obtiene la función de supremo habitual del conjunto potencia 2 X a X . Como antes, se produce otra situación importante siempre que esta función suprema sea también adjunta superior: en este caso, la red completa X es constructivamente completamente distributiva . Véanse también los artículos sobre distributividad completa y distributividad (teoría del orden) .
Las consideraciones de esta sección sugieren una reformulación de (partes de) la teoría del orden en términos de la teoría de categorías , donde las propiedades se expresan habitualmente haciendo referencia a las relaciones ( morfismos , más específicamente: adjunciones) entre objetos, en lugar de considerar su estructura interna. Para consideraciones más detalladas de esta relación, véase el artículo sobre la formulación categórica de la teoría del orden.
