Définition Fondamentale d’une Relation Binaire
Une relation binaire entre deux ensembles E et F est définie mathématiquement comme une partie du produit cartésien de ces ensembles. Cette définition formelle peut sembler abstraite, mais elle trouve de nombreuses applications pratiques.
\text{Une relation binaire } \mathcal{R} \text{ de } E \text{ vers } F \text{ est une partie de } E \times F
\]
Lorsqu’un couple \((x, y)\) appartient à cette relation, on note \(x \mathcal{R} y\) et on dit que « x est en relation avec y ». L’ensemble de tous les couples vérifiant la relation s’appelle le graphe de la relation.
Exemple Concret
Considérons l’ensemble \(E = \{1, 2, 3\}\) et \(F = \{2, 4, 6, 8\}\). Définissons la relation \(\mathcal{R}\) par : « x est en relation avec y si y est le double de x ».
Le graphe de cette relation est : \(\mathcal{G}_{\mathcal{R}} = \{(1,2), (2,4), (3,6)\}\)
Cas Particulier : Relation Binaire sur un Ensemble
Lorsque \(E = F\), on parle de relation binaire dans E ou relation binaire sur E. Ce cas particulier est fréquemment rencontré en algèbre et en théorie des ordres.
Représentations d’une Relation Binaire
Pour visualiser et manipuler les relations binaires, plusieurs méthodes de représentation graphique existent. Chacune présente des avantages selon le contexte d’utilisation.
Diagramme Sagittal
Le diagramme sagittal (du latin sagitta signifiant flèche) représente les éléments de chaque ensemble par des points, reliés par des flèches lorsqu’ils sont en relation. Cette représentation visuelle facilite la compréhension intuitive des propriétés d’une relation.
Matrice d’Incidence
Pour les ensembles finis, une matrice booléenne permet de coder la relation : on place un 1 (ou une croix) à l’intersection de la ligne x et de la colonne y si \(x \mathcal{R} y\), et 0 sinon. Cette représentation matricielle s’avère particulièrement utile en informatique et pour les calculs algorithmiques.
Représentation par le Graphe
En théorie des graphes, une relation binaire sur un ensemble E peut être visualisée comme un graphe orienté où chaque élément de E est un sommet, et chaque couple \((x,y)\) de la relation correspond à un arc orienté de x vers y.
Propriétés Caractéristiques des Relations Binaires
Les relations binaires peuvent posséder diverses propriétés qui déterminent leur nature et leurs applications. Ces propriétés fondamentales incluent la réflexivité, la symétrie, l’antisymétrie et la transitivité.
Propriété de Réflexivité
Une relation \(\mathcal{R}\) sur un ensemble E est dite réflexive si tout élément est en relation avec lui-même.
\mathcal{R} \text{ est réflexive } \Leftrightarrow \forall x \in E, \; x \mathcal{R} x
\]
Exemples : L’égalité, la relation « inférieur ou égal » (\(\leq\)), la relation de divisibilité sur les entiers naturels sont toutes réflexives. Une droite est parallèle à elle-même, donc le parallélisme est réflexif.
Propriété de Symétrie
Une relation est symétrique lorsque si x est en relation avec y, alors y est également en relation avec x.
\mathcal{R} \text{ est symétrique } \Leftrightarrow \forall x,y \in E, \; (x \mathcal{R} y \Rightarrow y \mathcal{R} x)
\]
Exemples : L’égalité, le parallélisme entre droites, la relation « avoir le même module » dans \(\mathbb{C}\) sont symétriques. En revanche, la relation « inférieur ou égal » n’est pas symétrique.
Propriété d’Antisymétrie
Une relation est antisymétrique si lorsque x est en relation avec y et y est en relation avec x, alors x et y sont nécessairement égaux.
\mathcal{R} \text{ est antisymétrique } \Leftrightarrow \forall x,y \in E, \; ((x \mathcal{R} y \text{ et } y \mathcal{R} x) \Rightarrow x = y)
\]
Exemples : La relation « inférieur ou égal » (\(\leq\)) et la relation d’inclusion (\(\subseteq\)) sont antisymétriques. Attention, une relation peut n’être ni symétrique ni antisymétrique.
Propriété de Transitivité
Une relation est transitive lorsque si x est en relation avec y et y est en relation avec z, alors x est en relation avec z.
\mathcal{R} \text{ est transitive } \Leftrightarrow \forall x,y,z \in E, \; ((x \mathcal{R} y \text{ et } y \mathcal{R} z) \Rightarrow x \mathcal{R} z)
\]
Exemples : L’égalité, l’inégalité (\(\leq\)), la divisibilité, l’inclusion d’ensembles sont transitives. Cette propriété est fondamentale dans les bases de données relationnelles et les systèmes hiérarchiques.
Relations d’Équivalence
Une relation d’équivalence est une relation binaire qui combine trois propriétés essentielles : elle doit être à la fois réflexive, symétrique et transitive. Ces relations jouent un rôle central en mathématiques car elles permettent de partitionner un ensemble en classes d’éléments équivalents.
\mathcal{R} \text{ est une relation d’équivalence } \Leftrightarrow \mathcal{R} \text{ est réflexive, symétrique et transitive}
\]
Classes d’Équivalence
Pour tout élément x d’un ensemble E muni d’une relation d’équivalence \(\mathcal{R}\), on définit la classe d’équivalence de x comme l’ensemble de tous les éléments en relation avec x.
Cl(x) = \{y \in E \mid x \mathcal{R} y\}
\]
Toute classe d’équivalence contient au moins son représentant x. Les classes d’équivalence distinctes forment une partition de E : elles sont disjointes deux à deux et leur réunion reconstitue l’ensemble E tout entier.
Ensemble Quotient
L’ensemble quotient, noté \(E/\mathcal{R}\), est l’ensemble de toutes les classes d’équivalence. Il représente une structure simplifiée de E où les éléments équivalents sont identifiés.
Exemple Fondamental : La Congruence Modulo n
Dans \(\mathbb{Z}\), deux entiers a et b sont congrus modulo n si leur différence est divisible par n.
a \equiv b \; [n] \Leftrightarrow n \mid (a-b) \Leftrightarrow \exists k \in \mathbb{Z}, \; a = b + kn
\]
Cette relation de congruence est une relation d’équivalence. Pour n = 3, l’ensemble quotient \(\mathbb{Z}/3\mathbb{Z}\) contient exactement trois classes : \(\overline{0}, \overline{1}, \overline{2}\).
Autres Exemples de Relations d’Équivalence
- Le parallélisme dans l’ensemble des droites du plan : deux droites sont équivalentes si elles sont parallèles ou confondues.
- L’égalité des modules dans \(\mathbb{C}\) : deux nombres complexes sont équivalents s’ils ont le même module. Géométriquement, chaque classe d’équivalence représente un cercle centré à l’origine.
- La relation définie par une fonction : si f est une fonction de E dans F, la relation « x et y ont la même image par f » est une relation d’équivalence sur E.
Relations d’Ordre
Une relation d’ordre est une relation binaire qui structure un ensemble de manière hiérarchique. Elle doit satisfaire trois propriétés : réflexivité, antisymétrie et transitivité.
\mathcal{R} \text{ est une relation d’ordre } \Leftrightarrow \mathcal{R} \text{ est réflexive, antisymétrique et transitive}
\]
On note généralement une relation d’ordre par le symbole \(\leq\) ou \(\preceq\), et on dit que le couple \((E, \leq)\) forme un ensemble ordonné.
Ordre Total et Ordre Partiel
Une relation d’ordre est dite totale (ou ordre total) si deux éléments quelconques de E sont toujours comparables, c’est-à-dire si pour tous x et y dans E, on a soit \(x \leq y\) soit \(y \leq x\).
\leq \text{ est un ordre total } \Leftrightarrow \forall x,y \in E, \; (x \leq y \text{ ou } y \leq x)
\]
Dans le cas contraire, l’ordre est dit partiel. Il existe alors au moins deux éléments non comparables.
Exemples de Relations d’Ordre
- L’inégalité usuelle \(\leq\) sur \(\mathbb{R}\) : c’est un ordre total car deux nombres réels quelconques peuvent toujours être comparés.
- La divisibilité sur \(\mathbb{N}^*\) : « a divise b » est un ordre partiel. Par exemple, 2 et 3 ne sont pas comparables pour la divisibilité.
- L’inclusion \(\subseteq\) sur \(\mathcal{P}(E)\) : c’est un ordre partiel (sauf si E est vide ou singleton).
Éléments Remarquables dans un Ensemble Ordonné
Soit A une partie d’un ensemble ordonné \((E, \leq)\). On définit plusieurs notions importantes :
- Un élément M de E est un majorant de A si \(\forall x \in A, \; x \leq M\)
- Un élément m de E est un minorant de A si \(\forall x \in A, \; m \leq x\)
- Le plus petit des majorants, s’il existe, s’appelle la borne supérieure de A, notée sup(A)
- Le plus grand des minorants, s’il existe, s’appelle la borne inférieure de A, notée inf(A)
- Un élément a de A est le maximum de A si \(\forall x \in A, \; x \leq a\)
- Un élément a de A est le minimum de A si \(\forall x \in A, \; a \leq x\)
Attention : La borne supérieure d’une partie A n’appartient pas nécessairement à A. Par exemple, sup(]0,1[) = 1, mais 1 n’appartient pas à l’intervalle ouvert ]0,1[.
Opérations sur les Relations Binaires
Relation Réciproque
Soit \(\mathcal{R}\) une relation de E vers F. La relation réciproque (ou inverse), notée \(\mathcal{R}^{-1}\), est la relation de F vers E définie par :
y \mathcal{R}^{-1} x \Leftrightarrow x \mathcal{R} y
\]
Graphiquement, on obtient la relation réciproque en inversant le sens de toutes les flèches dans un diagramme sagittal.
Composition de Relations
Soient \(\mathcal{R}\) une relation de E vers F et \(\mathcal{S}\) une relation de F vers G. La relation composée \(\mathcal{S} \circ \mathcal{R}\) est la relation de E vers G définie par :
x (\mathcal{S} \circ \mathcal{R}) z \Leftrightarrow \exists y \in F, \; (x \mathcal{R} y \text{ et } y \mathcal{S} z)
\]
La composition des relations est une opération associative, permettant d’enchaîner plusieurs relations successives.
Comment reconnaître rapidement le type de relation dans un exercice ?
- Si on te demande de montrer réflexive + symétrique + transitive → relation d’équivalence
- Si on te demande réflexive + antisymétrique + transitive → relation d’ordre
- Présence de ≤, ⊆, | → souvent ordre
- Présence de « même image », « même reste », « même valeur » → souvent équivalence
Exercices Résolus et Corrigés
Exercice 1 : Vérification d’une Relation d’Équivalence
Énoncé : On définit sur \(\mathbb{R}\) la relation \(\mathcal{R}\) par : \(x \mathcal{R} y \Leftrightarrow x^2 – y^2 = x – y\). Montrer que \(\mathcal{R}\) est une relation d’équivalence et déterminer la classe d’équivalence de x.
Solution détaillée :
Vérification de la réflexivité :
Pour tout \(x \in \mathbb{R}\), calculons \(x^2 – x^2 – (x – x)\) :
x^2 – x^2 = 0 \quad \text{et} \quad x – x = 0 \quad \Rightarrow \quad x \mathcal{R} x
\]
La relation est donc réflexive.
Vérification de la symétrie :
Supposons \(x \mathcal{R} y\), c’est-à-dire \(x^2 – y^2 = x – y\). Montrons que \(y \mathcal{R} x\) :
y^2 – x^2 &= -(x^2 – y^2) = -(x – y) = y – x \\
&\Rightarrow y \mathcal{R} x
\end{align*}
La relation est symétrique.
Vérification de la transitivité :
Supposons \(x \mathcal{R} y\) et \(y \mathcal{R} z\). Alors \(x^2 – y^2 = x – y\) et \(y^2 – z^2 = y – z\).
Additionnons ces égalités :
(x^2 – y^2) + (y^2 – z^2) &= (x – y) + (y – z) \\
x^2 – z^2 &= x – z \\
&\Rightarrow x \mathcal{R} z
\end{align*}
La relation est transitive. Conclusion : \(\mathcal{R}\) est bien une relation d’équivalence.
Détermination de la classe d’équivalence de x :
Cherchons l’ensemble des y tels que \(x \mathcal{R} y\), c’est-à-dire \(x^2 – y^2 = x – y\).
x^2 – y^2 &= x – y \\
(x – y)(x + y) &= x – y \\
(x – y)(x + y – 1) &= 0
\end{align*}
Donc soit \(x = y\), soit \(x + y = 1\), c’est-à-dire \(y = 1 – x\).
Conclusion : \(Cl(x) = \{x, 1-x\}\) pour tout \(x \in \mathbb{R}\).
Exercice 2 : Relation d’Ordre
Énoncé : Sur \(\mathbb{N}^*\), on définit la relation \(\mathcal{R}\) par : \(a \mathcal{R} b \Leftrightarrow a \mid b\) (a divise b). Montrer que \(\mathcal{R}\) est une relation d’ordre. Cette relation est-elle totale ?
Solution :
Réflexivité : Pour tout \(a \in \mathbb{N}^*\), on a \(a = 1 \times a\), donc a divise a. La relation est réflexive.
Antisymétrie : Supposons \(a \mid b\) et \(b \mid a\). Il existe alors des entiers k et l tels que \(b = ka\) et \(a = lb\). Par substitution : \(a = l(ka) = lka\), d’où \(lk = 1\). Dans \(\mathbb{N}^*\), cela implique \(l = k = 1\), donc \(a = b\). La relation est antisymétrique.
Transitivité : Si \(a \mid b\) et \(b \mid c\), il existe k et l tels que \(b = ka\) et \(c = lb\). Alors \(c = l(ka) = (lk)a\), donc \(a \mid c\). La relation est transitive.
Conclusion : La divisibilité est bien une relation d’ordre sur \(\mathbb{N}^*\).
Ordre total ou partiel ? Cette relation n’est pas totale. Contre-exemple : 2 et 3 ne sont pas comparables car ni 2 ne divise 3, ni 3 ne divise 2. Il s’agit donc d’un ordre partiel.
Exercice 3 : Congruence Modulo n
Énoncé : Soit \(n \geq 2\) un entier naturel. Montrer que la congruence modulo n est une relation d’équivalence sur \(\mathbb{Z}\). Déterminer le cardinal de l’ensemble quotient \(\mathbb{Z}/n\mathbb{Z}\).
Solution :
Rappelons la définition : \(a \equiv b \; [n] \Leftrightarrow n \mid (a-b)\).
Réflexivité : Pour tout \(a \in \mathbb{Z}\), on a \(a – a = 0 = n \times 0\), donc \(n \mid (a-a)\). Ainsi \(a \equiv a \; [n]\).
Symétrie : Si \(a \equiv b \; [n]\), alors \(n \mid (a-b)\), donc il existe k tel que \(a – b = nk\). Alors \(b – a = -nk = n(-k)\), donc \(n \mid (b-a)\), d’où \(b \equiv a \; [n]\).
Transitivité : Si \(a \equiv b \; [n]\) et \(b \equiv c \; [n]\), alors \(a – b = nk_1\) et \(b – c = nk_2\). En additionnant : \(a – c = n(k_1 + k_2)\), donc \(a \equiv c \; [n]\).
Détermination de l’ensemble quotient :
Par la division euclidienne, tout entier a s’écrit \(a = nq + r\) avec \(0 \leq r < n\). On a alors \(a \equiv r \; [n]\). Les classes d’équivalence sont donc :
\mathbb{Z}/n\mathbb{Z} = \{\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\}
\]
Conclusion : L’ensemble quotient contient exactement n classes d’équivalence, donc \(\text{card}(\mathbb{Z}/n\mathbb{Z}) = n\).
Conclusion et résumé du cours
Les relations binaires constituent un outil fondamental pour structurer et comparer les éléments d’un ensemble.
Elles interviennent naturellement dans de nombreuses notions mathématiques, notamment les relations d’équivalence
et les relations d’ordre, qui permettent respectivement de regrouper ou d’organiser les éléments selon des critères précis.
À retenir
- Une relation binaire est une partie du produit cartésien E × F.
- Une relation sur un ensemble E est dite réflexive, symétrique, antisymétrique ou transitive selon des propriétés précises.
- Une relation d’équivalence est réflexive, symétrique et transitive ; elle définit une partition de l’ensemble en classes d’équivalence.
- Une relation d’ordre est réflexive, antisymétrique et transitive ; elle peut être totale ou partielle.
- Les notions de majorant, minorant, borne supérieure et borne inférieure sont propres aux ensembles ordonnés.
- Les opérations sur les relations (réciproque, composition) permettent de construire de nouvelles relations à partir de relations existantes.
La maîtrise de ces notions est indispensable pour aborder sereinement les chapitres de structures algébriques, de théorie des ensembles et d’algèbre générale.