Transitive closure

ウィキペディア

推移閉包

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/24 19:21 UTC 版)

推移閉包（すいいへいほう、英: transitive closure）は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係 R⁺ を意味する。

たとえば X を人間（生死は問わない）の集合とし、「x は y の親である」という関係 xRy を考えると、その推移閉包は「x は y の先祖である」という関係 xR⁺y である。あるいは X を空港の集合とし、「x から y への直通便が存在する」という関係 xRy を考えると、その推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係 xR⁺y である。

解説

任意の関係 R について、R の推移閉包は常に存在する。これを示すため、任意の推移関係の族の共通部分が推移的であることに注意する。さらに少なくとも1つの自明な R を含む推移関係 X × X が存在する。R の推移閉包は、R を含む全ての推移関係の共通部分である。

推移閉包はより構成的に次のようにも記述できる。X 上の関係 R⁺ を xR⁺y となるのが X の要素の有限列 (x₀, …, x_n) （ただし n ≥ 1）が存在し、2条件

• x = x₀, y = x_n かつ
• x₀Rx₁, x₁Rx₂, …, x_n−1Rx_n

を満たすことと定義する。これは関係の合成を Rⁿ のように表すことにすれば、端的に

$R^{+}=\bigcup _{n\geq 1}R^{n}$