二項関係

数学において、二項関係は、定義域と呼ばれる集合の要素を、余領域と呼ばれる別の集合の要素に関連付けます。^[1]正確には、集合 と 上の二項関係は、が内にありが内にある順序付きペアの集合です。^[2]これは、関係の共通概念をエンコードします。つまり、要素 は要素 と関連しており、その場合、そのペアは二項関係を定義する順序付きペアの集合に属します。 ${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle X}$${\displaystyle y}$${\displaystyle Y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)}$

2 項関係の例としては、素数の集合と整数の集合に対する「を割る」関係が挙げられます。この関係では、各素数はの倍数である各整数と関連していますが、の倍数でない整数とは関連していません。この関係では、たとえば、素数は、、、などの数と関連していますが、 や とは関連していません。これは、素数が、、およびと関連していますが、 や とは関連していないのと同じです。 ${\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}$

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

• 算術における「より大きい」、「等しい」、「割り算」の関係。
• 幾何学における「合同な」関係。
• グラフ理論における「隣接している」関係。
• 線形代数における「直交する」関係。

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

集合と上の二項関係は、のべき集合の要素です。後者の集合は包含( ) によって順序付けられるので、各関係はのサブセットの格子内に位置を持ちます。のとき、二項関係は同次関係と呼ばれます。である必要がないとき、二項関係は異次関係とも呼ばれます。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\times Y.}$${\displaystyle \subseteq }$${\displaystyle X\times Y.}$${\displaystyle X=Y}$${\displaystyle X=Y}$

関係は集合であるため、集合演算（和集合、積集合、補集合など）を使用して操作することができ、集合代数の法則を満たします。さらに、関係の逆や関係の合成などの演算が利用可能で、関係の微積分の法則を満たします。この法則については、エルンスト・シュレーダー^[4] 、クラレンス・ルイス^[5]、ギュンター・シュミット^[6]による教科書があります。関係をより深く分析するには、関係を概念と呼ばれるサブセットに分解し、完全な格子に配置する必要があります。

公理的集合論のいくつかのシステムでは、関係は集合の一般化であるクラスに拡張されます。この拡張は、ラッセルのパラドックスなどの論理的矛盾に陥ることなく、集合論における「は の要素である」または「は のサブセットである」という概念をモデル化するために必要です。

二項関係は、直積のサブセットである集合上の-項関係の最も研究されている特別なケースである^[2]${\displaystyle n=2}$${\displaystyle n}$${\displaystyle X_{1},\dots ,X_{n}}$ ${\displaystyle X_{1}\times \cdots \times X_{n}.}$

集合およびが与えられた場合、直積は と定義され、その要素は順序付きペアと呼ばれます。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\times Y}$${\displaystyle \{(x,y)\mid x\in X{\text{ and }}y\in Y\},}$

集合と上の二項関係 は のサブセットです^{[2] [7]}集合はのドメイン^[2]または出発集合と呼ばれ、集合 はの終点または終点集合と呼ばれます。集合との選択を指定するために、一部の著者は二項関係または対応をのサブセットである順序付きトリプル として定義します。このサブセットはのグラフと呼ばれます。この文は「はと -関連している」と読み、 で表されます。^{[4] [5] [6] [注 1]}の定義域またはアクティブドメイン^[2]は、少なくとも 1 つの に対してとなるすべての の集合です。定義の終点、アクティブ終点、^{[2] の}像または値域は、少なくとも 1 つの に対して となるすべての の集合です。の体はその定義域と定義の終点の和集合です。^{[9] [10] [11]}${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\times Y.}$${\displaystyle X}$${\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}$${\displaystyle R}$${\displaystyle x}$${\displaystyle xRy}$${\displaystyle y}$ ${\displaystyle R}$${\displaystyle y}$${\displaystyle xRy}$${\displaystyle x}$${\displaystyle R}$

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

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

対応、^[16]二項関係、二項関係という用語は二項関係の同義語ですが、一部の著者は、およびを参照せずに直積の任意の部分集合に「二項関係」という用語を使用し、およびを参照する二項関係に「対応」という用語を予約しています。^[要出典] ${\displaystyle X\times Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$

2 項関係では、要素の順序が重要です。 の場合、 はとは関係なく true または false になります。 たとえば、は を割り切りますが、 はを割り切りません。 ${\displaystyle x\neq y}$${\displaystyle yRx}$${\displaystyle xRy}$${\displaystyle 3}$${\displaystyle 9}$${\displaystyle 9}$${\displaystyle 3}$

および が集合上の二項関係である場合、はおよびおよび上の和集合関係です。 ${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle R\cup S=\{(x,y)\mid xRy{\text{ or }}xSy\}}$${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$

単位元は空の関係です。たとえば、は < と = の和集合であり、は> と = の和集合です。 ${\displaystyle \leq }$${\displaystyle \geq }$

および が集合上の二項関係である場合、はおよびおよび上の交差関係です。 ${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle R\cap S=\{(x,y)\mid xRy{\text{ and }}xSy\}}$${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$

単位元は普遍的な関係です。たとえば、「6 で割り切れる」という関係は、「3 で割り切れる」と「2 で割り切れる」という関係の共通部分です。

が集合および上の二項関係であり、 が集合 上の二項関係である場合、( とも表記) はおよびおよび上のの合成関係です。 ${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle S}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle S\circ R=\{(x,z)\mid {\text{ there exists }}y\in Y{\text{ such that }}xRy{\text{ and }}ySz\}}$${\displaystyle R;S}$${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Z}$

恒等元は恒等関係です。ここで使用される表記法におけるとの順序は、関数 の合成の標準的な表記法の順序と一致します。たとえば、( の親である ) ( の母である ) の合成は の母方の祖父母 となり、一方、( の母である ) ( の親である ) の合成は の祖母 となります。前者の場合、が の親でありがの母である場合、 は の母方の祖父母です。 ${\displaystyle R}$${\displaystyle S}$${\displaystyle S\circ R,}$${\displaystyle \circ }$${\displaystyle \circ }$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle z}$

が集合上の二項関係である場合、はおよび上の逆関係（^[17]の逆関係（^[18]とも呼ばれる））です。 ${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle R^{\textsf {T}}=\{(y,x)\mid xRy\}}$${\displaystyle R}$${\displaystyle Y}$${\displaystyle X}$

たとえば、は自身の逆であり、 は であり、と は互いの逆であり、 と は です。二項関係は、対称 である場合に限り、その逆と等しくなります。 ${\displaystyle =}$${\displaystyle \neq }$${\displaystyle <}$${\displaystyle >}$${\displaystyle \leq }$${\displaystyle \geq }$

が集合上の二項関係である場合、( とも表記) はおよび上の の相補関係です。 ${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\bar {R}}=\{(x,y)\mid \neg xRy\}}$${\displaystyle \neg R}$${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$

たとえば、と は互いに補数であり、 と、と、と、および であり、全順序についてはと、およびと も同様です。 ${\displaystyle =}$${\displaystyle \neq }$${\displaystyle \subseteq }$${\displaystyle \not \subseteq }$${\displaystyle \supseteq }$${\displaystyle \not \supseteq }$${\displaystyle \in }$${\displaystyle \not \in }$${\displaystyle <}$${\displaystyle \geq }$${\displaystyle >}$${\displaystyle \leq }$

逆関係 の補語は補語の逆です。${\displaystyle R^{\textsf {T}}}$${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

補集合に次の特性がある 場合:${\displaystyle X=Y,}$

• 関係が対称的であれば、その補関係も対称的になります。
• 反射的な関係の補語は非反射的であり、その逆も同様です。
• 厳密な弱順序の補順序は全前順序であり、その逆も同様です。

が集合上の二項同次関係であり、がの部分集合である場合、 は${\displaystyle R}$${\displaystyle X}$${\displaystyle S}$${\displaystyle X}$${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S{\text{ and }}y\in S\}}$〜〜の制限関係。 ${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$

が集合と上の二項関係であり、がの部分集合である場合、は${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle S}$${\displaystyle X}$${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S\}}$からおよびへの左制限関係。^{[説明が必要]}${\displaystyle R}$${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$

関係が反射的、非反射的、対称的、反対称的、非対称的、推移的、全的、三分的、部分順序、全順序、厳密な弱い順序、全前順序（弱い順序）、または同値関係である場合、その制限も同様です。

ただし、制限の推移閉包は推移閉包の制限のサブセットです。つまり、一般には等しくありません。たとえば、「is parent of 」という関係を女性に制限すると、「 is mother of the woman 」という関係が生成されます。この推移閉包は、女性を父方の祖母に関連付けません。一方、「is parent of」の推移閉包は「is ancestor of」であり、これを女性に制限すると、女性を父方の祖母に関連付けます。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

また、完全性に関するさまざまな概念(「完全」であることと混同しないでください) は、制限には適用されません。たとえば、実数上の関係の特性として、の上限を持つすべての空でない部分集合には、 の最小の上限(上限とも呼ばれる)があります。ただし、有理数の場合、この上限は必ずしも有理数ではないため、同じ特性は、 の関係を有理数に 制限した場合には当てはまりません。${\displaystyle \leq }$${\displaystyle S\subseteq \mathbb {R} }$${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} .}$${\displaystyle \leq }$

集合と集合上の二項関係は次のように表現される。${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$はおよび上関係に含まれ、が の部分集合である場合、つまり に対して と、である場合となります。が に含まれ、 がに含まれる、と は等しいと書かが に含まれるがに含まれない場合、 はであると言われます${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle R\subseteq S,}$${\displaystyle R}$${\displaystyle S}$${\displaystyle x\in X}$${\displaystyle y\in Y,}$${\displaystyle xRy}$${\displaystyle xSy}$${\displaystyle R}$${\displaystyle S}$${\displaystyle S}$${\displaystyle R}$${\displaystyle R}$${\displaystyle S}$${\displaystyle R=S}$${\displaystyle R}$${\displaystyle S}$${\displaystyle S}$${\displaystyle R}$${\displaystyle R}$より小さく、 と書きます。たとえば、有理数、関係はより小さく、合成 と等しく。 ${\displaystyle S}$${\displaystyle R\subsetneq S.}$${\displaystyle >}$${\displaystyle \geq }$${\displaystyle >\circ >}$

集合と上の二項関係は、ブール半環の要素を持つ、およびでインデックス付けされた論理行列によって代数的に表現できます(加算は OR に、乗算は AND に対応します)。ここで、行列の加算は関係の和に対応し、行列の乗算は関係の合成 (と上の関係とと上の関係) に対応します。^[19]アダマール積は関係の交差に対応し、ゼロ行列は空関係に対応し、1 の行列は普遍関係に対応します。同次関係 (のとき) は行列半環(実際、ブール半環上の行列半代数)を形成します。ここで、単位行列は単位関係に対応します。^[20]${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle X=Y}$

集合上の二項関係のいくつかの重要なタイプを以下に示します。 ${\displaystyle R}$${\displaystyle X}$${\displaystyle Y}$

一意性プロパティ:

• 単射的^[23] (左一意性^[24]とも呼ばれる): すべての に対して であり、すべての である場合にとなる。言い換えれば、共役域のすべての要素は、多くとも1 つの原像要素を持つ。このような関係に対して、は の主キーと呼ばれる。^[2]たとえば、図の緑と青の二項関係は単射であるが、赤の関係 (との両方を に関連付けているため) や黒の関係 (との両方を に関連付けているため) は単射ではない。${\displaystyle x,y\in X}$${\displaystyle z\in Y,}$${\displaystyle xRz}$${\displaystyle yRz}$${\displaystyle x=y}$${\displaystyle Y}$${\displaystyle R}$${\displaystyle -1}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle -1}$${\displaystyle 1}$${\displaystyle 0}$
• 関数型^{[23] [25] [26]}（右一意^[24]または一価^[27]とも呼ばれる）：すべておよびすべてかつで場合成り立つ。言い換えれば、ドメインのすべての要素は、多くとも1 つの像要素を持つ。このような二項関係は、部分関数または部分マッピングと呼ばれる。 ^[28]このような関係に対して、は の主キーと呼ばれる。 ^[2]たとえば、図の赤と緑の二項関係は関数型であるが、青の関係（と の両方に）も黒の関係（と の両方に）も関数型ではない。${\displaystyle x\in X}$${\displaystyle y,z\in Y,}$${\displaystyle xRy}$${\displaystyle xRz}$${\displaystyle y=z}$${\displaystyle \{X\}}$${\displaystyle R}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle -1}$${\displaystyle 0}$${\displaystyle -1}$${\displaystyle 1}$
• 1 対 1 : 単射かつ関数的。たとえば、図の緑の 2 項関係は 1 対 1 ですが、赤、青、黒の関係は 1 対 1 ではありません。
• 1 対多: 単射であり、関数的ではありません。たとえば、図の青い 2 項関係は 1 対多ですが、赤、緑、黒はそうではありません。
• 多対 1 : 関数的であり、単射ではありません。たとえば、図の赤い 2 項関係は多対 1 ですが、緑、青、黒の関係は多対 1 ではありません。
• 多対多: 単射でも関数的でもない。たとえば、図の黒い 2 項関係は多対多ですが、赤、緑、青はそうではありません。

全体性プロパティ (ドメインとコドメインが指定されている場合にのみ定義可能): ${\displaystyle X}$${\displaystyle Y}$

• 全^[23]（左全^[24]とも呼ばれる）：すべての に対して、となる が存在する。言い換えれば、定義域のすべての要素には、少なくとも1 つの像要素がある。言い換えれば、 の定義域は に等しい。この特性は、 「特性」における連結（一部の著者は全とも呼ぶ^{） [要出典]}の定義とは異なる。このような二項関係は多価関数と呼ばれる。たとえば、図の赤と緑の二項関係は全であるが、青の関係は全ではない（実数に関連しないため実数に関連しないため）。別の例として、 は整数に対して全関係であるとなる正の整数には が存在しないことから、正の整数に対しては全関係ではない。 ^[29]しかし、は正の整数、有理数、実数に対して全関係である。すべての反射関係は全である。つまり、与えられた に対して、 を選択します。${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle xRy}$${\displaystyle R}$${\displaystyle X}$${\displaystyle -1}$${\displaystyle 2}$${\displaystyle >}$${\displaystyle y}$${\displaystyle 1>y}$${\displaystyle <}$${\displaystyle x}$${\displaystyle y=x}$
• 射影的^[23] (右全^[24]とも呼ばれる): すべての に対して、となるような が存在する。言い換えると、余域のすべての元には少なくとも1 つの原像元がある。言い換えると、 の定義の余域は に等しい。たとえば、図の緑と青の二項関係は射影的であるが、赤は射影的ではない ( に実数を関連付けていないため)。黒も同様である ( に実数を関連付けていないため)。${\displaystyle y\in Y}$${\displaystyle x\in X}$${\displaystyle xRy}$${\displaystyle R}$${\displaystyle Y}$${\displaystyle -1}$${\displaystyle 2}$

一意性と全体性プロパティ (ドメインとコドメインが指定されている場合にのみ定義可能): ${\displaystyle X}$${\displaystyle Y}$

• 関数（マッピング^[24]とも呼ばれる）：関数的かつ完全な2項関係。言い換えれば、ドメインのすべての要素には、正確に1つのイメージ要素があります。たとえば、図の赤と緑の2項関係は関数ですが、青と黒の2項関係は関数ではありません。
• 注入: 注入的な関数。たとえば、図の緑の関係は注入ですが、赤は注入ではありません。黒と青の関係は関数でさえありません。
• 全射: 全射的な関数。たとえば、図の緑の関係は全射ですが、赤の関係は全射ではありません。
• 全単射: 単射かつ全射である関数。言い換えると、ドメインのすべての要素には正確に1 つの像要素があり、コドメインのすべての要素には正確に1 つの原像要素があります。たとえば、図の緑の 2 項関係は全単射ですが、赤のものはそうではありません。

適切なクラス間の関係が許可されている場合:

• 集合的（局所的とも呼ばれる）：すべての に対して、、すなわち となるすべてののクラス。たとえば、関係 は集合的であり、2 つの集合上のすべての関係は集合的である。^[30]順序数のクラス上の通常の順序付け < は集合的関係であるが、その逆 > は集合的関係ではない。^[要出典]${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle yRx}$${\displaystyle \{y\in Y,yRx\}}$${\displaystyle \in }$

「等しい」、「サブセット」、「メンバー」などの特定の数学的な「関係」は、その定義域と共域を公理的集合論の通常の体系の集合と見なすことができないため、上で定義したような二項関係として理解することはできません。たとえば、「等しい」という一般的な概念を二項関係としてモデル化するには、定義域と共域を「すべての集合のクラス」と見なしますが、これは通常の集合論の集合ではありません。 ${\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やモース・ケリー集合論などの真クラスを持つ集合論を使用し、ドメインとコドメイン（およびグラフ）を真クラスとすることである。このような理論では、等式、メンバーシップ、およびサブセットは、特別なコメントなしの二項関係です。（通常、真クラスは順序付きタプルのメンバーになることはできないため、順序付きトリプルの概念に小さな修正を加える必要があります。または、もちろん、このコンテキストでは二項関係をそのグラフと同一視することもできます。）^[31]この定義を使用すると、たとえば、すべての集合とその冪集合上の二項関係を定義できます。 ${\displaystyle (X,Y,G)}$

集合上の同次関係は、およびそれ自身上の二項関係、すなわち直積の部分集合である^{[14] [32] [33]。}これは単に上の（二項）関係とも呼ばれる。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle X\times X.}$${\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}$
• 反対称：すべての場合、そして例えば、は反対称関係である。 ^[34]${\displaystyle x,y\in X,}$${\displaystyle xRy}$${\displaystyle yRx}$${\displaystyle x=y.}$${\displaystyle \geq }$
• 非対称：すべてならばはない。関係が非対称となるのは、反対称かつ非反射的な場合のみである。 ^[35]たとえば、> は非対称関係だが、 はそうではない。${\displaystyle x,y\in X,}$${\displaystyle xRy}$${\displaystyle yRx}$${\displaystyle \geq }$
• 推移的: すべて の場合、かつ。推移的関係は、非対称である場合にのみ非反射的である。 ^[36]たとえば、「〜の祖先である」は推移的関係であるが、「〜の親である」はそうではない。${\displaystyle x,y,z\in X,}$${\displaystyle xRy}$${\displaystyle yRz}$${\displaystyle xRz}$
• 接続: すべて に対してであれば、または。${\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のオブジェクトは集合であり、関係射はカテゴリで要求されるように合成される。^[要出典]

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

• の論理行列は、論理ベクトルの論理ベクトルの外積です。^{[説明が必要]}${\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年の調査論文「概念格子上の関係の分解」で引用されている。^[38]分解は

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

以下では、特定のケースについて検討します。全順序は Ferrers 型に対応し、恒等式は集合上の 同値関係の一般化である二関数に対応します。${\displaystyle E}$${\displaystyle E}$

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

• 命題:が直列関係であり、 がその転置である場合、 は恒等関係です。${\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}$

二機能関係の考え方は、同値関係 の概念を一般化して、属性を区別することによってオブジェクトを分割することです。これを行う 1 つの方法は、介在する指標のセットを使用することです。分割関係は、機能関係を使用した関係の合成です。ジャック・リゲは、この合成に一般に部分関数と呼ばれる機能関係が含まれるため、これらの関係を二機能と名付けました。 ${\displaystyle Z=\{x,y,z,\ldots \}}$${\displaystyle R=FG^{\textsf {T}}}$${\displaystyle F\subseteq A\times Z{\text{ and }}G\subseteq B\times Z.}$ ${\displaystyle FG^{\mathsf {T}}}$

1950年にリゲは、このような関係が包含関係を満たすことを示した。^[41]

$${\displaystyle RR^{\textsf {T}}R\subseteq R}$$

オートマトン理論では、直交関係という用語は、二機能関係を表すためにも使用されている。この用語は、論理行列として表現される場合、二機能関係の列と行は、（非対称の）主対角線上に 1 の矩形ブロックを持つブロック行列として配置できることを思い起こさせる。 ^[42]より正式には、上の関係が二機能的であるためには、 が のサブセットの分割であり、 が同様に のサブセットの分割である直積 の和集合 として表すことができる必要がある。^[43]${\displaystyle R}$${\displaystyle X\times Y}$${\displaystyle A_{i}\times B_{i}}$${\displaystyle A_{i}}$${\displaystyle X}$${\displaystyle B_{i}}$${\displaystyle Y}$