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:

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

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}yRightarrow 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 {egin{matrix}{mathcal {R}}^{2}={mathcal {R}} imes {mathcal {R}}:={(x,y)|exists z:x{mathcal {R}}zland z{mathcal {R}}y}\dots \{mathcal {R}}^{n+1}={mathcal {R}} imes {mathcal {R}}^{n}end{matrix}}}$

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

(3)${displaystyle {mathcal {R}}_{CT}=igcup _{iin mathbb {N} }{mathcal {R}}^{i}}$

${displaystyle B_{mathcal {R}}=[b_{ij}]quad land quad b_{ij}={egin{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: