べき集合とは？
べきしゅうごう
べき集合とは、ある集合のすべての部分集合を要素として持つ集合のことで、元の集合の要素数をnとすると2のn乗個の要素を持ちます。
べき集合（power set）とは、ある集合Sに対して、Sのすべての部分集合（空集合とS自身を含む）を要素として集めた集合のことです。Sのべき集合は「P(S)」や「2^S」と表記されます。
具体的な例を挙げると、S = {a, b, c} のとき、Sの部分集合はすべてで次の8つです。
- 空集合 ∅
- {a}、{b}、{c}
- {a, b}、{a, c}、{b, c}
- {a, b, c}
一般に、n個の要素を持つ有限集合のべき集合の要素数は2^n個になります。これは、各要素を「部分集合に含める／含めない」の二択で選ぶことができるため、2^n通りの組み合わせが生じることに由来します。
べき集合は集合論の基礎概念であるだけでなく、順序理論や位相空間論、コンピュータ科学（特に形式言語理論やアルゴリズム設計）でも重要な役割を果たします。カントールのべき集合定理は、任意の集合Sに対してP(S)のカーディナリティ（濃度）はSより常に真に大きいことを示しており、無限集合にも適用されます。この定理は無限集合の「大きさ」に階層があることを示す基礎となっています。
使い方・例文
プログラミングのアルゴリズム問題では、「与えられた集合のすべての部分集合を列挙せよ」という問題がよく登場します。これはべき集合の全要素を生成する問題で、ビット操作を用いて効率的に解くことができます。
この用語をシェア
最終更新: