Clausura transitiva

La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación ${\displaystyle R\,}$ se denotada ${\displaystyle CT(R)\,}$. En otras palabras, ${\displaystyle CT(R)\,}$ es la relación binaria que verifica:

1. ${\displaystyle R\subseteq CT(R)}$
2. ${\displaystyle CT(R)\,}$ es transitiva
3. Si ${\displaystyle R'\,}$ es una relación transitiva tal que ${\displaystyle R\subseteq R'}$, entonces ${\displaystyle CT(R)\subseteq R'}$

Nótese que si ${\displaystyle R\,}$ es transitiva, entonces ${\displaystyle CT(R)=R\,}$. Dada cualquier relación siempre existe su clausura transitiva.

Existencia y descripción

La clausura transitiva de una relación binaria siempre existe, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Además la clausura transitiva que denotaremos aquí mediante ${\displaystyle {\mathcal {R}}_{CT}}$ admite una caracterización muy sencilla:

(1)${\displaystyle x{\mathcal {R}}_{CT}y\Rightarrow \quad \exists z_{1}\dots \exists z_{n}:x{\mathcal {R}}z_{1}\land \dots \land z_{n}{\mathcal {R}}y}$

Definiendo las potencias de ${\displaystyle {\mathcal {R}}}$ inductivamente:

(2)${\displaystyle {\begin{matrix}{\mathcal {R}}^{2}={\mathcal {R}}\times {\mathcal {R}}:=\{(x,y)|\exists z:x{\mathcal {R}}z\land z{\mathcal {R}}y\}\\\dots \\{\mathcal {R}}^{n+1}={\mathcal {R}}\times {\mathcal {R}}^{n}\end{matrix}}}$

La clausura transitiva se puede caracterizar como la unión generalizada:

(3)${\displaystyle {\mathcal {R}}_{CT}=\bigcup _{i\in \mathbb {N} }{\mathcal {R}}^{i}}$

Cómo calcularla algorítmicamente

• Si una relación ${\displaystyle {\mathcal {R}}}$ ya es una relación transitiva, entonces es su propia clausura transitiva.
• En cambio, si ${\displaystyle {\mathcal {R}}}$ no es transitiva, su clausura transitiva puede hallarse usando la representación de la relación como matriz booleana. Dada la relación ${\displaystyle {\mathcal {R}}}$ sobre un conjunto de n elementos ${\displaystyle \{a_{1},\dots ,a_{n}\}}$, la matriz booleana asociada a la relación viene dada por:

${\displaystyle B_{\mathcal {R}}=[b_{ij}]\quad \land \quad b_{ij}={\begin{cases}1&{\mbox{si}}\ a_{i}{\mathcal {R}}a_{j}\\0&{\mbox{si}}\ \lnot a_{i}{\mathcal {R}}a_{j}\end{cases}}}$

Una vez calculada se examina en qué caso de los siguientes estamos:

1. Se encuentran las potencias de ${\displaystyle B_{\mathcal {R}}}$ (${\displaystyle B_{\mathcal {R}}^{2}}$, ${\displaystyle B_{\mathcal {R}}^{3}}$,..., ${\displaystyle B_{\mathcal {R}}^{k}}$, etc.)
2. Si ${\displaystyle B_{\mathcal {R}}^{k}}$ es la relación total o producto cartesiano, no se buscan más potencias y esa es la Clausura Transitiva.
3. Si ${\displaystyle B_{\mathcal {R}}^{k}}$ es la matriz nula, entonces la ${\displaystyle CT({\mathcal {R}})}$ es la unión generalizada (3).
4. Si ${\displaystyle B_{\mathcal {R}}^{k}}$ es igual a alguna potencia anterior, entonces no se buscan más potencias y la ${\displaystyle CT({\mathcal {R}})}$ es idéntica que en el punto anterior.

Véase también

• Clausura reflexiva
• Clausura simétrica