Tranzitivní uzávěr

Tranzitivní uzávěr binární relace R je definován jako nejmenší (z hlediska množinové inkluze) tranzitivní nadmnožina R.

Matematicky vyjádřeno, pro tranzitivní uzávěr R' binární relace R platí:
$R'=\cap_M[(R \subseteq M) \and ( \forall a,b,c)(([a,b] \isin M \and [b,c] \isin M) \implies ([a,c] \isin M))]$

Příklad

Máme určit tranzitivní uzávěr relace R:

$R=\{(1,2),(2,3)\}$

Protože existuje relace mezi 1 a 2 a mezi 2 a 3, aby byla relace tranzitivní, je třeba relaci rozšířit o $(1,3)$. Tranzitivní uzávěr tak bude:

$R'=\{(1,2),(2,3),(1,3)\}$