二項関係

数学において、二項関係は、定義域と呼ばれるある集合のいくつかの要素を、値域と呼ばれる別の集合（同じ集合である場合もある）のいくつかの要素と関連付けます。^{[ 1 ]}正確には、集合上の二項関係は、${\displaystyle X}$そして${\displaystyle Y}$順序対の集合です ${\displaystyle (x,y)}$、 どこ${\displaystyle x}$は${\displaystyle X}$そして${\displaystyle y}$は${\displaystyle Y}$[ ^{2 ]それは関係の共通概念を}符号化している：要素${\displaystyle x}$要素に関連しています${\displaystyle y}$ペアが${\displaystyle (x,y)}$二項関係を定義する順序対の集合に属する。

二項関係の一例として、素数の集合における「割り切れる」関係が挙げられる。${\displaystyle \mathbb {P} }$そして整数の集合${\displaystyle \mathbb {Z} }$、各素数が${\displaystyle p}$各整数に関連しています${\displaystyle z}$それは​${\displaystyle p}$ただし、の倍数ではない整数にはならない。${\displaystyle p}$この関係では、例えば素数は${\displaystyle 2}$は、次のような数字に関連しています。${\displaystyle -4}$、${\displaystyle 0}$、${\displaystyle 6}$、${\displaystyle 10}$しかし、${\displaystyle 1}$または${\displaystyle 9}$素数と同じように${\displaystyle 3}$は${\displaystyle 0}$、${\displaystyle 6}$、 そして${\displaystyle 9}$しかし、${\displaystyle 4}$または${\displaystyle 13}$。

二項関係は、次のような場合に同次関係と呼ばれます。${\displaystyle X=Y}$二項関係は、必ずしも${\displaystyle X=Y}$。

二項関係、特に同次関係は、数学の多くの分野で、さまざまな概念をモデル化するために用いられています。これには、以下のようなものが含まれます。

• 算術では、 「より大きい」、「等しい」、「割り算」の関係を表します。
• 幾何学における「は「と一致する」関係。
• グラフ理論における「隣接している」関係。
• 線形代数における「直交する」関係。

関数は、追加の制約を満たす二項関係として定義されることがある。^{[ 3 ]}二項関係はコンピュータサイエンスでも広く使われている。

集合上の二項関係${\displaystyle X}$そして${\displaystyle Y}$デカルト積の冪集合の要素と同一視できる${\displaystyle X\times Y.}$冪集合は集合包含の束であるため（${\displaystyle \subseteq }$) 関係は、集合演算 (和集合、積集合、補集合) および集合の代数を使用して操作できます。

公理的集合論のいくつかの体系では、関係は集合の一般化であるクラスに拡張されます。この拡張は、とりわけ、ラッセルのパラドックスのような論理的矛盾に陥ることなく、集合論における「～の要素である」または「～の部分集合である」という概念をモデル化するために必要です。

二項関係は最もよく研​​究されている特殊なケースである${\displaystyle n=2}$の${\displaystyle n}$集合上の-項関係${\displaystyle X_{1},\dots ,X_{n}}$これはデカルト積の部分集合である。${\displaystyle X_{1}\times \cdots \times X_{n}.}$^{[ 2 ]}

与えられた集合${\displaystyle X}$そして${\displaystyle Y}$、デカルト積${\displaystyle X\times Y}$は次のように定義される。${\displaystyle \{(x,y)\mid x\in X{\text{ かつ }}y\in Y\},}$そしてその要素は順序対と呼ばれます。

二項関係${\displaystyle R}$セット全体${\displaystyle X}$そして${\displaystyle Y}$は、${\displaystyle X\times Y.}$^{[ 2 ] [ 4 ]}セット${\displaystyle X}$はドメイン^{[ 2 ]}または出発点集合と呼ばれます。${\displaystyle R}$、そしてセット${\displaystyle Y}$終域または目的地の集合${\displaystyle R}$セットの選択肢を指定するために${\displaystyle X}$そして${\displaystyle Y}$二項関係または対応関係を順序付き三つ組として定義する著者もいる。${\displaystyle (X,Y,G)}$、 どこ${\displaystyle G}$は、${\displaystyle X\times Y}$二項関係のグラフと呼ばれる。${\displaystyle (x,y)\in R}$読む「${\displaystyle x}$は${\displaystyle R}$-関連${\displaystyle y}$「そして、は、で表されます。${\displaystyle xRy}$[ ^{5 ] [ 6 ] [ 7 ] [ a ]}定義領域またはアクティブ領域^{[ 2 ]​}${\displaystyle R}$すべての集合です${\displaystyle x}$そのため${\displaystyle xRy}$少なくとも1つ${\displaystyle y}$定義のコドメイン、アクティブコドメイン、^{[ 2 ]}イメージまたは範囲${\displaystyle R}$すべての集合です${\displaystyle y}$そのため${\displaystyle xRy}$少なくとも1つ${\displaystyle x}$.の分野${\displaystyle R}$定義域と定義域の和集合である。^{[ 9 ] [ 10 ] [ 11 ]}

いつ${\displaystyle X=Y,}$二項関係は同質関係（または内関係）と呼ばれます。${\displaystyle X}$そして${\displaystyle Y}$異なることが許される場合、二項関係は異質関係とも呼ばれます。^{[ 12 ] [ 13 ] [ 14 ]}接頭辞heteroはギリシャ語の ἕτερος ( heteros、「他の、別の、異なる」) に由来します。

異種関係は長方形関係と呼ばれており、^{[ 14 ]}集合上の同種関係のような正方形のような対称性を持たないことを示唆している。${\displaystyle A=B.}$同質関係を超えた二項関係の発展について、研究者たちは次のように述べている。「… 理論の変種が発展し、関係を最初から異質または矩形、つまり通常は異なる集合間の関係である関係として扱うようになった。」^{[ 15 ]}

対応関係[ ^{16 ] 、} 二項関係、二項関係という用語は二項関係の同義語であるが、一部の著者はデカルト積の任意の部分集合に対して「二項関係」という用語を使用している。${\displaystyle X\times Y}$参照せずに${\displaystyle X}$そして${\displaystyle Y}$、また「対応」という用語は、${\displaystyle X}$そして${\displaystyle Y}$。

二項関係では、要素の順序が重要です。${\displaystyle x\neq y}$それから${\displaystyle yRx}$独立して真偽を判断できる${\displaystyle xRy}$。 例えば、${\displaystyle 3}$分ける${\displaystyle 9}$、 しかし${\displaystyle 9}$割り切れない${\displaystyle 3}$。

重要な二項関係の種類${\displaystyle R}$セット全体${\displaystyle X}$そして${\displaystyle Y}$以下にリストされています。

独自性特性:

• 単射^{[ 23 ]} (左一意とも呼ばれる^{[ 24 ]} ): すべての${\displaystyle x,y\in X}$そしてすべて${\displaystyle z\in Y,}$もし${\displaystyle xRz}$そして${\displaystyle yRz}$それから${\displaystyle x=y}$言い換えれば、終域のすべての要素は、最大で１つの逆像要素を持つ。このような関係では、${\displaystyle Y}$は主キーと呼ばれます${\displaystyle R}$^{[ 2 ]}例えば、図中の緑と青の二項関係は単射ですが、赤の二項関係は単射ではありません（両方を関連付けているため）。${\displaystyle -1}$そして${\displaystyle 1}$に${\displaystyle 1}$)、また黒色のもの（両方に関係するため）${\displaystyle -1}$そして${\displaystyle 1}$に${\displaystyle 0}$)
• 機能的^{[ 23 ] [ 25 ] [ 26 ]} (右一意^{[ 24 ]}または一価^{[ 27 ]}とも呼ばれる) : すべての${\displaystyle x\in X}$そしてすべて${\displaystyle y,z\in Y,}$もし${\displaystyle xRy}$そして${\displaystyle xRz}$それから${\displaystyle y=z}$言い換えれば、ドメインの各要素は最大で1 つのイメージ要素を持つ。このような二項関係は部分関数または部分写像と呼ばれる。^{[ 28 ]}このような関係の場合、${\displaystyle \{X\}}$は主キーと呼ばれます${\displaystyle R}$^{[ 2 ]}例えば、図中の赤と緑の二項関係は機能的だが、青の二項関係は機能的ではない（${\displaystyle 1}$両方へ${\displaystyle 1}$そして${\displaystyle -1}$）も、黒いものも（${\displaystyle 0}$両方へ${\displaystyle -1}$そして${\displaystyle 1}$)
• 一対一：単射かつ関数的である。例えば、図中の緑色の二項関係は一対一であるが、赤、青、黒の二項関係はそうではない。
• 一対多：単射であり、関数的ではない。例えば、図中の青色の二項関係は一対多だが、赤、緑、黒の二項関係はそうではない。
• 多対一：関数的であり、単射ではない。例えば、図中の赤い二項関係は多対一だが、緑、青、黒の二項関係はそうではない。
• 多対多：単射でも関数でもない。例えば、図中の黒色の二項関係は多対多だが、赤、緑、青の二項関係はそうではない。

全体性特性（ドメインが定義可能な場合のみ）${\displaystyle X}$およびコドメイン${\displaystyle Y}$指定されている）：

• 合計^{[ 23 ]} (左合計とも呼ばれる^{[ 24 ]} ): すべての${\displaystyle x\in X}$存在する${\displaystyle y\in Y}$そのため${\displaystyle xRy}$言い換えれば、ドメインのすべての要素には少なくとも1 つのイメージ要素があります。言い換えれば、定義のドメインは${\displaystyle R}$に等しい${\displaystyle X}$この性質は、プロパティにおける接続（一部の著者は全結合とも呼ぶ）の定義とは異なります。このような二項関係は多値関数と呼ばれます。たとえば、図中の赤と緑の二項関係は全結合ですが、青の二項関係は全結合ではありません（関係がないため）。${\displaystyle -1}$実数にも関連しないため、黒色のものにも関連しない。${\displaystyle 2}$任意の実数に）。別の例として、${\displaystyle >}$は整数上の全関係です。しかし、正の整数上の全関係ではありません。なぜなら、${\displaystyle y}$正の整数において、${\displaystyle 1>y}$[ ^{29 ]}しかし^、${\displaystyle <}$は正の整数、有理数、実数全体にわたる全関係です。すべての反射関係は全関係です。${\displaystyle x}$、 選ぶ${\displaystyle y=x}$。
• 全射^{[ 23 ]} (右全射とも呼ばれる^{[ 24 ]} ): すべての${\displaystyle y\in Y}$存在する${\displaystyle x\in X}$そのため${\displaystyle xRy}$言い換えれば、値域のすべての要素には少なくとも１つの逆像要素が存在する。言い換えれば、定義域は${\displaystyle R}$に等しい${\displaystyle Y}$例えば、図中の緑と青の二項関係は全射ですが、赤の二項関係は全射ではありません（実数と関係がないため）。${\displaystyle -1}$)、また黒色のもの (実数と関連付けていないため)${\displaystyle 2}$)

一意性と全体性の性質（ドメインが定義可能な場合のみ）${\displaystyle X}$およびコドメイン${\displaystyle Y}$指定されている）：

• 関数（マッピングとも呼ばれる^{[ 24 ]}）：機能的かつ全射な二項関係。言い換えれば、ドメインのすべての要素には、ちょうど1つのイメージ要素が存在する。例えば、図中の赤と緑の二項関係は関数であるが、青と黒の二項関係は関数ではない。
  • 単射：単射である関数。例えば、図中の緑色の関係は単射ですが、赤色の関係は単射ではありません。黒色と青色の関係はそもそも関数ではありません。
  • 全射：全射である関数。例えば、図中の緑色の関係は全射ですが、赤色の関係は全射ではありません。
  • 全単射：単射かつ全射である関数。言い換えれば、定義域のすべての要素には像要素がちょうど1つ存在し、値域のすべての要素には原像要素がちょうど1つ存在する。例えば、図中の緑色の二項関係は全単射だが、赤色の二項関係は全単射ではない。

適切なクラス間の関係が許容される場合：

• セットのような（ローカルとも呼ばれる）：すべての${\displaystyle x\in X}$すべてのクラス${\displaystyle y\in Y}$そのため${\displaystyle yRx}$つまり${\displaystyle \{y\in Y,yRx\}}$は集合です。例えば、関係${\displaystyle \in }$は集合のようなものであり、2 つの集合上のすべての関係は集合のようなものである。^{[ 30 ]}順序数のクラス上の通常の順序 <は集合のような関係であるが、その逆 > は集合のような関係ではない。

「等しい」、「部分集合」、「メンバー」といった特定の数学的「関係」は、上記のように定義される二項関係として理解することはできません。なぜなら、それらの定義域と値域は、通常の公理的集合論の体系における集合とはみなせないからです。例えば、「等価性」という一般的な概念を二項関係としてモデル化することは困難です。${\displaystyle =}$定義域と値域を「すべての集合のクラス」とします。これは通常の集合論における集合ではありません。

ほとんどの数学的文脈において、等号、メンバーシップ、部分集合の関係への言及は、文脈内の何らかの集合に限定されていると暗黙のうちに理解できるため、問題ない。この問題に対する一般的な回避策は、「十分に大きな」集合を選択することである。${\displaystyle A}$対象となるすべてのオブジェクトを含み、制約付きで動作する${\displaystyle =_{A}}$の代わりに${\displaystyle =}$同様に、「部分集合」関係${\displaystyle \subseteq }$ドメインとコドメインに制限する必要がある${\displaystyle P(A)}$（特定の集合の冪集合）${\displaystyle A}$結果として得られる集合関係は次のように表すことができる。${\displaystyle \subseteq _{A}.}$また、「メンバー」関係はドメインを持つように制限する必要がある。${\displaystyle A}$およびコドメイン${\displaystyle P(A)}$二項関係を取得する${\displaystyle \in _{A}}$それは集合である。バートランド・ラッセルは、${\displaystyle \in }$すべての集合上で定義されることは、素朴な集合論において矛盾を生じさせる（ラッセルのパラドックスを参照）。

この問題に対する別の解決策は、 NBG集合論やモース・ケリー集合論のような適切なクラスを持つ集合論を用い、定義域と終域（したがってグラフ）を適切なクラスとすることです。このような理論では、等号、メンバーシップ、部分集合は特別な注釈なしに二項関係となります。（順序付き三つ組の概念に若干の修正を加える必要があります。）${\displaystyle (X,Y,G)}$（通常、適切なクラスは順序付きタプルのメンバーにはなれません。またはもちろん、この文脈では二項関係をそのグラフと同一視することもできます。）^{[ 31 ]}この定義により、たとえば、すべての集合とその冪集合上の二項関係を定義できます。

集合上の同次関係${\displaystyle X}$は二項関係である${\displaystyle X}$そしてそれ自体、つまりそれはデカルト積の部分集合である${\displaystyle X\times X.}$^{[ 14 ] [ 32 ] [ 33 ]}これは単に（二項）関係とも呼ばれます。${\displaystyle X}$。

同質な関係${\displaystyle R}$セットを超えて${\displaystyle X}$は、ループを許容する有向単純グラフと同一視できる。${\displaystyle X}$頂点集合であり、${\displaystyle R}$エッジセットは（頂点からエッジが存在する）${\displaystyle x}$頂点へ${\displaystyle y}$かつその場合に限り${\displaystyle xRy}$すべての同次関係の集合。${\displaystyle {\mathcal {B}}(X)}$セットを超えて${\displaystyle X}$パワーセットは${\displaystyle 2^{X\times X}}$これは、関係をその逆関係に写像する対合によって拡張されたブール代数です。関係の合成をの二項演算として考えると、${\displaystyle {\mathcal {B}}(X)}$、それは対合を持つ半群を形成する。

同次関係が持つ重要な特性${\displaystyle R}$セットを超えて${\displaystyle X}$考えられるもの：

• 再帰的:すべての${\displaystyle x\in X,}$${\displaystyle xRx}$。 例えば、${\displaystyle \geq }$は反射関係ですが、> は反射関係ではありません。
• 非反射的：すべての${\displaystyle x\in X,}$ない${\displaystyle xRx}$。 例えば、${\displaystyle >}$これは非反射的な関係ですが、${\displaystyle \geq }$そうではない。
• 対称: すべての${\displaystyle x,y\in X,}$もし${\displaystyle xRy}$それから${\displaystyle yRx}$例えば、「～の血縁者である」は対称的な関係です。
• 反対称: すべての${\displaystyle x,y\in X,}$もし${\displaystyle xRy}$そして${\displaystyle yRx}$それから${\displaystyle x=y.}$例えば、${\displaystyle \geq }$これは反対称関係である。^{[ 34 ]}
• 非対称: すべての${\displaystyle x,y\in X,}$もし${\displaystyle xRy}$それならそうではない${\displaystyle yRx}$関係が非対称であるのは、それが反対称かつ非反射的である場合に限る。^{[ 35 ]}例えば、> は非対称関係であるが、${\displaystyle \geq }$そうではない。
• 推移的:すべての${\displaystyle x,y,z\in X,}$もし${\displaystyle xRy}$そして${\displaystyle yRz}$それから${\displaystyle xRz}$推移関係は、非対称である場合に限り、非反射的である。^{[ 36 ]}例えば、「is ancestor of」は推移関係であるが、「is parent of」は推移関係ではない。
• つながる：すべての人々のために${\displaystyle x,y\in X,}$もし${\displaystyle x\neq y}$それから${\displaystyle xRy}$または${\displaystyle yRx}$。
• 強く繋がる：すべての人々のために${\displaystyle x,y\in X,}$${\displaystyle xRy}$または${\displaystyle yRx}$。
• 濃密：すべての${\displaystyle x,y\in X,}$もし${\displaystyle xRy,}$それからいくつか${\displaystyle z\in X}$が存在して、${\displaystyle xRz}$そして${\displaystyle zRy}$。

半順序とは、反射的、反対称的、推移的な関係である。厳密な半順序とは、非反射的、非対称的、推移的な関係である。全順序とは、反射的、反対称的、推移的、連結的な関係である。^{[ 37 ]}厳密な全順序とは、非反射的、非対称的、推移的、連結的な関係である。同値関係とは、反射的、対称的、推移的な関係である。例えば、「${\displaystyle x}$分ける${\displaystyle y}$「」は自然数上の部分順序ではあるが、全順序ではない。${\displaystyle \mathbb {N} ,}$「${\displaystyle x<y}$「は、厳密な全順序である」${\displaystyle \mathbb {N} ,}$そして "${\displaystyle x}$と並行しています${\displaystyle y}$「は、ユークリッド平面上のすべての直線の集合上の同値関係です。

§ 操作のセクションで定義されているすべての操作は、同次関係にも適用されます。さらに、集合上の同次関係は、${\displaystyle X}$以下のような閉鎖措置の対象となる可能性があります。

反射的閉鎖

最小の反射関係${\displaystyle X}$含む${\displaystyle R}$、

推移的閉包

最小の推移的関係${\displaystyle X}$含む${\displaystyle R}$、

同値閉包

最小の同値関係${\displaystyle X}$含む${\displaystyle R}$。

代数論理の発展により、二項関係の利用が容易になった。関係の計算には、集合の代数、関係の合成、および逆関係の使用が含まれる。${\displaystyle R\subseteq S,}$つまり${\displaystyle aRb}$暗示する${\displaystyle aSb}$関係性の格子の中に場面を設定する。しかし、${\displaystyle P\subseteq Q\equiv (P\cap {\bar {Q}}=\varnothing )\equiv (P\cap Q=P),}$包含記号は不要です。それにもかかわらず、シュレーダー規則に従った関係の合成と演算子の操作により、冪集合で作業するための計算が提供されます。${\displaystyle A\times B.}$

同種関係とは対照的に、関係の合成演算は部分関数にすぎない。合成された関係のターゲットとソースを一致させる必要性から、異種関係の研究は、集合の圏と同様に圏論の一章であるという提案がなされた。ただし、この圏の射は関係である。圏Relの対象は集合であり、関係射は圏で必要とされるように合成される。^{[ 38 ]}

二項関係は、それらが誘導する概念束を通して記述されてきた。概念${\displaystyle C\subset R}$2つの特性を満たす：

• 論理マトリックス​${\displaystyle C}$論理ベクトルの外積である${\displaystyle C_{ij}=u_{i}v_{j},\quad u,v}$論理ベクトル。
• ${\displaystyle C}$最大であり、他のどの外積にも含まれていない。したがって${\displaystyle C}$拡大できない長方形として説明されます。

与えられた関係に対して${\displaystyle R\subseteq X\times Y,}$概念の集合は、それらの結合と交わりによって拡張され、包含関係を持つ「概念の誘導格子」を形成する。${\displaystyle \sqsubseteq }$予約注文をしています。

マクニールの完全性定理（1937年）（任意の半順序は完全束に埋め込むことができる）は、2013年の調査論文「概念束上の関係の分解」で引用されている。^{[ 39 ]}分解は

${\displaystyle R=fEg^{\textsf {T}}}$、 どこ${\displaystyle f}$そして${\displaystyle g}$これらは関数であり、この文脈では写像または左全関数関係と呼ばれる。「誘導概念束」は、半順序のカット完備化と同型である。${\displaystyle E}$最小分解に属する${\displaystyle (f,g,E)}$関係の${\displaystyle R}$。

具体的な事例については以下で検討する。${\displaystyle E}$総次数はフェラーズ型に対応し、${\displaystyle E}$同一性は二関数性に対応し、集合上の同値関係の一般化である。

関係は、関係をカバーするために必要な概念の数を数えるシャインランクによってランク付けされることがある。 ^{[ 40 ]}概念を用いた関係の構造分析は、データマイニングのアプローチを提供する。^{[ 41 ]}

• 命題：もし${\displaystyle R}$は全射関係であり、${\displaystyle R^{\mathsf {T}}}$その転置は、${\displaystyle I\subseteq R^{\textsf {T}}R}$どこ${\displaystyle I}$は${\displaystyle m\times m}$同一性関係。
• 命題：もし${\displaystyle R}$は直列関係である、${\displaystyle I\subseteq RR^{\textsf {T}}}$どこ${\displaystyle I}$は${\displaystyle n\times n}$同一性関係。

すべての関係${\displaystyle R}$予約注文を生成する${\displaystyle R\backslash R}$これは左残差である。^{[ 53 ]}逆と補数の観点から言えば、${\displaystyle R\backslash R\equiv {\overline {R^{\textsf {T}}{\bar {R}}}}.}$対角線を形成する${\displaystyle R^{\textsf {T}}{\bar {R}}}$対応する行${\displaystyle R^{\textsf {T}}}$そして列${\displaystyle {\bar {R}}}$反対の論理値を持つため、対角線はすべてゼロになります。

${\displaystyle R^{\textsf {T}}{\bar {R}}\subseteq {\bar {I}}\implies I\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}=R\backslash R}$、 となることによって${\displaystyle R\backslash R}$これは反射関係です。

推移性を示すには、${\displaystyle (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$思い出してください${\displaystyle X=R\backslash R}$は、${\displaystyle RX\subseteq R.}$それから

${\displaystyle R(R\backslash R)\subseteq R}$

${\displaystyle R(R\backslash R)(R\backslash R)\subseteq R}$（繰り返す）

${\displaystyle \equiv R^{\textsf {T}}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$（シュレーダーの法則）

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}}$（補語）

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$（意味）

冪集合上の包含関係Ω${\displaystyle U}$メンバーシップ関係からこのようにして得ることができる${\displaystyle \in }$サブセットについて${\displaystyle U}$:

${\displaystyle \Omega ={\overline {\ni {\bar {\in }}}}=\in \backslash \in .}$^{[ 52 ] : 283}

関係が与えられた場合${\displaystyle R}$、その周辺は次のように定義される部分関係である。 $${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{\textsf {T}}R}}.}$$

いつ${\displaystyle R}$が部分的な恒等関係、二関数関係、またはブロック対角関係である場合、${\displaystyle \operatorname {fringe} (R)=R}$そうでなければ${\displaystyle \operatorname {fringe} }$演算子は、その論理行列で記述された境界部分関係を選択します。${\displaystyle \operatorname {fringe} (R)}$対角線が${\displaystyle R}$右上三角線形順序または厳密順序です。${\displaystyle \operatorname {fringe} (R)}$ブロックフリンジは${\displaystyle R}$非反射的である（${\displaystyle R\subseteq {\bar {I}}}$）または右上隅の三角形のブロック。${\displaystyle \operatorname {fringe} (R)}$境界矩形のシーケンスである場合${\displaystyle R}$フェラール型である。

一方で、${\displaystyle \operatorname {fringe} (R)=\emptyset }$いつ${\displaystyle R}$これは、密で線形かつ厳密な順序です。^{[ 52 ]}

2つの集合が与えられた場合${\displaystyle A}$そして${\displaystyle B}$それらの間の二項関係の集合${\displaystyle {\mathcal {B}}(A,B)}$三値演算機能を備えることができる${\displaystyle [a,b,c]=ab^{\textsf {T}}c}$どこ${\displaystyle b^{\mathsf {T}}}$逆の関係を表す${\displaystyle b}$1953年、ヴィクトル・ワグナーはこの三項演算の性質を利用して、半ヒープ、ヒープ、および一般化ヒープを定義した。^{[ 54 ] [ 55 ]}これらの定義によって、異種関係と同種関係の対比が強調される。

ワーグナーの研究には、ヒープ、セミヒープ、一般化ヒープと、グループ、セミグループ、一般化グループとの間に心地よい対称性が見られる。本質的に、異なる集合間の二項関係（および部分的な一対一写像）を考える際には、様々なタイプのセミヒープが現れる。${\displaystyle A}$そして${\displaystyle B}$半群の様々なタイプは、${\displaystyle A=B}$。