Accueil🇫🇷Chercher

Ordre partiel complet

Il existe plusieurs notions non équivalentes d'ordre partiel complet (complete partial order ou CPO).

La notion de CPO est utilisée pour résoudre les équations aux domaines, notamment quand on cherche une sémantique dénotationnelle pour un langage en informatique.

Motivation

Les ensembles partiellement ordonnés ne se comportent pas tous comme des ensembles de parties ordonnés par l'inclusion ⊆. En particulier, quand on a une suite croissante de sous-ensembles E0 ⊆ E1 ⊆ E2 ⊆ ..., on peut définir l'union infinie E0 ∪ E1 ∪ E2 ∪ ... . La définition de CPO abstrait et formalise ce point[1].

Définitions

Le plus petit élément d'un CPO, s'il existe, est noté ⊥.

Exemples

  • Tout ensemble E muni de la relation identité est un ω-CPO (sans plus petit élément sauf si E est un singleton).
  • L'ensemble des parties d'un ensemble, ordonné par l'inclusion, est un d-CPO (le plus petit élément est l'ensemble vide).

Notes et références

  1. (en) Glynn Winskel, The Formal Semantics of Programming Languages : An Introduction, The MIT Press, (lire en ligne), p. 69.
  2. (en) George Markowsky, « Chain-complete posets and directed sets with applications », Algebra Universalis, vol. 6, no 1,‎ , p. 53-68 (lire en ligne).
  3. Winskel 1993, p. 70.

Voir aussi

Théorème du point fixe de Kleene

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.