集合进阶

有穷和无穷

有穷集合和无穷集合的定义：称一个集合为有穷集合，当且仅当它与某一个自然数等势。不是有穷集合的集合，称为无穷集合。

关于有穷集的定理：

• 定理 $1$ 集合 $A$ 是有穷集合，当且仅当存在自然数 $n$，使得 $A⪯n$。
• 定理 $2$ 任意的自然数 $n$ 都没有与其等势的真子集。

因此，我们可以看出，有穷集合没有与其等势的真子集；无穷集合都有与其等势的真子集。显然我们可以举出如 $\{2n|n\in \omega \}\subset \omega$​ 这样的无穷集来说明。

关于无穷集的定理：

• 定理 $1$ 每一个无穷集都有无数的无穷子集。
• 定理 $2$ 若 $A$ 是无穷集，那么 $\omega ⪯A$。
• 定理 $3$ $A$​ 是无穷集，当且仅当它与它自身的一个真子集等势。
• 定理 $4$ 如果 $A$ 非空且 $\bigcup A=A$，那么 $A$ 是无穷集。

可数和不可数

可数集合的定义：称一个集合为可数集合，当且仅当它的势不大于 $\omega$ 的势。

可数集合的一些推论：

• 若一个集合可数，那么它要么是有穷集，要么与 $\omega$ 等势
• $\omega$ 是可数集合
• $\omega \times \omega$ 是可数集合
• $\mathbb{Z},\mathbb{Q}$​ 都是可数集合
• 多个可数集合之并也是可数集合

不可数集合的定义：不是可数的无穷集合叫不可数集合。

康托尔定理

每个集合都和它的幂集不等势。也就是说，对于任意集合 $A$，有 $A⪯\mathcal{P}A$。

关于不可数集的定理

• 区间 $(0,1)$ 是不可数的；
• 连续统假设：不存在集合 $A$ 使得 $\omega \prec A$ 和 $A\prec \mathbb{R}$。

序数

序数的定义：具有三歧性的传递集合叫做序数。

关于序数的定理：

• 序数的后继也是序数；
• 序数的每个元素也是序数；
• $0$、每个自然数、$\omega$​​ 都是序数；
• 对于任意序数 $\alpha$ 和 $\beta$，必定有 $\alpha \in \beta$ 或 $\beta \in \alpha$ 或 $\alpha =\beta$​；我们也可以表示成 $\alpha <\beta$ 或 $\alpha >\beta$ 或 $\alpha =\beta$；
• 若集合 $S$ 中的每一个元素都是序数，那么 $\bigcup S$ 也是序数。（需要会证明）

我们用 $On$ 来表示所有序数的类，即 $On=\{\alpha |\alpha \mathrm{是}\mathrm{序}\mathrm{数}\}$。注意，这是类而不是集合，因为 $On$ 本身也是序数。

从之前的介绍可知，每一个自然数都在通常的小于等于的关系下是一个良序集合，这就是自然数序。下面我们将这一具有较好性质的良序集合推广到其他良序集上。

定理 设 $(A,{\le }_A)$ 是一个良序集，$A$ 有穷，那么存在一个自然数 $n$，使得 $(A,{\le }_A)$ 与 $(n,\le )$​ 序同构。即：每一个良序集合都与一个自然数序同构。

从这一定理出发，有更强的同构定理。

同构定理 设 $(A,{\le }_A)$ 是一个良序集，则存在唯一的序数$\alpha$，使得 $(A,{\le }_A)$ 和 $(\alpha ,\le )$ 序同构。即存在映射 $f:A\to \alpha$，使得对任意 $x,y$，若 $x{\le }_{A}y$ 则 $f(x)\le f(y)$。

超穷归纳法

极限序数的定义：设 $\alpha$ 是序数，若存在序数 ${\beta }^{+}=\alpha$，那么称 $\alpha$ 是后继序数。不是后继序数的非零序数是极限序数。可以看出，自然数都是后继序数，$\omega$ 是极限序数，且是最小的极限序数。

关于极限序数的结论：

• 没有最大元的序数是极限序数。
• 对于任意的 $\beta <\alpha$，都有 ${\beta }^{+}<\alpha$，当且仅当 $\alpha$ 是极限序数。

超穷归纳法

设 $R(x)$ 是一个性质，若

1. $R(0)$成立；
2. 对于所有序数 $\alpha$，若 $R(\alpha )$ 成立，则 $R(\alpha +1)$ 成立；
3. 对于任意的极限序数 $\lambda$，若对任意 $\alpha <\lambda$ 有 $R(\alpha )$ 成立，那么 $R(\lambda )$ 成立。

那么对于任意序数 $R(x)$ 成立。

我们可以用超穷归纳法来定义序数的加法。

• $\alpha +0=\alpha$
• $\alpha +{\beta }^{+}=(\alpha +\beta {)}^{+}$
• $\alpha +\lambda ={\cup }_{\beta \in \lambda }(\alpha +\beta )$，其中 $\lambda$ 是极限序数。

定义了加法之后，序数的乘法也可以被定义：

• $\alpha \cdot 0=0$
• $\alpha \cdot {\beta }^{+}=(\alpha \cdot \beta )+\beta$
• $\alpha \cdot \lambda ={\cup }_{\beta <\lambda }(\alpha \cdot \beta )$，其中 $\lambda$ 是极限序数。

可数序数

如果序数 $\alpha$ 是一个可数集合，那么它是可数序数。例如，$\omega$、$\omega +1$、$2\omega$ 都是可数序数。

定义 ${\omega }_1=\{\alpha |\alpha \mathrm{是}\mathrm{可}\mathrm{数}\mathrm{序}\mathrm{数}\}$，我们可以证明 ${\omega }_1$ 是序数，但不可数。

一般地，假设对于后继序数 $\alpha$，我们已经定义了 ${\omega }_{\alpha }$，那么我们有

$${\omega }_{\alpha +1}=\{\beta |\beta \mathrm{是}\mathrm{序}\mathrm{数}\mathrm{且}\beta ⪯{\omega }_{\alpha }\}$$

对于极限序数 $\lambda$，我们也可以通过超穷定义法定义 ${\omega }_{\lambda }$。至此，我们定义了所有序数 $On$ 下的 ${\omega }_{\alpha }$。

基数

基数的定义：设 $\alpha$ 是一个序数，如果对任意的 $\beta <\alpha$ 都有 $\beta \prec \alpha$，那么称 $\alpha$ 为基数。

与基数相关的有以下结论：

• 所有自然数显然都是基数。
• 对于任意序数 $\alpha$，有 ${\omega }_{\alpha }$ 是基数。

我们定义 $Card=\omega \cup \{{\omega }_{\alpha }|\alpha \in On\}$，那么所有的无穷基数都是 $Card$ 的元素。注意，$Card$ 同样是类而非集合。对于任意的集合，我们都可以找到与它等势的基数。

既然如此，那么我们规定对于任意的集合 $A$，用 $|A|$ 或 $\mathrm{card}A$ 来表示与集合 $A$ 等势的唯一基数，称作 $A$ 的基数，也称 $A$ 的势。显然，$|A|$ 是等势的最小序数。若 $A,B$ 为集合，那么

• $A⪯B$ 当且仅当 $|A|\le |B|$
• $A\sim B$ 当且仅当 $|A|=|B|$
• $A\prec B$ 当且仅当 $|A|<|B|$

这样，就将等势和基数建立起了映射。

基数的运算

对于基数 $\kappa ,\lambda$，我们定义：

• $\kappa +\lambda =|(\{0\}\times \kappa )\cup (\{1\}\times \lambda )|$
• $\kappa \cdot \lambda =|\kappa \cdot \lambda |$

可以看出 $\kappa +\lambda =|A\cup B|$，其中 $|A|=\kappa$，$|B|=\lambda$ 且 $A\cap B=\mathrm{\varnothing }$；$\kappa \cdot \lambda =|A\times B|$，其中 $|A|=\kappa$，$|B|=\lambda$。基数的加法和乘法运算都具有结合律、交换律。

对于无穷基数 $\kappa$，我们有：

• $\kappa +\kappa =\kappa$
• 如果 $\lambda \le \kappa$，那么 $\kappa +\lambda =\kappa$，$\kappa \cdot \lambda =\lambda \cdot \kappa =\kappa$