Pedido parcial completo

En matemáticas , la frase orden parcial completo se utiliza de diversas formas para referirse a al menos tres clases similares, pero distintas, de conjuntos parcialmente ordenados , caracterizados por propiedades de completitud particulares . Los órdenes parciales completos desempeñan un papel central en la informática teórica : en la semántica denotacional y en la teoría de dominios .

Definiciones

El término orden parcial completa , abreviado cpo , tiene varios significados posibles según el contexto.

Un conjunto parcialmente ordenado es un conjunto parcial de orden dirigido-completo ( dcpo ) si cada uno de sus subconjuntos dirigidos tiene un supremo . (Un subconjunto de un orden parcial es dirigido si no está vacío y cada par de elementos tiene un límite superior en el subconjunto). En la literatura, los dcpos a veces también aparecen bajo la etiqueta de conjunto parcial completo-arriba .

Un orden parcial completo dirigido puntiagudo ( pointed dcpo , a veces abreviado cppo ), es un dcpo con un elemento menor (usualmente denotado como ). Formulado de otra manera, un dcpo puntiagudo tiene un supremo para cada subconjunto dirigido o vacío . El término orden parcial completo en cadena también se utiliza, debido a la caracterización de los dcpos puntiagudos como conjuntos parciales en los que cada cadena tiene un supremo. ${\displaystyle \bot }$

Un concepto relacionado es el de orden parcial ω-completo ( ω-cpo ). Se trata de conjuntos parciales en los que cada cadena ω ( ) tiene un supremo que pertenece al conjunto parcial. El mismo concepto puede extenderse a otras cardinalidades de cadenas. ^[1] ${\displaystyle x_{1}\leq x_{2}\leq x_{3}\leq ...}$

Todo dcpo es un ω-cpo, ya que toda ω-cadena es un conjunto dirigido, pero lo inverso no es cierto. Sin embargo, todo ω-cpo con una base es también un dcpo (con la misma base). ^[2] Un ω-cpo (dcpo) con una base también se denomina ω-cpo continuo (o dcpo continuo).

Téngase en cuenta que el orden parcial completo nunca se utiliza para referirse a un conjunto parcial en el que todos los subconjuntos tienen supremacía; se utiliza la terminología red completa para este concepto.

La exigencia de la existencia de supremas dirigidas puede estar motivada por la consideración de los conjuntos dirigidos como secuencias de aproximación generalizadas y de las supremas como límites de los respectivos cálculos (aproximados). Esta intuición, en el contexto de la semántica denotacional, fue la motivación detrás del desarrollo de la teoría de dominios .

El concepto dual de un orden parcial dirigido-completo se denomina orden parcial filtrado-completo . Sin embargo, este concepto se da con mucha menos frecuencia en la práctica, ya que normalmente se puede trabajar con el orden dual de forma explícita.

Por analogía con la compleción de Dedekind-MacNeille de un conjunto parcialmente ordenado, cada conjunto parcialmente ordenado puede extenderse de forma única hasta un dcpo mínimo. ^[1]

Ejemplos

• Cada conjunto finito está dirigido y completo.
• Todas las redes completas también están dirigidas de forma completa.
• Para cualquier conjunto parcial, el conjunto de todos los filtros no vacíos , ordenados por inclusión de subconjuntos , es un dcpo. Junto con el filtro vacío, también es puntiagudo. Si el orden tiene combinaciones binarias , entonces esta construcción (incluido el filtro vacío) en realidad produce un retículo completo .
• Cada conjunto S puede convertirse en un dcpo puntiagudo añadiendo un elemento menor ⊥ e introduciendo un orden plano con ⊥ ≤  s y s ≤  s para cada s en S y ninguna otra relación de orden.
• El conjunto de todas las funciones parciales en algún conjunto dado S se puede ordenar definiendo f  ≤  g si y solo si g extiende f , es decir, si el dominio de f es un subconjunto del dominio de g y los valores de f y g concuerdan en todas las entradas para las que ambos están definidos. (Equivalentemente, f  ≤  g si y solo si f  ⊆  g donde f y g se identifican con sus respectivos gráficos ). Este orden es un dcpo puntiagudo, donde el menor elemento es la función parcial no definida en ninguna parte (con dominio vacío). De hecho, ≤ también es completo acotado . Este ejemplo también demuestra por qué no siempre es natural tener un elemento mayor.
• El conjunto de todos los subconjuntos linealmente independientes de un espacio vectorial V , ordenados por inclusión .
• El conjunto de todas las funciones de elección parcial en una colección de conjuntos no vacíos , ordenados por restricción.
• El conjunto de todos los ideales primos de un anillo , ordenados por inclusión.
• El orden de especialización de cualquier espacio sobrio es un dcpo.
• Utilicemos el término " sistema deductivo " como un conjunto de oraciones cerradas bajo consecuencia (para definir la noción de consecuencia, utilicemos, por ejemplo, el enfoque algebraico de Alfred Tarski ^{[3] [4]} ). Hay teoremas interesantes que se refieren a un conjunto de sistemas deductivos que son un ordenamiento parcial dirigido-completo. ^[5] Además, un conjunto de sistemas deductivos puede elegirse para que tenga un mínimo de elementos de forma natural (de modo que también puede ser un dcpo apuntado), porque el conjunto de todas las consecuencias del conjunto vacío (es decir, "el conjunto de las oraciones lógicamente demostrables/lógicamente válidas") es (1) un sistema deductivo (2) contenido por todos los sistemas deductivos.

Caracterizaciones

Un conjunto ordenado es un dcpo si y solo si cada cadena no vacía tiene un supremo. Como corolario, un conjunto ordenado es un dcpo puntiagudo si y solo si cada cadena (posiblemente vacía) tiene un supremo, es decir, si y solo si es de cadena completa . ^{[1] [6] [7] [8]} Las demostraciones se basan en el axioma de elección .

Alternativamente, un conjunto ordenado es un dcpo puntiagudo si y solo si cada automapa que preserva el orden de tiene un punto fijo mínimo . ${\displaystyle P}$ ${\displaystyle P}$

Funciones continuas y puntos fijos

Una función f entre dos puntos de derivada P y Q se llama (Scott) continua si asigna conjuntos dirigidos a conjuntos dirigidos mientras preserva su supremacía:

• ${\displaystyle f(D)\subseteq Q}$está dirigido para cada dirigido . ${\displaystyle D\subseteq P}$
• ${\displaystyle f(\sup D)=\sup f(D)}$para cada dirigido . ${\displaystyle D\subseteq P}$

Nótese que toda función continua entre dcpos es una función monótona . Esta noción de continuidad es equivalente a la continuidad topológica inducida por la topología de Scott .

El conjunto de todas las funciones continuas entre dos dcpo P y Q se denota [ P  →  Q ]. Equipado con el orden puntual , este es nuevamente un dcpo, y apuntado siempre que Q sea apuntado. Por lo tanto, los órdenes parciales completos con aplicaciones Scott-continuas forman una categoría cartesiana cerrada . ^[9]

Toda automapa que preserva el orden f de un dcpo puntiagudo ( P , ⊥) tiene un punto fijo mínimo. ^[10] Si f es continua, entonces este punto fijo es igual al supremo de los iterados (⊥, f  (⊥), f  ( f  (⊥)), … f ⁿ (⊥), …) de ⊥ (véase también el teorema del punto fijo de Kleene ).

Otro teorema del punto fijo es el teorema de Bourbaki-Witt , que establece que si es una función de un dcpo a sí mismo con la propiedad de que para todo , entonces tiene un punto fijo. Este teorema, a su vez, puede utilizarse para demostrar que el lema de Zorn es una consecuencia del axioma de elección. ^{[11] [12]} ${\displaystyle f}$ ${\displaystyle f(x)\geq x}$ ${\displaystyle x}$ ${\displaystyle f}$

Véase también

La completitud dirigida por sí sola es una propiedad bastante básica que ocurre a menudo en otras investigaciones de teoría del orden, utilizando por ejemplo conjuntos algebraicos y la topología de Scott .

La completitud dirigida se relaciona de diversas maneras con otras nociones de completitud, como la completitud de la cadena .

Notas

1. Markowsky, George (1976), "Conjuntos de conjuntos dirigidos y conjuntos de conjuntos completos en cadena con aplicaciones", Algebra Universalis , 6 (1): 53–68, doi :10.1007/bf02485815, MR  0398913, S2CID  16718857
2. Abramsky S , Gabbay DM , Maibaum TS (1994). Manual de lógica en informática, volumen 3. Oxford: Clarendon Press. Prop 2.2.14, págs. 20. ISBN 9780198537625.
3. Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (El título significa: Prueba y verdad / Artículos seleccionados).
4. Stanley N. Burris y HP Sankappanavar: Un curso de álgebra universal
5. Véase en línea en la pág. 24 los ejercicios 5–6 del §5 en [1]. O, en papel, véase Tar:BizIg.
6. Goubault-Larrecq, Jean (23 de febrero de 2015). "Lema de Iwamura, teorema de Markowsky y ordinales" . Consultado el 6 de enero de 2024 .
7. Cohn, Paul Moritz. Álgebra universal . Harper and Row. pág. 33.
8. Goubault-Larrecq, Jean (28 de enero de 2018). «¿Markowsky o Cohn?» . Consultado el 6 de enero de 2024 .
9. Barendregt, Henk , El cálculo lambda, su sintaxis y semántica Archivado el 23 de agosto de 2004 en Wayback Machine , North-Holland (1984)
10. Este es un fortalecimiento del teorema de Knaster-Tarski , a veces denominado "teorema de Pataraia". Por ejemplo, véase la Sección 4.1 de "Realizability at Work: Separating Two Constructive Notions of Finiteness" (2016) de Bezem et al. Véase también el Capítulo 4 de The foundations of program checking (1987), 2.ª edición, Jacques Loeckx y Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4 , donde se presenta el teorema de Knaster-Tarski, formulado sobre dcpo puntiagudos, para demostrarlo como ejercicio 4.3-5 en la página 90. 
11. Bourbaki, Nicolas (1949), "Sur le théorème de Zorn", Archiv der Mathematik , 2 (6): 434–437 (1951), doi :10.1007/bf02036949, MR  0047739, S2CID  117826806.
12. Witt, Ernst (1951), "Beweisstudien zum Satz von M. Zorn", Mathematische Nachrichten , 4 : 434–438, doi :10.1002/mana.3210040138, SEÑOR  0039776.

Referencias

• Davey, BA; Priestley, HA (2002). Introducción a los retículos y el orden (segunda edición). Cambridge University Press. ISBN 0-521-78451-4.