関係の合成

Mathematical operation

二項関係の数学において、関係の合成とは、与えられた2つの二項関係RとSから新しい二項関係R  ; Sを形成することである。関係の計算においては、関係の合成は相対乗算^[1]と呼ばれ、その結果は相対積^[2]と呼ばれる。^:40関数合成は、関係の合成の特殊なケースであり、関係のすべてが関数となる。

「叔父」という語は複合的な関係を表します。つまり、ある人が「叔父」であるためには、その人は親の兄弟でなければなりません。代数論理学では、「叔父」（）という関係は、「兄弟である」（）と「親である」（）という関係の合成であると言われています。 ${\displaystyle xUz}$ ${\displaystyle xBy}$ ${\displaystyle yPz}$ $${\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}$$

オーガスタス・ド・モルガン^[3]に始まり、三段論法による伝統的な推論形式は関係論理式とその構成に包含されてきました。^[4]

意味

とが2つの二項関係である場合、それらの合成は関係 ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle S\subseteq Y\times Z}$ ${\displaystyle R\mathbin {;} S}$ $${\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.}$$

言い換えれば、は、 （つまり、 ）となるような要素が存在する場合にのみ、という規則によって定義されます。 ^{[5] : 13} ${\displaystyle R\mathbin {;} S\subseteq X\times Z}$ ${\displaystyle (x,z)\in R\mathbin {;} S}$ ${\displaystyle y\in Y}$ ${\displaystyle x\,R\,y\,S\,z}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle (y,z)\in S}$

表記上のバリエーション

関係の合成のための挿入記法としてのセミコロンは、 1895年のエルンスト・シュレーダーの教科書にまで遡ります。^[6]ギュンター・シュミットは、特に『関係数学』（2011年）で、セミコロンの使用を刷新しました。 ^{[2] : 40  [7]}セミコロンの使用は、カテゴリー理論（主にコンピュータ科学者によって）で使用される関数合成の記法と一致しており、^[8]言語の動的意味論における動的接続詞の記法とも一致しています。^[9]

ジョン・M・ハウイーは、関係の半群を考察した著書^[10]の中で、関係の合成を表すインフィックス表記に小円を用いている。しかし、小円は関数の合成を表すために広く用いられており、これはテキストの順序と演算の順序を逆にする。小円はグラフと関係^{[5]の導入部18}で使用されていたが、後に並置表記（インフィックス表記なし）に置き換えられた。並置表記は代数において乗算を表すためによく用いられるため、相対的な乗算を表すこともできる。 ${\displaystyle (R\circ S)}$ ${\displaystyle g(f(x))=(g\circ f)(x)}$ ${\displaystyle (RS)}$

さらに、円記号表記では下付き文字が使用される場合があります。一部の著者^[11]は、左関係と右関係のどちらが最初に適用されるかに応じて、必要に応じて明示的に と を記述することを好みます。コンピュータサイエンスで見られるさらなるバリエーションとして、 Z表記があります。:は従来の（右）構成を表すために使用され、左構成はファットセミコロンで表されます。Unicodeの記号は ⨾ と ⨟ です。^{[12] [13]} ${\displaystyle \circ _{l}}$ ${\displaystyle \circ _{r}}$ ${\displaystyle \circ }$

数学的一般化

二項関係は、カテゴリにおける射です。Rel では、対象は集合、射は二項関係 、射の合成はまさに上で定義した関係の合成です。集合と関数のカテゴリ集合 は、写像 が関数 であるのサブカテゴリです。 ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle R:X\to Y}$ ${\displaystyle {\mathsf {Rel}}}$ ${\displaystyle {\mathsf {Rel}}}$ ${\displaystyle X\to Y}$ ${\displaystyle f:X\to Y}$

正則カテゴリ が与えられると、その内部関係のカテゴリはと同じオブジェクトを持ちます が、今度は 射がの部分オブジェクトによって与えられます。^[14] 正式には、これらはと の間の共同モニック範囲です。内部関係のカテゴリは寓話です。特に です。体(またはより一般的には主イデアル領域) が与えられると、上の行列の内部関係のカテゴリは、線型部分空間の射を持ちます。有限体上の線型関係のカテゴリは、スカラーを法とする位相フリー量子ビットZX 計算と同型です。 ${\displaystyle \mathbb {X} }$ ${\displaystyle {\mathsf {Rel}}(\mathbb {X} )}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X\to Y}$ ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k)),}$ ${\displaystyle n\to m}$ ${\displaystyle R\subseteq k^{n}\oplus k^{m}}$ ${\displaystyle \mathbb {F} _{2}}$

プロパティ

• 関係の合成は結合的である: ${\displaystyle R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}$
• の逆関係は です。この特性により、 上のすべての二項関係の集合は反転を持つ半群になります。 ${\displaystyle R\mathbin {;} S}$ ${\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}$
• （部分）関数（つまり関数関係）の合成もまた、（部分）関数です。
• と が単射ならばは単射であり、逆に の単射性のみが示される。 ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle R.}$
• とが射影的であれば は射影的であり、逆に の射影性のみが示される。 ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle S.}$
• 集合 上の二項関係の集合（つまり、 から の関係）は、（左または右の）関係合成とともに、 0 を持つモノイドを形成します。ここで、 上の恒等写像は中立元であり、空集合は零元です。 ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

行列による構成

有限二項関係は論理行列によって表される。これらの行列の要素は、比較対象となる行と列において、表現される関係が偽か真かによって、0または1となる。このような行列を扱うには、とを用いたブール演算が必要となる。2つの論理行列の行列積の要素が1になるのは、乗算された行と列が対応する1を持つ場合のみである。したがって、関係の合成の論理行列は、合成の要素を表す行列の行列積を計算することで求められる。「行列は、仮説的三段論法やソリテスによって伝統的に導き出された結論を計算する方法である。」^[15] ${\displaystyle 1+1=1}$ ${\displaystyle 1\times 1=1.}$

異質な関係

異種関係、すなわちと が異なる集合である関係を考える。このとき、とその逆の関係の合成を用いると、 （ 上）および（ 上）の同種関係が成立する。 ${\displaystyle R\subseteq A\times B;}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$ ${\displaystyle R^{\textsf {T}},}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle A}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle B}$

すべてに対して、 となる関係が存在する場合（つまり、は（左）全関係）、 すべてに対してとなる関係が存在する場合、 は反射関係、または となります。ここで、 I は恒等関係です。同様に、が射影関係である場合、 この場合、二機能関係に対しては 、反対の包含が発生します。 ${\displaystyle x\in A}$ ${\displaystyle y\in B,}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x,xRR^{\textsf {T}}x}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle \mathrm {I} \subseteq RR^{\textsf {T}}}$ ${\displaystyle \{(x,x):x\in A\}.}$ ${\displaystyle R}$ $${\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}$$ ${\displaystyle R\subseteq RR^{\textsf {T}}R.}$

この合成は、フェラー型の関係を区別するために使用され、 ${\displaystyle {\bar {R}}^{\textsf {T}}R}$ ${\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}$

例

が の国語である場合、{ フランス、ドイツ、イタリア、スイス } と{ フランス語、ドイツ語、イタリア語 }の関係が で表されます。と はどちらも有限なので、行 (上から下) と列 (左から右) がアルファベット順に並んでいると仮定すると、 は論理行列で表すことができます。 ${\displaystyle A=}$ ${\displaystyle B=}$ ${\displaystyle R}$ ${\displaystyle aRb}$ ${\displaystyle b}$ ${\displaystyle a.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$ $${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$$

逆の関係は 転置行列に対応し、関係合成は、和を論理和で実装した場合の行列積に対応する。行列はすべての位置に1を含むが、逆行列積は次のように計算される：この行列は対称であり、上の同次関係を表す。 ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle R^{\textsf {T}};R}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle 3\times 3}$ ${\displaystyle R^{\textsf {T}}R}$ $${\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$$ ${\displaystyle A.}$

同様に、は普遍関係であり、したがって任意の2つの言語は、それらが話されている国（実際にはスイス）を共有している。逆に、2つの特定の国が1つの言語を共有しているかどうかという問いは、 ${\displaystyle R^{\textsf {T}}\,;R}$ ${\displaystyle B,}$ ${\displaystyle R\,;R^{\textsf {T}}.}$

シュレーダールール

与えられた集合に対して、上のすべての二項関係の集合は包含関係によって順序付けられたブール格子を形成する。補集合は包含関係を逆にすることを思い出してほしい。関係の計算^[16] では、集合の補集合をオーバーバーで表すのが一般的である。 ${\displaystyle V,}$ ${\displaystyle V}$ ${\displaystyle (\subseteq ).}$ ${\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}$ ${\displaystyle {\bar {A}}=A^{\complement }.}$

が二項関係である場合、 は逆関係（転置とも呼ばれる）を表すものとする。シュレーダーの規則は、次のように定義される。言葉で言えば、ある同値関係は別の同値関係から得られる。すなわち、第1または第2の因子を選択して転置し、他の2つの関係を補集合として置換する。^{[5] : 15–19} ${\displaystyle S}$ ${\displaystyle S^{\textsf {T}}}$ $${\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}$$

この関係の合成の包含の変換はエルンスト・シュレーダーによって詳細に説明されたが、実際にはオーガスタス・ド・モルガンが1860年に初めてこの変換を定理Kとして明確に表現した。^[4]彼は^[17] $${\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}$$

シュレーダー規則と相補関係を用いると、次のような関係包含における 未知の関係を解くことができます。例えば、シュレーダー規則と相補関係を用いると、 が得られ、これはによるの左残差と呼ばれます。 ${\displaystyle X}$ $${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$$ ${\displaystyle RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$ ${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$ ${\displaystyle S}$ ${\displaystyle R}$

商

関係の合成が乗算の一種であり、結果として積が得られるのと同様に、いくつかの演算は除算に相当し、商を生成します。ここでは、左残差、右残差、対称商の3つの商を示します。2つの関係の左残差は、それらが同じ定義域（ソース）を持つと仮定して定義され、右残差は、同じ余剰領域（値域、ターゲット）を持つと仮定します。対称商は、2つの関係が定義域と余剰領域を共有していると仮定します。

定義:

• 残差: ${\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}$
• 右残差: ${\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}$
• 対称商: ${\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}$

シュレーダーの規則を用いると、は次と等価である。したがって、左残差は次を満たす最大の関係である。同様に、包含は次と等価であり、右残差は次を満たす最大の関係である。^{[2] : 43–6} ${\displaystyle AX\subseteq B}$ ${\displaystyle X\subseteq A\backslash B.}$ ${\displaystyle AX\subseteq B.}$ ${\displaystyle YC\subseteq D}$ ${\displaystyle Y\subseteq D/C,}$ ${\displaystyle YC\subseteq D.}$

数独で残差の論理を練習することができます。^{[さらに説明が必要]}

結合：別の構成形式

フォーク演算子は、2つの関係とを融合するために導入されました。構築は投影に依存し、関係として理解されます。つまり、逆の関係があり、次に ${\displaystyle (<)}$ ${\displaystyle c:H\to A}$ ${\displaystyle d:H\to B}$ ${\displaystyle c\,(<)\,d:H\to A\times B.}$ ${\displaystyle a:A\times B\to A}$ ${\displaystyle b:A\times B\to B,}$ ${\displaystyle a^{\textsf {T}}}$ ${\displaystyle b^{\textsf {T}}.}$のフォークは^[18]で与えられる。 ${\displaystyle c}$ ${\displaystyle d}$ $${\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}$$

関係の合成のもう一つの形式は、一般的な- 項関係に適用される関係代数の結合演算です。ここで定義される2つの二項関係の通常の合成は、それらの結合をとって三項関係とし、その後に中間の要素を削除する射影を付加することで得られます。例えば、クエリ言語SQLには、結合 (SQL) という演算があります。 ${\displaystyle n}$ ${\displaystyle n\geq 2,}$

参照

• 悪魔の構成 – 数学的演算
• 友人の友人 – 共通の友人がいるからこそ生まれる人間関係

注記

1. Bjarni Jónsson (1984)「二項関係の最大代数」、群論への貢献、KI Appel編集、アメリカ数学会 ISBN 978-0-8218-5035-0
2. Gunther Schmidt (2011)関係数学、数学とその応用百科事典、第132巻、ケンブリッジ大学出版局 ISBN 978-0-521-76268-7
3. A. ド・モーガン (1860)「三段論法について：IVおよび関係の論理について」
4. Daniel D. Merrill (1990) Augustus De Morgan and the Logic of Relations、121ページ、Kluwer Academic ISBN 9789400920477
5. グンター・シュミット＆トーマス・シュトローライン（1993）『関係とグラフ』シュプリンガー・ブックス
6. エルンスト・シュレーダー(1895) 代数と相対論理
7. ポール・テイラー (1999). 『数学の実践的基礎』ケンブリッジ大学出版局. p. 24. ISBN 978-0-521-63107-5。この書籍の無料 HTML 版は http://www.cs.man.ac.uk/~pt/Practical_Foundations/ から入手できます。
8. Michael Barr & Charles Wells (1998) コンピュータ科学者のためのカテゴリー理論 Archived 2016-03-04 at the Wayback Machine、6ページ、McGill Universityより
9. リック・ナウエン他 (2016) 動的意味論 §2.2、スタンフォード哲学百科事典より
10. John M. Howie (1995) 『半群論の基礎』 16ページ、LMSモノグラフ#12、Clarendon Press ISBN 0-19-851194-9
11. キルプ、クナウアー、ミハレフ、p. 7
12. ISO/IEC 13568:2002(E)、p. 23
13. FileFormat.info の U+2A3E と U+2A1F を参照
14. "internal relations". nlab . 2023年9月26日閲覧。
15. アーヴィング・コピロウィッシュ(1948年12月)「関係計算の行列展開」、Journal of Symbolic Logic 13(4): 193–203 Jstorリンク、203ページからの引用
16. ヴォーン・プラット『関係微積分の起源』スタンフォード大学
17. ド・モルガンは、反対称を小文字で、変換をM ⁻¹で、包含を)で表したので、彼の表記法は ${\displaystyle nM^{-1}))\ l.}$
18. Gunther SchmidtとMichael Winter（2018）：リレーショナルトポロジー、26ページ、 Lecture Notes in Mathematics vol. 2208、 Springer books、 ISBN 978-3-319-74451-3

参考文献

• M. Kilp、U. Knauer、AV Mikhalev (2000)リース積およびグラフへの応用を伴うモノイド、アクトおよびカテゴリー、De Gruyter Expositions in Mathematics vol. 29、ウォルター・デ・グリュイテル、ISBN 3-11-015248-7。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Composition_of_relations&oldid=1325946985"