集合论入门学习笔记·集合的大小

· · 算法·理论

（《集合论基础》读了一半后感）

（本文与 OI 无关）

FUN FACT：俄国人用 \subset 表示子集，用 \subsetneqq 表示真子集，而且我也是这么学的。

集合的基数

我们把一个集合中元素的数量称为该集合的基数，集合 S 的基数表示为 \mid S\mid。

若集合 A 与 B 之间存在一一对应，则 \mid A\mid=\mid B\mid。

> $[0, 1]$ 与所有无限长的 01 串组成的集合有相同的基数。 这很简单，因为每个数都有二进制表示，如 $0.4375=0.011100000\cdots_{(2)}$。 > $[0, 1]^2=\{(x, y)\mid x, y\in[0, 1]\}$ 与 $[0, 1]$ 有相同的基数。 设 $x$ 的二进制表示对应的 01 串是 $a_0, a_1, a_2,\cdots$，$y$ 的是 $b_0, b_1, b_2,\cdots$。那么 $a_0, b_0, a_1, b_1, a_2, b_2, \cdots$ 也对应一个 $[0, 1]$ 间的数。也就是说 $\{(x, y)\mid x, y\in[0, 1]\}$ 与 $[0, 1]$ 存在一个一一对应。 这告诉我们一个正方形**内**的点的数量与这个正方形**上**点的数量是相同的。 ## 可数集的基数 我们可以发现基数的定义可以应用于无穷集，所以我们可以定义 $\mid\mathbb{N}\mid=\aleph_0$，同时我们把所有基数为 $\aleph_0$ 的集合称为可数集。 > $\mathbb{Z}$ 是一个可数集。 这是显然的，因为我们可以通过映射 $x\to 2\mid x\mid+[x\le 0]$ 建立 $\mathbb{Z}$ 与 $\mathbb{N}$ 之间的一个一一对应（这里用到了艾弗森括号）。 > $\mathbb{Q}$ 是一个可数集（这里我们只考虑正有理数）。 因为像 $\frac{3}{6}$ 这样的分数存在，所以 $\mid\mathbb{Q}\mid\le{\aleph_0}^2$，又因为整数集是有理数集的一个子集，所以 $\aleph_0\le\mid\mathbb{Q}\mid$。所以 $\aleph_0\le{\aleph_0}^2$，我们只需证明 ${\aleph_0}^2=\aleph_0$。 然后发现有映射 $(x, y)\to 2^{x+y}+2^y$，也就是说 ${\aleph_0}^2\le\aleph_0$，所以 ${\aleph_0}^2=\aleph_0$。 > 任何无穷集都有一个可数子集。 我们可以取出集合中的一个元素，将其标为 $1$ 号，再取出一个，标为 $2$ 号，……因为集合是无穷大的，所以我们可以一直做下去，于是这个集合有至少一个可数子集。 ## 集合比大小 实际上，我写的关于有理数集是可数集的证明是有问题的，因为我们不能通过“集合 $A$ 与集合 $B$ 的一个子集存在一一对应”和“集合 $B$ 与集合 $A$ 的一个子集存在一一对应”推出 $\mid A\mid=\mid B\mid$。接下来我们来证明这一点。 > （Cantor-Bernstein 定理）如果集合 $A$ 与集合 $B$ 的一个子集存在一一对应且集合 $B$ 与集合 $A$ 的一个子集存在一一对应，那么集合 $A$ 与集合 $B$ 存在一一对应。 它等价于：如果 $A_2\subseteq A_1\subseteq A_0$ 且 $\mid A_2\mid=\mid A_0\mid$，则这三个集合基数相等。 由条件可知，存在一个从 $A_0$ 到 $A_2$ 的一一对应 $f$。它把 $A_1$ 映射到 $A_3\subseteq A_2$ 上，把 $A_2$ 映射到 $A_4\subseteq A_3$ 上……于是我们可以构造出 $A_1\supseteq A_2\supseteq A_3\cdots$。 令 $C_i=A_i\backslash A_{i+1}$，$C=\cup_i A_i$。则 $f$ 会将 $C_i$ 映射到 $C_{i+2}$ 上，所以 $C_0, C_2, C_4, \cdots$ 有相同的基数；$C_1, C_3, C_5, \cdots$ 有相同的基数。 于是： $$ \begin{align*} A_0 & = C_0 + C_1 + C_2 + C_3 + C_4 \cdots + C \\ A_1 & = C_2 + C_1 + C_4 + C_3 + C_6 \cdots + C \end{align*} $$ 每一项之间都存在一一对应，所以 $A_0$ 与 $A_1$ 之间存在一一对应。 ## 实数是否是可数 不可数。 我们可以把 $0$ 映射到 $0$，把 $(0, 1]$ 通过 $x\to\frac{1}{x}$ 映射到 $[1, +\infty)$，所以 $[0, 1]$ 与 $\mathbb{R}$ 有相同的基数，我们把这个基数称为连续统基数，写作 $\mathfrak{c}$。于是我们只需考虑 $[0, 1]$ 是否可数。 我们假设存在一种方式，给每个 $[0, 1]$ 内的数一个正整数编号，如： $$ \begin{gather*} 1\to 0.{\color{red}1}100\cdots_{(2)}\\ 2\to 0.0{\color{red}1}01\cdots_{(2)}\\ 3\to 0.01{\color{red}0}1\cdots_{(2)}\\ 4\to 0.011{\color{red}1}\cdots_{(2)}\\ \vdots \end{gather*} $$ 那么可以构造出一个数使得它小数点后 $i$ 位与第 $i$ 个数的第 $i$ 位不同。在上面的例子中，我们构造 $0.0010\cdots_{(2)}$，由定义可知，它不在这个表中。所以不存在这种表示方式，即 $\mathfrak{c}=2^{\aleph_0}\gt\aleph_0$。 我们也可以用形式化的方式给出上面这个定理的一般形式的证明。 首先我们定义 $P(X)$ 是指 $X$ 所有子集组成的集合。 > （Cantor 定理）对于集合 $X$，$X$ 与 $P(X)$ 间不存在一一对应。 假设 $f$ 是 $X$ 与 $P(X)$ 间的一一对应。 设 $Z=\{x\in X\mid x\not\in f(x)\}$，这是 $X$ 的一个子集，所以 $Z\in P(X)$，所以存在 $a\in X$ 使得 $f(a)=Z$。 如果 $a\in Z$，则 $a\not\in f(a)$，又 $f(a)=Z$，所以 $a\not\in Z$。 如果 $a\not\in Z$，则 $a\in f(a)$，同理 $a\in Z$。 所以 $Z$ 根本不存在，$f$ 也是。 ## 基数的运算 这里我们要先重新定义一下几种运算。 设 $a=\mid A\mid, b=\mid B\mid$，其中集合 $A$ 与集合 $B$ 不相交。 - $a+b=\mid A\cup B\mid$，这很合理。 - $a\times b=\mid{(x, y)\mid x\in A, y\in B}\mid$，这也很合理。 - $a^b$ 是由所有映射 $f$ 组成的集合的基数，其中 $f$ 的定义域是 $B$，值域是 $A$ 的某个子集。说明这一点要用到乘法原理，$f$ 要把 $B$ 中每个元素映射到 $A$，每次都有 $a$ 种方案，那么总共就有 $a^b$ 种方案。 这几个运算与整数运算有着几乎一致的性质。 有意思的是，我的初一时的数学老师告诉我，$0^0$ 是没有意义的，但是根据上面的定义 $0^0=1$，因为空集到空集的映射只有一种。 接下来我们可以给出许多的等式： - $\aleph_0+n=\aleph_0

完结（？）撒花 + 参考文献

有意思的是，我们把满足 x\gt\aleph_0 的最小的 x 记作 \aleph_1。命题 \aleph_1=\mathfrak{c} 被称为连续统假设。

康托尔定理 - 维基百科，自由的百科全书