Poset

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un poset (de l'anglais partially ordered set, en français EPO: ensemble partiellement ordonné) formalise et généralise la notion intuitive d'ordre ou d'arrangement entre les éléments d'un ensemble. Un poset est un ensemble muni d'une relation d'ordre qui indique que pour certains couples d'éléments, l'un est plus petit que l'autre. Tous les éléments ne sont pas forcément comparables, contrairement au cas d'un ensemble muni d'un ordre total.

Si l'ensemble est fini, on dispose d'une représentation graphique du poset, le diagramme de Hasse, ce qui peut permettre de travailler plus aisément dessus. Si l'ensemble est infini, on peut dessiner une partie de son diagramme de Hasse.

Définition et exemples[modifier | modifier le code]

Définition[modifier | modifier le code]

Un ordre (ou ordre partiel) est une relation binaire sur un ensemble P qui est réflexive, antisymétrique et transitive. Elle se note ≤.

Les trois axiomes précédents se récrivent:

  1. aa (réflexivité).
  2. Si ab et ba, alors a = b (anti-symétrie).
  3. Si ab et bc, alors ac (transitivité).

Ce n'est donc pas nécessairement un ordre total.

Exemples[modifier | modifier le code]

  • L'ensemble des nombres entiers naturels, muni de la divisibilité est un poset infini.
  • Un ensemble de personnes muni de la relation de la descendance généalogique est un poset. Par exemple, deux sœurs sont inférieures à leur mère mais on ne peut pas les comparer entre elles.
  • L'ensemble des parties d'un ensemble donné, muni de l'inclusion forme un poset. Si l'ensemble donné est fini, son ensemble des parties est fini (plus précisément pour , on a ). La figure ci-dessous représente le diagramme de Hasse d'un ensemble à 3 éléments.
Diagramme de Hasse d'un ensemble à 3 éléments.
  • L'ensemble des nombres complexes muni de la relation d'ordre suivante est partiellement ordonné : .

Par exemple, on ne peut pas comparer 1 et i. Cet ordre n'est pas compatible avec la structure de corps de .

  • L'ensemble des fonctions de dans , muni de la relation d'ordre si , est un poset infini. Intuitivement, une fonction est plus petite qu'une autre si sa courbe est toujours en dessous de l'autre courbe. On peut généraliser cet exemple aux fonctions d'un ensemble X dans un poset P.
  • L'ensemble des partitions d'un ensemble donné est partiellement ordonné, avec l'ordre donné par le raffinement des partitions : par définition, une partition est plus fine qu'une autre si elle fractionne les parties de l'autre en de plus petites parties.
  • On peut munir l'ensemble des polynômes à n variables d'une relation d'ordre partiel. On commence par comparer les monômes à n variables via l'ordre lexicographique induit par (cet ordre lexicographique est total). On compare deux polynômes et en disant que est strictement plus petit que si tout monôme non nul de est strictement plus petit que tout monôme non nul de . Cette relation d'ordre sur les polynômes est partielle.

Spécificités des ensembles partiellement ordonnés[modifier | modifier le code]

Plus grand élément, élément maximal et borne supérieure[modifier | modifier le code]

Soit P un poset:

  • Un élément a de P est un plus grand élément si pour tout élément b de P, b≤a. Un poset ne peut avoir qu’un plus grand élément.
  • Un élément a de P est un élément maximal s’il n’existe pas d’élément b de P tel que b>a. Si P à un plus grand élément, il est l’unique élément maximal de P.
  • Pour un sous-ensemble A de P, l’élément x de P est une borne supérieur de A si a≤x pour tout élément a de A. x n’appartient pas nécessairement à A. Le plus grand élément de P, s’il existe, est une borne supérieure de P.

Exemple: considérons l’ensemble des entiers positifs, ordonné par la division. 1 est le plus petit élément. En revanche cet ensemble ne possède pas de plus grand élément. Si on excluait maintenant l’élément 1, le poset n’aurait plus de plus petit élément mais une infinité d’éléments minimaux : les nombres premiers.

Si E est un poset, il n'existe pas forcément de plus grand élément. Si E est un poset fini, il contiendra au moins un élément maximal. Si E est un ensemble inductif infini, on peut utiliser le lemme de Zorn pour avoir l'existence d'un élément maximal.

Certaines conditions sur les plus grands éléments et plus petits éléments d'un poset conduisent à la définition d'un treillis.

Par le même raisonnement on obtient le plus petit élément, les éléments minimaux et la borne inférieure.

Comparabilité[modifier | modifier le code]

Si a ≤ b ou a b, alors a et b sont comparables. Dans le diagramme de Hasse ci-dessus, {x} et {x,y,z} sont comparable, tandis que {x} et {y} ne le sont pas.Un ordre partiel dans lequel toute paire d’éléments est comparable est appelée un ordre total, et l’ensemble est appelé une chaîne.Un ensemble dans lequel on ne peut trouver de paire comparable s’appelle une antichaîne (par exemple l’ensemble {{x}, {y}, {z}} sur la figure ci-dessus)

Recouvrement[modifier | modifier le code]

On dit qu’un élément a est recouvert par un élément b, ce qui s’écrit a<:b, si a est strictement inférieur à b et qu’il n’existe pas d’élément c s’intercalant entre les deux. Par exemple, {x} est recouvert par {x,z} dans la figure ci-dessus mais pas par {x,y,z}.

Liens avec les complexes simpliciaux[modifier | modifier le code]

Une classe importante de complexes simpliciaux provient de posets finis. On définit le complexe d'ordre D(P) d'un poset fini P comme étant l'ensemble des chaînes de P. Le complexe d'ordre est trivialement un complexe simplicial.

L'étude du poset donne des informations sur son complexe d'ordre, et donc il est intéressant d'étudier un complexe simplicial comme le complexe d'ordre d'un poset.

Opération sur les Posets[modifier | modifier le code]

Produit cartésien de Poset[modifier | modifier le code]

Dans le but de supprimer la multiplicité des relations d'ordre possibles lors d'un produit de Poset, on peut définir trois règles différentes:

Toutes ces règles s'appliquent également pour des produits de plus de deux Posets.

Finitude locale[modifier | modifier le code]

Un poset E est dit localement fini si pour tous , l'intervalle est fini. Cette hypothèse permet de généraliser la formule d'inversion de Möbius.

Références[modifier | modifier le code]

(en) Richard P. Stanley, Enumerative Combinatorics, vol. 1 [détail des éditions] (présentation en ligne)

Voir aussi[modifier | modifier le code]