関係の合成のソースを表示

{{Expand English|Composition of relations|date=2024年5月}}
[[数学]]における[[二項関係]]の'''合成'''（ごうせい、{{lang-en-short|composition}}）は、与えられた二つの関係 ''R'', ''S'' から新たな関係 ''S'' ∘ ''R'' を作り出す操作である。この最もよく知られた特別の場合が[[写像の合成]]である。

== 定義 ==
''R'' &sube; ''X'' &times; ''Y'', ''S'' &sube; ''Y'' &times; ''Z'' を二つの関係とすると、それらの合成 ''S'' ∘ ''R'' は
:<math>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</math>

という関係として与えられる。これは、''S'' ∘ ''R'' &sube; ''X'' &times; ''Z'' は
: (''x'', ''z'') &isin; ''S'' ∘ ''R'' &hArr; ''x'' ''R'' ''y'' ''S'' ''z'' となる ''y'' &isin; ''Y'' が存在する

というようにも言うことができる。文献によってはここで定義した関係 ''S'' ∘ ''R'' のことを ''R'' ∘ ''S'' と書くような分野もあるが、ここでは（関係の合成の特別の場合である）[[写像の合成]]の通常の表記法に合わせた。場合によっては、適用順序が左からか右からかを区別するために必要ならば ∘<sub>''l''</sub>, ∘<sub>''r''</sub> と明示的に書き分けるものもある<ref>Kilp, Knauer & Mikhalev, p. 7</ref>。

計算機科学ではもっと別な[[Z記法]]も用いられる。Z記法では、通常の右からの合成には ∘ を使うが、左からの合成には &#x2A3E; を用いる（これはコードポイント[[ユニコード|U+2A3E]]の太いセミコロンである<ref>http://www.fileformat.info/info/unicode/char/2a3e/index.htm</ref>）<ref>U+2A3E のセミコロンは、欧文などの地の文の約物としてのセミコロンと（フォントデザインによっては小さいフォントサイズなどでは）紛らわしい場合もあるので、大文字版 &#x2A1F; ([http://www.fileformat.info/info/unicode/char/2a1f/index.htm U+2A1F]) を用意しているフォントもある。非ユニコードな[[LaTeX]]では <code>stmaryrd</code> パッケージが用意している <code>\fatsemi</code> コマンドを使えば利用できる。</ref>。このセミコロンを用いた記法は、主に計算機科学の文脈での[[圏論]]における射の合成の記法と一致する。

二項関係 ''R'' &sube; ''X'' &times; ''Y'' はしばしば、集合を対象とする[[関係の圏]] '''Rel''' における射 ''R'': ''X'' &rarr; ''Y'' と見做される。圏 '''Rel''' における射の合成は、先ほど定義した関係の合成によって与えられる。[[集合の圏]] '''Set''' は対象の類を同じくするが射が少ない '''Rel''' の部分圏である。この例の一般化が{{仮リンク|寓意 (圏論)|en|allegory (category theory)|label=寓意}}の理論である。

== 性質 ==

* 関係の合成は[[結合法則|結合的]]である。
* ''S'' ∘ ''R'' の[[逆関係]]は (''S'' ∘ ''R'')<sup>&minus;1</sup> = ''R''<sup>&minus;1</sup> ∘ ''S''<sup>&minus;1</sup> である。これにより、一つの集合上の二項関係全体は[[対合半群]]となる。
* [[部分写像|函数的関係]]の合成はふたたび函数的である。
* ''R'' および ''S'' が[[単射]]ならば合成 ''S'' ∘ ''R'' も単射である。逆に合成が単射ならば必ず ''R'' は単射となる。
* ''R'' および ''S'' が[[全射]]ならば合成 ''S'' ∘ ''R'' も全射である。逆に合成が全射ならば必ず ''S'' が全射となる。
* 集合 ''X'' 上の二項関係（つまり ''X'' から ''X'' への関係）全体の成す集合に（右または左からの）関係の合成を考えたものは、零元付き[[モノイド]]を成す。[[単位元]]は ''X'' 上の恒等関係、[[吸収元|零元]]は空関係である。

== 関係の結合 ==
{{main|結合 (リレーショナル代数)}}

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

==関連項目 ==
* [[二項関係]]
* [[Demonic composition]]
* [[写像の合成]]
* [[Join (SQL)]]

== 注釈 ==
{{reflist}}

== 参考文献 ==
*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.

{{DEFAULTSORT:かんけいのこうせい}}
[[Category:数理論理学]]
[[Category:数学的関係]]
[[Category:数学に関する記事]]