Relación transitiva - Transitive relation

En matemáticas , una relación R en un conjunto X es transitiva 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 transitivas
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico También conocido como: Total, Semiconnex Antirreflejos 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 ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ Orden parcial estricto ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Orden estrictamente débil ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Orden total estricto ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✓ Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones: ${\ Displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b \, {\ text {y}} \, S \ neq \ varnothing:}}$ ${\ Displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$ ${\ Displaystyle \ scriptstyle {aRb \, {\ text {y}} \, bRa \ Rightarrow a = b}}$ ${\ Displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {o}} \, bRa}}$ ${\ Displaystyle \ scriptstyle {\ min S \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {a \ vee b \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {a \ wedge b \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {aRa}}$ ${\ Displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$ ${\ Displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$
Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Aquí se enumeran las propiedades adicionales que puede satisfacer una relación homogénea. ${\ Displaystyle R}$${\ Displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b, c, {\ text {if}} aRb {\ text {y}} bRc {\ text {luego}} aRc}.}$

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

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 un R b es la notación infija para ( a , b ) ∈ 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 miembro del conjunto" (simbolizado como "∈")
• "es perpendicular a" (una relación sobre líneas en geometría euclidiana )

La relación vacía en cualquier conjunto es transitiva porque no hay elementos tales que y , y por lo 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 para algunos, los únicos elementos que lo son , y de hecho en este caso , mientras que si el par ordenado no es de la forma, entonces no existen tales elementos. y por tanto es vacuosamente transitivo. ${\ Displaystyle X}$${\ Displaystyle a, b, c \ en X}$${\ Displaystyle aRb}$${\ displaystyle bRc}$${\ Displaystyle (x, x)}$${\ Displaystyle x \ in X}$${\ Displaystyle a, b, c \ en X}$${\ Displaystyle a = b = c = x}$${\ Displaystyle aRc}$${\ Displaystyle (x, x)}$${\ Displaystyle a, b, c \ en X}$${\ Displaystyle R}$

Propiedades

Propiedades de cierre

• El inverso (inverso) de una relación transitiva es siempre transitivo. 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 .

Una relación transitiva no necesita ser reflexiva . Cuando lo es, se llama preorden . 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 ₁ , es la relación binaria más pequeña en X tal que R ₁ contiene R , y si ( a , b ) ∈ R y ( b , c ) ∈ R entonces ( a , c ) ∈ R ₁ . 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 ) ∈ 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 ) ∈ R ₁ 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 ₁ = R .

La extensión transitiva de R ₁ estaría denotada por R ₂ , 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 ^∞ es la unión de conjuntos de R , R ₁ , R ₂ , ....

El cierre transitivo de una relación es una relación transitiva.

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 ) ∈ R * siempre que pueda viajar entre las ciudades A y C utilizando cualquier número de carreteras.

Propiedades de relación que requieren transitividad

• Preorden - 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 ). 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étricas, transitivas , y antisimétricos, y los que son totales, transitivos y antisimétricos. Pfeiffer 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.

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		2 n 2 - n			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$S ( n , k )	n !	${\ textstyle \ sum _ {k = 0} ^ {n}}$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, pero no antitransitiva. La relación definida por xRy si x es par e y es impar es tanto transitiva como antitransitiva. La relación definida por xRy si x es el número sucesor de y es intransitiva y antitransitiva. Surgen ejemplos inesperados de intransitividad en situaciones tales como cuestiones políticas o preferencias de grupo.

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 .

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 .

Ver también

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

Notas

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 . Cambridge University Press, 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