幂集

在集合论中，集合 $S$ 的幂集是以 $S$ 的所有子集为元素的集合。它既包含空集，也包含 $S$ 本身。幂集通常记作 $\mathcal P(S)$，它将一组对象转化为由这些对象的所有可能选取方式组成的集合。幂集是研究集合、函数以及不同大小的无穷的一种基本构造。(plato.stanford.edu)

定义与示例

形式化定义为

因此，$A\in\mathcal P(S)$ 当且仅当 $A$ 的每个元素都属于 $S$。必须区分属于关系与包含关系：$S$ 的一个子集是其幂集的一个元素，而不是 $S$ 的另一个元素。(web.stanford.edu)

例如，若 $S=\{a,b,c\}$，则

共有八个子集，其中包括含零个元素和含三个元素的子集。特别地，

它并非空集，而是含有一个元素的集合。原集合本身总是属于其幂集，因为 $S\subseteq S$。这些例子都可以直接由定义得出。(web.stanford.edu)

有限集合的幂集基数

若 $S$ 含有 $n$ 个元素，则其幂集的基数为

对于每个元素，都有选入或不选入两种选择，而所有元素的选择结果唯一确定一个子集。也可以用数学归纳法证明这个公式：加入一个新元素后，子集的数量会加倍，因为每个原有子集都对应两个子集，一个不含新元素，另一个含有新元素。归纳的基础情形为 $2^0=1$。(cs.cornell.edu)

还可以按子集的大小进行计数：

其中，$\binom nk$ 表示恰好含有 $k$ 个元素的子集的数量。这个等式是二项式定理的一个特例，可通过展开 $(1+1)^n$ 得到。(cs.pomona.edu)

特征函数与二进制表示

每个子集 $A\subseteq S$ 都确定一个示性函数，也称特征函数：

反过来，任何这样的函数都确定一个子集，即函数值为 $1$ 的所有元素组成的集合。由此可在 $\mathcal P(S)$ 与所有函数 $S\to\{0,1\}$ 组成的集合之间建立一个双射函数，这也解释了幂集的另一种记法 $2^S$。这一对应关系保持了子集上的布尔运算与真值函数上的布尔运算。(home.uni-leipzig.de)

对于元素按固定顺序排列的有限集合，这些函数可以表示为比特串。$1$ 表示选入，$0$ 表示不选入。对于 $S=(a,b,c)$，比特串 $101$ 表示 $\{a,c\}$。将这些比特串读作二进制数，就可以通过从 $0$ 数到 $2^n-1$ 来枚举所有子集。(ics.uci.edu)

无限集合与康托尔定理

康托尔定理指出，每个集合的基数都严格小于其幂集的基数：

映射 $s\mapsto\{s\}$ 给出了一个从 $S$ 到 $\mathcal P(S)$ 的单射函数。关键结论在于，不存在从 $S$ 到 $\mathcal P(S)$ 的满射函数。(math.arizona.edu)

康托尔对角线论证通过考察任意函数 $f:S\to\mathcal P(S)$，并定义

来证明这一点。若 $f$ 是满射，则存在某个 $d\in S$，满足 $f(d)=D$。但这样就有

产生矛盾。因此，$D$ 是一个不在 $f$ 的像中的子集。这一论证对有限集合和无限集合都适用。(math.arizona.edu)

因此，自然数集的幂集不是可数集。反复取幂集会得到越来越大的无限基数，所以不存在最大的无穷大小。(math.arizona.edu)

序与代数结构

集合的包含关系在 $\mathcal P(S)$ 上定义了一个偏序。配备并、交以及相对于 $S$ 的补集运算后，幂集构成一个布尔代数。空集是其中的最小元，$S$ 是最大元；并与交分别对应析取与合取，取补集则对应否定。在特征函数表示下，这些运算变为逐点进行的布尔运算。(home.uni-leipzig.de)

对于含有 $n$ 个元素的有限集合，由此得到的偏序结构通常记作 $B_n$。其各层按子集的基数划分，空集位于最底层，整个集合位于最顶层。(math.mit.edu)

基础与应用

在策梅洛—弗兰克尔集合论中，幂集公理保证任意给定集合的所有子集组成一个集合。幂集也用于生成累积层级的后继阶段：

在极限阶段，则对此前各阶段取并集。(plato.stanford.edu)

在概率论中，事件属于一个包含于样本空间幂集的σ代数。对于离散模型，所有子集都可以作为事件。连续模型通常采用一个较小的 σ代数，从而无须为每个子集都赋予概率，也能一致地定义概率。(math.cmu.edu)

在计算领域，算法可以通过比特模式枚举有限集合的幂集。不过，对于含有 $n$ 个元素的输入，仍有 $2^n$ 个输出：即使紧凑地表示每个子集，也无法减少完整枚举所必须生成的、数量呈指数增长的子集。(web.eecs.utk.edu)