Relación transitiva

Una relación binaria $R$ sobre un conjunto $A$ es transitiva^[1]^[2] cuando se cumple: siempre que un elemento se relaciona con otro y este último con un tercero, entonces el primero se relaciona con el tercero.

Esto es:

\forall a, b, c \in A : a R b \land b R c ⟶ a R c

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 de orden "menor o igual que" vemos que es transitiva:

\forall a, b, c \in ℕ : a \leq b \land b \leq c ⟶ a \leq c

Así, puesto que:

2, 5, 7 \in ℕ : 2 \leq 5 \land 5 \leq 7 ⟶ 2 \leq 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 ℕ : a | b \land b | c ⟶ a | c

Para cualquiera de los números naturales a, b y c: si 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 Plantilla:Ecuación

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 \land (b, c) \in R \Rightarrow (a, c) \in R$

Como matriz de adyacencia $M$ , la matriz es tal que $M \lor M^{2} = M .$

Como grafo, cada vez que desde un nodo $v_{1}$ se pueda llegar a otro $v_{3}$ , pasando primero por un nodo intermedio $v_{2}$ , entonces también existirá la arista $(v_{1}, v_{3})$ .