本篇内容

集合的基数（cardinality）
有关基数的定理
康托尔对角论证

基数

1. 概念

基数（cardinality）的概念是指一个集合中元素的数量。例如，集合 $\{a, b, c\}$ 中有三个元素，所以它的基数是 $3$ 。我们用 $|A|$ 来表示集合 $A$ 的基数。

基数的概念可以用来比较不同集合的大小，或者判断一个集合是否是有限的或无限的。如果两个集合有相同的 cardinality，那么它们就是等势的，也就是说它们之间可以建立一一对应的关系。

例如，集合 $\{1, 2, 3\}$ 和集合 $\{a, b, c\}$ 是等势的，因为我们可以把 $1$ 对应到 $a$ ， $2$ 对应到 $b$ ， $3$ 对应到 $c$ 。

基数的概念也可以推广到无限集合，这样就可以区分不同类型的无穷大，并且对它们进行运算。例如，自然数集 $\mathbb{N}$ 和整数集 $\mathbb{Z}$ 都是无限集合，但它们有相同的基数 $\aleph_0$ （aleph null），这是最小的无穷大数。而实数集 $\mathbb{R}$ 的基数是 $2^{\aleph_0}$ （aleph one），这是比 $\aleph_0$ 大得多的一个无穷大数。

如果集合 $A$ 和集合 $B$ 之间存在一个双射，那么它们的元素个数是相等的，也就是说它们有相同的基数。因此，我们可以用“ $|A|=|B|$ ”来表示它们等势。

同样地，如果存在一个从 $A$ 到 $B$ 的单射（下文有讲），那么我们可以说集合 $A$ 的基数不大于集合 $B$ 的基数，即“ $|A|\leq |B|$ ”。这意味着 $B$ 至少包含 $A$ 的所有元素，但是还可能包含一些额外的元素。

如果 $A$ 的基数小于 $B$ 的基数（即 $|A|<|B|$ ），那么我们说 $A$ 的基数严格小于 $B$ 的基数，也就是说 $A$ 的元素比 $B$ 的元素更少。

2. 有关基数的定理

基数的基本性质

$|A| = |A|$

表示一个集合的基数等于它自己的基数，这是显然的。

$|A| = |B| \Rightarrow |B| = |A|$

表示如果两个集合 $A$ 和 $B$ 的基数相等，那么反过来 $B$ 和 $A$ 的基数也相等，这也是显然的。

$|A| = |B| \wedge |B| = |C| \Rightarrow |A| = |C|$

表示如果三个集合 $A$ 、 $B$ 和 $C$ 中，前两个集合的基数相等，并且后两个集合的基数相等，那么第一个和第三个集合的基数也相等，这是由传递性推出来的。

CBS 定理（Cantor-Bernstein-Schröder）

CBS 定理的内容是：区间 $(0,1)$ 和正整数集合 $\mathbb{Z}^+$ 的基数不相等，即

$|(0,1)|\neq|\mathbb{Z}^+ |$

也就是说，这个结论是证明实数集合的基数比自然数集合的基数要大的一部分。

我们使用的是康托尔对角论证来证明这个定理。

具体地，假设存在一个双射 $f:\mathbb{Z}^+\to(0,1)$ ，将正整数映射到 $(0,1)$ 之间的实数。根据这个映射，我们可以将每个正整数 $i$ 对应到 $f(i)$ 的小数表示，将每个小数的小数位展开：

并构造一个新的实数 $b$ 。设 $b$ 的第 $i$ 位小数等于

$b_{i} =\left\{ \begin{matrix} \ 4,\ b_{ii} \neq 4\\ \ 5,\ b_{ii} = 4 \end{matrix}\right.\ \ \ \ \ \ \ i = 1,\ 2,\ 3,\dots$

这样构造的 $b$ 是一个在区间 $(0,1)$ 中的实数，即存在 $f(n) = b$ 但由于 $b$ 的特殊的定义，这使得 $b$ 和 $f(n)$ 的第 $n$ 个小数位是不同的，所以 $b$ 不属于区间 $(0,1)$ 。这意味着 $f$ 不是一个满射，也就是说它不是一个双射，与我们的假设矛盾，因此不存在这样的双射 $f$ ，即 $|(0,1)|\neq|\mathbb{Z}^+ |$ 。

康托定理（Cantor's Theorem）

对于任意集合 $A$ ，其基数（元素个数）小于其幂集（所有子集构成的集合）的基数。或者用符号表示为：

$|A|<|\mathcal{P}(A)|$

换言之，幂集的大小（基数）大于该集合的大小（基数）。这是一个重要的结果，因为它表明在集合论中，存在不同大小的无穷集合，而且无穷集合的大小可以无限增长。这个定理也可以通过康托尔对角线论证（Cantor’s diagonal argument）来证明。

Schröder-Bernstein 定理

这是集合论中的一个基本定理，得名于施罗德、伯恩斯坦和康托尔。

如果在集合 $A$ 和 $B$ 之间存在单射 $f : A \to B$ 和 $g : B \to A$ ，则存在一个双射 $h : A \to B$ 。

或者更简洁地表达

如果 $|A|\leq |B|$ 且 $|B|\leq |A|$ ，那么 $|A|=|B|$ 。

这个定理通常用于证明两个集合具有相同的基数（cardinality），也就是说，它们有相同数量的元素。

康托尔对角论证

1. 介绍

之前对 CBS 定理的证明我们使用的是康托尔对角论证。

康托尔对角线论证是一种数学证明方法，它由集合论的创始人乔治·康托尔于1891年提出，用于说明实数集合是不可数集，即它的基数大于自然数集合的基数。

这个证明方法的基本思想是假设实数集合是可数的，即它可以排列成一个无穷序列，然后构造一个新的实数，使得它与序列中的任何一个实数都不相等。这个新的实数就是通过对角线法得到的，即将序列中每个实数的小数部分按照对角线顺序取出，并且改变每一位上的数字（例如将0改为1，将1改为2等），从而形成一个新的小数部分。这样，这个新的实数就与序列中任何一个实数在至少一位上不同，因此不属于序列中。这就产生了一个矛盾，因为假设了实数集合是可数的，但却找到了一个不属于序列中的实数。因此，假设不成立，实际上实数集合是不可能按照自然数的顺序排列所有的实数，所以实数集合和自然数集之间不存在双射，也就是说实数集合的基数大于自然数集合的基数，并且实数集合是不可数的。

它利用了一个类似于矩阵中主对角线（main diagonal）上元素构造出新元素来打破原来函数映射关系。

2. 基本过程

以下是总结出的基本过程：

假设实数集合是可数的，即它可以排列成一个无穷序列 ${r_1,r_2,r_3,\dots}$ 。
把这些实数的小数部分按照十进制展开，并排成一个表格，例如：

$\begin{align*} r_1 =0.\ a_{11}\ &a_{12}\ a_{13} \cdots \\ r_2 =0.\ a_{21}\ &a_{22}\ a_{23} \ \cdots \\ r_3 =0.\ a_{31}\ &a_{32}\ a_{33} \ \cdots \\ &\vdots \end{align*}$

其中 $a_{ij}$ 是 $0$ 到 $9$ 之间的整数。

从表格的左上角开始，沿着对角线取出每个实数的小数部分的一位数字，并且改变每一位上的数字（例如将 $0$ 改为 $1$ ，将 $1$ 改为 $2$ 等），从而形成一个新的小数部分。例如，如果对角线上的数字是 $a_{11},\ a_{22},\ a_{33},\ \dots$ ，那么新的小数部分就是 $b_1,\ b_2,\ b_3,\ \dots$ ，其中 $b_i$ 是不等于 $a_{ii}$ 的任意整数。
用这个新的小数部分构造一个新的实数 $x=0.b_1\ b_2\ b_3\ \dots$ 。
由于 $x$ 和序列中任何一个实数在至少一位上不同，因此 $x$ 不属于序列中。例如，对于任意正整数 $n$ ，有 $x$ 的第 $n$ 位小数是 $b_n$ ，而序列中第 $n$ 个实数的第 $n$ 位小数是 $a_{nn}$ ，而这两者不相等。
这就产生了一个矛盾，因为假设了实数集合是可数的，但却找到了一个不属于序列中的实数。
所以假设不成立，实际上实数集合是不可能排成一个无穷序列，即它是不可数的。

青山后小塘

组合学 [2]

基数