Completar pedido parcial

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

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

Un conjunto parcialmente ordenado es un orden parcial 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 una cota superior en el subconjunto). En la literatura, los dcpos a veces también aparecen bajo la etiqueta de poset up-completo .

Un orden parcial completo dirigido con punto ( dcpo con punto , a veces abreviado cppo ), es un dcpo con un elemento mínimo (generalmente denotado${\displaystyle \bot }$Dicho de otra forma, un dcpo con punto tiene un supremo para cada subconjunto dirigido o vacío . También se utiliza el término orden parcial completo en cadena , debido a la caracterización de los dcpos con punto como posets en los que cada cadena tiene un supremo.

Una noción relacionada es la de orden parcial ω-completo ( ω-cpo ). Estos son conjuntos parcialmente ordenados en los que cada ω-cadena (${\displaystyle x_{1}\leq x_{2}\leq x_{3}\leq ...}$) tiene un supremo que pertenece al poset. La misma noción puede extenderse a otras cardinalidades de cadenas. ^{[ 1 ]}

Todo dcpo es un ω-cpo, puesto que toda ω-cadena es un conjunto dirigido, pero lo contrario 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).

Cabe señalar que el orden parcial completo nunca se utiliza para referirse a un conjunto parcialmente ordenado en el que todos los subconjuntos tienen supremos; para este concepto se utiliza la terminología de retículo completo .

La exigencia de la existencia de supremas dirigidas puede justificarse al considerar los conjuntos dirigidos como secuencias de aproximación generalizadas y 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 .

La noción dual de un orden parcial completo dirigido se denomina orden parcial completo filtrado . Sin embargo, este concepto aparece con mucha menos frecuencia en la práctica, ya que normalmente se puede trabajar explícitamente con el orden dual.

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

• Todo conjunto parcialmente ordenado finito es completo dirigido.
• Todas las redes completas son también completas dirigidas.
• Para cualquier poset, 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 apuntado. Si el orden tiene coincidencias binarias , entonces esta construcción (incluido el filtro vacío) produce en realidad un retículo completo .
• Cada conjunto S puede convertirse en un dcpo apuntado agregando un elemento mínimo ⊥ 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 un conjunto S dado se puede ordenar definiendo f  ≤ g si y solo si g extiende a f , es decir, si el dominio de f es un subconjunto del dominio de g y los valores de f y g coinciden en todas las entradas para las que ambas están definidas. (De forma equivalente, f ≤ g si y solo si f ⊆ g, donde f y g se identifican con sus respectivos grafos ). Este orden es un dcpo con punto, donde el elemento menor es la función parcial no definida en ninguna parte (con dominio vacío). De hecho, ≤ también es acotado completo . 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 sobre una colección de conjuntos no vacíos , ordenadas por restricción.
• El conjunto de todos los ideales primordiales de un anillo , ordenados por inclusión.
• El orden de especialización de cualquier espacio sobrio es un dcpo.
• Usemos el término " sistema deductivo " como un conjunto de oraciones cerradas bajo consecuencia (para definir la noción de consecuencia, usemos, 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 orden parcial dirigido-completo. ^{[ 5 ] [ 3 ]} Además, un conjunto de sistemas deductivos puede elegirse de manera natural para tener un elemento mínimo (de modo que también pueda 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.

( Teorema de Markowsky ) Un conjunto ordenado es un dcpo si y solo si es completo en cadena; es decir, toda cadena no vacía tiene un supremo.

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

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

Una función f entre dos conjuntos dirigidos P y Q se denomina continua (de Scott) si mapea conjuntos dirigidos a conjuntos dirigidos conservando sus supremos:

• ${\displaystyle f(D)\subsetequq Q}$está dirigido para cada dirigido${\displaystyle D\subsetequ P}$.
• ${\displaystyle f(\sup D)=\sup f(D)}$para cada dirigido${\displaystyle D\subsetequ 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 , esto es nuevamente un dcpo, y apunta siempre que Q sea apuntado. Por lo tanto, los órdenes parciales completos con aplicaciones continuas de Scott forman una categoría cartesiana cerrada . ^{[ 9 ]} 

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

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

• conjuntos parcialmente ordenados algebraicos
• Topología de Scott
• Lo completo
• Teorema de Markowsky

• Davey, BA; Priestley, HA (2002). Introducción a las redes y el orden (Segunda  edición). Cambridge University Press. ISBN 0-521-78451-4.