Relation transitive

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Transitivité.

En mathématiques, une relation transitive est une relation binaire pour laquelle une suite d'objets reliés consécutivement aboutit à une relation entre le premier et le dernier. Formellement, la propriété de transitivité s'écrit, pour une relation \mathcal{R} définie sur un ensemble E :

\forall x, y, z \in E\quad(x \mathcal{R} y \and  y \mathcal{R} z)\Rightarrow x \mathcal{R} z.

Une relation binaire non transitive est donc une relation pour laquelle la propriété universelle ci-dessus est fausse, c'est-à-dire qu'il existe un élément en relation avec un deuxième qui lui-même est en relation avec un troisième, sans que le premier soit en relation avec le troisième : \exists x, y, z \in E\quad x \mathcal{R} y \and  y \mathcal{R} z \and \lnot (x \mathcal{R} z).C'est le cas de l'orthogonalité de droites, par exemple.

Cette négation de la transitivité est différente de la propriété d'antitransitivité, qui interdit les enchainements de relations sur tous les triplets de l'ensemble : \forall x, y, z \in E\quad(x \mathcal{R} y \and  y \mathcal{R} z)\Rightarrow\lnot (x \mathcal{R} z). C'est le cas de l'orthogonalité de droites dans le plan, mais pas dans l'espace, où il existe des triplets de droites deux à deux orthogonales. En revanche, la relation binaire de graphe vide (qui ne relie rien) est antitransitive et transitive à la fois.

Exemples[modifier | modifier le code]

  • Les relations d'équivalence, les relations d'ordre et les relations d'ordre strict sont transitives (suivre ces liens pour des exemples de telles relations).
  • La relation ≠ n'est ni transitive, ni antitransitive a ≠ b et b ≠ c ne permet d'affirme ni que a ≠ c, ni que a = c.
  • La relation « est le père de » est antitransitive : si (a est le père de b) et (b est le père de c), alors (a n'est pas le père de c).
  • Sur l'ensemble des couples de réels, la relation ℛ définie par « (x , y)(x', y') si et seulement si y < y' ou x < x' » n'est pas transitive[1], ni antitransitive.

Fermeture transitive[modifier | modifier le code]

Étant donnée une relation binaire sur un ensemble, il existe une relation transitive minimale contenant la première relation et appelée fermeture transitive.

Référence[modifier | modifier le code]

  1. J. Rivaud, Algèbre, Classes préparatoires et université, Exercices avec solutions, tome 1, Vuibert, 1978, p. 47.