集合进阶

有穷和无穷

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

关于有穷集的定理：

• 定理 $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$​
• 若集合 $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)$ 成立。