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 se denotada . En otras palabras, es la relación binaria que verifica:

  1. es transitiva
  2. Si es una relación transitiva tal que , entonces

Nótese que si es transitiva, entonces . Dada cualquier relación siempre existe su clausura transitiva.

Existencia y descripciónEditar

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   admite una caracterización muy sencilla:

(1) 

Definiendo las potencias de   inductivamente:

(2) 

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

(3) 

Cómo calcularla algorítmicamenteEditar

  • Si una relación   ya es una relación transitiva, entonces es su propia clausura transitiva.
  • En cambio, si   no es transitiva, su clausura transitiva puede hallarse usando la representación de la relación como matriz booleana. Dada la relación   sobre un conjunto de n elementos  , la matriz booleana asociada a la relación viene dada por:

 

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

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

Véase tambiénEditar