冪集合とは?集合の「部分集合すべて」を集めると、なぜ大きくなるのか

冪集合(べきしゅうごう)とは、ある集合の部分集合をすべて集めた集合です。元の要素を集め直すのではなく、選び方そのものを要素として扱います。記号ではP(A)などと表します。

二つの具材から作るトッピング

A={チーズ、きのこ}とします。選び方は「どちらも選ばない」「チーズだけ」「きのこだけ」「両方」の四つです。したがってP(A)={∅,{チーズ},{きのこ},{チーズ,きのこ}}です。

どちらも選ばない場合の空集合と、全部を選ぶ場合のA自身も部分集合です。集合では要素の順序を区別しないため、「チーズ、きのこ」と「きのこ、チーズ」を二つに数えません。

要素と部分集合は、階層が違う
  1. チーズ:元の集合Aの要素
  2. {チーズ}:Aの部分集合で、P(A)の要素
  3. 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の中から条件を満たす要素を取り出しています。「あらゆる集合の集合」を無制限に作っているわけではありません。

冪集合を繰り返し作ると、より大きな濃度へ進めます。「無限」という一語でひとまとめにせず、無限の間にも大きさの違いがあると分かる、印象的な概念です。

関連する用語

参考資料