PROPIEDADES DE LAS RELACIONES *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:

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:

Así, puesto que:

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:

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 y pero no se cumple 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.

Se dice que S es una relacion transitiva cuando se cumple: si mSn y

nSp

R es una relación transitiva en un conjunto A no vacío , si y sólo si cada trío de

elementos de él satisface lo siguiente:

a R b ð b R c ð a R c

Ejemplo:

A = { 1 , 2 , 3 }

R = { ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 3 ) }

Teorema. R es antisimétrica en A Û R · R^-1 Ì I_A.
 Relación transitiva. R es una relación transitiva en A sí y sólo sí R es una relación en A y cualquiera sean x, y, z pertenecientes a A se verifica que:

Sí x R y Ù y R z, entonces x R z.

En consecuencia:

• R es transitiva en A equivale a decir:

R Ì A x A Ù (" x)(" y)(" z) ( x R y Ù y R z Þ x R z)

• R no es transitiva en A equivale a decir:

R Ë A x A Ú ($ x)( $ y)($ z) ( x R y Ù y R z Ù x z).

Ejemplo 

I _A es transitiva en A.

Ejemplo

Sea = {2, 4, 6, 3} entonces:

R = {(2, 2), (2, 3), (4, 6), (6, 2), (4, 2), (4, 3), (6, 3)} es transitiva en A.

S = {(2, 2), (4, 4), (4, 2), (2, 6), (6, 4), (6, 2)} no es transitiva en A.

Ejemplo

La relación T = {(x, y) / x Î N, y Î N Ù x |y} es transitiva en N.

En matemáticas, a relación binaria R sobre a sistema X es transitivo si sostiene para todos a, b, y c en X, eso si a se relaciona con b y b se relaciona con c, entonces a se relaciona con c.

Para escribir esto adentro lógica del predicado:

 

Por ejemplo, la relación “mayor que” es transitiva:

Si A > B, y B > C, entonces A > C.

Por ejemplo, “es mayor que,” “es por lo menos tan grande como,” y “es igual a” (igualdad) son las relaciones transitivas:

siempre que A > B y B > C, entonces también A > C

siempre que ≥ B de A y ≥ C, entonces también ≥ C de B de A

siempre que A = B y B = C, entonces también A = C

Por una cierta hora, los economistas y los filósofos creyeron que la preferencia era una relación transitiva sin embargo allí ahora es las teorías matemáticas que demuestran que las preferencias y otros resultados económicos significativos pueden ser modelados sin el recurso a esta asunción.

Por otra parte, “es la madre de” no es una relación transitiva, porque si Alicia es la madre de Brenda, y Brenda es la madre de Claire, después Alicia no es siempre la madre de Claire. Cuál es más, es antitransitive: Alicia puede nunca sea la madre de Claire.

Entonces otra vez, en biología necesitamos a menudo considerar maternidad sobre un número arbitrario de generaciones: la relación “es a matrilinear antepasado de ". Esto es una relación transitiva. Más exacto, es encierro transitivo de la relación “está la madre de”.

Más ejemplos de relaciones transitivas:

• “es a subconjunto de " (fije la inclusión)
• “se divide” (divisibilidad)
• “implica” (implicación)

Características del encierro

El inverso de una relación transitiva es siempre transitivo: e.g. está sabiendo que “a subconjunto de " es transitivo y “es a sobreconjunto de " está su inverso, nosotros puede concluir que el último es transitivo también.

La intersección de dos relaciones transitivas es siempre transitiva: estamos sabiendo que “fue llevado antes de que” y “tenga el mismo nombre que” transitivo, podemos concluir que “fue llevado antes y también tiene el mismo nombre que” también transitivo.

La unión de dos relaciones transitivas no es siempre transitiva. Por ejemplo “fue llevado antes o tiene el mismo nombre que” no está generalmente una relación transitiva.

El complemento de una relación transitiva no es siempre transitivo. Por ejemplo, mientras que el “igual a” es transitivo, “no el igual a” es solamente transitivo en sistemas con a lo más dos elementos.

Características de la transitividad

Para una relación transitiva los siguientes son equivalentes:

• irreflexivity
• asimetría
• siendo a orden parcial terminante

Otras características que requieren transitividad

• preorder - a reflexivo relación transitiva
• orden parcial - antisimétrico preorder
• el total preorder - a total preorder
• relación de equivalencia - a simétrico preorder
• el ordenar débil terminante - una orden parcial terminante en la cual el incomparability es una relación de equivalencia
• el ordenar total - a total, antisimétrico relación transitiva

Cuenta de relaciones transitivas

Desemejante de otras características de la relación, ningún fórmula general que cuenta el número de relaciones transitivas en un sistema finito (secuencia A006905 en OEIS) se sabe.^[1] Sin embargo, hay un fórmula para encontrar el número de las relaciones que son simultáneamente reflexivas, simétricas, y transitivas - es decir relaciones de equivalencia - (secuencia A000110 en OEIS), los que son simétricos y transitivos, los que son simétricos, transitivos, y antisimétricos, y los que son totales, transitivos, y antisimétricos. Pfeiffer^[2] ha hecho un cierto progreso en esta dirección, expresando relaciones con combinaciones de estas características en términos de uno a, pero todavía calcular es difícil. Vea también^[3].

Número de n- relaciones binarias del elemento de diversos tipos
n	todos	transitivo	reflexivo	preorder	orden parcial	el total preorder	orden total	relación de equivalencia
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65536	3994	4096	355	219	75	24	15
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

entonces mSp.