Relación transitiva

Unarelación binaria $R$ sobre unconjunto $A$ estransitiva^[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:\quad aRb\quad \land \quad bRc\longrightarrow \quad aRc

Dado el conjuntoAy una relaciónR,esta relación es transitiva si:a R byb R cse cumplea R c.

La propiedad anterior se conoce comotransitividad.

Ejemplos

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

\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:

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óndivide a:

\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 naturalesa,byc:siadivide abybdivide acentoncesadivide ac

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 5noes la mitad de 20.

Representación

Unarelación binariase puede representar comopares ordenados,mediante unamatriz de adyacenciao mediante ungrafo.Para el caso de unarelación transitiva,cada una de estas representaciones tiene características especiales:

Comopares ordenados, $\forall a,b,c\in A,\ (a,b)\in R\land (b,c)\in R\;\Rightarrow \;(a,c)\in R$

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

Comografo,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})$ .

Véase también

Propiedades de larelación binaria homogénea:

Relación transitiva
Relación intransitiva

Relación total

Conceptos relacionados:

Silogismo hipotético

Referencias

↑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.
↑Richard Johnsonbaugh (2005). «3».Matemáticas discretas(6 edición). Pearson Educación. p. 118.ISBN 978-970-260-637-6.

Datos:Q64861

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

[1]

[2]