冪集合

ファイル:Hasse diagram of powerset of 3.svg

S = {x, y, z} の冪集合 P(S) = { {}, {x}, {y}, {z}, {x, y}, {y, z}, {z, x}, {x, y, z} } のハッセ図。要素数は 2³ = 8 である。

冪集合（べきしゅうごう、テンプレート:Lang-en-short）とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。べきは冪乗の冪（べき）と同じもので、冪集合と書くのが正確だが、一部分をとった略字としてしばしば巾集合とも書かれる。

集合と呼ぶべき対象を公理的に構成的に与える公理的集合論では、集合から作った冪集合が集合と呼ばれるべきもののうちにあることを公理の一つ（冪集合公理）としてしばしば提示する。

記法

集合 <math>S</math> の冪集合は、冪を表す power からとって、通常は

<math>\mathfrak P(S),\ \mathcal P(S),\ \mathfrak{pow}(S),\ \mathrm{Power}(S),\ \Pi(S)</math>, ℙ(S), ℘(S), 2^S

などのように記される。2^S という表記は S の元の数が n の場合、冪集合の元の数が 2ⁿ 個になることによる（後述）。

定義

集合 <math>S</math> が与えられたとき、<math>S</math> のどの部分集合をも元とする集合

<math>\mathfrak P(S) := \{A\colon\mbox{a set} \mid A \subseteq S\}</math>

を <math>S</math> の冪集合と呼ぶ。例えば

• <math>\mathfrak P(\varnothing) = \{\varnothing\}</math>
• <math>\mathfrak P(\{a\}) = \{\varnothing, \{a\}\}</math>
• <math>\mathfrak P(\{x,y\}) = \{\varnothing, \{x\}, \{y\}, \{x,y\}\}</math>
• <math>\mathfrak P(\{1,2,3\}) = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}</math>

などとなる。空集合の冪集合は空集合を唯一つの元として持つ一元集合であり、空集合とは別のものである。

構造

包含関係による順序

冪集合は包含関係を順序として順序集合になる。冪集合を底となる集合、包含関係を順序とする順序集合 <math>(\mathcal P(S), \subset)</math> （ここでの <math>\subset</math> は集合が一致する場合も含む）に順序同型な順序集合は単体様半順序集合 (simplex-like Poset) と呼ばれ、単体の一つの組合せ論的な特徴づけを与える（底となる <math>\mathcal P(S)</math> から空集合を抜いた順序集合を指すこともある）。また、冪集合 <math>\mathcal P(S)</math> に包含関係と逆の順序 <math>\subset^{\mathrm{opp}}</math>

<math>A \subset^{\mathrm{opp}} B \iff A \supset B</math>

を与えた順序集合 <math>(\mathcal P(S), \subset^{\mathrm{opp}})</math> は、もとの順序集合 <math>(\mathcal P(S), \subset)</math> に順序同型で、その対応は補集合をとる操作

<math>(\mathcal P(S),\subset^{\mathrm{opp}}) \ni A \ \stackrel{\simeq}{\longmapsto}\ A^c = S\smallsetminus A \in (\mathcal P(S),\subset)</math>

によって与えられる。またこの対応で、集合の結びと交わりが互いに入れ替わる（双対性：ド・モルガンの法則）、対称差は不変（自己双対性）などを見て取ることができる。

順序集合 <math>(\mathcal P(S), \subset)</math> の部分集合である集合族

<math>\mathfrak{M} \subset \mathcal P(S)</math>

が与えられたとき、集合族の結びや交わりをとる操作

<math>\sup(\mathfrak{M}) = \bigcup \mathfrak{M} = \bigcup_{m\in\mathfrak{M}}m,

\quad \inf(\mathfrak{M}) = \bigcap \mathfrak{M} = \bigcap_{m\in\mathfrak{M}}m</math> は、この集合族に対して包含関係による順序に関する上限と下限を与える。とくに、<math>S</math> の二つの部分集合 <math>A, B</math> について

<math>A\vee B := \sup\{A,B\} = A\cup B</math>

<math>A\wedge B := \inf\{A,B\} = A\cap B</math>

を考えることにより、組 <math>(\mathcal P(S), \land, \lor)</math> は完備な束となる。完備束の条件は空で無い部分集合族に対する上限・下限の存在を要求するものであるが、冪集合の束では集合族 <math>\mathfrak M \subset \mathcal P(S)</math> が空集合であるときにも

<math>\sup(\varnothing) = \varnothing,\quad \inf(\varnothing) = S</math>

が冪集合 <math>\mathcal P(S)</math> の中に存在する。

集合代数系

テンプレート:Main

冪集合に定義される様々な集合演算は、冪集合を代数系として取り扱う手段を与えてくれる。たとえば、集合の結び <math>\cup</math> や交わり <math>\cap</math> は交換可能で結合的な演算であるから、半群として冪集合を見ることができる。さらに、結びに関する中立元は空集合 <math>\emptyset</math> であり、全体集合 <math>S</math> が交わりに関する中立元となるので、<math>(\mathcal P(S), \cup, \emptyset)</math> や <math>(\mathcal P(S), \cap, S)</math> はモノイドである。また、対称差 <math>\Delta</math> を与えられた演算とする代数系 <math>(\mathcal P(S), \Delta)</math> は、空集合を単位元とし、補集合を逆元にもつ群になる。

結び <math>\cup</math> と交わり <math>\cap</math> は互いに他に対して分配的であるので、<math>(\mathcal P(S), \cup, \cap)</math> に環の構造を見て取ることができる。とくに冪集合 <math>\mathcal P(S)</math> を、集合の結び、交わり、補集合をとる操作および結び・交わりそれぞれに関する中立元を備えた代数系

<math>(P(S), \cap, \cup, ^\mathrm{c}, \varnothing, S)</math>

と考えたものはブール代数の例を与える。一方、事実として、任意の有限ブール代数は有限集合のべき集合が作るこのブール代数によって同型的に実現することができる。

冪集合の濃度

S の部分集合 A とその指示関数 χ_A: S → {0, 1} すなわち

<math>\chi_A(x) := \begin{cases}

 1 & \mbox{if } x \in A \\
 0 & \mbox{if } x \notin A

\end{cases}</math> を対応づけることにより、冪集合 2^S と Map(S, {0, 1}) = {0 ,1}^S が一対一に対応する。これは、S の元 a が部分集合 A に属するとき 1、属さないとき 0 をラベル付けすることで部分集合 A が特定できるということに対応する。したがって特に A の濃度 card(A) が有限の値 n であるとき冪集合 2^A の濃度 card(2^A) は 2^card(A) = 2ⁿ に等しい。一般に、有限集合 E から有限集合 F への写像の総数は card(F)^card(E) となり、このことは E から F への写像全体のなす集合を F^E と記す（無限集合の場合にも記号を流用する）ことの根拠の一つとなっている。そして、冪集合やその濃度の2の冪としての記法はこれの特別の場合にあたる。

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

関連項目

• 集合
• 族 (数学)
• ブール代数
• 連続体濃度
• 連続体仮説