Relation transitive

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 ${\displaystyle {\mathcal {R}}}$ définie sur un ensemble ${\displaystyle E}$ :

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

Exemple de relation transitive entre la taille de trois pommes

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 : ${\displaystyle \exists x,y,z\in E\quad x{\mathcal {R}}y\land y{\mathcal {R}}z\land \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 : ${\displaystyle \forall x,y,z\in E\quad (x{\mathcal {R}}y\land 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

• 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'affirmer 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

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