関係（数学）

数学において、関係とは、集合内の2 つのオブジェクト間の何らかの関係を表すもので、成り立つ場合もそうでない場合もあります。^[1]たとえば、「は より小さい」は自然数の集合上の関係です。この関係は、たとえば値1と3の間( 1 < 3と表記)、同様に3と4 の間 ( 3 < 4と表記) に成立しますが、値3と1 の間や4と4 の間では成立しません。つまり、3 < 1と4 < 4は両方とも false と評価されます。別の例として、「は の姉妹である」はすべての人の集合上の関係であり、たとえばMarie CurieとBronisława Dłuskaの間で成立し、同様にその逆も同様です。集合のメンバーは「ある程度」関係にあるとは限りません。つまり、関係にあるか、ないかのどちらかです。

正式には、集合X上の関係Rは、 Xの要素の順序付きペア( x、y )の集合と見なすことができます。^[2] ( x、y )がRの要素である場合、xとy の間に 関係R が成り立ちます。たとえば、自然数上の関係「は より小さい」は、 (1,3)と(3,4)の両方を含み、(3,1)と(4,4)のどちらも含まない自然数のペアの無限集合R_{より小さいです}。1桁の自然数の集合上の 関係「は の非自明な約数である」は_{、ここに示すことができるほど十分に小さいです。R dv} = { (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) }。例えば、2 は8の非自明な約数ですが、その逆は当てはまりません。したがって、(2,8) ∈ R _dvですが、(8,2) ∉ R _{dv です}。

R がxとyについて成り立つ関係である場合、 xRyと書くことが多い。数学における最も一般的な関係については、特別な記号が導入されている。たとえば、 「より小さい」には「 <」、「 は の非自明な約数である」には「 | 」 、「 に等しい」には最も一般的な「 = 」などである。たとえば、「1 < 3」、「1は3より小さい」、および「(1,3) ∈ R_{より小さい}」はすべて同じ意味であり、「(1,3) ∈ (<)」と書く著者もいる。

関係のさまざまな特性が調査されます。関係Rは、 xRx がすべてのxに対して成り立つ場合、反射的であり、xRx がどのxに対しても成り立たない場合、非反射的です。 xRy が常にyRx を意味する場合、対称的であり、xRy がyRxが不可能であることを意味する場合、非対称的です。 xRyとyRz が常にxRz を意味する場合、推移的です。たとえば、「より小さい」は、非反射的、非対称的、推移的ですが、反射的でも対称的でもありません。「の姉妹」は推移的ですが、反射的 (たとえば、ピエール・キュリーは自分の姉妹ではありません)、対称的でも非対称的でもありませんでした。非反射的かどうかは定義の問題かもしれませんが (すべての女性は自分の姉妹ですか?)、「の先祖」は推移的ですが、「の親」は推移的ではありません。 「推移的関係は、非対称である場合にのみ非反射的である」など、関係プロパティの組み合わせに関する数学的定理が知られています。

特に重要なのは、特定の性質の組み合わせを満たす関係です。半順序は反射的、反対称的、推移的な関係です。^[3] 同値関係は反射的、対称的、推移的な関係です。^[4] 関数は右一意かつ左全である関係です（下記参照）。^{[5] [6]}

関係は集合なので、和集合、積集合、補集合などの集合演算を使って操作することができ、集合代数を導くことができる。さらに、関係の計算には、逆関係をとったり、関係を合成したりする演算が含まれる。^{[7] [8] [9]}

上記の関係の概念^[a]は、2 つの異なる集合のメンバー間の関係 (幾何学におけるすべての点の集合とすべての直線の集合の間の「は上にある」のような異質関係)、3 つ以上の集合間の関係 ( 「人x は時刻zに町yに住んでいる」のような有限関係)、およびクラス間の関係^[b] (すべての集合のクラス上の「は の要素である」のような、二項関係 § 集合とクラス を参照) を認めるように一般化されています。

集合Xが与えられたとき、 X上の関係R はXの要素の順序付きペアの集合であり、正式にはR ⊆ { ( x , y ) | x , y ∈ X }となる。^{[2] [10]}

( x , y ) ∈ R は「xはyとRに関連している」という意味で、中置記法ではxRyと書きます 。^{[7] [8]}要素の順序は重要です。x ≠ yの場合、yRx はxRyとは関係なく真または偽になります。たとえば、3 は9 を割り切れますが、9 は3 を割り切れません。

有限集合X上の関係R は次のように表すことができます。

• 有向グラフ: Xの各要素は頂点に対応します。xからyへの有向辺は、 ( x , y ) ∈ Rの場合にのみ存在します。
• ブール行列: Xの要素はx ₁ , ..., x _nの固定された順序で並べられます。行列の次元はn × nで、 i行j列の要素は、もし( x _i , x _j ) ∈ Rであり、、 さもないと。
• 2D プロット: ブール行列の一般化として、実数の無限集合R上の関係を2 次元の幾何学的図形として表すことができます。直交座標を使用して、( x , y ) ∈ Rの場合は常に( x , y )に点を描きます。

有限集合X上の推移的^[c]関係Rは次のようにも表される。

• ハッセ図: Xの各要素は頂点に対応します。有向辺は、( x , y ) ∈ Rの場合にのみxからyへの有向パスが存在するように描画されます。有向グラフ表現と比較すると、ハッセ図では必要な辺が少なくなり、画像の複雑さが軽減されます。「xからyへの有向パスが存在する」という関係は推移的であるため、ハッセ図では推移的な関係のみを表現できます。通常、図はすべての辺が上方向を向くようにレイアウトされ、矢印は省略されます。

例えば、 12の約数集合上で、関係R _divを次のように 定義する。

x がyの約数であり、 x ≠ yである場合、 x R _div y となります。

正式には、X = { 1, 2, 3, 4, 6, 12 }かつR _div = { (1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) } です。 R _divのブール行列としての表現は中央の表に示されています。ハッセ図と有向グラフの両方としての表現は左の図に示されています。

以下は同等です:

• x R _div y は真です。
• ( x , y ) ∈ R _divです。
• R _{div を}表すハッセ図には、xからyへのパスが存在します。
• R _{div を}表す有向グラフにはxからyへのエッジが存在します。
• R _divを表すブール行列では、行x、列yの要素は「「」。

別の例として、 R上の関係R _elを次のように 定義します。

x ² + xy + y ² = 1の場合、 xは成り立ち_ます。

R _elを2D プロットとして表現すると楕円が得られます (右の図を参照)。Rは有限ではないため、有向グラフ、有限ブール行列、ハッセ図のいずれもR _{el を}表すために使用できません。

集合X上の関係Rが持つ可能性のある重要な特性には次のようなものがあります。

反射的

すべてのx ∈ Xに対してxRx が成り立ちます。たとえば、≥ は反射関係ですが、> はそうではありません。

非反射的（または厳密）

すべてのx ∈ Xに対して、xRxではありません。たとえば、> は非反射的な関係ですが、≥はそうではありません。

前の 2 つの選択肢は網羅的ではありません。たとえば、下の図に示す赤い関係y = x ²は、ペア(0,0)を含みますが、ペア(2,2)を含まないため、非反射的でも反射的でもありません。

対称的

すべてのx、y ∈ Xについて、xRyならばyRx。たとえば、「は〜の血縁者である」は対称関係です。なぜなら、x がyの血縁者であるためには、 yがxの血縁者である必要があるからです。

反対称

すべてのx、y ∈ Xに対して、xRyかつyRxならばx = y。たとえば、≥ は反対称関係であり、> も同様だが、意味をなさない（定義内の条件は常に偽である）。^[11]

非対称

すべてのx、y ∈ Xに対して、xRyならばyRxではない。関係が非対称となるのは、反対称かつ非反射的な場合のみである。^[12]たとえば、> は非対称関係だが、≥ はそうではない。

繰り返しますが、前の 3 つの選択肢は、網羅的ではありません。自然数の例として、x > 2で定義される関係xRyは、対称 (たとえば、5 R 1だが、1 R 5ではない) でも反対称 (たとえば、6 R 4だが、 4 R 6でもある) でもなく、ましてや非対称ではありません。

推移的

すべてのx、y、z ∈ Xに対して、xRyかつyRzならばxRz。推移関係は、非対称である場合にのみ非反射的である。^{[13]たとえば、「} 〜の祖先である」は推移関係であるが、「〜の親である」は推移関係ではない。

接続

すべてのx、y ∈ Xに対して、x ≠ yであればxRyまたはyRxです。たとえば、自然数では、<は接続されていますが、「は の約数です」は接続されていません (たとえば、5 R 7でも7 R 5でもありません)。

強く結びついた

すべてのx、y ∈ X、xRy、yRxに対して。たとえば、自然数では、≤ は強く連結されていますが、< は強く連結されていません。関係が強く連結されているのは、それが連結かつ反射的である場合のみです。

一意性プロパティ:

単射^[d]（左一意性^[14]とも呼ばれる）

すべてのx、y、z ∈ Xについて、xRyかつzRyであればx = zです。たとえば、図の緑と青の関係は単射ですが、赤の関係は単射ではありません ( −1と1 の両方が1に関連しているため)。黒の関係も単射ではありません ( −1と1 の両方が0に関連しているため)。

関数型^{[15] [16] [17] [d]}（右一意型^[14] 、右確定型^[18]、一価型^[9]とも呼ばれる）

すべてのx、y、z ∈ Xについて、xRyかつxRzであればy = zです。このような関係は部分関数と呼ばれます。たとえば、図の赤と緑の関係は関数的ですが、青の関係は関数的ではありません ( 1 を-1と1 の両方に関連付けるため)。また、黒の関係も関数的ではありません ( 0 を -1 と 1 の両方に関連付けるため)。

全体の特性:

シリアル^[d]（トータルまたは左トータルとも呼ばれる）

すべてのx ∈ Xに対して、 xRyとなるy ∈ Xが存在する。このような関係は多価関数と呼ばれる。たとえば、図の赤と緑の関係は完全だが、青の関係は完全ではない（−1 をどの実数にも関連付けていないため）。黒の関係も完全ではない（2をどの実数にも関連付けていないため）。別の例として、> は整数上の直列関係である。しかし、正の整数上の直列関係ではない。なぜなら、1 > yとなるような正の整数にはy が存在しないからである。^[19]しかし、< は正の整数、有理数、実数上の直列関係である。すべての反射関係は直列である。つまり、与えられたxに対して、 y = xを選択する。

全射^[d]（右全^[14]または全射とも呼ばれる）

すべてのy ∈ Yに対して、 xRyとなるx ∈ Xが存在します。たとえば、図の緑と青の関係は射影的ですが、赤の関係は射影的ではありません (どの実数も-1に関連しないため)。黒の関係も射影的ではありません (どの実数も2に関連しないため)。

上記の特性の特定の組み合わせを満たす関係は特に有用であるため、独自の名前が付けられています。

同値関係

反射的、対称的、推移的な関係。これらの特性は反射性を意味するため、対称的、推移的、直列的な関係でもあります。

注文:

部分的な順序

反射的、反対称的、推移的な関係。

厳密な半順序

非反射的、非対称的、推移的な関係。

合計注文

反射的、反対称的、推移的、連結的な関係。^[20]

厳密な全順序

非反射的、非対称的、推移的、かつ連結的な関係。

一意性プロパティ:

一対一^[d]

単射かつ関数的。たとえば、図の緑の関係は 1 対 1 ですが、赤、青、黒の関係は 1 対 1 ではありません。

一対多^[d]

単射であり、関数的ではありません。たとえば、図の青い関係は 1 対多ですが、赤、緑、黒の関係はそうではありません。

多対一^[d]

関数的であり、単射的ではありません。たとえば、図の赤い関係は多対一ですが、緑、青、黒の関係は多対一ではありません。

多対多^[d]

単射でも関数的でもない。たとえば、図の黒い関係は多対多ですが、赤、緑、青の関係はそうではありません。

一意性と全体性の特性:

関数^[d ]

機能的かつ完全な関係。たとえば、図の赤と緑の関係は関数ですが、青と黒の関係は関数ではありません。

注射^[d ]

単射的な関数。たとえば、図の緑の関係は単射ですが、赤、青、黒の関係は単射ではありません。

一射影^[d]

全射的な関数。たとえば、図の緑の関係は全射ですが、赤、青、黒の関係は全射ではありません。

一対一^[d ]

単射かつ全射である関数。たとえば、図の緑の関係は全単射ですが、赤、青、黒の関係は全単射ではありません。

連合^[e]

RとS がX上の関係である場合、R ∪ S = { ( x、y ) | xRyまたはxSy }はRとSの和集合関係です。この演算の単位元は空の関係です。たとえば、≤ は<と=の和集合であり、≥ は>と=の和集合です。

交差点^[e]

RとS がX上の関係である場合、R ∩ S = { ( x、y ) | xRyおよびxSy }はRとSの交差関係です。この演算の単位元は普遍関係です。たとえば、「同じスートの下位のカードである」は、「下位のカードである」と「同じスートに属する」の交差です。

構成^[e]

RとSがX上の関係である場合、S ∘ R = { ( x , z ) | y ∈ Xが存在し、xRyおよびySz } ( R ; Sとも表記) はRとSの相対積になります。恒等元は恒等関係です。ここで使用されている表記S ∘ RにおけるRとSの順序は、関数の合成の標準的な表記順序と一致しています。たとえば、「〜の母親である」∘ 「 〜の親である」という合成は「〜の母方の祖父母である」となり、一方、「〜の親である」∘「〜の母である」という合成は「〜の祖母である」となります。前者の場合、x がyの親であり、y がzの母親である場合、x はzの母方の祖父母です。

コンバース^[e]

R が集合XとY上の関係である場合、R ^T = { ( y , x ) | xRy }はYとX上のRの逆関係です。たとえば、= はそれ自身の逆であり、≠ も同様です。また、 <と> は互いの逆であり、 ≤と≥ も同様です。

補語^[e]

R がX上の関係である場合、R = { ( x , y ) | x , y ∈ XかつxRyではない} ( Rまたは¬ Rとも表記) はRの補関係です。たとえば、=と≠は互いに補関係であり、⊆と⊈、⊇と⊉、∈と∉も同様です。また、全順序については、<と≥、>と≤も同様です。逆関係R ^Tの補関係は、補関係の逆です。 ${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

制限^[e]

RがX上の関係であり、SがXの部分集合である場合、R _{| S} = { ( x , y ) | xRyかつx , y ∈ S }はRからSへの制約関係。式R _{| S} = { ( x , y ) | xRyかつx ∈ S }はRからSへの左制約関係。式R ^{| S} = { ( x , y ) | xRyかつy ∈ S }は、RからSへの右制限関係。関係が反射的、非反射的、対称的、反対称的、非対称的、推移的、全的、三分的、部分順序、全順序、厳密な弱い順序、全前順序(弱い順序)、または同値関係である場合、その制限も同様です。ただし、制限の推移閉包は推移閉包の制限のサブセットです。つまり、一般には等しくありません。たとえば、「xはyの親である」という関係を女性に制限すると、「 xは女性yの母親である」という関係が生成されます。この推移閉包は、女性を父方の祖母に関連付けません。一方、「〜の親である」の推移閉包は「〜の先祖である」であり、女性に制限すると、女性を父方の祖母に関連付けます。

集合XとYの関係Rは、R がSの部分集合である場合、つまりすべてのx ∈ Xおよびy ∈ Yに対して、 xRyならばxSyである場合、 R ⊆ Sと表記される関係SにXおよびY上。RがSに含まれ、 SがRに含まれる場合、 RとS は等しいとされ、 R = Sと表記されます。RがSに含まれるがS がRに含まれない、 RはSより小さく、 R ⊊ Sと書きます。たとえば、有理数、関係> は≥より小さく、合成> ∘ >。

• 関係が非対称となるのは、反対称かつ非反射的である場合のみです。
• 推移的な関係は、非対称である場合にのみ、非反射的です。
• 関係が反射的であるのは、その補関係が非反射的である場合のみです。
• 関係が強く結びついているのは、それが連結され反射的である場合のみです。
• 関係が対称的である場合に限り、その関係はその逆の関係に等しくなります。
• 関係が接続されるのは、その補関係が反対称関係である場合のみです。
• 関係が強く結びついているのは、その補関係が非対称である場合のみである。^[21]
• 関係Rが関係Sに含まれる場合、
  • Rが再帰的、連結的、強く連結的、左合計的、または右合計的である場合、 Sも同様です。
  • Sが非反射的、非対称的、反対称的、左一意的、または右一意的である場合、 Rも同様です。
• 関係は、その逆がそれぞれ反射的、非反射的、対称的、非対称的、反対称的、連結的、強く連結的、推移的である場合に、それぞれ該当します。

• 厳密な順序を含む順序関係:
  • より大きい
  • より大きいか等しい
  • 未満
  • 以下
  • 均等に分割する
  • サブセット​
• 同値関係:
  • 平等
  • と平行（アフィン空間の場合）
  • は単射である
  • 同型
• 許容関係、反射的かつ対称的な関係:
  • 依存関係、有限許容関係
  • 独立関係、依存関係の補完関係
• 親族関係

上記の関係の概念は、2つの異なる集合のメンバー間の関係を認めるように一般化されている。集合XとY が与えられたとき、XとY上の異種関係 Rは{ ( x、y ) | x ∈ X、y ∈ Y }のサブセットである。^{[2] [22]} X = Y のとき、上記の関係の概念が得られる。これは、その一般化と区別するために、同種関係（または内接関係）^{[23] [24]と呼ばれることが多い。それぞれ「 [d]}」および「^[e]」でマークされた上記の特性および演算は、異種関係に一般化される。異種関係の例としては、「海x は大陸yに接する」が挙げられる。最もよく知られている例は、 sqrt : N → R ₊などの、異なる定義域と値域を持つ関数^[f]である。

• 発生構造、点と線の集合間の異質な関係
• 秩序理論は、秩序関係の性質を研究する。
• 関係代数