Relations binaires

Comparer, ordonner, classer : une relation binaire sur un ensemble \(E\) formalise tout lien entre deux éléments de \(E\). On étudie ses propriétés (réflexivité, transitivité, symétrie, antisymétrie), puis les deux grandes familles qu'elles engendrent — les relations d'ordre et les relations d'équivalence.

Définition et exemples

Définition — relation binaire

On appelle relation binaire sur \(E\) toute partie \(\mathcal R\) de \(E\times E\). Pour tous \(x,y\in E\), la proposition \((x,y)\in\mathcal R\) se note

\[ x\,\mathcal R\,y \]

et se lit « \(x\) est en relation avec \(y\) par \(\mathcal R\) ».

Attention à l'ordre du couple

Le couple \((x,y)\) n'est pas le couple \((y,x)\). La relation \(x\,\mathcal R\,y\) peut donc être vraie sans que \(y\,\mathcal R\,x\) le soit — c'est tout l'enjeu de la symétrie, étudiée à l'étape suivante.

Exemple

Des relations binaires déjà rencontrées :

l'égalité \(=\) sur \(E\) ;
\(\leqslant\) et \(<\) sur \(\mathbb R\) ;
l'inclusion \(\subseteq\) sur \(\mathcal P(E)\) ;
\(\leqslant\) sur \(\mathbb R^{\mathbb R}\), définie par \(f\leqslant g\Longleftrightarrow\forall x\in\mathbb R,\ f(x)\leqslant g(x)\) ;
la divisibilité \(\mid\) sur \(\mathbb Z\) : \(a\mid b\Longleftrightarrow\exists k\in\mathbb Z,\ b=ak\) ;
pour \(a\in\mathbb R\), la congruence modulo \(a\) sur \(\mathbb R\) : \(x\equiv y\ [a]\Longleftrightarrow\exists k\in\mathbb Z,\ x=y+ka\).

Propriétés des relations binaires

Définition

Soit \(\mathcal R\) une relation binaire sur \(E\).

Réflexivité : \(\forall x\in E,\ x\,\mathcal R\,x\).
Transitivité : \(\forall x,y,z\in E,\ (x\,\mathcal R\,y\ \text{et}\ y\,\mathcal R\,z) \Longrightarrow x\,\mathcal R\,z\).
Symétrie : \(\forall x,y\in E,\ x\,\mathcal R\,y\Longrightarrow y\,\mathcal R\,x\).
Antisymétrie : \(\forall x,y\in E,\ (x\,\mathcal R\,y\ \text{et}\ y\,\mathcal R\,x) \Longrightarrow x=y\).

2.1 — Visualiser une relation comme un graphe

Animation — quatre relations, quatre profils

Chaque flèche relie \(x\) à \(y\) lorsque \(x\,\mathcal R\,y\). Un anneau pointillé autour d'un point signale qu'il est en relation avec lui-même. Change d'onglet pour comparer.

Réflexive · transitive · symétrique · antisymétrique — chaque élément n'est en relation qu'avec lui-même.

Exemple

\(=\) sur \(E\) est réflexive, transitive, symétrique et antisymétrique.
\(\leqslant\) sur \(\mathbb R\) et \(\mathbb R^{\mathbb R}\) est réflexive, transitive et antisymétrique, mais pas symétrique.
\(<\) sur \(\mathbb R\) est transitive et antisymétrique, mais ni réflexive ni symétrique.
« Avoir le même signe » sur \(\mathbb R^*\) est réflexive, transitive et symétrique.
\(\subseteq\) sur \(\mathcal P(E)\) est réflexive, transitive et antisymétrique.

Démonstration — divisibilité sur \(\mathbb Z\) et \(\mathbb N\)

La relation \(\mid\) est réflexive et transitive sur \(\mathbb Z\) et \(\mathbb N\), mais antisymétrique seulement sur \(\mathbb N\), car \(a\mid b\) et \(b\mid a\Longleftrightarrow|a|=|b|\).

Réflexivité : \(a=a\cdot1\) avec \(1\in\mathbb Z\), donc \(a\mid a\).
Transitivité : si \(a\mid b\) et \(b\mid c\), alors \(b=ak\) et \(c=b\ell\), d'où \(c=a(k\ell)\), donc \(a\mid c\).
Antisymétrie : \(a\mid b\) et \(b\mid a\) donnent \(|a|=|b|\) ; sur \(\mathbb N\), cela force \(a=b\), mais pas sur \(\mathbb Z\) (ex. \(a=2,\,b=-2\)).

Relations d'ordre

Définition — relation d'ordre, ordre total

On appelle relation d'ordre sur \(E\) toute relation binaire réflexive, transitive et antisymétrique. Elle est dite totale si

\[ \forall x,y\in E,\quad (x\preccurlyeq y\ \text{ou}\ y\preccurlyeq x), \]

et partielle sinon.

Exemple

\(\leqslant\) est un ordre total sur \(\mathbb R\).
\(\leqslant\) sur \(\mathbb R^{\mathbb R}\) est un ordre partiel : \(\cos\) et \(\sin\) ne sont pas comparables.
\(\subseteq\) est un ordre partiel sur \(\mathcal P(E)\).
\(\mid\) est un ordre partiel sur \(\mathbb N\), mais n'est même pas un ordre sur \(\mathbb Z\) (défaut d'antisymétrie).

Théorème — relation stricte associée

Soit \(\preccurlyeq\) un ordre sur \(E\). On définit la relation stricte par

\[ x\prec y \Longleftrightarrow \bigl(x\preccurlyeq y\ \text{et}\ x\neq y\bigr). \]

Alors \(\prec\) est transitive et antisymétrique : c'est la relation stricte associée à \(\preccurlyeq\).

Démonstration

Transitivité : si \(x\prec y\) et \(y\prec z\), alors \(x\preccurlyeq z\) par transitivité de \(\preccurlyeq\), et \(x\neq z\) (sinon \(x\preccurlyeq y\preccurlyeq x\) donnerait \(x=y\)) ; donc \(x\prec z\).
Antisymétrie : il est impossible d'avoir simultanément \(x\prec y\) et \(y\prec x\), puisque cela imposerait \(x\neq y\) et \(x=y\).

Exemple

\(<\) usuelle sur \(\mathbb R\) est la relation stricte associée à \(\leqslant\).

Relations d'équivalence

Définition

On appelle relation d'équivalence sur \(E\) toute relation binaire réflexive, transitive et symétrique.

Exemple

« Avoir le même signe » sur \(\mathbb R^*\).
La congruence modulo \(a\in\mathbb R\) (ou \(n\in\mathbb N\)).

Démonstration pour \(\equiv[a]\)

Réflexivité : \(x\equiv x\ [a]\) car \(x-x=0=0\cdot a\).
Transitivité : si \(x\equiv y\ [a]\) et \(y\equiv z\ [a]\), alors \(x\equiv z\ [a]\).
Symétrie : si \(x\equiv y\ [a]\), alors \(y\equiv x\ [a]\).

4.1 — Classes, ensemble quotient, représentants

Théorème — vocabulaire

Soit \(\sim\) une relation d'équivalence sur \(E\).

Classe de \(x\) : \(\operatorname{cl}(x)=\{y\in E\mid y\sim x\}\).
Ensemble quotient : \(E/{\sim}=\{\operatorname{cl}(x)\mid x\in E\}\).
Ensemble de représentants : un sous-ensemble de \(E\) contenant exactement un élément de chaque classe.

Remarque — la carte géographique

L'ensemble quotient \(E/{\sim}\) est un ensemble de parties de \(E\). Chaque classe est comme un pays à l'intérieur de \(E\), dont les éléments partagent une même « nationalité ». Le monde \(E\) se trouve ainsi partitionné en pays. Choisir un ensemble de représentants, c'est désigner un ambassadeur — et un seul — par pays.

Démonstration

Montrons d'abord que, pour tous \(x,y\in E\),

\[ \operatorname{cl}(x)=\operatorname{cl}(y) \Longleftrightarrow \operatorname{cl}(x)\cap\operatorname{cl}(y)\neq\varnothing \Longleftrightarrow x\sim y. \]

Si \(\operatorname{cl}(x)=\operatorname{cl}(y)\), l'intersection contient \(x\) : elle est non vide.
Si \(\operatorname{cl}(x)\cap\operatorname{cl}(y)\neq\varnothing\), soit \(z\) dans cette intersection ; alors \(z\sim x\) et \(z\sim y\), donc \(x\sim y\) par symétrie et transitivité.
Si \(x\sim y\), montrons \(\operatorname{cl}(x)\subseteq \operatorname{cl}(y)\) (l'autre inclusion vient de la symétrie) : pour \(z\in\operatorname{cl}(x)\), \(z\sim x\) et \(x\sim y\) donnent \(z\sim y\) par transitivité.

Les classes forment ensuite une partition de \(E\) :

pour tout \(x\), \(x\sim x\) donc \(x\in\operatorname{cl}(x)\) : chaque classe est non vide ;
\(E=\bigcup_{x\in E}\operatorname{cl}(x)\), car \(x\in\operatorname{cl}(x)\) pour tout \(x\) ;
deux classes sont égales ou disjointes, d'après le point précédent.

Exemple — même signe

Notons \(\mathcal S\) la relation « avoir le même signe » sur \(\mathbb R^*\). Tout réel non nul a le signe de \(1\) ou de \(-1\), et \(1\), \(-1\) n'ont pas le même signe.

Résultat \[ \mathbb R^*/\mathcal S=\{\mathbb R_+^*,\mathbb R_-^*\},\qquad \{1,-1\}\ \text{est un ensemble de représentants.} \]

4.2 — Congruence modulo \(n\) : une partition animée

Animation — \(\mathbb Z/n\mathbb Z\)

Chaque point représente un entier ; sa couleur indique sa classe modulo \(n\). Fais varier \(n\) : les entiers d'une même couleur sont exactement ceux qui diffèrent d'un multiple de \(n\).

\(n=\) n = 4 — 4 classes

Exemple — congruence modulo \(n\) sur \(\mathbb Z\)

Pour \(x\in\mathbb Z\), sa classe est \(x+n\mathbb Z=\{\ldots,x-n,x,x+n,x+2n,\ldots\}\), donc \(\mathbb Z/{\equiv[n]}=\{x+n\mathbb Z\mid x\in\mathbb Z\}\) — une écriture qui répète chaque classe plusieurs fois (\(1+n\mathbb Z=(n+1)+n\mathbb Z=\cdots\)).

D'après la division euclidienne,

\[ \forall x\in\mathbb Z,\quad \exists! r\in\{0,\ldots,n-1\},\quad x\equiv r\ [n]. \]

Résultat \[ \{0,1,\ldots,n-1\}\ \text{est un ensemble de représentants, et}\quad \mathbb Z/{\equiv[n]}=\{n\mathbb Z,\,n\mathbb Z+1,\,\ldots,\,n\mathbb Z+(n-1)\}. \]

Applications

Exercice 1 — vrai ou faux ?

Énoncé

1.a.La relation \(\leqslant\) sur \(\mathbb R\) est symétrique.

2.b.La relation \(=\) sur \(E\) est antisymétrique.

3.c.Si \(\mathcal R\) est à la fois symétrique et antisymétrique, alors \(x\,\mathcal R\,y\Rightarrow x=y\).

4.d.La divisibilité est une relation d'ordre total sur \(\mathbb N\).

5.e.« Avoir le même signe » sur \(\mathbb R^*\) est une relation d'ordre.

6.f.Si \(\preccurlyeq\) est un ordre et \(x\prec y\), alors on ne peut pas avoir \(y\prec x\).

7.g.Deux éléments d'une même classe d'équivalence ont la même classe.

Exercice 2 — classes de congruence

Énoncé

On considère sur \(\mathbb Z\) la relation d'équivalence \(\equiv[4]\) (congruence modulo \(4\)).

1.Déterminer les classes des entiers \(0\), \(1\), \(2\), \(3\) puis celle de \(13\).

2.Donner un ensemble de représentants et décrire \(\mathbb Z/{\equiv[4]}\).

Résumé — méthode générale

Pour étudier une relation binaire \(\mathcal R\) sur \(E\) :

vérifier la réflexivité, la transitivité, la symétrie et l'antisymétrie sur des exemples et des contre-exemples précis ;
réflexive + transitive + antisymétrique \(\Rightarrow\) relation d'ordre (totale si deux éléments quelconques sont toujours comparables) ;
réflexive + transitive + symétrique \(\Rightarrow\) relation d'équivalence : penser aussitôt en termes de classes, d'ensemble quotient et de représentants ;
pour un ordre, la relation stricte associée \(x\prec y\Leftrightarrow (x\preccurlyeq y\ \text{et}\ x\neq y)\) est transitive et antisymétrique ;
pour une équivalence, les classes forment toujours une partition de \(E\).