互いに素な2つの集合

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

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

[編集]

集合の素集合

集合族がペアワイズ素と呼ばれる場合、微妙に異なる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 番目の定義ではペアワイズ互いに素ではありません。

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

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

交差

2つの集合、または集合族の互いに素であることは、それらのペアの 交差によって表現できます。

2つの集合AとBは、それらの交差が空集合である場合に限り、素集合です。[1] この定義から、すべての集合は空集合と素であり、空集合は自身と素である唯一の集合であることが分かります。[5]

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

空の集合族はペアごとに互いに素です。[6]

ヘリー族とは、空の共通部分を持つ部分族のみが対ごとに素であるような集合の体系です。例えば、実数の閉区間はヘリー族を形成します。閉区間の族が空の共通部分を持ち、それが最小である場合（つまり、族のどの部分族も空の共通部分を持たない場合）、それは対ごとに素でなければなりません。[7]

素和と分割

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

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

参照

参考文献

  1. ^ ab Halmos, PR (1960), 素朴集合論, Undergraduate Texts in Mathematics , Springer, p. 15, ISBN 9780387900926 {{citation}}：ISBN / 日付の非互換性（ヘルプ）。
  2. ^ ab Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95, ISBN 978-0-495-56202-3。
  3. ^ Halbeisen, Lorenz J. (2011), 組合せ集合論：強制力への優しい入門, Springer monographs in math, Springer, p. 184, ISBN 978144712​​1732。
  4. ^ コプソン、エドワード・トーマス（1988年）『計量空間』、ケンブリッジ数学トラクト第57巻、ケンブリッジ大学出版局、62ページ、ISBN 9780521357326。
  5. ^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA teachings, Mathematical Association of America, p. 59, ISBN 9780883857793。
  6. ^ 「空集合族は互いに素か？」Mathematics Stack Exchange . 2024年10月10日閲覧
  7. ^ Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038。
  8. ^ ab Halmos (1960), p. 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. ^ ケビン・ファーランド (2008)、『離散数学：証明と組合せ論入門』、Cengage Learning、p. 45、ISBN 9780618415380。
  12. ^ マイケル・A・アービブ、AJ・クフォーリー、ロバート・N・モル（1981年）『理論計算機科学の基礎』、AKMシリーズ『理論計算機科学：計算機科学のテキストとモノグラフ』、シュプリンガー・フェアラーク、9ページ、ISBN 9783540905738。
  13. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471。
  14. ^ Lee, John M. (2010), Introduction to Topological Manifolds , Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407。