Corrigé des exercices : Relations d’équivalence et d’ordre en L1 de maths

---

---

Pour démarrer

Corrigé de l’exercice 1 – Quatre relations sur un ensemble à quatre éléments

Idée clé : sur un ensemble fini, on teste chaque propriété en parcourant la liste des couples, et un seul couple fautif suffit à la réfuter.

1. Relation \(R_1\). Les quatre couples \((i,i)\) sont présents : elle est réflexive. Les couples non diagonaux vont par paires \((1,2),(2,1)\) et \((3,4),(4,3)\) : elle est symétrique. Elle n’est pas antisymétrique, car \(1 \,R_1\, 2\) et \(2 \,R_1\, 1\) avec \(1 \neq 2\). Enfin, elle est transitive. En effet, les seuls chemins \(x \to y \to z\) restent dans \(\{1,2\}\) ou dans \(\{3,4\}\), et tous les couples de ces blocs sont présents.

   Relation \(R_2\). La diagonale est complète : elle est réflexive. Elle n’est pas symétrique, car \((1,2)\) est présent sans \((2,1)\). Elle est antisymétrique, car aucun couple non diagonal n’a son inverse dans le graphe. Pour la transitivité, le seul chemin non trivial est \(1 \to 2 \to 3\), et \((1,3)\) est bien présent. Les autres chemins passent par un couple diagonal. Ainsi, \(R_2\) est transitive.

   Relation \(R_3\). Elle n’est pas réflexive, car \((2,2) \notin R_3\). Elle n’est pas symétrique, car \((1,2)\) est présent sans \((2,1)\). Elle est antisymétrique : les couples \((1,2), (2,3), (3,1)\) n’ont pas leur inverse. Elle n’est pas transitive : \(1 \,R_3\, 2\) et \(2 \,R_3\, 3\), mais \((1,3) \notin R_3\).

   Relation \(R_4\). Elle n’est pas réflexive, car \((1,1)\) manque. Elle est symétrique. Elle n’est pas antisymétrique : \(1 \,R_4\, 3\) et \(3 \,R_4\, 1\). Elle n’est pas transitive : \(1 \,R_4\, 3\) et \(3 \,R_4\, 1\), mais \((1,1) \notin R_4\).

2. Seule \(R_1\) est réflexive, symétrique et transitive. \(R_1\) est l’équivalence, de classes \(\{1,2\}\) et \(\{3,4\}\).
3. Seule \(R_2\) est réflexive, antisymétrique et transitive : c’est la relation d’ordre. Les éléments \(2\) et \(4\) ne sont pas comparables, car ni \((2,4)\) ni \((4,2)\) ne figurent dans \(R_2\). L’ordre \(R_2\) est donc partiel.

Corrigé de l’exercice 2 – Le chiffre des unités

Idée clé : le chiffre des unités de \(a\) est le reste \(r(a)\) de la division euclidienne de \(a\) par \(10\), et la relation s’écrit \(r(a) = r(b)\).

1. La relation s’écrit \(r(a) = r(b)\), où \(r : \mathbb{N} \to \{0, \dots, 9\}\). D’après le cours, une relation de la forme \(f(a) = f(b)\) est toujours une équivalence. Donc \(\sim\) est une relation d’équivalence.
2. Écrivons \(a = 10q + r(a)\) et \(b = 10q^{\prime} + r(b)\). Si \(r(a) = r(b)\), alors \(b – a = 10(q^{\prime} – q)\). Réciproquement, supposons \(10 \mid b – a\). Alors \(r(b) – r(a) = (b – a) – 10(q^{\prime} – q)\) est un multiple de \(10\). Or \(|r(b) – r(a)| \leqslant 9\), donc cette différence est nulle. Ainsi, \(a \sim b \iff 10 \mid b – a\).
3. La classe de \(7\) est \(\{7, 17, 27, 37, \dots\} = \{7 + 10k \mid k \in \mathbb{N}\}\). Les classes correspondent aux dix chiffres possibles. Il y a exactement \(10\) classes.
4. On a \(2026 – 1996 = 30\), multiple de \(10\) : \(2026 \sim 1996\). En revanche, \(2026\) se termine par \(6\) et \(2062\) par \(2\). Ces deux entiers ne sont pas équivalents.

Corrigé de l’exercice 3 – Une partie de N* ordonnée par la divisibilité

Idée clé : un majorant pour la divisibilité est un multiple commun, et un minorant est un diviseur commun.

1. Les relations de couverture dans \(A\) sont \(2 \mid 4\), \(2 \mid 6\), \(3 \mid 6\), \(4 \mid 12\), \(6 \mid 12\) et \(6 \mid 18\). Par exemple, \(3 \mid 18\) n’est pas une couverture, car \(6\) s’intercale. La figure présente ce diagramme, complété par \(1\) et \(36\).

2. Un plus grand élément serait divisible par \(12\) et par \(18\), donc au moins égal à \(36\). Aucun élément de \(A\) ne convient. De même, un plus petit élément diviserait \(2\) et \(3\), donc vaudrait \(1\). La partie \(A\) n’a ni plus grand ni plus petit élément.
3. Un majorant \(M\) est un multiple commun de tous les éléments de \(A\). Comme \(4 = 2^2\) et \(18 = 2 \times 3^2\), on a \(\operatorname{ppcm}(A) = 2^2 \times 3^2 = 36\). Les multiples communs sont exactement les multiples de \(36\). Ainsi, l’ensemble des majorants est \(36\,\mathbb{N}^*\). Le nombre \(36\) en fait partie et divise tous les autres. Donc \(\sup A = 36\), qui n’appartient pas à \(A\).
4. Un minorant divise à la fois \(2\) et \(3\), donc divise \(\operatorname{pgcd}(2,3) = 1\). Réciproquement, \(1\) divise tout. L’ensemble des minorants est \(\{1\}\). Donc \(\inf A = 1\).

Corrigé de l’exercice 4 – Une congruence déguisée

Idée clé : modulo \(3\), on a \(2 \equiv -1\), donc \(x + 2y \equiv x – y\).

1. Réflexivité : \(x + 2x = 3x\) est divisible par \(3\). Symétrie : supposons \(3 \mid x + 2y\). On écrit \(y + 2x = 3(x + y) – (x + 2y)\). C’est une différence de deux multiples de \(3\). Donc \(\mathcal{R}\) est réflexive et symétrique.
2. Supposons \(3 \mid x + 2y\) et \(3 \mid y + 2z\). En additionnant, \(3 \mid x + 3y + 2z\). Or \(3 \mid 3y\), donc \(3 \mid x + 2z\). La relation \(\mathcal{R}\) est transitive.
3. On a \(x + 2y = (x – y) + 3y\). Ainsi \(3 \mid x + 2y\) si et seulement si \(3 \mid x – y\). Les classes sont \(3\mathbb{Z}\), \(1 + 3\mathbb{Z}\) et \(2 + 3\mathbb{Z}\). Remarquons que la question 3 redonne d’un coup les questions 1 et 2.

Corrigé de l’exercice 5 – Les parties d’un ensemble à trois éléments

Idée clé : pour l’inclusion, un majorant d’une famille de parties est une partie qui les contient toutes.

1. Les parties \(\{1\}\) et \(\{2\}\) ne sont pas comparables : aucune n’est incluse dans l’autre. L’ordre est donc partiel.
2. Toute partie est incluse dans \(\{1,2,3\}\) et contient \(\varnothing\). Le plus grand élément est \(\{1,2,3\}\) et le plus petit est \(\varnothing\).
3. Un majorant de \(A\) contient \(1\) et \(2\) : ce sont \(\{1,2\}\) et \(\{1,2,3\}\). Le plus petit des deux est \(\{1,2\}\). Ensuite, un minorant est inclus dans \(\{1\} \cap \{2\} = \varnothing\), donc seul \(\varnothing\) convient. On obtient \(\sup A = \{1,2\}\) et \(\inf A = \varnothing\). Comme \(\{1,2\} \notin A\), la partie \(A\) n’a pas de plus grand élément.
4. Choisir un couple \(X \subset Y\) revient à décider, pour chacun des trois éléments, s’il est dans \(X\), dans \(Y \setminus X\) ou hors de \(Y\). Ces choix sont indépendants. Il y a donc \(3^3 = 27\) couples.

Corrigé de l’exercice 6 – Symétrique et antisymétrique à la fois

Idée clé : la symétrie fournit la relation dans les deux sens, puis l’antisymétrie conclut à l’égalité.

1. Supposons \(x \,\mathcal{R}\, y\). Par symétrie, \(y \,\mathcal{R}\, x\). On a donc à la fois \(x \,\mathcal{R}\, y\) et \(y \,\mathcal{R}\, x\). Par antisymétrie, \(x = y\).
2. D’après la question précédente, le graphe de \(\mathcal{R}\) est contenu dans la diagonale \(\{(x,x) \mid x \in E\}\). De plus, la réflexivité donne l’inclusion réciproque. Le graphe est exactement la diagonale : \(\mathcal{R}\) est l’égalité.
3. Prenons le graphe \(\{(1,2), (2,1), (2,3)\}\). Il n’est pas symétrique, car \((3,2)\) manque. Il n’est pas antisymétrique, car \(1\) et \(2\) sont liés dans les deux sens avec \(1 \neq 2\). Cette relation n’est ni symétrique ni antisymétrique.

Pour s’entraîner

Corrigé de l’exercice 7 – Classes définies par la fonction x exp(-x)

Idée clé : les classes sont les ensembles de niveau de \(f\), donc les abscisses des points où une droite horizontale coupe la courbe.

1. La relation est de la forme \(f(x) = f(y)\). C’est donc une relation d’équivalence, d’après la proposition du cours.
2. La fonction \(f\) est dérivable et \(f^{\prime}(x) = e^{-x} – x\,e^{-x} = (1 – x)\,e^{-x}\). Ainsi \(f\) est strictement croissante sur \(]-\infty, 1]\) et strictement décroissante sur \([1, +\infty[\). Son maximum vaut \(f(1) = e^{-1}\). En \(-\infty\), \(x \to -\infty\) et \(e^{-x} \to +\infty\), donc \(f(x) \to -\infty\). En \(+\infty\), les croissances comparées donnent \(f(x) \to 0\). Enfin, \(f(x)\) a le signe de \(x\). Donc \(f < 0\) sur \(]-\infty, 0[\), \(f(0) = 0\) et \(f > 0\) sur \(]0, +\infty[\).
3. Soit \(x \leqslant 0\) et \(y \sim x\). Alors \(f(y) = f(x) \leqslant 0\), donc \(y \leqslant 0\) d’après le signe. Or \(f\) est injective sur \(]-\infty, 1]\), car strictement croissante. Ainsi \(y = x\). Ensuite, si \(f(y) = f(1)\), alors \(y = 1\), car le maximum n’est atteint qu’en \(1\) : en effet, \(f(y) < f(1)\) pour \(y \neq 1\) par stricte monotonie de part et d’autre. Les classes de \(x \leqslant 0\) et de \(1\) sont des singletons.
4. Soit \(x \in ]0, 1[\). On a \(c = f(x) \in ]0, e^{-1}[\). Sur \([1, +\infty[\), la fonction \(f\) est continue et strictement décroissante, de \(e^{-1}\) vers \(0\). D’après le théorème de la bijection, il existe un unique \(y > 1\) tel que \(f(y) = c\). Sur \(]-\infty, 1]\), la valeur \(c\) n’est prise qu’en \(x\), par injectivité. Le cas \(x > 1\) se traite de façon symétrique. Toute autre classe a exactement deux éléments, l’un dans \(]0,1[\), l’autre dans \(]1, +\infty[\).
5. Calculons \(f(2\ln 2) = 2\ln 2 \cdot e^{-2\ln 2} = \dfrac{2\ln 2}{4} = \dfrac{\ln 2}{2}\). De même, \(f(\ln 2) = \ln 2 \cdot e^{-\ln 2} = \dfrac{\ln 2}{2}\). Ces deux réels sont distincts et \(\ln 2 \in ]0, 1[\). La classe de \(\ln 2\) est \(\{\ln 2,\ 2\ln 2\}\).

Corrigé de l’exercice 8 – Des paraboles comme classes

Idée clé : la relation compare la quantité \(\varphi(x, y) = y – x^2\), dont les ensembles de niveau sont des paraboles.

1. La relation s’écrit \(\varphi(x,y) = \varphi(x^{\prime}, y^{\prime})\) avec \(\varphi : \mathbb{R}^2 \to \mathbb{R}\). C’est une relation d’équivalence.
2. On a \(\varphi(1,3) = 3 – 1 = 2\). La classe de \((1,3)\) est donc l’ensemble des \((x,y)\) tels que \(y = x^2 + 2\). C’est la parabole d’équation \(y = x^2 + 2\). Plus généralement, la classe d’un point où \(\varphi\) vaut \(c\) est la parabole \(y = x^2 + c\), translatée verticalement de la parabole \(y = x^2\).
3. Un point de l’axe des ordonnées s’écrit \((0, y)\). Il appartient à la parabole \(y = x^2 + c\) si et seulement si \(y = c\). Chaque classe rencontre l’axe en un unique point, \((0, c)\).
4. Considérons \(\Phi : \mathbb{R}^2/\sim \to \mathbb{R}\), \(\overline{(x,y)} \mapsto y – x^2\). Elle est bien définie, car deux représentants d’une même classe donnent la même valeur. Elle est injective, car \(\Phi(\overline{u}) = \Phi(\overline{v})\) signifie \(u \sim v\). Elle est surjective, car \(\Phi(\overline{(0,c)}) = c\). Ainsi \(\Phi\) est une bijection de \(\mathbb{R}^2/\sim\) sur \(\mathbb{R}\).

Corrigé de l’exercice 9 – Égalité à une puissance de 2 près

Idée clé : l’exposant de \(2\) se compense librement, donc seule la partie impaire distingue les classes.

1. Réflexivité : \(a = 2^0 a\). Symétrie : si \(a = 2^k b\), alors \(b = 2^{-k} a\) avec \(-k \in \mathbb{Z}\). Transitivité : si \(a = 2^k b\) et \(b = 2^{j} c\), alors \(a = 2^{k + j} c\). C’est donc une relation d’équivalence.
2. Écrivons \(a = 2^v m\) et \(b = 2^w m^{\prime}\) avec \(m, m^{\prime}\) impairs. Si \(m = m^{\prime}\), alors \(a = 2^{v – w} b\), donc \(a \sim b\). Réciproquement, supposons \(a = 2^k b\). Si \(k \geqslant 0\), alors \(a = 2^{k + w} m^{\prime}\). L’unicité de l’écriture donne \(m = m^{\prime}\). Si \(k < 0\), on applique ce raisonnement à \(b = 2^{-k} a\). Ainsi, \(a \sim b\) équivaut à l’égalité des parties impaires.
3. On a \(12 = 2^2 \times 3\), de partie impaire \(3\). La classe de \(12\) est \(\{3, 6, 12, 24, 48, \dots\} = \{3 \cdot 2^j \mid j \in \mathbb{N}\}\).
4. Chaque classe contient exactement un impair, sa partie impaire commune. Une classe rencontre \(\{1, \dots, 20\}\) si et seulement si son impair est au plus \(20\). En effet, l’impair est le plus petit élément de la classe. Il y a dix impairs entre \(1\) et \(19\). Exactement \(10\) classes rencontrent \(\{1, \dots, 20\}\).

Corrigé de l’exercice 10 – Ordre lexicographique et ordre produit

Idée clé : l’ordre lexicographique compare d’abord les premières coordonnées, et la seconde n’intervient qu’en cas d’égalité.

1. Réflexivité : \(a = a\) et \(b \leqslant b\), donc \((a,b) \leqslant_{\ell} (a,b)\).

   Antisymétrie : supposons \((a,b) \leqslant_{\ell} (c,d)\) et \((c,d) \leqslant_{\ell} (a,b)\). Alors \(a \leqslant c\) et \(c \leqslant a\), donc \(a = c\). Les deux hypothèses donnent ensuite \(b \leqslant d\) et \(d \leqslant b\), donc \(b = d\).

   Transitivité : supposons \((a,b) \leqslant_{\ell} (c,d) \leqslant_{\ell} (e,f)\). On a \(a \leqslant c \leqslant e\). Si \(a < e\), c’est terminé. Sinon \(a = c = e\), et alors \(b \leqslant d \leqslant f\).

   Totalité : soient deux couples. Si \(a < c\) ou \(c < a\), ils sont comparables. Sinon \(a = c\), et on compare \(b\) et \(d\) dans \(\mathbb{R}\), où l’ordre est total. L’ordre lexicographique est un ordre total.

2. Pour l’ordre produit, \((x, y)\) majore \(A\) si et seulement si \(x \geqslant 1\) et \(y \geqslant 1\). Le couple \((1,1)\) est un majorant, et il est inférieur à tout autre. Donc \(\sup A = (1,1)\), qui n’est pas dans \(A\) : pas de plus grand élément. Pour l’ordre lexicographique, \(0 < 1\) donne \((0,1) \leqslant_{\ell} (1,0)\). Ainsi \(\max A = \sup A = (1,0)\) pour \(\leqslant_{\ell}\), tandis que \(\sup A = (1,1) \notin A\) pour \(\leqslant_p\).
3. Le couple \((1, 0)\) majore \(B\), car \(0 < 1\). Cherchons tous les majorants \((c,d)\). Si \(c < 0\), alors \((0, y)\) dépasse \((c,d)\). Si \(c = 0\), il faudrait \(y \leqslant d\) pour tout réel \(y\), ce qui est faux pour \(y = d + 1\). Si \(c > 0\), le couple convient. L’ensemble des majorants est donc \(\{(c,d) \mid c > 0\}\). Or, pour un tel couple, \((c/2, d)\) est encore un majorant, strictement plus petit. Les majorants n’ont pas de plus petit élément : \(B\) n’a pas de borne supérieure.

Corrigé de l’exercice 11 – Comparer des fonctions point par point

Idée clé : chaque propriété se vérifie en fixant un réel \(x\) et en utilisant l’ordre de \(\mathbb{R}\).

1. Pour tout \(x\), \(f(x) \leqslant f(x)\) : réflexivité. Si \(f \leqslant g\) et \(g \leqslant f\), alors \(f(x) = g(x)\) pour tout \(x\), donc \(f = g\). Enfin, \(f(x) \leqslant g(x) \leqslant h(x)\) donne la transitivité. C’est une relation d’ordre.
2. On a \(\cos 0 = 1 > 0 = \sin 0\), donc \(\cos \not\leqslant \sin\). En revanche, \(\cos(\pi/2) = 0 < 1 = \sin(\pi/2)\), donc \(\sin \not\leqslant \cos\). Les deux fonctions sont incomparables : l’ordre n’est pas total.
3. Pour tout \(x\), \(h(x) \geqslant \cos x\) et \(h(x) \geqslant \sin x\) : \(h\) est un majorant. Soit \(g\) un autre majorant. Pour tout \(x\), \(g(x)\) dépasse \(\cos x\) et \(\sin x\), donc dépasse leur maximum \(h(x)\). Ainsi \(h \leqslant g\). Donc \(\sup\{\cos, \sin\} = h\). Elle n’est égale ni à \(\cos\) ni à \(\sin\), comme le montre la figure.
4. Par le même raisonnement, en renversant les inégalités, \(\inf\{\cos, \sin\}\) est la fonction \(x \mapsto \min(\cos x, \sin x)\).

Corrigé de l’exercice 12 – Le rôle surprenant de 0 pour la divisibilité

Idée clé : tout entier divise \(0\), puisque \(0 = 0 \times a\) ; zéro se retrouve donc tout en haut de l’ordre.

1. Réflexivité : \(a = 1 \times a\). Transitivité : si \(b = ka\) et \(c = jb\), alors \(c = (jk)a\). Antisymétrie : supposons \(b = ka\) et \(a = \ell b\). Si \(a = 0\), alors \(b = 0\). Sinon \(a = k\ell a\) donne \(k\ell = 1\), donc \(k = \ell = 1\) et \(a = b\). La divisibilité est un ordre sur \(\mathbb{N}\).
2. On a \(1 \mid n\) et \(n \mid 0\) pour tout \(n \in \mathbb{N}\). Le plus petit élément est \(1\) et le plus grand est \(0\).
3. Décomposons : \(12 = 2^2 \cdot 3\), \(20 = 2^2 \cdot 5\) et \(45 = 3^2 \cdot 5\). Les majorants sont les multiples communs, c’est-à-dire les multiples de \(\operatorname{ppcm} = 2^2 \cdot 3^2 \cdot 5 = 180\), zéro compris. Le nombre \(180\) divise chacun d’eux. Ensuite, les minorants sont les diviseurs communs, donc les diviseurs de \(\operatorname{pgcd} = 1\). Ainsi \(\sup\{12, 20, 45\} = 180\) et \(\inf\{12, 20, 45\} = 1\).

Corrigé de l’exercice 13 – Être proches ne suffit pas

Idée clé : une équivalence qui relie les réels proches finit par relier tous les réels, par une chaîne de petits pas.

1. \(|x – x| = 0 \leqslant 1\) et \(|y – x| = |x – y|\) donnent la réflexivité et la symétrie. Cependant, \(0 \,\mathcal{R}\, 1\) et \(1 \,\mathcal{R}\, 2\), alors que \(|0 – 2| = 2 > 1\). La relation n’est pas transitive.
2. Raisonnons par récurrence sur \(n\). Pour \(n = 0\), c’est la réflexivité. Supposons \(x \sim x + n\). Comme \(|(x + n + 1) – (x + n)| = 1\), on a \(x + n \sim x + n + 1\). Par transitivité, \(x \sim x + n + 1\). Donc \(x \sim x + n\) pour tout \(n \in \mathbb{N}\).
3. Soient \(x \leqslant y\) deux réels et \(n = \lfloor y – x \rfloor\). Alors \(0 \leqslant y – (x + n) < 1\), donc \(x + n \sim y\). Avec la question précédente, \(x \sim y\). Si \(y < x\), on échange les rôles grâce à la symétrie. Tous les réels sont équivalents : \(\sim\) a une seule classe, \(\mathbb{R}\).

Corrigé de l’exercice 14 – Calculer dans Z/6Z

Idée clé : on calcule avec des représentants entre \(0\) et \(5\), puis on réduit modulo \(6\).

1. Les produits non triviaux, pour \(a, b \in \{2, \dots, 5\}\), donnent :
   \[\begin{array}{c|cccc} \times & 2 & 3 & 4 & 5 \\ \hline 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 \\ 4 & 2 & 0 & 4 & 2 \\ 5 & 4 & 3 & 2 & 1 \end{array}\]
   Les lignes de \(\overline{0}\) et \(\overline{1}\) sont immédiates : \(\overline{0}\,\overline{b} = \overline{0}\) et \(\overline{1}\,\overline{b} = \overline{b}\). La table complète s’en déduit.
2. On lit les zéros de la table hors de la ligne et de la colonne de \(\overline{0}\) : \(\overline{2}\,\overline{3} = \overline{0}\) et \(\overline{4}\,\overline{3} = \overline{0}\). À l’inverse, les lignes de \(\overline{1}\) et \(\overline{5}\) ne contiennent pas de zéro. Les classes cherchées sont \(\overline{2}\), \(\overline{3}\) et \(\overline{4}\).
3. Dans \(\mathbb{Z}/6\mathbb{Z}\), on a \(\overline{0} = \overline{6}\). Pourtant, \(0 \bmod 4 = 0\) et \(6 \bmod 4 = 2\). La même classe aurait deux images. Cette règle ne définit pas une application.
4. Supposons \(\overline{a} = \overline{b}\) dans \(\mathbb{Z}/6\mathbb{Z}\). Alors \(6 \mid b – a\), donc \(3 \mid b – a\), car \(3 \mid 6\). Ainsi \(a \bmod 3 = b \bmod 3\). L’image ne dépend pas du représentant : l’application est bien définie.

Corrigé de l’exercice 15 – D’une partition à une relation

Idée clé : deux éléments sont équivalents exactement lorsqu’ils sont dans le même bloc de la partition.

1. Les trois parties sont non vides et deux à deux disjointes. Leur réunion contient \(3 + 3 + 2 = 8\) éléments, à savoir \(1, \dots, 8\). C’est bien une partition de \(E\).
2. Le bloc \(\{1,4,7\}\) regroupe les éléments congrus à \(1\) modulo \(3\). De même, \(\{2,5,8\}\) regroupe ceux congrus à \(2\), et \(\{3,6\}\) ceux congrus à \(0\). Ainsi \(x \sim y \iff x \equiv y \ [3]\).
3. Dans un bloc de \(k\) éléments, il y a \(k^2\) couples. Le total vaut \(9 + 9 + 4 = 22\) couples.
4. La relation est symétrique, donc le couple \((y,x)\) est dans le graphe dès que \((x,y)\) y est. Le graphe est symétrique par rapport à la diagonale.

Pour approfondir

Corrigé de l’exercice 16 – Compter les relations sur quatre éléments

Idée clé : une relation est une partie de \(E \times E\), donc on compte des choix indépendants couple par couple.

1. L’ensemble \(E \times E\) a \(16\) éléments, donc \(2^{16} = 65\,536\) parties. Une relation réflexive contient obligatoirement les \(4\) couples diagonaux. Il reste \(12\) couples libres. Il y a \(65\,536\) relations, dont \(2^{12} = 4\,096\) réflexives.
2. Une relation symétrique est déterminée par deux types de choix. D’abord, on choisit librement les \(4\) couples diagonaux. Ensuite, pour chacune des \(\binom{4}{2} = 6\) paires \(\{x, y\}\) avec \(x \neq y\), on prend les deux couples \((x,y), (y,x)\) ou aucun. Il y a donc \(2^{4 + 6} = 1\,024\) relations symétriques.
3. Les équivalences correspondent exactement aux partitions. Sur \(\{a,b,c\}\), on trouve un seul bloc, ou un singleton et une paire (trois façons), ou trois singletons : \(1 + 3 + 1 = 5\). Sur \(E\), classons les partitions selon la taille des blocs :
   • un bloc de \(4\) : \(1\) partition ;
   • blocs de tailles \(3\) et \(1\) : \(4\) partitions, selon l’élément isolé ;
   • deux blocs de \(2\) : \(3\) partitions, car le partenaire de \(a\) détermine tout ;
   • blocs de tailles \(2, 1, 1\) : \(\binom{4}{2} = 6\) partitions ;
   • quatre singletons : \(1\) partition.

   Il y a \(5\) équivalences sur \(\{a,b,c\}\) et \(1 + 4 + 3 + 6 + 1 = 15\) équivalences sur \(E\).

Corrigé de l’exercice 17 – Intersection et réunion de deux équivalences

Idée clé : l’intersection hérite de chaque propriété, alors que la réunion casse la transitivité en mélangeant deux types de pas.

1. Notons \(\approx\) la relation « \(x \sim_1 y\) et \(x \sim_2 y\) ». Elle est réflexive, car \(\sim_1\) et \(\sim_2\) le sont. De même, elle est symétrique. Pour la transitivité, supposons \(x \approx y\) et \(y \approx z\). Alors \(x \sim_1 z\) par transitivité de \(\sim_1\), et de même \(x \sim_2 z\). Donc \(\approx\) est une équivalence.
2. On a \(x \equiv_2 y\) et \(x \equiv_3 y\) si et seulement si \(2\) et \(3\) divisent \(y – x\). Comme \(2\) et \(3\) sont premiers entre eux, c’est équivalent à \(6 \mid y – x\), par le lemme de Gauss. L’intersection est la congruence modulo \(6\).
3. On a \(0 \equiv_2 2\) et \(2 \equiv_3 5\). Pourtant \(5\) est impair et n’est pas multiple de \(3\). Donc ni \(0 \equiv_2 5\) ni \(0 \equiv_3 5\). La réunion n’est pas transitive.
4. Soit \(\sim\) une équivalence contenant \(\equiv_2\) et \(\equiv_3\). Pour tout entier \(a\), on a \(a \sim a + 3\) grâce à \(\equiv_3\), puis \(a + 3 \sim a + 1\) grâce à \(\equiv_2\). Ainsi \(a \sim a + 1\). Par récurrence et symétrie, \(a \sim b\) pour tous entiers \(a, b\). Réciproquement, la relation totale est bien une équivalence qui contient les deux congruences. La seule équivalence contenant \(\equiv_2\) et \(\equiv_3\) est \(\mathbb{Z} \times \mathbb{Z}\).

Corrigé de l’exercice 18 – Existence des bornes selon l’ordre choisi

Idée clé : une même partie peut avoir une borne supérieure pour un ordre et aucune pour un autre ; tout dépend de l’ensemble des majorants.

1. Posons \(U = \bigcup_{i} A_i\). Chaque \(A_i\) est inclus dans \(U\) : c’est un majorant. Soit \(M\) un autre majorant, donc \(A_i \subset M\) pour tout \(i\). Tout élément de \(U\) est dans un \(A_i\), donc dans \(M\) : ainsi \(U \subset M\). Par conséquent \(U\) est le plus petit majorant. De même, \(V = \bigcap_{i} A_i\) est inclus dans chaque \(A_i\). Si \(m \subset A_i\) pour tout \(i\), alors \(m \subset V\). Donc \(\sup = \bigcup_i A_i\) et \(\inf = \bigcap_i A_i\).
2. Supposons que \(M \in \mathbb{N}^*\) majore \(D\). Alors \(2^k \mid M\) pour tout \(k\), donc \(2^k \leqslant M\) puisque \(M \geqslant 1\). C’est absurde pour \(k = M\), car \(2^M > M\). La partie \(D\) n’a aucun majorant dans \((\mathbb{N}^*, \mid)\).
3. Dans \(\mathbb{N}\), le raisonnement précédent exclut tout majorant non nul. En revanche, \(0\) est divisible par tout entier, donc majore \(D\). Le seul majorant est \(0\), donc \(\sup D = 0\).
4. Dans \((\mathbb{R}, \leqslant)\), on a \(2^k \geqslant k\) pour tout \(k\), donc \(D\) n’est pas majorée. Elle n’a pas de borne supérieure dans \(\mathbb{R}\). En résumé, la même partie n’a aucun majorant dans \((\mathbb{N}^*, \mid)\), admet la borne supérieure \(0\) dans \((\mathbb{N}, \mid)\), et n’est pas majorée dans \(\mathbb{R}\).

Corrigé de l’exercice 19 – Problème : d’un préordre à un ordre

Idée clé : le préordre échoue seulement par manque d’antisymétrie ; en identifiant les éléments qui se précèdent mutuellement, on récupère un vrai ordre.

1. Réflexivité : \(x \preccurlyeq x\) deux fois, donc \(x \sim x\). La symétrie est immédiate, car la définition de \(\sim\) est symétrique en \(x\) et \(y\). Pour la transitivité, supposons \(x \sim y\) et \(y \sim z\). Alors \(x \preccurlyeq y \preccurlyeq z\) donne \(x \preccurlyeq z\), et \(z \preccurlyeq y \preccurlyeq x\) donne \(z \preccurlyeq x\). Donc \(\sim\) est une relation d’équivalence.
2. Par hypothèse, \(x^{\prime} \preccurlyeq x\), \(x \preccurlyeq y\) et \(y \preccurlyeq y^{\prime}\). Deux applications de la transitivité donnent \(x^{\prime} \preccurlyeq y^{\prime}\).
3. La question 2 montre exactement que la condition \(x \preccurlyeq y\) ne change pas quand on remplace \(x\) et \(y\) par d’autres représentants. La relation \(\leqslant\) est donc bien définie. Elle est réflexive et transitive, car \(\preccurlyeq\) l’est. Pour l’antisymétrie, supposons \(\overline{x} \leqslant \overline{y}\) et \(\overline{y} \leqslant \overline{x}\). Alors \(x \preccurlyeq y\) et \(y \preccurlyeq x\), c’est-à-dire \(x \sim y\). Ainsi \(\overline{x} = \overline{y}\), et \(\leqslant\) est une relation d’ordre sur \(E/\sim\).

4. La divisibilité sur \(\mathbb{Z}\) est réflexive, car \(a = 1 \cdot a\), et transitive, car \(b = ka\) et \(c = jb\) donnent \(c = (jk)a\). Ce n’est pas un ordre : \(2 \mid -2\) et \(-2 \mid 2\) avec \(2 \neq -2\).

   Décrivons \(\sim\). Si \(a \mid b\) et \(b \mid a\) avec \(a \neq 0\), on écrit \(b = ka\) et \(a = \ell b\), d’où \(k\ell = 1\) dans \(\mathbb{Z}\). Ainsi \(k = \pm 1\) et \(b = \pm a\). Si \(a = 0\), alors \(b = 0\). Réciproquement, \(a\) et \(-a\) se divisent mutuellement. Les classes sont donc \(\{a, -a\}\) pour \(a \geqslant 1\), et \(\{0\}\).

   L’application \(\Psi : \overline{a} \mapsto |a|\) est bien définie, car \(|a| = |-a|\). Elle est surjective, car \(n = \Psi(\overline{n})\) pour tout \(n \in \mathbb{N}\). Elle est injective, car \(|a| = |b|\) entraîne \(b = \pm a\), donc \(\overline{a} = \overline{b}\). Enfin, \(a \mid b\) équivaut à \(|a| \mid |b|\). Donc \(\Psi\) est une bijection de \(\mathbb{Z}/\sim\) sur \(\mathbb{N}\) qui transforme l’ordre quotient en divisibilité.

5. La relation \(|x| \leqslant |y|\) est réflexive et transitive : c’est un préordre. Ensuite, \(x \sim y\) signifie \(|x| \leqslant |y|\) et \(|y| \leqslant |x|\), c’est-à-dire \(|x| = |y|\). Les classes sont donc \(\{x, -x\}\) pour \(x > 0\), et \(\{0\}\). Pour deux classes \(\overline{x}\) et \(\overline{y}\), les réels \(|x|\) et \(|y|\) sont toujours comparables dans \(\mathbb{R}\). L’ordre quotient est total, et il s’identifie à l’ordre usuel sur \([0, +\infty[\).

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «corrigé des exercices : Relations d'équivalence et d'ordre en L1 de maths» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 406 cours et exercices de maths téléchargés en PDF et 4 250 exercices.