feature image

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

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

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

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

はじめに

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

証明に必要なものの定義

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

極大元

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

帰納的

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

整列集合

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

証明

選択公理

集合族について,すべてのが空集合でないとき,集合族の直積は空でない.

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

Zornの補題

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

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

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

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

について,となるが存在する

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

任意のについて,が成り立つ.

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

が最大元を持たないとき,となるが存在する

に対して,集合を考えると,定義からこれは空ではない.よって選択公理からも空でない.
 この集合の元を一つとり,に対応させる写像をとする.このとき,からへの写像であるので,であり,の定義からとなる.(証明終)

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

が帰納的な順序集合であるとき,となるは存在しない

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

となる関数全体
の集合をとする.は空ではない.(実際,とすれば条件を満たす.)
 の任意の写像に対して,となるが存在していれば,命題の条件を満たすは存在しない.

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

ここで,あるを含む整列集合であり,以下の条件を満たすような集合を考える.

  1. に対してとなる最大の元が存在するとき,(すなわちにおけるの"直前の元"があるとき,)
  2. 上記のが存在しないとき,の部分集合における上限がと一致する(このような部分集合をによる切片という).

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

ここで,のすべての和集合をとすると,これもの元であることを示そう.
 の任意の元について,となるが存在している.このとき,に条件1.を満たすが存在していればであり,存在していないのなら当然条件2.を満たす.
よって,の元であり,任意のに対してが成り立つので,の包含における最大元である.

ここで,が帰納的であるという過程からには上限が存在する.この上限をとすると,である.実際,とするとの元となりが最大であることと矛盾する.

さて,このについてを考える.と仮定すると,について,に対するは条件1.においてに対するとなるので,これはの元となる.
より,やはりが包含の最大元になることと矛盾する.
よってが成り立つ.

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

このような手順を踏むことで,どんな写像に対してもとなるが存在しているため,常にが成り立つような写像は存在しない.

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

おわりに

†いかがでしたか?†

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

参考文献

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

追記

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

TAMAGO icon
この記事を書いた人
TAMAGO

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

この記事をシェア

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

関連する記事

2019年12月21日
モデリングを始めてみたい君へ、MagicaVoxelのススメ
isak icon isak
2019年12月13日
ゲーム紹介「League of Legends」【AdC2019 44日目】
Yataka_ML icon Yataka_ML
2019年12月25日
TensorFlow.jsでwasmを使ってみるためにコントリビュートした【AdC2019 56日目】
sappi_red icon sappi_red
2019年12月25日
無料でDTM環境構築 電子音系編
liquid1224 icon liquid1224
2019年12月4日
部内製チャットサービス「traQ」UIのこれまで 【AdC2019 35日目】
spa icon spa
2019年12月23日
無料でDTM環境構築 生音系編
kashiwade icon kashiwade
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記