Relación transitiva

Tipo de relación binaria
Relación transitiva
TipoRelación binaria
CampoÁlgebra elemental
DeclaraciónUna relación en un conjunto es transitiva si, para todos los elementos , , en , siempre que se relaciona con y con , entonces también se relaciona con . R {\estilo de visualización R} incógnita {\estilo de visualización X} a {\estilo de visualización a} b {\estilo de visualización b} do {\estilo de visualización c} incógnita {\estilo de visualización X} R {\estilo de visualización R} a {\estilo de visualización a} b {\estilo de visualización b} b {\estilo de visualización b} do {\estilo de visualización c} R {\estilo de visualización R} a {\estilo de visualización a} do {\estilo de visualización c}
Declaración simbólica a , b , do incógnita : ( a R b b R do ) a R do {\displaystyle \paratodos a,b,c\en X:(aRb\wedge bRc)\Flecha derecha aRc}

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 son transitivas. Por ejemplo, la menor que y la igualdad entre números reales son ambas transitivas: Si a < b y b < c entonces a < c ; y si x = y e y = z entonces x = z .

Definición

Relaciones binarias transitivas 
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico
Total, SemiconnexAnti-
reflexivo
Relación de equivalencia Marca verdeY Marca verdeY
Pedido anticipado (cuasi pedido) Marca verdeY
Orden parcial Marca verdeY Marca verdeY
Pedido anticipado total Marca verdeY Marca verdeY
Pedido total Marca verdeY Marca verdeY Marca verdeY
Pedido previo al pozo Marca verdeY Marca verdeY Marca verdeY
Bien-cuasi-ordenamiento Marca verdeY Marca verdeY
Buen orden Marca verdeY Marca verdeY Marca verdeY Marca verdeY
Enrejado Marca verdeY Marca verdeY Marca verdeY Marca verdeY
Unión de semirrejilla Marca verdeY Marca verdeY Marca verdeY
Conocer-semilattice Marca verdeY Marca verdeY Marca verdeY
Orden parcial estricta Marca verdeY Marca verdeY Marca verdeY
Orden débil estricta Marca verdeY Marca verdeY Marca verdeY
Orden total estricta Marca verdeY Marca verdeY Marca verdeY Marca verdeY
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico
Definiciones, para todos y a , b {\estilo de visualización a,b} S : {\displaystyle S\neq \varnothing :} a R b b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} a R b  y  b R a a = b {\displaystyle {\begin{aligned}aRb{\text{ y }}&bRa\\\Rightarrow a={}&b\end{aligned}}} a b a R b  o  b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ o }}&bRa\end{aligned}}} mín. S existe {\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}} a b existe {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} a b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} a R a {\displaystyle aRa} not  a R a {\displaystyle {\text{not }}aRa} a R b not  b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}
Marca verdeYindica que la propiedad de la columna siempre es verdadera para el término de la fila (a la izquierda), mientras que indica que la propiedad no está garantizada en general (puede cumplirse o no). Por ejemplo, que toda relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica con en la columna "Simétrica" ​​y en la columna "Antisimétrica", respectivamente.Marca verdeY

Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva: para todo si y entonces La definición de un término puede requerir propiedades adicionales que no están enumeradas en esta tabla. R {\displaystyle R} a , b , c , {\displaystyle a,b,c,} a R b {\displaystyle aRb} b R c {\displaystyle bRc} a R c . {\displaystyle aRc.}

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

para todo a , b , cX , si a R b y b R c , entonces a R c .

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

a , b , c X : ( a R b b R c ) a R c {\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 .

Ejemplos

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

Por otra parte, "es la madre biológica de" no es una relación transitiva, porque si Alice es la madre biológica de Brenda y Brenda es la madre biológica de Claire, entonces no se sigue 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 partidos deportivos (calendarios de playoffs), 'sabe' y 'habla con'.

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

siempre que x > y y y > z , entonces también x > z
siempre que xy e yz , entonces también xz
siempre que x = y e y = z , entonces también x = z .

Más ejemplos de relaciones transitivas:

Ejemplos de relaciones no transitivas:

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

Propiedades

Propiedades del cierre

  • La inversa de una relación transitiva siempre es transitiva. Por ejemplo, si se sabe que "es un subconjunto de" es transitiva y que "es un superconjunto de" es su inversa, se puede concluir que esta última también es transitiva.
  • La intersección de dos relaciones transitivas es siempre transitiva. [4] Por ejemplo, sabiendo que "nació antes de" y "tiene el mismo nombre que" son transitivas, se puede concluir que "nació antes y también tiene el mismo nombre que" también es transitivo.
  • La unión de dos relaciones transitivas no tiene por qué ser necesariamente transitiva. Por ejemplo, "nació antes o tiene el mismo nombre que" no es una relación transitiva, ya que, por ejemplo, Herbert Hoover está emparentado con Franklin D. Roosevelt , quien a su vez está emparentado con Franklin Pierce , mientras que Hoover no está emparentado con Franklin Pierce.
  • El complemento de una relación transitiva no necesita ser transitivo. [5] Por ejemplo, mientras que "igual a" es transitivo, "no igual a" solo es transitivo en conjuntos con como máximo un elemento.

Otras propiedades

Una relación transitiva es asimétrica si y sólo si es irreflexiva . [6]

Una relación transitiva no tiene por qué ser reflexiva . Cuando lo es, se denomina preorden . Por ejemplo, en el conjunto X = {1,2,3}:

  • R = { (1,1), (2,2), (3,3), (1,3), (3,2) } es reflexiva, pero no transitiva, ya que el par (1,2) está ausente,
  • R = { (1,1), (2,2), (3,3), (1,3) } es reflexivo y transitivo, por lo que es un preorden,
  • R = { (1,1), (2,2), (3,3) } es reflexivo y transitivo, otro preorden.

Como contraejemplo, la relación entre los números reales es transitiva, pero no reflexiva. < {\displaystyle <}

Extensiones transitivas y clausura transitiva

Sea R una relación binaria en el conjunto X . La extensión transitiva de R , denotada R 1 , es la relación binaria más pequeña en X tal que R 1 contiene a R , y si ( a , b ) ∈ R y ( b , c ) ∈ R entonces ( a , c ) ∈ R 1 . [7] Por ejemplo, supongamos que X es un conjunto de ciudades, algunas de las cuales están conectadas por carreteras. Sea R la relación en ciudades donde ( A , B ) ∈ R si hay una carretera que une directamente la ciudad A y la ciudad B . Esta relación no necesita ser transitiva. La extensión transitiva de esta relación puede definirse por ( A , C ) ∈ R 1 si puede viajar entre las ciudades A y C utilizando 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 1 = R .

La extensión transitiva de R 1 se denotaría por R 2 , y continuando de esta manera, en general, la extensión transitiva de R i sería R i + 1 . La clausura transitiva de R , denotada por R * o R es la unión de conjuntos de R , R 1 , R 2 , ... . [8]

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

La relación "es el 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 un antepasado biológico de" es una relación transitiva y es el cierre transitivo de la relación "es el padre biológico de".

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

Tipos de relaciones que requieren transitividad

Contando relaciones transitivas

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, hay una fórmula para encontrar el número de relaciones que son simultáneamente reflexivas, simétricas y transitivas –en otras palabras, 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 hecho algunos avances en esta dirección, expresando relaciones con combinaciones de estas propiedades en términos de cada una de ellas, pero aún así es difícil calcular cualquiera de ellas. Véase también Brinkmann y McKay (2005). [11]

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 2 n veces mayor que el número de preórdenes, por lo que es asintóticamente correcto según los resultados de Kleitman y Rothschild. [12] 2 ( 1 / 4 + o ( 1 ) ) n 2 {\displaystyle 2^{(1/4+o(1))n^{2}}}

Número de relaciones binarias de n elementos de diferentes tipos
ElementosCualquierTransitivoReflexivoSimétricoHacer un pedidoOrden parcialPedido anticipado totalPedido totalRelación de equivalencia
0111111111
1221211111
216134843322
3512171646429191365
465.5363.9944.0961.024355219752415
norte2 y 22n ( n −1 )2n ( n +1) / 2nk =
0
k ! S ( n , k )
¡no !nk =
0
S ( n , k )
OEISA002416A006905A053763A006125A000798A001035A000670A000142A000110

Téngase en cuenta que S ( n , k ) se refiere a números de Stirling del segundo tipo .

Diagrama de ciclo
El juego de piedra, papel o tijera se basa en una relación intransitiva y antitransitiva " x le gana a y ".

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

Generalizado a versiones estocásticas ( transitividad estocástica ), el estudio de la transitividad encuentra aplicaciones en la teoría de decisiones , la psicometría y los modelos de utilidad . [19]

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

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

Prueba: Supongamos Entonces hay a y b tales que Como R es univalente, yRb y aR T y implican a = b . Por lo tanto x R a R T z , por lo tanto x R;R T z y R;R T son transitivos. x R ; R T y R ; R T z . {\displaystyle xR;R^{T}yR;R^{T}z.} x R a R T y R b R T z . {\displaystyle xRaR^{T}yRbR^{T}z.}

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étrica y reflexiva en su dominio. Con univalencia de R , se cumple el requisito transitivo de equivalencia.

Véase también

Notas

  1. ^ Smith, Eggen y St. Andre 2006, pág. 145
  2. ^ Sin embargo, la clase de ordinales de von Neumann está construida de tal manera que ∈ es transitivo cuando se restringe a esa clase.
  3. ^ Smith, Eggen y St. Andre 2006, pág. 146
  4. ^ Bianchi, Mariagrazia; Mauri, Anna Gillio Berta; Herzog, Marcel; Verardi, Libero (12 de enero de 2000). "Sobre grupos finitos resolubles en los que la normalidad es una relación transitiva". Journal of Group Theory . 3 (2). doi :10.1515/jgth.2000.012. ISSN  1433-5883. Archivado desde el original el 4 de febrero de 2023 . Consultado el 29 de diciembre de 2022 .
  5. ^ ab Robinson, Derek JS (enero de 1964). «Grupos en los que la normalidad es una relación transitiva». Mathematical Proceedings of the Cambridge Philosophical Society . 60 (1): 21–38. Bibcode :1964PCPS...60...21R. doi :10.1017/S0305004100037403. ISSN  0305-0041. S2CID  119707269. Archivado desde el original el 2023-02-04 . Consultado el 2022-12-29 .
  6. ^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Facultad de Matemáticas - Física de la Universidad Charles. p. 1. Archivado desde el original (PDF) el 2 de noviembre de 2013.Lema 1.1 (iv). Nótese que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
  7. ^ Liu 1985, pág. 111
  8. ^Ab Liu 1985, pág. 112
  9. ^ Steven R. Finch, "Relaciones transitivas, topologías y órdenes parciales" Archivado el 4 de marzo de 2016 en Wayback Machine , 2003.
  10. ^ Götz Pfeiffer, "Contando relaciones transitivas Archivado el 4 de febrero de 2023 en Wayback Machine ", Journal of Integer Sequences , Vol. 7 (2004), Artículo 04.3.2.
  11. ^ Gunnar Brinkmann y Brendan D. McKay, "Conteo de topologías sin etiquetar y relaciones transitivas " . Archivado el 20 de julio de 2005 en Wayback Machine .
  12. ^ Kleitman, D.; Rothschild, B. (1970), "El número de topologías finitas", Actas de la American Mathematical Society , 25 (2): 276–282, JSTOR  2037205
  13. ^ ya que por ejemplo 3 R 4 y 4 R 5, pero no 3 R 5
  14. ^ ya que por ejemplo 2 R 3 y 3 R 4 y 2 R 4
  15. ^ ya que xRy y yRz nunca pueden suceder
  16. ^ ya que por ejemplo 3 R 2 y 2 R 1, pero no 3 R 1
  17. ^ ya que, de manera más general, xRy y yRz implican x = y +1 = z +2≠ z +1, es decir, no xRz , para todo x , y , z
  18. ^ Drum, Kevin (noviembre de 2018). «Las preferencias no son transitivas». Mother Jones . Archivado desde el original el 29 de noviembre de 2018. Consultado el 29 de noviembre de 2018 .
  19. ^ Oliveira, IFD; Zehavi, S.; Davidov, O. (agosto de 2018). "Transitividad estocástica: axiomas y modelos". Revista de psicología matemática . 85 : 25–35. doi :10.1016/j.jmp.2018.06.002. ISSN  0022-2496.
  20. ^ Sen, A. (1969). "Cuasi-transitividad, elección racional y decisiones colectivas". Rev. Econ. Stud . 36 (3): 381–393. doi :10.2307/2296434. JSTOR  2296434. Zbl  0181.47302.

Referencias

  • Grimaldi, Ralph P. (1994), Matemáticas discretas y combinatorias (3.ª ed.), Addison-Wesley, ISBN 0-201-19912-2
  • Liu, CL (1985), Elementos de matemáticas discretas , McGraw-Hill, ISBN 0-07-038133-X
  • Gunther Schmidt , 2010. Matemáticas relacionales . Cambridge University Press, ISBN 978-0-521-76268-7 . 
  • Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), Una transición a las matemáticas avanzadas (6.ª ed.), Brooks/Cole, ISBN 978-0-534-39900-9
  • Pfeiffer, G. (2004). Conteo de relaciones transitivas. Journal of Integer Sequences , 7 (2), 3.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Transitive_relation&oldid=1248456287"