Ordre partiel complet

{{#invoke:Bandeau|ébauche}} Modèle:Confusion Modèle:Voir homonymes

Il existe plusieurs notions non équivalentes d'ordre partiel complet (Modèle:Langue 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 E₀ ⊆ E₁ ⊆ E₂ ⊆ ..., on peut définir l'union infinie E₀ ∪ E₁ ∪ E₂ ∪ ... . La définition de CPO abstrait et formalise ce point<ref>Modèle:Ouvrage.</ref>.

Définitions

• Un d-CPO est un ensemble partiellement ordonné dont toutes les chaînes ont une borne supérieure. Cette définition équivaut à celle d'ensemble inductif strict avec plus petit élément (la borne supérieure de la chaîne vide)<ref>Modèle:Article.</ref>.
• La notion d'ω-CPO est définie de même mais en se limitant aux « ω-chaînes », c'est-à-dire aux suites croissantes<ref>Modèle:Harvsp.</ref>. La borne supérieure d'une suite croissante d₀ ≤ d₁ ≤ ... ≤ d_n ≤ ...est notée ⨆{d₀, d₁, ...}, ou ⨆_nd_n.

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).

Voir aussi

Théorème du point fixe de Kleene