Corrigé, et les relations d’ordre

Deux des cinq relations proposées sont des équivalences, une est un ordre, et les deux qui échouent le font pour des raisons opposées : l’une perd la transitivité, l’autre la symétrie. Le corrigé les traite dans l’ordre, puis démonte la démonstration fausse — dont l’erreur tient à quatre mots — et termine sur la notion que l’exercice avait laissée en réserve : l’ordre, et ce que signifie exactement le mot partiel.

L’article corrige l’exercice précédent de la série Aux fondations, « Cinq relations, lesquelles sont des équivalences ? », et il prolonge « Relations d’équivalence et passage au quotient ». Les règles de déduction qu’il met en cause au paragraphe 6 sont celles de l’anatomie du mot « donc ».

1. La parité sur ℤ : une équivalence à deux classes

La relation $x\,\mathcal{R}_{a}\,y$ signifie que $x-y$ est pair, c’est-à-dire qu’il existe $k\in\mathbb{Z}$ tel que $x-y=2k$ . Réflexivité : $x-x=0=2\cdot 0$ . Symétrie : si $x-y=2k$ , alors $y-x=2(-k)$ . Transitivité : si $x-y=2k$ et $y-z=2\ell$ , alors $x-z=2(k+\ell)$ . C’est donc une relation d’équivalence, et les trois vérifications n’ont utilisé que la stabilité de $2\mathbb{Z}$ par opposé et par somme.

La division euclidienne par $2$ donne pour tout entier $x=2q+r$ avec $r\in\{0,1\}$ , et $x-r=2q$ : chaque entier est donc équivalent à $0$ ou à $1$ . Ces deux classes sont distinctes, puisque $1-0=1$ n’est pas pair. Le quotient a exactement deux éléments, les pairs et les impairs, et $\{0,1\}$ est un système de représentants. C’est l’ensemble noté $\mathbb{Z}/2\mathbb{Z}$ .

2. L’écart d’au plus un : la transitivité tombe

La relation $|x-y|\leq 1$ est réflexive, puisque $|x-x|=0$ , et symétrique, puisque $|x-y|=|y-x|$ . Elle n’est pas transitive : $|0-1|=1\leq 1$ et $|1-2|=1\leq 1$ , mais $|0-2|=2>1$ . Elle n’est donc pas une relation d’équivalence, et elle n’est pas non plus un ordre, faute d’antisymétrie — $0$ et $1$ se répondent sans être égaux.

L’exemple mérite mieux qu’un rejet. Il modélise une ressemblance : être proche à une unité près. Or la ressemblance ne se transmet pas, et c’est exactement pour cela qu’elle ne permet aucun quotient. Sans transitivité, pas de classes : les ensembles $\mathcal{R}_{b}(0)=[-1,1]$ et $\mathcal{R}_{b}(1)=[0,2]$ ne sont ni égaux ni disjoints, ce que la proposition du paragraphe 2 de l’article précédent interdit à deux classes.

3. La différence entière : une équivalence dont le quotient est un cercle

Pour $x-y\in\mathbb{Z}$ , les trois vérifications sont celles du paragraphe 1, avec $\mathbb{Z}$ au lieu de $2\mathbb{Z}$ : $0\in\mathbb{Z}$ , l’opposé d’un entier est entier, la somme de deux entiers est entière. C’est une relation d’équivalence sur $\mathbb{R}$ .

La classe de $x$ est $x+\mathbb{Z}=\{x+n\mid n\in\mathbb{Z}\}$ . Tout réel s’écrit de manière unique $x=\lfloor x\rfloor+t$ avec $t\in[0,1[$ , donc chaque classe rencontre $[0,1[$ en exactement un point : l’intervalle $[0,1[$ est un système de représentants, et le quotient est infini. Ce quotient, noté $\mathbb{R}/\mathbb{Z}$ , se représente comme un cercle : on enroule la droite réelle, et deux réels qui diffèrent d’un tour entier deviennent le même point. C’est la construction qui donne son sens à la phrase « les angles sont définis modulo un tour ».

4. Le parallélisme : une équivalence, et ses classes ont un nom

Avec la définition retenue — deux droites sont parallèles si elles sont égales ou sans point commun —, la réflexivité est acquise par le mot « égales », et la symétrie est évidente. La transitivité se démontre : soient $\mathcal{D}_{1}$ parallèle à $\mathcal{D}_{2}$ et $\mathcal{D}_{2}$ parallèle à $\mathcal{D}_{3}$ , avec $\mathcal{D}_{1}\neq\mathcal{D}_{3}$ . Si ces deux droites avaient un point commun $A$ , elles seraient deux parallèles distinctes à $\mathcal{D}_{2}$ passant par $A$ , ce que l’axiome des parallèles interdit. Elles sont donc sans point commun. Les classes s’appellent les directions.

Le mot « égales » n’est pas un ornement : si l’on définissait le parallélisme par la seule absence de point commun, la relation ne serait pas réflexive, et la transitivité tomberait aussi — deux droites parallèles distinctes seraient toutes deux parallèles à une troisième sans l’être entre elles dès qu’elles coïncident. Quant à l’espace, la réponse à la question posée en indication est négative sans précaution : la définition doit exiger que les droites soient coplanaires, faute de quoi deux droites non coplanaires seraient déclarées parallèles et la transitivité s’effondrerait.

5. La divisibilité n’est pas symétrique

Sur $\mathbb{N}^{\ast}$ , la divisibilité est réflexive ( $x=x\cdot 1$ ) et transitive (si $y=xk$ et $z=y\ell$ , alors $z=x(k\ell)$ ). Elle n’est pas symétrique : $2$ divise $4$ , et $4$ ne divise pas $2$ . Elle est en revanche antisymétrique : si $y=xk$ et $x=y\ell$ , alors $x=xk\ell$ , donc $k\ell=1$ dans $\mathbb{N}^{\ast}$ , donc $k=\ell=1$ et $x=y$ . C’est donc une relation d’ordre.

Le choix de $\mathbb{N}^{\ast}$ compte : sur $\mathbb{Z}$ , l’antisymétrie tombe, puisque $2$ et $-2$ se divisent mutuellement sans être égaux. Le même énoncé, sur un autre ensemble, cesse d’être un ordre : c’est une illustration de plus du fait qu’une relation ne se lit jamais sans l’ensemble sur lequel elle est posée.

Réponse à la question 2. Une relation qui serait à la fois une équivalence et un ordre serait symétrique et antisymétrique : de $xRy$ on tirerait $yRx$ , puis $x=y$ . Jointe à la réflexivité, cette condition force $R$ à être l’égalité, c’est-à-dire la diagonale $\{(x,x)\mid x\in X\}$ . Il y en a donc exactement une, sur n’importe quel ensemble.

6. La démonstration fausse, et les quatre mots coupables

L’argument disait : « soit $x\in X$ et soit $y$ tel que $xRy$ ». L’erreur est là, dans les quatre derniers mots. On ne peut introduire un objet vérifiant une propriété qu’après avoir établi qu’il en existe un ; la règle d’élimination du quantificateur existentiel exige une prémisse de la forme « il existe $y$ tel que $xRy$ », et cette prémisse n’a pas été démontrée. Elle est même exactement ce qu’il faudrait prouver : dire que tout $x$ est en relation avec au moins un élément, c’est dire que le domaine de définition de $R$ est $X$ tout entier.

Le contre-exemple le plus économique est la relation vide sur un ensemble non vide : elle est symétrique et transitive par vacuité — aucune prémisse n’est jamais satisfaite — et elle n’est pas réflexive. On peut aussi prendre $X=\{a,b,c\}$ et $R=\{(a,a),(a,b),(b,a),(b,b)\}$ : symétrique, transitive, mais $(c,c)\notin R$ .

Réponse à la question 7. L’énoncé correct est celui-ci : une relation symétrique, transitive et dont le domaine de définition est $X$ tout entier est réflexive. La démonstration est alors celle de l’énoncé fautif, mais légitimée : pour $x\in X$ , l’hypothèse fournit un $y$ avec $xRy$ , la symétrie donne $yRx$ , la transitivité conclut $xRx$ . Ce n’est pas le raisonnement qui était mauvais, c’est l’hypothèse manquante — et c’est la troisième fois dans cette série que la même leçon se présente.

Réponses aux questions 4 et 5. Si $R$ est réflexive, tout $x$ vérifie $xRx$ , donc possède une image : $D_{R}=X$ . La réciproque est fausse, et la relation $\{(a,b),(b,a)\}$ sur $\{a,b\}$ le montre — son domaine est $\{a,b\}$ tout entier sans qu’elle soit réflexive. Enfin, une relation d’équivalence qui serait aussi une application associerait à chaque $x$ exactement une image ; la réflexivité impose que cette image soit $x$ lui-même. La seule est donc l’application identité, dont le graphe est la diagonale — la même que celle du paragraphe 5, ce qui n’est pas une coïncidence.

7. Les relations d’ordre, et ce que « partiel » veut dire

Définition. Une relation binaire sur un ensemble est une relation d’ordre si elle est réflexive, antisymétrique et transitive. Elle est dite totale lorsque deux éléments quelconques sont toujours comparables, et partielle sinon.

Une seule propriété sépare l’ordre de l’équivalence : la symétrie devient l’antisymétrie. Le changement paraît mince ; il retourne complètement la notion. L’équivalence identifie et produit un quotient ; l’ordre hiérarchise et produit une structure. Il n’y a pas de « quotient par un ordre ».

Le mot partiel ne signifie pas « défini sur une partie », contresens fréquent : il signifie que la comparaison, elle, est partielle. Sur $\mathbb{N}^{\ast}$ ordonné par divisibilité, $2$ et $3$ ne sont comparables ni dans un sens ni dans l’autre, et pourtant la relation est parfaitement définie sur tout l’ensemble. Trois exemples suffisent à fixer l’échelle : $\leq$ sur $\mathbb{R}$ est un ordre total ; la divisibilité sur $\mathbb{N}^{\ast}$ est un ordre partiel ; l’inclusion $\subseteq$ sur $\mathcal{P}(X)$ est un ordre partiel dès que $X$ a au moins deux éléments, puisque deux singletons distincts ne s’incluent pas l’un l’autre.

Cette dernière est la plus importante des trois, parce qu’elle existe sur n’importe quel ensemble et qu’elle est le terrain de tous les énoncés d’existence maximale. C’est sur elle que s’appuiera l’article à paraître « L’axiome du choix et le lemme de Zorn », qui demande précisément ce qu’un ordre partiel doit vérifier pour qu’on puisse y garantir un élément maximal.

Les relations d’équivalence, les relations d’ordre et la relation d’inclusion sur l’ensemble des parties occupent la section 3.2 de Discours formel sur les mathématiques pour le secondaire, Volume I, où la relation vide sert déjà de contre-exemple à la réflexivité.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Corrigé, et les relations d’ordre

1. La parité sur ℤ : une équivalence à deux classes

2. L’écart d’au plus un : la transitivité tombe

3. La différence entière : une équivalence dont le quotient est un cercle

4. Le parallélisme : une équivalence, et ses classes ont un nom

5. La divisibilité n’est pas symétrique

6. La démonstration fausse, et les quatre mots coupables

7. Les relations d’ordre, et ce que « partiel » veut dire

Une réflexion sur “Corrigé, et les relations d’ordre”

Votre commentaire Annuler la réponse.

1. La parité sur ℤ : une équivalence à deux classes

2. L’écart d’au plus un : la transitivité tombe

3. La différence entière : une équivalence dont le quotient est un cercle

4. Le parallélisme : une équivalence, et ses classes ont un nom

5. La divisibilité n’est pas symétrique

6. La démonstration fausse, et les quatre mots coupables

7. Les relations d’ordre, et ce que « partiel » veut dire

Partagez :

Similaire

Une réflexion sur “Corrigé, et les relations d’ordre”

Votre commentaire Annuler la réponse.