Relación transitiva

De Wikipedia, la enciclopedia libre

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 da que si un elemento de A está relacionado con otro, y ese otro a su vez se relaciona con un tercero, entonces el primero está relacionado también con este último.

Es decir,

$forall a, b, c in A, a R b and b R c ; Rightarrow ; aRc$

En tal caso, decimos que $R$ cumple con la propiedad de transitividad.

La aplicación de cualquier relación $R$ sobre un conjunto $A$ , se representa con el par ordenado $(A, R)$ .

[editar] 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 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)$ .

[editar] Ejemplos

Sea $A$ un conjunto cualquiera:

Sea $(A, ge)$ , $ge$ (“mayor o igual que”) es transitiva, al igual que $>,” class=”tex” src=”https://upload.wikimedia.org/math/1/1/4/114529aa81593e4dfb2279a9b594c779.png”> (“mayor estricto que”).</li> </ul> <ul> <li>Sea <img decoding=$ , $le$ (“menor o igual que”) es transitiva, al igual que $<,$ (“menor estricto que”).

Sea $(A, subseteq)$ , $subseteq$ (la inclusión de conjuntos), es transitiva.

Sea $(A, =),$ , $=,$ (la igualdad matemática), es transitiva.

Sea $(mathbb{N}backslash{0}, backslash)$ , $backslash,$ (la divisibilidad) es transitiva.

Ser la madre de no es una relación transitiva, pues el que Alicia sea la madre de María y María la madre de Josefina no implica que Alicia sea la madre de Josefina.

[editar] Véase también

Clausura transitiva