ツォルンの補題
こんにちは,ぱいです.
寒いですね.寒いのに雪が降らない.
雪が降れば寒くてもちょっとワクワクするのにね.こんなこと言ったら雪国の人たちに殴られそうだけど.
にゃーんって感じです.
そういえばなんかツイッターのアカウントが消えてますけどまあ寂しくなったら多分また復活します.
にゃーん.
ところで,
年末ぐらいに,選択公理⇔Zornの補題 の証明を書こーってツイートした記憶があるので,忘れないうちに書いておきますね.
とりあえず主張を.
任意の非空集合族$\{X_{\alpha}|\alpha\in A\}$に対して,$\varphi(\alpha)\in X_{\alpha}(\forall\alpha\in A)$となる写像$\varphi:A\to \underset{\alpha\in A}{\cup}X_{\alpha}$(選択関数)が存在する.
任意の帰納的順序集合は極大元をもつ.
帰納的とか極大とかの定義をたぶん前までの記事で書いてないので書いときます.
順序とかの定義はたぶんどこかで書きました.わからなかったら過去記事を漁ってください.
順序集合$X$が帰納的である.$\overset{def}{\Leftrightarrow}$任意の全順序集合$Y\subseteq X$が$X$で上限をもつ.
(順序集合$X$で)$m\in X$が極大である.$\overset{def}{\Leftrightarrow}$$m\leq a\Rightarrow m=a(\forall a\in X)$.
最大と極大ってなんかややこしいですよね.
僕は最初のころどう違うのかよく分かんなかったです（）
最大元はどの元と比べても一番大きいやつで,極大元は比べられる元たちの中では一番大きいものという感じです.
さて、次の定理を考えてゆきましょー.
定理.
この定理を示していく前に,ひとつ命題を紹介しておきます.
任意の半順序集合は(包含関係で)極大な整列部分集合を含む.
(この命題を☆と呼ぶことにします.)
この命題☆について,次が成り立ちます.
この補題を使うと定理の証明が少し楽になる(気がする)ので,まずはこれから考えてゆきましょー.
細かい記号とかは前の記事とかを参照してください.$W<a>$で切片とか.
(補題の証明)
任意の帰納的集合$X$を考える.
$X$の整列部分集合全体の集合を$\mathbb{A}$とすると,☆の条件から$\mathbb{A}$は包含関係での極大元$M $をもつ.
いま$X$は帰納的なので,$M $は上界$a$をもつ.
このとき,じつは$a\in M $となる.
それを背理法で示す.
$a\notin M $と仮定する.
$N:=M\cup\{a\}$に次のように順序を入れる.
$\forall x,y\in N,x<_{N}y\overset{def}{\Leftrightarrow}x<_{M}y\lor y=a.$
すると$N$は整列集合となり$N<a>=M$となるが,これは$M $の極大性に反する.
よって$a\in M $である.
したがって,$a$は$M $の最大元である.
また,$a<_{X}b$となる$b\in X$が存在すると仮定すると,$M\cup\{b\}$でさっきと同じ議論をして矛盾が出てくる.
よって,この$a$が$X$の極大元である.$■$
はいじゃあ今度は定理のほうを証明していきましょー.
いま示した補題を使ったら,このあいだの記事で選択公理から整列定理を示したのとほとんど同じやり方で証明ができます.
任意の半順序集合$X$を考える.
$\varphi:2^X\to X$を選択関数とする.つまり,$\forall Y\subseteq X, \varphi(Y)\in Y$.
また,$X$の整列部分集合全体を$\mathbb{W}$として,$A$で添え字づけて$\mathbb{W}=\{W_{\alpha}|\alpha\in A\}$としておく.
そして$W=\underset{\alpha\in A}{\cup}W_{\alpha}$としておく.
あと,各部分集合$Y\subseteq X$についての次の性質をPと呼ぶことにする.
(P1)$Y$は整列集合である.
(P2)各$y\in Y$について$P_{Y}(y):=\{x\in X|\forall p\in Y<y>,p<_{Y}y\}$として,$y=\varphi(P_{Y}(y))$となる.
性質Pをみたす集合全体を$\mathbb{Y}$として,$\mathbb{Y}$を$\Lambda$で添え字づけて$\mathbb{Y}={Y_{\lambda}|\lambda\in\Lambda}$としておく.
また,$Y=\underset{\lambda\in\Lambda}{\cup}Y_{\lambda}$とする.
整列定理のときみたいに,3つのステップに分けて考えていきます.
ステップ１
各$\lambda,\mu\in\Lambda$について次のうち1つのみが必ず成り立つ.
(ア)$Y_{\lambda}=Y_{\mu}$.
(イ)$\exists l\in Y_{\lambda},Y_{\lambda}<l>=Y_{\mu}$.
(ウ)$\exists m\in Y_{\mu},Y_{\lambda}=Y_{\mu}<m>$.
ステップ２
$Y$は性質Pをみたす.
ステップ3
$Y$は$\mathbb{W}$の極大元である.
じゃあ,順番に示していきます.
(ステップ１)
整列集合の比較定理から,各$\lambda,\mu\in\Lambda$について次のうち1つのみが必ず成り立つ.
(あ)$Y_{\lambda}\cong Y_{\mu}$.
(い)$\exists l\in Y_{\lambda},Y_{\lambda}<l>\cong Y_{\mu}$.
(う)$\exists m\in Y_{\mu},Y_{\lambda}\cong Y_{\mu}<m>$.
まず(あ)が成り立つ場合を考える.
$f:Y_{\lambda}\to Y_{\mu}$を順序同型写像とすると,$f$は恒等写像となる.
それを背理法で示す.
$f$が恒等写像でないと仮定する.
すると,$S:=\{y\in Y_{\lambda}|f(y)\neq y\}$として$S\neq\emptyset$となる.
そこで$S$の$\leq_{Y_{\lambda}}$での最小元$m $が取れる.
ここで,整列定理のときの証明と同じようにして$Y_{\lambda}<m>=Y_{\mu}<f(m)>$とわかる.
このとき,$P_{Y_{\lambda}}(m)=P_{Y_{\mu}}(f(m))$となり$m=\varphi(P_{Y_{\lambda}}(m))=\varphi(P_{Y_{\mu}}(f(m)))=f(m)$となる.
ところがこれは$m\in S$に反する.
よって$f$は恒等写像となる.
したがって(ア)が成り立つ.
同様にして,(い),(う)に対してそれぞれ(イ),(ウ)が成り立つ.$■$
(ステップ２)
$Y$に整列定理の証明のときと同じ順序を入れておく.
すると$Y$は(P1)をみたす.
あとは$Y$が(P2)をみたすことを示せばよい.
任意の$y\in Y$を考えると,ある$\lambda\in\Lambda$で$y\in Y_{\lambda}$となる.
このとき,整列定理のときの証明と同じで$Y<y>=Y_{\lambda}<y>$となる.
すると$P_{Y}(y)=P_{Y_{\lambda}}(y)$となり,$\varphi(P_{Y}(y))=\varphi(P_{Y_{\lambda}}(y))=y$となる.
よって$Y$は性質Pをみたす.$■$
(ステップ３)
背理法で示す.
$Y$が$\mathbb{W}$の極大元でないと仮定する.
すると,ある$\alpha\in A$で$Y\underset{\neq}{\subset}W_{\alpha}$となる.
そこで,$a\in W_{\alpha}-Y$をとり,$Z:=Y\{a\}$とする.
$Z$には次のように順序を入れておく.
$\forall z,w\in Z,z<_{Z}w\overset{def}{\Leftrightarrow}z<_{Y}w\lor w=a$.
すると$Z$は(P1)をみたす.
また,$Y$は(P2)をみたすし$P_{Z}(a)=\{a\}$より$\varphi(P_{Z}(a))=a$なので,$Z$は(P2)もみたす.
よって$Z\in\mathbb{Y}$となるので,$Z\subseteq Y$つまり$a\in Y$となる.
ところがこれは$a$の取り方に反する.
よって$Y$は$\mathbb{W}$の極大元である.$■$
以上のステップから,選択公理⇒☆が示された.
こっちは割りとあっさりしています.
任意の非空集合族$\{X_{\alpha}|\alpha\in A\}$を考える.
$F:=\{f:B\to\underset{\alpha\in A}{\cup}:選択関数|B\subseteq A\}$とすると,$F$は帰納的な集合となる.
よって,Zornの補題から$F$は極大元$m:M\to\underset{\alpha\in A}{\cup}X_{\alpha}$をもつ.
このときじつは$M=A$である.
それを背理法で示す.
$M\neq A$と仮定すると,$\lambda\in A-M$が取れる.
この$\lambda$に対して,$a\in X_{\lambda}$が取れる.
そこで$N:=M\cup\{\lambda\}$として,$f:N\to\underset{\alpha\in A}{\cup}X_{\alpha}$を各$\alpha\in N$に対して次のように定める.
$\alpha\in M$なら$f(\alpha)=m(\alpha)$,$\alpha=\lambda$なら$f(\alpha)=a$.
するとこの$f$は選択関数になっていて,$m\underset{\neq}{\subset}f$である.
ところがこれは$m $の極大性に反する.
よって$M=A$となるので,$m $が$\{X_{\alpha}|\alpha\in A\}$の選択関数となっている.$■$
はいおしまい.
選択公理⇒☆⇒Zornの補題⇒選択公理 というふうに証明をしたので,じつは命題☆も選択公理と同値だったんですね～.
あ,そういえば明けましておめでとうございます.
参考文献
