Ensembles ordonnés suivant:Index monter:aas précédent:aas
  Index
Ensembles ordonnés
Définition Soit un ensemble. Un ordre (partiel) sur est une relation telle que pour tout
:
Ces trois propriétés sont respectivement la réflexivité, la symétrie et la transitivité.
équipé d'un tel ordre est appelé «ensemble partiellement ordonné».
Un ordre donne naissance à une relation d'inégalité stricte par :
.
On définit aussi:
( et ne sont pas comparables)
Soit un sous-ensemble de , étant muni d'un ordre partiel ; on définit l'ordre partiel induit sur par
.
Définition Un ensemble muni d'un ordre partiel est dit totalement ordonné si et seulement si
. Un ensemble totalement ordonné est aussi appelé une chaîne. Un ensemble tel que
est appelé une antichaîne.
Définition Une chaîne est dîte maximale si et seulement si quel que soit l'élément , l'ensemble
n'est pas une chaîne.
Une antichaîne est dîte maximale si et seulement si quel que soit l'élément , l'ensemble
n'est pas une antichaîne.
On note la chaîne .
Dans la suite du texte désigne une relation d'ordre partiel.
Définition Etant donné , on définit la relation de couverture par ( couvre ou est couvert par ) si et seulement si
. Ceci signifie qu'il n'y a pas de tel que .
Si est fini, la relation de couverture détermine la relation d'ordre partiel (et réciproquement).
Définition On définit maintenant le diagramme de Hasse pour un ensemble fini partiellement ordonné. A chaque élément de on associe un point du plan, et on trace une ligne de à si . On veille à ce que ces lignes n'intersectent pas les autres points, et on veille à ce que implique que l'ordonnée du point associé à soit inférieure à l'ordonnée du point associé à .
DéfinitionUne application
est dîte:
monotone si
.
un morphisme si
.
un isomorphisme d'ordre si c'est un morphisme bijectif.
Quand est un morphisme, on écrit
.
Quand est un isomorphisme on écrit ; et sont isomorphes.
Proposition Soit bijective de dans : alors les trois énoncés suivants sont équivalents:
est un isomorphisme d'ordre
dans si et seulement si
dans dans P si et seulement si
Deux ensembles finis ordonnés sont isomorphes si et seulement si ils ont un diagramme de Hasse commun.
Définition
Le dual d'un ensemble ordonné est le même ensemble mais muni de l'ordre
tel que
si et seulement si . Le dual d'un énoncé et l'énoncé
obtenu en remplaçant par et réciproquement.
Un énoncé est vrai pour tous les ensembles ordonnés si et seulement si son dual est vrai pour tous les ensembles ordonées.
Définition Soit sous-ensemble de tel que
, avec ordonné. est un idéal d'ordre si et seulement si
. est un filtre d'ordre si et seulement si
.
est un filtre d'ordre si et seulement si le complémentaire de est un idéal d'ordre.
On définit
par l'ensemble des tel que pour un certain dans on a . Par définition
est égal à
.
se lit «section initiale engendrée par ».
On définit
par l'ensemble des tel que pour un certain dans on a . Par définition
est égal à
.
se lit «section initiale engendrée par ».
est donc le plus petit idéal d'ordre contenant , et
est le plus petit filtre d'ordre contenant .
On note l'ensemble des idéaux d'ordre de l'ensemble ordonné ; il est lui-même ordonné.
Les trois énoncés suivants sont équivalents:
Définition est maximal si et seulement si
est le maximum de si et seulement si pour tout on a . On écrit .
Les notions de minimal et d'élément minimum sont définies de manière duale, en renversant l'ordre.
L'élément maximum d'un ensemble est généralement noté , et l'élément minimum est généralement noté .
Lorsque l'ensemble est fini, l'ensemble des éléments maximaux et l'ensemble des éléments minimaux sont des anti-chaînes maximales.
Lorsqu'une chaîne
est maximale, alors
.
Définition
On appelle généralement:
graphe de la relation le graphe dans lequel on supprime les réflexivités.
graphe de compatibilité l'ensemble des avec comparable à .
graphe de Hasse (ne pas confondre avec diagramme de Hasse) l'ensemble des tels que .
graphe de couverture l'ensemble des tels que ou .
On note dans la suite l'ensemble ordonné constitué de l'ensemble auquel on ajoute une constante inférieure à tous les éléments de . S'il y avait une relation d'ordre sur , la relation sur contient cette relation. S'il n'y en avait pas, on obtient ce que l'on appelle un ordre plat.
Définition
L'union disjointe de deux ensembles ordonnés disjoints et est l'ensemble union de et avec
.
La somme linéaire de deux ensembles ordonnés disjoints et est l'ensemble réunion de et muni de la relation
.
On note
la somme séparée de et , égale à
.
On note
la somme coalescente de et , obtenue en considérant
et en identifiant les deux éléments .
Le produit de
est défini sur l'ensemble produit cartésien par
.
Soit
, et soit
défini par
avec
si et
sinon. Alors est un isomorphisme d'ordre.
L'ensemble des applications d'un ensemble vers un ensemble ordonné sont naturellement ordonnées par
. Si est lui-même ordonné, on peut considérer simplement l'ensemble des applications monotones, que l'on note .
On peut aussi considérer des fonctions au lieu de considérer des applications; on considère alors que si et seulement si pour tout élément du domaine de définition de on a
.
Pour ordonner l'ensemble des fonctions de dans on ajoute un élément dans inférieur à tous les éléments, et en remplaçant une fonction par l'application qui lui est égale sur son domaine de définition et qui est égale à en dehors de ce domaine. Cette fonction qui à une fonction de dans associe une application de dans est un isomorphisme d'ordre.
suivant:Index monter:aas précédent:aas
  Index
C_antonini,J-F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud