A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

272 personne(s) sur le site en ce moment

E. Cartan

Les maths pour l'agreg

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Théo. Sylow

Théo. Ascoli

Théo. Baire

Loi forte grd nbre

Nains magiques

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 $\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é.

é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$ ( et ne sont pas comparables)

Soit un sous-ensemble de , étant muni d'un ordre partiel $\leq_E$ ; on définit l'ordre partiel $\leq_E$ induit sur par $x \leq_F y \iff x \leq_E y$ .

Définition Un ensemble muni d'un ordre partiel 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.

Définition Une chaîne est dîte maximale si et seulement si quel que soit l'élément , l'ensemble $C \cup \{x\}$ 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 $C \cup \{x\}$ n'est pas une antichaîne.

On note la chaîne .
Dans la suite du texte $\leq$ désigne une relation d'ordre partiel.

Définition Etant donné $\leq$ , on définit la relation de couverture $\prec$ par $x \prec y$ ( couvre ou est couvert par ) 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 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 $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é à soit inférieure à l'ordonnée du point associé à .

Définition 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$ ; et sont isomorphes.

Proposition Soit $\phi$ bijective de dans : alors les trois énoncés suivants sont équivalents:
$\bullet\$ $\phi$ est un isomorphisme d'ordre
$\bullet\$ dans si et seulement si $\phi (x) < \phi (y)$ dans
$\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.

Définition 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.

Définition Soit sous-ensemble de tel que $F \subset E$ , avec ordonné. est un idéal d'ordre si et seulement si $x \in F \land y \leq x \rightarrow y \in F$ . est un filtre d'ordre si et seulement si $(x \in F \land x \leq y) \rightarrow y \in F$ .
est un filtre d'ordre si et seulement si le complémentaire de est un idéal d'ordre.

On définit $\downarrow F$ par l'ensemble des tel que pour un certain dans on a $x \leq y$ . Par définition $\downarrow x$ est égal à $\downarrow {x}$ . $\downarrow F$ se lit «section initiale engendrée par ».
On définit $\uparrow F$ par l'ensemble des tel que pour un certain dans on a $y \leq x$ . Par définition $\uparrow x$ est égal à $\uparrow {x}$ . $\uparrow F$ se lit «section initiale engendrée par ».
$\downarrow F$ est donc le plus petit idéal d'ordre contenant , et $\uparrow F$ 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:
$\bullet\$ $x \leq y$
$\bullet\$ $\downarrow x \subset \downarrow y$
$\bullet\$ $(\forall F \in O(E)) y \in F \rightarrow x \in F$

Définition est maximal si et seulement si $x \leq y \rightarrow x=y$
est le maximum de si et seulement si pour tout on a $y \leq x$ . 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é $\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}$ .

Définition 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 avec comparable à .
$\bullet\$ graphe de Hasse (ne pas confondre avec diagramme de Hasse) l'ensemble des tels que $x \prec y$ .
$\bullet\$ graphe de couverture l'ensemble des tels que $x \prec y$ ou $y \prec x$ .

On note dans la suite $E_\bot$ l'ensemble ordonné constitué de l'ensemble auquel on ajoute une constante $\bot$ inférieure à tous les éléments de . S'il y avait une relation d'ordre sur , 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.

Définition L'union disjointe $E \dot \cup F$ de deux ensembles ordonnés disjoints et est l'ensemble union de et 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 et est l'ensemble réunion de et 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 et , égale à $(P \dot \cup Q)_\bot$ .
On note $P \oplus_\lor Q$ la somme coalescente de et , obtenue en considérant $P \dot \cup Q$ et en identifiant les deux éléments $\bot$ .
Le produit de 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 des applications d'un ensemble vers un ensemble ordonné sont naturellement ordonnées par $f \leq g \iff \forall x \ f(x) \leq g(x)$ . Si 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 du domaine de définition de on a $f(x) \leq g(x)$ .
Pour ordonner l'ensemble des fonctions de dans on ajoute un élément $\bot$ 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 à $\bot$ en dehors de ce domaine. Cette fonction qui à une fonction de dans associe une application de dans $Y_{\bot}$ est un isomorphisme d'ordre.