# 二項関係 ## 定義 二項関係(binary relation)R は、定義域(domain)と呼ばれる集合A、余域(codomain)と呼ばれる集合B、そしてRのグラフ(graph)と呼ばれるA×Bの部分集合、の三つ組からなる。関係のグラフに (a, b) が含まれることを a R b と書く(中置記法)。二項関係の定義は関数の定義とほぼ同じだが、「定義域の各要素aについて、第一座標がaであるグラフの要素は高々1つ」という関数性の条件を課さない点が異なる——すなわち関数は二項関係の特別な場合である。関係は、定義域を左列・余域を右列に並べ、グラフの各対 (a,b) を a から b への矢印として描く関係図(relation diagram)で視覚化できる。この図を使うと、5つの基本的な性質が矢印の本数条件として統一的に定義できる: **関数**(function、「≤1本の矢印が出る」= 各定義域要素から出る矢印が高々1本)、**全射**(surjective、「≥1本の矢印が入る」= 余域の各要素に入る矢印が少なくとも1本)、**全域**(total、「≥1本の矢印が出る」= 各定義域要素から出る矢印が少なくとも1本)、**単射**(injective、「≤1本の矢印が入る」= 余域の各要素に入る矢印が高々1本)、**全単射**(bijective、「出る矢印も入る矢印もちょうど1本」= 全域かつ関数かつ全射かつ単射)。関係R: A → Bの逆関係(inverse)R⁻¹は、b R⁻¹ a iff a R b で定義されるB → Aの関係であり、関係図の矢印の向きを反転させたものに対応する。関数の場合と同様に、集合Y ⊆ Bの下でのRの像(image)R(Y)はYの要素と関係づけられる余域の要素の集合として定義され、集合X ⊆ Aの下でのR⁻¹による像は「Xの逆像(inverse image)」と呼ばれる。グラフだけからは全域性のような性質は決まらない(定義域Aに、グラフに現れない要素があるかどうかは、グラフだけでは分からない)ため、全域性・全射性の判定には定義域・余域の情報が別途必要になる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]]) ## 横断的知見 - 第4章は二項関係を「定義域A・余域B・A×Bの部分集合であるグラフ」の三つ組として定義し、有向グラフへの接続は予告にとどめていた。第9章はこの予告を回収し、「有向グラフ=定義域と余域が同じ集合である二項関係」という等式を明示する。両章を並べると、有向グラフは新しい構造ではなく、二項関係のうち定義域と余域が一致する特別な場合の**別名(視点の変更)**にすぎないことが分かる。矢印本数条件による5性質(関数・全域・全射・単射・全単射)は、有向グラフの語彙では各頂点の出次数・入次数の上限/下限として読み替えられる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) - 第4章では関係の性質として関数性(function)・全域性(total)・全射性(surjective)・単射性(injective)・全単射性(bijective)の5つが「矢印の本数」で導入されるにとどまっていたが、第9章は視点を変え、反射性・非反射性・対称性・非対称性・反対称性・推移性という別の6性質を導入し、これらの組み合わせで半順序・全順序・同値関係([[半順序]]・[[同値関係]]参照)を定義する。前者は「関数とその変種」を切り出す性質群、後者は「順序・同値」を切り出す性質群であり、二項関係という同じ土台の上に独立した2系統の分類体系が乗っている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) - 関係の合成 `R∘S`(第4章で定義)は、第9章では有向グラフの歩道関係を `G^n`(グラフ自身のn回合成)として表現するために再利用される。「合成をn回繰り返す」という操作が、関数の場合の反復適用から、有向グラフの場合は歩道をn歩伸ばす操作へとそのまま一般化されている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) ## 未解決の問い - 二項関係の5性質(関数・全域・全射・単射・全単射)は、関係合成(R∘S)や恒等関係(Id_A)を使った包含式(例: Rが関数 iff R∘R⁻¹ ⊆ Id_B)としても表現できると章末問題(Problem 4.32)で示唆されている。この代数的な表現と、矢印の本数条件による定義の等価性はどこまで一般化できるか。 ## 関連 - 概念: [[関数]] / [[集合]] / [[濃度]] / [[有向グラフ]] / [[半順序]] / [[同値関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 4.