Relación transitiva

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

Relacións binarias transitivas v c e
Simétrica Antisimétrica Conexa 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 Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Definicións, para todo ${\displaystyle a,b}$ e ${\displaystyle S\neq \varnothing$ :} ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{non }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}}$
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 ${\displaystyle R}$ sexa transitiva: para todo ${\displaystyle a,b,c,}$ se ${\displaystyle aRb}$ e ${\displaystyle bRc}$ entón ${\displaystyle aRc.}$ 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:

${\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}$,

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

Exemplos

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:

• "é o sucesor de" (unha relación sobre números naturais)
• "é perpendicular a" (unha relación en liñas en xeometría euclidiana)

A relación baleira en calquera conxunto ${\displaystyle X}$ é transitiva ^[2] porque non hai elementos ${\displaystyle a,b,c\in X}$ tal que ${\displaystyle aRb}$ e ${\displaystyle bRc}$, 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 ${\displaystyle (x,x)}$ para algúns ${\displaystyle x\in X}$ os únicos elementos deste tipo ${\displaystyle a,b,c\in X}$ son ${\displaystyle a=b=c=x}$, e de feito neste caso ${\displaystyle aRc}$, mentres que se o par ordenado non é da forma ${\displaystyle (x,x)}$ entón non hai tales elementos ${\displaystyle a,b,c\in X}$ e polo tanto ${\displaystyle R}$ é vacuamente transitivo.

Propiedades

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.

Tipos de relación que requiren transitividade

• 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

Contando as relacións transitivas

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

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]