De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En matemáticas , la frase orden parcial completo se usa 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 juegan un papel central en la informática teórica : en la semántica denotacional y la teoría de dominios .

Definiciones

Un orden parcial completo abreviado cpo puede, según el contexto, hacer referencia a cualquiera de los siguientes conceptos.

  • 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 se dirige 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 aparecen bajo la etiqueta up-complete poset .
  • Un conjunto parcialmente ordenado es un orden parcial dirigido-completo puntiagudo si es un dcpo con un elemento mínimo. A veces se abrevian cppo s.
  • Un conjunto parcialmente ordenado es un ω-orden parcial completo ( ω-cpo ) si es un conjunto en el que cada ω-cadena ( x 1 ≤ x 2 ≤ x 3 ≤ x 4 ≤ ...) tiene un supremo que pertenece a el conjunto subyacente del poset. Cada dcpo es un ω-cpo, ya que cada ω-cadena es un conjunto dirigido, pero lo contrario no es cierto. Sin embargo, cada ω-cpo con una base también es un dcpo (con la misma base). [1] Un ω-CPO (DCPO) con una base también se llama un continuo ω-CPO (DCPO continua).

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

Exigir la existencia de suprema dirigido puede ser motivado por ver los conjuntos dirigidos como secuencias de aproximación generalizadas y suprema como límites de los cálculos respectivos (aproximados). Esta intuición, en el contexto de la semántica denotacional, fue la motivación detrás del desarrollo de la teoría del dominio .

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

Ejemplos

  • Cada poset finito se dirige completo.
  • Todas las celosías completas también se dirigen completas.
  • 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 se apunta. Si el orden tiene encuentros binarios , entonces esta construcción (incluido el filtro vacío) en realidad produce un enrejado completo .
  • El conjunto de todas las funciones parciales en algún conjunto dado S se puede ordenar definiendo f  ≤  g para las funciones f y g si y solo si g extiende f , es decir, si el dominio de f es un subconjunto del dominio de gy los valores de f y g coinciden en todas las entradas para las que se definen ambas funciones. (De manera equivalente, f  ≤  g si y solo si f  ⊆  g donde f y g se identifican con sus respectivosgráficos .) Este orden es un dcpo puntiagudo, donde el elemento mínimo es la función 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 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, usemos, por ejemplo , el enfoque algebraico de Alfred Tarski [2] [3] ). Hay teoremas interesantes que se refieren a un conjunto de sistemas deductivos que son un ordenamiento parcial dirigido-completo. [4] Además, un conjunto de sistemas deductivos puede elegirse para tener un elemento mínimo de forma natural (de modo que también puede 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.

Propiedades

Un conjunto ordenado P es un dcpo puntiagudo si y solo si cada cadena tiene un supremo en P , es decir, P es una cadena completa . [5] Alternativamente, un conjunto ordenado P es un dcpo puntiagudo si y solo si cada automapa de P que conserva el orden tiene un punto fijo mínimo . Cada conjunto S se puede convertir en un dcpo puntiagudo agregando un elemento mínimo ⊥ e introduciendo un orden plano con ⊥ ≤  sy s ≤  s para cada s  ∈  S y ninguna otra relación de orden.

Funciones continuas y puntos fijos

Una función f entre dos dcpos P y Q se llama (Scott) continua si mapea conjuntos dirigidos a conjuntos dirigidos conservando su suprema:

  • está dirigido para cada dirigido .
  • por cada dirigido .

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 . [6]

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

Ver también

La completitud dirigida se relaciona de diversas formas con otras nociones de completitud , como la completitud de la cadena . La completitud dirigida por sí sola es una propiedad bastante básica que ocurre a menudo en otras investigaciones de la teoría del orden, utilizando, por ejemplo, posets algebraicos y la topología de Scott .

Notas

  1. ^ Abramsky S , Gabbay DM , Maibaum TS (1994). Manual de Lógica en Ciencias de la Computación, volumen 3 . Oxford: Clarendon Press. Prop 2.2.14, págs. 20. ISBN 9780198537625.
  2. ↑ 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).
  3. ^ Stanley N. Burris y HP Sankappanavar: un curso de álgebra universal
  4. ^ Ver en línea en la p. 24 ejercicios 5-6 del §5 en [1] . O, en papel, consulte Tar: BizIg .
  5. ^ Markowsky, George (1976), "Posets completos en cadena y conjuntos dirigidos con aplicaciones", Algebra Universalis , 6 (1): 53–68, doi : 10.1007 / bf02485815 , MR 0398913 , S2CID 16718857  .
  6. ^ Barendregt, Henk , El cálculo lambda, su sintaxis y semántica Archivado el 23 de agosto de 2004 en la Wayback Machine , Holanda del Norte (1984)
  7. ^ Véase el teorema de Knaster-Tarski ; Los fundamentos de la verificación del programa, 2ª 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 muestra como ejercicio 4.3-5 en la página 90. 

Referencias

  • Davey, BA; Priestley, HA (2002). Introducción a las celosías y el orden (Segunda ed.). Prensa de la Universidad de Cambridge. ISBN 0-521-78451-4.