Relación transitiva

En matemáticas , una relación binaria R en un conjunto X es transitiva si, para todos los elementos a , b , c en X , siempre que R relaciona a con b y b con c , entonces R también relaciona a con c .

Todo orden parcial y toda relación de equivalencia es transitiva. Por ejemplo, la igualdad entre números reales y la menor que son ambas transitivas: si a < b y b < c , entonces a < c ; y si x = y e y = z , entonces x = z .

Una relación homogénea R en el conjunto X es una relación transitiva si, ^{[ 1 ]}

para todo a , b , c ∈ X , si a R b y b R c , entonces a R c .

O en términos de lógica de primer orden :

${\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}$,

donde a R b es la notación infija para ( a , b ) ∈ R .

Como ejemplo no matemático, la relación "es antepasada de" es transitiva. Por ejemplo, si Amy es antepasada de Becky, y Becky es antepasada de Carrie, entonces Amy también es antepasada de Carrie.

Por otro lado, la relación "es la madre biológica de" no es transitiva, ya que si Alice es la madre biológica de Brenda, y Brenda es la madre biológica de Claire, entonces no se deduce que Alice sea la madre biológica de Claire. De hecho, esta relación es antitransitiva : Alice nunca puede ser la madre biológica de Claire.

Las relaciones no transitivas y no antitransitivas incluyen los calendarios deportivos (horarios de los playoffs), "conoce" y "habla con".

Los ejemplos "es mayor que", "es al menos tan grande como" y "es igual a" ( igualdad ) son relaciones transitivas en diversos conjuntos. Al igual que el conjunto de los números reales o el conjunto de los números naturales:

siempre que x > y e y > z , entonces también x > z

siempre que x ≥ y e y ≥ z , entonces también x ≥ z

siempre que x = y e y = z , entonces también x = z .

Más ejemplos de relaciones transitivas:

• "es un subconjunto de" (inclusión de conjuntos, una relación entre conjuntos)
• "divide" ( divisibilidad , una relación sobre los números naturales)
• "implica" ( implicación , simbolizada por "⇒", una relación entre proposiciones )

Ejemplos de relaciones no transitivas:

• "es el sucesor de" (una relación sobre números naturales)
• "es un miembro del conjunto" (simbolizado como "∈") ^{[ 2 ]}
• "es perpendicular a" (una relación entre líneas en geometría euclidiana )

La relación vacía en cualquier conjunto${\displaystyle X}$es transitivo ^{[ 3 ]} porque no hay elementos${\displaystyle a,b,c\in X}$de tal manera que${\displaystyle aRb}$y${\displaystyle bRc}$y por lo tanto la condición de transitividad es trivialmente verdadera . Una relación R que contiene solo un par ordenado también es transitiva: si el par ordenado es de la forma${\displaystyle (x,x)}$para algunos${\displaystyle x\in X}$los únicos elementos de este tipo${\displaystyle a,b,c\in X}$son${\displaystyle a=b=c=x}$y de hecho en este caso${\displaystyle aRc}$, mientras que si el par ordenado no es de la forma${\displaystyle (x,x)}$entonces no existen tales elementos${\displaystyle a,b,c\in X}$y por lo tanto${\displaystyle R}$es trivialmente transitivo.

La transitividad vacía es transitividad cuando en una relación no hay pares ordenados de la forma ( a , b ) y ( b , c ).

Sea R una relación binaria en el conjunto X. La extensión transitiva de R , denotada R ₁ , es la relación binaria más pequeña en X tal que R ₁ contiene a R , y si ( a , b ) ∈ R y ( b , c ) ∈ R entonces ( a , c ) ∈ R ₁ . ^{[ 7 ]} Por ejemplo, supongamos que X es un conjunto de pueblos, algunos de los cuales están conectados por carreteras. Sea R la relación en los pueblos donde ( A , B ) ∈ R si hay una carretera que une directamente el pueblo A y el pueblo B . Esta relación no tiene por qué ser transitiva. La extensión transitiva de esta relación se puede definir por ( A , C ) ∈ R ₁ si se puede viajar entre los pueblos A y C usando como máximo dos carreteras.

Si una relación es transitiva, entonces su extensión transitiva es ella misma, es decir, si R es una relación transitiva, entonces R ₁ = R .

La extensión transitiva de R ₁ se denotaría por R ₂ , y continuando de esta manera, en general, la extensión transitiva de R _i sería R _{i + 1} . El cierre transitivo de R , denotado por R * o R ^∞ es la unión de conjuntos de R , R ₁ , R ₂ , ... . ^{[ 8 ]}

El cierre transitivo de una relación es una relación transitiva. ^{[ 8 ]}

La relación "es padre biológico de" en un conjunto de personas no es una relación transitiva. Sin embargo, en biología, a menudo surge la necesidad de considerar la paternidad biológica a lo largo de un número arbitrario de generaciones: la relación "es antepasado biológico de" es una relación transitiva y es el cierre transitivo de la relación "es padre biológico de".

Para el ejemplo de pueblos y carreteras anterior, ( A , C ) ∈ R * siempre que se pueda viajar entre los pueblos A y C utilizando cualquier número de carreteras.

• Preordenar : una relación reflexiva y transitiva
• Orden parcial : un preorden antisimétrico
• Total preorden – una preorden conectada (anteriormente llamada total)
• Relación de equivalencia : un preorden simétrico
• Ordenamiento débil estricto : un orden parcial estricto en el que la incomparabilidad es una relación de equivalencia.
• Ordenación total : una relación conectada (total), antisimétrica y transitiva.

No se conoce ninguna fórmula general que cuente el número de relaciones transitivas en un conjunto finito (secuencia A006905 en la OEIS ) . ^{[ 9 ]} Sin embargo, existe una fórmula para hallar el número de relaciones que son simultáneamente reflexivas, simétricas y transitivas —es decir, relaciones de equivalencia— ( secuencia A000110 en la OEIS ) , aquellas que son simétricas y transitivas, aquellas que son simétricas, transitivas y antisimétricas, y aquellas que son totales, transitivas y antisimétricas. Pfeiffer ^{[ 10 ]} ha avanzado en esta dirección, expresando relaciones con combinaciones de estas propiedades en términos de otras, pero aún así, calcular cualquiera de ellas es difícil. Véase también Brinkmann y McKay (2005) ^{[ 11 ]} y Mala (2022). ^{[ 12 ]}

Dado que la reflexivización de cualquier relación transitiva es un preorden , el número de relaciones transitivas en un conjunto de n elementos es como máximo el 2n ^- veces del número de preórdenes, por lo tanto es asintóticamente${\displaystyle 2^{(1/4+o(1))n^{2}}}$por los resultados de Kleitman y Rothschild. ^{[ 13 ]}

Nótese que S ( n , k ) se refiere a los números de Stirling de segundo tipo .

Una relación R se denomina intransitiva si no es transitiva, es decir, si xRy y yRz , pero no xRz , para algún x , y , z . Por el contrario, una relación R se denomina antitransitiva si xRy y yRz siempre implican que xRz no se cumple. Por ejemplo, la relación definida por xRy si xy es un número par es intransitiva, ^{[ 14 ]} pero no antitransitiva. ^{[ 15 ]} La relación definida por xRy si x es par e y es impar es tanto transitiva como antitransitiva. ^{[ 16 ]} La relación definida por xRy si x es el número sucesor de y es tanto intransitiva ^{[ 17 ]} como antitransitiva. ^{[ 18 ]} Ejemplos inesperados de intransitividad surgen en situaciones como cuestiones políticas o preferencias de grupo. ^{[ 19 ]}

Generalizado a versiones estocásticas ( transitividad estocástica ), el estudio de la transitividad encuentra aplicaciones en la teoría de la decisión , la psicometría y los modelos de utilidad . ^{[ 20 ]}

Una relación cuasitransitiva es otra generalización; ^{[ 5 ]} se requiere que sea transitiva solo en su parte no simétrica. Dichas relaciones se utilizan en la teoría de la elección social o en la microeconomía . ^{[ 21 ]}

Proposición: Si R es univalente , entonces R;R ^T es transitivo.

Prueba: Supongamos${\displaystyle xR;R^{T}yR;R^{T}z.}$Entonces existen a y b tales que${\displaystyle xRaR^{T}yRbR^{T}z.}$Dado que R es univalente, yRb y aR ^T y implican a = b . Por lo tanto , x R a R ^T z , de ahí que x R;R ^T z y R;R ^T sea transitivo.

Corolario : Si R es univalente, entonces R;R ^T es una relación de equivalencia en el dominio de R.

Demostración: R;R ^T es simétrico y reflexivo en su dominio. Con la univalencia de R , se cumple el requisito transitivo de equivalencia.

• Reducción transitiva
• dados intransitivos
• Teoría de la elección racional
• Silogismo hipotético : transitividad del condicional material

• Liu, CL (1985), Elementos de matemáticas discretas , McGraw-Hill, ISBN 0-07-038133-X
• Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), Transición a las matemáticas avanzadas (6.ª  ed.), Brooks/Cole, ISBN 978-0-534-39900-9

• Grimaldi, Ralph P. (1994), Matemáticas discretas y combinatorias (3.ª  ed.), Addison-Wesley, ISBN 0-201-19912-2
• Gunther Schmidt , 2010. Matemáticas relacionales . Cambridge University Press, ISBN 978-0-521-76268-7.

• "Transitividad" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Transitividad en acción en cut-the-knot