2.4 集合的基数

基数 Cardinality
可数集合
不可数集合

基数¶

定义¶

集合A和集合B有相同的 基数（cardinality） ，当且仅当存在从 $A$ 到 $B$ 的一个一一对应（bijecction）。记作，$|A| = |B|$

如果存在一个从 $A$ 到 $B$ 的一对一函数，则 $A$ 的基数小于或等于 $B$ 的基数，并写成 $|A| \leq |B|$。再者，$|A| \leq |B|$ 且 $A$ 和 $B$ 基数不同或不存在一一对应，则说明 $A$ 的基数小于 $B$ 的基数，$|A| < |B|$

命题¶

\[ |A|=|B| \ \ and \ \ |B|=|C| \Rightarrow |A|=|C| \]

\[ |A| \leq |B| \ \ and |B| \leq |C| \Rightarrow |A| \leq |C| \]

Schröder-Bernstein Theorem¶

$$ |A|=|B| iff |A| \leq |B| and |B| \leq |A| $$ "证明"

构造一个双射函数 $h: A \rightarrow B$，利用从 $A$ 到 $B$ 的单射函数 $f$ 和从 $B$ 到 $A$ 的单射函数 $g$。

构造法一¶

考虑通过交替使用 $f$ 和 $g$ 获得的最大序列：

循环序列（cyclic） $$ a \xrightarrow{f} f(a) \xrightarrow{g} g(f(a)) \xrightarrow{f} f(g(f(a))) \xrightarrow{g} (g \circ f)^2(a) = a $$
从 $A$ 开始的序列（A-starting）

\[ a \xrightarrow{f} f(a) \xrightarrow{g} g(f(a)) \xrightarrow{f} \cdots \quad \text{如果} \quad a \in A \setminus g(B) \]
从 $B$ 开始的序列（B-starting）

\[ g^{-1}(a) \xrightarrow{g} a \xrightarrow{f} f(a) \xrightarrow{g} g(f(a)) \xrightarrow{f} \cdots \quad \text{如果} \quad g^{-1}(a) \in B \setminus f(A) \]
双向无限序列（bi-infinite）

\[ \cdots \xrightarrow{g} f^{-1}(g^{-1}(a)) \xrightarrow{f} g^{-1}(a) \xrightarrow{g} a \xrightarrow{f} f(a) \xrightarrow{g} g(f(a)) \xrightarrow{f} \cdots \]

观察¶

观察 I：两个不同的序列是互不相交的（mutually disjoint）。
观察 I：这些序列形成了集合 A 和 B 的一个划分（partition）

h(a)¶

\[ h(a) = \begin{cases} f(a) & \text{如果 } a \text{ 在一个双向无限或循环序列中} \\ f(a) & \text{如果 } a \text{ 在一个从 } A \text{ 开始的无限序列中} \\ g^{-1}(a) & \text{如果 } a \text{ 在一个从 } B \text{ 开始的无限序列中} \end{cases} \]

单射性（injective）：由于每个元素 $a$ 被唯一地映射到一个元素 $h(a)$，且不同序列中的元素互不相交，因此 $h$ 是单射的。
满射性（onto）：由于这些序列形成了集合 $A$ 和 $B$ 的一个划分，因此每个元素 $b \in B$ 都有一个对应的元素 $a \in A$ 使得 $h(a)=b$。

构造法二¶

双射函数 $h(a)$ 的定义如下：

\[ h(a) = \begin{cases} f(a) & \text{如果 } a \in g f p_{\overline{g \circ f}} \\ f(a) & \text{如果 } a \in \bigcup_{n \in \mathbb{N}} (g \circ f)^n (A \setminus g(B)) \\ g^{-1}(a) & \text{如果 } a \in \bigcup_{n \in \mathbb{N}} (g \circ f)^n (g(B \setminus f(A))) \end{cases} \]

说明¶

情况1：当 $a$ 属于 $\overline{g \circ f}$ 的最大不动点集合 $g f p_{\overline{g \circ f}}$ 时，$h(a)$ 取 $f(a)$。
情况2：当 $a$ 属于从 $A \setminus g(B)$ 出发，通过多次应用 $g \circ f$ 得到的并集时，$h(a)$ 同样取 $f(a)$。
情况3：当 $a$ 属于从 $g(B \setminus f(A))$ 出发，通过多次应用 $g \circ f$ 得到的并集时，$h(a)$ 取 $g^{-1}(a)$。

构造法3¶

\[ h(a) = \begin{cases} g^{-1}(a) & \text{如果 } a \in \bigcup_{n \in \mathbb{N}} (g \circ f)^n (g(B \setminus f(A))) \\ f(a) & \text{其他情况} \end{cases} \]

构造说明¶

函数 $h(a)$ 的两种情况:
- 当 $a$ 属于集合 $\bigcup_{n \in \mathbb{N}} (g \circ f)^n (g(B \setminus f(A)))$ 时，$h(a)$ 取 $g^{-1}(a)$。
- 在其他所有情况下，$h(a)$ 取 $f(a)$。
集合 $\bigcup_{n \in \mathbb{N}} (g \circ f)^n (g(B \setminus f(A)))$:
- 这个集合是由函数 $g \circ f$ 的迭代应用生成的。具体来说，它包括所有通过多次应用 $g \circ f$ 到初始集合 $g(B \setminus f(A))$ 上得到的元素。
- $B \setminus f(A)$ 表示集合 $B$ 中不属于 $f(A)$ 的部分。
- $g(B \setminus f(A))$ 表示将函数 $g$ 应用到 $B \setminus f(A)$ 上得到的集合。
- $(g \circ f)^n$ 表示函数 $g \circ f$ 的第 $n$ 次迭代应用。

h(a)¶

单射性
- 在第一种情况下，使用 $g^{-1}(a)$ 确保了从 $B$ 中的特定元素映射回 $A$。
- 在其他情况下，直接使用 $f(a)$ 确保了从 $A$ 到 $B$ 的映射。
满射性 通过覆盖所有可能的元素情况，确保了 $B$ 中的每个元素都有一个对应的 $A$ 中的元素映射到它。

可数集合¶

定义¶

一个集合被称为 可数的，如果它是有限的或者与正整数集 $\mathbb{Z}_{+}$ 具有相同的基数。一个集合被称为 不可数的，如果它不是可数的。

$\aleph_{0}$（Aleph-null）：正整数集合的基数；也就是说，如果一个无限集 $S$ 是可数的，我们就用符号 $\aleph_{0}$ 表示集合 $S$ 的基数，$|S|=\aleph_{0}$，并说 $S$ 有基数“阿里夫零”。

Aleph $\aleph$：阿里夫，希伯来字母表的第一个字母。

希尔伯特大饭店

希尔伯特大旅馆悖论是数学家大卫·希尔伯特提出的一个思想实验，用于说明可数无限集合的性质。这个悖论假设有一个拥有无限个房间的大旅馆，每个房间都住满了客人。尽管如此，旅馆仍然可以容纳新的客人，甚至无限多的客人，而无需驱逐任何现有的客人。这是通过重新排列客人来实现的。

具体来说： 1. 单个新客人：如果有一个新客人到达，旅馆可以将每个客人从房间 $n$ 移动到房间 $n+1$，从而空出房间 1 给新客人。 2. 无限多新客人：如果有无限多的新客人到达，旅馆可以将每个客人从房间 $n$ 移动到房间 $2n$，从而空出所有奇数房间给新客人。

这个悖论展示了可数无限集合的奇特性质，即一个可数无限集合可以与它的一个真子集建立一一对应关系。

命题¶

集合 $A$ 是可数的，当且仅当 $|A| \leq |\mathbb{Z}_+|$。
- 推论 1：如果 $A$ 是可数的且 $|B| \leq |A|$，那么 $B$ 也是可数的。
- 推论 2：如果 $A$ 是可数的且 $B$ 是任一集合，那么 $A$ 与 $B$ 的笛卡尔积 $A \times B$ 也是可数的。
两个可数集的并集也是可数的。
整数集 $\mathbb{Z}$ 是可数的。
正整数集的笛卡尔积 $\mathbb{Z}_+ \times \mathbb{Z}_+$ 是可数的。

可以通过利用以下命题来证明：
- 命题：集合 $A$ 是可数的，当且仅当 $|A| \leq |\mathbb{Z}_+|$。
整数集的笛卡尔积 $\mathbb{Z} \times \mathbb{Z}$ 是可数的。
有理数集是可数的
对于每一个 $n \geq 1$，((\mathbb{Z}_+)^n$ 是可数的。
正整数集的有限序列集合 $(\mathbb{Z}_+)^+$ 是可数的。
集合 {0,1}* 和 {0,⋯,9}* 是可数的。
Info

解释：
- {0,1}*：表示由0和1组成的有限序列集合，包括空序列ε。例如，ε、(0)、(1)、(0,0)、(0,1)等都是{0,1}*中的元素。
- {0,⋯,9}*：表示由数字0到9组成的有限序列集合，包括空序列ε。例如，ε、(1)、(2,3)、(4,5,6)等都是{0,⋯,9}*中的元素。
数学表示：

\[ \{0,1\}^* = \bigcup_{n \in \mathbb{N}} \{0,1\}^n \quad \quad \{0,\cdots,9\}^* = \bigcup_{n \in \mathbb{N}} \{0,\cdots,9\}^n \]

可数性说明：
- 对于每个固定的n，{0,1}^{n和{0,⋯,9}}n都是可数的，因为它们可以与正整数集建立一一对应关系。
- 由于可数个可数集的并集仍然是可数的，因此{0,1}*和{0,⋯,9}*作为所有长度n的序列的并集，也是可数的。
C 程序的集合是可数的。
Tip

解释：
- 符号表的有限性：C 程序中使用的符号集合，记作 Σ，是有限的。这包括字母、数字、标点符号以及 C 语言中的保留字等。
- 符号序列：Σ* 表示由 Σ 中的符号组成的有限序列集合，包括空序列 ε。例如，ε、"a"、"123"、"if (x > 0)" 等都是 Σ* 中的元素。
- C 程序作为符号序列：每个 C 程序都可以视为一个来自 Σ* 的符号序列。也就是说，任何 C 程序都可以表示为有限个符号的组合。
- C 程序集合是 Σ* 的子集：所有 C 程序的集合是 Σ* 的一个子集，即 C 程序 ⊆ Σ*。
- 可数性：由于 Σ 是有限的，Σ* 是可数的。具体来说，对于每个固定的 n，Σ^n（长度为 n 的符号序列集合）是有限的，因此是可数的。而 Σ* 是所有 Σ^n 的并集，即可数个可数集的并集，因此 Σ* 是可数的。既然 C 程序集合是 Σ* 的子集，它也必然是可数的。

定理¶

可数个可数集的并集是可数的。

不可数集合¶

定理¶

所有的实数集不可数
对于任意集合 $A$，$|A| < |2^A|$ $2^A$：从集合 $A$ 到集合 $\{0, 1\}$ 的所有函数的集合。

康托尔定理的两种表述

康托尔定理的两种表述虽然在表面涉及不同的数学对象（幂集与函数集合），但本质上它们是等价的，因为两者之间存在自然的双射关系，从而具有相同的基数。具体分析如下：

等价性证明：
- 幂集 $ P(A) $ 是集合 $ A $ 所有子集的集合。
- 函数集合 $ 2^A $ 定义为所有从 $ A $ 到二元集合 $ \{0,1\} $ 的函数。
- 每个子集 $ S \subseteq A $ 可唯一对应一个 特征函数 $ \chi_S: A \to \{0,1\} $，满足 $ \chi_S(a) = 1 $ 当且仅当 $ a \in S $。
- 这种对应关系是双射的，因此 $ |P(A)| = |2^A| $。
基数运算的一致性：
- 若集合 $ A $ 的基数为 $ \kappa $，则幂集的基数 $ |P(A)| = 2^\kappa $。
- 函数集合 $ 2^A $ 的基数同样为 $ 2^\kappa $，因为每个函数可视为长度为 $ \kappa $ 的二元序列。
定理的两种表述：
- 幂集版本：$ |A| < |P(A)| $，即不存在从 $ A $ 到 $ P(A) $ 的满射。
- 函数集合版本：$ |A| < |2^A| $，即不存在从 $ A $ 到 $ 2^A $ 的满射。
- 通过双射 $ P(A) \leftrightarrow 2^A $，两种表述的结论一致。
对角线法的应用：
- 假设存在满射 $ f: A \to P(A) $，构造 $ B = \{a \in A \mid a \notin f(a)\} $，则 $ B \notin f[A] $，矛盾。
- 类似地，假设存在满射 $ g: A \to 2^A $，构造函数 $ h(a) = 1 - g(a)(a) $，则 $ h \notin g[A] $，矛盾。
- 两种证明思路相同，仅替换了数学对象（子集与函数）。

结论：康托尔定理的两种表述是等价的，因为 $ P(A) $ 和 $ 2^A $ 的基数相等，且均严格大于 ( |A| \。因此，无论是通过幂集还是函数集合的形式，定理的核心断言一致：任何集合的势总小于其幂集（或对应的函数集合）的势。

$\boxed{|A| < |P(A)| \text{且} |A| < |2^A|, |P(A)| = |2^A|}$

命题¶

$|(0,1)=|[0,1)|=|(0,1]|=|[0,1]|=|\mathbb{R}|$
假设 $A$ 不可数，$B$ 是 $A$ 的可数子集。那么，$|A \setminus B|=|A|$
$|2^{\mathbb{Z}_+}| = |\{0,1\}^\omega| = |\{0,\cdots,9\}^\omega| = |(0,1)|$.
- $2^{\mathbb{Z}_+}$: 从正整数集 $\mathbb{Z}_+$ 到集合 $\{0, 1\}$ 的所有函数的集合。
- $\{0,1\}^\omega$: 由 0 和 1 组成的无限序列的集合
  $b_1b_2\cdots$
- $\{0,\cdots,9\}^\omega$: 由数字 0 到 9 组成的无限序列的集合
  $d_1d_2\cdots$

$A^B$

在集合论中，符号 $A^B$ 通常表示从集合 $B$ 到集合 $A$ 的所有函数的集合。这里的 $2$ 常被用来表示二元集合 $\{0, 1\}$，因此 $2^{\mathbb{Z}_+}$ 表示从正整数集 $\mathbb{Z}_+$ 到 $\{0, 1\}$ 的所有函数的集合。每个函数可以看作是一个无限序列，其中每个位置的值为 0 或 1，对应 $\mathbb{Z}_+$ 的子集的特征函数。

实数集不可数的两种证明方法¶

1. 康托尔对角线法¶

核心思路：构造一个不在假设可数列表中的实数。

关键步骤： 1. 假设：区间 $[0,1]$ 可数，则所有实数可排列为序列 $a_1, a_2, a_3, \dots$。 2. 构造对角数：定义新数 $b = 0.b_1b_2b_3\dots$，其中 $$ b_i \neq \text{第 }i\text{ 个数的第 }i\text{ 位小数} \quad (\text{例如取 } b_i = 5 \text{ 当原第 }i\text{ 位} \neq 5)。 $$ 3. 矛盾：$b \neq a_i$ 对所有 $i$ 成立，矛盾。

2. 闭区间套定理法¶

核心思路：通过区间套排除所有可数列表中的数。

关键步骤： 1. 假设：区间 $[0,1]$ 可数，即 $[0,1] = \{a_1, a_2, a_3, \dots\}$。 2. 构造闭区间套： - 初始区间 $I_1 = [0,1]$。 - 递归定义 $I_{n+1} \subset I_n$ 为 $I_n$ 的三分之一子区间，且 $I_{n+1} \cap \{a_1, \dots, a_{n+1}\} = \emptyset$。 3. 闭区间套定理：存在唯一 $x \in \bigcap_{n=1}^\infty I_n$。 4. 矛盾：$x \in [0,1]$ 但 $x \neq a_n$ 对所有 $n$ 成立，矛盾。

结论：两种方法均说明实数集不可数。

康托尔定理：对任意集合 $A$，$|A| < |2^A|$¶

核心思路：构造矛盾证明不存在双射。

1. 证明 $|A| \leq |2^A|$¶

构造单射：定义映射 $f: A \to 2^A$，其中 $f(a) = \{a\}$。
单射性：若 $a \neq b$，则 $\{a\} \neq \{b\}$，故 $f$ 是单射。

2. 证明 $|A| \neq |2^A|$（关键）¶

假设存在双射：假设存在双射 $g: A \to 2^A$。
构造矛盾子集：定义集合 $$ B = { a \in A \mid a \notin g(a) } \subseteq A. $$
矛盾推导：
若 $B = g(a_0)$ 对某个 $a_0 \in A$，则：
- 若 $a_0 \in B$，由定义得 $a_0 \notin g(a_0) = B$，矛盾。
- 若 $a_0 \notin B$，由定义得 $a_0 \in g(a_0) = B$，矛盾。
结论：不存在双射 $g$，故 $|A| < |2^A|$。

注：此构造称为“对角线法”，与罗素悖论思想类似。

2.4 集合的基数

基数¶

定义¶

命题¶

Schröder-Bernstein Theorem¶

构造法一¶

观察¶

h(a)¶

构造法二¶

相关定义¶

说明¶

构造法3¶

构造说明¶

h(a)¶

可数集合¶

定义¶

命题¶

定理¶

不可数集合¶

定理¶

命题¶

实数集不可数的两种证明方法¶

1. 康托尔对角线法¶

2. 闭区间套定理法¶

康托尔定理：对任意集合 \(A\)，\(|A| < |2^A|\)¶

1. 证明 \(|A| \leq |2^A|\)¶

2. 证明 \(|A| \neq |2^A|\)（关键）¶