这一节只有一个主题:Zorn引理,证明过程很长!
很多存在性定理,经常会归结到一个偏序集以及一个最大元的存在性,这其中Zorn引理是最重要的一个.
Zorn引理(Zorn’s lemma)：若$X$是一个偏序集(partially set),它的每一个链(chain)都存在上界(upper bound),那么$X$中包含一个最大元(maximal element).
链(chain)是一个全序集,这里所谓$X$中的chain是指$X$的子集,它自身构成一个全序集.
设$A$是$X$中的一个链,则根据题设要求,$X$中存在$A$的一个上界,这个上界不一定属于$A$,Zorn引理的结论是,存在一个元素$a \in X$,对于任意$x \in X$,如果$a \le x$,那么必有$a=x$.
直观的,既然$X$非空,那么存在$x_0 \in X$,如果它是最大元,那就可以停止了.否则,存在$x_1$严格大于$x_0$,若$x_1$是最大元,停止,否则继续,Zorn引理是说,这个过程最终将能得到有一个最大元.
这里面前面部分没有问题,问题在于最后一步,因为这里是可能是一个无限过程,它会停止吗?这也是这里的困难所在,因为完全可能出现,上面的过程永远得不到最大元,或者说得到是一个non-maximal elements序列,此时怎么办?其实此时这个序列本身是$X$中的链,从而有上界,于是从这个上界开始,继续上述过程,这个过程何时结束,会如何结束,在这里还是不清晰的,我们需要更明确的证明过程,书中的方法来自Zermelo.
首先把抽象的偏序具体化:使用集合的包含关系.把问题进行转化,把抽象的变具体,通常是我们解决问题的思路所在.考虑weak initial segment $\bar{s}(x)$.用$\mathscr{S}$来表示$\bar{s}$的值域.$\mathscr{S}$是$P(X)$的子集.可以用包含关系形成一个偏序.$\bar{s}$是一个一一映射.并且$\bar{s}(x) \subset \bar{s}(y)$的充分必要条件是$x \le y$.于是寻找$X$中的最大元,实际上成了寻找$\mathscr{S}$中的最大元.关于$X$中的链的假设对应于$\mathscr{S}$中的链.
用$\mathscr{X}$表示$X$中所有链的集合.这样的话$\mathscr{X}$也是$P(X)$的子集.$\mathscr{X}$中的每一个元素包含在某个$\bar{s}(x)$中,$\mathscr{X}$非空,我们以包含关系作偏序.若$\mathscr{C}$是$\mathscr{X}$中的一个链,那么$\bigcup_{A \in \mathscr{C}}{A}$属于$\mathscr{X}$,由于$\mathscr{X}$中的每一个集合包含在$\mathscr{S}$的某个集合中,从$\mathscr{S}$到$\mathscr{X}$这一个过程中没有引入新的最大元(maximal element).
$\mathscr{X}$的好处:首先它把条件中关于链的假设更加具体化了,对于$\mathscr{S}$中的每一个链$\mathscr{C}$有上界,$\mathscr{C}$中集合的并集是$\mathscr{C}$的上界,它属于$\mathscr{X}$;另一方面,$\mathscr{X}$包含它的每一个元素的所有子集,这使得我们可以通过每次给non-maximal集合添加一个元素来逐步放大.
至此,我们可以抛开$X$中的偏序,只需要考虑非空集合$X$的子集簇$\mathscr{X}$.根据上面的讨论$\mathscr{X}$满足两个条件:(1)$\mathscr{X}$的每一个元素的任一子集属于$\mathscr{X}$.它说明$\emptyset \in \mathscr{X}$;(2)$\mathscr{X}$中的每一个链中集合的并集属于$\mathscr{X}$.我们需要证明$\mathscr{X}$中存在最大元.
设$f$为$X$上的选择函数,即$f:P(X)-\{\emptyset\}\to X$,并且$f(A) \in A$,$\forall A \in \text{dom}f$,对于$A \in \mathscr{X}$,我们定义$\hat{A}=\{x \in X: A \cup \{x\} \in \mathscr{X}\}$,定义映射$g:\mathscr{X}\to\mathscr{X}$,
\[g(A)=\begin{cases}
A \cup \{f(\hat{A}-A)\},&\quad\hat{A}-A\neq\emptyset\\
g(A)=A,&\quad\hat{A}-A=\emptyset
\end{cases}\]
若$\hat{A}-A\neq\emptyset$,令$g(A)=A \cup \{f(\hat{A}-A)\}$,若$\hat{A}-A=\emptyset$,令$g(A)=A$.根据$\hat{A}$的定义,$\hat{A}-A=\emptyset$当且仅当$A$是一个最大元.也就是说我们需要证明存在$A \in \mathscr{X}$,使得$g(A)=A$.注意到$A \subset g(A)$,并且$g(A)$最多比$A$多一个元素.
为方便,引入一个临时定义:称$\mathscr{X}$的一个子集$\mathscr{J}$是tower,如果
(i) $\emptyset \in \mathscr{J}$;
(ii) 若$A \in \mathscr{J}$,则$g(A) \in \mathscr{J}$;
(iii) 若$\mathscr{C}$是$\mathscr{J}$中的链,则并集$\bigcup_{A \in \mathscr{C}}{A} \in \mathscr{J}$.
Tower是存在的,$\mathscr{X}$本身就是一个,并且Tower的交集还是一个Tower,于是令$\mathscr{J}_0$表示所有tower的交集.则$\mathscr{J}_0$是最小的tower,我们来证明$\mathscr{J}_0$是一个链.
称$\mathscr{J}_0$中的集合$C$是comparable,如果它和$\mathscr{J}_0$中的任意元素都是comparable.于是$\forall A \in \mathscr{J}_0$,或者$A \subset C$,或者$C \subset A$.我们要证$\mathscr{J}_0$是一个链,意味着要证明$\mathscr{J}_0$中所有元素(集合)是comparable.comparable集合是存在的,$\emptyset$就是其中之一.下面的讨论暂时把注意力集中在一个任意的但是预先固定的comparable集合$C$.
设$A \in \mathscr{J}_0$,$A$是$C$的真子集,我们有$g(A) \subset C$.由于$C$是comparable,于是或者$g(A) \subset C$,或者$C$是$g(A)$的真子集,对于后一情形,$A$是$g(A)$的真子集的真子集,$g(A)-A$将会超过1个元素,不可能.
令$\mathscr{U}=\{A \in \mathscr{J}_0: A \subset C\text{或}g(C) \subset A\}$,$\mathscr{U}$中的所有元素和$g(C)$是comparable.因为若$A \in \mathscr{U}$,则由于$C \subset g(C)$,或者$A \subset g(C)$,或者$g(C) \subset A$.接下来证明$\mathscr{U}$是一个tower.
(i) $\emptyset \in \mathscr{U}$,因为$\emptyset \subset C$;
(ii) 欲证$A \in \mathscr{U}$,必有$g(A) \in \mathscr{U}$,分三步:(1)$A$是$C$的真子集;则$g(A) \subset C$,故$g(A) \in \mathscr{U}$;(2)$A=C$,则$g(A)=g(C)$,$g(C) \subset g(A)$,$g(A) \in \mathscr{U}$.(3)$g(C) \subset A$,则$g(C) \subset g(A)$,故$g(A) \in \mathscr{U}$.
(iii) 从$\mathscr{U}$的定义可知,$\mathscr{U}$中一个链的并集属于$\mathscr{U}$.
于是$\mathscr{U}$是一个tower,它包含于$\mathscr{J}_0$中,而$\mathscr{J}_0$是最小的tower,于是$\mathscr{U}=\mathscr{J}_0$.
上面的结论说明对于每一个comparable集合$C$,$g(C)$是comparable集合:给定$C$,按上述方式构造$\mathscr{U}$,从$\mathscr{U}=\mathscr{J}_0$说明若$A \in \mathscr{J}_0$,则或者$A \subset C$(从而$A \subset g(C)$),或者$g(C) \subset A$.
我们已经知道$\emptyset$是comparable,$g$把comparable集合映射到comparable集合,comparable集合构成的链的并集还是comparable集合,这说明$\mathscr{J}_0$中的comparable集合构成一个tower,comparable集合穷尽了$\mathscr{J}_0$,于是$\mathscr{J}_0$是一个链.$\mathscr{J}_0$中任一集合是comparable.既然$\mathscr{J}_0$是一个链,$\mathscr{J}_0$中所有集合的并集$A$属于$\mathscr{J}_0$,于是$g(A) \subset A$,另一方面$A \subset g(A)$,故$A=g(A)$.Zorn引理证毕.
习题:Zorn引理等价于选择公理.考察下面的结论,证明它们也等价于选择公理:(i)任一偏序集有一个最大链(maximal chain),也就是这个链不可能是其他链的真子集;(ii)偏序集的任一链包含在某个最大链中;(iii)每一个偏序集,如果任一链都有下界,那么这个偏序集必有一最大元(这里书中恐怕有问题,似乎应该是最小元).
对于集合$X$,考虑映射$f$:$\text{dom}{f} \subset P(X)$,$\text{ran}{f} \subset X$,$f(A) \in A$,$\forall A \in \text{dom}{f}$.以映射的扩张作为偏序,使用Zorn引理寻找一个最大元,并且证明若$f$是最大元,必有$\text{dom}{f} = P(X)-\{\emptyset\}$.