Ordre partiel complet

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[1].

• 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)[2].
• La notion d'ω-CPO est définie de même mais en se limitant aux « ω-chaînes », c'est-à-dire aux suites croissantes[3]. 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é ⊥.

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

Théorème du point fixe de Kleene

• Portail des mathématiques
• Portail de l’informatique