关于利用bijective principle证明集合族|𝔸|与|𝔹|基数相等的方法咨询

问题背景 #

给定集合 $X = {1,2,\dots,n}$，以及两个集合族：

• $\mathscr{A} = {A\subseteq X \mid n\notin A}$（X中所有不含元素n的子集）
• $\mathscr{B} = {A\subseteq X \mid n\in A}$（X中所有包含元素n的子集）

你需要利用双射原理证明 $|\mathscr{A}| = |\mathscr{B}|$，但目前不知道如何入手使用双射原理解决这类问题。

双射原理的核心思路 #

先明确：两个集合的基数（元素个数）相等的充要条件是存在一个从其中一个集合到另一个集合的双射函数——也就是同时满足“单射”（不同输入对应不同输出）和“满射”（每个输出都有对应的输入）的函数。简单来说，就是要找到一种规则，能把$\mathscr{A}$里的每个子集和$\mathscr{B}$里的子集一一配对，没有重复也没有遗漏。

具体构造与证明步骤 #

我们可以直接构造一个$\mathscr{A}$到$\mathscr{B}$的双射函数：

1. 定义函数：对于任意$A \in \mathscr{A}$（即$A$是X的子集且不含n），令
   $$f(A) = A \cup {n}$$
   显然$f(A)$包含元素n，所以$f(A) \in \mathscr{B}$，这个函数是合法的。

2. 证明f是单射：
   假设$f(A_1) = f(A_2)$，即$A_1 \cup {n} = A_2 \cup {n}$。
   因为$A_1$和$A_2$都不含n，我们可以在等式两边同时去掉元素n，得到$A_1 = A_2$。
   这说明不同的输入对应不同的输出，满足单射的定义。

3. 证明f是满射：
   任取一个$B \in \mathscr{B}$（即B包含n），我们令$A = B \setminus {n}$（也就是从B中去掉元素n）。
   显然$A$不含n，所以$A \in \mathscr{A}$，而且$f(A) = A \cup {n} = (B \setminus {n}) \cup {n} = B$。
   这说明$\mathscr{B}$里的每个元素都能找到对应的原像，满足满射的定义。

结论 #

因为我们找到了一个从$\mathscr{A}$到$\mathscr{B}$的双射函数$f$，根据双射原理，就可以直接得出$|\mathscr{A}| = |\mathscr{B}|$。

刚开始接触这类问题的时候，确实容易不知道怎么构造双射——其实核心就是观察两个集合的元素差异（这里就是是否包含n），然后基于这个差异设计一个“转换规则”，再验证这个规则是双射就可以了。

备注：内容来源于stack exchange，提问作者Michele