Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
157 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 next up previous index
suivant: Index monter: aas précédent: aas   Index


Ensembles ordonnés

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

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

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

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

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

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$; $ E$ et $ F$ sont isomorphes.

Proposition 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.

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 $ 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$

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

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 $ (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.

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


next up previous index
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
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page