Relación transitiva

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

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

## Definición 
Unha relación homoxénea  no conxunto  é unha *relación transitiva* se, 

: para todo , se  e , entón .

Ou en termos de lóxica de primeira orde:

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

onde  é a notación infixa para .

## 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* &#x3E; *y* e *y* &#x3E; *z*, entón tamén *x* &#x3E; *z,*
: sempre que *x* &#x2265; *y* e *y* &#x2265; *z*, entón tamén *x* &#x2265; *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  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 . 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     , 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.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
*Gunther Schmidt, 2010. *Relational Mathematics*. Cambridge University Press, .
* 
* 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 
* 
* Transitivity in Action at cut-the-knot