互いに素な集合（数学）：定義・記法・例・応用

簡単な例

有限集合の具体例を見ると分かりやすい。集合 {1, 3} と {2, 4} は共通の要素を持たないため、互いに素である。これに対し、{1, 3} と {1, 5} は、ともに1を含むので互いに素ではない。互いに素であるという関係は対称的であり、AがBと互いに素ならば、BもAと互いに素である。

性質と記法

互いに素であることは、共通部分の条件 A ∩ B = ∅、または「AとBには共通要素がない」という表現で示される。二つを超える集合については、ペアごとに互いに素（あるいは相互に素）という語は、それらのうち異なる任意の二集合が互いに素であることを意味する。ペアごとに互いに素な集合族は、しばしば分割を記述する際に用いられる。ある集合の分割とは、和集合が元の集合全体となる、空でないペアごとに互いに素な部分集合の集まりである。

変種と関連概念

密接に関連する概念には、直和と相互排他的な事象がある。直和とは、元となる集合どうしが重なっている場合にも、その要素を区別する情報を保った集合の和である。これは代数学および圏論で一般的に用いられ、特殊な記号 ⊔ または ⨿ で表されることもある。確率論では、同時には起こり得ない事象を相互排他的であるといい、これは結果の集合が互いに素であることに対応する。

応用と意義

互いに素性は多くの数学的文脈で現れる。測度論と確率論では、互いに素な可測集合の和集合の測度は、それぞれの測度の和に等しい。組合せ論では、重複計数を避けるため、対象を互いに素な類に分割して数えることが多い。計算機科学では、互いに素な部分集合への要素の分割を効率よく追跡する互いに素集合データ構造（union–find）が、連結性やクラスタリングのためのアルゴリズムで使われる。

補足

• 標準的な集合論では、異なる空集合が二つ存在することはない。空集合は一つだけであり、あらゆる集合と互いに素である。
• 互いに素性は、数学的対象を整理し、和や計数などの操作が予測可能に振る舞うようにする、単純ながら強力な手段である。
• 集合とその演算のより広い文脈については、集合論の基礎を参照。