Éducation Nationale Française · MP2I

Relations binaires

⌚ ~402 min ▢ 48 blocs ✓ 187 exercices PDFCours complet PDFFiche d'exercices PDFCorrections ➣ Prérequis : Ensembles

Vue d'ensemble du chapitre

Une relation binaire sur un ensemble $E$ décide, pour chaque couple $(x, y)$ d'éléments de $E$, si $x$ est en relation avec $y$. La première idée du chapitre est qu'une telle règle est un objet : la partie de $E \times E$ formée des couples en relation, comme une application du chapitre Applications est connue par son graphe. Quatre propriétés — réflexivité, symétrie, antisymétrie, transitivité — sont distinctes, une relation pouvant en avoir certaines et pas les autres, et deux de leurs combinaisons donnent les deux grandes familles de relations. La première famille identifie. Une relation d'équivalence dit que deux éléments sont les mêmes à un critère près : la parité d'un entier, le signe d'un réel, un angle à des tours complets près. Son fil est une phrase : une relation d'équivalence est toujours « avoir la même image par une application », ce que le chapitre démontre dans les deux sens. Les classes d'équivalence découpent l'ensemble en morceaux, et relations d'équivalence et partitions sont deux descriptions des mêmes objets. Les congruences, modulo un entier et modulo un réel, en sont le modèle, et chacune de leurs classes a un représentant que la partie entière trouve. La seconde famille compare. Une relation d'ordre peut être totale, comme $\le$ sur les réels, ou partielle, comme l'inclusion des ensembles ou la divisibilité des entiers ; elle donne un sens au plus grand élément d'une partie, à ses majorants, à sa borne supérieure, et aux applications qui respectent l'ordre.
Notations. Une relation s'écrit $\mathcal{R}$, et $x \, \mathcal{R} \, y$ signifie $(x, y) \in \mathcal{R}$ ; la diagonale de $E \times E$ est $\Delta_E = \{(x, x) \mid x \in E\}$. Une relation d'équivalence s'écrit $\sim$, la classe de $x$ est $\mathrm{cl}(x)$, aussi notée $\bar{x}$, et l'ensemble des classes est $\{\mathrm{cl}(x) \mid x \in E\}$. La congruence de deux entiers $a$ et $b$ modulo $n$ s'écrit $a \equiv b \ [n]$, et la même notation sert modulo un réel strictement positif $\alpha$ ; la classe de $x$ est $x + n\mathbb{Z}$, ou $x + \alpha\mathbb{Z}$. Une relation d'ordre quelconque s'écrit $\preccurlyeq$, le symbole $\le$ restant réservé aux nombres, et sa version stricte $\prec$ ; $\max A$, $\min A$, $\sup A$ et $\inf A$ désignent le plus grand élément, le plus petit élément, la borne supérieure et la borne inférieure d'une partie $A$. Un ordre qui n'est pas total est dit partiel. Comme dans le chapitre Ensembles, les éléments d'une partition sont ses morceaux, $\llbracket a, b \rrbracket$ est l'ensemble des entiers de $a$ à $b$, et $\emptyset$ est l'ensemble vide ; $\lfloor x \rfloor$ est la partie entière d'un réel $x$ ; $\mathbb{R}_+^*$ et $\mathbb{R}_-^*$ sont les ensembles des réels strictement positifs et des réels strictement négatifs, et $\mathbb{R}^* = \mathbb{R} \setminus \{0\}$. En français, « supérieur à » est large, et l'inégalité stricte s'écrit « strictement supérieur à ». Dans un ensemble listé, un $n$-uplet ou un intervalle, le séparateur est la virgule.

Signaler une erreur

Prérequis

Ce chapitre suppose connu le chapitre Ensembles : ensembles, inclusion et ses propriétés (la réflexivité de l'inclusion, les Propositions « Égalité par double inclusion » et « Transitivité de l'inclusion »), réunion, intersection et complémentaire (la Proposition « Propriétés du complémentaire »), la Proposition « Réunion et intersection comme bornes », la Proposition « Lois de la réunion et de l'intersection », la Proposition « L'ensemble vide est inclus dans tout ensemble », la Proposition « Inclusion caractérisée par réunion ou intersection », la Méthode « Lister les parties d'un ensemble fini », familles de parties, partitions (la Définition « Recouvrement disjoint, partition », la Proposition « Partitions élément par élément » et la Méthode « Démontrer qu'un ensemble de parties est une partition »), produit cartésien $E \times F$, ensemble $E^2$ et parties d'un produit, ensemble $\mathcal{P}(E)$, intervalles d'entiers, et description d'un ensemble par un paramètre. Il suppose connu le chapitre Applications : application, graphe, ensemble $F^E$ des applications de $E$ dans $F$ (en particulier $\mathbb{R}^{\mathbb{R}}$), restriction, image directe et image réciproque, fibres (la Proposition « Fibres d'une application »), composition, injection, surjection, bijection, la croissance de $A \mapsto f(A)$ et de $B \mapsto f^{-1}(B)$ pour l'inclusion (les Propositions « Image directe et opérations ensemblistes » et « Image réciproque et opérations ensemblistes »), et la Proposition « La stricte monotonie implique l'injectivité ». Des chapitres Raisonner et rédiger et Logique : les schémas de démonstration d'un énoncé universel ou existentiel, de l'unicité, par disjonction des cas, par contraposée, par l'absurde, par contre-exemple et par récurrence, les lois des connecteurs et des quantificateurs et leurs négations, et l'irrationalité de $\sqrt{2}$. Du chapitre Propriétés sur les nombres entiers : divisibilité, division euclidienne dans $\mathbb{Z}$, nombres premiers, décomposition en facteurs premiers, PGCD et PPCM. Du chapitre Radians et cercle unité : la Proposition « Réels ayant la même image » — deux réels ont la même image sur le cercle trigonométrique si et seulement si leur différence est un multiple de $2\pi$ — et les valeurs de $\cos$ et $\sin$ en $x + 2k\pi$. Du chapitre Dénombrement : les coefficients binomiaux. Les exemples et les exercices utilisent aussi : le calcul sur les réels (identités, inégalités, valeur absolue, racine carrée) ; les intervalles ; la partie entière $\lfloor x \rfloor$, l'entier $k$ tel que $k \le x < k + 1$, et le fait qu'un entier dépasse tout réel donné ; les fonctions usuelles (puissances, exponentielle, logarithme, cosinus, sinus) et le sens de variation d'une fonction lu sur le signe de sa dérivée ; les nombres complexes sous forme algébrique.

Signaler une erreur

I Relations binaires

I.1 Relations sur un ensemble

Répondre pour chaque couple

Comparer deux objets, les identifier ou les ordonner, c'est toujours répondre à une question sur un couple : $x$ est-il plus petit que $y$, $x$ divise-t-il $y$, $x$ et $y$ ont-ils la même parité ? Une relation binaire est une famille de telles réponses, une pour chaque couple d'éléments d'un ensemble. On étudie deux grandes familles de relations : celles qui identifient deux éléments, les relations d'équivalence, et celles qui les comparent, les relations d'ordre. Toutes deux se décrivent par les mêmes quatre propriétés, que chaque relation peut avoir ou non.

Signaler une erreur

Le graphe d'une relation

Quel objet mathématique est la relation $<$ sur l'ensemble $\llbracket 1, 3 \rrbracket$ ? Son contenu est entièrement donné par les couples $(x, y)$ pour lesquels $x < y$ : $(1, 2)$, $(1, 3)$ et $(2, 3)$. La relation est l'ensemble $\{(1, 2), (1, 3), (2, 3)\}$, une partie du produit $\llbracket 1, 3 \rrbracket^2$ du chapitre Ensembles. C'est le point de vue adopté : une relation est une partie d'un produit, de sorte que le vocabulaire des parties d'un produit — appartenance, inclusion, régions du plan lorsque l'ensemble est un ensemble de nombres — s'applique aux relations.

Signaler une erreur

Définition — Relation binaire

Soit $E$ un ensemble. Une relation binaire sur $E$ est une partie $\mathcal{R}$ du produit $E \times E$, noté aussi $E^2$. Pour $x, y \in E$, on écrit $x \, \mathcal{R} \, y$ pour $(x, y) \in \mathcal{R}$, lu « $x$ est en relation avec $y$ ». Une relation répond donc, pour chaque couple $(x, y)$, à la question « $x$ est-il en relation avec $y$ ? » : oui lorsque $(x, y) \in \mathcal{R}$, non sinon. La partie $\mathcal{R}$ de $E \times E$ est le graphe de la relation, comme le graphe $\Gamma_f$ d'une application $f$ est une partie de $E \times F$. Deux relations $\mathcal{R}$ et $\mathcal{S}$ sur $E$ sont égales si et seulement si elles ont les mêmes couples : $\forall (x, y) \in E^2, \ x \, \mathcal{R} \, y \iff x \, \mathcal{S} \, y$. Une relation est souvent donnée par un symbole placé entre les deux éléments, comme $=$, $\le$, $\mid$ ou $\sim$, et le couple n'est pas écrit.

Exemple — Les graphes de quatre relations

Quatre relations, dessinées par leurs graphes ; sur chaque dessin la diagonale, formée des couples $(x, x)$, est en pointillés. La première est la divisibilité $x \mid y$ sur $E = \llbracket 1, 4 \rrbracket$ : son graphe est un ensemble fini de points de la grille, les huit couples $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 2)$, $(2, 4)$, $(3, 3)$ et $(4, 4)$. Les trois autres sont des relations sur $E = \mathbb{R}$, dont les graphes sont des régions ou des courbes du plan $\mathbb{R}^2$ : le graphe de $x \le y$ est le demi-plan au-dessus de la diagonale, celui de $\lvert x - y \rvert \le 1$ est la bande comprise entre les droites d'équations $y = x - 1$ et $y = x + 1$, et celui de $x^2 = y^2$ est la réunion des droites d'équations $y = x$ et $y = -x$.

Un couple $(x, y)$ est en relation lorsque le point d'abscisse $x$ et d'ordonnée $y$ est dans le graphe. L'énoncé « $x \, \mathcal{R} \, y$ » n'est pas l'énoncé « $y \, \mathcal{R} \, x$ », le couple étant ordonné : $(1, 2)$ est dans le graphe de la divisibilité, car $1 \mid 2$, alors que $(2, 1)$ n'y est pas, car $2 \nmid 1$ ; de même $(0, 1)$ est dans le graphe de $x \le y$ et $(1, 0)$ n'y est pas. Les relations $\lvert x - y \rvert \le 1$ et $x^2 = y^2$ valent dans les deux sens à la fois, puisque $\lvert y - x \rvert = \lvert x - y \rvert$ et $x^2 = y^2 \iff y^2 = x^2$ : leurs graphes ne changent pas lorsque le plan est symétrisé par rapport à la diagonale.

Compétences à pratiquer

Lire une relation sur son graphe ★
Compter les couples d'une relation ★

I.2 Propriétés d'une relation

Quatre questions sur une relation

Une relation, comme simple partie de $E \times E$, dit peu de chose. Ce qui la rend utile, ce sont les questions que l'on peut se poser à son sujet, et quatre comptent : chaque élément est-il en relation avec lui-même, la relation est-elle la même lue de gauche à droite et de droite à gauche, deux éléments distincts peuvent-ils être en relation dans les deux sens, une chaîne de deux relations en donne-t-elle toujours une troisième ? Chaque question est un énoncé sur tous les éléments, ou tous les couples, ou tous les triplets de $E$. Aucun des quatre énoncés ne découle d'un seul autre, comme le montrent l'Exemple « Sept relations et leurs propriétés » et le Piège « antisymétrique ne veut pas dire non symétrique ». Deux d'entre eux ensemble peuvent cependant imposer le troisième : une relation à la fois symétrique et antisymétrique est contenue dans la diagonale, et elle est donc transitive, comme le démontre ce même Piège.

Signaler une erreur

Définition — Réflexive, symétrique, antisymétrique, transitive

Soit $\mathcal{R}$ une relation binaire sur un ensemble $E$. La relation $\mathcal{R}$ est :

réflexive si $\forall x \in E, \ x \, \mathcal{R} \, x$ ;
symétrique si $\forall (x, y) \in E^2, \ x \, \mathcal{R} \, y \Rightarrow y \, \mathcal{R} \, x$ ;
antisymétrique si $\forall (x, y) \in E^2, \ (x \, \mathcal{R} \, y \text{ et } y \, \mathcal{R} \, x) \Rightarrow x = y$ ;
transitive si $\forall (x, y, z) \in E^3, \ (x \, \mathcal{R} \, y \text{ et } y \, \mathcal{R} \, z) \Rightarrow x \, \mathcal{R} \, z$.

Ces propriétés se lisent sur le graphe. La diagonale de $E$ est la partie $\Delta_E = \{(x, x) \mid x \in E\}$ de $E \times E$. La relation est réflexive si et seulement si $\Delta_E \subset \mathcal{R}$, puisque $\Delta_E \subset \mathcal{R}$ signifie $(x, x) \in \mathcal{R}$ pour tout $x \in E$. Elle est symétrique si et seulement si l'image miroir $(y, x)$ de chaque couple $(x, y)$ de son graphe, par rapport à la diagonale, est aussi dans son graphe. Elle est antisymétrique si et seulement si les seuls couples de son graphe dont l'image miroir est aussi dans son graphe sont les couples de la diagonale.

Exemple — Sept relations et leurs propriétés

Les propriétés de sept relations sont résumées dans un tableau ; R, S, A et T désignent réflexive, symétrique, antisymétrique et transitive. « Même parité » signifie « tous deux pairs ou tous deux impairs ».

relation	R	S	A	T
$=$ sur un ensemble $E$	oui	oui	oui	oui
$\le$ sur $\mathbb{R}$	oui	non	oui	oui
$<$ sur $\mathbb{R}$	non	non	oui	oui
$\mid$ sur $\mathbb{N}$	oui	non	oui	oui
$\mid$ sur $\mathbb{Z}$	oui	non	non	oui
même parité sur $\mathbb{Z}$	oui	oui	non	oui
$\ne$ sur $\mathbb{R}$	non	oui	non	non

Chaque « non » est établi par un contre-exemple, dont les éléments sont donnés :

$\le$ n'est pas symétrique : $1 \le 2$, mais $2 \le 1$ est faux.
$<$ n'est pas réflexive, puisque $1 < 1$ est faux, ni symétrique : $1 < 2$, mais $2 < 1$ est faux. Elle est antisymétrique à vide : aucun couple $(x, y)$ ne vérifie à la fois $x < y$ et $y < x$, donc l'implication « $(x < y \text{ et } y < x) \Rightarrow x = y$ » est vraie pour tout couple.
$\mid$ sur $\mathbb{N}$ n'est pas symétrique : $1 \mid 2$, mais $2 \nmid 1$.
$\mid$ sur $\mathbb{Z}$ n'est pas symétrique, pour la même raison, ni antisymétrique : $2 \mid -2$ et $-2 \mid 2$, mais $2 \ne -2$.
« Même parité » n'est pas antisymétrique : $2$ et $4$ ont la même parité, et $2 \ne 4$.
$\ne$ n'est pas réflexive, puisque $1 \ne 1$ est faux, ni antisymétrique : $1 \ne 2$ et $2 \ne 1$, mais $1 = 2$ est faux, ni transitive : $1 \ne 2$ et $2 \ne 1$, mais $1 \ne 1$ est faux.

Chaque « oui » se vérifie à partir de la définition de la relation, comme le décrit la Méthode « Démontrer ou réfuter une propriété d'une relation ». Prenons la divisibilité sur $\mathbb{N}$, où $a \mid b$ signifie que $b = ka$ pour un certain $k \in \mathbb{N}$ :

Réflexivité. Soit $a \in \mathbb{N}$. Alors $a = 1 \times a$, donc $a \mid a$.
Transitivité. Soient $a, b, c \in \mathbb{N}$ tels que $a \mid b$ et $b \mid c$ : $b = ka$ et $c = \ell b$ avec $k, \ell \in \mathbb{N}$. Alors $$ \begin{aligned} c &= \ell b && \text{(hypothèse $b \mid c$)} \\ &= \ell(ka) && \text{(hypothèse $b = ka$)} \\ &= (\ell k)a, \end{aligned} $$ la dernière égalité par l'associativité du produit, avec $\ell k \in \mathbb{N}$, donc $a \mid c$.
Antisymétrie. Soient $a, b \in \mathbb{N}$ tels que $a \mid b$ et $b \mid a$ : $b = ka$ et $a = \ell b$ avec $k, \ell \in \mathbb{N}$. Alors $$ \begin{aligned} b &= ka && \text{(hypothèse $a \mid b$)} \\ &= k(\ell b) && \text{(hypothèse $b \mid a$, c'est-à-dire $a = \ell b$)} \\ &= (k\ell)b, \end{aligned} $$ la dernière égalité par l'associativité du produit. Si $b = 0$, alors $$ \begin{aligned} a &= \ell b && \text{(hypothèse $a = \ell b$)} \\ &= 0 && \text{(car $b = 0$)} \\ &= b. \end{aligned} $$ Si $b \ne 0$, alors $b = (k\ell)b$ donne $k\ell = 1$ après division par $b$, donc $k = \ell = 1$, deux entiers naturels de produit $1$ étant tous deux égaux à $1$, et $$ \begin{aligned} a &= \ell b && \text{(hypothèse $a = \ell b$)} \\ &= 1 \times b && \text{(car $\ell = 1$)} \\ &= b. \end{aligned} $$ Dans les deux cas $a = b$.

Méthode — Démontrer ou réfuter une propriété d'une relation

Pour décider si une relation $\mathcal{R}$ sur un ensemble $E$ a l'une des quatre propriétés, la démontrer ou la réfuter :

Pour démontrer une propriété, qui est un énoncé universel, introduire des éléments génériques, par la Méthode « Démontrer une proposition universelle » : $x \in E$ pour la réflexivité ; $x, y \in E$ avec l'hypothèse $x \, \mathcal{R} \, y$ pour la symétrie ; $x, y \in E$ avec les hypothèses $x \, \mathcal{R} \, y$ et $y \, \mathcal{R} \, x$ pour l'antisymétrie, où la conclusion est l'égalité $x = y$ ; $x, y, z \in E$ avec les hypothèses $x \, \mathcal{R} \, y$ et $y \, \mathcal{R} \, z$ pour la transitivité. Traduire chaque hypothèse par la définition de la relation et mener le calcul jusqu'à la conclusion.
Pour réfuter une propriété, donner un contre-exemple, la négation d'un énoncé universel étant un énoncé existentiel (la Proposition « Négation des quantificateurs ») : un élément $x$ tel que $x \, \mathcal{R} \, x$ soit faux, pour la réflexivité ; un couple avec $x \, \mathcal{R} \, y$ et non $y \, \mathcal{R} \, x$, pour la symétrie ; un couple d'éléments distincts avec $x \, \mathcal{R} \, y$ et $y \, \mathcal{R} \, x$, pour l'antisymétrie ; un triplet avec $x \, \mathcal{R} \, y$, $y \, \mathcal{R} \, z$ et non $x \, \mathcal{R} \, z$, pour la transitivité. Les éléments choisis sont donnés et les deux membres sont vérifiés, comme dans la Méthode « Réfuter une implication ».
Pour deviner la réponse, lire le graphe : la diagonale pour la réflexivité, la symétrie par rapport à la diagonale pour la symétrie et l'antisymétrie.

Par exemple, soit $x \, \mathcal{R} \, y \iff x^2 \le y^2$ sur $\mathbb{R}$. Elle est réflexive, puisque $x^2 \le x^2$. Elle est transitive : $x^2 \le y^2$ et $y^2 \le z^2$ donnent $x^2 \le z^2$, par la transitivité de $\le$. Elle n'est pas symétrique : $0^2 \le 1^2$, mais $1^2 \le 0^2$ est faux. Elle n'est pas antisymétrique : $(-1)^2 \le 1^2$ et $1^2 \le (-1)^2$, mais $-1 \ne 1$.

Piège — antisymétrique ne veut pas dire non symétrique

« Antisymétrique » n'est pas le contraire de « symétrique ». Les deux propriétés ne sont pas complémentaires : une relation peut avoir les deux, ou aucune. L'égalité est à la fois symétrique et antisymétrique. La relation $\{(1, 2), (2, 1), (1, 3)\}$ sur $\{1, 2, 3\}$ n'est ni l'une ni l'autre : elle n'est pas symétrique, puisque $(1, 3)$ en fait partie et pas $(3, 1)$, et elle n'est pas antisymétrique, puisque $(1, 2)$ et $(2, 1)$ en font partie et que $1 \ne 2$. Une relation n'est pas antisymétrique parce qu'elle n'est pas symétrique : il faut vérifier la définition.
Une relation à la fois symétrique et antisymétrique est contenue dans la diagonale, et elle est donc transitive. Soit $\mathcal{R}$ une telle relation sur $E$. Pour $(x, y) \in \mathcal{R}$, la symétrie donne $y \, \mathcal{R} \, x$, donc $x \, \mathcal{R} \, y$ et $y \, \mathcal{R} \, x$ sont vraies ensemble et l'antisymétrie donne $x = y$ : le couple $(x, y)$ est le couple $(x, x)$ de la diagonale $\Delta_E$, d'où $\mathcal{R} \subset \Delta_E$. Pour la transitivité, soient $x \, \mathcal{R} \, y$ et $y \, \mathcal{R} \, z$. La première relation donne $x = y$, donc la seconde s'écrit $x \, \mathcal{R} \, z$. Ainsi la transitivité découle de la symétrie et de l'antisymétrie prises ensemble. Elle ne découle d'aucune des trois autres propriétés prise seule. La relation $\ne$ sur $\mathbb{R}$ de l'Exemple « Sept relations et leurs propriétés » est symétrique et n'est pas transitive. La relation $\mathcal{S}$ sur $\{1, 2, 3\}$ dont le graphe est $\Delta_{\{1, 2, 3\}} \cup \{(1, 2), (2, 3)\}$ est réflexive, et antisymétrique puisque les images miroirs $(2, 1)$ et $(3, 2)$ de ses couples $(1, 2)$ et $(2, 3)$ n'en font pas partie, mais elle n'est pas transitive : $1 \, \mathcal{S} \, 2$ et $2 \, \mathcal{S} \, 3$, alors que $1 \, \mathcal{S} \, 3$ est faux.

Signaler une erreur

Compétences à pratiquer

Reconnaître les propriétés d'une relation ★
Décider les propriétés d'une relation ★
Démontrer ou réfuter une propriété d'une relation ★★
Combiner les propriétés des relations ★★★

II Relations d'équivalence

II.1 Relations d'équivalence et applications

Identifier à un critère près

Les relations d'équivalence sont la plus faible identification raisonnable : elles permettent de dire que $x$ et $y$ sont les mêmes à un critère choisi près, sans imposer aucune autre structure. Les trois axiomes — réflexivité, symétrie, transitivité — expriment exactement ce que l'on attend d'une identification : tout $x$ est identifié à lui-même, l'identification est à double sens, et les chaînes d'identifications se contractent. Trois faits sont établis à leur sujet. Les éléments identifiés à un élément donné forment sa classe. Les classes découpent l'ensemble en morceaux disjoints : elles forment une partition, et toute partition s'obtient ainsi. Et une relation d'équivalence est toujours « avoir la même image par une application », ce qui est aussi le moyen le plus rapide de démontrer qu'une relation est une relation d'équivalence.

Signaler une erreur

Un raccourci pour les trois axiomes

Pour montrer qu'une relation est une relation d'équivalence, on vérifie les trois axiomes un par un, sur des éléments génériques. Il existe souvent un raccourci : lorsque deux éléments sont en relation exactement quand ils ont la même image par une certaine application, les trois axiomes sont la réflexivité, la symétrie et la transitivité de l'égalité, et ils sont vrais sans autre vérification. La Proposition « La relation d'équivalence d'une application » le dit, et la Méthode « Démontrer une équivalence par une application » en fait une procédure.

Signaler une erreur

Définition — Relation d'équivalence

Une relation binaire $\mathcal{R}$ sur $E$ est une relation d'équivalence si elle est réflexive, symétrique et transitive. On note souvent les relations d'équivalence par des symboles comme $\sim$, $\equiv$, $\approx$.

Méthode — Démontrer qu'une relation est une relation d'équivalence

Pour démontrer qu'une relation $\sim$ sur un ensemble $E$ est une relation d'équivalence, deux voies :

Les trois axiomes, chacun sur des éléments génériques, par la Méthode « Démontrer une proposition universelle » : réflexivité, pour tout $x \in E$, $x \sim x$ ; symétrie, pour tous $x, y \in E$, si $x \sim y$ alors $y \sim x$ ; transitivité, pour tous $x, y, z \in E$, si $x \sim y$ et $y \sim z$ alors $x \sim z$.
Le raccourci par une application : mettre la relation sous la forme $f(x) = f(y)$ pour une application $f$ définie sur $E$, et conclure par la Proposition « La relation d'équivalence d'une application » ; la Méthode « Démontrer une équivalence par une application » le décrit.

Une relation qui ne vérifie pas l'un au moins des trois axiomes n'est pas une relation d'équivalence : l'ordre $\le$ sur $\mathbb{R}$ est réflexif et transitif mais pas symétrique ; l'ordre strict $<$ est transitif mais ni réflexif ni symétrique ; et une relation peut être réflexive et symétrique sans être transitive, comme le montre l'Exemple « Signe, parité et diviseurs communs ».

Exemple — Signe, parité et diviseurs communs

Trois relations, les deux premières étant des relations d'équivalence et la troisième non.

Même signe sur $\mathbb{R}^*$. Deux réels non nuls $x$ et $y$ sont en relation, $x \sim y$, lorsqu'ils sont tous deux strictement positifs ou tous deux strictement négatifs. Réflexivité : $x$ et $x$ sont tous deux strictement positifs ou tous deux strictement négatifs. Symétrie : la condition « tous deux strictement positifs ou tous deux strictement négatifs » ne dépend pas de l'ordre de $x$ et $y$. Transitivité : soient $x \sim y$ et $y \sim z$. Si $y > 0$, alors $x > 0$ et $z > 0$ ; si $y < 0$, alors $x < 0$ et $z < 0$. Comme $y \ne 0$, ces deux cas couvrent toutes les possibilités, et dans les deux $x \sim z$.
Même parité sur $\mathbb{Z}$. Deux entiers $x$ et $y$ sont en relation, $x \sim y$, lorsqu'ils sont tous deux pairs ou tous deux impairs. La réflexivité et la symétrie se vérifient comme ci-dessus. Transitivité : soient $x \sim y$ et $y \sim z$. Si $y$ est pair, alors $x$ et $z$ sont pairs ; si $y$ est impair, alors $x$ et $z$ sont impairs. Dans les deux cas $x \sim z$.
Diviseurs communs sur les entiers $x \ge 2$. Deux entiers $x, y \ge 2$ sont en relation, $x \, \mathcal{R} \, y$, lorsqu'ils ont un diviseur commun strictement supérieur à $1$. La relation est réflexive, puisque $x$ divise $x$ et que $x \ge 2$, et symétrique, puisque la condition est la même pour $x$ et $y$ dans un ordre ou dans l'autre. Elle n'est pas transitive : $2 \, \mathcal{R} \, 6$, puisque $2$ divise les deux ; $6 \, \mathcal{R} \, 3$, puisque $3$ divise les deux ; mais $2 \, \mathcal{R} \, 3$ est faux, puisque les diviseurs de $2$ sont $1$ et $2$, et que $2$ ne divise pas $3$, de sorte que le seul diviseur commun de $2$ et $3$ est $1$. Ce n'est pas une relation d'équivalence.

Proposition — La relation d'équivalence d'une application

Soit $f \colon E \to F$ une application. La relation $\sim_f$ sur $E$ définie par $$ x \sim_f y \iff f(x) = f(y) $$ est une relation d'équivalence. Deux éléments sont en relation exactement lorsqu'ils ont la même image par $f$.

Preuve

On applique la Méthode « Démontrer qu'une relation est une relation d'équivalence » : les trois axiomes sont ceux de l'égalité dans $F$, transportés par $f$.

Réflexivité. Soit $x \in E$. Alors $f(x) = f(x)$, donc $x \sim_f x$.
Symétrie. Soient $x, y \in E$ tels que $x \sim_f y$. Alors $f(x) = f(y)$, donc $f(y) = f(x)$, c'est-à-dire $y \sim_f x$.
Transitivité. Soient $x, y, z \in E$ tels que $x \sim_f y$ et $y \sim_f z$. Alors $$ \begin{aligned} f(x) &= f(y) && \text{(hypothèse $x \sim_f y$)} \\ &= f(z), \end{aligned} $$ la dernière égalité par l'hypothèse $y \sim_f z$. Donc $x \sim_f z$.

La relation $\sim_f$ est réflexive, symétrique et transitive : c'est une relation d'équivalence.

Méthode — Démontrer une équivalence par une application

Pour démontrer qu'une relation $\sim$ sur un ensemble $E$ est une relation d'équivalence par une application :

Transformer la relation $x \sim y$, par équivalences, jusqu'à la forme $f(x) = f(y)$, avec $x$ seul d'un côté et $y$ seul de l'autre.
Nommer l'application : sa règle $x \mapsto f(x)$, son ensemble de départ $E$ et son ensemble d'arrivée ; $f$ doit être définie en tout élément de $E$.
Conclure par la Proposition « La relation d'équivalence d'une application » : $\sim$ est la relation de $f$, donc une relation d'équivalence, et ses classes seront les fibres de $f$. Aucun axiome n'est plus à vérifier.

Lorsque l'on ne trouve aucune application $f$ explicite, on vérifie les trois axiomes à la main, par la Méthode « Démontrer qu'une relation est une relation d'équivalence ».
Par exemple, sur $E = \mathbb{R}^2$, soit $(x, y) \sim (x', y') \iff x^2 - x'^2 = y'^2 - y^2$. En ajoutant $x'^2 + y^2$ aux deux membres, cela s'écrit $x^2 + y^2 = x'^2 + y'^2$, c'est-à-dire $f(x, y) = f(x', y')$ pour l'application $f \colon \mathbb{R}^2 \to \mathbb{R}$, $(x, y) \mapsto x^2 + y^2$, définie sur tout $\mathbb{R}^2$. Donc $\sim$ est la relation de $f$ : une relation d'équivalence, sans aucun axiome à vérifier.

Compétences à pratiquer

Reconnaître une relation d'équivalence ★
Décider si une relation est une relation d'équivalence ★
Démontrer une équivalence par une application ★★
Construire des relations d'équivalence ★★★

II.2 Classes d'équivalence

Regrouper ce qui est identifié

Une relation d'équivalence identifie des éléments, et la question naturelle est alors de savoir quels éléments sont identifiés à un élément donné. La réponse est sa classe. Une classe est une partie de $E$, et les classes de tous les éléments forment un ensemble dont les éléments sont des parties, comme dans le chapitre Ensembles. Deux propriétés sont attendues, et la Proposition « Comparer deux classes » les démontre : une classe n'est jamais vide, et deux classes sont égales ou disjointes. Une classe peut être nommée par n'importe lequel de ses éléments, ses représentants, et choisir un représentant dans chaque classe donne un système de représentants.

Signaler une erreur

Définition — Classe d'équivalence

Soient $\sim$ une relation d'équivalence sur un ensemble $E$ et $x \in E$. La classe d'équivalence de $x$ pour $\sim$ est l'ensemble $$ \mathrm{cl}(x) = \{y \in E \mid x \sim y\}, $$ notée aussi $\bar{x}$. Un représentant d'une classe $C$ est un élément $x \in E$ tel que $C = \mathrm{cl}(x)$. L'ensemble des classes de $\sim$ est $\{\mathrm{cl}(x) \mid x \in E\}$ : un ensemble de parties de $E$, décrit par un paramètre, comme dans la Définition « Extension, compréhension ». Plusieurs éléments $x$ peuvent donner la même classe, qui n'est alors écrite qu'une fois.

Proposition — Comparer deux classes

Soit $\sim$ une relation d'équivalence sur un ensemble $E$.

Tout élément appartient à sa classe : $x \in \mathrm{cl}(x)$ pour tout $x \in E$ ; en particulier, une classe n'est jamais vide.
Deux classes se comparent par leurs éléments : pour tous $x, y \in E$, les quatre énoncés $$ x \sim y, \qquad y \in \mathrm{cl}(x), \qquad \mathrm{cl}(x) = \mathrm{cl}(y), \qquad \mathrm{cl}(x) \cap \mathrm{cl}(y) \ne \emptyset $$ sont équivalents.

Par conséquent deux classes sont égales ou disjointes, et tout élément d'une classe en est un représentant.

Preuve

Première démonstration : un cycle d'implications. Soit $x \in E$. Par réflexivité, $x \sim x$, donc $x \in \mathrm{cl}(x)$, par la définition de la classe. Soient maintenant $x, y \in E$. L'équivalence de $x \sim y$ et de $y \in \mathrm{cl}(x)$ est la définition de $\mathrm{cl}(x)$. On démontre le cycle d'implications $x \sim y \Rightarrow \mathrm{cl}(x) = \mathrm{cl}(y) \Rightarrow \mathrm{cl}(x) \cap \mathrm{cl}(y) \ne \emptyset \Rightarrow x \sim y$, qui rend ces trois énoncés équivalents.

Supposons $x \sim y$. Alors $y \sim x$ par symétrie, et pour tout $z \in E$ $$ \begin{aligned} z \in \mathrm{cl}(x) &\iff x \sim z && \text{(définition de la classe)} \\ &\iff y \sim z && \text{(transitivité, dans les deux sens)} \\ &\iff z \in \mathrm{cl}(y), \end{aligned} $$ la dernière équivalence par la définition de la classe. Celle du milieu est vraie car $y \sim x$ et $x \sim z$ donnent $y \sim z$, et $x \sim y$ et $y \sim z$ donnent $x \sim z$. Donc $\mathrm{cl}(x)$ et $\mathrm{cl}(y)$ ont les mêmes éléments : $\mathrm{cl}(x) = \mathrm{cl}(y)$.
Supposons $\mathrm{cl}(x) = \mathrm{cl}(y)$. Alors $\mathrm{cl}(x) \cap \mathrm{cl}(y) = \mathrm{cl}(x)$, qui contient $x$, comme on l'a montré au début : elle est non vide.
Supposons $\mathrm{cl}(x) \cap \mathrm{cl}(y) \ne \emptyset$, et soit $z$ un élément de cette intersection : $x \sim z$ et $y \sim z$. Par symétrie $z \sim y$, et de $x \sim z$ et $z \sim y$ la transitivité donne $x \sim y$.

Les conséquences. Si deux classes $\mathrm{cl}(x)$ et $\mathrm{cl}(y)$ ne sont pas disjointes, elles sont égales, par l'équivalence du quatrième et du troisième énoncé. Si $y \in \mathrm{cl}(x)$, alors $\mathrm{cl}(y) = \mathrm{cl}(x)$, par l'équivalence du deuxième et du troisième énoncé, donc $y$ est un représentant de $\mathrm{cl}(x)$.
Seconde démonstration : par double inclusion, à partir de l'énoncé « $y \in \mathrm{cl}(x)$ ». L'équivalence de $x \sim y$ et de $y \in \mathrm{cl}(x)$ est la définition. Si $\mathrm{cl}(x) = \mathrm{cl}(y)$, alors $y \in \mathrm{cl}(y) = \mathrm{cl}(x)$, puisque $y \in \mathrm{cl}(y)$. Si $y \in \mathrm{cl}(x)$, c'est-à-dire $x \sim y$, alors tout $z \in \mathrm{cl}(y)$ donne $y \sim z$, donc $x \sim z$ par transitivité, d'où $\mathrm{cl}(y) \subset \mathrm{cl}(x)$ ; la symétrie donne $y \sim x$ et le même argument donne $\mathrm{cl}(x) \subset \mathrm{cl}(y)$, donc $\mathrm{cl}(x) = \mathrm{cl}(y)$ par la Proposition « Égalité par double inclusion ». Le troisième énoncé est donc équivalent au deuxième. Enfin le quatrième est équivalent au deuxième : si $y \in \mathrm{cl}(x)$, alors $y \in \mathrm{cl}(x) \cap \mathrm{cl}(y)$, qui est non vide ; et si $z \in \mathrm{cl}(x) \cap \mathrm{cl}(y)$, alors $x \sim z$ et $y \sim z$, donc $z \sim y$ et $x \sim y$, c'est-à-dire $y \in \mathrm{cl}(x)$.

Exemple — Des cercles et des signes

Pour la relation $\sim_f$ d'une application $f \colon E \to F$, la classe d'un élément $x$ est une fibre de $f$ : $$ \begin{aligned} \mathrm{cl}(x) &= \{y \in E \mid f(x) = f(y)\} && \text{(définitions de la classe et de $\sim_f$)} \\ &= \{y \in E \mid f(y) \in \{f(x)\}\} && \text{(appartenance à un singleton)} \\ &= f^{-1}(\{f(x)\}), \end{aligned} $$ la dernière égalité par la définition de l'image réciproque. La Proposition « Fibres d'une application » du chapitre Applications montre que les fibres non vides d'une application partitionnent son ensemble de départ.
Par exemple, soit $\sim$ la relation sur $\mathbb{R}^2$ définie par $(x, y) \sim (x', y') \iff x^2 + y^2 = x'^2 + y'^2$, la relation de l'application $f \colon \mathbb{R}^2 \to \mathbb{R}$, $(x, y) \mapsto x^2 + y^2$. La classe d'un point $P = (a, b)$ se calcule de la même façon : $$ \begin{aligned} \mathrm{cl}(P) &= f^{-1}(\{f(P)\}) && \text{(la classe est une fibre de $f$)} \\ &= \{(x, y) \in \mathbb{R}^2 \mid f(x, y) = f(P)\} && \text{(image réciproque)} \\ &= \{(x, y) \in \mathbb{R}^2 \mid x^2 + y^2 = a^2 + b^2\}, \end{aligned} $$ la dernière égalité par la définition de $f$. Cet ensemble est le cercle de centre $O = (0, 0)$ et de rayon $\sqrt{a^2 + b^2}$, réduit au point $O$ lorsque $(a, b) = (0, 0)$.

Les classes sont le point $O$ et les cercles de centre $O$ et de rayon strictement positif. Elles forment une partition du plan, comme le font toujours les fibres d'une application : tout point autre que $O$ est sur exactement un cercle de centre $O$, et le point $O$ forme à lui seul une classe.
Pour la relation « même signe » sur $\mathbb{R}^*$, la classe de $1$ est $$ \begin{aligned} \mathrm{cl}(1) &= \{y \in \mathbb{R}^* \mid 1 \sim y\} && \text{(définition de la classe)} \\ &= \{y \in \mathbb{R}^* \mid y > 0\} && \text{($y$ a le signe de $1$ si et seulement si $y > 0$)} \\ &= \mathbb{R}_+^*, \end{aligned} $$ et la classe de $-1$ est $\mathrm{cl}(-1) = \mathbb{R}_-^*$. Un réel strictement positif $x$ vérifie $x \sim 1$, donc $\mathrm{cl}(x) = \mathrm{cl}(1)$ par la Proposition « Comparer deux classes » ; de même $\mathrm{cl}(x) = \mathrm{cl}(-1)$ pour $x < 0$. Il y a exactement deux classes.

Définition — Système de représentants

Soit $\sim$ une relation d'équivalence sur un ensemble $E$. Une partie $R$ de $E$ est un système de représentants de $\sim$ si elle contient exactement un élément de chaque classe : pour tout $x \in E$, il existe exactement un $r \in R$ tel que $r \in \mathrm{cl}(x)$, c'est-à-dire tel que $x \sim r$. Un système de représentants n'est en général pas unique. Pour la relation $x^2 + y^2 = x'^2 + y'^2$ sur $\mathbb{R}^2$, dont les classes sont le point $O$ et les cercles de centre $O$, la demi-droite $\{(r, 0) \mid r \ge 0\}$ est un système de représentants : le cercle de rayon $r > 0$ ne la rencontre qu'en $(r, 0)$, et la classe $\{O\}$ qu'en $(0, 0)$. Pour la relation « même signe » sur $\mathbb{R}^*$, la partie $\{-1, 1\}$ est un système de représentants, et $\{-\pi, \sqrt{2}\}$ en est un aussi.

Méthode — Déterminer les classes d'une relation d'équivalence

Pour déterminer les classes d'une relation d'équivalence $\sim$ sur un ensemble $E$ :

Fixer un élément générique $x \in E$ et résoudre la condition $x \sim y$ d'inconnue $y$ : la classe de $x$ est l'ensemble de ses solutions. Lorsque $\sim$ est la relation d'une application $f$, cet ensemble est la fibre $f^{-1}(\{f(x)\})$.
Distinguer les cas où l'ensemble des solutions change d'allure, souvent une valeur particulière de $x$ pour laquelle deux solutions se confondent ou l'une disparaît.
Décrire toutes les classes par un système de représentants : lister les classes trouvées, une pour chaque représentant, et vérifier que tout élément de $E$ est dans l'une d'elles — la réflexivité — et dans une seule, par la Proposition « Comparer deux classes ».

Par exemple, soit $x \sim y \iff \max(x, 0) = \max(y, 0)$ sur $\mathbb{R}$, la relation de l'application $x \mapsto \max(x, 0)$ : « $x$ et $y$ ont la même partie positive ». Fixons $x \in \mathbb{R}$ et résolvons $x \sim y$. Si $x \le 0$, alors $\max(x, 0) = 0$, et $$ \begin{aligned} x \sim y &\iff \max(x, 0) = \max(y, 0) && \text{(définition de $\sim$)} \\ &\iff \max(y, 0) = 0 && \text{(car $\max(x, 0) = 0$)} \\ &\iff y \le 0, \end{aligned} $$ la dernière équivalence car $\max(y, 0) = 0$ signifie $y \le 0$ : la classe de $x$ est $\, ]-\infty, 0]$. Si $x > 0$, alors $\max(x, 0) = x > 0$, donc $\max(y, 0) = x$ force $y > 0$, d'où $\max(y, 0) = y$ et $y = x$ : la classe de $x$ est $\{x\}$. Les classes sont $\, ]-\infty, 0]$ et les singletons $\{x\}$ pour $x > 0$, et $[0, +\infty[$ est un système de représentants : il ne rencontre $\, ]-\infty, 0]$ qu'en $0$ et chaque $\{x\}$ qu'en $x$.

Compétences à pratiquer

Compter les classes d'une relation d'équivalence ★
Déterminer une classe d'équivalence ★
Décrire toutes les classes ★★
Trouver un système de représentants ★★★

II.3 Classes et partitions

Deux descriptions d'une même structure

Découper un ensemble en morceaux et identifier des éléments sont deux façons de regarder une même chose. Une relation d'équivalence étant donnée, ses classes sont des morceaux qui couvrent l'ensemble sans se chevaucher ; une partition étant donnée, déclarer deux éléments en relation lorsqu'ils sont dans un même morceau définit une relation d'équivalence. Les Théorèmes « Les classes forment une partition » et « Toute partition provient d'une équivalence » énoncent ce dictionnaire, et la Proposition « Toute relation d'équivalence est la relation d'une application » ajoute une troisième description : une relation d'équivalence est une façon d'envoyer les éléments de $E$ vers un autre ensemble, deux éléments étant en relation lorsqu'ils ont la même image.

Signaler une erreur

Définition — Recouvrement disjoint, partition

Soit $E$ un ensemble. Une partition de $E$ est un ensemble $\mathcal{A}$ de parties de $E$, c'est-à-dire $\mathcal{A} \subset \mathcal{P}(E)$, tel que :

ses éléments sont non vides : $\emptyset \notin \mathcal{A}$ ;
deux éléments distincts de $\mathcal{A}$ sont disjoints : $\forall A, B \in \mathcal{A}, \ \big(A \ne B \Rightarrow A \cap B = \emptyset\big)$ ;
leur réunion est $E$ : $\bigcup_{A \in \mathcal{A}} A = E$, réunion de la famille indexée par $\mathcal{A}$ lui-même.

Les éléments de $\mathcal{A}$ sont les morceaux de la partition. Un recouvrement disjoint de $E$ est une famille $(A_i)_{i \in I}$ de parties de $E$, deux à deux disjointe, dont la réunion est $E$, ce que l'on note $E = \bigsqcup_{i \in I} A_i$ ; certains de ses morceaux peuvent être vides. Lorsque les morceaux d'un recouvrement disjoint sont tous non vides, deux morceaux d'indices distincts sont distincts, puisqu'ils sont disjoints et non vides, et l'ensemble $\{A_i \mid i \in I\}$ des morceaux est une partition de $E$.

Théorème — Les classes forment une partition

Soit $\sim$ une relation d'équivalence sur $E$. L'ensemble des classes d'équivalence $$ \{\mathrm{cl}(x) \mid x \in E\} $$ est une partition de $E$.

Preuve

Première démonstration : le critère élément par élément. Soit $\mathcal{C} = \{\mathrm{cl}(x) \mid x \in E\}$, un ensemble de parties de $E$. Toute classe est non vide, puisque $x \in \mathrm{cl}(x)$ par la Proposition « Comparer deux classes », donc $\emptyset \notin \mathcal{C}$, et la Proposition « Partitions élément par élément » s'applique : il reste à montrer que tout $x \in E$ appartient à exactement un élément de $\mathcal{C}$. Existence : $x$ appartient à $\mathrm{cl}(x)$, un élément de $\mathcal{C}$. Unicité : soient $a, b \in E$ tels que $x \in \mathrm{cl}(a)$ et $x \in \mathrm{cl}(b)$. Alors $x \in \mathrm{cl}(a) \cap \mathrm{cl}(b)$, qui est donc non vide, et la Proposition « Comparer deux classes » donne $\mathrm{cl}(a) = \mathrm{cl}(b)$. Donc $\mathcal{C}$ est une partition de $E$.
Seconde démonstration : les trois vérifications. On applique la Méthode « Démontrer qu'un ensemble de parties est une partition », première voie. Les morceaux sont non vides, comme ci-dessus. Deux morceaux distincts sont disjoints : soient $a, b \in E$ tels que $\mathrm{cl}(a) \cap \mathrm{cl}(b) \ne \emptyset$ ; la Proposition « Comparer deux classes » donne $\mathrm{cl}(a) = \mathrm{cl}(b)$, et par contraposition deux classes distinctes sont disjointes. Les morceaux recouvrent $E$ : tout $x \in E$ est dans $\mathrm{cl}(x)$, donc $E$ est contenu dans la réunion des classes, et cette réunion, faite de parties de $E$, est contenue dans $E$.

Exemple — Des partitions lues comme des relations

La relation « même parité » sur $\mathbb{Z}$ a deux classes : $\mathrm{cl}(0)$ est l'ensemble des entiers pairs, $2\mathbb{Z}$, et $\mathrm{cl}(1)$ est l'ensemble des entiers impairs, $2\mathbb{Z} + 1$, tout entier étant en relation avec exactement un des deux nombres $0$ et $1$. Ces classes forment la partition $\{2\mathbb{Z}, 2\mathbb{Z} + 1\}$ de l'Exemple « Quatre partitions » du chapitre Ensembles, comme le prévoit le Théorème « Les classes forment une partition ». Réciproquement, cette partition redonne la relation : deux entiers sont en relation lorsqu'ils sont dans le même morceau.
La partition $\{\mathbb{R}_+^*, \mathbb{R}_-^*\}$ de $\mathbb{R}^*$ définit la relation « même signe » : deux réels non nuls sont en relation lorsqu'ils sont dans le même morceau, les strictement positifs ou les strictement négatifs.
La partition $\{\{1, 2\}, \{3\}\}$ de $E = \{1, 2, 3\}$ définit la relation dont les couples sont ceux qui sont dans un même morceau : $(1, 1)$, $(1, 2)$, $(2, 1)$, $(2, 2)$ et $(3, 3)$. Son graphe est la réunion $\{1, 2\}^2 \cup \{3\}^2$ des carrés des morceaux, et il a cinq couples. C'est une relation d'équivalence, dont les classes sont $\{1, 2\}$ et $\{3\}$.

Théorème — Toute partition provient d'une équivalence

Soit $\mathcal{U}$ une partition de $E$. Définissons, pour $x, y \in E$ : $$ x \sim y \iff \text{il existe } U \in \mathcal{U} \text{ avec } x \in U \text{ et } y \in U. $$ Alors $\sim$ est une relation d'équivalence sur $E$, et ses classes d'équivalence sont exactement les morceaux de $\mathcal{U}$.
Avec le Théorème « Les classes forment une partition », ceci dit que les relations d'équivalence sur $E$ et les partitions de $E$ sont deux descriptions des mêmes objets.

Preuve

Première démonstration : par une application. Par la Proposition « Partitions élément par élément », tout $x \in E$ appartient à exactement un morceau de $\mathcal{U}$, que l'on note $U(x)$ : cela définit une application $x \mapsto U(x)$ de $E$ dans $\mathcal{U}$. La condition qui définit $\sim$ se relit $x \sim y \iff U(x) = U(y)$. En effet, si $x$ et $y$ appartiennent tous deux à un morceau $V$, alors $V = U(x)$ et $V = U(y)$ par unicité, donc $U(x) = U(y)$ ; réciproquement, si $U(x) = U(y)$, alors $x$ et $y$ appartiennent tous deux au morceau $U(x)$. Ainsi $\sim$ est la relation de l'application $x \mapsto U(x)$, et la Proposition « La relation d'équivalence d'une application » montre que c'est une relation d'équivalence.
Il reste à trouver les classes. Soit $x \in E$ ; montrons que $\mathrm{cl}(x) = U(x)$. Si $y \in \mathrm{cl}(x)$, alors $x \sim y$, donc $U(y) = U(x)$, et $y \in U(y) = U(x)$. Réciproquement, si $y \in U(x)$, alors $x$ et $y$ appartiennent tous deux au morceau $U(x)$, donc $x \sim y$ et $y \in \mathrm{cl}(x)$. Les deux ensembles ont les mêmes éléments, donc $\mathrm{cl}(x) = U(x)$ : toute classe est un morceau. Réciproquement, soit $V \in \mathcal{U}$. Le morceau $V$ est non vide, donc il contient un élément $x$, et $V = U(x)$ par unicité, donc $V = \mathrm{cl}(x)$ est une classe. Les classes de $\sim$ sont exactement les morceaux de $\mathcal{U}$.
Seconde démonstration : les trois axiomes. Réflexivité. Soit $x \in E$. Les morceaux recouvrent $E$, donc $x$ appartient à un morceau $V$, et « $x \in V$ et $x \in V$ » donne $x \sim x$. Symétrie. La condition qui définit $\sim$ est symétrique en $x$ et $y$. Transitivité. Soient $x \sim y$ et $y \sim z$ : il existe des morceaux $V$ et $W$ tels que $x, y \in V$ et $y, z \in W$. Alors $y \in V \cap W$, donc $V \cap W \ne \emptyset$, et $V = W$ puisque deux morceaux distincts sont disjoints. Donc $x, z \in V$, c'est-à-dire $x \sim z$. Les classes. Soient $x \in E$ et $V$ le morceau qui contient $x$. Tout $y \in V$ vérifie $x \sim y$, donc $V \subset \mathrm{cl}(x)$. Réciproquement, si $y \in \mathrm{cl}(x)$, il existe un morceau $W$ avec $x \in W$ et $y \in W$ ; alors $x \in V \cap W$, donc $V = W$ puisque deux morceaux distincts sont disjoints, et $y \in V$ : $\mathrm{cl}(x) \subset V$. Donc $\mathrm{cl}(x) = V$, de sorte que toute classe est un morceau ; et tout morceau $V$ est non vide, donc il contient un $x$, et $V = \mathrm{cl}(x)$.

Proposition — Toute relation d'équivalence est la relation d'une application

Soient $\sim$ une relation d'équivalence sur un ensemble $E$, et $C = \{\mathrm{cl}(x) \mid x \in E\}$ l'ensemble de ses classes. L'application $$ \pi \colon E \to C, \quad x \mapsto \mathrm{cl}(x) $$ est surjective, et $\sim$ est la relation de $\pi$ : pour tous $x, y \in E$, $x \sim y \iff \pi(x) = \pi(y)$. Par conséquent, une relation sur $E$ est une relation d'équivalence si et seulement si c'est la relation d'une application définie sur $E$.

Preuve

Surjectivité. L'ensemble $C$ est décrit par un paramètre : tout élément de $C$ est de la forme $\mathrm{cl}(x)$ avec $x \in E$, c'est-à-dire $\pi(x)$. Donc tout élément de l'ensemble d'arrivée $C$ a un antécédent, et $\pi$ est surjective.
La relation de $\pi$. Pour $x, y \in E$, $$ \begin{aligned} x \sim y &\iff \mathrm{cl}(x) = \mathrm{cl}(y) && \text{(Proposition « Comparer deux classes »)} \\ &\iff \pi(x) = \pi(y), \end{aligned} $$ la dernière étape par la définition de $\pi$. Donc $\sim$ est la relation de $\pi$.
La conséquence. Une relation qui est la relation d'une application est une relation d'équivalence, par la Proposition « La relation d'équivalence d'une application ». Réciproquement, une relation d'équivalence est la relation de l'application $\pi$ construite à partir de ses propres classes, par ce qui vient d'être démontré.

Compétences à pratiquer

Associer une partition à une relation d'équivalence ★
Compter les couples en relation ★★
Passer d'une partition à une relation d'équivalence ★★
Comparer les relations d'équivalence d'applications ★★★

III Congruences

III.1 Congruence modulo $n$ et modulo $\alpha$

Égaux à un pas près

Les congruences sont les relations d'équivalence les plus familières. Deux entiers sont congrus modulo $n$ lorsque leur différence est un multiple de $n$, ce qui signifie qu'ils ont le même reste dans la division euclidienne par $n$ ; c'est la base de l'arithmétique modulaire, des critères de divisibilité à la cryptographie. Deux réels sont congrus modulo $\alpha$ lorsque leur différence est un multiple entier de $\alpha$, et pour $\alpha = 2\pi$ c'est la formalisation des « angles modulo un tour ». Calculer avec des congruences — les additionner, les multiplier — relève de l'arithmétique des entiers et de la trigonométrie. Ce qu'il faut d'abord, c'est la relation elle-même : c'est une relation d'équivalence, ses classes se décrivent facilement, et chaque classe a un représentant canonique.

Signaler une erreur

Une différence qui est un multiple

Pour décider si deux nombres sont congrus, on regarde leur différence et l'on se demande si c'est un multiple du pas, $n$ ou $\alpha$. La définition dit exactement cela, les multiples du pas étant l'ensemble des différences permises. Cette observation rend la démonstration de l'équivalence courte et générale : la relation est « $x - y$ appartient à un ensemble $M$ », et trois propriétés de $M$ suffisent.

Signaler une erreur

Définition — Congruence modulo

Soit $n \in \mathbb{N}^*$. Deux entiers $x$ et $y$ sont congrus modulo $n$, ce que l'on note $x \equiv y \ [n]$, lorsque $x - y$ est un multiple de $n$ : $$ x \equiv y \ [n] \iff \exists k \in \mathbb{Z}, \ x - y = kn \iff x - y \in n\mathbb{Z}, $$ où $n\mathbb{Z} = \{kn \mid k \in \mathbb{Z}\}$ est l'ensemble des multiples de $n$. Cette relation sur $\mathbb{Z}$ est la congruence modulo $n$.
Soit $\alpha \in \mathbb{R}_+^*$. Deux réels $x$ et $y$ sont congrus modulo $\alpha$, ce que l'on note $x \equiv y \ [\alpha]$, lorsque $x - y$ est un multiple entier de $\alpha$ : $$ x \equiv y \ [\alpha] \iff \exists k \in \mathbb{Z}, \ x - y = k\alpha \iff x - y \in \alpha\mathbb{Z}, $$ où $\alpha\mathbb{Z} = \{k\alpha \mid k \in \mathbb{Z}\}$. Cette relation sur $\mathbb{R}$ est la congruence modulo $\alpha$.

Sur les entiers, les deux définitions coïncident lorsque $\alpha = n$ est un entier.

Proposition — Les congruences sont des relations d'équivalence

Soit $X$ égal à $\mathbb{Z}$ ou à $\mathbb{R}$, et $M$ une partie de $X$ telle que

$0 \in M$ ;
pour tout $m \in M$, $-m \in M$ ;
pour tous $m, m' \in M$, $m + m' \in M$.

Alors la relation définie sur $X$ par $x \sim y \iff x - y \in M$ est une relation d'équivalence. En particulier, la congruence modulo $n$ est une relation d'équivalence sur $\mathbb{Z}$, et la congruence modulo $\alpha$ est une relation d'équivalence sur $\mathbb{R}$.

Preuve

Première démonstration : l'énoncé général. On applique la Méthode « Démontrer qu'une relation est une relation d'équivalence ». Soient $x, y, z \in X$.

Réflexivité. $x - x = 0 \in M$, donc $x \sim x$.
Symétrie. Supposons $x \sim y$, c'est-à-dire $x - y \in M$. Alors $y - x = -(x - y) \in M$ par la deuxième propriété, donc $y \sim x$.
Transitivité. Supposons $x \sim y$ et $y \sim z$, c'est-à-dire $x - y \in M$ et $y - z \in M$. Alors $$ \begin{aligned} x - z &= (x - y) + (y - z) && \text{(simplification de $y$)} \\ &\in M, \end{aligned} $$ la dernière étape par la troisième propriété, appliquée à $x - y$ et $y - z$. Donc $x \sim z$.

Les congruences sont de cette forme. La partie $n\mathbb{Z}$ vérifie les trois propriétés : $0 = 0 \cdot n$ ; si $m = kn$ avec $k \in \mathbb{Z}$, alors $-m = (-k)n$ ; si $m = kn$ et $m' = k'n$ avec $k, k' \in \mathbb{Z}$, alors $m + m' = (k + k')n$. Il en va de même pour $\alpha\mathbb{Z}$. Et la congruence modulo $n$ est, par définition, la relation $x - y \in n\mathbb{Z}$ sur $\mathbb{Z}$, et la congruence modulo $\alpha$ la relation $x - y \in \alpha\mathbb{Z}$ sur $\mathbb{R}$.
Seconde démonstration : directement, sur l'entier $k$. Prenons la congruence modulo $\alpha$ ; pour la congruence modulo $n$, remplacer $\alpha$ par $n$ et les réels par des entiers. Réflexivité : $x - x = 0 \cdot \alpha$, avec $0 \in \mathbb{Z}$. Symétrie : si $x - y = k\alpha$ avec $k \in \mathbb{Z}$, alors $y - x = (-k)\alpha$, avec $-k \in \mathbb{Z}$. Transitivité : si $x - y = k\alpha$ et $y - z = l\alpha$ avec $k, l \in \mathbb{Z}$, alors $$ \begin{aligned} x - z &= (x - y) + (y - z) && \text{(simplification de $y$)} \\ &= k\alpha + l\alpha && \text{(hypothèses)} \\ &= (k + l)\alpha, \end{aligned} $$ avec $k + l \in \mathbb{Z}$.

Exemple — Des congruences sur les entiers et sur les réels

Modulo $5$ dans $\mathbb{Z}$. $17 \equiv 2 \ [5]$, car $$ \begin{aligned} 17 - 2 &= 15 && \text{(soustraction)} \\ &= 3 \times 5, \end{aligned} $$ et $-3 \equiv 2 \ [5]$, car $$ \begin{aligned} -3 - 2 &= -5 && \text{(soustraction)} \\ &= (-1) \times 5. \end{aligned} $$ Aussi $0 \equiv 5 \equiv 10 \ [5]$, car les différences $0 - 5 = -5$, $5 - 10 = -5$ et $0 - 10 = -10$ sont des multiples de $5$. En revanche $7 \not\equiv 3 \ [5]$, car $7 - 3 = 4$ n'est pas un multiple de $5$.
Modulo $2\pi$ dans $\mathbb{R}$. $\frac{\pi}{3} \equiv \frac{7\pi}{3} \ [2\pi]$, car $\frac{7\pi}{3} - \frac{\pi}{3} = 2\pi$. Par la Proposition « Réels ayant la même image » du chapitre Radians et cercle unité, $x \equiv y \ [2\pi]$ si et seulement si $x$ et $y$ ont la même image sur le cercle trigonométrique : la congruence modulo $2\pi$ est la relation de l'application $x \mapsto M(x)$, où $M(x)$ est le point du cercle associé à $x$. C'est la formalisation de « même angle à un tour près », et une relation d'équivalence aussi par la Proposition « La relation d'équivalence d'une application ».
Modulo $1$ dans $\mathbb{R}$. $x \equiv y \ [1]$ signifie $x - y \in \mathbb{Z}$, et c'est « avoir la même partie fractionnaire » : $x \equiv y \ [1] \iff x - \lfloor x \rfloor = y - \lfloor y \rfloor$. En effet, si les parties fractionnaires sont égales, alors $x - y = \lfloor x \rfloor - \lfloor y \rfloor \in \mathbb{Z}$. Réciproquement, si $x - y = k \in \mathbb{Z}$, alors $\lfloor y \rfloor + k \le y + k = x < \lfloor y \rfloor + k + 1$, donc $\lfloor x \rfloor = \lfloor y \rfloor + k$ et $$ \begin{aligned} x - \lfloor x \rfloor &= (y + k) - \lfloor x \rfloor && \text{(car $x = y + k$)} \\ &= (y + k) - (\lfloor y \rfloor + k) && \text{(car $\lfloor x \rfloor = \lfloor y \rfloor + k$)} \\ &= y - \lfloor y \rfloor, \end{aligned} $$ la dernière égalité en simplifiant par $k$. La congruence modulo $1$ est la relation de l'application $x \mapsto x - \lfloor x \rfloor$.

Méthode — Décider une congruence

Pour décider si $x \equiv y \ [\alpha]$, avec $\alpha > 0$ (un entier $n$ lorsque $x$ et $y$ sont entiers) :

Calculer le quotient $q = \frac{x - y}{\alpha}$. Comme $\alpha \ne 0$, $x - y = k\alpha \iff q = k$, donc $x \equiv y \ [\alpha]$ si et seulement si $q$ est un entier.
Pour démontrer la congruence, montrer que $q$ est un entier, et dire lequel : c'est le témoin $k$ de la définition.
Pour la réfuter, encadrer $q$ strictement entre deux entiers consécutifs, $k < q < k + 1$ : aucun entier n'est dans cet intervalle, donc $q \notin \mathbb{Z}$.

Par exemple, $\frac{11\pi}{6} \equiv -\frac{\pi}{6} \ [2\pi]$, car $$ \begin{aligned} q &= \frac{\frac{11\pi}{6} + \frac{\pi}{6}}{2\pi} && \text{(définition de $q$)} \\ &= \frac{2\pi}{2\pi} && \text{(car $\frac{11\pi}{6} + \frac{\pi}{6} = 2\pi$)} \\ &= 1. \end{aligned} $$ En revanche $\frac{11\pi}{6} \not\equiv \frac{\pi}{6} \ [2\pi]$ : ici $$ \begin{aligned} q &= \frac{\frac{11\pi}{6} - \frac{\pi}{6}}{2\pi} && \text{(définition de $q$)} \\ &= \frac{\frac{5\pi}{3}}{2\pi} && \text{(car $\frac{11\pi}{6} - \frac{\pi}{6} = \frac{5\pi}{3}$)} \\ &= \frac{5}{6}, \end{aligned} $$ la dernière égalité en simplifiant par $\pi$, et $0 < \frac{5}{6} < 1$. Pour des entiers, $100 \equiv 2 \ [7]$, car $\frac{100 - 2}{7} = 14$, alors que $100 \not\equiv 3 \ [7]$, car $\frac{100 - 3}{7} = \frac{97}{7}$ et $13 < \frac{97}{7} < 14$.

Compétences à pratiquer

Reconnaître une congruence ★
Décider une congruence ★
Démontrer une équivalence de la forme $x - y \in M$ ★★
Comparer deux congruences ★★★

III.2 Classes modulo $n$ et modulo $\alpha$

Un représentant par classe

Une classe modulo $\alpha$ contient, avec un élément $x$, tous les nombres $x + k\alpha$. Pour nommer une classe, on choisit un représentant dans une fenêtre de longueur $\alpha$, choisie par commodité : $[0, \alpha[$ pour un reste, $\, ]-\pi, \pi]$ pour un angle. La partie entière, qui découpe la droite réelle en intervalles $[k, k + 1[$, trouve le représentant dans une fenêtre par une formule, et la division euclidienne des entiers est le cas particulier d'une fenêtre $[0, n[$.

Signaler une erreur

Proposition — Représentants modulo $\alpha$ et modulo $n$

Soient $\alpha \in \mathbb{R}_+^*$ et $n \in \mathbb{N}^*$.

La classe d'un réel $x$ modulo $\alpha$ est $x + \alpha\mathbb{Z} = \{x + k\alpha \mid k \in \mathbb{Z}\}$, et la classe d'un entier $x$ modulo $n$ est $x + n\mathbb{Z}$.
Pour tout réel $a$, tout réel $x$ est congru modulo $\alpha$ à un et un seul élément de $[a, a + \alpha[$, à savoir $$ r = x - \alpha \left\lfloor \frac{x - a}{\alpha} \right\rfloor. $$ Donc $[a, a + \alpha[$ est un système de représentants de la congruence modulo $\alpha$.
Tout entier est congru modulo $n$ à un et un seul élément de $\llbracket 0, n - 1 \rrbracket$ : cette partie est un système de représentants de la congruence modulo $n$ sur $\mathbb{Z}$, qui a exactement $n$ classes. Deux entiers sont congrus modulo $n$ si et seulement s'ils ont le même reste dans la division euclidienne par $n$.

Preuve

Première démonstration : la partie entière, une fois pour les deux énoncés.
La classe. Pour $y \in \mathbb{R}$, $x \equiv y \ [\alpha]$ signifie $x - y = k\alpha$ pour un certain $k \in \mathbb{Z}$, c'est-à-dire $y = x + (-k)\alpha$. Quand $k$ parcourt $\mathbb{Z}$, $-k$ aussi : la classe de $x$ est $\{x + k\alpha \mid k \in \mathbb{Z}\}$. Il en va de même dans $\mathbb{Z}$ modulo $n$.
Existence du représentant. Soient $a, x \in \mathbb{R}$, $k = \left\lfloor \frac{x - a}{\alpha} \right\rfloor$ et $r = x - k\alpha$. Alors $x - r = k\alpha$ avec $k \in \mathbb{Z}$, donc $r \equiv x \ [\alpha]$. Par la définition de la partie entière, $$ \begin{aligned} k \le \frac{x - a}{\alpha} < k + 1 &\Rightarrow k\alpha \le x - a < k\alpha + \alpha && \text{(multiplication par $\alpha > 0$)} \\ &\Rightarrow 0 \le r - a < \alpha && \text{(soustraction de $k\alpha$, car $r = x - k\alpha$)} \\ &\Rightarrow a \le r < a + \alpha, \end{aligned} $$ la dernière étape par l'addition de $a$ : $r \in [a, a + \alpha[$.
Unicité. Soient $r, r' \in [a, a + \alpha[$ tous deux congrus à $x$ modulo $\alpha$. Alors $r \equiv r' \ [\alpha]$, par la symétrie et la transitivité de la congruence, donc $r - r' = m\alpha$ pour un certain $m \in \mathbb{Z}$. Les deux nombres sont dans $[a, a + \alpha[$, donc $$ \begin{aligned} -\alpha < r - r' < \alpha &\Rightarrow \lvert r - r' \rvert < \alpha && \text{(définition de la valeur absolue)} \\ &\Rightarrow \lvert m \rvert \alpha < \alpha && \text{(car $r - r' = m\alpha$ et $\alpha > 0$)} \\ &\Rightarrow \lvert m \rvert < 1, \end{aligned} $$ la dernière étape par division par $\alpha > 0$. L'entier $m$ est $0$, et $r = r'$.
Entiers. Prenons $a = 0$ et $\alpha = n$, et soit $x \in \mathbb{Z}$. Le nombre $r = x - n \lfloor \frac{x}{n} \rfloor$ est un entier, et il est dans $[0, n[$, donc $0 \le r \le n - 1$ : $r \in \llbracket 0, n - 1 \rrbracket$, et $r \equiv x \ [n]$. Si $r' \in \llbracket 0, n - 1 \rrbracket$ est aussi congru à $x$ modulo $n$, alors $r' \in [0, n[$ et l'unicité ci-dessus donne $r' = r$. Donc $\llbracket 0, n - 1 \rrbracket$ est un système de représentants. Ses éléments sont dans $n$ classes distinctes, puisque deux d'entre eux dans une même classe seraient deux représentants de cette classe, et toute classe $\mathrm{cl}(x)$ en contient un, de sorte que $\mathrm{cl}(x) = \mathrm{cl}(r)$ par la Proposition « Comparer deux classes ». Il y a exactement $n$ classes.
Seconde démonstration pour les entiers : la division euclidienne. Soit $x \in \mathbb{Z}$. La division euclidienne de $x$ par $n$ donne $x = qn + r$ avec $q \in \mathbb{Z}$ et un unique $r \in \llbracket 0, n - 1 \rrbracket$. Alors $x - r = qn$, donc $x \equiv r \ [n]$ : existence. Si $r' \in \llbracket 0, n - 1 \rrbracket$ et $x \equiv r' \ [n]$, alors $x - r' = q'n$ avec $q' \in \mathbb{Z}$, donc $x = q'n + r'$ est une division euclidienne de $x$ par $n$, et l'unicité du reste donne $r' = r$ : unicité. Le compte des classes s'en déduit comme ci-dessus.
Congruence et restes. L'élément de $\llbracket 0, n - 1 \rrbracket$ congru à un entier $x$ est le reste $r$ de la division euclidienne de $x$ par $n$ : de $x = qn + r$ avec $q \in \mathbb{Z}$ et $0 \le r \le n - 1$ découle $x - r = qn$, donc $x \equiv r \ [n]$, et cet élément est unique. Soient $x, y \in \mathbb{Z}$, de restes $r$ et $r'$. Si $x \equiv y \ [n]$, alors $r' \equiv y \equiv x \ [n]$ par la symétrie et la transitivité de la congruence, donc $r'$ est un élément de $\llbracket 0, n - 1 \rrbracket$ congru à $x$, et $r' = r$ par unicité. Si $r = r'$, alors $x \equiv r \ [n]$ et $y \equiv r \ [n]$, donc $x \equiv y \ [n]$ par la symétrie et la transitivité de la congruence. Ainsi $x \equiv y \ [n]$ si et seulement si $x$ et $y$ ont le même reste.

Exemple — Trois vues des classes

Trois dessins d'une même idée : une classe est une suite de points espacés du pas, et une fenêtre dont la longueur est le pas en contient exactement un.

Sur la droite réelle. Pour $\alpha = 2$, $a = 1$ et $x = \frac{1}{2}$, la classe de $x$ est $\frac{1}{2} + 2\mathbb{Z} = \{\dots, -\frac{7}{2}, -\frac{3}{2}, \frac{1}{2}, \frac{5}{2}, \frac{9}{2}, \dots\}$ : des points espacés de $2$. La fenêtre est $[1, 3[$, et la formule de la Proposition « Représentants modulo $\alpha$ et modulo $n$ » donne $$ \begin{aligned} \left\lfloor \frac{x - a}{\alpha} \right\rfloor &= \left\lfloor \frac{\frac{1}{2} - 1}{2} \right\rfloor && \text{(valeurs de $x$, $a$ et $\alpha$)} \\ &= \left\lfloor -\frac{1}{4} \right\rfloor && \text{(soustraction et division)} \\ &= -1, \end{aligned} $$ et $$ \begin{aligned} r &= \frac{1}{2} - (-1) \times 2 && \text{(formule $r = x - k\alpha$, avec $k = -1$)} \\ &= \frac{5}{2}, \end{aligned} $$ le seul point de la classe dans la fenêtre.
Sur le cercle. Les réels $\frac{\pi}{3}$, $\frac{7\pi}{3}$ et $-\frac{5\pi}{3}$ diffèrent de multiples de $2\pi$ et ont la même image $M$ sur le cercle trigonométrique : une classe modulo $2\pi$ correspond à un unique point du cercle, atteint après un nombre quelconque de tours complets, dans un sens ou dans l'autre.
Dans $\mathbb{Z}$. Les entiers se répartissent en cinq classes modulo $5$, dessinées en cinq couleurs : la classe de $2$ est $2 + 5\mathbb{Z}$, écrite sous le dessin, et $\llbracket 0, 4 \rrbracket$ contient un entier de chaque classe.

Méthode — Réduire modulo $n$ ou modulo $\alpha$

Pour réduire un nombre $x$ modulo $\alpha$ dans une fenêtre $[a, a + \alpha[$, c'est-à-dire trouver son représentant :

Calculer $\frac{x - a}{\alpha}$ et sa partie entière $k$, puis $r = x - k\alpha$ : c'est la formule de la Proposition « Représentants modulo $\alpha$ et modulo $n$ ». Vérifier que $a \le r < a + \alpha$.
Choisir la fenêtre qui convient au problème, $[0, 2\pi[$ pour un angle ou $\, ]-\pi, \pi]$. La seconde est ouverte à gauche, ce que la formule ne donne pas : réduire $-x$ dans $[-\pi, \pi[$, et changer le signe du résultat $s$. C'est correct, car $s \in [-\pi, \pi[$ signifie $-s \in \, ]-\pi, \pi]$, et $s \equiv -x \ [2\pi]$ donne $-s \equiv x \ [2\pi]$.
Pour un entier $x$ et le module $n$, prendre la fenêtre $[0, n[$ : $r = x - n \lfloor \frac{x}{n} \rfloor$ est le reste de la division euclidienne, positif ou nul même lorsque $x$ est négatif.

Par exemple, pour réduire $x = \frac{22\pi}{3}$ dans $[0, 2\pi[$ : $\frac{x}{2\pi} = \frac{11}{3}$ a pour partie entière $3$, donc $$ \begin{aligned} r &= x - 3 \times 2\pi && \text{(formule $r = x - k\alpha$)} \\ &= \frac{22\pi}{3} - 6\pi && \text{(valeur de $x$, et $3 \times 2\pi = 6\pi$)} \\ &= \frac{4\pi}{3}. \end{aligned} $$ Dans $\, ]-\pi, \pi]$ : comme $\frac{4\pi}{3} > \pi$, on utilise la règle. Pour $-x = -\frac{22\pi}{3}$ et la fenêtre $[-\pi, \pi[$, $\frac{-x + \pi}{2\pi} = -\frac{19}{6}$ a pour partie entière $-4$, donc $$ \begin{aligned} s &= -x - (-4) \times 2\pi && \text{(formule $s = -x - k\alpha$)} \\ &= -\frac{22\pi}{3} + 8\pi && \text{(valeur de $x$, et $4 \times 2\pi = 8\pi$)} \\ &= \frac{2\pi}{3}, \end{aligned} $$ et le représentant de $x$ est $-s = -\frac{2\pi}{3}$ ; en effet $\frac{22\pi}{3} - \left(-\frac{2\pi}{3}\right) = 8\pi$. Pour l'entier $x = -23$ et $n = 6$ : $\left\lfloor \frac{-23}{6} \right\rfloor = -4$, donc $$ \begin{aligned} r &= -23 - 6 \times (-4) && \text{(formule $r = x - n \lfloor \frac{x}{n} \rfloor$)} \\ &= -23 + 24 && \text{(car $6 \times (-4) = -24$)} \\ &= 1, \end{aligned} $$ c'est-à-dire $-23 \equiv 1 \ [6]$ et $-23 = (-4) \times 6 + 1$.

Compétences à pratiquer

Réduire un entier modulo $n$ ★
Réduire un réel modulo $\alpha$ ★
Compter les éléments d'une classe dans un intervalle ★★
Démontrer qu'une partie est un système de représentants ★★★

IV Relations d'ordre

IV.1 Ordres totaux et partiels

Une hiérarchie

L'autre grande famille est celle des relations d'ordre. Là où une relation d'équivalence identifie, une relation d'ordre exprime une hiérarchie : plus petit, plus grand, avant, après. Les trois axiomes — réflexivité, antisymétrie, transitivité — sont la bonne combinaison : tout $x$ est comparable à lui-même ; si $x \preccurlyeq y$ et $y \preccurlyeq x$, alors $x = y$, de sorte qu'il n'y a pas d'ex æquo entre éléments distincts ; et les chaînes de comparaisons se composent. Deux sortes d'ordres existent : les ordres totaux, où deux éléments quelconques se comparent, comme $\le$ sur $\mathbb{R}$, et les ordres partiels, où certains éléments ne se comparent pas, comme l'inclusion des ensembles ou la divisibilité des entiers. Dans un ensemble ordonné on cherche le plus grand élément d'une partie, ses majorants, le plus petit d'entre eux, qui est sa borne supérieure, et les applications qui respectent l'ordre. Les diagrammes de Hasse sont la façon canonique de dessiner un ordre partiel fini.

Signaler une erreur

Comparables ou non

Deux éléments d'un ensemble ordonné peuvent ne pas être comparables, et cela sépare les ordres partiels de l'ordre total des réels. Raisonner dans un ordre partiel demande de l'attention : la négation de $x \preccurlyeq y$ n'est pas toujours $y \prec x$, où $\prec$ est la version stricte de l'ordre, $x \prec y$ signifiant $x \preccurlyeq y$ et $x \ne y$. Les Propositions « Ordre strict associé à un ordre » et « Nier une inégalité » donnent les règles, et la Méthode « Démontrer qu'une relation est un ordre » la démonstration des trois axiomes.

Signaler une erreur

Définition — Relation d'ordre

Une relation binaire $\preccurlyeq$ sur $E$ est une relation d'ordre (ou ordre) si elle est réflexive, antisymétrique et transitive. Le couple $(E, \preccurlyeq)$ est alors appelé ensemble ordonné. Les relations d'ordre sont notées typiquement $\le$, $\preccurlyeq$, $\sqsubseteq$.

Définition — Ordre total, ordre partiel

Soit $(E, \preccurlyeq)$ un ensemble ordonné. Deux éléments $x, y \in E$ sont comparables si $x \preccurlyeq y$ ou $y \preccurlyeq x$. L'ordre $\preccurlyeq$ est :

total si deux éléments quelconques de $E$ sont comparables : $\forall (x, y) \in E^2, \ x \preccurlyeq y \text{ ou } y \preccurlyeq x$ ;
partiel dans le cas contraire (il existe des éléments incomparables).

Exemple — Des ordres sur des nombres, des parties et des entiers

$(\mathbb{R}, \le)$, $(\mathbb{Q}, \le)$, $(\mathbb{Z}, \le)$ et $(\mathbb{N}, \le)$ sont totalement ordonnés : deux réels quelconques sont comparables.
$(\mathcal{P}(E), \subset)$ est un ensemble ordonné. Ses trois axiomes sont connus : la réflexivité, $A \subset A$, par la Définition « Inclusion, sous-ensemble » ; l'antisymétrie, puisque $A \subset B$ et $B \subset A$ donnent $A = B$, par la Proposition « Égalité par double inclusion » ; la transitivité, par la Proposition « Transitivité de l'inclusion ». L'ordre est partiel dès que $E$ a deux éléments distincts $a \ne b$ : les parties $\{a\}$ et $\{b\}$ ne sont pas comparables, aucune n'étant incluse dans l'autre.
$(\mathbb{N}^*, \mid)$, la divisibilité, est un ensemble ordonné : la divisibilité est réflexive, antisymétrique et transitive sur $\mathbb{N}$, comme le démontre l'Exemple « Sept relations et leurs propriétés », et ces trois propriétés, vraies pour tous les éléments de $\mathbb{N}$, le sont pour ceux de $\mathbb{N}^*$. L'ordre est partiel : $2$ et $3$ ne sont pas comparables, puisque $2 \nmid 3$ et $3 \nmid 2$.

Un ensemble ordonné fini se dessine par un diagramme de Hasse : les éléments sont des points, et une arête monte de $x$ vers $y$ lorsque $x \preccurlyeq y$, $x \ne y$, et qu'aucun élément $z$ distinct de $x$ et de $y$ ne vérifie $x \preccurlyeq z \preccurlyeq y$. L'ordre se lit sur le diagramme : $x \preccurlyeq y$ lorsque l'on peut monter de $x$ à $y$ le long des arêtes. Voici le diagramme de $(\mathcal{P}(\{1, 2, 3\}), \subset)$.

Les trois singletons $\{1\}$, $\{2\}$, $\{3\}$ sont deux à deux incomparables, et les trois paires $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ aussi : c'est le caractère partiel de l'ordre.

Exemple — Diviseurs de 12

La divisibilité sur l'ensemble $D_{12} = \{1, 2, 3, 4, 6, 12\}$ des diviseurs de $12$ est un ordre partiel, dont le diagramme de Hasse est dessiné ci-dessous.

Lecture du diagramme : $2 \mid 4$ et $2 \mid 6$, puisque l'on monte de $2$ à $4$ et à $6$ ; mais $4$ et $6$ sont incomparables, aucun ne divisant l'autre. L'élément $1$ est au-dessous de tous les éléments et $12$ est au-dessus de tous les éléments : ce sont les deux éléments extrêmes de cet ordre.

Exemple — Des fonctions comparées point par point

Sur l'ensemble $\mathbb{R}^{\mathbb{R}}$ des applications de $\mathbb{R}$ dans $\mathbb{R}$, notons $f \preccurlyeq g$ lorsque $g$ est au-dessus de $f$ en tout point : $$ f \preccurlyeq g \iff \forall x \in \mathbb{R}, \ f(x) \le g(x). $$ Cette relation est un ordre, chaque axiome étant l'axiome correspondant de $\le$ appliqué en tout point. Réflexivité : $f(x) \le f(x)$ pour tout $x$. Antisymétrie : si $f \preccurlyeq g$ et $g \preccurlyeq f$, alors $f(x) \le g(x)$ et $g(x) \le f(x)$ pour tout $x$, donc $f(x) = g(x)$ pour tout $x$, et $f = g$ puisque les deux applications ont le même ensemble de départ et le même ensemble d'arrivée. Transitivité : si $f \preccurlyeq g$ et $g \preccurlyeq h$, alors $f(x) \le g(x) \le h(x)$ pour tout $x$, donc $f \preccurlyeq h$. L'ordre est partiel : $\sin$ et $\cos$ ne sont pas comparables.

En effet $\sin \preccurlyeq \cos$ est faux, puisque $\sin \frac{\pi}{2} = 1 > 0 = \cos \frac{\pi}{2}$, et $\cos \preccurlyeq \sin$ est faux, puisque $\cos 0 = 1 > 0 = \sin 0$ : chaque fonction est au-dessus de l'autre en un point.

Proposition — Ordre strict associé à un ordre

Soit $(E, \preccurlyeq)$ un ensemble ordonné. La relation $\prec$ définie par $$ x \prec y \iff (x \preccurlyeq y \text{ et } x \ne y) $$ est l'ordre strict associé à $\preccurlyeq$. Pour tous $x, y, z \in E$ :

$\prec$ est irréflexive et asymétrique : $x \prec x$ est faux, et $x \prec y$ et $y \prec x$ ne sont jamais vrais tous les deux ;
$\prec$ est transitive, et même mixte : si $x \prec y$ et $y \preccurlyeq z$, ou si $x \preccurlyeq y$ et $y \prec z$, ou si $x \prec y$ et $y \prec z$, alors $x \prec z$ ;
$x \preccurlyeq y \iff (x \prec y \text{ ou } x = y)$.

Preuve

Irréflexivité et asymétrie. Par définition, $x \prec x$ exigerait $x \ne x$, ce qui est faux. Si $x \prec y$ et $y \prec x$, alors $x \preccurlyeq y$ et $y \preccurlyeq x$, donc $x = y$ par antisymétrie, ce qui contredit $x \ne y$.
Transitivité. Soient $x, y, z \in E$ tels que $x \preccurlyeq y$ et $y \preccurlyeq z$, et tels que l'un des deux pas soit strict, $x \ne y$ ou $y \ne z$ : les trois cas de l'énoncé sont contenus dans ces hypothèses. Par la transitivité de $\preccurlyeq$, $x \preccurlyeq z$. Supposons par l'absurde que $x = z$. Alors $y \preccurlyeq z = x$ et $x \preccurlyeq y$, donc $x = y$ par antisymétrie, et ensuite $y = x = z$ : ni $x \ne y$ ni $y \ne z$ ne vaut, contrairement à l'hypothèse. Contradiction ! Donc $x \ne z$, et $x \prec z$.
La dernière équivalence. Si $x \preccurlyeq y$, alors ou bien $x = y$, ou bien $x \ne y$ et alors $x \prec y$. Réciproquement, $x \prec y$ implique $x \preccurlyeq y$, et $x = y$ implique $x \preccurlyeq y$ par réflexivité.

Proposition — Nier une inégalité

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $x, y \in E$.

Si $y \prec x$, alors $x \preccurlyeq y$ est faux.
Si l'ordre est total, la réciproque est vraie : $\neg(x \preccurlyeq y) \iff y \prec x$. Dans un ensemble totalement ordonné, la négation d'une inégalité est l'inégalité stricte dans l'autre sens.
Dans un ordre partiel la réciproque est fausse en général : dans $(\mathcal{P}(\{1, 2\}), \subset)$, $\{1\} \subset \{2\}$ est faux, mais $\{2\} \prec \{1\}$ est faux aussi.

Preuve

Premier point. Supposons $y \prec x$ et $x \preccurlyeq y$. De $y \prec x$ on tire $y \preccurlyeq x$, donc $x = y$ par antisymétrie, ce qui contredit $y \ne x$. Donc $x \preccurlyeq y$ est faux.
Deuxième point. Supposons l'ordre total et $x \preccurlyeq y$ faux. Par totalité, $x \preccurlyeq y$ ou $y \preccurlyeq x$ ; le premier est faux, donc $y \preccurlyeq x$. De plus $y \ne x$ : si $y = x$, la réflexivité donnerait $x \preccurlyeq y$. Donc $y \prec x$. Avec le premier point, cela démontre l'équivalence.
Troisième point. Dans $\mathcal{P}(\{1, 2\})$, $\{1\} \subset \{2\}$ est faux, puisque $1 \in \{1\}$ et $1 \notin \{2\}$. Et $\{2\} \prec \{1\}$ exigerait $\{2\} \subset \{1\}$, ce qui est faux, puisque $2 \in \{2\}$ et $2 \notin \{1\}$.

Méthode — Démontrer qu'une relation est un ordre

Pour démontrer qu'une relation $\preccurlyeq$ sur un ensemble $E$ est une relation d'ordre :

Réflexivité : $x \preccurlyeq x$ pour tout $x \in E$.
Antisymétrie : de $x \preccurlyeq y$ et $y \preccurlyeq x$, déduire $x = y$. Les deux inégalités se croisent, et se combinent souvent en une égalité : par l'antisymétrie d'un ordre déjà connu, comme $\le$ sur $\mathbb{R}$, ou en les additionnant.
Transitivité : de $x \preccurlyeq y$ et $y \preccurlyeq z$, déduire $x \preccurlyeq z$, par disjonction des cas lorsque la relation est définie par cas.

Pour montrer que l'ordre est total, prendre deux éléments quelconques et montrer par disjonction des cas qu'ils sont comparables ; pour montrer qu'il est partiel, exhiber deux éléments et vérifier qu'aucun n'est au-dessous de l'autre.
Par exemple, sur $\mathbb{R}$, soit $x \preccurlyeq y \iff (x = y \text{ ou } y - x \ge 1)$ : « $y$ est $x$ lui-même ou le dépasse d'au moins $1$ ». Réflexivité : $x = x$. Antisymétrie : supposons $x \preccurlyeq y$ et $y \preccurlyeq x$ avec $x \ne y$ ; alors $y - x \ge 1$ et $x - y \ge 1$, et en les additionnant on obtient $0 \ge 2$, ce qui est absurde ; donc $x = y$. Transitivité : supposons $x \preccurlyeq y$ et $y \preccurlyeq z$ ; si $x = y$ ou $y = z$, alors $x \preccurlyeq z$ directement ; sinon $y - x \ge 1$ et $z - y \ge 1$, donc $z - x \ge 2 \ge 1$ et $x \preccurlyeq z$. L'ordre est partiel : $0$ et $\frac{1}{2}$ ne sont pas comparables, puisque $\frac{1}{2} - 0 < 1$ et $0 - \frac{1}{2} < 1$.

Piège — les mots des inégalités

Les mots des inégalités ne signifient pas la même chose en anglais et en français. En français, « supérieur à » et « plus grand que » sont larges, $x \ge y$, et l'inégalité stricte se dit « strictement supérieur à ». En anglais, « greater than » est strict : « $x$ is greater than $y$ » signifie $x > y$, et l'inégalité large se dit « greater than or equal to ». La même différence vaut pour « positif », qui signifie $\ge 0$ en français, alors que « positive » signifie $> 0$ en anglais, et pour « négatif » et « negative ». Pour les applications entre ensembles ordonnés, la Définition « Application croissante » prend « croissante », en français, et « increasing », en anglais, au sens large, et nomme le sens strict « strictement croissante » et « strictly increasing » ; certains ouvrages anglais disent « non-decreasing » pour le sens large. Ce texte écrit « greater than or equal to » en toutes lettres chaque fois qu'il veut dire $\ge$ en anglais : avant d'employer un mot d'inégalité, vérifier dans quelle langue il est lu.

Signaler une erreur

Compétences à pratiquer

Reconnaître un ordre, total ou partiel ★
Décider si un ordre est total ★
Lire et tracer un diagramme de Hasse ★
Démontrer qu'une relation est un ordre ★★
Manipuler l'ordre strict et la négation d'une inégalité ★★
Construire des ordres sur un produit ou sur des fonctions ★★★

IV.2 Plus grand élément, majorants, borne supérieure

Du plus grand élément à la borne supérieure

Dans un ensemble ordonné, une partie $A$ peut avoir un plus grand élément, un élément de $A$ au-dessus de tous les autres, mais elle n'en a souvent pas : l'intervalle $]0, 1[$ de réels n'en a pas. On peut alors chercher les éléments de l'ensemble ambiant qui sont au-dessus de tout $A$, ses majorants, et parmi eux le plus petit : la borne supérieure. Le plus grand élément appartient à $A$, la borne supérieure n'y appartient pas forcément. Ces notions sont reliées par des règles simples, et chaque démonstration repose sur une idée : deux éléments, chacun au-dessous de l'autre, sont égaux.

Signaler une erreur

Définition — Plus grand, plus petit élément

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A$ une partie de $E$.

Un élément $a \in A$ est un plus grand élément de $A$ si $\forall x \in A, \ x \preccurlyeq a$.
Un élément $a \in A$ est un plus petit élément de $A$ si $\forall x \in A, \ a \preccurlyeq x$.

Par la Proposition « Unicité du plus grand élément », une partie a au plus un plus grand élément et au plus un plus petit élément. Lorsqu'il existe, c'est le plus grand élément, noté $\max A$, ou le plus petit élément, noté $\min A$. L'existence n'est pas garantie : dans $(\mathbb{R}, \le)$, l'intervalle $]0, 1[$ n'en a aucun, comme le montre l'Exemple « Bornes dans les réels et dans les parties d'un ensemble ».

Proposition — Unicité du plus grand élément

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A$ une partie de $E$. $A$ a au plus un plus grand élément et au plus un plus petit élément.

Preuve

Soient $a$ et $b$ deux plus grands éléments de $A$. Comme $b$ est un plus grand élément et que $a \in A$, $a \preccurlyeq b$ ; comme $a$ est un plus grand élément et que $b \in A$, $b \preccurlyeq a$. Par antisymétrie, $a = b$. Pour les plus petits éléments, soient $a$ et $b$ deux plus petits éléments de $A$ : $a \preccurlyeq b$, puisque $a$ est un plus petit élément et que $b \in A$, et $b \preccurlyeq a$, puisque $b$ est un plus petit élément et que $a \in A$ ; de nouveau $a = b$.

Définition — Majorant, minorant

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A$ une partie de $E$. Un élément $m \in E$ est :

un majorant de $A$ si $\forall x \in A, \ x \preccurlyeq m$ ;
un minorant de $A$ si $\forall x \in A, \ m \preccurlyeq x$.

La partie $A$ est majorée si elle a au moins un majorant, minorée si elle a au moins un minorant, et bornée si elle a les deux. Un majorant est un élément de $E$, pas forcément de $A$ : c'est ce qui le distingue d'un plus grand élément.

Exemple — Bornes dans les réels et dans les parties d'un ensemble

Dans $(\mathbb{R}, \le)$ :

$A = [0, 1]$. Majorants : $[1, +\infty[$. Minorants : $]-\infty, 0]$. Plus grand élément : $1$. Plus petit élément : $0$.
$A = \, ]0, 1[$. Majorants : $[1, +\infty[$. Tout $m \ge 1$ en est un, puisque $x < 1 \le m$ pour $x \in A$ ; un réel $m < 1$ n'en est pas un, puisque l'élément $\frac{1 + \max(m, 0)}{2}$ de $A$ est strictement supérieur à $m$. Minorants : $]-\infty, 0]$, de la même façon. Pas de plus grand élément : pour $a \in A$, l'élément $\frac{1 + a}{2}$ de $A$ est strictement supérieur à $a$, donc $a$ n'est pas au-dessus de tout $A$. Pas de plus petit élément non plus, avec $\frac{a}{2}$. Les nombres $0$ et $1$ bornent $A$ sans lui appartenir.
$A = \mathbb{N}$. Minorants : $]-\infty, 0]$, et le plus petit élément est $0$. Aucun majorant : pour un réel $m$, l'entier naturel $n = \lfloor \lvert m \rvert \rfloor + 1$ vérifie $n > \lvert m \rvert \ge m$. Donc il n'y a pas de plus grand élément.

Dans $(\mathcal{P}(\{1, 2, 3\}), \subset)$, la partie $\mathcal{A} = \{\{1\}, \{2\}\}$ a pour majorants $\{1, 2\}$ et $\{1, 2, 3\}$ et pour seul minorant $\emptyset$ ; elle n'a ni plus grand ni plus petit élément. L'ensemble entier $\{1, 2, 3\}$ est le plus grand élément de $\mathcal{P}(\{1, 2, 3\})$ lui-même, et $\emptyset$ son plus petit élément.

Définition — Borne supérieure, borne inférieure

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A$ une partie de $E$.

Si l'ensemble des majorants de $A$ a un plus petit élément, cet élément est la borne supérieure de $A$, notée $\sup A$.
Si l'ensemble des minorants de $A$ a un plus grand élément, cet élément est la borne inférieure de $A$, notée $\inf A$.

Autrement dit, $M = \sup A$ lorsque $M$ est un majorant de $A$ et que $M \preccurlyeq m$ pour tout majorant $m$ de $A$ ; et $\mu = \inf A$ lorsque $\mu$ est un minorant de $A$ et que $m \preccurlyeq \mu$ pour tout minorant $m$ de $A$. Une borne supérieure, contrairement à un plus grand élément, n'appartient pas forcément à $A$, et elle n'existe pas forcément.

Proposition — Plus grand élément et borne supérieure

Soient $(E, \preccurlyeq)$ un ensemble ordonné et $A$ une partie de $E$.

$A$ a au plus une borne supérieure et au plus une borne inférieure.
Si $A$ a un plus grand élément $a$, alors $a$ est le seul majorant de $A$ qui appartient à $A$, et $\sup A = a$. Autrement dit, $\sup A = \max A$ lorsque $\max A$ existe.
Si $\sup A$ existe et appartient à $A$, alors c'est le plus grand élément de $A$.

Il en va de même pour le plus petit élément et la borne inférieure, avec les inégalités renversées.

Preuve

Unicité. La borne supérieure est le plus petit élément de l'ensemble des majorants, et par la Proposition « Unicité du plus grand élément » une partie a au plus un plus petit élément. Le même argument s'applique à la borne inférieure, plus grand élément de l'ensemble des minorants.
Une remarque. Un majorant de $A$ qui appartient à $A$ est, mot pour mot, un plus grand élément de $A$ : les deux signifient $m \in A$ et $x \preccurlyeq m$ pour tout $x \in A$.
Un plus grand élément. Soit $a$ un plus grand élément de $A$. Par la remarque, c'est un majorant de $A$ qui appartient à $A$. Soit $m$ un majorant de $A$ : comme $a \in A$, $a \preccurlyeq m$. Donc $a$ est au-dessous de tout majorant : c'est le plus petit élément de l'ensemble des majorants, c'est-à-dire $a = \sup A$. Soit maintenant $m$ un majorant de $A$ qui appartient à $A$. Par la remarque, $m$ est un plus grand élément de $A$, donc $m = a$ par la Proposition « Unicité du plus grand élément ».
Une borne supérieure dans $A$. Supposons que $M = \sup A$ existe et que $M \in A$. Alors $M$ est un majorant de $A$ qui appartient à $A$ : par la remarque, c'est un plus grand élément de $A$.
Dualité. La relation réciproque $\succcurlyeq$, définie par $x \succcurlyeq y \iff y \preccurlyeq x$, est un ordre sur $E$, ses trois axiomes étant ceux de $\preccurlyeq$ lus à l'envers. Pour cet ordre, les plus grands éléments, les majorants et les bornes supérieures sont les plus petits éléments, les minorants et les bornes inférieures de $\preccurlyeq$. Les énoncés pour le plus petit élément et la borne inférieure en découlent.

Exemple — Des bornes supérieures dans trois ensembles ordonnés

Dans $(\mathcal{P}(E), \subset)$, pour des parties $A$ et $B$ de $E$, $\sup\{A, B\} = A \cup B$ et $\inf\{A, B\} = A \cap B$. En effet $A \cup B$ est un majorant de $\{A, B\}$, puisque $A \subset A \cup B$ et $B \subset A \cup B$, par la Proposition « Lois de la réunion et de l'intersection » ; et pour tout majorant $C$, c'est-à-dire toute partie $C$ telle que $A \subset C$ et $B \subset C$, la Proposition « Réunion et intersection comme bornes » donne $A \cup B \subset C$. Pour l'intersection, les inclusions sont renversées : $A \cap B$ est un minorant, puisque $A \cap B \subset A$ et $A \cap B \subset B$, par la Proposition « Lois de la réunion et de l'intersection », et tout minorant $C$, avec $C \subset A$ et $C \subset B$, vérifie $C \subset A \cap B$. La Proposition « Réunion et intersection comme bornes » est relue : la réunion est la borne supérieure, l'intersection la borne inférieure.
Dans $(D_{12}, \mid)$, la partie $\{4, 6\}$ a pour seul majorant $12$, le seul élément de $D_{12}$ divisible par $4$ et par $6$, donc $\sup\{4, 6\} = 12$. Ses minorants sont les diviseurs communs $1$ et $2$, et $1 \mid 2$ fait de $2$ le plus grand : $\inf\{4, 6\} = 2$.
Dans $(\mathbb{R}, \le)$, $\sup\, [0, 1[ \, = 1$, bien que $[0, 1[$ n'ait pas de plus grand élément. Le réel $1$ est un majorant. Soit $m$ un majorant de $[0, 1[$ : puisque $0 \in [0, 1[$, $m \ge 0$ ; si $m < 1$, le nombre $\frac{1 + m}{2}$ est dans $[0, 1[$ et dépasse $m$, ce qui est impossible ; donc $m \ge 1$. Comme $1 \notin [0, 1[$, la Proposition « Plus grand élément et borne supérieure » confirme qu'il n'y a pas de plus grand élément : ce serait $\sup\, [0, 1[ \, = 1$, qui n'appartient pas à la partie.

Méthode — Déterminer une borne supérieure

Pour déterminer la borne supérieure $M$ d'une partie $A$ d'un ensemble ordonné $(E, \preccurlyeq)$, un candidat $M$ ayant été deviné :

Vérifier que $M$ est un majorant : $x \preccurlyeq M$ pour tout $x \in A$.
Vérifier que c'est le plus petit : tout majorant $m$ vérifie $M \preccurlyeq m$. Dans un ensemble totalement ordonné, cela équivaut, par la Proposition « Nier une inégalité », à : pour tout $m \prec M$, un élément $a \in A$ vérifie $m \prec a$, de sorte que $m$ n'est pas un majorant.
S'arrêter au plus grand élément : si $M \in A$, alors $M$ est le plus grand élément de $A$ et $\sup A = \max A$, par la Proposition « Plus grand élément et borne supérieure ».

Pour la borne inférieure, renverser les inégalités.
Par exemple, soit $A = \{x \in \mathbb{R} \mid x^2 < 4\}$. Comme $x^2 < 4 \iff -2 < x < 2$, $A = \, ]-2, 2[$. Le candidat est $M = 2$. C'est un majorant : $x < 2$ pour tout $x \in A$. Soit $m < 2$ un réel, et cherchons un élément de $A$ au-dessus de $m$ : si $m < 0$, alors $0 \in A$ et $m < 0$ ; si $0 \le m < 2$, alors $\frac{m + 2}{2} \in A$ et $\frac{m + 2}{2} > m$. Donc aucun $m < 2$ n'est un majorant, et $\sup A = 2$. Comme $2 \notin A$, $A$ n'a pas de plus grand élément.

Piège — une partie majorée peut n'avoir pas de borne supérieure

Une borne supérieure dépend de l'ensemble ordonné. Une partie majorée n'a pas forcément de borne supérieure, car le plus petit majorant peut manquer à l'ensemble ordonné. Dans $(\mathbb{Q}, \le)$, la partie $A = \{x \in \mathbb{Q} \mid x^2 < 2\}$ est majorée, par $2$. Soit $m$ un majorant rationnel de $A$ : $m \ge 1$, puisque $1 \in A$. Le rationnel $m' = \frac{2m + 2}{m + 2}$ vérifie $m' - m = \frac{2 - m^2}{m + 2}$ et $m'^2 - 2 = \frac{2(m^2 - 2)}{(m + 2)^2}$. Si $m^2 < 2$, alors $m' \in A$ et $m' > m$, ce qui est impossible puisque $m$ majore $A$ ; et $m^2 \ne 2$ par l'irrationalité de $\sqrt{2}$. Donc $m^2 > 2$, et alors $m' < m$ et $m'^2 > 2$ : tout $x \in A$ vérifie $x^2 < 2 < m'^2$, donc $x < m'$ puisque $m' > 0$, et $m'$ est un majorant strictement plus petit que $m$. L'ensemble des majorants n'a pas de plus petit élément, et $A$ n'a pas de borne supérieure dans $\mathbb{Q}$. Dans $(\mathbb{R}, \le)$, au contraire, toute partie non vide majorée a une borne supérieure : c'est la propriété de la borne supérieure des réels, propriété de $\mathbb{R}$ qui relève de l'étude des nombres réels et ne découle pas des trois axiomes d'un ordre.

Signaler une erreur

Compétences à pratiquer

Distinguer plus grand élément et majorant ★
Déterminer majorants, minorants et éléments extrêmes ★
Calculer une borne supérieure ou inférieure dans $\mathbb{R}$ ★★
Déterminer une borne supérieure ou inférieure ★★
Démontrer qu'une borne supérieure n'existe pas ★★★

IV.3 Applications croissantes

Respecter l'ordre

Une application entre deux ensembles ordonnés peut respecter l'ordre ou non. Le chapitre Applications a rencontré deux cas : l'application $A \mapsto f(A)$, qui envoie une inclusion sur une inclusion, et une fonction strictement croissante d'une variable réelle, qui est injective. Les deux sont des cas d'une même notion, l'application croissante, qui compare l'ordre de l'ensemble de départ à celui de l'ensemble d'arrivée et se définit pour deux ensembles ordonnés quelconques. Elle se compose, elle obéit à des règles de signes simples, et lorsque l'ensemble de départ est totalement ordonné elle porte plus d'information qu'on ne l'attend.

Signaler une erreur

Définition — Application croissante

Soient $(E, \preccurlyeq)$ et $(F, \trianglelefteq)$ deux ensembles ordonnés, d'ordres stricts associés $\prec$ et $\triangleleft$, et $f \colon E \to F$ une application. L'application $f$ est :

croissante si $\forall (x, y) \in E^2, \ x \preccurlyeq y \Rightarrow f(x) \trianglelefteq f(y)$ ;
strictement croissante si $\forall (x, y) \in E^2, \ x \prec y \Rightarrow f(x) \triangleleft f(y)$ ;
décroissante si $\forall (x, y) \in E^2, \ x \preccurlyeq y \Rightarrow f(y) \trianglelefteq f(x)$ ;
strictement décroissante si $\forall (x, y) \in E^2, \ x \prec y \Rightarrow f(y) \triangleleft f(x)$.

Elle est monotone si elle est croissante ou décroissante, et strictement monotone si elle est strictement croissante ou strictement décroissante. Pour $E, F \subset \mathbb{R}$ munis de l'ordre $\le$, ce sont les fonctions croissantes, strictement croissantes, décroissantes et strictement décroissantes d'une variable réelle.

Exemple — Cinq applications entre ensembles ordonnés

Pour une partie fixée $C$ d'un ensemble $E$, l'application $X \mapsto X \cup C$ de $(\mathcal{P}(E), \subset)$ dans lui-même est croissante : si $X \subset Y$, alors $X \cup C \subset Y \cup C$, la Conséquence de la Proposition « Réunion et intersection comme bornes ». Elle n'est pas strictement croissante en général : pour $E = \{1, 2\}$ et $C = E$, $\emptyset \subsetneq \{1\}$, mais les deux images sont égales à $E$.
L'application $X \mapsto \overline{X}$ de $(\mathcal{P}(E), \subset)$ dans lui-même est décroissante : si $X \subset Y$, alors $\overline{Y} \subset \overline{X}$, par la Proposition « Propriétés du complémentaire ».
Pour une application $f \colon E \to F$, l'application $A \mapsto f(A)$ de $(\mathcal{P}(E), \subset)$ dans $(\mathcal{P}(F), \subset)$ est croissante : $A \subset B$ implique $f(A) \subset f(B)$, par la Proposition « Image directe et opérations ensemblistes ».
L'application $n \mapsto 2n$ de $(\mathbb{N}^*, \mid)$ dans lui-même est strictement croissante : si $m \mid n$, alors $2m \mid 2n$, et si de plus $m \ne n$, alors $2m \ne 2n$.
La partie entière $x \mapsto \lfloor x \rfloor$ de $(\mathbb{R}, \le)$ dans $(\mathbb{Z}, \le)$ est croissante : si $x \le y$, alors $$ \begin{aligned} \lfloor x \rfloor &\le x && \text{(définition de la partie entière)} \\ &\le y && \text{(hypothèse)} \\ &< \lfloor y \rfloor + 1, \end{aligned} $$ la dernière inégalité par la définition de la partie entière, donc l'entier $\lfloor x \rfloor$ est strictement inférieur à l'entier $\lfloor y \rfloor + 1$, d'où $\lfloor x \rfloor \le \lfloor y \rfloor$. Elle n'est pas strictement croissante : $\frac{1}{5} < \frac{7}{10}$ et $\lfloor \frac{1}{5} \rfloor = \lfloor \frac{7}{10} \rfloor = 0$.

Proposition — Composée d'applications monotones

Soient $(E, \preccurlyeq)$, $(F, \trianglelefteq)$ et $(G, \sqsubseteq)$ des ensembles ordonnés, d'ordres stricts associés $\prec$, $\triangleleft$ et $\sqsubset$, et $f \colon E \to F$, $g \colon F \to G$ deux applications monotones. La composée $g \circ f$ est monotone, et son sens suit la règle des signes :

deux applications croissantes, ou deux applications décroissantes, donnent une composée croissante ;
une application croissante et une décroissante, dans un ordre ou dans l'autre, donnent une composée décroissante.

Il en va de même pour des applications strictement monotones, la composée étant strictement monotone.

Preuve

Première démonstration : renverser un ordre. Le renversé d'un ordre $\preccurlyeq$ est la relation $\succcurlyeq$ définie par $x \succcurlyeq y \iff y \preccurlyeq x$ : c'est un ordre, comme dans la démonstration de la Proposition « Plus grand élément et borne supérieure », son ordre strict est le renversé $\succ$ de $\prec$, et son propre renversé est $\preccurlyeq$. Une application $h$ de $(E, \preccurlyeq)$ dans $(F, \trianglelefteq)$ est décroissante si et seulement si elle est croissante de $(E, \preccurlyeq)$ dans $(F, \trianglerighteq)$, car $h(y) \trianglelefteq h(x)$ signifie $h(x) \trianglerighteq h(y)$ ; et si et seulement si elle est croissante de $(E, \succcurlyeq)$ dans $(F, \trianglelefteq)$, car $x \preccurlyeq y$ signifie $y \succcurlyeq x$. Il en va de même pour « strictement décroissante » et « strictement croissante ». Donc renverser l'ordre de l'ensemble de départ, ou celui de l'ensemble d'arrivée, échange « croissante » et « décroissante », et renverser les deux ne change rien.
Renversons l'ordre de $E$ si $f$ est décroissante, et celui de $G$ si $g$ est décroissante ; soient $\preccurlyeq'$ et $\sqsubseteq'$ les ordres de $E$ et de $G$ ainsi obtenus. Alors $f$ et $g$ sont toutes deux croissantes, et $$ \begin{aligned} x \preccurlyeq' y &\Rightarrow f(x) \trianglelefteq f(y) && \text{($f$ croissante)} \\ &\Rightarrow g(f(x)) \sqsubseteq' g(f(y)), \end{aligned} $$ la dernière étape parce que $g$ est croissante : $g \circ f$ est croissante de $(E, \preccurlyeq')$ dans $(G, \sqsubseteq')$. Revenons aux ordres d'origine : chaque renversement échange « croissante » et « décroissante », et il y a un renversement par application décroissante parmi $f$ et $g$. Donc $g \circ f$ est croissante lorsque $f$ et $g$ sont toutes deux croissantes ou toutes deux décroissantes (aucun renversement, ou deux), et décroissante lorsqu'exactement une des deux est décroissante (un renversement). Pour des applications strictement monotones l'argument est le même, la chaîne partant de l'ordre strict.
Seconde démonstration : les quatre cas, écrits un à un. Soient $x, y \in E$ tels que $x \preccurlyeq y$. Chacune de $f$ et $g$ est croissante ou décroissante, donc il y a quatre cas, qui couvrent toutes les possibilités.

$f$ et $g$ croissantes : $$ \begin{aligned} x \preccurlyeq y &\Rightarrow f(x) \trianglelefteq f(y) && \text{($f$ croissante)} \\ &\Rightarrow g(f(x)) \sqsubseteq g(f(y)), \end{aligned} $$ la dernière étape parce que $g$ est croissante : $g \circ f$ est croissante.
$f$ croissante, $g$ décroissante : $$ \begin{aligned} x \preccurlyeq y &\Rightarrow f(x) \trianglelefteq f(y) && \text{($f$ croissante)} \\ &\Rightarrow g(f(y)) \sqsubseteq g(f(x)), \end{aligned} $$ la dernière étape parce que $g$ est décroissante : $g \circ f$ est décroissante.
$f$ décroissante, $g$ croissante : $$ \begin{aligned} x \preccurlyeq y &\Rightarrow f(y) \trianglelefteq f(x) && \text{($f$ décroissante)} \\ &\Rightarrow g(f(y)) \sqsubseteq g(f(x)), \end{aligned} $$ la dernière étape parce que $g$ est croissante : $g \circ f$ est décroissante.
$f$ et $g$ décroissantes : $$ \begin{aligned} x \preccurlyeq y &\Rightarrow f(y) \trianglelefteq f(x) && \text{($f$ décroissante)} \\ &\Rightarrow g(f(x)) \sqsubseteq g(f(y)), \end{aligned} $$ la dernière étape parce que $g$ est décroissante : $g \circ f$ est croissante.

Pour des applications strictement monotones, les quatre chaînes sont les mêmes avec $\prec$, $\triangleleft$, $\sqsubset$ à la place de $\preccurlyeq$, $\trianglelefteq$, $\sqsubseteq$ : en partant de $x \prec y$, l'inégalité stricte que donne la stricte monotonie de $f$ est transportée par la stricte monotonie de $g$.

Proposition — Applications strictement croissantes sur un ensemble totalement ordonné

Soient $(E, \preccurlyeq)$ un ensemble totalement ordonné, $(F, \trianglelefteq)$ un ensemble ordonné et $f \colon E \to F$ une application strictement croissante. Alors :

$f$ est injective ;
$f$ reflète l'ordre : pour tous $x, y \in E$, $x \preccurlyeq y \iff f(x) \trianglelefteq f(y)$ ; en particulier $f$ est croissante.

La totalité est nécessaire. L'application $X \mapsto \lvert X \rvert$ de $(\mathcal{P}(\{1, 2\}), \subset)$ dans $(\mathbb{N}, \le)$ est strictement croissante, comme le montrent les cinq inclusions strictes $\emptyset \subsetneq \{1\}$, $\emptyset \subsetneq \{2\}$, $\emptyset \subsetneq \{1, 2\}$, $\{1\} \subsetneq \{1, 2\}$ et $\{2\} \subsetneq \{1, 2\}$, mais $\lvert \{1\} \rvert = \lvert \{2\} \rvert$ avec $\{1\} \ne \{2\}$, donc elle n'est pas injective, et $\lvert \{1\} \rvert \le \lvert \{2\} \rvert$ alors que $\{1\} \subset \{2\}$ est faux. Pour $E \subset \mathbb{R}$ et $F = \mathbb{R}$, le premier point est le cas strictement croissant de la Proposition « La stricte monotonie implique l'injectivité » du chapitre Applications.

Preuve

Réflexion de l'ordre. Soient $x, y \in E$. Supposons $x \preccurlyeq y$. Ou bien $x = y$, donc $f(x) = f(y)$ et $f(x) \trianglelefteq f(y)$ par réflexivité ; ou bien $x \prec y$, donc $f(x) \triangleleft f(y)$ et $f(x) \trianglelefteq f(y)$. Réciproquement, on démontre la contraposée : supposons que $x \preccurlyeq y$ est faux. Alors $$ \begin{aligned} \neg(x \preccurlyeq y) &\Rightarrow y \prec x && \text{(« Nier une inégalité », ordre total)} \\ &\Rightarrow f(y) \triangleleft f(x) && \text{($f$ strictement croissante)} \\ &\Rightarrow \neg\bigl(f(x) \trianglelefteq f(y)\bigr), \end{aligned} $$ la dernière étape par le premier point de la Proposition « Nier une inégalité », appliquée dans $F$. Donc $f(x) \trianglelefteq f(y)$ implique $x \preccurlyeq y$.
Injectivité, par la réflexion de l'ordre. Soient $x, y \in E$ avec $f(x) = f(y)$. Alors $f(x) \trianglelefteq f(y)$ et $f(y) \trianglelefteq f(x)$ par réflexivité, donc $x \preccurlyeq y$ et $y \preccurlyeq x$ par la réflexion de l'ordre, et $x = y$ par antisymétrie.
Injectivité, seconde démonstration : par la trichotomie. Soient $x, y \in E$ avec $x \ne y$. L'ordre étant total, $x \preccurlyeq y$ ou $y \preccurlyeq x$, et comme $x \ne y$, $x \prec y$ ou $y \prec x$. Dans le premier cas $f(x) \triangleleft f(y)$ et dans le second $f(y) \triangleleft f(x)$, parce que $f$ est strictement croissante ; dans les deux cas $f(x) \ne f(y)$, par la définition de l'ordre strict. Ainsi $x \ne y$ implique $f(x) \ne f(y)$, ce qui est, par contraposition, l'injectivité de $f$ ; cette démonstration n'utilise pas la réflexion de l'ordre.

Méthode — Démontrer qu'une application est monotone

Pour démontrer qu'une application $f \colon E \to F$ entre ensembles ordonnés est croissante, ou décroissante :

Fixer $x \preccurlyeq y$ dans $E$, génériques, et en déduire $f(x) \trianglelefteq f(y)$ pour une application croissante, $f(y) \trianglelefteq f(x)$ pour une décroissante, par une chaîne d'inégalités dont chacune nomme la loi qui la donne. Lorsque $f$ est construite à partir d'applications plus simples, utiliser la Proposition « Composée d'applications monotones » ; pour une fonction réelle sur un intervalle, le signe de la dérivée.
Pour réfuter : pour « croissante », donner un couple $x \preccurlyeq y$ tel que $f(x) \trianglelefteq f(y)$ soit faux, et le vérifier ; pour « monotone », donner deux couples, l'un qui met en défaut « croissante » et l'autre « décroissante ».
Pour la version stricte, partir de $x \prec y$ et démontrer l'inégalité stricte, par la même chaîne avec au moins une étape stricte.

Par exemple, l'application $\varphi \colon (\mathbb{R}, \le) \to (\mathcal{P}(\mathbb{R}), \subset)$, $t \mapsto \, ]-\infty, t]$, est strictement croissante. Soit $s < t$. Si $x \in \, ]-\infty, s]$, alors $x \le s < t$, donc $x \in \, ]-\infty, t]$ : $\varphi(s) \subset \varphi(t)$. Et $t \in \varphi(t)$ alors que $t \notin \varphi(s)$, puisque $t > s$ : $\varphi(s) \ne \varphi(t)$. Donc $\varphi(s) \subsetneq \varphi(t)$. Comme $\mathbb{R}$ est totalement ordonné, la Proposition « Applications strictement croissantes sur un ensemble totalement ordonné » donne davantage : $\varphi$ est injective, et $s \le t \iff \, ]-\infty, s] \subset \, ]-\infty, t]$. En revanche $x \mapsto x^2$, de $(\mathbb{R}, \le)$ dans lui-même, n'est pas monotone : $-2 \le -1$ mais $(-2)^2 \le (-1)^2$ est faux, donc elle n'est pas croissante ; et $1 \le 2$ mais $2^2 \le 1^2$ est faux, donc elle n'est pas décroissante.

Pour aller plus loin

L'ensemble des classes. L'ensemble des classes d'une relation d'équivalence $\sim$ sur $E$ se note $E / {\sim}$ et s'appelle l'ensemble quotient ; l'application $x \mapsto \mathrm{cl}(x)$ en est la surjection canonique. Les ensembles $\mathbb{Z}/n\mathbb{Z}$, formé des $n$ classes modulo $n$, et $\mathbb{R}/2\pi\mathbb{Z}$, formé des angles modulo un tour, sont des ensembles quotients. La somme de deux classes modulo $n$ est la classe de la somme de leurs représentants, et cela ne dépend pas des représentants choisis : c'est le contenu de l'arithmétique des congruences.
Des nombres et des vecteurs comme classes. Un nombre rationnel est une classe de couples : $\frac{a}{b}$ est la classe de $(a, b)$ dans $\mathbb{Z} \times \mathbb{Z}^*$ pour la relation $(a, b) \sim (c, d) \iff ad = bc$, et les couples $(1, 2)$, $(2, 4)$ et $(-3, -6)$ de $\mathbb{Z} \times \mathbb{Z}^*$ sont trois représentants d'une même classe, le nombre rationnel $\frac{1}{2}$. Un vecteur du plan est une classe de bipoints : $(A, B) \sim (C, D)$ lorsque $ABDC$ est un parallélogramme, éventuellement aplati, c'est-à-dire lorsque les segments $[AD]$ et $[BC]$ ont le même milieu, et le vecteur $\overrightarrow{AB}$ est la classe de $(A, B)$.
Prolonger un ordre. Tout ordre sur un ensemble fini est contenu dans un ordre total : lister les éléments de sorte que $x$ soit avant $y$ chaque fois que $x \prec y$, ce qui est un tri topologique, et comparer deux éléments par leurs positions dans la liste. Pour un ensemble infini, c'est le théorème de Szpilrajn, qui utilise l'axiome du choix.

Signaler une erreur

Compétences à pratiquer

Décider si une application est monotone ★
Démontrer une propriété des applications monotones ★★
Exploiter une application croissante ★★★

V Exercices de colle

Compétences à pratiquer

Travailler un exercice de colle ★
Travailler un exercice de colle ★★
Travailler un exercice de colle ★★★
Travailler un exercice de colle ★★★★

VI Problèmes d'écrit

Compétences à pratiquer

Travailler un problème d'écrit ★
Travailler un problème d'écrit ★★
Travailler un problème d'écrit ★★★
Travailler un problème d'écrit ★★★★
Quiz

Devoir facile : deux ordres sur les couples d'entiers

4 exercices, sur 20 points. Durée indicative : 1 h 30.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Devoir difficile : chaînes, antichaînes et couplages

3 exercices, sur 20 points. Durée indicative : 3 h.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Aller à la section

relation	R	S	A	T
\(=\) sur un ensemble \(E\)	oui	oui	oui	oui
\(\le\) sur \(\mathbb{R}\)	oui	non	oui	oui
\(<\) sur \(\mathbb{R}\)	non	non	oui	oui
\(\mid\) sur \(\mathbb{N}\)	oui	non	oui	oui
\(\mid\) sur \(\mathbb{Z}\)	oui	non	non	oui
même parité sur \(\mathbb{Z}\)	oui	oui	non	oui
\(\ne\) sur \(\mathbb{R}\)	non	oui	non	non