Zorn's Lemma

Zorn's Lemma陈述如下：在偏序集$P$中，如果$P$的每一条链都有一个$P$中元素作为上界，那么$P$中存在极大元。

Proof

反证法，假如$P$中没有极大元。那么对于$P$的任意一条链$C\subseteq P$，我们一定能在$P\setminus C$中找到一个元素作为$C$的上界（如果不是这样，那么既然$C$一定有一个上界，这个上界只能在$C$内部。如果$C$是无穷的，那么这是不可能的；如果$C$是有穷的，那么这个上界就是$C$的末端点，$P$中没有元素比它大，说明这是一个极大元，矛盾）。我们任取这样一个可行的上界，记为$g(C)$（其中，$g$是由我们的选择给出的$\mathscr{Pow} \ (P)\to P$的映射。注意，这里我们假设了集合论中的选择公理(Axiom of Choice)成立）。

对于$P$的任意子集$S$，记$S_{ < a }=\{x\in S\mid x<a\}$。称链$C$是一条$g$链，如果$C$中不存在无穷下降的子链（i.e. $c_i\in C,c_1>c_2>\cdots>c_n>\cdots$）且$\forall a\in C,g(C_{ < a })=a$。

下面我们证明(Lemma 1)：如果$A,B$是两条不同的$g$链，那么$\exists b\in B$，$A=B_{ < b }$与$\exists a\in A$，$B=A_{ < a }$中至少有一个成立（这个Lemma想说，两条不同的$g$链一定一条包含另一条，偏序集中只有一条“完整的”$g$链）。记$C=\{c\in A\cap B\mid A_{ < c }=B_{ < c }\}$。那么$C\subseteq A$。如果$C\neq A$，那么考虑$A\setminus C$，$A\setminus C$是$A$的子链，它一定有最小元（设为$a$），不然就无穷下降了。那么$A_{ < a }$中没有任何$A\setminus C$中的元素，而$A_{ < a}\subseteq A$，因此$A_{ <a}\subseteq C$。此时考虑$C\setminus A_{ <a}$，如果其中存在元素$c$，那么$c\not\in A_{ < a}$，也即$c\geq a$。而$a\in A\setminus C$，因此$a\not\in C$，因此$a\not\in C\setminus A_{ < a }$，因此$a\neq c$。所以$c>a$，所以$a\in A_{ < c }$。而$c\in C$，因此$A_{ < c }=B_{ < c }$。而$\forall c'\in A_{ < c }$，若$c'<c$，则$A_{<c'}=B_{<c'}$，且$c'\in A\cap B$，因此$c'\in C$。所以$A_{ < c }\subseteq C$，这说明$a\in C$，矛盾。 综上，$C\neq A\implies C=A_{ < a }$。对称地，$C\neq B\implies C=B_{ < b }$，其中$b$是$B\setminus C$的最小元。设$C\neq A$且$C\neq B$，那么$C=A_{ < a }=B_{ < b }$。根据$g$链的定义，$g(A_{ < a })=a$，$g(B_{ < b })=b$，而$A_{ < a }=B_{ < b }$，所以$g(A_{ < a })=g(B_{ < b })$，因此$a=b$。而$a\in A,b\in B$，所以$a\in C$。而$a\in A\setminus C$，矛盾。因此$C=A$与$C=B$中有且仅有一个成立（因为$A\neq B$）。假如$C=A$，那么$C\neq B$，这推出$C=B_{ < b }$，可见$A=B_{ < b }$；假设$C=B$，那么$C\neq A$，这推出$C=A_{ < a }$，可见$B=A_{ < a }$。证毕。

把所有的$g$链收集进集合$G$，记$E=\bigcup\limits_{C\in G}C$（$E\in \mathscr{Pow} \ (P)$）。下面我们证明$\forall a\in E$，如果$A\in G$且$a\in A$，那么$A_{ < a }=E_{ < a }$(Lemma 2)（这个Lemma想说：$E$中每个元素都满足，所有比它小的元素恰好就是这个元素所在的$g$链中比它小的元素）。显然$A\subseteq E$，因此$A_{ < a }\subseteq E_{ < a }$。那么只需证$E_{ < a }\subseteq A_{ < a }$。$\forall x\in E_{ < a }$，存在$B\in G$使得$x\in B$。对$B$分类讨论，如果$B\subseteq A$，那么$x\in A_{ < a }$；如果$B\not\subseteq A$，那么$A\neq B$，由Lemma 1可知$\exists b\in B,A=B_{ < b }$与$\exists a\in A,B=A_{ < a }$中至少有一个成立。后者意味着$B\subseteq A$，矛盾，因此一定是前者成立。因为$a\in A$，于是$a\in B_{ < b }$，所以$a<b$。而$x<a$，因此$x<b$。因此$x\in B_{ < b }$。因此$x\in A$。而$x<a$，因此$x\in A_{ < a }$。综上，$E_{ < a }\subseteq A_{ < a }$。证毕。

下面证明$E$是链。$\forall a,b\in E$，存在$A\in G$使得$a\in A$，存在$B\in G$使得$b\in B$。由Lemma 1可知，两条$g$链必然有一条包含在另一条中。若$A\subseteq B$，则$a,b\in B$，因此可比较大小；若$B\subseteq A$，则$a,b\in A$，因此也可以比较大小。由此可见$E$中任意两个元素都可以比较大小，因此$E$是链。

下面证明$E$是$g$链。先证$E$没有无穷下降的子链。如果$E$有无穷下降的子链$a_1>a_2>\cdots$，设$a_1\in A$且$A\in G$，那么$\forall i>1,a_i<a_1$，因此$a_i\in E_{<a_1}$。由Lemma 2可知，$E_{<a_1}=A_{ < a }$。因此$a_i\in A_{ < a }$。这说明$A$有无穷下降的子链，与$A$是$g$链矛盾。再证$\forall a\in E,g(E_{ < a })=a$。设$a\in A,A\in G$，那么$g(A_{ < a })=a$。根据Lemma 2，$E_{ < a }=A_{ < a }$，因此$g(E_{ < a })=a$。

下面证明$F=E\cup \{g(E)\}$也是$g$链。$E$中元素可以两两比较大小，$g(E)$作为上界可以和所有$E$中元素比较大小，因此$F$中元素可以两两比较大小；因为$E$中不存在无穷下降的子链，因此加上一个元素后还是不存在无穷下降的子链；$\forall a\in E$，因为$E$是$g$链，$g(E_{ < a })=a$，而$(E\cup \{g(E)\})_{<g(E)}=E$，因此$g((E\cup \{g(E)\})_{<g(E)})=g(E)$。综上，$F$是$g$链。

$\forall E'\in \mathscr{Pow} \ (P)$，如果$E'$是$g$链，那么$E'\subseteq E$。而$F$是$g$链，可是$F\not\subseteq E$。矛盾。

Qed.

Remark

上述证明过程用到了选择公理（给定一族集合，那么可以从每个集合中选一个元素组成一个新的集合）。事实上可以证明，在集合论的ZF公理体系下，如果承认除了选择公理以外的其它公理以及Zorn's Lemma，那么可以推出选择公理。这说明，Zorn's Lemma是集合论的ZF公理体系中选择公理的等价表述。