ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Relation d'ordre, ensembles et structures ordonnés
    
majorant, minorant, bornes , préordre , bon ordre , treillis , ordre lexicographique , ordre total , groupe et anneau ordonnés

Dans un ensemble E, une relation binaire R est dite :

  Une relation d'ordre dans (ou sur) E est une relation binaire dans E, à la fois réflexive, antisymétrique et transitive.


1. Soit (E,*) un ensemble muni d'une loi de composition interne commutative notée *. On pose x R ssi  a*b = a.
Montrer que l'on définit ainsi un ordre sur E.

2. Montrer que si f est une application idempotente d'un ensemble E dans lui-même (f o f = f), la relation définie par
xRssi  y = f(x) est antisymétrique et transitive. A quelle condition sur f serait-elle réflexive ?

Rappelons l'existence d'une autre relation binaire fondamentale : la relation d'équivalence, dont les trois propriétés qui la définissent sont la réflexivité, la symétrie (si x R y, alors y R x) et la transitivité.

 En savoir plus sur les relations d'équivalence :  
 
Ensembles ordonnés, éléments comparables, ordre partiel, total, dense, strict, intervalles, encadrements :

La structure d'ensemble ordonné (ensemble muni d'une relation d'ordre) a été mise en place dans le cadre de la théorie des nombres par Cantor et Dedekind.

Ordre partiel, ordre total :      

Il se peut, que l'on ait ni x R y, ni y R x : on parle alors d'ordre partiel; sinon, l'ordre est total :

(x,y) E E : x R y  ou  y R x

On use, avec un sens évident des locutions E est partiellement ordonné par R, E est totalement ordonné par R.

Intervalles & encadrements :      

Dans un ensemble totalement ordonné (E, ), on parle d'intervalle [a,b] pour désigner l'ensemble des éléments x de E vérifiant la « double inégalité » : a   b. On parle aussi d'encadrement de x. Si les bornes a et b ne doivent pas être comprises, on notera a < x < b.     ordre strict.


Encadrements (encadrer  une somme, un produit, un quotient)

Ordre dense :   

Un ordre total est dit dense si pour tout (x,y) tel que x R y, il existe z tel que x R y et x R y

Relation de divisibilité dans N* :    

Dans N* = N - {0}, on dit que a divise b, et on note généralement a|b, pour signifier que b est un multiple de a, c'est à dire qu'il existe  kN, tel que b = k × a.

La relation de divisibilité dans N est est un ordre partiel.

1. Réflexivité : aN, a|a car a = 1a.
2. Antisymétrie :
si a|b et b|a, il existe k et k' dans N tels que b = ka et a = k'b, par suite kk' = 1 et, dans N, cette égalité implique k = k' = 1, donc a = b.
3. Transitivité : si a|b et b|c, il existe k et k' dans N tels que b = ka et c = k'b, par suite c = kk'a, kk'
N, donc a|c.

On  parle de divisibilité dans Z* mais la relation ne sera pas antisymétrique car kk' = 1 peut alors se produire pour k = k' = -1, ce qui conduit à a = -b. Ce n'est plus une relation d'ordre.

  On note R1[x], l'ensemble des polynômes unitaires (le coefficient du monôme de plus haute degré est 1) d'une variable x à coefficients réels. On dit que a divise b, s'il existe q dans R1[x] tels que pour tout x, b(x) = a(x)q(x).
Montrer que l'on définit ainsi un ordre partiel dans R1[x].
 

Ordre strict :      

La relation usuelle <, souvent dite d'ordre strict, n'est cependant pas une relation d'ordre car elle n'est pas réflexive. L'antisymétrie n'est cependant pas en défaut puisque les inégalités a < b et b < a ne peuvent avoir lieu conjointement.

A toute relation d'ordre , on peut associer une relation d'ordre strict par :

a   a b  et a b        ordre lexicographique

Intervalle ouvert, intervalle fermé :

Ordre induit :

Si R est un ordre sur E et F une partie de E, la restriction à F de la relation R est un ordre sur F, dit ordre induit par R dans F.


On munit N de l'ordre partiel "divise" : a|b b est multiple de a.
Montrer que la restriction de cet ordre à F = {n N, n = 2p, pN} est un ordre total dans F.

Préordre :

On munit Z de la relation divise : a | b b = k × a avec kZ. Restreinte à N, c'est une relation d'ordre partiel. Montrer que, définie dans Z, cette relation est réflexive et transitive mais n'est ni symétrique ni antisymétrique : on parle de relation de préordre.


On munit l'ensemble des vecteurs du plan de la relation, notée , définie par : u v  ssi  || u || || v ||
Montrer que l'on définit ainsi une relation de préordre  en exhibant un contre-exemple pour la propriété d'antisymétrie.

Majorant, minorant, ensemble majoré, minoré, ensemble borné :

Soit (E, ) un ensemble ordonné et F une partie de E.

  S'il existe un élément m de E tel que x m pour tout x de F, on dit que m est un majorant de F dans E ou encore que F est majorée par m. Si l'on a, au contraire, m x pour tout x de F, on parle de minorant et de partie minorée.

La partie F sera dite bornée si elle admet un majorant et un minorant.

Plus petit élément, plus grand élément :      

  Si un majorant (resp. minorant) d'une partie F de E est élément de F, il est le seul à posséder cette propriété : on l'appelle le plus grand (resp. plus petit) élément de de F pour la relation .

Preuve : supposons, par exemple, l'existence de deux majorants : on aurait, dans F, x m et x m' pour tout x de F et en choisissant x = m puis x = m',on obtient m = m' par antisymétrie.

On peut aussi énoncer : s'il existe un élément m de E inférieur (resp. supérieur) à tous les éléments de E (au sens de la relation ), on dit que m est le plus petit (resp. plus grand) élément de E. De tels éléments sont uniques.

Borne supérieure, borne inférieure :      

Lorsqu'une partie F est majorée (resp. minorée), le plus petit des majorants (resp. le plus grand des minorants), s'il existe, est appelée borne supérieure (resp. borne inférieure) de F.

  Un ensemble peut être borné sans pour autant admettre une borne supérieure ou une borne inférieure :

Dans l'ensemble Q des nombres rationnels (fractions a/b, a et b entiers, b non nul) muni de l'ordre usuel, la partie :

F = {x Q, x 0, x2 2}

manifestement majorée (par 3/2, 2, ...) n'admet pas de borne supérieure. En effet, supposons l'existence d'une borne supérieure m pour F; m est rationnel, il est le plus petit des majorants de F. On peut donc écrire :

(1)   xF, x m      et     (2)     M, M majorant de F, m M

(2) permet d'affirmer :

 Q, ε > 0, xoF / m - ε < xo m

Il s'ensuit que pour ε tout rationnel vérifiant 0 < ε m, on a (m - ε)2 < 2 et, par conséquent : ε2 - 2mε + m2 - 2 < 0 pour tout ε de l'intervalle rationnel ]0,m]. Si nous résolvons cette équation dans R, on voit qu'elle n'admet des solutions que si m 2. Or on sait que 2 n'est pas rationnel. ainsi m est un rationnel vérifiant m < 2. En tant que partie de R, les majorants M de F vérifient l'inégalité M 2 et les majorants de F dans Q sont alors les rationnels vérifiant M > 2 et en particulier m > 2. Les inégalités m <  2 et m > 2 étant incompatibles, F n'admet pas de borne supérieure.

Cas d'une partie de l'ensemble des nombres réels, théorème de Bolzano :

Élément maximal, élément minimal :

Soit (E, ) un ensemble ordonné. S'il existe dans E un élément m tel que tout x de E, comparable à m (et autre que m) lui soit inférieur (resp. supérieur) au sens de la relation , on dit que m est un élément maximal (resp. minimal). Lorsque l'ordre de E n'est pas total, il peut exister plusieurs éléments maximaux ou minimaux.

Si (E, ) admet un plus petit (resp. grand) élément m, alors m est l'unique élément minimal (resp. maximal) de E pour la relation .

Ensemble filtrant, ensemble réticulé, treillis :

Si, dans l'ensemble ordonné (E, ), toute paire {x,y} d'éléments de E admet un majorant (resp. minorant), E est dit filtrant supérieurement (resp. inférieurement).

Toute partie finie d'un ensemble filtrant supérieurement (resp. inférieurement)
est majoré (resp. minoré).


Soit (E,*) un ensemble muni d'une loi interne * commutative. On pose x R y  ssi  a*b = a.
R
est un ordre sur E. Vérifier que E est filtrant inférieurement en montrant que l'on a pour toute paire {a,b} :
(a*b) R a et (a*b) R b

Treillis :    

Si, dans l'ensemble ordonné (E, ), toute paire {x,y} d'éléments de E admet une borne supérieure et une borne inférieure, on parle d'ensemble réticulé ou encore de treillis, notion initiée par Skolem.

Si toute partie majorée et non vide de E admet une borne supérieure, on dit que E est complètement réticulé.


Ordonnons N par la relation de divisibilité. L'entier c majore {a,b} ssi a | m et b | m, donc sup(a,b) =... et inf(a,b) = ...(keywords = pgcd, ppmc...).

Théorème de Bolzano-Weirerstrass :Espace de Riesz :

Dans un treillis, on a les lois d'absorption : on a inf(x , sup(x,y)) = sup(x,inf(x,y)) = x. Pour mieux appréhender ce résultat, notons inf(x,y) = xy et sup(x,y) = xy en remarquant que cette notation fait apparaître etcomme deux lois de composition internes commutatives.

x(xy) = x(xy) = x

Un treillis est dit distributif si les lois inf et sup sont distributives l'une par rapport à l'autre :

x(yz) = (xy)(xz)    et   x(yz) = (xy)(xz)

Illustration : Sur les schémas de gauche (appelés diagrammes de Hasse), une flèche d'un élément x vers un élément y signifiera x y :

Le treillis de gauche est distributif. Le second ne l'est pas. La chaîne (représentation linéaire) correspond à un ordre total.


Il n'y a que 3 treillis distributifs pour un ensemble de 5 éléments.
Mise à part la chaîne, Quel sont les deux autres?  

Un treillis est dit complémenté s'il admet un plus petit élément m (improprement dit nul) et un plus grand élément M (dit universel) et si tout élément x admet un élément x dit complémenté de x tel que xx = inf(x,x) = m et xx = sup(x,x) = M.

à droite, le treillis en chaîne n'est pas complémenté. Le second l'est :  x, par exemple, a deux compléments y et z et m est l'unique complément de M.

On appelle treillis de Boole un treillis distributif et complémenté. Les éléments nul et universel sont alors notés respectivement 0 et 1.

G. Boole, anneau  et algèbre de Boole : 


1.  l'ensemble P des parties d'un ensemble E ordonné par la relation d'inclusion est un treillis de Boole..

2.  Dans un treillis de Boole, le complémenté est unique. Rép. : clic...

Un treillis de Boole est aussi un anneau commutatif unitaire : il suffit de poser x + y = (xy) (xy) et xy = x y. Le plus petit élément m est neutre pour l'addition et M est neutre pour la multiplication.

                  Compléments sur les algèbres et anneaux de Boole :                   Algèbre de Lindenbaum :

Ordre réciproque :

Si R est un ordre sur E, la relation R' (souvent notée R-1) définie par :

x R' y y R x

est un ordre sur E, dit ordre réciproque de R.

Ordre produit :

Si (E,O) et F,O') sont deux ensembles ordonnés par les relations notées O et O', on peut ordonner le produit cartésien E x F par l'ordre T dit ordre produit de O et O' :

(a,b) T (c,d) (a O c  et  b O' d)
Relation de bon ordre, ensemble bien ordonné :

Un ensemble ordonné (E,) est dit bien ordonné si toute partie non vide de E admet un plus petit élément. La relation est alors qualifiée de bon ordre. (N, ≤) est bien ordonné mais non pas (Z, ≤). L'existence d'un bon ordre dans R, est assuré par le théorème de Zermelo selon lequel

Tout ensemble peut être bien ordonné

est tributaire de l'axiome du choix. Quoi qu'il en soit, un tel ordre dans R n'a pas encore été exhibé.

En savoir un peu plus, bon ordre sur Z et Q :                     Bon ordre et nombres ordinaux :

Ordre lexicographique (ordre des dictionnaires) :

 Si ≤ est un ordre sur E, on peut munir E2 = E x E (ensemble produit) de l'ordre  ainsi défini :

(a,b) (a',b') (a < a') ou (a = a' et b ≤ b')

Si l'ordre de E est total, alors l'ordre ainsi défini dans E2 l'est aussi. On peut généraliser la définition à En, n entier quelconque.

Groupe ordonné, valeur absolue :

Un groupe (G,*) est dit ordonné par une binaire définie dans G lorsque :

  1. est un ordre dans G;
  2. si a b, pour tout c de G, on a : a*c b*c et c*a c*b  (et par conséquent a*c-1 b*c-1).

On note (G,*,) un tel groupe ordonné par l'ordre . En conséquence, on a en particulier :

Proposition 1 :     

Dans un groupe ordonné, Si a b  et  c d, alors  a*c b*d

En effet, a b et c d entraînent d'une part a*c b*c, d'autre part b*c b*d et le résultat est acquis par transitivité.

Valeur absolue :   

Dans un groupe totalement ordonné (G,*,), d'élément neutre e, on peut définir la valeur absolue | x | d'un élément par | x | = Max(x, x-1) et parler d'éléments positifs (resp. négatifs) lorsque e x (resp. x e).


Soit x-1 le symétrique de x dans (G,*,).  Montrer que | x-1 | = | x |

On pourra prouver, tout comme dans le cas usuel de R, la double inégalité dite inégalité triangulaire qui s'écrit dans ce cas abstrait :

| y |*| x |-1 | x*y | | x |*| y |

En savoir plus sur la notion de valeur absolue :

Anneau et corps ordonnés :

Un anneau ou un corps (A,+,x), d'élément nul 0 est dit ordonné par une binaire définie dans A si :

  1. est un ordre dans A
  2. (A,+,) est un groupe (commutatif) ordonné, en particulier :
    si a b, pour tout c de A, on a : a + c b + c et c + a c + b  (et par conséquent a - c
    b - c).
  3. si on note A+ l'ensemble des éléments x de A tels que 0 x (éléments positifs de a : on peut aussi écrire, au moyen de l'ordre réciproque : x 0, alors :
0 x  et  0 y   0 xy.    (pour simplifier, xy désigne x x y)

Il en est ainsi, par exemple, du corps des nombres réels et de l'anneau des entiers relatifs.

  L'ensemble C des nombres complexes est totalement ordonné par l'ordre lexicographique usuel. C'est un ordre total :

si z = x + iy  et  z' = x' + iy' : z z'  (x < x')  ou  (x = x' et y y')

  Mais attention ! on parle ici de l'ensemble C. Il n'existe PAS d'ordre sur C lui conférant la structure de corps totalement ordonné : Vérifier cela en raisonnant par l'absurde, en montrant que le célèbre nombre i dont le carré est -1, serait alors à la fois positif et négatif !


Dans C, si z = x + iy et z' = x'+iy', on pose z z'  (x x'  et  y = y'). Montrer que muni de cette relation binaire,
C
est un corps ordonné mais non totalement ordonné (chercher à comparer 0 et i).

  Le seul ordre ordre total de Z, prolongeant celui de N est l'ordre usuel :

x ≤ y si et seulement si x - y N


On définit dans Z la relation binaire : x y y - x est pair. Prouver que muni de cette relation, (Z,+,x) est un anneau partiellement ordonné dans lequel les éléments positifs sont les nombres pairs.

On prouvera aisément les résultats suivants :

Proposition 1 :    

Dans un anneau ordonné (A,+,x) : x 0  et  a b   ax bx  et  xa xb

Proposition 2 :    

Dans un anneau ordonné (A,+,x), on a la règle des signes :

x 0 , y 0    xy 0    et   x 0 , y 0    xy 0

Proposition 3 :    

Dans un anneau totalement ordonné (A,+,x), on a x2 0 pour tout x (les carrés sont positifs).

Corollaire :    

Dans un anneau unitaire ordonné (A,+,x) d'élément neutre e, on a 1 0.

Proposition 4 :    

Dans un corps ordonné ordonné (K,+,x), soit x 0,et x' l'inverse de x, alors  x' 0.

Proposition 5 :   

Si un corps (K ,+, x) est ordonné, d'élément unité e 0, alors entre deux éléments a et b tels que a b, il existe une infinité d'éléments.

Par contraposition, on obtient le résultat suivant :

Un corps fini ne peut être ordonné

Preuve : Dans un corps, tout élément admet un inverse pour la multiplication : e désigne l'élément unité de K , pour tout a de K, il existe un unique a' tel que aa' = e, Ce qui peut être noté a/a' = e. La proposition est établie si on trouve au moins un élément c de K tel que a c b. Or, pareillement au cas de R avec la moyenne arithmétique de a et b, à savoir (a + b)/2, c'est à dire a + b multiplié par l'inverse de 2x1, choisissons c = (a + b)/(e +e) où e désigne l'élément unité de K. Notons u = e + e et u' l'inverse de u. On a c = (a + b)/u. On sait que e 0, donc u = e +e 0 et u' 0. Donc c - a = (a + b)/u - a = (a + b)u' - a est du signe de a + b -au en composant par u' : d'où a + b -au = a + b -a(e + e) = b - a  0. De même b - c 0. Finalement a c   b.

 En fait, on travaille dans un corps abstrait (K ,+, x) tout comme dans (R ,+, x) tout en prenant garde à l'ordre des éléments si k n'est pas commutatif. Cette remarque simplifie alors considérablement les calculs précédents.

  Là encore, rappelons qu'il faut distinguer l'ordre d'un ensemble E et la structure ordonnée de E comme dit ci-dessus. Prenons le cas particulier de l'anneau Z/11Z des classes résiduelles modulo 11 qui est un corps puisque 11 est premier. On peut bien sûr ordonner Z/11Z = {0, 1, 2, ..., 10} par x y si et seulement si x ≤ y. Mais Z/11Z N'EST PAS un corps ordonné ! On a 3 6. La proposition 1, par exemple, n'est pas vérifiée : multiplions les deux membres de cette inégalité par 2 : l'inégalité 23  26 est fausse, car 12 = 1 !


 Pour en savoir plus :


© Serge Mehl - www.chronomath.com