超穷归纳
严格来讲，“超穷归纳”(transfinite induction)指代的是如何在序数上归纳地定义(类)函数的定理。
定理 1: (Transfinite Induction)
令A是一个序数，或者A等同于序数类\(\mathbf{On}\)，假定\(B
\subseteq A\)满足
那么\(B = A\)
这里，\(\alpha \subseteq B\)等同于\(\forall a < \alpha, a \in B\)。如果我们令\(B\)是一个类，那么这个条件就是在说“如果所有小于\(\alpha\)的元素都具有性质B，那么\(\alpha\)也有性质B”，也就是我们常见的归纳原则(Principle of Induction)。注意到我们既能对整个序数类做归纳，又能对某个单独的序数做归纳。
这个定理的证明很简单，因为序数具有良基性。那么\(<\)在序数上构成一个良序，那么我们用良序证明数学归纳法的方法也能套用到这上面来：
证明 2: 假定\(B \neq A\)，则取\(\alpha \in A\backslash B\)为\(A\backslash B\)中最小的元素，那么我们有\(\forall a < \alpha, a \in B\)，故\(\alpha \subseteq B\)，因此\(\alpha \in B\)，矛盾。
证毕
常用的超穷归纳是这个定理的一个推论。
定理 3:
令A是一个序数或者A等同于序数类\(\mathbf{On}\)，假定\(B \subseteq
A\)满足
- 若\(0 \in A\)，那么\(0 \in B\)
- 若\(\alpha + 1 \in A\)，\(\alpha \in B\)，那么\(\alpha + 1 \in B\)
- 若\(\alpha\)是一个极限序数，\(\alpha \in A\)并且\(\alpha \subseteq B\)，那么\(\alpha \in B\)
那么\(B = A\)
证明 4:
只需证明这三个条件蕴含超穷归纳原则的假设即可。对于\(\alpha
\in A\)，假定对所有的\(\beta < \alpha\)都有\(\beta \in
B\)成立。若\(\alpha = 0\)，那么根据1我们有\(\alpha \in B\)；若\(\alpha
= \alpha' + 1\)，那么因为\(\alpha' < \alpha\)，我们有\(\alpha \in
B\)成立；若\(\alpha\)是一个极限序数，那么直接成立。
证毕
把序数与我们在各种集合上的归纳联系起来的是下面两个定理：
定理 5: 每个良序集\((S, <)\)都同构于某个序数\((\alpha, <)\)
定理 6: (Well-ordering Theorem) 每个集合上都存在一个良序
同构是序理论的一个基本结论，它的证明需要用到replacement公理。
良序定理则是一个非常著名的定理，更著名的是良序定理，Zorn's lemma，以及选择公理这三者是等价的。事实上，一部分“超穷归纳”都可以直接用良序定理来完成，绕过对序数的讨论，比如zorn引理的证明。
引理 7: (Zorn's lemma) 对于一个非空偏序集\((Z, \leqslant)\)，如果Z中的每个链（全序子集）都在Z中有一个上界，那么Z中存在一个极大元素
证明 8:
假定Z中的每个链（全序子集）都在Z中有一个上界，现在要想办法构造一个极大元素。
-
根据良序定理，\(Z\)和某个序数\(\alpha\)同构。因此有一个\(\alpha\)到\(Z\)的同构\(f : \alpha \rightarrow Z\)
-
我们使用超穷归纳，遍历\(Z\)中全部的元素，并构造一个链，即构造一个函数\(g : \alpha \rightarrow P (Z)\)
归纳假设对所有\(\beta < \gamma\)，我们已经遍历过了\(f (\beta)\)，也就是\(g (\beta)\)已经定义好了，我们定义\(g (\gamma)\)为
\[ g (\gamma) := \left\{\begin{array}{ll} \{ f (\gamma) \} & \textrm{如果} \{ f (\gamma) \} \cup \bigcup_{\beta < \gamma} g (\beta) \textrm{构成一个全序}\\ \varnothing & 否则 \end{array}\right. \]那么我们有\(S = \bigcup_{\beta < \alpha} g (\beta)\)是一个链：对于任意\(f (\alpha), f (\beta) \in S\)，不妨设\(\alpha < \beta\)，我们有\(g (\alpha) = \{ f (\alpha) \}, g (\beta) = \{ f (\beta) \}\)，因为\(\{ f (\beta) \} \cup \bigcup_{\beta < \gamma} g (\beta)\)构成一个全序，所以有\(f (\alpha), f (\beta)\)可比较。
根据假设，\(S\)有一个上界，我们说这个上界就是一个极大元素。为什么？因为假定存在一个更大的元素，那么它必然也在\(S\)中，故只能等于上界。
证毕
极大理想定理
接下来，我们用超穷归纳证明代数里面的一个结论（一般是用zorn引理证明）。
定理 9: 令\(I \neq (1)\)是交换群R的一个真理想，那么存在一个极大理想\(\mathfrak{m} \subseteq R\)包含I
证明 10:
令\(F\)为所有包含I的真理想构成的集合。我们对它进行超穷归纳，设存在一个同构\(f
: \alpha \rightarrow F\)。
类似地，我们枚举\(F\)中的元素构造一个全序。即
\[ g (\gamma) := \left\{\begin{array}{ll} \{ f (\gamma) \} & \textrm{如果} \{ f (\gamma) \} \cup \bigcup_{\beta < \gamma} g (\beta) \textrm{关于} \subseteq \textrm{构成一个全序}\\ \varnothing & 否则 \end{array}\right. \]那么只需要证明
\[ U := \bigcup_{\gamma < \alpha} g (\gamma) \]是一个极大理想即可。首先它包含\(I\)，其次它是一个理想：显然，任何在\(U\)中的元素必然存在某个真理想中。对任何\(a, b \in U\)，我们有\(a - b \in U\)，以及\(\forall r \in R, r a \in U\)。其次，\(U\)是一个极大理想：\(U \neq (1)\)，否则\(1\)存在于某个\(F\)中的成员。并且对于任何更大的理想，它必然也包含在\(U\)中，故\(U\)是一个极大理想。
取\(\mathfrak{m}= U\)即可。
总结
实际上本文举的例子直接使用良序定理就可以，因为构造过程没有涉及到对序数的讨论。那么为什么还要用超穷归纳呢？可能是闲的吧。