2019年12月19日 | ブログ記事

選択したり 極大元を取ったり

TAMAGO

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

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

はじめに

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

証明に必要なものの定義

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

極大元

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

帰納的

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

整列集合

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

証明

選択公理

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

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

Zornの補題

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

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

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

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

xX\forall x\in Xについて,x<xx<x'となるxXx'\in Xが存在する

といいかえてみます.この主張はxXx\in Xに対してxXx'\in X対応させているかのように見えますよね.そこで,以下のような写像ffを考えてみましょう.

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

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

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

xXx\in Xに対して,集合MX={yy>x}M_{X}=\{y|y>x\}を考えると,定義からこれは空ではない.よって選択公理からx XAx\prod_{x\in\ X}A_{x}も空でない.
 この集合の元(aλ)λX(a_{\lambda})_{\lambda \in X}を一つとり,xxaxa_{x}に対応させる写像をff'とする.このとき,ffxXx\in XからyMx(X)y\in M_{x}(\subset X)への写像であるので,f(x)Xf'(x)\in Xであり,MxM_{x}の定義からx<f(x)x<f'(x)となる.(証明終)

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

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

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

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

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

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

  1. xWx\in Wに対してy<xy<xとなる最大の元yWy\in Wが存在するとき,(すなわちWWにおけるxxの"直前の元"があるとき,)ϕ(y)=x\phi(y)=x
  2. 上記のyyが存在しないとき,WWの部分集合Wx={yWy<x}W_{x}=\{y\in W|y<x\}XXにおける上限がxxと一致する(このような部分集合をWWxxによる切片という).

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

ここで,VVのすべての和集合をWW^{*}とすると,これもVVの元であることを示そう.
 WW^{*}の任意の元wwについて,wAw\in AとなるAVA\in Vが存在している.このとき,AAに条件1.を満たすyyが存在していればyWy\in W^{*}であり,存在していないのなら当然条件2.を満たす.
よって,WW^{*}VVの元であり,任意のWVW\in Vに対してWWW\subset W^{*}が成り立つので,WW^{*}VVの包含における最大元である.

ここで,AAが帰納的であるという過程からWW^{*}には上限が存在する.この上限をaaとすると,aWa\in W^{*}である.実際,a/Wa\notin WとするとW{a}W^{*}\cup\{a\}VVの元となりWW^{*}が最大であることと矛盾する.

さて,このaaについてϕ(a)\phi(a)を考える.ϕ(a)>a\phi(a)>aと仮定すると,W{ϕ(a)}W^{*}\cup\{\phi(a)\}について,ϕ(a)\phi(a)に対するaaは条件1.においてxxに対するyyとなるので,これはVVの元となる.
WW{ϕ(a)}W^{*}\subset W^{*}\cup\{\phi(a)\}より,やはりWW^{*}が包含の最大元になることと矛盾する.
よってϕ(a)=a\phi(a)=aが成り立つ.

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

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

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

おわりに

†いかがでしたか?†

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

参考文献

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

追記

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

この記事を書いた人
TAMAGO

数学とかをしています。1日十時間寝たい。

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2019年12月26日
アドベントカレンダーエンディング
HF
2019年12月25日
今からでも間に合う!?彼女(嫁/ママ/推し/etc...)とデートしよう!
chuukunn
2019年12月25日
TensorFlow.jsでwasmを使ってみるためにコントリビュートした【AdC2019 56日目】
sappi_red
2019年12月25日
無料でDTM環境構築 電子音系編
liquid1224
2019年12月23日
無料でDTM環境構築 生音系編
kashiwade
2019年12月22日
部内製チャットサービス「traQ」UIのこれから 【AdC2019 53日目】
sigma

活動の紹介

カテゴリ

タグ