Ordre partiel complet

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

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 E₀ ⊆ E₁ ⊆ E₂ ⊆ ..., on peut définir l'union infinie E₀ ∪ E₁ ∪ E₂ ∪ ... . La définition des ordres partiels complets abstrait et formalise ce point.Modèle:Pas clair

Définitions

On 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 $x_1\le x_2\le x_3\le ...$ 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 Modèle:Lien 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

• Tout ensemble $E$ muni de l'égalité comme relation d'ordre est un dcpo (sans plus petit élément sauf si $E$ 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

Un 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érieureModèle:,Modèle:,Modèle:,.

Voir aussi

Théorème du point fixe de Kleene