# Zorn 引理
Zorn 引理是数学中多处可见的重要结论
其证明在初学阶段会稍显复杂，不必强求全部理解
对于顺序集 (X,≤) 的子集 C⊆X，称 C 为 链 (Chain)「鎖」，当且仅当对于任意 a,b∈C，均有 a≤b 或 b≤a 成立，即可比较
定义
令 (X,≤) 为非空偏序集
若任意链均存在上界，则称该偏序集为 归纳的 (Inductive)「帰納的」
这一性质保证了构造最大元的过程中，能够通过极限序数的关卡，从而使超限归纳（或超限递归）的过程能够一直进行下去，直到被迫停止（即找到最大元）。
为了证明该结论，需要引入数个引理结论，以下默认记号 C 均为链
首先设归纳的偏序集 (X,⪯)，取链 C⊆X，定义
C^={x∈X∣∀c∈C:c≺x}
由于 c≺x 等价于 c⪯x 且 c=x，所以
C^=U(C)∖C
其中 U(C) 为 C 的上界集合
引理 1
若存在非空链 C，使得 C^=∅，则 X 存在极大元
证明
由于 X 是归纳的，所以 C 有上界
另一边根据定义，C^=∅ 意味着 C 的所有上界均在 C 中
因此 C 存在最大元 maxC
现在取 x∈X，满足 maxC⪯x
因为对于任意的 c∈C，都有 c⪯maxC，所以 c⪯x，因此 x 为 C 的上界
这也意味着 x∈C，由最大性可知 x=maxC，所以 maxC 为极大元
□
接下来证明可以取到这样的非空链
利用选择公理，对 X 的各个非空子集 A，取其中一元 xA∈A，考虑满足如下条件的链 K：
∀C⊆K:C^∩K=∅⟹xC^=min(C^∩K)
即对于 K 的任意子链 C，若 C^ 在 K 中非空，则取 C^ 在 K 中的最小元作为 xC^
设满足该条件的所有链构成集合 Ω
引理 2
令 K∈Ω, K^=∅，设 H:=K∪{xK^}，则
- ∀C⊆X:xC^∈C⟹C^∩H=∅
- H∈Ω
证明
(1)
令 C 为包含 xC^ 的链
任取 x∈K，因为 xK^∈K^，所以 x≺xK^
另一边由于 xC^∈C，所以 x 并非是 C 的上界，得到 C^∩K=∅
又因为 C^⊆X∖C，所以 xK^∈C^，最终得到 C^∩H=∅
(2)
因为 xK^∈K^，所以 xK^ 是 K 的上界
注意其可以与 K 中任意元比较，所以 H 也是链，需要证明 H 满足 Ω 的条件
任取 C⊆H，满足 C^∩H=∅，根据 (1) 可知 xC^∈C，所以 C⊆K
- 如果 C^∩K=∅，根据 K∈Ω 可知 xC^=min(C^∩K)
注意 xC^∈K，所以 xC^⪯xK^，因此 xC^=min(C^∩H) - 如果 C^∩K=∅，则 C^∩H={xK^}
任取 x∈C^,y∈K，因为 y∈C^，所以存在 c∈C 使得 y⪯c
此时，推移律给出 y≺x，所以 x∈K^，因此 C^⊆K^
又因为 C⊆K，所以 K^⊆C^，最终得到 C^=K^
从而 C^∩H={xK^}，所以 xC^=xK^=min(C^∩H)
□
设
K0:=K∈Ω⋃K
引理 3
对于任意 K∈Ω，均有 K0∖K⊆K^
证明
任取 y∈K0∖K，则存在 K′∈Ω，使得 y∈K′，设
C:={x∈K∣x⪯y}
那么 C 成为被 K∩K′ 包含的链
根据定义可以得知 y∈C^∩K′，所以得到
C^∩K′=∅,xC^=min(C^∩K′)⪯y
假设 C^∩K=∅，则根据 xC^ 的定义得知 xC^∈K∩K′
又因为 xC^⪯y 且 y∈K，所以得到 xC^≺y，这导致 xC^∈C 得到矛盾
所以假设不成立，C^∩K=∅
那么，对于任取的 x∈K，由于 x∈C^，所以存在 c∈C，使得 x⪯c
此时推移律得到 x≺y，因此 y∈K^
□
引理 4
K0∈Ω
证明
首先证明 K0 是链
任取 x,y∈K0 根据定义
{}^\exists K \in \Omega: x \in K$ - 如果 $y \in K$，则 $x$ 与 $y$ 可比较 - 如果 $y \not\in K$，则根据引理 3 可知 $y \in \hat K$ 因此 $x \prec y$，所以 $x$ 与 $y$ 可比较 所以 $K_0$ 是链 接下来证明 $K_0$ 满足 $\Omega$ 的条件 任取 $C \subseteq K_0$，满足 $\hat C \cap K_0 \neq \emptyset$，根据定义 $${}^\exists K \in \Omega: C \cap K \neq \emptyset
首先利用反证法证明 C⊆K
假设存在 c∈C，使得 c∈K，则根据引理 3 可知 c∈K^
因此 c∈C^∩K0，这与假设矛盾，所以假设不成立，C⊆K
所以 K∈Ω，根据定义可知
xC^=min(C^∩K)
又根据引理可知任意 K0∖K 的元都是 K 的上界，所以
min(C^∩K)=min(C^∩K0)
因此 K0∈Ω
□
如果 K^0=∅，则根据引理 2 得到 K0∪{xK^0}∈Ω
但是 K0 的定义指出对于任意 K∈Ω，均有 K⊆K0，所以 K0∪{xK^0}⊆K0，这导致矛盾
因此 K^0=∅，根据引理 1 可知 X 存在极大元
Zorn 引理得证。
