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 particulares de completitud . Los órdenes parciales completos desempeñan un papel central en la informática teórica : en la semántica denotacional y 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 orden parcial completo dirigido ( dcpo ) si cada uno de sus subconjuntos dirigidos tiene un supremo . (Un subconjunto de un orden parcial está dirigido si no está vacío y cada par de elementos tiene un límite superior en el subconjunto). En la literatura, dcpos a veces también aparece bajo la etiqueta up-complete poset .

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

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

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

Tenga en cuenta que el 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 .

Requerir 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 orden parcial completo dirigido se denomina orden parcial completo filtrado . 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.

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

Ejemplos

• Todo poset finito está dirigido completo.
• Todas las celosías completas también están dirigidas en su totalidad.
• Para cualquier poset, el conjunto de todos los filtros no vacíos , ordenados por inclusión de subconjunto , es un dcpo. Junto con el filtro vacío también está apuntado. Si el orden tiene encuentros binarios , entonces esta construcción (incluido el filtro vacío) en realidad produce una red completa .
• Cada conjunto S se puede convertir en un dcpo puntiagudo 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 algún conjunto S dado se puede ordenar definiendo f  ≤  g si y sólo 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 todas las entradas para las que ambas están definidas. (Equivalentemente, f  ≤  g si y solo si f  ⊆  g donde f y g se identifican con sus respectivas gráficas ). Este orden es un dcpo puntiagudo, donde el elemento mínimo es la función parcial no definida en ninguna parte (con dominio vacío). De hecho, ≤ también está acotado completo . Este ejemplo también demuestra por qué no siempre es natural tener el elemento más grande.
• 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.
• 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 ordenamiento parcial completo y dirigido. ^[5] Además, se puede elegir que un conjunto de sistemas deductivos tenga un elemento mínimo de forma natural (de modo 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 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 sólo si toda cadena no vacía tiene un supremo. Como corolario, un conjunto ordenado es un dcpo puntiagudo si y sólo si toda cadena (posiblemente vacía) tiene un supremo, es decir, si y sólo si es una cadena completa . ^{[1] [6] [7] [8]} Las pruebas se basan en el axioma de elección .

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

Funciones continuas y puntos fijos

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

• ${\displaystyle f(D)\subseteq Q}$está dirigido para cada dirigido . ${\displaystyle D\subseteq P}$
• ${\displaystyle f(\sup D)=\sup f(D)}$por cada dirigido . ${\displaystyle D\subseteq 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 cerrada cartesiana . ^[9]

Cada automapa f que conserva el orden de un cpo ( P , ⊥) tiene un punto mínimo fijo. ^[10] Si f es continua entonces este punto fijo es igual al supremo de los iterados (⊥, f  (⊥), f  ( f  (⊥)), … f ⁿ (⊥), …) de ⊥ (ver 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 todos , entonces tiene un punto fijo. Este teorema, a su vez, puede utilizarse para demostrar que el lema de Zorn es consecuencia del axioma de elección. ^{[11] [12]} ${\displaystyle f}$ ${\displaystyle f(x)\geq x}$ ${\displaystyle x}$ ${\displaystyle f}$

Ver 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, posets algebraicos y la topología de Scott .

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

Notas

1. Markowsky, George (1976), "Posets de cadena completa y conjuntos dirigidos 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: Prensa de Clarendon. Proposición 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. Ver en línea en la p. 24 ejercicios 5–6 del §5 en [1]. O, en papel, consulte 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 y Row. pag. 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 , Holanda Septentrional (1984)
10. Ver teorema de Knaster-Tarski ; Los fundamentos de la verificación de programas, segunda edición, Jacques Loeckx y Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4 , Capítulo 4; El teorema de Knaster-Tarski, formulado sobre cpo, se demuestra en el ejercicio 4.3-5 de 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, Licenciatura en Letras; Priestley, HA (2002). Introducción a las celosías y al orden (Segunda ed.). Prensa de la Universidad de Cambridge. ISBN 0-521-78451-4.