接続関係

数学において、集合上の関係は、その集合の全ての異なる要素のペアを一方向または他方向に関連付ける（または「比較する」）場合、連結関係、完全関係、または全関係と呼ばれます。一方、全ての要素のペアを関連付ける場合、強連結関係と呼ばれます。以下の用語のセクションで説明するように、これらの特性を表す用語は統一されていません。この「全関係」という概念は、全ての要素に対してが存在するという意味での「全関係」の概念と混同しないでください（直列関係を参照）。 ${\displaystyle x\in X}$ ${\displaystyle y\in X}$ ${\displaystyle x\mathrel {R} y}$

連結性は全順序の定義において重要な役割を果たします。全順序（または線形順序）とは、任意の2つの要素が比較可能な半順序、つまり順序​​関係が連結されている順序です。同様に、連結されている厳密な半順序は厳密な全順序です。関係が全順序となるのは、半順序かつ強連結である場合のみです。関係が厳密な全順序となるのは、厳密な半順序かつ単連結である場合のみです。厳密な全順序は、（空ドメインを除く）強連結になることはありません。

しかしながら、一部の著者は「連結」という用語をより緩い意味で使用しており、これはまさに比較可能性グラフが連結グラフである順序に適用される。これは例えばフェンスに当てはまり、そのうちの非自明な例はどれも全順序ではない。

正式な定義

集合上の関係は${\displaystyle R}$ ${\displaystyle X}$ すべてに対して接続されている場合 、または、同等に、すべてに対して接続されている場合${\displaystyle x,y\in X,}$ $${\displaystyle {\text{ }}x\neq y{\text{ ならば }}x\mathrel {R} y\quad {\text{ または }}\quad y\mathrel {R} x,}$$ ${\displaystyle x,y\in X,}$ $${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x\quad {\text{or}}\quad x=y.}$$

すべてのものに対して呼ばれる性質との関係${\displaystyle x,y\in X,}$ $${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x}$$ 強く結びついている。^[1][2][3]

用語

連結関係の概念は、主に順序の文脈で用いられ、全順序、あるいは線型順序を定義するために使用されます。この文脈では、この性質は明確に名付けられないことが多いです。むしろ、全順序は、任意の2つの要素が比較可能な半順序として定義されます。^{[4] [5]} つまり、全体的は、より一般的には、連結関係または強く連結された関係を指すために使用される。^[6]直列関係の性質とは区別する必要がある。同様に、連結関係は、完全である^[7]、これも混乱を招く可能性がある。普遍関係は完全とも呼ばれ、^[8]「完全順序理論においていくつかの他の意味がある。連結関係は完全とも呼ばれる。connex ^[9][10]またはtrichotomy^[11]trichotomyのより一般的な定義では、3 つの選択肢のうち1 つだけをという点でより強力です）。 ${\displaystyle x\mathrel {R} y,y\mathrel {R} x,x=y}$

考慮される関係が順序関係でない場合、連結であることと強く連結されていることは重要な点で異なる性質である。両者を定義する情報源では、次のような用語のペアが用いられる。弱くつながっているとつながっている、^[12] 完全と強く完全、^[13] 完全に完全、^[6] セミコネックスとコネックス、^[14]またはコネックスと厳密に連結、^[15]はそれぞれ、上で定義した連結と強く連結の概念の別名として使用されます。

特徴づけ

を同次関係とする。以下は同値である：^[14]${\displaystyle R}$

• ${\displaystyle R}$ 強く結びついています。
• ${\displaystyle U\subseteq R\cup R^{\top }}$ ;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }}$ ;
• ${\displaystyle {\overline {R}}}$ 非対称です、

ここで、は普遍的な関係であり、は逆の関係である。${\displaystyle U}$ ${\displaystyle R^{\top}}$ ${\displaystyle R.}$

以下は同等である: ^[14]

• ${\displaystyle R}$ 接続されています。
• ${\displaystyle {\overline {I}}\subseteq R\cup R^{\top }}$ ;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }\cup I}$ ;
• ${\displaystyle {\overline {R}}}$ 反対称であり、

ここで、はの相補関係、は の恒等関係、は の逆関係です。 ${\displaystyle {\overline {R}}}$ ${\displaystyle R}$ ${\displaystyle I}$ ${\displaystyle R^{\top}}$ ${\displaystyle R}$

ラッセルは進行を導入する際に接続の公理を引用した。

級数が元々推移的な非対称関係によって与えられているときはいつでも、級数の任意の 2 つの項が生成関係を持つという条件によって接続を表現できます。

— バートランド・ラッセル『数学原理』239ページ

プロパティ

• トーナメントグラフのエッジ関係^{[注 1]は常に} 'の頂点の集合上の接続関係である。${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle G}$
• 強く結びついた関係が対称的である場合、それは普遍的な関係です。
• 関係が強く連結されている場合、それは連結されており、かつ反射的である場合に限ります。^{[証明 1]}
• 集合上の連結関係は、少なくとも4つの要素を持つ場合、反推移的になることはできない。 ^[16]例えば、3要素の集合では、関係は両方の特性を持つ。${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \{a,b,c\},}$ ${\displaystyle \{(a,b),(b,c),(c,a)\}}$
• が連結関係である場合、 の全て、または１つ​​を除く全ての要素はの範囲にある。^[証明2]同様に、 の全て、または１つ​​を除く全ての要素はの領域にある。${\displaystyle R}$ ${\displaystyle X,}$ ${\displaystyle X}$ ${\displaystyle R.}$ ${\displaystyle X}$ ${\displaystyle R.}$

注記

1. グラフの辺が頂点から頂点へつながるかどうかによって正式に定義される${\displaystyle vEw}$ ${\displaystyle v}$ ${\displaystyle w}$

証明

1. only if方向の場合、両方の特性は自明に従います。 — if方向の場合: then のときは連結性から従い、 のときは反射性から従います。${\displaystyle x\neq y,}$ ${\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}$ ${\displaystyle x=y,}$ ${\displaystyle x\mathrel {R} y}$
2. とが不可能であれば、連結性から が導かれます。${\displaystyle x,y\in X\setminus \operatorname {ran} (R),}$ ${\displaystyle x\mathrel {R} y}$ ${\displaystyle y\mathrel {R} x}$ ${\displaystyle x=y}$

参考文献

1. クリストファー・クラパム、ジェームズ・ニコルソン (2014年9月18日). 「connected」. オックスフォード数学辞典（コンサイス・オックスフォード）. オックスフォード大学出版局. ISBN 978-0-19-967959-1. 2021年4月12日閲覧。
2. ニーバーゲルト、イヴ（2015年10月13日）『論理学、数学、コンピュータサイエンス：実践的応用を伴う現代的基礎』シュプリンガー、182頁。ISBN 978-1-4939-3223-8。
3. Causey, Robert L. (1994).論理、集合、再帰. Jones & Bartlett Learning. ISBN 0-86720-463-X。、135ページ
4. ポール・R・ハルモス (1968).素朴集合論. プリンストン: ノストランド. ここでは、第 14 章で、ハルモスは反射性、反対称性、推移性という名前を挙げていますが、連結性については挙げていません。
5. Patrick Cousot (1990). 「プログラム証明のための方法と論理」. Jan van Leeuwen (編).形式モデルと意味論. 理論計算機科学ハンドブック. 第B巻. Elsevier. pp.  841– 993. ISBN  0-444-88074-7。ここでは：セクション6.3、p.878
6. アリプランティス, チャラランボス D.; ボーダー, キム C. (2007-05-02).無限次元解析：ヒッチハイク・ガイド. シュプリンガー. ISBN 978-3-540-32696-0。、6ページ
7. マキンソン、デイビッド (2012年2月27日). 『集合、論理、そしてコンピューティングのための数学』 シュプリンガー. ISBN 978-1-4471-2500-6。、50ページ
8. ホワイトヘッド、アルフレッド・ノース；ラッセル、バートランド(1910). 『プリンキピア・マテマティカ』ケンブリッジ：ケンブリッジ大学出版局.
9. ウォール、ロバート・E. (1974).数理言語学入門. プレンティス・ホール.114ページ。
10. カール・ポラード. 「関係と関数」(PDF) . オハイオ州立大学. 2018年5月28日閲覧。 7ページ。
11. クネン、ケネス (2009). 『数学の基礎』カレッジ出版. ISBN 978-1-904987-14-7。24ページ
12. フィッシュバーン、ピーター・C. (2015年3月8日). 社会選択理論. プリンストン大学出版局. p. 72. ISBN 978-1-4008-6833-9。
13. Roberts, Fred S. (2009-03-12). 『測定理論：第7巻：意思決定、効用、そして社会科学への応用』ケンブリッジ大学出版局. ISBN 978-0-521-10243-8。29ページ
14. シュミット、グンター、シュトレーライン、トーマス (1993). 『関係とグラフ：コンピュータ科学者のための離散数学』 ベルリン: シュプリンガー. ISBN 978-3-642-77970-1。
15. ガンター、ベルンハルト、ヴィレ、ルドルフ (2012年12月6日).形式概念分析：数学的基礎. シュプリンガー・サイエンス＆ビジネス・メディア. ISBN 978-3-642-59830-2。86ページ
16. Jochen Burghardt (2018年6月). 二項関係の非顕著な性質に関する単純な法則（技術レポート）. arXiv : 1806.05036 . Bibcode :2018arXiv180605036B. 補題8.2、p.8。