Relación transitiva

Ejemplo: Si a es mayor que b, y b es mayor que c, entonces, a es mayor que c.

Una relación binaria R sobre un conjunto A es transitiva cuando se cumple: siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.

Esto es:

$\forall a, b, c \in \mathbb{A}: \quad aRb \quad \and \quad bRc \longrightarrow \quad aRc$

Dado el conjunto A y una relación R, esta relación es transitiva si: a R b y b R c se cumple a R c.

La propiedad anterior se conoce como transitividad.

Ejemplos

Así por ejemplo dado el conjunto N de los números naturales y la relación binaria "menor o igual que" vemos que es transitiva:

$\forall a, b, c \in \N : \quad a \le b \quad \and \quad b \le c \longrightarrow \quad a \le c$

Así, puesto que:

$2, 5, 7 \in \N : \quad 2 \le 5 \quad \and \quad 5 \le 7 \longrightarrow \quad 2 \le 7$

En general las relaciones de orden (ser menor, mayor, igual, menor o igual, mayor o igual) son transitivas.

Tomando de nuevo el conjunto de los números naturales, y la relación divide a:

$\forall a, b, c \in \N : \quad a | b \quad \and \quad b | c \longrightarrow \quad a | c$

Si para todo valor a, b, c numero natural: a divide a b y b divide a c entonces a divide a c

Dado que 3|12 (3 divide a 12) y 12|48 (12 divide a 48), la transitividad establece que 3|48 (3 divide a 48).

Sin embargo, no todas las relaciones binarias son transitivas. La relación "no es subconjunto" no es transitiva. Por ejemplo, si X = {1,2,3}, Y={2,3,4,5}, Z={1,2,3,4}. Entonces

Se cumple $X \not\subset Y$ y $Y\not\subset Z$ pero no se cumple $X\not\subset Z$ puesto que X es subconjunto de Z.

Otro ejemplo de relación binaria que no es transitiva es "ser la mitad de": 5 es la mitad de 10 y 10 es la mitad de 20, pero 5 no es la mitad de 20.

Representación

Una relación binaria se puede representar como pares ordenados, mediante una matriz de adyacencia o mediante un grafo. Para el caso de una relación transitiva, cada una de estas representaciones tiene características especiales:

• Como pares ordenados, $\forall a, b, c \in A,\ (a,b)\in R \and (b,c)\in R \; \Rightarrow \; (a,c)\in R$

• Como matriz de adyacencia M, la matriz es tal que $M \or M^2 = M.$

• Como grafo, cada vez que desde un nodo v₁ se pueda llegar a otro v₃, pasando primero por un nodo intermedio v₂, entonces también existirá la arista (v₁,v₃).

Véase también

Propiedades de la relación binaria homogénea:

Relación reflexiva Relación irreflexiva

Relación simétrica Relación antisimétrica

Relación transitiva Relación intransitiva

Relación total

Relación bien fundada