冪集合

出典: フリー百科事典『ウィキペディア（Wikipedia）』

べき集合（べきしゅうごう、power set）とは、 集合 S の部分集合全体のつくる集合のことである。べきは冪乗の冪（べき）と同じもので、冪集合と書くのが正確だが、一部分をとった略字としてしばしば巾集合とも書かれる。集合 S のべき集合は普通、

（ここでは 便宜上P(S) と書く）または 2^S のように表記する。2^S という表記は、S の要素数が n の場合、各要素数の有無の組み合わせによりべき集合の要素数が 2ⁿ 個になること、 あるいは同じことだが、S の部分集合 A とその定義関数（characteristic function、特性関数、指示関数などとも呼ぶ。）χ_A: S → {0, 1} すなわち

を対応づけることにより、べき集合と Map(S, {0, 1}) = {0 ,1}^S が一対一に対応することによる。

[編集] 例

S = {1, 2, 3} のとき、

P(S) = { {}, {1}, {2}, {3}, {1,2}, {2,3}, {3,1}, {1,2,3} }

で、確かに要素数は 2³ = 8 である。

べき集合の基数は元の集合の基数より常に大きい。有限集合のときにはこれは当たり前である。一般の場合は、カントールの対角線論法によって示される。

[編集] 構造

べき集合は包含関係を順序として順序集合になる。（順序集合としては複体あるいは束であり、複体としては単体、束としては完備である。）

[編集] 関連項目

• 集合