Soit \(E\) un ensemble. Un ordre (partiel) sur \(E\) est une relation \(\leq\) telle que pour tout \((x,y,z) \in E^3\):
\(\bullet\)\(x \leq x\)
\(\bullet\)\((x \leq y \land y \leq x) \rightarrow x=y\)
\(\bullet\)\((x \leq y \land y \leq z) \rightarrow x \leq z\)
Ces trois propriétés sont respectivement la réflexivité, la symétrie et la transitivité.
\(E\) équipé d’un tel ordre est appelé << ensemble partiellement ordonné>>.
Un ordre \(\leq\) donne naissance à une relation d’inégalité stricte \(<\) par : \(x<y \iff (x \leq y \land x \neq y\).
On définit aussi:
\(\bullet\)\(x \geq y \iff y \leq x\)
\(\bullet\)\(x \not \leq y \iff \neg ( x \leq y)\)
\(\bullet\)\(x \parallel y \iff x \not \leq y \land y \not \leq x\) (\(x\) et \(y\) ne sont pas comparables)
Soit \(F\) un sous-ensemble de \(E\), \(E\) étant muni d’un ordre partiel \(\leq_E\); on définit l’ordre partiel \(\leq_E\) induit sur \(F\) par \(x \leq_F y \iff x \leq_E y\).
Un ensemble \(E\) muni d’un ordre partiel \(E\) est dit totalement ordonné si et seulement si \(\forall (x,y) \in E^2 x \leq y \lor y \leq x\). Un ensemble totalement ordonné est aussi appelé une chaîne. Un ensemble tel que \(x \leq y \rightarrow x=y\) est appelé une antichaîne.
Une chaîne \(C\) est dîte maximale si et seulement si quel que soit l’élément \(x\), l’ensemble \(C \cup \{x\}\) n’est pas une chaîne.
Une antichaîne \(C\) est dîte maximale si et seulement si quel que soit l’élément \(x\), l’ensemble \(C \cup \{x\}\) n’est pas une antichaîne.
On note \(n\) la chaîne \([0,n[\).
Dans la suite du texte \(\leq\) désigne une relation d’ordre partiel.
Etant donné \(\leq\), on définit la relation de couverture \(\prec\) par \(x \prec y\) (\(y\) couvre \(x\) ou \(x\) est couvert par \(y\)) si et seulement si \(x < y \land \forall z ( x \leq z <y \rightarrow z=x)\). Ceci signifie qu’il n’y a pas de \(z\) tel que \(x<y<z\).
Si \(E\) est fini, la relation de couverture détermine la relation d’ordre partiel (et réciproquement).
On définit maintenant le diagramme de Hasse pour un ensemble fini partiellement ordonné. A chaque élément de \(E\) on associe un point du plan, et on trace une ligne de \(x\) à \(y\) si \(x \prec y\). On veille à ce que ces lignes n’intersectent pas les autres points, et on veille à ce que \(x \prec y\) implique que l’ordonnée du point associé à \(x\) soit inférieure à l’ordonnée du point associé à \(y\).
Une application \(\phi : E \rightarrow F\) est dîte:
\(\bullet\)monotone si \(x \leq y \rightarrow \phi (x) \leq \phi (y)\).
\(\bullet\)un morphisme si \(x \leq y \iff \phi(x) \leq \phi (y)\).
\(\bullet\)un isomorphisme d’ordre si c’est un morphisme bijectif.
Quand \(\phi\) est un morphisme, on écrit \(\phi : E \hookrightarrow F\).
Quand \(\phi\) est un isomorphisme on écrit \(E \cong F\); \(E\) et \(F\) sont isomorphes.
Soit \(\phi\) bijective de \(E\) dans \(F\): alors les trois énoncés suivants sont équivalents:
\(\bullet\) \(\phi\) est un isomorphisme d’ordre
\(\bullet\)\(x < y\) dans \(E\) si et seulement si \(\phi (x) < \phi (y)\) dans \(F\)
\(\bullet\)\(x \prec y\) dans P si et seulement si \(\phi (x) \prec \phi (y)\)
Deux ensembles finis ordonnés sont isomorphes si et seulement si ils ont un diagramme de Hasse commun.
Le dual d’un ensemble ordonné est le même ensemble mais muni de l’ordre \(\leq ^ \delta\) tel que \(x \leq ^ \delta y\) si et seulement si \(y \leq x\). Le dual d’un énoncé \(\psi\) et l’énoncé \(\psi ^ \delta\) obtenu en remplaçant \(\leq\) par \(\geq\) 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.
Soit \(F\) sous-ensemble de \(E\) tel que \(F \subset E\), avec \(E\) ordonné. \(F\) est un idéal d’ordre si et seulement si \(x \in F \land y \leq x \rightarrow y \in F\). \(F\) est un filtre d’ordre si et seulement si \((x \in F \land x \leq y) \rightarrow y \in F\).
\(F\) est un filtre d’ordre si et seulement si le complémentaire de \(F\) est un idéal d’ordre.
On définit \(\downarrow F\) par l’ensemble des \(x\) tel que pour un certain \(y\) dans \(F\) on a \(x \leq y\). Par définition \(\downarrow x\) est égal à \(\downarrow {x}\). \(\downarrow F\) se lit << section initiale engendrée par \(F\)>>.
On définit \(\uparrow F\) par l’ensemble des \(x\) tel que pour un certain \(y\) dans \(F\) on a \(y \leq x\). Par définition \(\uparrow x\) est égal à \(\uparrow {x}\). \(\uparrow F\) se lit << section initiale engendrée par \(F\)>>.
\(\downarrow F\) est donc le plus petit idéal d’ordre contenant \(F\), et \(\uparrow F\) est le plus petit filtre d’ordre contenant \(F\).
On note \(O(E)\) l’ensemble des idéaux d’ordre de l’ensemble ordonné \(E\); il est lui-même ordonné.
Les trois énoncés suivants sont équivalents:
\(\bullet\)\(x \leq y\)
\(\bullet\)\(\downarrow x \subset \downarrow y\)
\(\bullet\)\((\forall F \in O(E)) y \in F \rightarrow x \in F\)
\(x\) est maximal si et seulement si \(x \leq y \rightarrow x=y\)
\(x\) est le maximum de \(E\) si et seulement si pour tout \(y\) on a \(y \leq x\). On écrit \(x=max Q\).
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é \(\top\), et l’élément minimum est généralement noté \(\bot\).
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 \(\{ x_1<x_2<...<x_n \}\) est maximale, alors \(\forall i \ x_i \prec x_{i+1}\).
On appelle généralement:
\(\bullet\)graphe de la relation le graphe dans lequel on supprime les réflexivités.
\(\bullet\)graphe de compatibilité l’ensemble des \((x,y)\) avec \(x\) comparable à \(y\).
\(\bullet\)graphe de Hasse (ne pas confondre avec diagramme de Hasse) l’ensemble des \((x,y)\) tels que \(x \prec y\).
\(\bullet\)graphe de couverture l’ensemble des \({x,y}\) tels que \(x \prec y\) ou \(y \prec x\).
On note dans la suite \(E_\bot\) l’ensemble ordonné constitué de l’ensemble \(E\) auquel on ajoute une constante \(\bot\) inférieure à tous les éléments de \(E\). S’il y avait une relation d’ordre sur \(E\), la relation sur \(E_\bot\) contient cette relation. S’il n’y en avait pas, on obtient ce que l’on appelle un ordre plat.
L’union disjointe \(E \dot \cup F\) de deux ensembles ordonnés disjoints \(E\) et \(F\) est l’ensemble union de \(E\) et \(F\) avec \(x \leq_{E \dot \cup F} y \iff ( x \leq_E y \lor x \leq_F y)\).
La somme linéaire \(E \oplus F\) de deux ensembles ordonnés disjoints \(E\) et \(F\) est l’ensemble réunion de \(E\) et \(F\) muni de la relation \(x \leq_{E \oplus F} \iff ( x \leq_E y \lor x \leq_F y \lor ( x\in E \land y \in F) )\).
On note \(P \oplus_\bot Q\) la somme séparée de \(P\) et \(Q\), égale à \((P \dot \cup Q)_\bot\).
On note \(P \oplus_\lor Q\) la somme coalescente de \(P\) et \(Q\), obtenue en considérant \(P \dot \cup Q\) et en identifiant les deux éléments \(\bot\).
Le produit de \(P_1,...,P_n\) est défini sur l’ensemble produit cartésien par \((x_1,...,x_n) \leq_{P_1 \times P_2 \times ... \times Pn} (y_1,...,y_n) \iff \forall i \ x_i \leq_{P_i} y_i\).
Soit \(X= \{ 1,2,...,n \}\), et soit \(\phi : P(X) \rightarrow \{ 0,1 \} ^n\) défini par \(\phi (A) = ( \epsilon_1, ... , \epsilon_n )\) avec \(\epsilon_i = 1\) si \(i \in A\) et \(\epsilon_i=0\) sinon. Alors \(\phi\) est un isomorphisme d’ordre.
L’ensemble \(Y^X\) des applications d’un ensemble \(X\) vers un ensemble ordonné \(Y\) sont naturellement ordonnées par \(f \leq g \iff \forall x \ f(x) \leq g(x)\). Si \(X\) est lui-même ordonné, on peut considérer simplement l’ensemble des applications monotones, que l’on note \(Y^{<X>}\).
On peut aussi considérer des fonctions au lieu de considérer des applications; on considère alors que \(f \leq g\) si et seulement si pour tout élément \(x\) du domaine de définition de \(f\) on a \(f(x) \leq g(x)\).
Pour ordonner l’ensemble des fonctions de \(X\) dans \(Y\) on ajoute un élément \(\bot\) dans \(Y\) 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 à \(\bot\) en dehors de ce domaine. Cette fonction qui à une fonction de \(X\) dans \(Y\) associe une application de \(X\) dans \(Y_{\bot}\) est un isomorphisme d’ordre.