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 .
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 :}
![{\displaystyle S\neq \varnothing :}](//wikimedia.org/api/rest_v1/media/math/render/svg/a538fab804c9428c4f7d4ca3ed214a97483c4260) | ![{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a18cac1ed3115c87d45b4d751de57124233a6e00) | ![{\displaystyle {\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7550bd701e3b9f4349182cd31b6f011252f37937) | ![{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/86340704b63a925c20825c29a6bc1caffbaf8920) | ![{\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/c43f4f74b9b5f3b96cbf6fab874160fcca781a1b) | ![{\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/6bc791171001c580251f89aab8022640a0facce7) | ![{\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/9655bd850325b66e2f8f03df6227267fa73af901) | ![{\displaystyle aRa}](//wikimedia.org/api/rest_v1/media/math/render/svg/ba7fc1d9d50c65105d5edcb3478b5ca4172c54d6) | ![{\displaystyle {\text{non }}aRa}](//wikimedia.org/api/rest_v1/media/math/render/svg/6f37ccc45bf3e5daf790413f6e79ca02de2b945f) | ![{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/dee1c190f4b2b109fb080e298a5cc313597c46e0) |
|
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, c ∈ X, 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.
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 x ≥ y e y ≥ z, entón tamén x ≥ z,
- sempre que x = y e y = z, entón tamén x = z.
Máis exemplos de relacións transitivas:
- "é un subconxunto de" (inclusión de conxuntos, unha relación entre conxuntos)
- "divide" (divisibilidade, unha relación entre números naturais)
- "implica" (implicación, simbolizada por "⇒", unha relación entre proposicións)
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 de pechamento
- 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
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.
- Preorde: unha relación reflexiva e transitiva
- Orde parcial: unha preorde antisimétrica
- Preorde total: unha orde previo conectado (anteriormente chamado total).
- Relación de equivalencia: unha preorde simétrica
- Orde débil estrita: unha orde parcial estrita na que a incomparabilidade é unha relación de equivalencia
- Orde total: relación conexa (total), antisimétrica e transitiva
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).
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]
posto que, por exemplo, 3R4 e 4R5, mais non 3R5
posto que, por exemplo, 2R3 e 3R4 e 2R4
posto que xRy eyRz nunca pode acontecer
posto que, por exemplo, 3R2 e 2R1, mais non 3R1
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
Bibliografía
- Grimaldi, Ralph P. (1994). Discrete and Combinatorial Mathematics (3rd ed.). Addison-Wesley. ISBN 0-201-19912-2.
- Liu, C.L. (1985). Elements of Discrete Mathematics. McGraw-Hill. ISBN 0-07-038133-X.
- Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.
- Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006). A Transition to Advanced Mathematics (6th ed.). Brooks/Cole. ISBN 978-0-534-39900-9.
- Pfeiffer, G. (2004). Counting transitive relations. Journal of Integer Sequences, 7(2), 3.