# Fecho transitivo

Na matemática, o fecho transitivo de uma relação binária R sobre um conjunto X é a relação transitiva R$^+$ sobre o conjunto X de maneira que R$^+$ contém R e R$^+$ é mínimo (Lidl and Pilz 1998:337). Se a própria relação binária é transitiva, então o fecho transitivo é a própria relação; senão, o fecho transitivo é uma outra relação. Por exemplo, se X é um conjunto de aeroportos e x R y significa "existe um voo direto do aeroporto x para o aeroporto y", então o fecho transitivo de R sobre X é a relação R$^+$: "é possível voar a partir de x para y em um ou mais voos."

## Relações transitivas e exemplos

Uma relação transitiva R sobre um conjunto X é transitiva se, para todo x,y,z em X, sempre que x R y e y R z então x R z. Exemplos de relações transitivas incluem a relação de igualdade em qualquer conjunto, a relação "menor ou igual que" em qualquer conjunto linearmente ordenado, e a relação "x nasceu antes de y" no conjunto de todas as pessoas. Simbolicamente, isso pode ser descrito como: se x < y ey < z, então x < z.
Um exemplo de uma relação intransitiva é "a cidade x é alcançável através de um voo direto a partir da cidade y" no conjunto de todas as cidades. Simplesmente por haver um voo direto de uma cidade para uma segunda, e também um voo direto dessa segunda cidade para uma terceira, não implica haver um voo direto da primeira cidade para a terceira. O fecho transitivo dessa relação é uma relação diferente, que é "existe uma sequência de voos diretos que começa na cidade x e termina na cidade y". Toda relação pode ser estendida de maneira semelhante para uma relação transitiva.

## Existência e descrição

Para qualquer relação R, o fecho transitivo de R sempre existe. Para comprovar isso, note que a interseção de qualquer família de relações transitivas é novamente transitiva. Além disso, existe ao menos uma relação transitiva contendo R,
Para conjunto finitos, podemos construir o fecho transitivo passo a passo, começando por R e adicionando arestas transitivas. Isso nos dá a ideia para a construção geral. Para qualquer conjunto X, podemos provar que o fecho transitivo é dado pela seguinte expressão
    $R^{+}=\bigcup _{i\in \{1,2,3,\ldots \}}R^{i}.$
onde $R^{i}$ é a i-ésima potência de R, definida através de indução por
    $R^{1}=R\,\!$
e, para $i>0$,
    $R^{i+1}=R\circ R^{i}$
onde $\circ$ representa a composição de relações.
Para mostrar que a definição de R$^+$ mostrada acima é a menor relação transitiva contendo R, mostramos que ela contém R, que é transitiva, e que é o menor conjunto com ambas as características.
* $R\subseteq R^{+}$: $\displaystyle R^{+}$ contém contém todas $\displaystyle R^{i}$, particularmente $\displaystyle R^{+}$ contém $\displaystyle R$.
* $\displaystyle R^{+}$ é transitiva: todo elemento de $\displaystyle R^{+}$ está em um dos $\displaystyle R^{i}$, então $\displaystyle R^{+}$ deve ser transitivo pela seguinte razão: se $(s_{1},s_{2})\in R^{j}$ e $(s_{2},s_{3})\in R^{k}$, então pela composição associativa, $(s_{1},s_{3})\in R^{j+k}$ (logo, em $\displaystyle R^{+}$) por conta da definição de $\displaystyle R^{i}$.
* $\displaystyle R^{+}$ é mínima: Seja $\displaystyle G$ qualquer relação transitiva contendo $\displaystyle R$, queremos mostrar que $R^{+}\subseteq G$. Isso é suficiente para mostrar que $i>0$, $R^{i}\subseteq G$. Bem, já que $\displaystyle G$ contém $\displaystyle R$, $R^{1}\subseteq G$. E como $\displaystyle G$ é transitiva, para qualquer $R^{i}\subseteq G$, $R^{i+1}\subseteq G$ de acordo com a construção de $R^{i}\,\!$ e que é transitivo. Logo, por indução, $\displaystyle G$ contém todo $R^{i}\,\!$, e também contém $\displaystyle R^{+}$.

## Propriedades

A interseção de duas relações transitivas é transitiva.
A união de duas relações transitivas não pode ser transitiva. Para preservar a transitividade, uma delas precisa manter o fecho transitivo. Isso ocorre, por exemplo, quando geramos a união de duas relações de equivalência ou duas relações de pré-ordem. Para obter uma nova relação de equivalência ou pré-ordem uma precisa manter o fecho transitivo (reflexividade e simetria—no caso de relações de equivalência—são automáticas).

## Na teoria dos grafos

Na ciência da computação, o conceito de fecho transitivo pode ser pensado como a construção de uma estrutura de dados que possibilita responder problemas de atingibilidade. Isso é, será possível chegar à um nó b, partindo de um nó a em um ou mais saltos? Uma relação binária apenas informa que esse nó a está conectado ao nó b, e que o nó b está conectado ao nó c, etc. Após o fecho transitivo ser construído, como mostrado na figura abaixo, em uma operação O(1) pode se determinar que o nó d é atingível a partir do nó a. A estrutura de dados é geralmente armazenada como uma matriz, então se matriz[1][4] = 1, significa que o nó 4 é atingível a partir do nó 1 e um ou mais saltos.
O fecho transitivo de um grafo acíclico direcionado (GAD) é a relação de atingibilidade do GAD e uma ordem parcial estrita.

## Na lógica e na complexidade computacional

O fecho transitivo de uma relação binária não pode, geralmente, ser expresso em lógica de primeira ordem (LPO). Isso significa que não é possível escrever uma fórmula usando predicados R e T que serão satisfatíveis em qualquer modelo se e somente se T é o fecho transitivo de R.
Na teoria dos modelos finitos, lógica de primeira ordem (LPO) estendida com um operador de fecho transitivo é normalmente chamada lógica de fecho transitivo, e abreviada LPO(FT) ou apenas FT.
Na teoria da complexidade computacional, a classe NL corresponde precisamente ao conjunto de sentenças lógicas que podem ser expressas em FT. Isso acontece porque a propriedade do fecho transitivo tem uma relação próxima com o problema NL-Completo da conectividade st, para achar caminhos direcionados em um grafo. Similarmente, a classe L é de lógica de primeira ordem com fecho transitivo e comutativo. Quando o fecho transitivo é adicionado à lógica de segunda ordem, obtemos PSPACE.

## Em linguagens de consulta à banco de dados

Desde os anos 1980 o Oracle database implementa uma extensão SQL prioritária CONNECT BY... START WITH que permite a computação de um fecho transitivo como parte de uma consulta. O padrão SQL 3 (1999) um um construtor mais generalizado WITH RECURSIVE permitindo fechos transitivos serem computados dentro do processador de consultas; em 2011 esse último foi implementado por IBM DB2, Microsoft SQL Server, e PostgreSQL, entretanto não pelo MySQL (Benedikt and Senellart 2011:189).
Datalog também implementa computações transitivamente fechadas. (Silberschatz et al. 2010:C.3.6).

## Algoritmos

Algoritmos eficientes para computar o fecho transitivo de um grafo podem ser encontrados em Nuutila (1995). A técnica mais simples é provavelmente o Algoritmo de Floyd-Warshall. O métodos de pior caso mais rápidos, que não são praticamente viáveis, reduzem o problema à uma multiplicação de matrizes.