Ordre décroissant

Ordre décroissant

Relation d'ordre

Une relation d’ordre dans un ensemble E est une relation binaire dans cet ensemble qui permet de comparer ses éléments entre eux de manière cohérente. Un ensemble muni d’une relation d’ordre est un ensemble ordonné ou tout simplement un ordre.

Sommaire

Définitions et exemples

Relation d'ordre

Une relation d'ordre est une relation binaire réflexive, transitive et antisymétrique : soit E un ensemble et une relation binaire sur cet ensemble notée « ≤ », cette relation est une relation d'ordre si et seulement si pour tous x, y et z éléments de E :

  • xx (réflexivité)
  • (xy et yx) ⇒ x = y (antisymétrie)
  • (xy et yz) ⇒ xz (transitivité)

De par la forme même de ces axiomes, ceux-ci sont vérifiés par la relation inverse ou réciproque ≥, qui est définie par

xy si et seulement si yx.

À toute relation d'ordre est donc associée une relation d'ordre réciproque sur le même ensemble (plus petit ou égal / plus grand ou égal, inférieur ou égal / supérieur ou égal etc.). On associe également à toute relation d'ordre ≤, une relation dite d’ordre strict notée alors <, qui est la restriction de la relation d'ordre aux couples d'éléments distincts :

x < y si et seulement si xy et xy.

Une relation d'ordre au sens de la définition ci-dessus est parfois qualifiée d’ordre large.

Quand deux éléments de E sont toujours comparables pour l'ordre, c'est-à-dire que pour tous x, y de E :

xy ou yx

on dit que la relation d'ordre est totale, et que l'ensemble E est totalement ordonné par cette relation. Une relation d'ordre sur E est dite partielle si elle n'est pas totale, et E est alors partiellement ordonné.

Exemples et contre-exemples

  • La relation « est inférieur ou égal à » est une relation d'ordre total sur l'ensemble des entiers (naturels ou relatifs), sur l'ensemble des rationnels ou l'ensemble des réels.
  • La relation « est strictement inférieur à », par exemple sur l'ensemble des entiers naturels, n'est pas une relation d'ordre car elle n'est pas réflexive (une relation d'ordre strict n'est jamais un ordre large).
  • La relation de divisibilité est une relation d'ordre partiel sur les entiers naturels, mais ce n'est pas une relation d'ordre sur les entiers relatifs car elle n'est pas antisymétrique : 1 divise -1 et -1 divise 1.
  • La relation d'inclusion, « est un sous-ensemble de » ou « est contenu dans » est une relation d'ordre partiel sur l'ensemble des parties d'un ensemble.
  • On ne peut définir de façon satisfaisante une relation d'ordre sur le cercle qui signifierait « est placé avant ». Par exemple, sur l'ensemble des points du cercle trigonométrique (de centre O), la relation entre deux points M et N définie par « la mesure principale de l'angle ([OM),[ON)) » est positive ou nulle n'est pas une relation d'ordre car elle n'est pas transitive.
  • La relation « est le père de » sur un ensemble de personnes n'est pas une relation d'ordre car elle n'est pas transitive.
  • La relation ≤ définie sur l'ensemble des complexes par
\scriptstyle x \leq y   si et seulement si   \scriptstyle\mathrm{Re}(x) < \mathrm{Re}(y)\, ou \scriptstyle(\mathrm{Re}(x)=\mathrm{Re}(y)\, et \scriptstyle\mathrm{Im}(x)\le \mathrm{Im}(y))

est une relation d'ordre total. Elle n'est cependant pas compatible avec la structure de corps de l'ensemble des complexes.

Applications croissantes

Si (E, ≤E) et (F, ≤F) sont deux ensembles ordonnés, une application f de E dans F est dite croissante (ou parfois croissante au sens large) quand elle conserve l'ordre, décroissante (au sens large) quand elle inverse celui-ci, c'est-à-dire que :

f est croissante quand pour tous x et y de E,   xE yf(x) ≤F f(y).
f est décroissante quand pour tous x et y de E pour tous x et y de E,   xE yf(x) ≥F f(y).

Quand elle conserve l'ordre strict elle est strictement croissante : pour tous x et y de E,   x <E yf(x) <F f(y),

et strictement décroissante quand elle l'inverse : pour tous x et y de E,   x <E yf(x) >F f(y).

À noter qu'une application injective croissante est nécessairement strictement croissante.

Relation d'ordre strict

On a vu qu'à une relation d'ordre « ≤ » sur un ensemble donné, on associait naturellement une relation « < », dite d’ordre strict, définie sur le même ensemble, et obtenue en restreignant celle-ci aux couples d'éléments distincts. Il est tout à fait possible d'axiomatiser directement la notion d'ordre strict. Cela peut même s'avérer plus naturel dans certains cas.

Une relation d'ordre strict est une relation binaire irréflexive, et transitive : soit E un ensemble et une relation binaire sur cet ensemble notée <, cette relation est une relation d'ordre strict si et seulement si pour tous x, y et z éléments de E :

  • non (x < x) (irréflexivité)
  • (x < y et y < z) ⇒ x < z (transitivité)

On déduit immédiatement de ces deux propriétés qu'une relation d'ordre strict est antisymétrique. À dire vrai une relation d'ordre strict est antisymétrique en un sens plus fort qu'une relation d'ordre large, c’est-à-dire que pour tous x et y de l'ensemble support E :

  • x < y ⇒ non (y < x) (antisymétrie « forte »)

Cependant pour une relation irréflexive, comme les ordres stricts, cette propriété est équivalente à la propriété d'antisymétrie définie pour les ordres larges. Il n'y a donc pas d'inconvénient à parler d'antisymétrie dans les deux cas.

De même qu'à une relation d'ordre (large) on associait une relation d'ordre strict, à une relation d'ordre strict, soit « < », on associe naturellement une relation d'ordre large, soit « ≤ », définie par :

xy si et seulement si x < y ou x = y.

Choisir l'une ou l'autre des axiomatisations n'a pas d'importance en soi. Dans les deux cas on a défini un ordre large et un ordre strict associés. En effet on vérifie facilement, en utilisant les propriétés de l'égalité, que :

  • La relation d'ordre strict associée à une relation d'ordre large (transitive, réflexive et antisymétrique) vérifie bien les axiomes d'ordre stricts (elle est transitive et irréflexive).
  • La relation d'ordre large associée à une relation d'ordre strict (transitive et irréflexive) vérifie bien les axiomes d'ordre large (elle est transitive, réflexive et antisymétrique).
  • Il y a bien symétrie : étant données une relation d'ordre strict « < », et une relation d'ordre large « ≤ », « < » est associée à « ≤ » si et seulement si « ≤ » est associée à « < ».

Pour un ordre strict, la totalité s'exprime ainsi :

x, yE ( x < y ou x = y ou y < x ).

et on dit alors que c'est une relation d'ordre strict total. Il n'y a pas de confusion possible avec le sens précédent de relation totale, car une relation d'ordre strict, qui est irréflexive, ne peut être totale au sens où l'est un ordre large.

Pour un ordre strict total, les trois possibilités — x < y, x = y et y < x — sont exclusives, et l'on parle parfois, à la suite de Cantor, de propriété de trichotomie.

Propriétés complémentaires

Négation (ou complémentaire) d'une relation d'ordre

La négation d'une relation binaire R définie sur un ensemble A est la relation de graphe le complémentaire de celui de R dans A \times A. On la note \not\! R. Dit autrement, deux éléments sont en relation par \not\! R si et seulement s'ils ne le sont pas par R.

Dire qu'un ordre est total, c'est dire que sa négation est l'ordre strict inverse. C’est-à-dire qu'il y a équivalence pour un ordre \le\, entre :

  • \le\, est total ;
  • x \not\leq y \iff y < x

Par contre dès qu'il existe deux éléments distincts non comparables par un ordre, sa négation ne peut être un ordre (strict ou large), car elle n'est pas antisymétrique. La négation d'un ordre non total n'est donc jamais un ordre.

Par exemple, la négation de l'inclusion \not\subset sur l'ensemble des parties d'un ensemble d'au moins deux éléments n'est pas un ordre, car, si ab, on a \scriptstyle\{a\} \not\subset \{b\} et \scriptstyle\{b\} \not\subset \{a\}.

Compatibilité

Une relation d’ordre \mathbb{<} sur un ensemble E muni d’une loi de composition interne * est compatible avec cette loi si et seulement si :

\forall (x,y,z) \in E^3 , \quad  x \le y \Longrightarrow x * z \le y * z \;\wedge\; z * x \le z * y
  • La relation d'ordre \mathbb{<} sur l'ensemble des réels est compatible avec l'addition mais pas avec la multiplication.
  • La relation d'ordre \mathbb{<} sur l'ensemble des réels strictement positifs est compatible avec l'addition et la multiplication.
  • L’ensemble \mathbb{C} des nombres complexes n’est pas ordonnable par une relation d’ordre compatible avec les opérations d’addition et de multiplication.

Si un groupe est muni d'une relation d'ordre compatible avec sa loi interne, on l'appelle groupe ordonné.

Un groupe totalement ordonné vérifiant la propriété

\forall (x,y) \in (G_+)^2 , \quad  \exists n \in \mathbb N , \quad x \le n y

est dit archimédien.

Ensemble bien ordonné

Un ensemble ordonné est dit bien ordonné si toute partie non vide de cet ensemble possède un plus petit élément.

Treillis

Un ensemble est appelé treillis s'il est ordonné et que tout couple d'éléments possède une borne supérieure et une borne inférieure.

Diagramme de Hasse

Quand on travaille sur un ordre fini, il peut être agréable de disposer d’une représentation visuelle de celui-ci. On peut en proposer une qui est similaire à la représentation habituelle d’un graphe sur papier. C’est le diagramme de Hasse.

Notions dérivées

Pré-ordre

Un pré-ordre est une relation binaire réflexive et transitive.

On peut le considérer comme une relation d’ordre dans laquelle on autoriserait les cycles non triviaux (c’est-à-dire des cycles de plus d’un élément). Ajouter la condition d'anti-symétrie rend impossible la présence de ces cycles non triviaux.

Voir aussi

Wiktprintable without text.svg

Voir « comparabilité » sur le Wiktionnaire.

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Relation d%27ordre ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Ordre décroissant de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Methode Condorcet avec rangement des paires par ordre decroissant — Méthode Condorcet avec rangement des paires par ordre décroissant La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode… …   Wikipédia en Français

  • Méthode Condorcet Avec Rangement Des Paires Par Ordre Décroissant — La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode initialement proposée par Condorcet est développée par Tideman[1]. Sommaire 1 …   Wikipédia en Français

  • Méthode condorcet avec rangement des paires par ordre décroissant — La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode initialement proposée par Condorcet est développée par Tideman[1]. Sommaire 1 …   Wikipédia en Français

  • Méthode Condorcet avec rangement des paires par ordre décroissant — La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode initialement proposée par Condorcet est développée par Nicolaus Tideman[1].… …   Wikipédia en Français

  • décroissant — décroissant, ante [ dekrwasɑ̃, ɑ̃t ] adj. • 1276; de décroître ♦ Qui décroît. Par ordre décroissant. Vitesse décroissante. « des hauts, des bas, d amplitude décroissante » (Maurois). ♢ Math. Fonction décroissante, qui varie en sens contraire des… …   Encyclopédie Universelle

  • ordre — [ ɔrdr ] n. m. • 1080 sens II; lat. ordo, ordinis I ♦ (1155) Relation intelligible entre une pluralité de termes. ⇒ organisation, structure; économie. « L idée de la forme se confond avec l idée de l ordre » (A. Cournot). 1 ♦ Didact. Disposition …   Encyclopédie Universelle

  • Ordre de Sant'Iago de l'Épée — L Ordre de Sant Iago de l Épée (Ordem de Sant Iago da Espada) est un ordre qui vient d un ancien ordre militaire au Portugal, l Ordre militaire de Santiago (dit aussi Ordre militaire de Saint Jacques en français), éteint en 1910. C est en 1918… …   Wikipédia en Français

  • Ordre de l'Infant Dom Henri — L’ordre de l’Infant Dom Henri (portugais : Ordem do Infante Dom Henrique) est un ordre national portugais, créé le 2 juin 1960, en commémoration du 5e centenaire de la mort de l Infant, connu sous le nom d Henri le Navigateur. Des réformes… …   Wikipédia en Français

  • Ordre (biologie) — Pour les articles homonymes, voir Ordre. En biologie, l ordre est le quatrième niveau de classification classique des espèces vivantes (voir systématique). Terminaisons latines indiquant le rang Le nom des ordres se termine par le suffixe ales… …   Wikipédia en Français

  • Ordre du Saint-Sepulcre — Ordre du Saint Sépulcre Ordre du Saint Sépulcre de Jérusalem Armes de l ordre Nom Equestris Ordo Sancti Sepulcri Hierosolymitani Devise Deus lo vult Création Entre le 18 juillet et le 12  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”