Integridad (teoría del orden) - Completeness (order theory)

En el área matemática de la teoría del orden , las propiedades de completitud afirman la existencia de ciertos infima o suprema de un determinado conjunto parcialmente ordenado (poset). El ejemplo más conocido es la integridad de los números reales . Un uso especial del término se refiere a órdenes parciales completas o celosías completas . Sin embargo, existen muchas otras nociones interesantes de completitud.

La motivación para considerar las propiedades de completitud deriva de la gran importancia de suprema (menores límites superiores, uniones , " ") e infima (mayores límites inferiores, encuentros " ") para la teoría de órdenes parciales. Encontrar un supremo significa distinguir 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 ciertos tipos de subconjuntosestán garantizados para tener suprema o infima nos permite considerar el cálculo de estos elementos como operaciones totales en un conjunto parcialmente ordenado. Por esta razón, los posets con ciertas propiedades de completitud a menudo pueden describirse como estructuras algebraicas de cierto tipo. Además, el estudio de las propiedades de las operaciones recién obtenidas arroja otros temas interesantes.

Tipos de propiedades de completitud

Todas las propiedades de completitud se describen a lo largo de un esquema similar: uno describe una cierta clase de subconjuntos de un conjunto parcialmente ordenado que se requiere para tener un supremum o un infimum. Por tanto, toda propiedad de completitud tiene su dual , que se obtiene invirtiendo las definiciones dependientes del orden en el enunciado dado. Algunas de las nociones generalmente no están dualizadas, mientras que otras pueden ser auto-duales (es decir, equivalentes a sus declaraciones duales).

Elementos menores y mayores

El ejemplo más fácil de supremum es el vacío, es decir, el supremum 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 poset, si tiene uno, ya que el subconjunto vacío de un poset P se considera convencionalmente como acotado tanto desde arriba como desde abajo, siendo cada elemento de P un límite superior e inferior del subconjunto vacío. Otros nombres comunes para el elemento mínimo son bottom y zero (0). La noción dual, el límite inferior vacío, es el elemento , la parte superior o la unidad más grande (1).

Las poses que tienen una parte inferior a veces se denominan puntiagudas, mientras que las poses con una parte superior se denominan unitales o rematadas. Un orden que tiene tanto un elemento menor como uno mayor está acotado. Sin embargo, esto no debe confundirse con la noción de completitud limitada que se da a continuación.

Completitud finita

Otras condiciones simples de completitud 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 supremum como un infimum se llama reticulado . Basta exigir que existan todos los supremos e infima de dos elementos para obtener todos los finitos no vacíos; un argumento de inducción sencillo muestra que cada supremum / infimum finito no vacío se puede descomponer en un número finito de supremum / infimum binarios. Así, las operaciones centrales de las celosías son suprema e infima binarios . Es en este contexto donde los términos reunirse para y unirse para son más comunes.

Por lo tanto, un poset en el que solo se sabe que existen supremas finitos no vacíos se denomina unión-semirrejilla . La noción dual es encuentro-semirreticulado .

Condiciones adicionales de integridad

La forma más fuerte de completitud es la existencia de todo suprema y todo infima. Los posets con esta propiedad son las celosías completas . Sin embargo, usando el orden dado, uno puede restringir a más clases de subconjuntos (posiblemente infinitos), que no producen esta completa completitud a la vez.

Si todos los subconjuntos dirigidos de un poset 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 rara vez considerada de un dcpo es el poset completo filtrado. 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 poset respectivo se llama acotado completo . El término se usa ampliamente con esta definición que se enfoca en suprema y no existe un nombre común para la propiedad dual. Sin embargo, la completitud limitada 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 estaban definidos, es poco probable que se produzca confusión ya que rara vez se habla de un "poset completo acotado" cuando se refiere a un "cpo acotado" (que es solo un "cpo con el elemento más grande "). Del mismo modo, "retículo completo acotado" es casi inequívoco, ya que no se indicaría la propiedad de delimitación para retículos completos, donde está implícita de todos modos. También tenga en cuenta que el conjunto vacío generalmente tiene límites superiores (si el poset no está vacío) y, por lo tanto, un poset completo acotado tiene un elemento mínimo.

También se pueden considerar los subconjuntos de un poset que están totalmente ordenados , es decir, las cadenas . Si todas las cadenas tienen un supremo, el pedido se llama cadena completa . Una vez más, este concepto rara vez se necesita en la forma dual.

Relaciones entre propiedades de completitud

Ya se ha observado que las reuniones / combinaciones binarias producen todas las reuniones / combinaciones finitas no vacías. Asimismo, muchas otras (combinaciones) de las condiciones anteriores son equivalentes.

  • El ejemplo más conocido es la existencia de todo suprema, que de hecho es equivalente a la existencia de todo infima, siempre que exista un fondo. De hecho, para cualquier subconjunto X de un poset, se puede considerar su conjunto de límites inferiores B , que no está vacío ya que contiene al menos la parte inferior. El extremo superior de B es entonces igual a la infimum de X : ya que cada elemento de X es un límite superior de B , sup  B es menor que todos los elementos de X , es decir, sup  B está en B . Es el mayor elemento de B y por lo tanto el ínfimo de X . De manera dual, la existencia de todos los infima implica la existencia de todo suprema.
  • La completitud limitada 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 equivale a la existencia de todos los infima no vacíos.
  • Un poset es un entramado completo si y solo si es un cpo y un semirremolque de unión. De hecho, para cualquier subconjunto X , el conjunto de todos suprema finito (se une) de X se dirige y el supremo de este conjunto (que existe por completo dirigida) es igual al supremo de X . Por lo tanto, cada conjunto tiene un supremo y, según la observación anterior, tenemos una red completa. La otra dirección de la demostración es trivial.
  • Suponiendo el axioma de elección , un poset es una cadena completa si y solo si es un dcpo.

Completitud en términos de álgebra universal

Como se explicó anteriormente, la presencia de ciertas condiciones de completitud permite considerar la formación de ciertos supremos e infima 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, entonces se puede 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 "enrejados" para los cuales esto se considera típicamente: ver semirreticulado , celosía , álgebra de Heyting y álgebra booleana . Tenga en cuenta que las dos últimas estructuras amplían la aplicación de estos principios más allá de los simples requisitos de integridad al introducir una operación adicional de negación .

Completitud en términos de adjuntos

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

Considere un conjunto parcialmente ordenado ( X , ≤). Como primer ejemplo simple, supongamos que 1 = {*} sea un conjunto de un elemento especificado con el único orden parcial posible. Hay una cartografía obvio j : X → 1 con j ( x ) = * para todos los x en X . X tiene un elemento menos si y sólo si la función J tiene un adjunto inferior j * : 1 → X . De hecho, la definición de conexiones de Galois da como resultado 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.

Otro mapeo simple es la función q : X → X × X dada por q ( x ) = ( x , x ). Naturalmente, la relación de pedido prevista para X × X es solo el pedido de producto habitual . q tiene un adjunto menor 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 todas las coincidencias binarias. Por tanto, la operación de encuentro , si existe, siempre es un adjunto superior. Si ambos y existen y, además, también es un adjunto inferior, entonces el poset X es un álgebra de Heyting, otra clase especial importante de órdenes parciales.

Se pueden obtener más declaraciones de integridad mediante la explotación de procedimientos de finalización adecuados. Por ejemplo, es bien sabido que la colección de todos los conjuntos inferiores de un poset X , ordenados por inclusión de subconjuntos , produce un retículo D ( X ) completo (el retículo descendente). Además, hay una incrustación obvia e : X → D ( X ) que mapea 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 más bajo si y solo si X es una red completa. De hecho, este adjunto inferior será asignar cualquier conjunto inferior de X a su supremo en X . Composición de esto con la función que mapea cualquier subconjunto de X a su cierre inferior (de nuevo la contigüidad para la inclusión de conjuntos inferiores en el powerset ), se obtiene el mapa supremo habitual desde el powerset 2 X a X . Como antes, se produce otra situación importante siempre que este mapa superior también sea un adjunto 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 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. Para consideraciones más detalladas de esta relación, consulte el artículo sobre la formulación categórica de la teoría del orden .

Ver también

Notas


Referencias

  • G. Markowsky y BK Rosen. Bases para posets completos en cadena IBM Journal of Research and Development. Marzo de 1976.
  • Stephen Bloom. Variedades de álgebras ordenadas Journal of Computer and System Sciences. Octubre de 1976.
  • Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
  • Daniel Lehmann. Sobre el álgebra de orden Journal of Computer and System Sciences. Agosto de 1980.