Rの推移閉包とは、Rを含む最小の推移的関係R^+のこと

例

S=\{a,b,c\}があり、関係R=\{(a,b), (b,c)\}があるとする

この時、Rは推移的でない

なぜなら、aRb,bRcがあるのに、aRcがないから

ここで、それら加えたR^+ = \{(a,b),(b,c),(a,c)\}を考えた時、

これがRの(最小の)推移閉包となる

推移閉包を二階述語論理に加えると、クラスPSPACEが得られる。

そうなんだ