Les relations binaires

Propriétés et types de relations binaires

Ce ne sont pas ces relations-ci qu’il est prioritaire d’entretenir pour faciliter une carrière mais ce sont elles qui structurent les mathématiques. Elles facilitent surtout la bonne compréhension de nombreux raisonnements. Mais elles sont moins abstraites qu'il n'y paraît et la connaissance de ces notions est utile aux concepteurs de bases de données.

Flash back

Les notions que nous allons énumérer sont aujourd'hui enseignées après le bac. Mais dans les années 70, une bonne partie d'entre elles figuraient au programme de cinquième ! En seconde, les fonctions étaient introduites comme des relations binaires munies de certaines propriétés. Conséquence, les programmes hyper abstraits de l’époque ont sans doute contribué à faire détester les mathématiques par la majorité de la population française pour plusieurs générations… D'ailleurs, la rédaction de cette page a été en partie inspirée d'un manuel de l'époque (« Les maths de seconde, tome 1, algèbre et analyse » par Y. Bellecave, M. Claude et M. Péa, nouveaux guides Bordas, 1977).

Vocabulaire

Observons deux ensembles munis d’une relation \(R\). Il existe une infinité de relations envisageables. Les ensembles sont constitués d’éléments, en nombre fini ou infini. Un couple comprend un élément (composante) de chacun des deux ensembles. Il est toujours ordonné : la première composante est l’élément de l’ensemble de départ et la seconde est l’élément image de l’ensemble d’arrivée.

Le sous-ensemble des couples possibles est appelé produit cartésien. Il est noté \(E × F\) (si \(E\) est l’ensemble de départ et \(F\) celui d’arrivée). Ce produit est nommé carré cartésien si les deux ensembles n'en font qu’un. C’est d’ailleurs le cas le plus habituel en analyse mathématique, ce fameux carré étant généralement \(\mathbb{R}^2\).

Si le couple \((x,y) \in E \times F\) vérifie la relation \(R\), on le note \(x\,R\,y\).

Propriétés

La relation est réflexive si \(x\,R\,x\). Dans l’ensemble des réels, la relation \(\geqslant\) est réflexive puisque \(x \geqslant x\). En revanche, dans l’ensemble des droites, la relation « est orthogonale à » n’est pas réflexive puisqu’une droite n’est pas orthogonale à elle-même.

La relation est symétrique si \(x\,R\,y\) implique que \(y\,R\,x\). Dans \(\mathbb{R}^2\), l’addition, la multiplication, l’égalité et l’inégalité sont symétriques mais pas la division.

La relation est antisymétrique si \(x\,R\,y\) et \(y\,R\,x\) implique que \(x = y\). Cette notion est plus délicate à maîtriser. La relation \(\geqslant\) est antisymétrique car si \(x \geqslant y\) et \(y \geqslant x\), c’est que \(x = y\). La relation \(x + y = 0\) n’est pas antisymétrique. Le fait que \(x + y = 0\) et \(y + x = 0\) ne signifie pas que \(x = y\). On utilise l’antisymétrie pour démontrer, par exemple, que deux ensembles sont égaux si le premier est inclus dans le deuxième et si le deuxième est inclus dans le premier. L’antisymétrie n’a donc rien à voir avec la non-symétrie (l’inclusion n’est pas symétrique tout en étant antisymétrique, et vice versa pour le parallélisme).

La relation est transitive si \(x\,R\,y\) et \(y\,R\,z\) implique que \(x\,R\,y\). La relation \(>\) (strictement supérieur) est transitive mais pas la relation d’orthogonalité… La notion de transitivité est bien connue des concepteurs de bases de données : si le matricule d'un ouvrier peut être rattaché à un atelier et si cet atelier peut être rattaché à un lieu géographique, alors le matricule peut être rattaché au lieu géographique.

Il faut toujours préciser les ensembles dans lesquels ces relations sont appliquées car elles peuvent vérifier telle propriété dans un ensemble mais pas dans un autre. La relation « à pour frère… » est symétrique dans un ensemble d’hommes mais pas dans un ensemble mixte, la division est antisymétrique dans l’ensemble des entiers naturels mais pas dans celui des entiers relatifs, etc.

Types de relations

Une relation d’équivalence est réflexive, symétrique et transitive. La relation de parallélisme, par exemple, en est une. La congruence également.

Une relation d’ordre est réflexive, antisymétrique et transitive. Si, pour tout couple \((x\,,y)\) de \(E × E\) on a \(x\,R\,y\) ou \(y\,R\,x\), alors il s’agit d’un ordre total (c’est habituellement le cas sur \(\mathbb{R}\)). Sinon, cet ordre est partiel. Une telle relation caractérise les ensembles ordonnés (par exemple les entiers naturels, les réels, un classement hiérarchisé de produits obtenu auprès d’un échantillon de consommateurs, etc.).

Dans une relation d’ordre strict, \(x\) et \(y\) sont différents. Ainsi, \(x < y\) se lit « x strictement inférieur à y ».

Les ensembles ordonnés peuvent accepter des majorants et / ou minorants.

Pour résumer...

Attention, les relations d’ordre et d’équivalence sont deux notions bien distinctes. L’égalité vérifie les deux mais l’orthogonalité ni l’une ni l’autre. L’inclusion est une relation d’ordre mais pas d’équivalence, au contraire du parallélisme qui est une relation d’équivalence mais pas d’ordre.

S’il existe au moins un couple d’éléments non comparables, l’ordre est partiel. Sinon, il est total (ou complet). L’inclusion est une relation d’ordre partiel puisque deux sous-ensembles peuvent être disjoints. En revanche, tous les réels sont comparables entre eux et la relation \( \leqslant\) est totale.

Si une relation n'est que réflexive et transitive, il s'agit d'un préordre. Toute relation d'ordre est donc un préordre mais l'inverse est faux. Si la relation est complète, le préordre est complet. Sinon il est partiel. À titre d'exemple, un préordre complet caractérise les préférences du consommateur dans la théorie de l'utilité ordinale.

Relation réciproque

Soit \(R\) une relation d'un ensemble vers un autre. La relation réciproque de \(R\) que l'on notera ici \(R'\) est telle que \(x\, R\, y \Leftrightarrow y\, R'\, x.\)

Par exemple la relation « pays appartient à ce continent » à pour réciproque « continent contient ce pays ».

Classes d’équivalence

Une classe d’équivalence d’un élément modulo \(R\) est l’ensemble des éléments qui sont en relation avec lui. Les classes distinctes sont forcément disjointes. Dans l’ensemble des droites muni de la relation de parallélisme, la classe d’une droite \((\Delta)\) est l’infinité des droites parallèles à \((\Delta)\). Pour signifier que deux éléments font partie d’une même classe, on écrit : \(x \equiv y\left( {\bmod R} \right)\).

On dit que \(x\) est équivalent ou congru à \(y\) modulo \(R\).

Pour un élément \(x\) de \(E\), la classe d’équivalence est l’ensemble des images de \(x\) par \(R\) :

\(R(x) = \left\{ {y \in E\;|\;x\,R\,y} \right\}\)

On appelle ensemble quotient de \(E\) par \(R\) l’ensemble des classes d’équivalence de \(E\) modulo \(R\). Elles forment une partition de \(E\).

Prenons l’exemple de la relation « est de la même famille que » (au sens taxonomique du terme). C’est bien sûr une relation d’équivalence. Classons six animaux choisis dans une ferme : deux équidés (un cheval et un âne), trois bovidés (une vache, une chèvre et un mouton) et un suidé (un cochon). Il y a donc trois classes d’équivalence qui correspondent aux trois familles zoologiques. L’ensemble quotient est \(\{\{\rm{cochon}\},\) \(\{\rm{cheval, âne}\},\) \(\{\rm{vache, chèvre, mouton}\}\}.\)