素集合

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "素集合" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年9月)

2つの集合が交わりを持たない (disjoint) あるいは互いに素（たがいにそ、英語: mutually disjoint）であるとは、それらが共通の元を持たぬことをいう。一般に、与えられた集合族が互いに素（英語: pairwise disjoint）、あるいは素集合系（そしゅうごうけい、英語: disjoint sets）であるとは、その集合族に属するどの2つの集合を選んでも、その2つの共通部分が空集合であることをいう。例えば、{1, 2, 3} と {4, 5, 6} は互いに素である。

2つの集合 A と B が互いに素であるとは、それらの共通部分が空集合であること、すなわち、

${\displaystyle A\cap B=\varnothing }$

であることを意味する。

この定義は任意の個数の集合に拡張できる。集合族が互いに素であるとは、その集合族に属するどの2つの集合の共通部分も空集合であることをいう。つまり、I を添字集合として I のそれぞれの元 i について、A_i という集合が対応しているとき、集合族 {A_i : i ∈ I} が「互いに素」であるとは、i ≠ j である任意の i と j について、

${\displaystyle A_{i}\cap A_{j}=\varnothing }$

が成り立つことをいう。例えば、{ {1}, {2}, {3}, … } は互いに素な集合族である。

{A_i} が（少なくとも2つの集合を含む）互いに素な集合族であるとき、その共通部分は明らかに空集合である。すなわち、

${\displaystyle \bigcap _{i\in I}A_{i}=\varnothing }$

が成り立つ。しかし、その逆は真ではない。例えば、集合族 {{1, 2}, {2, 3}, {3, 1}} の共通部分は空集合だが、互いに素ではない（{1, 2} と {2, 3} の共通部分は {2}）。

集合 X の分割とは、その直和が X に等しい集合族のことである。すなわち、各 A_i が X の部分集合である族 {A_i : i ∈ I} であり、互いに素であると同時に

${\displaystyle \bigcup _{i\in I}A_{i}=X}$

が成り立つものである。通常は、各 A_i が空でないことを要請する。

• 互いに素
• 直和
• 素集合データ構造