Ordre partiel complet
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
Ne pas confondre avec les treillis complets, parfois également appelés ordres partiels complets.
Pour les articles homonymes, voir CPO.
En mathématiques, le terme ordre partiel complet recouvre plusieurs classes de relations d'ordre qui satisfont certaines conditions d'existence de bornes supérieures. L'étude des ordres partiels complets se rattache à la théorie des domaines. Elle joue un rôle central en informatique théorique, où elle permet de définir des sémantiques dénotationnelles pour les langages de programmation.
Motivation
modifierLes 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 des ordres partiels complets abstrait et formalise ce point[1].[pas clair]
Définitions
modifierOn appelle dcpo (abréviation de l'anglais directed-complete partial order) un ensemble muni d'un ordre (partiel) dont toutes les parties dirigées admettent une borne supérieure. (Une partie est dite dirigée si elle est non-vide et deux de ses éléments quelconques ont un majorant commun dans cette partie.)
Un dcpo pointé est un dcpo qui possède un minimum. Autrement dit, c'est un ensemble ordonné dans lequel toute partie dirigée ou vide admet une borne supérieure.
Un ω-cpo (pour l'anglais ω-complete partial order) est un ensemble partiellement ordonné dans lequel toute suite croissante admet une borne supérieure.
Tout dcpo est trivialement un ω-cpo (puisque les suites croissantes sont dirigées), mais la réciproque n'est pas vraie. Cependant, tout ω-cpo muni d'une base (en) est aussi un dcpo (avec la même base). Un ω-cpo (ou dcpo) qui possède une base est dit ω-cpo continu (ou dcpo continu).
Exemples
modifier- Tout ensemble muni de l'égalité comme relation d'ordre est un dcpo (sans plus petit élément sauf si est un singleton).
- L'ensemble des parties d'un ensemble, ordonné par l'inclusion, est un dcpo pointé (le plus petit élément est l'ensemble vide).
Caractérisations
modifierUn ensemble ordonné est un dcpo si et seulement si toute chaîne non-vide admet une borne supérieure. Par conséquent, un ensemble ordonné est un dcpo pointé si et seulement si toute chaîne (éventuellement vide) admet une borne supérieure[2],[3],[4],[5].
Notes et références
modifier- (en) Glynn Winskel, The Formal Semantics of Programming Languages : An Introduction, The MIT Press, (lire en ligne), p. 69.
- George Markowsky, Chain-complete posets and directed sets with applications, vol. 6, , 53–68 p. (DOI 10.1007/bf02485815, MR 0398913, S2CID 16718857), chap. 1.
- Jean Goubault-Larrecq, « Iwamura's Lemma, Markowsky's Theorem and ordinals », (consulté le )
- Paul Moritz Cohn, Universal Algebra, Harper and Row, p. 33
- Jean Goubault-Larrecq, « Markowsky or Cohn? », (consulté le )
