Relación transitiva

relación binaria R coa propiedade de que xRy e yRz implica xRz

En matemáticas, unha relación binaria R nun conxunto X é transitiva se, para todos os elementos a, b, c en X, sempre que R relaciona a con b e b con c, entón R tamén relaciona a con c.

Toda orde parcial e toda relación de equivalencia son transitivas. Por exemplo, a desigualdade e a igualdade entre os números reais son ambas as dúas transitivas: Se a < b e b < c entón a < c; e se x = y e y = z entón x = z .

Definición editar

Relacións binarias transitivas
Simétrica Antisimétrica Conectada Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica
Relación de equivalencia   Si   Non   Non   Non   Non   Non   Si   Non   Non
Preorde (Cuasiorde)   Non   Non   Non   Non   Non   Non   Si   Non   Non
Orde parcial   Non   Si   Non   Non   Non   Non   Si   Non   Non
Preorde total   Non   Non   Si   Non   Non   Non   Si   Non   Non
Orde total   Non   Si   Si   Non   Non   Non   Si   Non   Non
Pre-Ben ordenada   Non   Non   Si   Si   Non   Non   Si   Non   Non
Cuasi-Ben ordenada   Non   Non   Non   Si   Non   Non   Si   Non   Non
Ben ordenada   Non   Si   Si   Si   Non   Non   Si   Non   Non
Retícula   Non   Si   Non   Non   Si   Si   Si   Non   Non
Semiretícula superior (join)   Non   Si   Non   Non   Si   Non   Si   Non   Non
Semiretícula inferior (meet)   Non   Si   Non   Non   Non   Si   Si   Non   Non
Orde estrita parcial   Non   Si   Non   Non   Non   Non   Non   Si   Si
Orde estrita feble   Non   Si   Non   Non   Non   Non   Non   Si   Si
Orde estrita total   Non   Si   Si   Non   Non   Non   Non   Si   Si
Simétrica Antisimétrica Conectada Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica
Definicións, para todo   e                    
  Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que   Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por   Si na columna "Simétrica" e   Non na columna "Antisimétrica".

Todas as definicións requiren tacitamente que a relación homoxénea   sexa transitiva: para todo   se   e   entón  
Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

Unha relación homoxénea R no conxunto X é unha relación transitiva se, [1]

para todo a, b, cX, se a R b e b R c, entón a R c.

Ou en termos de lóxica de primeira orde:

 ,

onde a R b é a notación infixa para (a, b) ∈ R.

Exemplos editar

Como exemplo non matemático, a relación "é ascendente de" é transitiva. Por exemplo, se Paz é ascendente de Belén e Belén é ascendente de Nuno, daquela Paz tamén é ascendente de Nuno.

"É maior que", "é polo menos tan grande como" e "é igual a" son relacións transitivas en varios conxuntos, por exemplo, o conxunto de números reais ou o conxunto de números naturais:

sempre que x > y e y > z, entón tamén x > z,
sempre que xy e yz, entón tamén xz,
sempre que x = y e y = z, entón tamén x = z.

Máis exemplos de relacións transitivas:

Exemplos de relacións non transitivas:

A relación baleira en calquera conxunto   é transitiva [2] porque non hai elementos   tal que   e  , e polo tanto a condición de transitividade é vacuamente verdadeira. Unha relación R que contén só un par ordenado tamén é transitiva: se o par ordenado é da forma   para algúns   os únicos elementos deste tipo   son  , e de feito neste caso  , mentres que se o par ordenado non é da forma   entón non hai tales elementos   e polo tanto   é vacuamente transitivo.

Propiedades editar

Propiedades de pechamento editar

  • A inversa dunha relación transitiva é sempre transitiva. Por exemplo, sabendo que "é un subconxunto de" é transitiva e que "é un superconxunto de" é a súa inversa, pódese concluír que esta última tamén é transitiva.
  • A intersección de dúas relacións transitivas é sempre transitiva. [3] Por exemplo, sabendo que "naceu antes" e "ten o mesmo nome que" son transitivas, pódese concluír que "naceu antes e tamén ten o mesmo nome que" tamén é transitiva.
  • A unión de dúas relacións transitivas non ten por que ser transitiva. Por exemplo, "naceu antes ou ten o mesmo nome que" non é unha relación transitiva.
  • O complemento dunha relación transitiva non ten por que ser transitiva.[4] Por exemplo, mentres "igual a" é transitiva, "non igual a" só é transitiva en conxuntos cun elemento como máximo.

Outras propiedades editar

Unha relación transitiva é asimétrica se e só se é irreflexiva.[5]

Unha relación transitiva non ten por que ser reflexiva. Cando o é, chámase preorde. Por exemplo, no conxunto X = {1,2,3}:

  • R = { (1,1), (2,2), (3,3), (1,3), (3,2) } é reflexiva, pero non transitiva, xa que o par (1,2) está ausente,
  • R = { (1,1), (2,2), (3,3), (1,3) } é reflexiva e transitiva, polo que é unha preorde,
  • R = { (1,1), (2,2), (3,3) } é reflexiva e transitiva, tamén é unha preorde.

Tipos de relación que requiren transitividade editar

Contando as relacións transitivas editar

Non se coñece ningunha fórmula xeral que conte o número de relacións transitivas nun conxunto finito (secuencia A006905 na OEIS). No entanto, existe unha fórmula para atopar o número de relacións que son simultaneamente reflexivas, simétricas e transitivas, é dicir, relacións de equivalencia (secuencia A000110 na OEIS) , as simétricas e transitivas, as simétricas, transitivas., e antisimétricas, e as que son totais, transitivas e antisimétricas. Pfeiffer fixo algúns progresos nesta dirección, expresando relacións con combinacións destas propiedades en termos entre si, mais aínda é difícil calcular calquera en si mesma. Véxase tamén Brinkmann e McKay (2005).

Propiedades relacionadas editar

Unha relación R chámase intransitiva se non é transitiva, é dicir, se xRy e yRz, pero non xRz, para algúns x, y, z. Pola contra, unha relación R chámase antitransitiva se xRy e yRz sempre implican que non se cumpre xRz. Por exemplo, a relación definida por xRy se xy é un número par é intransitiva,[6] mais non antitransitiva.[7] A relación definida por xRy se x é par e y é impar é transitiva e antitransitiva.[8] A relación definida por xRy se x é o número sucesor de y é tanto intransitiva [9] como antitransitiva.[10]

Notas editar

  1. Smith, Eggen & St. Andre 2006
  2. Smith, Eggen & St. Andre 2006
  3. Bianchi, Mariagrazia; Mauri, Anna Gillio Berta; Herzog, Marcel; Verardi, Libero (2000-01-12). "On finite solvable groups in which normality is a transitive relation". Journal of Group Theory 3 (2). ISSN 1433-5883. doi:10.1515/jgth.2000.012. Arquivado dende o orixinal o 2023-02-04. Consultado o 2022-12-29. 
  4. Robinson, Derek J. S. (January 1964). "Groups in which normality is a transitive relation". Mathematical Proceedings of the Cambridge Philosophical Society 60 (1): 21–38. Bibcode:1964PCPS...60...21R. doi:10.1017/S0305004100037403. 
  5. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics - Physics Charles University. p. 1. Arquivado dende o orixinal (PDF) o 2013-11-02.  Lemma 1.1 (iv).
  6. posto que, por exemplo, 3R4 e 4R5, mais non 3R5
  7. posto que, por exemplo, 2R3 e 3R4 e 2R4
  8. posto que xRy eyRz nunca pode acontecer
  9. posto que, por exemplo, 3R2 e 2R1, mais non 3R1
  10. posto que, máis xeneralmente, xRy e yRz implica x=y+1=z+2≠z+1, isto é, non xRz, para todos os x, y, z

Véxase tamén editar

Bibliografía editar

Outros artigos editar

Ligazóns externas editar