関係の構成

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

叔父という言葉は複合関係を示します。つまり、ある人が叔父であるためには、その人は親の兄弟でなければなりません。代数論理学では、叔父 ( ) の関係は、「兄弟である」( ) と「親である」( ) の関係の合成であると言われています。${\displaystyle xUz}$${\displaystyle xBy}$${\displaystyle yPz}$$${\displaystyle U=BP\quad {\text{ は次と同等: }}\quad xUz{\text{ }}\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{ }}y\in Y{\text{ が存在し、}}(x,y)\in R{\text{ かつ }}(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]しかし、小円は}関数の合成を表すために広く使用されており、テキストシーケンスと演算シーケンスが逆になっています。小円は、 Graphs and Relations ^{[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 では、オブジェクトは集合、射は二項関係、射の合成は上で定義した関係の合成とまったく同じです。集合と関数のカテゴリSetは、写像 が関数であるのサブカテゴリです。 ${\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.}$
• 集合 上の二項関係の集合（つまり、 からへの関係）は、（左または右の）関係合成とともに、ゼロを持つモノイドを形成します。ここで、 上の恒等写像は中立元であり、空集合はゼロ元です。${\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つの特定の国が言語を共有しているかどうかという質問は、次のように答えることができます。${\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つの同値関係は別の同値関係から得られます。つまり、第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 つの 2 項関係の通常の合成は、それらの結合を取って 3 項関係にし、その後に中間の要素を削除する射影を実行することで得られます。たとえば、クエリ言語SQLには、結合 (SQL)という演算があります。 ${\displaystyle n}$${\displaystyle n\geq 2,}$

• 悪魔的な構成
• 友人の友人 – 共通の友人のおかげで存在する人間関係

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