関係の構成

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

「叔父」という言葉は複合関係を示します。人が叔父であるためには、その人は親の兄弟でなければなりません。代数論理では、「～の叔父である」という関係は、${\displaystyle xUz}$) は「～の兄弟である」という関係の合成です (${\displaystyle xBy}$）そして「～の親である」${\displaystyle yPz}$) $${\displaystyle U=B\mathbin {;} P\quad {\text{ は、 }}\quad xUz{\text{ は }}\exists y.\ xBy{\text{ かつ }}yPz の場合に限り同値である。}$$

オーガスタス・ド・モルガン^{[ 3 ]}以来、三段論法による伝統的な推論形式は、関係論理表現とその合成に吸収されてきた^{[ 4 ] 。}

もし${\displaystyle R\subseteq X\times Y}$そして${\displaystyle S\subseteq Y\times Z}$2 つの二項関係がある場合、それらの合成${\displaystyle R\mathbin {;} S}$関係 $${\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ (x,y)\in R かつ (y,z)\in S となるような y\in Y が存在する。}$$

言い換えると、${\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}$). ^{[ 5 ]： 13}

• 関係の合成は結合法則を満たす。${\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 S}$また、合計も${\displaystyle {\text{range}}(R)}$^{[ 15 ]}は、${\displaystyle R.}$
• もし${\displaystyle R}$そして${\displaystyle S}$が全射である場合、${\displaystyle R\mathbin {;} S}$は全射であり、逆に は全射であることを意味する。${\displaystyle S.}$
• 集合上の二項関係の集合${\displaystyle X}$（つまり、${\displaystyle X}$に${\displaystyle X}$) と (左または右) 関係合成を組み合わせると、ゼロを持つモノイドが形成され、そのモノイド上の恒等写像はゼロになります。${\displaystyle X}$は中立要素であり、空集合は零要素である。

有限の二項関係は論理行列で表されます。これらの行列のエントリは、比較対象に対応する行と列について、表される関係が偽か真かに応じて、0または1になります。このような行列を扱うには、ブール演算と${\displaystyle 1+1=1}$そして$1×1=1。$2 つの論理行列の行列積のエントリは次のようになります。${\displaystyle 1}$行と列の乗算が対応する値を持つ場合に限り、${\displaystyle 1}$したがって、関係の合成の論理行列は、合成の要素を表す行列の行列積を計算することによって見つけることができます。「行列は、従来仮言三段論法とソリテスによって導き出されてきた結論を計算する方法を構成する。」^{[ 16 ]}

異質な関係を考える${\displaystyle R\subseteq A\times B}$つまり、${\displaystyle A}$そして${\displaystyle B}$これらは異なる集合である可能性があります。次に、関係の合成を使用します。${\displaystyle R}$その逆${\displaystyle R^{\textsf {T}},}$同質な関係が存在する${\displaystyle R\mathbin {;} R^{\textsf {T}}}$（の上${\displaystyle A}$） そして${\displaystyle R^{\textsf {T}}\mathbin {;} R}$（の上${\displaystyle B}$)

すべての場合${\displaystyle x\in A}$いくつか存在する${\displaystyle y\in B,}$そのため${\displaystyle xRy}$（つまり、${\displaystyle R}$が（左）全関係である場合、すべての${\displaystyle x}$、${\displaystyle xR\mathbin {;} R^{\textsf {T}}x}$となることによって${\displaystyle R\mathbin {;} R^{\textsf {T}}}$反射関係または${\displaystyle \mathrm {I} \subseteq R\mathbin {;} R^{\textsf {T}}}$ここで、Iは恒等関係である。${\displaystyle \{(x,x):x\in A\}.}$同様に、${\displaystyle R}$は全射関係で ある$${\displaystyle R^{\textsf {T}}\mathbin {;} R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}$$ この場合${\displaystyle R\subseteq R\mathbin {;} R^{\textsf {T}}\mathbin {;} R.}$二関数関係の場合は、これとは逆の包含関係が生じる。

構成${\displaystyle {\bar {R}}^{\textsf {T}}\mathbin {;} R}$は、以下の条件を満たすフェレール型の関係を区別するために使用されます。${\displaystyle R\mathbin {;} {\bar {R}}^{\textsf {T}}\mathbin {;} R=R.}$

与えられた集合に対して${\displaystyle V,}$すべての二項関係のコレクション${\displaystyle V}$包含関係によって順序付けられたブール格子を形成する${\displaystyle (\subseteq ).}$補文は包含関係を逆転させることを思い出してください。 ${\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}$関係の計算^{[ 17 ]} では、集合の補集合を上線で表すのが一般的です。${\displaystyle {\bar {A}}=A^{\complement }.}$

もし${\displaystyle S}$は二項関係である。${\displaystyle S^{\textsf {T}}}$は逆関係、転置とも呼ばれる関係を表す。するとシュレーダー規則は次のようになる。 $${\displaystyle Q\mathbin {;} R\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}\mathbin {;} {\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}\mathbin {;} R^{\textsf {T}}\subseteq {\bar {Q}}.}$$ 言葉で言えば、ある等価関係から別の等価関係を得ることができる。まず、最初の因子または2番目の因子を選択して転置し、次に残りの2つの関係を補数にしてそれらを入れ替える。^{[ 5 ]： 15-19}

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

シュレーダーの規則と補元を用いることで、未知の関係式を解くことができる。${\displaystyle X}$関係する包含物としては $${\displaystyle R\mathbin {;} X\subseteq S\quad {\text{and}}\quad X\mathbin {;} R\subseteq S.}$$ 例えば、シュレーダーの法則によれば${\displaystyle R\mathbin {;} X\subseteq S{\text{ implies }}R^{\textsf {T}}\mathbin {;} {\bar {S}}\subseteq {\bar {X}},}$そして補数は${\displaystyle X\subseteq {\overline {R^{\textsf {T}}\mathbin {;} {\bar {S}}}},}$これは、${\displaystyle S}$による${\displaystyle R}$。

関係の合成が積となる乗算の一種であるのと同様に、除算に類似した演算によって商が得られる場合もあります。ここでは、左残差、右残差、対称商の3つの商を示します。2つの関係の左残差は、それらが同じ定義域（ソース）を持つと仮定して定義され、右残差は同じ値域（値域、ターゲット）を持つと仮定して定義されます。対称商は、2つの関係が定義域と値域の両方を共有すると仮定して定義されます。

定義:

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

シュレーダーの法則を用いると、${\displaystyle A\mathbin {;} X\subseteq B}$と同等${\displaystyle X\subseteq A\backslash B.}$したがって、左残差は、以下の条件を満たす最大の関係である。${\displaystyle A\mathbin {;} X\subseteq B.}$同様に、包含${\displaystyle Y\mathbin {;} C\subseteq D}$と同等${\displaystyle Y\subseteq D/C,}$そして右残差は、以下の条件を満たす最大の関係である。${\displaystyle Y\mathbin {;} C\subseteq D.}$^{[ 2 ]： 43-6}

数独を使って残差の論理を練習することができる。

フォークリフトオペレーター${\displaystyle (<)}$2つの関係を融合するために導入された${\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}}.}$それからフォーク​${\displaystyle c}$そして${\displaystyle d}$^{[ 20 ]}で与えられる$${\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}$$

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

• 悪魔的な構成– 数学的演算 
• 友人の友人– 共通の友人を介して存在する人間関係 

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