選択公理はツォルンの補題を導く

選択公理 $\implies$ ツォルンの補題を証明する(他の同値性は標準的だがより長い;この方向は代数学で絶えず使われる方向である)。$(P, \le)$ をすべての鎖が $P$ 内に上界を持つ空でない半順序集合とし、矛盾を導くために $P$ に極大元がないと仮定する。

$P$ に極大元がないので、すべての $x \in P$ は $P$ 内に厳密な上界(ある元 $y$ で $x < y$)を持つ:さもなければその $x$ 自身が極大となる。特に、すべての鎖 $C \subseteq P$ は(仮定により)上界を持ち、その上界自体もまた厳密な上界を持つので、すべての鎖は $P$ 内に厳密な上界を持つ。

選択公理により、すべての鎖 $C \subseteq P$ に対して、鎖 $C$ の厳密な上界 $g(C)$ を選ぶ選択関数を固定する。$g$ を用いて、すべての順序数 $\alpha$ で添字づけられた超限列 $(a_\alpha)$ を構成する:$a_0 = g(\emptyset)$ とし、各順序数 $\alpha$ について、すべての $\beta < \alpha$ に対して $a_\beta$ がすでに定義されているとき、集合 $\{a_\beta : \beta<\alpha\}$ は鎖である(構成により、新しい各項はそれ以前のすべての項の厳密な上界である)ので、$a_\alpha = g(\{a_\beta : \beta<\alpha\})$ と定義し、これはそれ以前のすべての項の厳密な上界である。

これにより、順序数から $P$ への狭義単調増加な写像が得られる:$\alpha < \beta \implies a_\alpha < a_\beta$。しかし順序数全体は集合をなさない(すべての順序数からなる集合は存在しない)一方、$P$ は通常の集合である;順序数から $P$ への狭義単調増加な写像は、順序数の濃度が $P$ 以下であることを意味し、どんな集合もすべての順序数ほど大きな集まりの上へ単射で写ることはできないという事実(置換公理の帰結)に矛盾する。この矛盾は「$P$ に極大元がない」という仮定が偽であることを示し、よって $P$ は極大元を持ち、選択公理からツォルンの補題が証明される。