冪集合(べきしゅうごう)とは、ある集合の部分集合をすべて集めた集合です。元の要素を集め直すのではなく、選び方そのものを要素として扱います。記号ではP(A)などと表します。
二つの具材から作るトッピング
A={チーズ、きのこ}とします。選び方は「どちらも選ばない」「チーズだけ」「きのこだけ」「両方」の四つです。したがってP(A)={∅,{チーズ},{きのこ},{チーズ,きのこ}}です。
どちらも選ばない場合の空集合と、全部を選ぶ場合のA自身も部分集合です。集合では要素の順序を区別しないため、「チーズ、きのこ」と「きのこ、チーズ」を二つに数えません。
- チーズ:元の集合Aの要素
- {チーズ}:Aの部分集合で、P(A)の要素
- P(A):選び方の集まり。空集合も一つの選び方として含む
有限集合なら、個数は2のn乗
要素がn個あると、それぞれを「入れる」「入れない」の二通りから選びます。独立したn個の選択なので、部分集合は2ⁿ個です。三つの要素なら8個、四つなら16個になります。
ここで、要素の重複や順番を数える問題とは区別が必要です。例えば同じ具を何個でも選べる注文や、料理の盛り付け順まで区別する問題は、この単純な冪集合の数え方とは条件が違います。
無限集合でも、元より大きくなる
カントールの定理によると、どんな集合AでもP(A)はAより大きい濃度を持ちます。Aの要素aを一要素集合{a}へ送れば、AをP(A)の中に重複なく対応させることはできます。しかし、P(A)全体を尽くす全射は作れません。
仮にf:A→P(A)が全射だとし、D={a∈A | a∉f(a)}を作ります。全射ならf(d)=Dとなるdがあるはずです。するとd∈Dなら定義からd∉Dとなり、d∉Dならd∈Dとなります。どちらでも矛盾するので、その全射は存在しません。
ラッセルのパラドックスとの関係
自分自身を含むかどうかで反転する形は、ラッセルのパラドックスとよく似ています。ただしここでは、すでにある集合Aの中から条件を満たす要素を取り出しています。「あらゆる集合の集合」を無制限に作っているわけではありません。
冪集合を繰り返し作ると、より大きな濃度へ進めます。「無限」という一語でひとまとめにせず、無限の間にも大きさの違いがあると分かる、印象的な概念です。