冪集合

同義語：power set

概要

冪集合（power set）とは、集合 $X$ の部分集合をすべて集めた集合 $\mathcal P(X)$ である。
集合を一段上から眺め、その部分集合自身を元として扱うための基本概念である。部分集合の選択は各元を選ぶか選ばないかの二択なので、有限集合では元の個数が指数的に増える。

定義

部分集合の全体

集合 $X$ に対し、$X$ の部分集合の全体からなる集合
$$ \mathcal{P}(X):=\{A\mid A\subseteq X\} $$
を $X$ の冪集合（power set）という。$2^{X}$ とも書く。$\emptyset\in\mathcal{P}(X)$ かつ $X\in\mathcal{P}(X)$ である。

例と反例

小さな集合の冪集合

$X=\{1,2\}$ なら
$$ \mathcal P(X)=\{\emptyset,\{1\},\{2\},\{1,2\}\} $$
である。空集合については $\mathcal P(\emptyset)=\{\emptyset\}$ であり、空集合そのものとは異なる。前者は空集合を一つの元としてもつ一元集合である。

元と部分集合の区別

$X=\{\emptyset,1\}$ とする。このとき $\emptyset\in X$ かつ $\emptyset\subseteq X$ であるため、$\emptyset$ は $X$ の元であると同時に $\mathcal P(X)$ の元でもある。一方、$\{1\}\subseteq X$ なので $\{1\}\in\mathcal P(X)$ だが、$\{1\}\notin X$ である。
この例は、$x\in X$ と $\{x\}\subseteq X$、さらに $\{x\}\in\mathcal P(X)$ を区別する必要があることを示す。記号 $\in$ は元であること、$\subseteq$ は部分集合であることを表し、同じ意味ではない。

冪集合を繰り返すと階層が一段ずつ上がる。たとえば
$$ \mathcal P(\emptyset)=\{\emptyset\},\qquad \mathcal P(\mathcal P(\emptyset))=\{\emptyset,\{\emptyset\}\} $$
である。特に $\emptyset$、$\{\emptyset\}$、$\{\{\emptyset\}\}$ は互いに異なる集合である。

基本性質

有限集合の冪集合の濃度

$X$ が $n$ 個の元をもつ有限集合ならば、$\mathcal P(X)$ は $2^n$ 個の元をもつ。

有限集合の冪集合の濃度の証明

各部分集合 $A\subseteq X$ に対し、各 $x\in X$ を $A$ に入れるか入れないかを選ぶ。$n$ 個の元ごとに二つの選択肢があり、異なる選択列は異なる部分集合を定めるので、全部で $2^n$ 個である。$\square$

別の数え方として、ちょうど $k$ 個の元をもつ部分集合は $\binom nk$ 個ある。部分集合を大きさごとに分けると
$$ |\mathcal P(X)|=\sum_{k=0}^{n}\binom nk=(1+1)^n=2^n $$
となる。この分解は、冪集合が「部分集合をすべて集める」という定義と二項定理を結びつける。

冪集合による包含の判定

集合 $A,B$ について、$A\subseteq B$ であることと $\mathcal P(A)\subseteq\mathcal P(B)$ であることは同値である。

冪集合による包含の判定の証明

$A\subseteq B$ とし、$C\in\mathcal P(A)$ とする。$C\subseteq A\subseteq B$ だから $C\in\mathcal P(B)$ である。逆に $\mathcal P(A)\subseteq\mathcal P(B)$ とすると、$A\in\mathcal P(A)$ なので $A\in\mathcal P(B)$、すなわち $A\subseteq B$ である。$\square$

部分集合と特性写像

集合 $X$ と二元集合 $\mathbf 2=\{0,1\}$ に対し、$\mathcal P(X)$ と写像全体の集合 $\mathbf2^X$ の間に標準的な全単射
$$ \mathcal P(X)\longrightarrow\mathbf2^X, \qquad A\longmapsto\chi_A $$
がある。ただし
$$ \chi_A(x)= \begin{cases} 1&x\in A,\\ 0&x\notin A \end{cases} $$
である。このため冪集合を $2^X$ とも書く。

特性写像との全単射の証明

$A=B$ なら明らかに $\chi_A=\chi_B$ である。逆に $\chi_A=\chi_B$ なら、任意の $x\in X$ について
$$ x\in A\Longleftrightarrow\chi_A(x)=1 \Longleftrightarrow\chi_B(x)=1 \Longleftrightarrow x\in B $$
なので、外延性により $A=B$ である。従って対応は単射である。
任意の写像 $u\colon X\to\mathbf2$ に対し $A_u:=\{x\in X:u(x)=1\}$ とおけば $u=\chi_{A_u}$ である。従って対応は全射でもある。

集合演算の構造

$\mathcal P(X)$ には包含関係に加えて、和集合、共通部分、補集合という演算がある。これらは論理演算と対応する。
$$ \chi_{A\cap B}(x)=\min\{\chi_A(x),\chi_B(x)\},\qquad \chi_{A\cup B}(x)=\max\{\chi_A(x),\chi_B(x)\}, $$
$$ \chi_{X\setminus A}(x)=1-\chi_A(x). $$
従って包含順序のもとで、$\emptyset$ は最小元、$X$ は最大元、任意の集合族 $(A_i)_{i\in I}$ の上限は $\bigcup_{i\in I}A_i$、下限は $\bigcap_{i\in I}A_i$ である。

冪集合は完備Boolean代数である

$\mathcal P(X)$ は和集合を上限、共通部分を下限、$X\setminus A$ を補元とする完備Boolean代数である。特に任意の $A\subseteq X$ と集合族 $(B_i)_{i\in I}$ に対し
$$ A\cap\bigcup_{i\in I}B_i =\bigcup_{i\in I}(A\cap B_i) $$
が成り立つ。

完備Boolean代数であることの証明

$(A_i)_{i\in I}$ を $X$ の部分集合族とする。$I\neq\emptyset$ なら和集合と共通部分はともに $X$ の部分集合であり、それぞれ包含関係について最小上界と最大下界になる。$I=\emptyset$ のときは
$$ \bigcup_{i\in\emptyset}A_i=\emptyset, \qquad \bigcap_{i\in\emptyset}A_i=X $$
と定める。これらはそれぞれ $\mathcal P(X)$ の最小元と最大元なので、空族についても上限と下限を与える。さらに
$$ A\cup(X\setminus A)=X,\qquad A\cap(X\setminus A)=\emptyset $$
なので $X\setminus A$ は $A$ の補元である。分配律を示すには各 $x\in X$ の所属を調べればよい。実際、
$$ x\in A\cap\bigcup_{i\in I}B_i $$
であることは、$x\in A$ かつ、ある $i\in I$ について $x\in B_i$ であることと同値であり、これはある $i\in I$ について $x\in A\cap B_i$ であること、すなわち右辺への所属と同値である。

写像と冪集合

写像 $f\colon X\to Y$ は、部分集合を前向きに送る像(写像)と、後ろ向きに引き戻す逆像という二つの操作を定める。
$$ f_*\colon\mathcal P(X)\to\mathcal P(Y),\quad A\mapsto f(A), $$
$$ f^*\colon\mathcal P(Y)\to\mathcal P(X),\quad B\mapsto f^{-1}(B). $$
像は任意の和集合を保つが、一般には共通部分や補集合を保たない。逆像は任意の和集合、任意の共通部分、補集合をすべて保つ。この違いは、像では異なる元が同じ値へ移る可能性があるのに対し、逆像では所属条件を合成しているだけであることに由来する。

像と逆像の随伴関係

$A\subseteq X$、$B\subseteq Y$ に対し
$$ f(A)\subseteq B \quad\Longleftrightarrow\quad A\subseteq f^{-1}(B) $$
が成り立つ。

像と逆像の随伴関係の証明

$f(A)\subseteq B$ とする。$x\in A$ なら $f(x)\in f(A)\subseteq B$ なので、$x\in f^{-1}(B)$ である。従って $A\subseteq f^{-1}(B)$ である。
逆に $A\subseteq f^{-1}(B)$ とする。$y\in f(A)$ なら、ある $x\in A$ が存在して $y=f(x)$ である。仮定から $x\in f^{-1}(B)$、従って $f(x)=y\in B$ である。ゆえに $f(A)\subseteq B$ である。

この同値は、像が包含順序について逆像の左随伴であることを表す。また、恒等写像と合成について
$$ (\operatorname{id}_X)_*=\operatorname{id}_{\mathcal P(X)},\qquad (g\circ f)_*=g_*\circ f_*, $$
$$ (\operatorname{id}_X)^*=\operatorname{id}_{\mathcal P(X)},\qquad (g\circ f)^*=f^*\circ g^* $$
が成り立つ。像による操作は写像と同じ向き、逆像による操作は反対向きに進む。

Cantorの定理

任意の集合 $X$ に対し、全射 $f\colon X\to\mathcal P(X)$ は存在しない。したがって冪集合は $X$ より真に大きい濃度をもつ。

Cantorの定理の証明

全射 $f\colon X\to\mathcal P(X)$ があると仮定し、
$$ D:=\{x\in X\mid x\notin f(x)\} $$
とおく。$D\in\mathcal P(X)$ だから、全射性より $f(d)=D$ となる $d\in X$ がある。すると $d\in D$ と $d\notin f(d)=D$ が同値になり矛盾する。$\square$

反例：冪集合は和集合をそのまま保たない

$A=\{1\}$、$B=\{2\}$ とすると、$\{1,2\}\in\mathcal P(A\cup B)$ だが $\{1,2\}\notin\mathcal P(A)\cup\mathcal P(B)$ である。したがって一般に $\mathcal P(A\cup B)\neq\mathcal P(A)\cup\mathcal P(B)$ である。

反例：$X$ と $\mathcal P(X)$ の元数が同じになることはない

無限集合について「両方とも無限だから同じ大きさかもしれない」と考えることはできない。Cantorの定理は $X\to\mathcal P(X)$ の全射を否定する。一方、$x\mapsto\{x\}$ は $X\to\mathcal P(X)$ の単射なので、濃度の意味で
$$ |X|<|\mathcal P(X)| $$
である。この厳密な増大を反復すると、$X,\mathcal P(X),\mathcal P(\mathcal P(X)),\ldots$ はすべて異なる濃度をもつ。

用途

冪集合は、位相、測度、確率、論理、組合せ論の共通の土台である。位相は $\mathcal P(X)$ の部分集合 $\mathcal O\subseteq\mathcal P(X)$ で、任意和と有限共通部分について閉じたものとして定義される。$\sigma$-代数も $\mathcal P(X)$ の部分集合であり、補集合と可算和について閉じている。二項関係は $X\times Y$ の部分集合、単純グラフの辺集合は二元部分集合を集めた $\mathcal P(X)$ の部分集合として表せる。
一方、冪集合は「部分集合をすべて集める」ため非常に大きい。有限集合でも元数は $n$ から $2^n$ へ増える。アルゴリズムで全部分集合を列挙するときに指数時間が現れるのは、この大きさそのものによる。
定義、集合演算、写像による像と逆像については Hara20（第1章 §§1.1--1.3、第3章 §§3.1--3.2）、Matsusaka68（第1章 §§1--4, pp. 1--41）を参照した。