二項関係

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2013年10月7日 (月) 19:45時点における130.34.248.9 (トーク)による版 (→‎特殊な二項関係)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索

数学において、二項関係（にこうかんけい、テンプレート:Lang-en-short）あるいは二変数関係 (dyadic relation, 2-place relation) は、集合 A の元からなる順序対のあつまりである。別な言い方をすれば、直積集合 A2 = 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 ⊆ A1 × … × An（各 j-番目の成分が関係の j-番目の始集合 Aj からとられているような n-組からなる集合）で n = 2 とした特別の場合である。

ある種の公理的集合論では（集合の一般化としての）類の上の関係を考えることができる。このような拡張は、集合論における元の帰属関係や包含関係の概念（に限った話ではないが）のモデル化を、ラッセルの逆理のような論理矛盾に陥らずに行うために必要である。

定義

二項関係 R は通常、任意の集合（または類）X, Y とそれらの直積 X × Y の部分集合 G の順序三つ組 (X, Y, G) として定義される。このとき、集合 X および Y はそれぞれこの関係の始集合 (domain) および終集合 (codomain) と呼ばれ、G はこの関係のグラフと呼ばれる。

R が関係であるとき、(x, y) ∈ R となることを、「x は y と R-関係を持つ」などといい、x R y や R(x, y) で表す。後者は対の集合 G の指示函数として R を見ることに対応する。

G に属する対の各要素の順番は重要で、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 に x2 を対応させるとき、終域を実数全体とするかより精密に非負の実数全体とするかによって二つの異なる写像 f: R → R および g: R → R+ が得られる。しかし別な文脈では、写像とは単に第一成分が一意であるような順序対の集合として扱われることもある。この差異はとある自明でない問題から生じていると見ることができる。例えば、前者の立場では写像の性質として全射性を考えることができるし、一方で後者は集合を生み出す関係性として写像を捉えることができる。

この二つの異なる定義の選択が問題となるのは圏論のような極めて厳密な文脈のみであって、殆どの場面で何れの流儀であってもさほど問題となることは無いし、必要に応じて適当に用語や記法を変更してやれば、関係の制限や関係の合成、逆関係といった概念を定義することはできる。

例

4つの「もの」 {ボール, 車, 人形, 拳銃} と4人の人間 {ジョン, メアリ, イアン, ヴィーナス} を想定する。ジョンはボールを所有し、メアリは人形を所有し、ヴィーナスは車を所有するが、誰も拳銃は所有しておらず、またイアンは何も所持していないものとする。このとき、「～は～に所有される」という二項関係は

R = ({ボール, 車, 人形, 拳銃}, {ジョン, メアリ, イアン, ヴィーナス}, {(ボール, ジョン), (人形, メアリ), (車, ヴィーナス)})

によって与えられる。ここで、R の最初の成分は「もの」の集合、二番目の成分は人の集合、最後の三番目の成分は (もの, 所有者) の形の順序対からなる集合となっている。順序対 (ボール, ジョン) は "ボール R ジョン" と書き表され、ボールがジョンに所有されていることを示している。

二つの異なる関係がまったく同じグラフを持つことがありうる。たとえば、

({ボール, 車, 人形, 拳銃}, {ジョン, メアリ, ヴィーナス}, {(ボール, ジョン), (人形, メアリ), (車, ヴィーナス)})

は先ほどと異なり、全員が何かの所有者となっているが、グラフは先ほどと同じになっている。にもかかわらず, R はふつう、そのグラフ G(R) と同一視あるいはそのものとして定義され、順序対 (x, y) がグラフ G(R) に属すことをしばしば "(x, y) ∈ R" と表す。

特殊な二項関係

X と Y 上の二項関係のいくつか重要なクラスを以下に挙げる。

一意性条件:

左一意的 (left-unique)[1]
X の任意の元 x, z と Y の任意の元 y in Y について、x R y かつ z R y なるときは必ず x = z となるような関係 R は左一意的あるいは単射であるという。
右一意的 (right-unique)[1]
X の任意の元 x と Y の任意の元 y, z について、x R y かつ x R z なるときは必ず y = z であるような二項関係は右一意的あるいは函数的 (functional)[2]であるという。このような関係は、部分写像（partial function; 偏写像）とも呼ばれる。
一対一 (one-to-one)
左一意的かつ右一意的ならば、関係は一対一であるという。

全域性条件:

左全域的 (left-total)[1]
X の各元 x に対して、それぞれ x R y となるような y ∈ Y がとれるとき、 R は左全域的であるという。
（この性質を単に、全域的 (total) として言及することもあるが、次節にいう完全性の意味での total とは異なる概念である）
右全域的 (right-total)[1]
Y の各元 y に対してそれぞれ x R y となるような x ∈ X がとれるとき、R は右全域的あるいは全射であるという。
対応 (correspondence)
左全域的かつ右全域的な二項関係は対応と呼ばれる。

一意かつ全域性条件:

函数関係 (function)
函数的かつ左全域的なる関係は函数関係または一意対応、あるいは単に函数もしくは写像であるという。
全単射 (bijection)
一対一かつ対応となるような関係は、写像であり、全単射または双射と呼ばれる。

集合上の関係

X = Y で二項関係の始集合 X と終集合 Y とが一致しているならば、簡単に X 上の二項関係（あるいはもう少し明示的に X 上の自己関係 (endorelation)）と呼ぶ。自己関係のいくつかのクラスについては有向グラフとしてグラフ理論において広く調べられている。

集合 X 上の二項関係全体の成す集合 B(X) は、関係をその逆関係へ写す対合を備えた対合付き半群を成す。

集合 X 上の二項関係のいくつか重要なクラスとして、以下のようなものを挙げることができる：

反射的 (reflexive)
X の各元 x について x R x が満たされる関係 R は反射的であるという。
例えば「大なりイコール」"≥" は反射関係だが、「大なり」">" は反射的ではない。
非反射的 (irreflexive) あるいは狭義 (strict)
X のどの元 x についても x R x が満たされることが無いとき、R は非反射的あるいは無反射的な関係であるという。
「大なり」">" は非反射的関係の例である。
余反射的 (coreflexive)
X の各元 x, y について、x R y ならば x = y が成り立つとき、R は余反射的であるという。
「等しくて奇数である」という関係は余反射関係の例を与える。
対称的 (symmetric)
X の各元 x, y について、x R y ならば y R x となるような関係は対称であるという。
「血縁である」という関係は対称関係である。実際、x が y の血縁であるための必要十分条件は y が x の血縁であることである。
反対称的 (antisymmetric)
X の各元 x, y について、x R y かつ y R x ならば x = y となるならば、関係 R は反対称であるという。
「大なりイコール」"≥" は x ≥ y かつ y ≥ x ならば x = y ゆえ反対称関係の例を与える。
非対称 (asymmetric)
X の各元 x, y について、x R y なるときは常に y R x が成立しないような関係 R は非対称であるという。
「大なり」">" は x > y ならば y > x は成立しないから非対称である。
推移的 (transitive)
X の各元 x, y, z について、x R y かつ y R z ならば x R z となるとき、関係 R は推移的であるという。
「先祖である」という関係は推移的である。実際、x が y の先祖で、y が z の先祖ならば、x は z の先祖である。
完全性 (total)
X の任意の二元 x, y について、x R y または y R x の一方あるいは両方が必ず満足されるとき、R は完全であるという。
「大なりイコール」"≥" は完全関係の例である。本節にいう total は前節の total とは意味が異なる。
三分的 (trichotomous)
X の任意の元 x, y に対して、x R y, y R x, x = y のうちの何れか一つのみが成り立つとき、R は三分的（三分法的）であるという。
「大なり」">" は三分的関係の例である。
ユークリッド的 (Euclidean)
X の任意の元 x, y, z について、x R y かつ x R z が成り立てば必ず y R z かつ z R y が成り立つような関係 R は右ユークリッド的であるという (通常、単に「ユークリッド的関係」とされていたら「右ユークリッド的関係」を指す)。
X の任意の元 x, y, z について、x R z かつ y R z が成り立てば必ず x R y かつ y R x が成り立つような関係 R は左ユークリッド的であるという。
恒等関係 "=" は x = y かつ x = z ならば y = z となるから(右)ユークリッド関係であり、また、勿論左ユークリッド関係でもある。
連続的 (serial)
X の各元 x に対して、x R y となるような y ∈ X がそれぞれとれるとき、関係 R は連続的であるという。
「大なり」">" は整数全体の成す集合 Z 上の連続的関係だが、正の整数全体の成す集合 N 上の連続的関係ではない（1 > y となるような正の整数 y は存在しない）[3]。一方で「小なり」"<" は N 上の（あるいは有理数全体の成す集合 Q または実数全体の成す集合 R 上の）連続的関係である。
集合的 (set-like)
集合X の任意の元 x に対して、y R x となるような y 全体の成すクラスが集合であるような関係は、集合的（あるいは集合状、集合様）であるという。
（これは真のクラス上の関係を認める場合でないと意味を持たない）
順序数全体の成すクラス上の通常の順序関係 "<" は集合的関係だが、その逆順序 ">" は集合的ではない。
整礎的 (well-founded)
X の任意の空でない部分集合Aが極小元a(Aのどの元xもxRaとならない)を持つときR は整礎的であるという。
自然数上の大小関係"≤"は整礎的である。正則性公理を仮定すると∈は任意の集合上で整礎的である。
外延的 (extensive)
X の任意の元 x, y について、X の任意の元 z について　zRx⇔zRy　が成り立てば必ず x=y となるとき R は外延的であるという。
全順序は外延的である。∈は任意の集合上で外延的である。

反射的、対称的かつ推移的な関係は同値関係（あるいは等値関係）と呼ばれる。反射的、反対称的かつ推移的な関係は半順序である。半順序が完全ならば全順序、単純順序、線型順序あるいは鎖などと呼ばれる[4]。整礎的な線型順序は整列順序と呼ばれる。ある関係が対称、推移的かつ連続的ならば必ず反射的である。

二項関係に対する操作

R が X と Y の上の二項関係ならば、次のような Y と X 上の二項関係が定まる：

逆 (inverse, converse) R−1
R−1 = {(y, x) | (x, y) ∈ R}.
ある集合上の二項関係がその逆関係と一致することと、その関係が対称であることとは同値である（テンプレート:仮リンクを参照）。

R が X 上の二項関係ならば、次のような X 上の二項関係が定義される：

反射閉包 (reflexive closure) R=
R= = {(x, x) | x ∈ X} ∪ R;
あるいは R を含む最小の反射関係。これは R を含む反射関係全ての交わりに等しい。
反射還元 (reflexive reduction) R≠
R≠ = R \ {(x, x) | x ∈ X};
あるいは X 上の R に含まれる最大の非反射関係。
推移閉包 transitive closure) R+
R を含む X の最小の推移関係。これは、R を含む推移関係全ての交わりに等しい。
推移還元 (transitive reduction) R−
R と同じ推移閉包を持つ最小の関係。
反射推移閉包 (reflexive transitive closure) R∗
R∗ = (R+)=;
R を含む最小の前順序つまり擬順序(preorder)。
反射推移対称閉包 (reflexive transitive symmetric closure) R≡
X 上の R を含む最小の同値関係。

R と S がともに X と Y 上の二項関係ならば、次のような関係が定義できる：

結び（和、union）R ∪ S
R ∪ S = {(x, y) | (x, y) ∈ R または (x, y) ∈ S}.
交わり（積、intersection）R ∩ S
R ∩ S = {(x, y) | (x, y) ∈ R かつ (x, y) ∈ S}.

R が X と Y の上の二項関係で、S が Y と Z の上の二項関係ならば、次のような X と Z 上の二項関係が定まる：

合成 (Composition) S ∘ R
S ∘ R = {(x, z) | (x, y) ∈ R かつ (y, z) ∈ S となるような y ∈ Y が存在する}.
ここで用いた S ∘ R と逆順に書いたときの R と S の順番は写像の合成の標準的な記法と一致する。正順となる R ; S と（あるいは少し紛らわしいが R ∘ S とも）書くことがある。

補関係

R が X と Y 上の二項関係ならば、R の 補関係 S が、

x S y となるのは x R y でないとき

として定まる。

逆関係の補関係は補関係の逆関係である。

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 が定められて問題を回避することができる。

もっと別な解決の方法として、真の類 (proper class) を持つような集合論、たとえばNBG やモース-ケリー集合論のようなものを考え、始域 (domain)、終域 (codomain)（およびグラフ）が（集合だけでなく）真の類であることを許すような関係を考えるというのがある。このような集合論と関係の定義であれば、先ほどの恒等関係、帰属関係、包含関係は特に注釈を入れることなくそのまま二項関係として扱うことができる（順序三つ組 (X, Y, G) の概念を考えるには少々修正が必要で、通常は真の類は順序組の元になれないものとする。もちろんこの文脈でもグラフを指示函数と同一視することは可能である）。

ほとんどの数学的な文脈では、恒等関係、帰属関係、包含関係は暗黙のうちに適当な集合に制限して考えているものとして扱って差し支えない。

二項関係の総数

n-元集合上の相異なる二項関係の総数は 2n2 であるテンプレート:OEIS。

Notes:

  • 非反射関係の総数は反射関係の総数に等しい。
  • 狭義半順序関係（非反射的推移関係）の総数は半順序関係の総数に等しい。
  • 狭義弱順序関係の総数は全前順序関係の総数に等しい。
  • 全順序関係は半順序かつ全前順序な関係である。半順序でも全前順序でもない前順序関係の総数は、「前順序関係の総数」引く「半順序関係の総数」引く「全前順序関係の総数」足す「全順序関係の総数」となる。
  • 同値関係の総数は類別の総数と等しくベル数となる。

二項関係の全体は、ある関係とその補関係の対に分けることができる（ただし n = 0 のときは関係はその補関係と一致するので除く）。非対称関係の全体は、ある関係、その補関係、その逆関係、その逆補関係の四つ組に分けることができる。

よくある二項関係の例

二項関係とその性質
二項関係 反射的 対称的 推移的 よくつかう記号 例
有向グラフ →
無向グラフ テンプレート:No テンプレート:Yes
トーナメント テンプレート:No テンプレート:No 上下関係（つっつき順序）
テンプレート:仮リンク テンプレート:Yes テンプレート:Yes
テンプレート:仮リンク テンプレート:Yes ≤
前順序 テンプレート:Yes テンプレート:Yes ≤ preference
半順序 テンプレート:Yes テンプレート:No テンプレート:Yes ≤ 包含関係
テンプレート:仮リンク テンプレート:Yes テンプレート:Yes
同値関係 テンプレート:Yes テンプレート:Yes テンプレート:Yes ∼, ≅, ≈, ≡ 恒等関係
テンプレート:仮リンク テンプレート:No テンプレート:No テンプレート:Yes < 真の包含関係

関連項目

注釈

テンプレート:Reflist

参考文献

  • M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, ISBN 3110152487.
  1. ↑ 1.0 1.1 1.2 1.3 Klip, Knauer and Mikhalev: p. 3
  2. ↑ 汎函数の意味の functional とは異なる
  3. ↑ テンプレート:Cite journal.
  4. ↑ Joseph G. Rosenstein, Linear orderings, Academic Press, 1982, ISBN 012597680, p. 4
「http://wikippe.e-do-match.com/index.php?title=二項関係&oldid=32475」から取得