2.2 幂集、笛卡尔积与基数：集合怎样构造新空间

一个服务有 read、write、delete 三项权限。单个权限集合只有三个元素，但可能的授权组合有八种。集合既能筛选已有对象，也能构造“所有子集”“所有配对”和“所有映射”的新空间。

幂集：所有子集组成的集合

集合 A 的幂集记为：

𝒫(A) = {B | B ⊆ A}

若：

A = {read, write}

则：

𝒫(A) = {
  ∅,
  {read},
  {write},
  {read, write}
}

注意层次：

read ∈ A
{read} ∈ 𝒫(A)
{read} ⊆ A

但 read 通常不是 𝒫(A) 的元素，因为幂集的元素本身是集合。

为什么 n 个元素有 2ⁿ 个子集

构造子集时，每个元素只有两个独立选择：加入或不加入。n 个元素产生：

2 × 2 × ... × 2 = 2ⁿ

也可以把每个子集编码成长度为 n 的位向量：

权限顺序：[read, write, delete]

000 -> ∅
001 -> {delete}
010 -> {write}
011 -> {write, delete}
...
111 -> {read, write, delete}

这解释了为什么 30 个彼此独立的布尔特性就有超过十亿种组合。测试策略不能指望穷举全部组合，必须利用约束、覆盖准则或生成式方法缩小空间。

下面的 Python 3 标准库例子保持权限顺序固定，用 frozenset 表示可作为其他集合元素的子集：

from itertools import product

def power_set(items):
    items = tuple(items)
    if len(set(items)) != len(items):
        raise ValueError("input must list each element exactly once")
    return [frozenset(item for item, bit in zip(items, bits) if bit)
            for bits in product([0, 1], repeat=len(items))]

permissions = ("read", "write", "delete")
subsets = power_set(permissions)
print(len(subsets), sorted(subsets[1]))  # 8 ['delete']
print(power_set([]))                    # [frozenset()]
assert len(set(subsets)) == 2 ** len(permissions)

空集也有一个子集，即它自身，所以 2⁰=1；“没有权限种类”和“没有任何授权组合”不同。例子会拒绝重复输入，否则 [read, read] 的四个位模式会重复表示同样的子集。它会实际保存全部子集，只适合小规模验证。

特征函数把子集变成布尔函数

给定 B ⊆ A，定义特征函数：

χ_B : A → {0,1}

χ_B(x) = 1  当 x ∈ B
χ_B(x) = 0  当 x ∉ B

每个子集对应一个从 A 到 {0,1} 的函数，反之亦然。因此：

𝒫(A) 与 {0,1}^A 一一对应

位图、权限掩码和布尔特征向量都利用了这种对应。编码方便不代表语义自然：超过机器字宽、权限需要层级或将来要插入新位时，还要处理版本和兼容性。

一般记号 B^A 表示从 A 到 B 的所有函数。若有限集合的大小分别是 n 和 m，每个输入独立选择一个输出，因此共有 mⁿ 个函数。空定义域恰有一个空函数；定义域非空而陪域为空时没有函数。在这个计数约定下，空集到空集对应 0⁰=1，不是对实数极限作结论。

有序对与笛卡尔积

集合无序，但有序对 (a,b) 区分第一、第二位置。通常：

(a,b) = (c,d)  ⇔  a=c ∧ b=d

集合 A 与 B 的笛卡尔积：

A × B = {(a,b) | a∈A ∧ b∈B}

例如：

A={alice,bob}
B={read,write}

A×B={
  (alice,read), (alice,write),
  (bob,read),   (bob,write)
}

一个授权关系可以是 A×B 的子集：只保留真正允许的用户与权限配对。第 5 章会把“关系就是笛卡尔积的子集”系统展开。

有限集合满足：

|A × B| = |A| · |B|

多个输入维度相乘会形成组合爆炸。配置矩阵、跨浏览器测试和参数化查询都要警惕未经约束的全笛卡尔积。

集合族与索引并交

有时要对不止两个集合运算。令集合族由索引集 I 标记，并固定 A_i ⊆ U：

{A_i | i ∈ I}

它们的并与交写作：

⋃_{i∈I} A_i = {x ∈ U | ∃i∈I, x∈A_i}
⋂_{i∈I} A_i = {x ∈ U | ∀i∈I, x∈A_i}

例如多个角色的权限并集表示用户拥有任一角色授予的权限；交集表示所有角色共同拥有的权限。

空索引集上的并集通常定义为空集；空索引集上的交集需要相对于给定论域理解为全集。这与逻辑中空析取为假、空合取为真的约定相呼应。

基数比较不只靠“数完”

有限集合的基数 |A| 是元素个数。无限集合不能逐个数完，但可以用双射比较大小。

若存在双射 f:A→B，则 A 与 B 等势，记作：

|A| = |B|

自然数集合 ℕ 与偶数集合 2ℕ 等势，因为：

f(n)=2n

它既是单射又是满射。偶数看似只占自然数“一半”，但无限基数的直觉不同于有限比例。

能与 ℕ 建立双射的集合称为可数无限。整数 ℤ 和有理数 ℚ 都可数；实数 ℝ 不可数。

Cantor 定理：幂集严格更大

对任意集合 A，不存在从 A 到 𝒫(A) 的满射，因此：

比较大小还用到单射 x ↦ {x}：A 至少可以嵌入 𝒫(A)。下面排除从 A 到 𝒫(A) 的满射，因而也排除双射，这才得到严格更大。

|A| < |𝒫(A)|

证明使用对角构造。假设 f:A→𝒫(A) 是满射，定义：

D = {x∈A | x∉f(x)}

因为假设满射，应存在 d∈A 使 f(d)=D。问 d∈D 吗？

d∈D  ⇔  d∉f(d)  ⇔  d∉D

产生矛盾，所以这样的满射不存在。

这不仅是一个技巧。它说明即使从无限集合出发，取全部子集仍得到严格更大的无限层次。

完成检查

给定 A={a,b,c}、B={0,1}：

1. 写出 𝒫(A)；
2. 用位向量为每个子集编码；
3. 写出 A×B 与 B×A，说明它们是否相等；
4. 把一个用户权限关系写成 Users×Permissions 的子集；
5. 解释为什么 20 个独立开关有 2²⁰ 种配置；
6. 用一句话说明 Cantor 对角集合 D 为什么不可能出现在 f 的值域中。

参考资料

• Open Logic Project