Completitud (teoría del orden)

En el área matemática de la teoría del orden, la propiedad de completitud afirma la existencia de ciertos elementos ínfimo o supremo de un conjunto parcialmente ordenado (también denominado poset, abreviatura del término inglés "partial ordered set") determinado. El ejemplo más familiar es el axioma del supremo. Un uso especial del término se refiere al orden parcial completo o retículo completo. 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 los elementos supremo (límite superior mínimo, junta, "$\vee$") e ínfimo (límites inferiores máximos, encuentro, "$\wedge$") para la teoría de órdenes parciales. Encontrar un supremo significa seleccionar un elemento mínimo 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 se garantiza que ciertos tipos de subconjuntos tienen supremo o ínfimo permite considerar la evaluación de estos elementos como operaciones totales en un conjunto parcialmente ordenado. Por esta razón, los conjuntos parcialmente ordenados con ciertas propiedades de completitud a menudo pueden describirse como cierto tipo de estructuras algebraicas. Además, el estudio de las propiedades de las operaciones recién obtenidas ofrece otros temas interesantes.​

Tipos de propiedades de completitud

Todas las propiedades de completitud se describen siguiendo un esquema similar: se describe una cierta clase de subconjuntos de un conjunto parcialmente ordenado que deben tener un supremo o un mínimo. Por lo tanto, cada propiedad de completitud tiene su dual, que se obtiene invirtiendo las definiciones dependientes del orden en la declaración dada. Algunas de las nociones no suelen estar dualizadas, mientras que otras pueden ser autoduales (es decir, equivalentes a sus enunciados duales).

Elementos menores y mayores

El ejemplo más sencillo de 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 menor elemento de todo el conjunto parcialmente ordenado, si lo tiene, ya que convencionalmente se considera que el subconjunto vacío de un conjunto parcialmente ordenado P está acotado tanto desde arriba como desde abajo, con cada elemento de P siendo un límite superior e inferior del subconjunto vacío. Otros nombres comunes para el elemento mínimo 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 parcialmente ordenados que tienen una parte inferior a veces se llaman puntiagudos,​ mientras que los conjuntos parcialmente ordenados con una parte superior se llaman unitarios o rematados.​ Un orden que tiene un elemento menor y mayor es acotado. Sin embargo, esto no debe confundirse con la noción de completitud limitada que se presenta a continuación.

Completitud finita

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 mínimo se llama retículo. Basta con exigir que existan tanto el elemento supremo como el ínfimo de cualquier pareja de elementos para concluir que todos son finitos no vacíos.​ Un sencillo argumento de inducción muestra que cada supremo/ínfimo finito no vacío se puede descomponer en un número finito de supremos/infimos binario. Por lo tanto, las operaciones centrales de los retículos​ son el supremo binario $\vee$ y el ínfimo binario $\wedge$. Es en este contexto en el que los términos encuentro para $\wedge$ y junta para $\vee$ son más comunes.

Por lo tanto, un conjunto parcialmente ordenado en el que solo se sabe que existe un supremo finito no vacío se llama semirretículo de junta. La noción dual es el semirretículo de encuentro.​

Otras condiciones de completitud

La forma más fuerte de completitud es la existencia de todos los supremos y de todos los ínfimos. Los conjuntos parcialmente ordenados con esta propiedad son los denominados retículos completos. Sin embargo, utilizando el orden dado, se puede restringir a otras clases de subconjuntos (posiblemente infinitos) que no produzcan esta fuerte completitud de inmediato.

Si todos los subconjuntos dirigidos de un conjunto parcialmente ordenado tienen un supremo, entonces el orden es un orden parcial dirigido completo (opdc).​ Estos son especialmente importantes en teoría de dominios. La noción dual rara vez considerada para un opdc es el conjunto parcialmente ordenado completo filtrado. Los opdc con un elemento mínimo ("opdc puntiagudos") son uno de los posibles significados de la frase orden parcial completo (opc).

Si cada subconjunto que tiene algún límite superior tiene también un límite superior mínimo, entonces el conjunto parcialmente ordenado respectivo se llama completo acotado. El término se usa ampliamente con esta definición que se centra en el supremo y no existe 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 (véase más abajo). Aunque los conceptos con los nombres "completo" y "acotado" ya estaban definidos, es poco probable que se produzca confusión, ya que rara vez se hablaría de un "conjunto parcialmente ordenado completo acotado" cuando se quiere decir un "opc acotado" (que es simplemente un "opc con un elemento mayor"). Asimismo, el concepto de "red completa acotada" es casi inequívoco, ya que no se establecería la propiedad de acotación para retículos completos, donde de todos modos está implícita. También debe tenerse en cuenta que el conjunto vacío generalmente tiene límites superiores (si el conjunto parcialmente ordenado no está vacío) y, por lo tanto, un conjunto parcialmente ordenado completo acotado tiene un elemento mínimo.

También se pueden considerar los subconjuntos de un conjunto parcialmente ordenado que están totalmente ordenados, es decir, las cadenas. Si todas las cadenas tienen un supremo, el orden se llama orden parcial completo.​ Nuevamente, este concepto rara vez se necesita en su forma dual.

Relaciones entre propiedades de completitud

Ya se ha observado que los encuentros/juntas binarios producen todos los encuentros/juntas finitos no vacíos. Asimismo, muchas otras (combinaciones) de las condiciones anteriores son equivalentes.​

• El ejemplo más conocido es la existencia de todos los supremos, que de hecho equivale a la existencia de todos los ínfimos. De hecho, para cualquier subconjunto X de un conjunto parcialmente ordenado, se puede considerar su conjunto de límites inferiores B. El supremo de B es entonces igual al mínimo de X: dado que cada elemento de X es un límite superior de B, el sup B es menor que todos los elementos de X, es decir, sup B está en B. Es el elemento mayor de B y, por lo tanto, el mínimo de X. De manera dual, la existencia de todos los ínfimos implica la existencia de todos los supremos.
• La completitud acotada también se puede caracterizar de manera diferente. Mediante un argumento similar al anterior, se encuentra que el supremo de un conjunto con límites superiores es el mínimo del conjunto de límites superiores. En consecuencia, la completitud limitada es equivalente a la existencia de todos los ínfimos no vacíos.
• Un conjunto parcialmente ordenado es un retículo completo si y solo si, es un orden parcial completo y un semirretículo de junta. De hecho, para cualquier subconjunto X, el conjunto de todos los supremos (juntas) finitos de X es dirigido, y el supremo de este conjunto (que existe por la completitud dirigida) es igual al supremo de X. Así, todo conjunto tiene un supremo y, según la observación anterior, se tiene un retículo completo. La otra dirección de la prueba es trivial.
• Asumiendo el axioma de elección, un conjunto parcialmente ordenado es una cadena completa si y solo si es un orden parcial dirigido completo.

Completitud en términos del álgebra universal

Como se explicó anteriormente, la presencia de determinadas 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 una estructura algebraica apropiada en el sentido del álgebra universal,​ equipada con operaciones como $\vee$ o $\wedge$. Al imponer condiciones adicionales (en forma de identidades adecuadas) a estas operaciones, se puede deducir 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 normalmente se consideran las condiciones detalladas en los artículos siguientes: retículo, semirretículo, álgebra de Heyting y álgebra booleana. Obsérvese que las dos últimas 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.

Completitud en términos de complementos

Otra forma interesante de caracterizar las propiedades de completitud se proporciona a través del concepto de conexiones de Galois (monótonas), es decir, conjunciones 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 supremos o ínfimos proporciona partes adjuntas izquierda o derecha de conexiones Galois adecuadas.​

Considérese un conjunto parcialmente ordenado (X, ≤). Como primer ejemplo simple, sea 1 = {*} un conjunto especificado de un elemento con el único orden parcial posible. Hay una asignación j obvia: X → 1 con j(x) = * para todo x en X. X tiene un elemento mínimo 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 es válido para cualquier x. Dualmente, la existencia de un adjunto superior para j equivale a que X tenga un elemento mayor.

Otra aplicación simple es la función q: X → X × X dada por q(x) = (x , X). Naturalmente, la relación de orden prevista para X × X es simplemente el orden del producto habitual. q tiene un adjunto inferior q^* si y solo si existen todas las juntas binarias en X. Por el contrario, la operación de junta $\vee$: X × X → X siempre puede proporcionar el adjunto inferior (necesariamente único) para q. Dualmente, q admite un adjunto superior si y solo si X tiene todos los encuentros binarios. Por tanto, la operación de encuentro $\wedge$, si existe, siempre es un adjunto superior. Si existen tanto $\vee$ como $\wedge$ y, además, $\wedge$ también es un adjunto inferior, entonces el conjunto parcialmente ordenado X es un álgebra de Heyting, otra clase especial importante de órdenes parciales.​

Se pueden obtener más declaraciones de completitud explotando los procedimientos de completación adecuados. Por ejemplo, es bien sabido que la colección de todos los conjuntos inferiores de un conjunto parcialmente ordenado X, ordenados por la relación de inclusión de subconjuntos, produce un retículo completo D(X) (un retículo descendente). Además, hay una inclusió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 muestra ahora que e tiene un adjunto inferior si y solo si X es un retículo completo. 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 cierre inferior (nuevamente un complemento de la inclusión de conjuntos inferiores en el conjunto potencia), se obtiene la aplicación del supremo habitual del conjunto de potencias 2^X a X.​ Como antes, otra situación importante se produce siempre que esta aplicación del supremo es también un adjunto superior: en este caso, el retículo completo X es constructivamente completamente distributivo. Consúltense también los artículos sobre distributividad completa y distributividad (teoría del orden).

Las consideraciones en 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 generalmente se expresan haciendo referencia a las relaciones (morfismos, más específicamente: adjunciones) entre objetos, en lugar de considerar su estructura interna.

Véase también

• Retículo completamente distributivo
• Función de preservación de límites sobre la preservación del supremo/ínfimo existente.
• Orden total

Bibliografía

• G. Markowsky and B.K. Rosen. Bases for chain-complete posets IBM Journal of Research and Development. March 1976.
• Stephen Bloom. Varieties of ordered algebras Journal of Computer and System Sciences. October 1976.
• Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
• Daniel Lehmann. On the algebra of order Journal of Computer and System Sciences. August 1980.

• Datos: Q5156540