非結合集合

数学と形式論理学における集合論では、 2つの集合に共通の要素がない場合、それらの集合は互いに素な集合であると言われます。同様に、2つの互いに素な集合とは、その共通部分が空集合である集合のことです。^[1]たとえば、{1, 2, 3}と{4, 5, 6}は互いに素な集合ですが、 {1, 2, 3}と{3, 4, 5}は互いに素ではありません。2つ以上の集合の集合は、その集合の任意の2つの異なる集合が互いに素である場合に互いに素であると呼ばれます。

一般化

この非素集合の定義は、集合族やインデックス付き集合族に拡張できます。定義により、集合のコレクションは集合族と呼ばれます(たとえば、べき集合など)。情報源によっては、これは集合の集合ですが、他の情報源では、一部の集合が繰り返される集合の多重集合である場合もあります。インデックス付き集合族は 、定義により、集合値関数(つまり、その定義域内のすべての要素に集合を割り当てる関数) であり、その定義域はインデックス集合と呼ばれます(その定義域の要素はインデックスと呼ばれます)。 $\left(A_{i}\right)_{i\in I},$ $A_{i}$ $i\in I$ $I$

集合の族がペアワイズディスジョイントと呼ばれる場合の定義には、微妙に異なる 2 つの方法があります。 1 つの定義によると、集合の族内の 2 つの集合がそれぞれ同一またはディスジョイントである場合、その集合はディスジョイントです。この定義では、ペアワイズディスジョイントの集合の族が同じ集合のコピーを繰り返し持つことができます。別の定義によると、集合の族内の 2 つの集合はそれぞれディスジョイントでなければならず、コピーの繰り返しは許可されません。同じ 2 つの定義をインデックス付き集合の族に適用できます。最初の定義によると、集合の族内の 2 つの異なるインデックスはすべてディスジョイントまたは同一の集合を指定する必要がありますが、2 番目の定義によると、2 つの異なるインデックスはすべてディスジョイントの集合を指定する必要があります。^[2]たとえば、集合族{ {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... } は、両方の定義によれば互いに素であり、整数の2つのパリティクラスの族{ {..., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} }も同様です。ただし、10 個のメンバーを持つ族には、互いに素な 2 つの集合がそれぞれ 5 回繰り返されるため、最初の定義ではペアワイズ互いに素ですが、2 番目の定義ではペアワイズ互いに素ではありません。 ${\mathcal {F}}$ $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$

2つの集合の交差が何らかの意味で小さい場合、それらの集合はほぼ互いに素な集合であると言われる。例えば、交差が有限集合である2つの無限集合は、ほぼ互いに素であると言える。^[3]

位相幾何学では、分離集合の概念は、互いに素であることよりも厳しい条件で様々に存在します。例えば、2つの集合が互いに素な閉包や互いに素な近傍を持つ場合、それらの集合は分離しているとみなされます。同様に、距離空間では、正に分離した集合とは、非ゼロの距離で分離された集合です。^[4]

交差点

2 つの集合または集合族の非重複性は、それらのペアの交差によって表現できます。

2つの集合AとBは、それらの共通部分が空集合である場合に限り、互いに素である。^[1] この定義から、すべての集合は空集合と互いに素であり、空集合はそれ自身と互いに素である唯一の集合であることが分かる。^[5] $A\cap B$

集合に少なくとも 2 つの集合が含まれている場合、集合が互いに素であるという条件は、集合全体の交差が空であることを意味します。ただし、集合の集合は互いに素でなくても交差が空になることがあります。さらに、2 つ未満の集合の集合は比較するペアがないため自明に互いに素ですが、1 つの集合の集合の交差はその集合と等しくなり、その集合は空でない可能性があります。^[2]たとえば、3 つの集合{ {1, 2}、{2, 3}、{1, 3} }には交差が空ですが、互いに素ではありません。実際、この集合には互いに素な 2 つの集合は存在しません。また、空の集合族はペアごとに互いに素です。^[6]

ヘリー族は、交差が空である部分族のみが対ごとに互いに素である集合のシステムである。例えば、実数の閉区間はヘリー族を形成する。閉区間の族が交差が空であり、かつそれが最小である（すなわち、族のどの部分族も交差が空ではない）場合、それは対ごとに互いに素でなければならない。^[7]

分離した結合と分割

集合 Xの分割とは、互いに素な空でない集合の集まりで、その和集合がX となるものである。^{[8]すべての分割は、}同値関係、つまり、分割内の 2 つの要素が同じ集合に属しているかどうかを記述する二項関係によって同等に記述することができる。 ^[8] 素集合データ構造^[9]と分割改良^[10]は、それぞれ 2 つの集合を結合する和集合演算、または 1 つの集合を 2 つに分割する改良演算の対象である集合の分割を効率的に維持するためのコンピュータサイエンスの 2 つの手法である。

非結合和集合は、2 つの意味のいずれかになります。最も単純な意味は、非結合である集合の和集合です。^[11]しかし、2 つ以上の集合がすでに非結合でない場合は、それらの非結合和集合は、それらの集合を非結合に修正してから修正された集合の和集合を形成することによって形成されます。^[12]たとえば、2 つの集合は、各要素を、その要素と、それが最初の集合に属するか 2 番目の集合に属するかを示す 2 進値との順序付きペアに置き換えることによって非結合にすることができます。^[13] 2 つ以上の集合の族の場合、同様に、各要素を、その要素と、それを含む集合のインデックスとの順序付きペアに置き換えることができます。^[14]

参照

非交差凸集合に対する超平面分離定理
相互に排他的なイベント
互いに素な数、素因数が互いに交わらない数
セパロイド
セットパッキング、集合族の最大の互いに素な部分族を見つける問題

参考文献

^ ab Halmos, PR (1960)、Naive Set Theory、Undergraduate Texts in Mathematics、Springer、p. 15、ISBN 9780387900926。
^ ab スミス、ダグラス; エゲン、モーリス; セントアンドレ、リチャード (2010)、「上級数学への移行」、Cengage Learning、p. 95、ISBN 978-0-495-56202-3。
^ ハルベイゼン、ロレンツ J. (2011)、組合せ集合論：強制への優しい入門、シュプリンガー数学モノグラフ、シュプリンガー、p. 184、ISBN 9781447121732。
^ コプソン、エドワード・トーマス（1988）、メトリック空間、ケンブリッジ数学論文集、第57巻、ケンブリッジ大学出版局、62ページ、ISBN 9780521357326。
^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012)、Bridge to Abstract Mathematics、MAA 教科書、アメリカ数学協会、p. 59、ISBN 9780883857793。
^ 「空の集合族はペアワイズで素ですか？」Mathematics Stack Exchange 。 2024年10月10日閲覧。
^ ボロバス、ベラ（1986）、組合せ論：集合システム、ハイパーグラフ、ベクトル族、および組合せ確率、ケンブリッジ大学出版局、p. 82、ISBN 9780521337038。
^ ab Halmos (1960)、28ページ。
^ コーメン、トーマス H. ;レイソン、チャールズ E. ;リベスト、ロナルド L. ;スタイン、クリフォード(2001)、「第 21 章: 分離集合のデータ構造」、アルゴリズム入門(第 2 版)、MIT プレス、pp. 498–524、ISBN 0-262-03293-7。
^ ペイジ、ロバート; タージャン、ロバート E. (1987)、「3 つのパーティション改良アルゴリズム」、SIAM Journal on Computing、16 (6): 973–989、doi :10.1137/0216062、MR 0917035、S2CID 33265037。
^ Ferland, Kevin (2008)、離散数学：証明と組合せ論入門、Cengage Learning、p. 45、ISBN 9780618415380。
^ Arbib, Michael A.; Kfoury, AJ; Moll, Robert N. (1981)、「理論計算機科学の基礎」、理論計算機科学の AKM シリーズ: 計算機科学のテキストとモノグラフ、Springer-Verlag、p. 9、ISBN 9783540905738。
^ モナン、ジャン・フランソワ、ヒンチー、マイケル・ジェラード（2003）、形式手法の理解、シュプリンガー、p. 21、ISBN 9781852332471。
^ Lee, John M. (2010)、「位相多様体入門」、Graduate Texts in Mathematics、vol. 202 (第2版)、Springer、p. 64、ISBN 9781441979407。

外部リンク

Weisstein、Eric W.「Disjoint Sets」。MathWorld。

[halmos-1] Halmos, PR (1960)、Naive Set Theory、Undergraduate Texts in Mathematics、Springer、p. 15、ISBN 9780387900926。

[douglas-2] スミス、ダグラス; エゲン、モーリス; セントアンドレ、リチャード (2010)、「上級数学への移行」、Cengage Learning、p. 95、ISBN 978-0-495-56202-3。

[3] ハルベイゼン、ロレンツ J. (2011)、組合せ集合論：強制への優しい入門、シュプリンガー数学モノグラフ、シュプリンガー、p. 184、ISBN 9781447121732。

[4] コプソン、エドワード・トーマス（1988）、メトリック空間、ケンブリッジ数学論文集、第57巻、ケンブリッジ大学出版局、62ページ、ISBN 9780521357326。

[5] Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012)、Bridge to Abstract Mathematics、MAA 教科書、アメリカ数学協会、p. 59、ISBN 9780883857793。

[6] 「空の集合族はペアワイズで素ですか？」Mathematics Stack Exchange 。 2024年10月10日閲覧。

[7] ボロバス、ベラ（1986）、組合せ論：集合システム、ハイパーグラフ、ベクトル族、および組合せ確率、ケンブリッジ大学出版局、p. 82、ISBN 9780521337038。

[h60-28-8] Halmos (1960)、28ページ。

[9] コーメン、トーマス H. ;レイソン、チャールズ E. ;リベスト、ロナルド L. ;スタイン、クリフォード(2001)、「第 21 章: 分離集合のデータ構造」、アルゴリズム入門(第 2 版)、MIT プレス、pp. 498–524、ISBN 0-262-03293-7。

[10] ペイジ、ロバート; タージャン、ロバート E. (1987)、「3 つのパーティション改良アルゴリズム」、SIAM Journal on Computing、16 (6): 973–989、doi :10.1137/0216062、MR 0917035、S2CID 33265037。

[11] Ferland, Kevin (2008)、離散数学：証明と組合せ論入門、Cengage Learning、p. 45、ISBN 9780618415380。

[12] Arbib, Michael A.; Kfoury, AJ; Moll, Robert N. (1981)、「理論計算機科学の基礎」、理論計算機科学の AKM シリーズ: 計算機科学のテキストとモノグラフ、Springer-Verlag、p. 9、ISBN 9783540905738。

[13] モナン、ジャン・フランソワ、ヒンチー、マイケル・ジェラード（2003）、形式手法の理解、シュプリンガー、p. 21、ISBN 9781852332471。

[14] Lee, John M. (2010)、「位相多様体入門」、Graduate Texts in Mathematics、vol. 202 (第2版)、Springer、p. 64、ISBN 9781441979407。