Loading AI tools
ウィキペディアから
数学において、二項関係(にこうかんけい、英: binary relation)あるいは二変数関係 (dyadic relation, 2-place relation) は、集合 A の元からなる順序対のあつまりである。別な言い方をすれば、直積集合 A2 = A × A の部分集合を、集合 A 上の二項関係と呼ぶ[1]。あるいはもっと一般に、二つの集合 A, B に対して、A と B との間の二項関係とは、直積 A × B の部分集合のことをいう[2]。
二項関係の一つの例は素数全体の成す集合 P と整数全体の成す集合 Z の間の整除関係である。この整除関係では任意の素数 p は、p の倍数である任意の整数 z に関係を持ち、倍数でない整数には関係しないものとして扱われる。例えば、素数 2 が関係を持つ整数には −4, 0, 6, 10 などが含まれるが 1 や 9 は含まれない。同様に素数 3 が関係する整数として 0, 6, 9 などが挙げられるが、4 や 13 はそうでない。
二項関係は数学のさまざまな分野で用いられ、不等関係、恒等関係、算術の整除関係、初等幾何学の合同関係、グラフ理論の隣接関係、線型代数学の直交関係などのさまざまな概念が二項関係として定式化することができる。また、写像の概念を特別な種類の二項関係として定義することもできる。二項関係は計算機科学においても重用される。
二項関係は n-項関係 R ⊆ A1 × ⋯ × An(各 j-番目の成分が関係の j-番目の始集合 Aj からとられているような 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 を考慮しない流儀も一般的である[2]。この場合、二項関係とは X × Y の部分集合であるグラフ G そのものをいうのに相違ない。このような立場では、対の集合{(1,2), (1,3), (2,7)} は {1, 2} を含む任意の始集合から {2, 3, 7} を含む任意の終集合への関係を表す。
この差異を、関係の特別な場合として写像の概念に適用する場合を考えよう。多くの文脈では、写像の終域と値域とを異なるものとして峻別して扱うので、ひとつの「規準」として例えば実数 x に x2 を対応させるとき、終域を実数全体 R とするか、あるいはより精密に非負の実数全体 R+ とするかによって、二つの異なる写像 f: R → R および g: R → R+ が得られる。しかし別な文脈では、写像とは単に第一成分が一意であるような順序対の集合として扱われることもある。この差異はとある自明でない問題から生じていると見ることができる。例えば、前者の立場では写像の性質として全射性を考えることができるし、一方で後者は集合を生み出す関係性として写像を捉えることができる。
この二つの異なる定義の違いが問題となるのは圏論のような極めて厳密な文脈のみであって、殆どの場面で何れの流儀であってもさほど問題となることはないし、必要に応じて適当に用語や記法を変更してやれば、関係の制限や関係の合成、逆関係といった概念を定義することができる。
4つの「もの」{ボール, 車, 人形, 拳銃} と4人の人間 {ジョン, メアリ, イアン, ヴィーナス} を想定する。ジョンはボールを所有し、メアリは人形を所有し、ヴィーナスは車を所有するが、誰も拳銃は所有しておらず、またイアンは何も所有していないものとする。このとき、「~は~に所有される」という二項関係は
によって与えられる。ここで、R の最初の成分は「もの」の集合、二番目の成分は人の集合、最後の三番目の成分は (もの, 所有者) の形の順序対からなる集合となっている。順序対 (ボール, ジョン) が R のグラフに属していることは "ボール R ジョン" と書き表され、ボールがジョンに所有されていることを示している。
二つの異なる関係がまったく同じグラフを持つことがありうる。たとえば、上の例で何も所有していなかったイアンを除外した次の関係
は先ほどと異なり、全員が何かの所有者となっているが、グラフは先ほどと同じになっている。にもかかわらず, R はふつう、そのグラフ G(R) と同一視あるいはそのものとして定義され、順序対 (x, y) がグラフ G(R) に属すことをしばしば "(x, y) ∈ R" と表す。
X と Y 上の二項関係のいくつか重要なクラスを以下に挙げる。
一意性条件:
全域性条件:
一意かつ全域性条件:
X = Y で二項関係の始集合 X と終集合 Y とが一致しているならば、簡単に X 上の二項関係(あるいはもう少し明示的に X 上の自己関係 (endorelation))と呼ぶ。自己関係のいくつかのクラスについては有向グラフとしてグラフ理論において広く調べられている。
集合 X 上の二項関係全体の成す集合 B(X) は、関係をその逆関係へ写す対合を備えた対合付き半群を成す。
集合 X 上の二項関係のいくつか重要なクラスとして、以下のようなものを挙げることができる:
反射的、対称的かつ推移的な関係は同値関係(あるいは等値関係)と呼ばれる。反射的、反対称的かつ推移的な関係は半順序である。半順序が完全ならば全順序、単純順序、線型順序あるいは鎖などと呼ばれる[5]。整礎的な線型順序は整列順序と呼ばれる。ある関係が対称、推移的かつ連続的ならば必ず反射的である。
R が X と Y の上の二項関係ならば、次のような Y と X 上の二項関係が定まる:
R が X 上の二項関係ならば、次のような X 上の二項関係が定義される:
R と S がともに X と Y 上の二項関係ならば、次のような関係が定義できる:
R が X と Y の上の二項関係で、S が Y と Z の上の二項関係ならば、次のような X と Z 上の二項関係が定まる:
R が X と Y 上の二項関係ならば、R の 補関係 S が、
として定まる。
逆関係の補関係は補関係の逆関係である。
X = Y の場合には補関係は以下の性質を持つ:
逆関係の補関係も同様の性質を持つ。
集合 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 が定められて問題を回避することができる。
もっと別な解決の方法として、真の類を持つような集合論、たとえばノイマン=ベルナイス=ゲーデル集合論やモース=ケリー集合論のようなものを考え、始域 (domain)、終域 (codomain)(およびグラフ)が(集合だけでなく)真の類であることを許すような関係を考えるというのがある。このような集合論と関係の定義であれば、先ほどの恒等関係、帰属関係、包含関係は特に注釈を入れることなくそのまま二項関係として扱うことができる(順序三つ組 (X, Y, G) の概念を考えるには少々修正が必要で、通常は真の類は順序組の元になれないものとする。もちろんこの文脈でもグラフを指示函数と同一視することは可能である)。
ほとんどの数学的な文脈では、恒等関係、帰属関係、包含関係は暗黙のうちに適当な集合に制限して考えているものとして扱って差し支えない。
n-元集合上の相異なる二項関係の総数は 2n2 であるオンライン整数列大辞典の数列 A002416。
Notes:
二項関係の全体は、ある関係とその補関係の対に分けることができる(ただし n = 0 のときは関係はその補関係と一致するので除く)。非対称関係の全体は、ある関係、その補関係、その逆関係、その逆補関係の四つ組に分けることができる。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.