こんにちは。TAMAGOと申します。
　本記事は2019年度 traP Advent Calendar $n$日目の記事です。($n=50$)

今日は数学のお話をします.より具体的に言うと,集合論における重大な命題である選択公理を仮定してZornの補題の証明を行います.

はじめに

この記事は私が集合論を勉強していて「Zornの補題ナンもわからん(逆ギレ)」となったのをきっかけに書いた記事です.自分が読んでいた本(参考文献[1],[2])をベースに,より人に優しい説明を心がけました.
　基本的に集合論の本を読んだことがある程度の人間を読者として想定してはいますが,なるべく必要な前提知識は少なくしました.

証明に必要なものの定義

Zornの補題の証明に必要な用語をいくつか定義しておきます.

極大元

順序集合$A$の中で,ある$a\in A$に対して$a<x$となる$x\in A$が存在しないとき,aを極大元という.

帰納的

順序集合$A$の任意の空でない全順序部分集合に上限が存在するとき,$A$を帰納的な順序集合という.

整列集合

全順序集合で,任意の空でない部分集合に最小元が存在しているような集合を整列集合という.

証明

選択公理

集合族$(A_{\lambda }{)}_{\lambda \in \Lambda }$について,すべての$\lambda$で$A_{\lambda }$が空集合でないとき,集合族の直積${\prod }_{\lambda \in \Lambda }{A}_{\lambda }$は空でない.

言葉の意味さえわかればあまりにも直観的な主張ですね.これを出発点としてZornの補題を示します.

Zornの補題

帰納的な順序集合には極大元が存在する.

ここで,やや突然ですが,順序集合$X$が極大元を持つという命題の否定,すなわち

順序集合$X$が極大元を持たない.

ことについて考えましょう.これを具体的な$x$の元に言及して,

$\forall x\in X$について,$x<x^{\prime }$となる$x^{\prime }\in X$が存在する

といいかえてみます.この主張は$x\in X$に対して$x^{\prime }\in X$を対応させているかのように見えますよね.そこで,以下のような写像$f$を考えてみましょう.

任意の$x\in X$について,$f(x)>x$が成り立つ.

このような$f$が存在すれば,$X$が極大元を持たないことは明らかといって良いでしょう.では,その逆はどうでしょうか.次の命題を示しましょう.

$X$が最大元を持たないとき,$\forall x\in X[f(x)>x]$となる$f$が存在する

$x\in X$に対して,集合$M_X=\{y|y>x\}$を考えると,定義からこれは空ではない.よって選択公理から${\prod }_{x\in X}{A}_x$も空でない.
　この集合の元$(a_{\lambda }{)}_{\lambda \in X}$を一つとり,$x$を$a_x$に対応させる写像を$f^{\prime }$とする.このとき,$f$は$x\in X$から$y\in M_x(\subset X)$への写像であるので,$f^{\prime }(x)\in X$であり,$M_x$の定義から$x<f^{\prime }(x)$となる.(証明終)

さて,上の命題を証明するのに選択公理を使いましたが,この対偶をとると,条件を満たす$f$が存在しないならば$X$は最大元が存在する と言い換えることができます.
　Zornの補題の証明のためにこの命題を経由すれば,残りの示すべき部分は

$X$が帰納的な順序集合であるとき,$\forall x\in X[f(x)>x]$となる$f$は存在しない

ですね.これを示すために命題を次のように言い換えて観ましょう.

$\varphi (x)\ge x$となる関数$\varphi$全体
の集合を$F$とする.$F$は空ではない.(実際,$\varphi (x)=x$とすれば条件を満たす.)
　$F$の任意の写像$\varphi$に対して,$\varphi (a)=a$となる$a\in A$が存在していれば,命題の条件を満たす$f$は存在しない.

これを示すためには,指定された$\varphi$に対して$\varphi (a)=a$となる$a$を用意してくれば良いですね。ここでの方針として,$a$と$\varphi (a)$をともに含むような集合を用意し,その集合の最大元が$a$になるようにとって行きます.

ここで,ある$x_0\in X$を含む整列集合$W(\subset X)$であり,以下の条件を満たすような集合を考える.

1. $x\in W$に対して$y<x$となる最大の元$y\in W$が存在するとき,(すなわち$W$における$x$の"直前の元"があるとき,)$\varphi (y)=x$
2. 上記の$y$が存在しないとき,$W$の部分集合$W_x=\{y\in W|y<x\}$の$X$における上限が$x$と一致する(このような部分集合を$W$の$x$による切片という).

例えば,$\{x_0\}$は条件を満たす.また,$\{x_0,\varphi (x_0)\}$も条件を満たす.
　このような$W$全体の集合系$V$を考えたとき,Vの元$W_1,W_2$を考えると,整列集合の性質からこの二つは同型または一方が他方の切片と同型である.
ここで$W_1,W_2$はともに最小限として$x_0$をもつことに気を付けると,超限帰納法からこの二つは一致または一方が他方の切片と一致することがわかる.($\because$$W_1$が$W_2$の切片と同型とすると.順序同型な単射$g$が取れる.この写像が恒等写像になっていること($g(w)=w$)を示せばよい.両者の最小限が同じこと,および$w$以下の元で成り立つならばそれぞれの集合の直後の元も等しいことが条件からいえる.)

ここで,$V$のすべての和集合を$W^{\ast }$とすると,これも$V$の元であることを示そう.
　$W^{\ast }$の任意の元$w$について,$w\in A$となる$A\in V$が存在している.このとき,$A$に条件1.を満たす$y$が存在していれば$y\in W^{\ast }$であり,存在していないのなら当然条件2.を満たす.
よって,$W^{\ast }$は$V$の元であり,任意の$W\in V$に対して$W\subset W^{\ast }$が成り立つので,$W^{\ast }$は$V$の包含における最大元である.

ここで,$A$が帰納的であるという過程から$W^{\ast }$には上限が存在する.この上限を$a$とすると,$a\in W^{\ast }$である.実際,$a\notin W$とすると$W^{\ast }\cup \{a\}$が$V$の元となり$W^{\ast }$が最大であることと矛盾する.

さて,この$a$について$\varphi (a)$を考える.$\varphi (a)>a$と仮定すると,$W^{\ast }\cup \{\varphi (a)\}$について,$\varphi (a)$に対する$a$は条件1.において$x$に対する$y$となるので,これは$V$の元となる.
$W^{\ast }\subset W^{\ast }\cup \{\varphi (a)\}$より,やはり$W^{\ast }$が包含の最大元になることと矛盾する.
よって$\varphi (a)=a$が成り立つ.

以上のことをまとめると,次のようになります.
1.集合$X$の全順序部分集合で,与えられた$\varphi$に対して特殊な条件をみたす集合全体の集まりを$V$とする.
2.その$V$の中から最大な集合$M$を持ってくると,$X$は帰納的なので上限が存在し,その上限は$M$の最大元と一致した.
3.こうしてできた$M$の最大元$A$は$\varphi (a)=a$を満たす.

このような手順を踏むことで,どんな写像$\varphi$に対しても$\varphi (a)=a$となる$a\in X$が存在しているため,常に$f(a)>a$が成り立つような写像$f$は存在しない.

これと前半を組み合わせればZornの補題が示された.

おわりに

†いかがでしたか？†

特に後半はやや複雑になってしまいましたが,証明の流れや気持ちだけでも汲み取っていただけるとありがたいです.より詳しい解説や別証明,Zornの補題の応用例などを知りたい場合,下記の参考文献を参照してください.
　この記事を呼んで数学が面白いと思ったそこのあなたはぜひ数学系に来てね！
明日はyou10さんとひなるひさんの記事です.楽しみですね！
それではまた.あしたもみてね！

参考文献

[1]松坂和夫/集合・位相入門,岩波書店 1968
[2]内田伏一/集合と位相,裳華房 1986

追記

証明の一部に誤り・紛らわしい部分があったため修正・加筆を行いました(12/23)