Relación transitiva

Una relación binaria ${\displaystyle R}$ sobre un conjunto ${\displaystyle 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.

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

Esto es:

${\displaystyle \forall a,b,c\in A:\quad aRb\quad \land \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 de orden "menor o igual que" vemos que es transitiva:

${\displaystyle \forall a,b,c\in \mathbb {N} :\quad a\leq b\quad \land \quad b\leq c\longrightarrow \quad a\leq c}$ 

Así, puesto que:

${\displaystyle 2,5,7\in \mathbb {N} :\quad 2\leq 5\quad \land \quad 5\leq 7\longrightarrow \quad 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:

${\displaystyle \forall a,b,c\in \mathbb {N} :\quad a|b\quad \land \quad b|c\longrightarrow \quad 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

Se cumple ${\displaystyle X\not \subset Y}$  y ${\displaystyle Y\not \subset Z}$  pero no se cumple ${\displaystyle X\not \subset Z}$  puesto que ${\displaystyle X}$  es subconjunto de ${\displaystyle 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, ${\displaystyle \forall a,b,c\in A,\ (a,b)\in R\land (b,c)\in R\;\Rightarrow \;(a,c)\in R}$ 

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

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

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 Acotado

Conceptos relacionados:

• Silogismo hipotético

Referencias

1. Caicedo Barrero, Alfredo; Wagner de Gardia, Graciela; Me¡éndez Parra, Rosa María (2010). «2.4». Introducción a la Teoría de Grafos (1 edición). Ediciones Elizcom. p. 21. ISBN 978-958-993-257-5. 
2. Richard Johnsonbaugh (2005). «3». Matemáticas discretas (6 edición). Pearson Educación. p. 118. ISBN 978-970-260-637-6. 

•   Datos: Q64861