二項関係

数学において、二項関係（にこうかんけい、英: binary relation）あるいは二変数関係 (dyadic relation, 2-place relation) は、集合 A の元からなる順序対のあつまりである。別な言い方をすれば、直積集合 A² = A × A の部分集合を、集合 A 上の二項関係と呼ぶ。あるいはもっと一般に、二つの集合 A, B に対して、A と B との間の二項関係とは、直積 A × B の部分集合のことをいう。
二項関係の一つの例は素数全体の成す集合 P と整数全体の成す集合 Z の間の整除関係である。この整除関係では任意の素数 p は、p の倍数である任意の整数 z に関係を持ち、倍数でない整数には関係しないものとして扱われる。例えば、素数 2 が関係を持つ整数には −4, 0, 6, 10 などが含まれるが 1 や 9 は含まれない。同様に素数 3 が関係する整数として 0, 6, 9 などが挙げられるが、4 や 13 はそうではない。
二項関係は数学のさまざまな分野で用いられ、不等関係、恒等関係、算術の整除関係、初等幾何学の合同関係、グラフ理論の隣接関係、線型代数学の直交関係などのさまざまな概念が二項関係として定式化することができる。また、写像の概念を特別な種類の二項関係として定義することもできる。二項関係は計算機科学においても重用される。
二項関係は n-項関係 R ⊆ A₁ × ⋯ × Aₙ（各 j-番目の成分が関係の j-番目の始集合 Aⱼ からとられているような n-組からなる集合）で n = 2 とした特別の場合である。
ある種の公理的集合論では（集合の一般化としての）類の上の関係を考えることができる。このような拡張は、集合論における元の帰属関係や包含関係の概念（に限った話ではないが）のモデル化を、ラッセルの逆理のような論理矛盾に陥らずに行うために必要である。

定義

二項関係 R は通常、任意の集合（または類）X, Y とそれらの直積 X × Y の部分集合 G の順序三つ組 (X, Y, G) として定義される。このとき、集合 X および Y はそれぞれこの関係の始集合 (domain) および終集合 (codomain) と呼ばれ、G はこの関係のグラフと呼ばれ、G(R) と表すこともある。
R が関係 (X, Y, G) であるとき、(x, y) ∈ G となることを、「x は y と R-関係を持つ」などといい、x R y や R(x, y) で表す。後者は、対の集合 G の指示函数として R を見ることに対応する。
始集合 X と終集合 Y が同じ場合であっても、対の各要素の順番は重要で、a ≠ b ならば a R b および b R a はそれぞれ独立に真にも偽にもなりうる。

関係とグラフ

定義から、グラフ G がまったく同じになるような関係があっても、始集合 X や終集合 Y が異なれば、それらは相異なる別の関係である。たとえば G = {(1,2), (1,3), (2,7)} を共有する三つの関係 (Z, Z, G), (R, N, G), (N, R, G) はそれぞれ異なる関係を表す。
ただし、関係の定義に始集合 X や終集合 Y を考慮しない流儀もある。この場合、二項関係とは X × Y の部分集合であるグラフ G そのものをいうのに相違ない。このような立場では、対の集合{(1,2), (1,3), (2,7)} は {1, 2} を含む任意の始集合から {2, 3, 7} を含む任意の終集合への関係を表す。
この差異を、関係の特別な場合として写像の概念に適用する場合を考えよう。多くの文脈では、写像の終域と値域とを異なるものとして峻別して扱うので、ひとつの「規準」として例えば実数 x に x² を対応させるとき、終域を実数全体 R とするか、あるいはより精密に非負の実数全体 R⁺ とするかによって、二つの異なる写像 f: R → R および g: R → R⁺ が得られる。しかし別な文脈では、写像とは単に第一成分が一意であるような順序対の集合として扱われることもある。この差異はとある自明でない問題から生じていると見ることができる。例えば、前者の立場では写像の性質として全射性を考えることができるし、一方で後者は集合を生み出す関係性として写像を捉えることができる。
この二つの異なる定義の違いが問題となるのは圏論のような極めて厳密な文脈のみであって、殆どの場面で何れの流儀であってもさほど問題となることはないし、必要に応じて適当に用語や記法を変更してやれば、関係の制限や関係の合成、逆関係といった概念を定義することができる。

関係の制限

集合 X の関係の部分集合 S への制限 (restriction) とは、その関係のグラフに属する順序対 (x, y) で x と y がともに S に属するようなもの全体の成す集合をいう。
関係が、反射的である、非反射的である、対称である、反対称である、非対称である、推移的である、完全である、三分的である、半順序である、全順序である、狭義弱順序である、全前順序である、同値関係であるといった性質は、制限によって保たれる。
しかし、関係の制限の推移閉包はもとの関係の推移閉包の制限の部分集合とはなるが一般には一致しない。
また、完備性 (completeness) のいくつかの概念（完全性 totalness と混同してはいけない）は、制限によって遺伝しない。例えば、実数全体の成す集合 R 上で、通常の大小関係 "≤" は「R の任意の空でない部分集合 S で R に上界を持つものは R に上限（最小上界）を持つ」という性質があるが、しかし関係 "≤" を有理数全体の成す集合 Q 上に制限すれば、有理数からなる部分集合の上限は必ずしも有理数ではないから、この性質は保たれない。
X と Y 上の二項関係の左制限 (left-restriction) あるいは右制限 (right-restriction) はそれぞれ、その始集合あるいは終集合の部分集合 S に対して、その関係に属する対 (x, y) でそれぞれ x あるいは y が S の元となっているようなもの全体として得られる関係をいう。

集合と類

（集合の）恒等関係（「～に等しい」）、帰属関係（「～の元である」）、包含関係（「～の部分集合である」）といったようなある種の「関係」では、これらの関係の始集合および終集合となるべきものが公理的集合論の通常の公理系では集合とはならず、上述の意味での二項関係として理解することができないということがしばしば起こりうる。
例えば、（通常の集合論では集合にならない）「集合全体の成す集合」を始集合と終集合に持つ二項関係 “=” として「恒等関係」の一般概念のモデルを考えたいとする。この問題は、通常は（宇宙または普遍集合と呼ばれるような）「十分大きな」集合 A をとって、“=” の代わりに考える対象を A に含まれる集合だけに制限した制限関係 “=A” を考えることによって回避する（必要ならば普遍集合をさらに大きなものに取り替える）。同様に、「包含関係」⊆ も始集合と終集合をある特定の集合 A の冪集合 P(A) に制限して関係 ⊆A を考え、また同様に「帰属関係」∈ も始集合を A に終集合を P(A) に制限することで関係 ∈A が定められて問題を回避することができる。
もっと別な解決の方法として、真の類を持つような集合論、たとえばNBGやモース–ケリー集合論のようなものを考え、始域 (domain)、終域 (codomain)（およびグラフ）が（集合だけでなく）真の類であることを許すような関係を考えるというのがある。このような集合論と関係の定義であれば、先ほどの恒等関係、帰属関係、包含関係は特に注釈を入れることなくそのまま二項関係として扱うことができる（順序三つ組 (X, Y, G) の概念を考えるには少々修正が必要で、通常は真の類は順序組の元になれないものとする。もちろんこの文脈でもグラフを指示函数と同一視することは可能である）。
ほとんどの数学的な文脈では、恒等関係、帰属関係、包含関係は暗黙のうちに適当な集合に制限して考えているものとして扱って差し支えない。