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 ${\mathcal {R}}$ définie sur un ensemble $E$ : $\forall x,y,z\in E,\left[(x{\mathcal {R}}y\land y{\mathcal {R}}z)\Rightarrow x{\mathcal {R}}z\right]$. Elle est satisfaite pour les relations d'équivalence (en particulier la relation d'égalité), les relations d'ordre et même pour les relations d'ordre strict.

Une relation binaire non transitive est 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,\left[(x{\mathcal {R}}y\land y{\mathcal {R}}z)\land \lnot (x{\mathcal {R}}z)\right]$. 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,\left[(x{\mathcal {R}}y\land y{\mathcal {R}}z)\Rightarrow \lnot (x{\mathcal {R}}z)\right]$. 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 =, ≥ et ≤ sont parmi quelques-unes des relations transitives les plus couramment utilisées. Si a = b et si b = c alors automatiquement a = c.
• La relation de parallélisme est transitive : si une droite D est parallèle à D', elle-même parallèle à D", alors D est parallèle à D". Il en est de même pour toute relation d'équivalence.
• De même, les relations d'ordre sont transitives. Par exemple, (a ≤ b ∧ b ≤ c) ⇒ a ≤ c ou encore tout diviseur naturel d'un diviseur naturel de n divise n.
• Ainsi, on dit de la relation de congruence qu'elle est transitive dans ℕ. Cela veut dire que si a ≡ b [2] et si b ≡ c [2], alors a ≡ c [2].
• La relation ≠ n'est pas transitive, c'est-à-dire a ≠ b et b ≠ c ne permet pas de dire que a ≠ c.
• La relation « est le père de » est anti-transitive : 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).

Fermeture transitive

É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.