関係の合成

数学における二項関係の合成(ごうせい、英: composition)は、与えられた二つの関係 R, S から新たな関係 S ∘ R を作り出す操作である。この最もよく知られた特別の場合が写像の合成である。

R ⊆ X × Y, S ⊆ Y × Z を二つの関係とすると、それらの合成 S ∘ R は

${\displaystyle S\circ R=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}\subseteq X\times Z}${\displaystyle S\circ R=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}\subseteq X\times Z}

という関係として与えられる。これは、S ∘ R ⊆ X × Z は

(x, z) ∈ S ∘ R ⇔ x R y S z となる y ∈ Y が存在する

というようにも言うことができる。文献によってはここで定義した関係 S ∘ R のことを R ∘ S と書くような分野もあるが、ここでは(関係の合成の特別の場合である)写像の合成の通常の表記法に合わせた。場合によっては、適用順序が左からか右からかを区別するために必要ならば ∘_l, ∘_r と明示的に書き分けるものもある^[1] 。

計算機科学ではもっと別なZ記法も用いられる。Z記法では、通常の右からの合成には ∘ を使うが、左からの合成には ⨾ を用いる(これはコードポイントU+2A3Eの太いセミコロンである^[2] )^[3] 。このセミコロンを用いた記法は、主に計算機科学の文脈での圏論における射の合成の記法と一致する。

二項関係 R ⊆ X × Y はしばしば、集合を対象とする関係の圏 Rel における射 R: X → Y と見做される。圏 Rel における射の合成は、先ほど定義した関係の合成によって与えられる。集合の圏 Set は対象の類を同じくするが射が少ない Rel の部分圏である。この例の一般化が寓意 (英語版)の理論である。

• 関係の合成は結合的である。
• S ∘ R の逆関係は (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹ である。これにより、一つの集合上の二項関係全体は対合半群となる。
• 函数的関係の合成はふたたび函数的である。
• R および S が単射ならば合成 S ∘ R も単射である。逆に合成が単射ならば必ず R は単射となる。
• R および S が全射ならば合成 S ∘ R も全射である。逆に合成が全射ならば必ず S が全射となる。
• 集合 X 上の二項関係(つまり X から X への関係)全体の成す集合に(右または左からの)関係の合成を考えたものは、零元付きモノイドを成す。単位元は X 上の恒等関係、零元は空関係である。

二項関係ではなく一般の多項関係に対しても定義される別な種類の関係の合成として、関係代数の演算である結合 (join) がある。結合を使えば、二項関係の通常の合成は、三項関係の結合をとったものに中間成分を取り除く射影を施すことによって得られるものと一致する。

• 二項関係
• Demonic composition
• 写像の合成
• Join (SQL)

• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, ISBN 3-11-015248-7.

• 数理論理学
• 数学的関係
• 数学に関する記事

• 英語版ウィキペディアからの翻訳を必要とする記事
• ISBNマジックリンクを使用しているページ