Relación transitiva

En matemáticas , una relación homogénea $R$ sobre un conjunto $X$ es transitivo si para todos los elementos $de una$ , $b$ , $c$ en $X$ , siempre que $R$ se refiere $a$ a $b$ y $b$ a $c$ , entonces $R$ también se refiere $a$ a $c$ . Cada orden parcial , así como cada relación de equivalencia, debe ser transitiva.

Definición

Relaciones binarias

	Simétrico	Antisimétrico	Conectado	Bien fundado	Tiene uniones	Tiene cumple
Relación de equivalencia	✓	✗	✗	✗	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗
Orden parcial	✗	✓	✗	✗	✗	✗
Reserva total	✗	✗	✓	✗	✗	✗
Orden total	✗	✓	✓	✗	✗	✗
Ordenamiento previo	✗	✗	✓	✓	✗	✗
Bien casi ordenado	✗	✗	✗	✓	✗	✗
Bien ordenado	✗	✓	✓	✓	✗	✗
Enrejado	✗	✓	✗	✗	✓	✓
Unión-semirrejilla	✗	✓	✗	✗	✓	✗
Encuentro-semilattice	✗	✓	✗	✗	✗	✓

Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila.
Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica.
Todas las definiciones requieren tácitamente transitividad y reflexividad .

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

para todo

a, b, c \in 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 $un R b$ es la notación infija para $(a, b) \in R$ .

Ejemplos de

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 el padre biológico de" no es una relación transitiva, porque si Alice es el padre biológico de Brenda y Brenda es el padre biológico de Claire, entonces Alice no es el padre biológico de Claire. Es más, es antitransitivo : Alice nunca podrá ser la madre biológica de Claire.

"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 números reales o el conjunto de números naturales:

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

siempre que x ≥ y y 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 de conjuntos)
"divide" ( divisibilidad , una relación de 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 en números naturales)
"es un miembro del conjunto" (simbolizado como "∈") ^[2]
"es perpendicular a" (una relación sobre líneas en geometría euclidiana )

La relación vacía en cualquier conjunto ${\ Displaystyle X}$ es transitivo ^[3]^[4] porque no hay elementos ${\ Displaystyle a, b, c \ en X}$ tal que ${\ Displaystyle aRb}$ y ${\ Displaystyle bRc}$ , y por tanto la condición de transitividad es vacuosamente 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 \ en X}$ están ${\ 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 \ en X}$ y por lo tanto ${\ Displaystyle R}$ es vagamente transitivo.

Propiedades

Propiedades de cierre

La inversa (recíproca) de una relación transitiva es siempre transitiva. Por ejemplo, sabiendo que "es un subconjunto de" es transitivo y "es un superconjunto de" es su inverso, se puede concluir que este último también es transitivo.
La intersección de dos relaciones transitivas es siempre transitiva. Por ejemplo, sabiendo que "nació antes" y "tiene el mismo nombre que" son transitivos, 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 necesita ser transitiva. Por ejemplo, "nació antes o tiene el mismo nombre que" no es una relación transitiva, ya que, por ejemplo, Herbert Hoover está relacionado con Franklin D. Roosevelt , que a su vez está relacionado con Franklin Pierce , mientras que Hoover no está relacionado con Franklin Pierce. .
El complemento de una relación transitiva no necesita ser transitivo. 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 solo si es irreflexiva . ^[5]

Una relación transitiva no necesita ser reflexiva . Cuando lo es, se llama pedido anticipado . Por ejemplo, en el set X = {1,2,3}:

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

Extensiones transitivas y cierre transitivo

Deje que $R$ sea una relación binaria en el set $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 $R$ , y si $(a, b) \in R$ y $(b, c) \in R$ entonces $(a, c) \in R 1$ . ^[6] Por ejemplo, suponga que $X$ es un conjunto de ciudades, algunas de las cuales están conectadas por carreteras. Deje que $R$ sea la relación en ciudades donde $(A, B) \in 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 se puede definir por $(A, C) \in 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 transitivo es en sí misma, es decir, si $R$ es una relación transitiva entonces $R 1 = R$ .

La extensión transitiva de $R 1$ estaría denotada por $R 2$ , y continuando así, en general, la extensión transitiva de $R i$ sería $R i + 1$ . El cierre transitivo de $R$ , denotado por $R *$ o $R \infty$ es la unión de conjuntos de $R$ , $R 1$ , $R 2$ , .... ^[7]

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

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 en un número arbitrario de generaciones: la relación "es un ancestro 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) \in R *$ siempre que pueda viajar entre las ciudades $A$ y $C$ utilizando cualquier número de carreteras.

Propiedades de relación que requieren transitividad

Preorder : una relación reflexiva y transitiva
Pedido parcial : un pedido anticipado antisimétrico
Pedido anticipado total : un pedido anticipado conectado (anteriormente llamado total)
Relación de equivalencia : un preorden simétrico
Orden estrictamente débil : un orden parcial estricto en el que la incomparabilidad es una relación de equivalencia
Orden 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 ). ^[8] 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 ), aquellas que son simétricas y transitivas, aquellas que son simétricos, transitivos y antisimétricos, y los que son totales, transitivos y antisimétricos. Pfeiffer ^[9] ha hecho algunos avances en esta dirección, expresando relaciones con combinaciones de estas propiedades en términos entre sí, pero aún así calcular cualquiera de ellas es difícil. Ver también. ^[10]

Número de relaciones binarias de n elementos de diferentes tipos
Elementos	Alguna	Transitivo	Reflexivo	Hacer un pedido	Orden parcial	Reserva total	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	dieciséis	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3.994	4.096	355	219	75	24	15
norte	2 ^{n ²}		2 ^{n ² - n}			$\sum n k = 0 k! S (n, k)$	n !	$\sum n k = 0 S (n, k)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Propiedades relacionadas

El juego Piedra-papel-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, ^[11] pero no antitransitiva. ^[12] La relación definida por xRy si x es par e y es impar es tanto transitiva como antitransitiva. ^[13] La relación definida por xRy si x es el número sucesor de y es intransitiva ^[14] y antitransitiva. ^[15] Surgen ejemplos inesperados de intransitividad en situaciones tales como cuestiones políticas o preferencias de grupo. ^[dieciséis]

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 . ^[17]

Una relación cuasitransitiva es otra generalización; 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 . ^[18]

Ver también

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

Notas

^ Smith, Eggen y St. Andre 2006 , p. 145
^ Sin embargo, la clase de ordinales de von Neumann se construye de tal manera que ∈ es transitiva cuando se restringe a esa clase.
^ Smith, Eggen y St. Andre 2006 , p. 146
^ https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf
↑ Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Escuela de Matemáticas - Universidad de Física Charles. pag. 1. Archivado desde el original (PDF) en 2013-11-02.Lema 1.1 (iv). Tenga en cuenta que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
^ Liu 1985 , p. 111
↑ a b Liu , 1985 , p. 112
^ Steven R. Finch, "Relaciones transitivas, topologías y órdenes parciales" , 2003.
^ Götz Pfeiffer, " Contando relaciones transitivas ", Diario de secuencias de enteros , vol. 7 (2004), artículo 04.3.2.
^ Gunnar Brinkmann y Brendan D. McKay, " Contando topologías sin etiquetar y relaciones transitivas "
^ ya que, por ejemplo, 3 R 4 y 4 R 5, pero no 3 R 5
^ ya que, por ejemplo, 2 R 3 y 3 R 4 y 2 R 4
^ dado que xRy y yRz nunca pueden suceder
^ ya que, por ejemplo, 3 R 2 y 2 R 1, pero no 3 R 1
^ 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
^ Drum, Kevin (noviembre de 2018). "Las preferencias no son transitivas" . Madre Jones . Consultado el 29 de noviembre de 2018 .
^ 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 .
^ 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 (3a 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, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6a ed.), Brooks / Cole, ISBN 978-0-534-39900-9

enlaces externos

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

[1] Smith, Eggen y St. Andre 2006 , p. 145

[2] Sin embargo, la clase de ordinales de von Neumann se construye de tal manera que ∈ es transitiva cuando se restringe a esa clase.

[3] Smith, Eggen y St. Andre 2006 , p. 146

[4] ttps://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf

[5] Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Escuela de Matemáticas - Universidad de Física Charles. pag. 1. Archivado desde el original (PDF) en 2013-11-02.Lema 1.1 (iv). Tenga en cuenta que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".

[6] Liu 1985 , p. 111

[Liu112-7] Liu , 1985 , p. 112

[8] Steven R. Finch, "Relaciones transitivas, topologías y órdenes parciales" , 2003.

[9] Götz Pfeiffer, " Contando relaciones transitivas ", Diario de secuencias de enteros , vol. 7 (2004), artículo 04.3.2.

[10] Gunnar Brinkmann y Brendan D. McKay, " Contando topologías sin etiquetar y relaciones transitivas "

[11] ya que, por ejemplo, 3 R 4 y 4 R 5, pero no 3 R 5

[12] ya que, por ejemplo, 2 R 3 y 3 R 4 y 2 R 4

[13] que xRy y yRz nunca pueden suceder

[14] ya que, por ejemplo, 3 R 2 y 2 R 1, pero no 3 R 1

[15] 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

[16] Drum, Kevin (noviembre de 2018). "Las preferencias no son transitivas" . Madre Jones . Consultado el 29 de noviembre de 2018 .

[17] 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 .

[18] 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 .

[1]