relación transitiva

Tipo de relación binaria

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 desigualdad y la igualdad entre números reales son ambas transitivas: si a < b y b < c entonces a < c ; y si x = y y y = z entonces x = z .

Definición

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 .

Ejemplos

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

Por otro lado, "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 esto no implica que Alice sea la madre biológica de Claire. . Es más, es antitransitivo : Alice nunca podrá ser la madre biológica de Claire.

Las relaciones no transitivas y no antitransitivas incluyen partidos deportivos (calendarios de playoffs), "saber" y "hablar con".

"Es mayor que", "es al menos tan grande como" y "es igual a" ( igualdad ) son relaciones transitivas en varios conjuntos, por ejemplo, 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 x ≥ y y y ≥ z , entonces también x ≥ z

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

Más ejemplos de relaciones transitivas:

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

Ejemplos de relaciones no transitivas:

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

The empty relation on any set ${\displaystyle X}$ is transitive^[3] because there are no elements ${\displaystyle a,b,c\in X}$ such that ${\displaystyle aRb}$ and ${\displaystyle bRc}$, and hence the transitivity condition is vacuously true. A relation R containing only one ordered pair is also transitive: if the ordered pair is of the form ${\displaystyle (x,x)}$ for some ${\displaystyle x\in X}$ the only such elements ${\displaystyle a,b,c\in X}$ are ${\displaystyle a=b=c=x}$, and indeed in this case ${\displaystyle aRc}$, while if the ordered pair is not of the form ${\displaystyle (x,x)}$ then there are no such elements ${\displaystyle a,b,c\in X}$ and hence ${\displaystyle R}$ is vacuously transitive.

Properties

Closure properties

• The converse (inverse) of a transitive relation is always transitive. For instance, knowing that "is a subset of" is transitive and "is a superset of" is its converse, one can conclude that the latter is transitive as well.
• The intersection of two transitive relations is always transitive.^[4] For instance, knowing that "was born before" and "has the same first name as" are transitive, one can conclude that "was born before and also has the same first name as" is also transitive.
• The union of two transitive relations need not be transitive. For instance, "was born before or has the same first name as" is not a transitive relation, since e.g. Herbert Hoover is related to Franklin D. Roosevelt, who is in turn related to Franklin Pierce, while Hoover is not related to Franklin Pierce.
• The complement of a transitive relation need not be transitive.^[5] For instance, while "equal to" is transitive, "not equal to" is only transitive on sets with at most one element.

Other properties

A transitive relation is asymmetric if and only if it is irreflexive.^[6]

A transitive relation need not be reflexive. When it is, it is called a preorder. For example, on set X = {1,2,3}:

• R = { (1,1), (2,2), (3,3), (1,3), (3,2) } is reflexive, but not transitive, as the pair (1,2) is absent,
• R = { (1,1), (2,2), (3,3), (1,3) } is reflexive as well as transitive, so it is a preorder,
• R = { (1,1), (2,2), (3,3) } is reflexive as well as transitive, another preorder.

Transitive extensions and transitive closure

Sea R una relación binaria en el conjunto X. La extensión transitiva de R , denotada como 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 entre 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 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 ₁ = R .

La extensión transitiva de R ₁ se denotaría por R ₂ , y siguiendo así, 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 conjunto de R , R ₁ , R ₂ , .... ^[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 la clausura transitiva de la relación "es el padre biológico de".

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

Tipos de relaciones que requieren transitividad

• Preorden : una relación reflexiva y transitiva
• Orden parcial : un preorden antisimétrico
• Reserva total : una reserva 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
• Ordenamiento total : una relación conectada (total), antisimétrica y transitiva

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, existe una fórmula para encontrar el número de relaciones que son simultáneamente reflexivas, simétricas y transitivas –es decir, relaciones de equivalencia- (secuencia A000110 en la OEIS ), las que son simétricas y transitivas, las que son simétricos, transitivos y antisimétricos, y los totales, transitivos y antisimétricos. Pfeiffer ^[10] ha hecho algunos avances en esta dirección, expresando relaciones con combinaciones de estas propiedades en términos de cada una de otras, 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 ⁿ veces mayor que el número de preordenes, por lo que es asintóticamente según los resultados de Kleitman y Rothschild. ^[12] ${\displaystyle 2^{(1/4+o(1))n^{2}}}$

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

Propiedades relacionadas

El juego piedra, papel y tijera se basa en una relación intransitiva y antitransitiva " x vence a y ".

Una relación R se llama intransitiva si no es transitiva, es decir, si xRy y yRz , pero no xRz , para algunos x , y , z . Por el contrario, una relación R se llama antitransitiva si xRy e 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 ^[13] pero no antitransitiva. ^[14] La relación definida por xRy si x es par e y es impar es transitiva y antitransitiva. ^[15] La relación definida por xRy si x es el número sucesor de y es a la vez intransitiva ^[16] y antitransitiva. ^[17] Surgen ejemplos inesperados de intransitividad 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 la decisión , la psicometría y los modelos de utilidad . ^[19]

Una relación cuasitransitiva es otra generalización; ^[5] se requiere que sea transitivo solo en su parte no simétrica. Estas 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 que entonces hay a y b tales que Dado que 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 es transitivo. ${\displaystyle xR;R^{T}yR;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.

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

Ver también

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

Notas

1. Smith, Eggen y St. Andre 2006, pág. 145
2. Sin embargo, la clase de ordinales de von Neumann se construye 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 Gilio Berta; Herzog, Marcel; Verardi, Líbero (12 de enero de 2000). "Sobre grupos finitos resolubles en los que la normalidad es una relación transitiva". Revista de teoría de grupos . 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. Robinson, Derek JS (enero de 1964). "Grupos en los que la normalidad es una relación transitiva". Actas matemáticas de la Sociedad Filosófica de Cambridge . 60 (1): 21–38. Código Bib : 1964PCPS...60...21R. doi :10.1017/S0305004100037403. ISSN  0305-0041. S2CID  119707269. Archivado desde el original el 4 de febrero de 2023 . Consultado el 29 de diciembre de 2022 .
6. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres Transitivos de Relaciones Binarias I (PDF) . Praga: Escuela de Matemáticas - Universidad Carolina de Física. pag. 1. Archivado desde el original (PDF) el 2 de noviembre de 2013.Lema 1.1 (iv). Tenga en cuenta que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
7. Liu 1985, pág. 111
8. 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 la Wayback Machine ", Journal of Integer Sequences , vol. 7 (2004), Artículo 04.3.2.
11. Gunnar Brinkmann y Brendan D. McKay, "Contando 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 Sociedad Matemática Estadounidense , 25 (2): 276–282, JSTOR  2037205
13. desde, por ejemplo, 3 R 4 y 4 R 5, pero no 3 R 5
14. desde, por ejemplo, 2 R 3 y 3 R 4 y 2 R 4
15. dado que xRy y yRz nunca pueden suceder
16. desde, por ejemplo, 3 R 2 y 2 R 1, pero no 3 R 1
17. ya que, de manera más general, xRy e yRz implican x = y +1= z +2≠ z +1, es decir, no xRz , para todo x , y , z
18. Tambor, Kevin (noviembre de 2018). "Las preferencias no son transitivas". Madre 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). "Cuasitransitividad, elección racional y decisiones colectivas". Rev. Economía. Semental . 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 . Prensa de la Universidad de Cambridge, ISBN 978-0-521-76268-7 . 
• Smith, Douglas; Eggen, Mauricio; 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). Contando relaciones transitivas. Diario de secuencias enteras , 7 (2), 3.

enlaces externos

• "Transitividad", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Transitividad en acción al cortar el nudo