Relación transitiva

En matemáticas, unha relación binaria Modelo:Mvar nun conxunto Modelo:Mvar é transitiva se, para todos os elementos Modelo:Mvar, Modelo:Mvar, Modelo:Mvar en Modelo:Mvar, sempre que Modelo:Mvar relaciona Modelo:Mvar con Modelo:Mvar e Modelo:Mvar con Modelo:Mvar, entón Modelo:Mvar tamén relaciona Modelo:Mvar con Modelo:Mvar.

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 Modelo:Math e Modelo:Math entón Modelo:Math; e se Modelo:Math e Modelo:Math entón Modelo:Math .

Definición

Unha relación homoxénea Modelo:Mvar no conxunto Modelo:Mvar é unha relación transitiva se,

para todo Modelo:Math, se Modelo:Math e Modelo:Math, entón Modelo:Math.

Ou en termos de lóxica de primeira orde:

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

onde Modelo:Math é a notación infixa para Modelo:Math.

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 $X$ é transitiva porque non hai elementos $a,b,c\in X$ tal que $aRb$ e $bRc$, e polo tanto a condición de transitividade é vacuamente verdadeira. Unha relación Modelo:Math que contén só un par ordenado tamén é transitiva: se o par ordenado é da forma $(x,x)$ para algúns $x\in X$ os únicos elementos deste tipo $a,b,c\in X$ son $a=b=c=x$, e de feito neste caso $aRc$, mentres que se o par ordenado non é da forma $(x,x)$ entón non hai tales elementos $a,b,c\in X$ e polo tanto $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. 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. 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.

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 Modelo: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 Modelo: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, mais non antitransitiva. A relación definida por xRy se x é par e y é impar é transitiva e antitransitiva. A relación definida por xRy se x é o número sucesor de y é tanto intransitiva como antitransitiva.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, Modelo:Isbn.
• Modelo:Cita libro
• Pfeiffer, G. (2004). Counting transitive relations. Journal of Integer Sequences, 7(2), 3.

Outros artigos

• Relación simétrica.
• Relación reflexiva.

Ligazóns externas

• Modelo:Springer
• Transitivity in Action at cut-the-knot