Completar orden parcial

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 juegan un papel central en la informática teórica: en la semántica denotacional y la teoría de dominios.

Definiciones

Una orden parcial completa, abreviada cpo, puede hacer referencia a cualquiera de los siguientes conceptos según el contexto.

• Un conjunto parcialmente ordenado es un orden parcial completo ()dcpo) si cada uno de sus subconjuntos dirigidos tiene un supremum. Un subconjunto de orden parcial se dirige si no es 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 poset completo.

• Un conjunto parcialmente ordenado es un orden parcial completo si es un dcpo con un elemento menos. A veces se abrevian cppos.

• Un conjunto parcialmente ordenado es un Orden parcial completa ()ω-cpo) si es una pose en la que cada cadena ω (x₁ ≤ x₂ ≤ x₃ ≤ x₄ ≤...) tiene un supremum que pertenece a la pose. Cada dcpo es un ω-cpo, ya que cada ω-chain es un conjunto dirigido, pero el converso no es cierto. Sin embargo, cada ω-cpo con base es también un dcpo (con la misma base). Un ω-cpo (dcpo) con una base también se llama a continuo ω-cpo (continuous dcpo).

Tenga en cuenta que orden parcial completo nunca se utiliza para referirse a un poset en el que todos los subconjuntos tienen suprema; Para este concepto se utiliza la terminología celosía completa.

El requisito de la existencia de suprema dirigida puede estar motivado viendo los conjuntos dirigidos como secuencias de aproximación generalizadas y la suprema como límites de los respectivos cálculos (aproximativos). Esta intuición, en el contexto de la semántica denotacional, fue la motivación detrás del desarrollo de la teoría de dominio.

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

Ejemplos

• Cada pose finita está dirigida completa.
• Todas las rejillas completas también están dirigidas completas.
• Para cualquier pose, el conjunto de todos los filtros no vacíos, ordenado por la inclusión del subconjunto, es un dcpo. Junto con el filtro vacío también se apunta. Si el pedido tiene reuniones binarias, entonces esta construcción (incluyendo el filtro vacío) realmente produce una celosía completa.
• Cada conjunto S se puede convertir en un dcpo apuntado añadiendo un elemento menos ⊥ e introduciendo un orden plano con ≤ ≤s y s ≤s para todos s dentro S y ninguna otra relación de orden.
• El conjunto de todas las funciones parciales en un determinado conjunto S puede ser ordenado por definición f≤g si g extensivos f, es decir, si el dominio de f es un subconjunto del dominio de g y los valores de f y g acuerda todos los insumos para los cuales ambos están definidos. (Equivalentemente, f≤g si f⊆g Donde f y g son identificados con sus respectivos gráficos.) Este orden es un dcpo puntiagudo, donde el elemento menos es la función parcial no definida (con dominio vacío). De hecho, ≤ también está atado completo. Este ejemplo también demuestra por qué no siempre es natural tener un elemento más grande.
• 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, utilicemos, por ejemplo, el enfoque algebraico de Alfred Tarski). Hay teoremas interesantes que conciernen a un conjunto de sistemas deductivos siendo un orden parcial completo dirigido. Además, se puede elegir un conjunto de sistemas deductivos para tener un elemento mínimo de manera natural (para que también pueda ser un dcpo puntiagudo), porque el conjunto de todas las consecuencias del conjunto vacío (es decir, “el conjunto de las oraciones lógicamente provables/lógicamente válidas”) es (1) un sistema deductivo (2) contenido por todos los sistemas deductivos.

Propiedades

Un conjunto ordenado P es un dcpo puntiagudo si y sólo si cada cadena tiene un supremo en P, es decir, P es cadena- completo. Alternativamente, un conjunto ordenado P es un dcpo puntiagudo si y sólo si cada automapa de P que conserva el orden tiene un punto fijo mínimo.

Funciones continuas y puntos fijos

Una función f entre dos dcpos P y Q se llama (Scott) continua si se asigna de forma dirigida. conjuntos a conjuntos dirigidos conservando su supremacía:

• ${displaystyle f(D)subseteq Q}$ se dirige a cada dirección ${displaystyle Dsubseteq P}$.
• ${displaystyle f(sup D)=sup f(D)}$ por cada dirección ${displaystyle Dsubseteq P}$.

Tenga en cuenta que cada 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 dcpos P y Q se denota [P → Q]. Equipado con el orden puntual, esto es nuevamente un dcpo, y un cpo siempre que Q sea un cpo. Así, los órdenes parciales completos con mapas continuos de Scott forman una categoría cartesiana cerrada.

Cada automapa f que conserva el orden de un cpo (P, ⊥) tiene un punto mínimo fijo. Si f es continuo, entonces este punto fijo es igual al supremo de las iteraciones (⊥, f (⊥), f (f (⊥)), … fⁿ(⊥), …) de ⊥ (ver también el Kleene fijo- teorema del punto).