Pedido parcial completo - Complete partial order

Em matemática , a frase ordem parcial completa é usada de várias maneiras para se referir a pelo menos três classes semelhantes, mas distintas, de conjuntos parcialmente ordenados , caracterizados por propriedades de completude particulares . Pedidos parciais completos desempenham um papel central na ciência da computação teórica : na semântica denotacional e na teoria de domínio .

Definições

Uma ordem parcial completa cpo abreviada pode, dependendo do contexto, referir-se a qualquer um dos seguintes conceitos.

  • Um conjunto parcialmente ordenado é uma ordem parcial completa direcionada ( dcpo ) se cada um de seus subconjuntos direcionados tiver um supremo . Um subconjunto de uma ordem parcial é direcionado se não estiver vazio e cada par de elementos tiver um limite superior no subconjunto. Na literatura, dcpos às vezes também aparecem sob o rótulo poset up-complete .
  • Um conjunto parcialmente ordenado é uma ordem parcial direcionada completa se for um dcpo com um mínimo de elemento. Às vezes, são abreviados como cppo s.
  • Um conjunto parcialmente ordenado é uma ordem parcial ω-completa ( ω-cpo ) se for um poset em que cada cadeia ω ( x 1 ≤ x 2 ≤ x 3 ≤ x 4 ≤ ...) tem um supremo que pertence a o conjunto subjacente do poset. Todo dcpo é um ω-cpo, uma vez que toda cadeia ω é um conjunto direcionado, mas o inverso não é verdadeiro. No entanto, todo ω-cpo com uma base também é um dcpo (com a mesma base). Um ω-cpo (dcpo) com uma base é também chamado um contínuo ω-cpo (dcpo contínua).

Observe que a ordem parcial completa nunca é usada para significar um poset em que todos os subconjuntos têm suprema; a terminologia completa lattice é usada para este conceito.

Exigir a existência de suprema direcionado pode ser motivado pela visualização de conjuntos direcionados como sequências de aproximação generalizadas e suprema como limites dos respectivos cálculos (aproximativos). Essa intuição, no contexto da semântica denotacional, foi a motivação por trás do desenvolvimento da teoria do domínio .

A noção dupla de um poset completo direcionado é chamada de ordem parcial completa filtrada . No entanto, esse conceito ocorre com muito menos frequência na prática, uma vez que geralmente se pode trabalhar explicitamente na ordem dual.

Exemplos

  • Cada poset finito é direcionado completo.
  • Todas as redes completas também são direcionadas de forma completa.
  • Para qualquer poset, o conjunto de todos os filtros não vazios , ordenados por inclusão de subconjunto, é um dcpo. Junto com o filtro vazio também é apontado. Se a ordem tem encontros binários , então esta construção (incluindo o filtro vazio) realmente produz uma rede completa .
  • Cada conjunto S pode ser transformado em um dcpo pontiagudo adicionando um elemento mínimo ⊥ e introduzindo uma ordem plana com ⊥ ≤  s e s ≤  s para cada s  ∈  S e nenhuma outra relação de ordem.
  • O conjunto de todas as funções parciais em algum dado conjunto S podem ser encomendados através da definição de f  ≤  g para as funções f e g se e somente se g estende f , isto é, se o domínio de f é um subconjunto do domínio de g e os valores de f e g concordam com todas as entradas para as quais ambas as funções são definidas. (Equivalentemente, f  ≤  g se e somente se f  ⊆  g onde f e g são identificados com os respectivos gráficos .) Esta ordem é um dcpo pontiaguda, em que o elemento é menos a função de nenhuma parte-definido (com domínio vazio). Na verdade, ≤ também é limitado como completo . Este exemplo também demonstra por que nem sempre é natural ter um elemento maior.
  • A ordem de especialização de qualquer espaço sóbrio é um dcpo.
  • Vamos usar o termo “ sistema dedutivo ” como um conjunto de sentenças fechadas sob consequência (para definir a noção de consequência, vamos usar, por exemplo , a abordagem algébrica de Alfred Tarski ). Existem teoremas interessantes que dizem respeito a um conjunto de sistemas dedutivos sendo uma ordenação parcial dirigida completa. Além disso, um conjunto de sistemas dedutivos pode ser escolhido para ter um mínimo de elemento de uma forma natural (de modo que também possa ser um dcpo pontiagudo), porque o conjunto de todas as consequências do conjunto vazio (ou seja, "o conjunto do logicamente provável / sentenças logicamente válidas ”) é (1) um sistema dedutivo (2) contido por todos os sistemas dedutivos.

Propriedades

Um conjunto ordenado P é um dcpo pontiagudo se e somente se cada cadeia tiver um supremo em P , isto é, P é cadeia completa . Alternativamente, um conjunto ordenado P é um dcpo pontiagudo se e somente se todo auto-mapa de preservação de ordem de P tiver um ponto fixo mínimo .

Funções contínuas e pontos fixos

Uma função f entre dois dcpos P e Q é chamada de (Scott) contínua se mapeia conjuntos direcionados para conjuntos direcionados, preservando sua suprema:

  • é dirigido para cada dirigido .
  • para cada dirigido .

Observe que toda função contínua entre dcpos é uma função monótona . Esta noção de continuidade é equivalente à continuidade topológica induzida pela topologia de Scott .

O conjunto de todas as funções contínuas entre dois dcpos P e Q é denotado [ P  →  Q ]. Equipado com a ordem pontual, é novamente um dcpo e um cpo sempre que Q for um cpo. Assim, os pedidos parciais completos com mapas contínuos de Scott formam uma categoria cartesiana fechada .

Todo auto-mapa com preservação de ordem f de um cpo ( P , ⊥) tem pelo menos um ponto fixo. Se f é contínuo, então este ponto fixo é igual ao supremo dos iterados (⊥, f (⊥), f ( f (⊥)), ... f n (⊥), ...) de ⊥ (ver também o fixo de Kleene teorema do ponto ).

Veja também

A completude direcionada se relaciona de várias maneiras a outras noções de completude , como a completude da cadeia . A completude dirigida por si só é uma propriedade básica que ocorre frequentemente em outras investigações teóricas da ordem, usando, por exemplo, posets algébricos e a topologia de Scott .

Notas

  1. ^ Abramsky S , Gabbay DM , Maibaum TS (1994). Handbook of Logic in Computer Science, volume 3 . Oxford: Clarendon Press. Prop 2.2.14, pp. 20. ISBN 9780198537625.
  2. ^ Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapeste, 1990. (Título significa: Prova e verdade / Artigos selecionados.)
  3. ^ Stanley N. Burris e HP Sankappanavar: Um curso de álgebra universal
  4. ^ Veja online na pág. 24 exercícios 5–6 de §5 em [1] . Ou, no papel, consulte Tar: BizIg .
  5. ^ Markowsky, George (1976), "Chain-complete posets and direct sets with applications", Algebra Universalis , 6 (1): 53-68, doi : 10.1007 / bf02485815 , MR  0398913 , S2CID  16718857.
  6. ^ Barendregt, Henk , The lambda calculus, its syntax and semantics Archived 2004-08-23 na Wayback Machine , North-Holland (1984)
  7. ^ Veja teorema de Knaster – Tarski ; The foundations of program verification, 2ª edição, Jacques Loeckx e Kurt Sieber, John Wiley & Sons, ISBN  0-471-91282-4 , Capítulo 4; o teorema de Knaster-Tarski, formulado sobre o cpo, é dado para provar como exercício 4.3-5 na página 90.

Referências