Transitivité (mathématiques)

Un article de Wikivisual, l'encyclopédie libre.

En mathématiques, la transitivité est une propriété éventuelle d'une relation binaire. Une relation binaire <math>\mathcal{R}</math> définie sur un ensemble <math>E</math> est transitive quand à chaque fois que l'on a trois éléments x, y et z de E tels que x et y sont en relation, ainsi que y et z, alors x et z sont en relation. Plus formellement :

<math>\forall x, y, z \in E\left[(x \mathcal{R} y \and y \mathcal{R} z) \implies x \mathcal{R} z\right] </math>.

Si l'amitié était transitive, on pourrait affirmer « Tous les amis de mes amis sont mes amis.»

On en déduit qu'une relation sur E n'est pas transitive si et seulement s'il existe un triplet d'éléments de E qui fournit un contre-exemple à la transitivité : x et y sont en relation, ainsi que y et z, mais pas x et z. Plus formellement :

<math>\exists x, y, z \in E\left[x \mathcal{R} y \and y \mathcal{R} z \and \lnot(x\mathcal{R}z)\right] </math>.

On dit alors que la relation binaire <math>\mathcal{R}</math> est non-transitive. Cette propriété, qui est la simple négation de la transitivité, ne doit pas être confondue avec la propriété suivante :

<math>\forall x, y, z \in E \left[(x \mathcal{R} y \and y \mathcal{R} z) \implies\lnot(x \mathcal{R} z)\right] </math>.

On dit parfois d'une telle relation qu'elle est anti-transitive (cette propriété est moins utile et moins courante que la transitivité, le vocabulaire n'est pas forcément bien établi). Remarquez que les propriétés de non-transitivité et d'anti-transitivité ne sont pas comparables (acune des deux n'entraîne l'autre), et qu'une relation, même non vide, peut très bien être transitive et anti-transitive (il suffit qu'il n'y ait pas de triplet (x, y z) vérifiant x R y et y R z).

[modifier] Exemples

Les relations <math>=</math>, <math>\geq</math> et <math>\leq</math> sont parmi quelques unes des relations transitives les plus couramment utilisées. Si <math>a = b</math> et si <math>b = c</math> alors automatiquement <math>a = c</math>.

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, <math>(a \leq b \and b \leq c) \implies a \leq c</math> 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 <math>\mathbb N</math>. Cela veut dire que si <math>a \equiv b [2]</math> et si <math>b \equiv c [2]</math>, alors <math>a \equiv c [2]</math>.

[modifier] Exemple de non-transitivité

La relation <math>\not=</math> n'est pas transitive, c'est-à-dire <math>a \not= b</math> et <math>b \not= c</math> ne permet pas de dire que <math>a \not= c</math>.