Zorn's Lemma

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

Proof

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

对于的任意子集，记。称链是一条链，如果中不存在无穷下降的子链（i.e. ）且。

下面我们证明(Lemma 1)：如果是两条不同的链，那么，与，中至少有一个成立（这个Lemma想说，两条不同的链一定一条包含另一条，偏序集中只有一条“完整的”链）。记。那么。如果，那么考虑，是的子链，它一定有最小元（设为），不然就无穷下降了。那么中没有任何中的元素，而，因此。此时考虑，如果其中存在元素，那么，也即。而，因此，因此，因此。所以，所以。而，因此。而，若，则，且，因此。所以，这说明，矛盾。 综上，。对称地，，其中是的最小元。设且，那么。根据链的定义，，，而，所以，因此。而，所以。而，矛盾。因此与中有且仅有一个成立（因为）。假如，那么，这推出，可见；假设，那么，这推出，可见。证毕。

把所有的链收集进集合，记（）。下面我们证明，如果且，那么(Lemma 2)（这个Lemma想说：中每个元素都满足，所有比它小的元素恰好就是这个元素所在的链中比它小的元素）。显然，因此。那么只需证。，存在使得。对分类讨论，如果，那么；如果，那么，由Lemma 1可知与中至少有一个成立。后者意味着，矛盾，因此一定是前者成立。因为，于是，所以。而，因此。因此。因此。而，因此。综上，。证毕。

下面证明是链。，存在使得，存在使得。由Lemma 1可知，两条链必然有一条包含在另一条中。若，则，因此可比较大小；若，则，因此也可以比较大小。由此可见中任意两个元素都可以比较大小，因此是链。

下面证明是链。先证没有无穷下降的子链。如果有无穷下降的子链，设且，那么，因此。由Lemma 2可知，。因此。这说明有无穷下降的子链，与是链矛盾。再证。设，那么。根据Lemma 2，，因此。

下面证明也是链。中元素可以两两比较大小，作为上界可以和所有中元素比较大小，因此中元素可以两两比较大小；因为中不存在无穷下降的子链，因此加上一个元素后还是不存在无穷下降的子链；，因为是链，，而，因此。综上，是链。

，如果是链，那么。而是链，可是。矛盾。

Qed.

Remark

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