Relación transitiva


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 grafo, cada vez que desde un nodo v1 se pueda llegar a otro v3, pasando primero por un nodo intermedio v2, entonces también existirá la arista (v1,v3).

Véase también

Propiedades de la relación binaria homogénea:

  • Relación transitiva
  • Relación intransitiva

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Relación transitiva — En matemáticas, una relación binaria R sobre un conjunto X es transitiva si se cumple que para todo a, b, y c pertenecientes a X, que si a …   Enciclopedia Universal

  • Relación binaria — Saltar a navegación, búsqueda En matemáticas, una relación binaria es una relación matemática R entre los elementos de dos conjuntos A y B. Una relación de este tipo se puede representar mediante pares ordenados, : Las dos propo …   Wikipedia Español

  • Relación — Saltar a navegación, búsqueda El concepto relación puede referirse a muy distintos ámbitos: Contenido 1 En el sentido de relato 1.1 Folclore 1.2 Literatura …   Wikipedia Español

  • Relación de orden — Saltar a navegación, búsqueda Sea A un conjunto dado no vacío y R una relación binaria definida en A, entonces decimos que R es una relación de orden si cumple las siguientes propiedades: Reflexividad: Todo elemento de A está relacionado consigo… …   Wikipedia Español

  • Relación total — Saltar a navegación, búsqueda Una relación binaria R sobre un conjunto A es una relación total cuando se cumple que para cada dos elementos a y b de A, ó a esta relacionado con b ó b esta relacionado con a, esto es: Tenga en cuenta que esto… …   Wikipedia Español

  • Relación bien fundada — En teoría de conjuntos, una relación bien fundada sobre una clase X es una relación binaria R sobre X tal que todo subconjunto no vacío de X tiene un elemento R mínimo; esto es: Para todo subconjunto no vacío S de X, hay un elemento m en S tal… …   Wikipedia Español

  • Relación de equivalencia — Una relación de equivalencia sobre K es una relación binaria Relación de equivalencia que cumple las siguientes propiedades: ● Es reflexiva: ∀a ∈ K, a Relación de equivalencia a. ● Es simétrica: a Relación de equivalencia b ⇒ b Relación de equiva …   Enciclopedia Universal

  • Relación de equivalencia — …   Wikipedia Español

  • Clausura transitiva — La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación se denotada . En… …   Wikipedia Español

  • Clausura de relación — En matemática, sea una relación R sobre un conjunto A, la clausura o cierre de R es la menor relación que contiene a R y cumple con una propiedad dada. Tales propiedades pueden ser la transitividad, reflexividad o simetría, en cuyo caso la… …   Wikipedia Español