コンテンツにスキップ
メインメニュー
メインメニュー
サイドバーに移動
非表示
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
Wikippe
検索
検索
表示
ログイン
個人用ツール
ログイン
二項関係のソースを表示
ページ
議論
日本語
閲覧
ソースを閲覧
履歴を表示
ツール
ツール
サイドバーに移動
非表示
操作
閲覧
ソースを閲覧
履歴を表示
全般
リンク元
関連ページの更新状況
ページ情報
表示
サイドバーに移動
非表示
←
二項関係
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
[[数学]]において、'''二項関係'''（にこうかんけい、{{lang-en-short|''binary relation on'', }}）あるいは二変数関係 {{lang|en|(''dyadic relation'', ''2-place relation'')}} は、[[集合]] ''A'' の元からなる[[順序対]]のあつまりである。別な言い方をすれば、[[直積集合]] ''A''<sup>2</sup> = ''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''<sub>1</sub> × … × ''A''<sub>''n''</sub>（各 ''j''-番目の成分が関係の ''j''-番目の始集合 ''A''<sub>''j''</sub> からとられているような[[タプル| ''n''-組]]からなる集合）で ''n'' = 2 とした特別の場合である。 ある種の[[公理的集合論]]では（集合の一般化としての）[[類 (数学)|類]]の上の関係を考えることができる。このような拡張は、集合論における元の帰属関係や包含関係の概念（に限った話ではないが）のモデル化を、[[ラッセルの逆理]]のような論理矛盾に陥らずに行うために必要である。 == 定義 == 二項関係 ''R'' は通常、任意の[[集合]]（または[[類 (数学)|類]]）''X'', ''Y'' とそれらの[[直積集合|直積]] ''X'' × ''Y'' の[[部分集合]] ''G'' の[[タプル|順序三つ組]] (''X'', ''Y'', ''G'') として定義される。このとき、集合 ''X'' および ''Y'' はそれぞれこの関係の'''[[始集合]]''' {{lang|en|(domain)}} および'''[[終集合]]''' {{lang|en|(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'' に ''x''<sup>2</sup> を対応させるとき、終域を実数全体とするかより精密に非負の実数全体とするかによって二つの異なる写像 ''f'': '''R''' → '''R''' および ''g'': '''R''' → '''R'''<sup>+</sup> が得られる。しかし別な文脈では、写像とは単に第一成分が一意であるような順序対の集合として扱われることもある。この差異はとある自明でない問題から生じていると見ることができる。例えば、前者の立場では写像の性質として[[全射性]]を考えることができるし、一方で後者は集合を生み出す関係性として写像を捉えることができる。 この二つの異なる定義の選択が問題となるのは[[圏論]]のような極めて厳密な文脈のみであって、殆どの場面で何れの流儀であってもさほど問題となることは無いし、必要に応じて適当に用語や記法を変更してやれば、関係の制限や[[関係の合成]]、[[逆関係]]といった概念を定義することはできる。 === 例 === <!--WE MUST GET A GOOD PICTURE TO GO WITH THIS EXAMPLE--> 4つの「もの」 {ボール, 車, 人形, 拳銃} と4人の人間 {ジョン, メアリ, イアン, ヴィーナス} を想定する。ジョンはボールを所有し、メアリは人形を所有し、ヴィーナスは車を所有するが、誰も拳銃は所有しておらず、またイアンは何も所持していないものとする。このとき、「～は～に所有される」という二項関係は : ''R'' = ({ボール, 車, 人形, 拳銃}, {ジョン, メアリ, イアン, ヴィーナス}, {(ボール, ジョン), (人形, メアリ), (車, ヴィーナス)}) によって与えられる。ここで、''R'' の最初の成分は「もの」の集合、二番目の成分は人の集合、最後の三番目の成分は (もの, 所有者) の形の順序対からなる集合となっている。順序対 (ボール, ジョン) は "ボール ''R'' ジョン" と書き表され、ボールがジョンに所有されていることを示している。 二つの異なる関係がまったく同じグラフを持つことがありうる。たとえば、 : ({ボール, 車, 人形, 拳銃}, {ジョン, メアリ, ヴィーナス}, {(ボール, ジョン), (人形, メアリ), (車, ヴィーナス)}) は先ほどと異なり、全員が何かの所有者となっているが、グラフは先ほどと同じになっている。にもかかわらず, ''R'' はふつう、そのグラフ ''G''(''R'') と同一視あるいはそのものとして定義され、順序対 (''x'', ''y'') がグラフ ''G''(''R'') に属すことをしばしば "(''x'', ''y'') ∈ ''R''" と表す。 == 特殊な二項関係 == ''X'' と ''Y'' 上の二項関係のいくつか重要なクラスを以下に挙げる。 一意性条件: ; 左一意的 {{lang|en|(''left-unique'')}}<ref name=kkm/> : ''X'' の任意の元 ''x'', ''z'' と ''Y'' の任意の元 ''y'' in ''Y'' について、''x R y'' かつ ''z R y'' なるときは必ず ''x'' = ''z'' となるような関係 ''R'' は'''左一意的'''あるいは[[単射]]であるという。 ; 右一意的 {{lang|en|(''right-unique'')}}<ref name=kkm/> : ''X'' の任意の元 ''x'' と ''Y'' の任意の元 ''y'', ''z'' について、''x R y'' かつ ''x R z'' なるときは必ず ''y'' = ''z'' であるような二項関係は'''右一意的'''あるいは'''函数的''' {{lang|en|(''functional'')}}<ref>汎函数の意味の functional とは異なる</ref>であるという。このような関係は、[[部分写像]]（{{lang|en|partial function}}; 偏写像）とも呼ばれる。 ; 一対一 {{lang|en|(''one-to-one'')}} : 左一意的かつ右一意的ならば、関係は'''一対一'''であるという。 全域性条件: ; 左全域的 {{lang|en|(''left-total'')}}<ref name=kkm>Klip, Knauer and Mikhalev: p. 3</ref> : ''X'' の各元 ''x'' に対して、それぞれ ''x R y'' となるような ''y'' ∈ ''Y'' がとれるとき、 ''R'' は'''左全域的'''であるという。 : （この性質を単に、'''全域的''' {{lang|en|(''total'')}} として言及することもあるが、次節にいう'''完全性'''の意味での {{lang|en|''total''}} とは異なる概念である） ; 右全域的 {{lang|en|(''right-total'')}}<ref name=kkm/> : ''Y'' の各元 ''y'' に対してそれぞれ ''x R y'' となるような ''x'' ∈ ''X'' がとれるとき、''R'' は'''右全域的'''あるいは[[全射]]であるという。 ; [[対応 (数学)|対応]] {{lang|en|(''correspondence'')}} : 左全域的かつ右全域的な二項関係は'''対応'''と呼ばれる。 一意かつ全域性条件: ; [[写像|函数関係]] {{lang|en|(''function'')}} : 函数的かつ左全域的なる関係は'''函数関係'''または'''一意対応'''、あるいは単に'''函数'''もしくは'''写像'''であるという。 ; [[全単射]] {{lang|en|(''bijection'')}} : 一対一かつ対応となるような関係は、写像であり、'''全単射'''または'''双射'''と呼ばれる。 == 集合上の関係 == ''X'' = ''Y'' で二項関係の始集合 ''X'' と終集合 ''Y'' とが一致しているならば、簡単に ''X'' 上の二項関係（あるいはもう少し明示的に ''X'' 上の'''自己関係''' {{lang|en|(''endorelation'')}}）と呼ぶ。自己関係のいくつかのクラスについては[[有向グラフ]]として[[グラフ理論]]において広く調べられている。 集合 ''X'' 上の二項関係全体の成す集合 '''B'''(''X'') は、関係をその逆関係へ写す[[対合]]を備えた[[対合付き半群]]を成す。 集合 ''X'' 上の二項関係のいくつか重要なクラスとして、以下のようなものを挙げることができる： ; [[反射関係|反射的]] {{lang|en|(''reflexive'')}} : ''X'' の各元 ''x'' について ''x R x'' が満たされる関係 ''R'' は'''反射的'''であるという。 : 例えば「大なりイコール」"≥" は反射関係だが、「大なり」">" は反射的ではない。 ; 非反射的 {{lang|en|(''irreflexive'')}} あるいは狭義 {{lang|en|(''strict'')}} : ''X'' のどの元 ''x'' についても ''x R x'' が満たされることが無いとき、''R'' は'''非反射的'''あるいは無反射的な関係であるという。 : 「大なり」">" は非反射的関係の例である。 ; [[余反射関係|余反射的]] {{lang|en|(''coreflexive'')}} : ''X'' の各元 ''x'', ''y'' について、''x R y'' ならば ''x'' = ''y'' が成り立つとき、''R'' は'''余反射的'''であるという。 : 「等しくて奇数である」という関係は余反射関係の例を与える。 ; [[対称関係|対称的]] {{lang|en|(''symmetric'')}} : ''X'' の各元 ''x'', ''y'' について、''x R y'' ならば ''y R x'' となるような関係は'''対称'''であるという。 : 「血縁である」という関係は対称関係である。実際、''x'' が ''y'' の血縁であるための必要十分条件は ''y'' が ''x'' の血縁であることである。 ; [[反対称関係|反対称的]] {{lang|en|(''antisymmetric'')}} : ''X'' の各元 ''x'', ''y'' について、''x R y'' かつ ''y R x'' ならば ''x'' = ''y'' となるならば、関係 ''R'' は'''反対称'''であるという。 : 「大なりイコール」"≥" は ''x'' ≥ ''y'' かつ ''y'' ≥ ''x'' ならば ''x'' = ''y'' ゆえ反対称関係の例を与える。 ; [[非対称関係|非対称]] {{lang|en|(''asymmetric'')}} : ''X'' の各元 ''x'', ''y'' について、''x R y'' なるときは常に ''y R x'' が成立しないような関係 ''R'' は'''非対称'''であるという。 : 「大なり」">" は ''x'' > ''y'' ならば ''y'' > ''x'' は成立しないから非対称である。 ; [[推移関係|推移的]] {{lang|en|(''transitive'')}} : ''X'' の各元 ''x'', ''y'', ''z'' について、''x R y'' かつ ''y R z'' ならば ''x R z'' となるとき、関係 ''R'' は'''推移的'''であるという。 : 「先祖である」という関係は推移的である。実際、''x'' が ''y'' の先祖で、''y'' が ''z'' の先祖ならば、''x'' は ''z'' の先祖である。 ; [[完全関係|完全性]] {{lang|en|(''total'')}} : ''X'' の任意の二元 ''x'', ''y'' について、''x R y'' または ''y R x'' の一方あるいは両方が必ず満足されるとき、''R'' は'''完全'''であるという。 : 「大なりイコール」"≥" は完全関係の例である。本節にいう total は前節の total とは意味が異なる。 ; [[三分的関係|三分的]] {{lang|en|(''trichotomous'')}} : ''X'' の任意の元 ''x'', ''y'' に対して、''x R y'', ''y R x'', ''x'' = ''y'' のうちの何れか一つのみが成り立つとき、''R'' は'''三分的'''（三分法的）であるという。 : 「大なり」">" は三分的関係の例である。 ; [[ユークリッド関係|ユークリッド的]] {{lang|en|(''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'' となるから(右)ユークリッド関係であり、また、勿論左ユークリッド関係でもある。 ; 連続的 {{lang|en|(''serial'')}} : ''X'' の各元 ''x'' に対して、''x R y'' となるような ''y'' ∈ ''X'' がそれぞれとれるとき、関係 ''R'' は'''連続的'''であるという。 : 「大なり」">" は整数全体の成す集合 '''Z''' 上の連続的関係だが、正の整数全体の成す集合 '''N''' 上の連続的関係ではない（1 > ''y'' となるような正の整数 ''y'' は存在しない）<ref>{{cite journal|last = Yao|first = Y.Y.|coauthors = Wong, S.K.M.|title = Generalization of rough sets using relationships between attribute values|journal = Proceedings of the 2nd Annual Joint Conference on Information Sciences|year = 1995|pages = 30–33|url = http://www2.cs.uregina.ca/~yyao/PAPERS/relation.pdf}}.</ref>。一方で「小なり」"<" は '''N''' 上の（あるいは有理数全体の成す集合 '''Q''' または実数全体の成す集合 '''R''' 上の）連続的関係である。 ; 集合的 {{lang|en|(''set-like'')}} : 集合''X'' の任意の元 ''x'' に対して、''y R x'' となるような ''y'' 全体の成すクラスが集合であるような関係は、'''集合的'''（あるいは集合状、集合様）であるという。 : （これは真のクラス上の関係を認める場合でないと意味を持たない） : 順序数全体の成すクラス上の通常の順序関係 "<" は集合的関係だが、その逆順序 ">" は集合的ではない。 ; [[整礎関係|整礎的]] {{lang|en|(''well-founded'')}} : ''X'' の任意の空でない部分集合Aが極小元a(Aのどの元xもxRaとならない)を持つとき''R'' は'''整礎的'''であるという。 :自然数上の大小関係"≤"は整礎的である。[[公理的集合論|正則性公理]]を仮定すると∈は任意の集合上で整礎的である。 ; 外延的 {{lang|en|(''extensive'')}} : ''X'' の任意の元 ''x'', ''y'' について、''X'' の任意の元 ''z'' について ''zRx''⇔''zRy'' が成り立てば必ず ''x=y'' となるとき ''R'' は'''外延的'''であるという。 :全順序は外延的である。∈は任意の集合上で外延的である。 反射的、対称的かつ推移的な関係は[[同値関係]]（あるいは等値関係）と呼ばれる。反射的、反対称的かつ推移的な関係は[[半順序]]である。半順序が完全ならば[[全順序]]、単純順序、線型順序あるいは鎖などと呼ばれる<ref>Joseph G. Rosenstein, ''Linear orderings'', Academic Press, 1982, ISBN 012597680, p. 4</ref>。整礎的な線型順序は[[整列順序]]と呼ばれる。ある関係が対称、推移的かつ連続的ならば必ず反射的である。 == 二項関係に対する操作 == ''R'' が ''X'' と ''Y'' の上の二項関係ならば、次のような ''Y'' と ''X'' 上の二項関係が定まる： ; [[逆関係|逆]] {{lang|en|(''inverse'', ''converse'')}} ''R''<sup>−1</sup> : ''R''<sup>−1</sup> = {(''y'', ''x'') | (''x'', ''y'') ∈ ''R''}. : ある集合上の二項関係がその逆関係と一致することと、その関係が対称であることとは同値である（{{仮リンク|順序の双対性|en|duality (order theory)}}を参照）。 ''R'' が ''X'' 上の二項関係ならば、次のような ''X'' 上の二項関係が定義される： ; [[反射閉包]] {{lang|en|(''reflexive closure'')}} ''R''<sup>=</sup> : ''R''<sup>=</sup> = {(''x'', ''x'') | ''x'' ∈ ''X''} ∪ ''R''; : あるいは ''R'' を含む最小の反射関係。これは ''R'' を含む反射関係全ての交わりに等しい。 ; [[反射還元]] {{lang|en|(''reflexive reduction'')}} ''R''<sup>≠</sup> : ''R''<sup>≠</sup> = ''R'' \ {(''x'', ''x'') | ''x'' ∈ ''X''}; : あるいは ''X'' 上の ''R'' に含まれる最大の非反射関係。 ; [[推移閉包]] {{lang|en|''transitive closure'')}} ''R''<sup>+</sup> : ''R'' を含む ''X'' の最小の推移関係。これは、''R'' を含む推移関係全ての交わりに等しい。 ; [[推移還元]] {{lang|en|(''transitive reduction'')}} ''R''<sup>−</sup> : ''R'' と同じ推移閉包を持つ最小の関係。 ; 反射推移閉包 {{lang|en|(''reflexive transitive closure'')}} ''R''<sup>∗</sup> : ''R''<sup>∗</sup> = (''R''<sup>+</sup>)<sup>=</sup>; : ''R'' を含む最小の[[前順序]]つまり[[擬順序]](preorder)。 ; [[反射推移対称閉包]] {{lang|en|(''reflexive transitive symmetric closure'')}} ''R''<sup>≡</sup> : ''X'' 上の ''R'' を含む最小の[[同値関係]]。 ''R'' と ''S'' がともに ''X'' と ''Y'' 上の二項関係ならば、次のような関係が定義できる： ; 結び（和、{{lang|en|''union''}}）''R'' ∪ ''S'' : ''R'' ∪ ''S'' = {(''x'', ''y'') | (''x'', ''y'') ∈ ''R'' または (''x'', ''y'') ∈ ''S''}. ; 交わり（積、{{lang|en|''intersection''}}）''R'' ∩ ''S'' : ''R'' ∩ ''S'' = {(''x'', ''y'') | (''x'', ''y'') ∈ ''R'' かつ (''x'', ''y'') ∈ ''S''}. ''R'' が ''X'' と ''Y'' の上の二項関係で、''S'' が ''Y'' と ''Z'' の上の二項関係ならば、次のような ''X'' と ''Z'' 上の二項関係が定まる： ; [[関係の合成|合成]] {{lang|en|(''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'' への'''制限''' {{lang|en|(''restriction'')}} とは、その関係のグラフに属する順序対 (''x'', ''y'') で ''x'' と ''y'' がともに ''S'' に属するようなもの全体の成す集合をいう。 関係が、反射的である、非反射的である、対称である、反対称である、非対称である、推移的である、完全である、三分的である、半順序である、全順序である、狭義弱順序である、全前順序である、同値関係であるといった性質は、制限によって保たれる。 しかし、関係の制限の推移閉包はもとの関係の推移閉包の制限の部分集合とはなるが一般には一致しない。 また、[[完備 (順序集合論)|完備性]] {{lang|en|(''completeness'')}} のいくつかの概念（完全性 {{lang|en|''totalness''}} と混同してはいけない）は、制限によって遺伝しない。例えば、[[実数]]全体の成す集合 '''R''' 上で、通常の大小関係 "≤" は「'''R''' の任意の[[空集合|空]]でない部分集合 ''S'' で '''R''' に[[上界]]を持つものは '''R''' に上限（最小上界）を持つ」という性質があるが、しかし関係 "≤" を[[有理数]]全体の成す集合 '''Q''' 上に制限すれば、有理数からなる部分集合の上限は必ずしも有理数ではないから、この性質は保たれない。 ''X'' と ''Y'' 上の二項関係の'''左制限''' {{lang|en|(''left-restriction'')}} あるいは'''右制限''' {{lang|en|(''right-restriction'')}} はそれぞれ、その始集合あるいは終集合の部分集合 ''S'' に対して、その関係に属する対 (''x'', ''y'') でそれぞれ ''x'' あるいは ''y'' が ''S'' の元となっているようなもの全体として得られる関係をいう。 == 集合と類 == （集合の）恒等関係（「～に等しい」）、帰属関係（「～の元である」）、包含関係（「～の部分集合である」）といったようなある種の「関係」では、これらの関係の始集合および終集合となるべきものが[[公理的集合論]]の通常の公理系では集合とはならず、上述の意味での二項関係として理解することができないということがしばしば起こりうる。 例えば、（通常の集合論では集合にならない）「集合全体の成す集合」を始集合と終集合に持つ二項関係 "=" として「恒等関係」の一般概念のモデルを考えたいとする。この問題は、通常は（宇宙または[[普遍集合]]と呼ばれるような）「十分大きな」集合 ''A'' をとって、"=" の代わりに考える対象を ''A'' に含まれる集合だけに制限した制限関係 "=<sub>''A''</sub>" を考えることによって回避する（必要ならば普遍集合をさらに大きなものに取り替える）。同様に、「包含関係」⊆ も始集合と終集合をある特定の集合 ''A'' の[[冪集合]] ''P''(''A'') に制限して関係 ⊆<sub>''A''</sub> を考え、また同様に「帰属関係」∈ も始集合を ''A'' に終集合を ''P''(''A'') に制限することで関係 ∈<sub>''A''</sub> が定められて問題を回避することができる。 もっと別な解決の方法として、[[真の類]] {{lang|en|(proper class)}} を持つような集合論、たとえば[[フォンノイマン-ベルナイス-ゲーゲル集合論|NBG]] や[[モース-ケリー集合論]]のようなものを考え、始域 (domain)、終域 (codomain)（およびグラフ）が（集合だけでなく）真の類であることを許すような関係を考えるというのがある。このような集合論と関係の定義であれば、先ほどの恒等関係、帰属関係、包含関係は特に注釈を入れることなくそのまま二項関係として扱うことができる（順序三つ組 (''X'', ''Y'', ''G'') の概念を考えるには少々修正が必要で、通常は真の類は順序組の元になれないものとする。もちろんこの文脈でもグラフを指示函数と同一視することは可能である）。 ほとんどの数学的な文脈では、恒等関係、帰属関係、包含関係は暗黙のうちに適当な集合に制限して考えているものとして扱って差し支えない。 == 二項関係の総数 == ''n''-元集合上の相異なる二項関係の総数は 2<sup>''n''<sup>2</sup></sup> である{{OEIS|id=A002416}}。 <!-- {{number of relations}} --> Notes: * 非反射関係の総数は反射関係の総数に等しい。 * 狭義半順序関係（非反射的推移関係）の総数は半順序関係の総数に等しい。 * 狭義弱順序関係の総数は全前順序関係の総数に等しい。 * 全順序関係は半順序かつ全前順序な関係である。半順序でも全前順序でもない前順序関係の総数は、「前順序関係の総数」引く「半順序関係の総数」引く「全前順序関係の総数」足す「全順序関係の総数」となる。 * 同値関係の総数は[[集合の分割|類別]]の総数と等しく[[ベル数]]となる。 二項関係の全体は、ある関係とその補関係の対に分けることができる（ただし ''n'' = 0 のときは関係はその補関係と一致するので除く）。非対称関係の全体は、ある関係、その補関係、その逆関係、その逆補関係の四つ組に分けることができる。 == よくある二項関係の例 == * [[順序関係]]（狭義の順序を含む） ** [[不等号|小なり]] < ** 小なりイコール ≤ ** 大なり > ** 大なりイコール ≥ ** [[整除関係]] | ** [[包含関係]] ⊂, ⊆, ⊃, ⊇ * [[同値関係]] ⇔ ** [[恒等関係]] = ** （[[アフィン空間]]における）[[平行|平行関係]] ∥, ‖ ** （集合の双射による）[[対等関係]] ↔ ** [[同型]] ≅ * [[従属関係]]: 対称かつ反射的な関係 * [[独立関係]]: 対称かつ非反射的関係 {| class="wikitable" style="margin: 1ex auto 1ex auto; text-align: center;" |+ align="top"| 二項関係とその性質 |- ! 二項関係 ![[反射関係|反射的]] !! [[対称関係|対称的]] !! [[推移関係|推移的]] ! よくつかう記号 !! 例 |- ! [[有向グラフ]] | || || | → || |- ! [[無向グラフ]] | {{No}} || {{Yes}} || | || |- ! [[トーナメント (グラフ理論)|トーナメント]] | {{No}} || {{No}} || | || [[上下関係]]（つっつき順序） |- ! {{仮リンク|従属関係|en|dependency relation|label=従属}} | {{Yes}} || {{Yes}} || | || |- ! {{仮リンク|弱順序|en|weak order}} | || || {{Yes}} | ≤ || |- ! [[前順序]] | {{Yes}} || || {{Yes}} | ≤ || [[preference]] |- ! [[半順序]] | {{Yes}} || {{No}} || {{Yes}} | ≤ || [[部分集合|包含関係]] |- ! {{仮リンク|半同値関係|en|partial equivalence relation|label=半同値}} | || {{Yes}} || {{Yes}} | || |- ! [[同値関係]] | {{Yes}} || {{Yes}} || {{Yes}} | ∼, ≅, ≈, ≡ || [[等式|恒等関係]] |- ! {{仮リンク|狭義半順序|en|strict partial order}} | {{No}} || {{No}} || {{Yes}} | < || 真の包含関係 |} == 関連項目 == <div style="-moz-column-count:2; column-count:2;"> * [[合流性]]（項書き換え系） * [[ハッセ図]] * {{仮リンク|隣接構造|en|Incidence structure}} * [[Logic of relatives]] * [[順序集合論]] * [[関係代数 (数学)]] * [[三項関係]] </div> == 注釈 == {{Reflist|2}} == 参考文献 == *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. {{DEFAULTSORT:にこうかんけい}} [[Category:数学的構造]] [[Category:関係構造]] [[Category:数学に関する記事]] {{Link FA|nl}}
このページで使用されているテンプレート:
テンプレート:Cite journal
(
ソースを閲覧
)
テンプレート:Lang
(
ソースを閲覧
)
テンプレート:Lang-en-short
(
ソースを閲覧
)
テンプレート:Link FA
(
ソースを閲覧
)
テンプレート:No
(
ソースを閲覧
)
テンプレート:OEIS
(
ソースを閲覧
)
テンプレート:Reflist
(
ソースを閲覧
)
テンプレート:Yes
(
ソースを閲覧
)
テンプレート:仮リンク
(
ソースを閲覧
)
二項関係
に戻る。
検索
検索
二項関係のソースを表示
話題を追加