Zorn の補題と選択公理のお話

(about Zorn's Lemma and Axiom of Choice)

by Akihiko Koga
6th Aug. 2018 (Update)
1st Aug. 2018 (First)

集合,位相,論理など へ
ホームページトップへ戻る

目次

概要

動機

日記にも書いたが,ここしばらく選択公理からZornの補題 (ツォルンの補題) の証明を独力でやろうと 四苦八苦していて,先日(2018年7月26日(木))ようやく完了した.実は,はずかしいくらい 長い時間をかけた(日記には書いたが,こちらにはとても書けない).色々考えたことも あったので,ここではそういうことも含めながら,選択公理と Zorn の補題に 関すること(証明のアプローチ,証明,応用,関連事項)を書こうと思う.ここで書く 話題は,どちらかと言うと,選択公理より Zorn の補題に重きを置くと思う.また,自分が長い時間をかけたこともあり,Zorn の 補題は,その証明を直接書くより,どこが難しいのかや,関連する周辺のことを書いた方が 勉強になると思う.

ここの内容は Zorn の補題を独力で選択公理から証明してみようと思う人にとっては 一種のスポイラ(楽しみを台無しにしてしまうもの)となっているので注意してほしい. あと,申し訳ないが,ここの記述はまだバグが全部とれてないかもしれない. 間違いが混入しているかもしれないと思って読んで欲しい

また,上に書いたように紆余曲折を書くつもりなので,ここの記事は時間のある人用 になっている.Zorn の補題とその証明,応用を手っ取り早く 知りたいという人は,そういう内容が世の中の集合論や順序集合に関する教科書には 載っているのでそれを参照すればよいと思う.このページの終わりにも 参考文献をあげておくので参照していただきたい.


選択公理とZorn の補題の内容

とりあえず,選択公理と Zorn の補題の内容を書いておく. まずは選択公理から.

選択公理(Axiom of Choice)

空集合でない集合の集合 X があるとき(つまり,x ∈ X ならば x は空でない集合),X の各集合から1つずつ要素を選ぶ関数

f : X → ∪X で f(x) ∈ x for ∀ x ∈ X

が存在する.

選択公理にはいくつかバリエーションがあるが, ここではそのうちの一つを載せた.他に,X の集合がお互いに交わりがないとか, ∪ X = B として,X 側を P(B) = 2B にするなどの バリエーションなどがある.当たり前の内容に思えるが,無限個の選択でも保証する ところにポイントがあるらしい.

次は Zorn の補題を書いておく.Zorn の補題は,チェイン(鎖)の上が「上限」か「上界」の二つのバージョンが あるようだが,ここではより条件のきつい「上限」版の方を載せておく.結局はそれらは同値 なのだが.

Zorn の補題(Zorn's Lemma)

(P, ≤) を任意のチェイン(P の中の部分集合で全順序集合になるもの.鎖ともいう)に 必ず上限がある 順序集合とする.このとき, P には少なくとも一つの極大元(それより大きい元が存在しない元)がある. (この補題の中の「上限」を「上界」に変えてもよい)

読み取りにくいかもしれないが,どの上昇列もどこかで止まっていたら, もう上に上がることができない元があるということである.これも 当たり前に見えるが,無限集合上の順序では威力を発揮する補題である.


Zorn の補題の成分表

通常,我々が使う素朴集合論を公理化したものとして,ZFC という体系がある. これはZermelo-Fraenkel + axiom of Choice の略である.前の2つは人の名前で その公理系に選択公理 (Axiom of Choice) を加えたという意味である.選択公理を取り除いた 体系は ZF の集合論 と言われる.ZFC も ZF も純粋に集合だけを扱う体系で, すべての集合のあつまりなどのクラスの概念は扱わない.ここらあたりの概要は 集合論のページ に載せた.

選択公理と Zorn の補題は同値な命題として扱われるが,

選択公理 → Zornの補題 の証明

は逆よりかなり難しい. 実際,これらが同値なのは ZF の集合論の下にであって,Zorn の補題には ZF 集合論の成分がかなりたくさん含まれている.つまり,

Zorn の補題 ← 選択公理 + 多くの ZF の公理と推論

となっているわけである.感覚的には次の図の右下側の配分位である (選択公理成分 : ZF 集合論成分 = 1 : 10 よりも ZF 集合論成分が多いかなと思う).

Zorn の補題の証明において,選択公理は,順序集合 (P, ≤) に,関数 f : P → P で,

    f(x) = x    if x が極大
         > x    otherwise

の存在を保証するだけである.そういう関数が存在すれば,ZF の集合論で,Zorn の 補題の残りの部分は証明できてしまう.つまり,

順序集合 (P, ≤) の任意のチェインに上限があり,関数 f : P → P で
    f(x) = x   if x が極大
         > x   otherwise
が存在すれば,P には少なくとも1つの極大元がある.

が,ZF 集合論の中で言えてしまうのである.


Zorn の補題は何に使えるのか

数学の中での利用と計算機科学の中での利用を考えてみる.私は計算機科学に興味があるので もっぱら,後者の話をする.

ということで,まず,数学での用途だが,無限回の選択操作をやらなければ構成できないものの存在証明に使える.こちらは私の専門という訳ではないので,いくつかの例を挙げておくだけにする.

数学における Zorn の補題の利用

計算機科学における Zorn の補題の利用

書いていると長くなってきたので,「これは読むのが怠い」と思い,中断した.そのうち整理してどこかに書くが,ここでは書きかけたことの概要だけ書いておく(ということで,数学の方の 分量の方が多くなってしまった).

計算機科学では,色々な概念を順序集合の中の不動点として表現することがしばしばある. 例えば,プログラムの意味は,プログラムの記述を汎関数(つまり, 関数を受け取って別の関数を返すもの)と考え,そのプログラムが表す汎関数の 最小不動点となる関数が,そのプログラムが表す意味とする理論 (領域理論 (domain theory) とか 表示的意味論 (denotational semantics))などがその例である.

もちろん,計算機科学は計算できないといけないので,通常,そのような不動点は 構成的な作り方をする

その構成的な作り方は工夫を要するので,とりあえず,存在だけ保証したいときに, Zorn の補題で保証しておけば,最低限の安心感は得られるかなというのが, 計算機科学での Zorn の補題に私が期待するところである.


主な証明方法の種類

Zorn の補題の証明方法は(私が知っているものは)次のような方針のものがある.

  1. 長いかもしれないチェインを作る
    P の任意の元 x0 から,上にたどって行って,もう,その上に他の元を 加えられない(長い)チェイン C を作り,その上限を ∨ C とする (∨ はその次の集合の上限を表す記号).このチェインは,場合によっては 長くない場合もあるが,最悪のケースは集合 P の大きさのチェインに なり得る.P は,自然数の集合 ω,2ω,... といくらでも 大きくなり得る.したがって,このチェインは,とてつもなく長くなり得る.

  2. 順序集合の不動点定理を使う
    順序集合 (Q, ≤) は,Q と関数 h : Q → Q に対してある条件を課すと不動点, すなわち, h(q) = q となる q ∈ Q の存在が言えることがある.例えば,Q が 完備束で, h が単調関数 (x > y ならば h(x) > h(y) が成立する関数)の場合, 不動点の存在が,選択公理なしに言える.したがって,上に書いた長いチェインが 不動点と なるような順序集合 Q ⊆ 2P と h : Q → Q を作ることが できれば,極大元に至るチェインをその不動点として求めることができる.

  3. 整列可能定理を使う
    (田中尚夫著「選択公理と数学-発生と論争,そして確立」, 1987年, 1999年, 2005年 など)

ここの考察や証明では,最初の,長いかもしれないチェインを構成することを考える.


インターネットで Zorn August Max lemma あたりで画像検索すると Zorn さんの顔写真がでてきます.あまり似てなくて申し訳ないですが,ご参考までに絵を描いてみました. 興味のある方はご自分で検索してみてください.

Wikipedia によると

Max August Zorn

1906-1993

だそうです.後に書いた年表によると Zorn の補題は 1935 年ですから,29歳のときですか.研究分野は, 集合論ではなく,抽象代数学, 群理論,数値解析なんですね.

何が難しいのか(長いチェインを作る証明について)

Zorn の補題に出てくる順序集合 (P, ≤) は任意のチェインに上限があるから,

もうその上に元を加えることができないようなチェイン C (⊆ P)
が見つかってしまえば,その上限 ∨C が極大元である.こういう, もうその上の元を加えていけないチェインを ここでは上に極大なチェインと呼ぶことにする.チェインとしては,下や, 元と元の隙間にまだ元を入れる余地はあるものの,上にはもう元を入れる余地が無いと いう意味を込めて「上に」という限定を付けている.

P のどれか適当な元 x0 をとって,それから,上にたどっていき,もう上がないところまでたどり着ければ問題ないのだが,なかなかそんなチェインが見つからないかもしれない.

我々の場合は,選択公理を仮定しているので,関数 f : P → P で,

    f(x) = x   if x が極大
         > x   otherwise
というものは存在すると仮定して話を進める.

●「上に極大なチェイン」を求めて

たぶん,最初の直観は,x0 から f で上に上に行けば良いのではないだろうかという予想を 訴えてくるだろう.(P, ≤) はすべてのチェインに上限があるから,x0 から f(x0), f2(x0), ... と求めて行って,その列と,その上限 ∨ n = 0 to ∞fn(x0) を合わせたチェインが上に極大なチェインの 第一候補となる.


これで極大元が見つかれば良いのだが容易に分かるようにまだその上があるかもしれない.


この構造は無限回繰り返されるかもしれない.


さらにこれらの無限回繰り返し自身を1つの単位として無限回繰り返される可能性 がある.


こうしたネストした繰り返しはいつまででも繰り返され得る.なにしろ,選択公理を 仮定すると,すべての集合,つまり,すべての実数の集合やその冪集合や,そのまた 冪集合が整列し得る訳であるから,この上昇列の繰り返しもそんなすべての集合サイズで 起こり得る.

ここで疑問を抱く方もいると思う.つまり,

今までの例で,確かにどれだけでも長いチェインが 発生し得ることを示して頂いた訳だが,結局,どれだけ長くても全部 チェインになっていた訳で,(P, ≤) のチェインには上限があるのだから, 問題ないのではないか?
という疑問である.

確かにこれは一理あるのだが,今までの例はチェインの途中で止めたらチェインと いう訳で,まだ上がある場合は「上に極大な」チェインは完成していない訳で, 上限をとって極大元が得られるチェインはまだ得られていないのではないだろうか.

それに対して,

だから,極大なチェインになるまで伸ばしてから考えれば良いのではないか?
という反論があるかもしれないが,それは極大元が存在するのとほぼ同等のことを 言っている訳で,話は堂々巡りになってるような気がする.

いや本当はこれで正しいのかもしれない.結局,何とか上に極大なチェインを作ることでしか 証明はできないわけで,ここでの議論を精密化すれば良いのかもしれない.

・・・・・・・・・・・・・・・・・・・・・・・・

・・・・・・・・・・・・・・・・・・・・・・・・

しかし,もうちょっとスカっとした明解な証明を追い求めて行こう(と思う).

こういう,直接,巨大なチェインを構成できないときは, その部分部分を作ってつなげば良いのではないだろうか.


●チェインを集めてつなぐ

部分部分を作ってつなぐというよりは,段々伸ばしていったチェインの集合を作り,それらの 和集合を作る方法である.つまり,次の図のように x0 から始めて, より上の元を選ぶ関数 f と上限をとる操作 ∨ で上に 伸ばしていったすべてのチェインの集合 C を考え,その和集合

C

を作ることによって,「上に極大な」チェインを作るのである.


これは一本の長いチェインを作るより気が楽である.チェインをたくさん集めたら, その中に本当に 長いチェインが入っているかもしれない.「投資信託」と同じ原理である.一つの株に 全財産を賭けると危ないので,複数の株を買って,リスクを分散するのである.すべての卵を 一つのカゴに盛ってはいけないのである.などとつまらないことを考えていないで, 話をもとに戻すと,この方法で気を付けないといけないことは次の図のように集めた チェインの集合の中に ∪ C で統合できないチェインを含めないこと である.


基本的には x0 から,f と,上限をとる ∨ の操作で作成したチェインは統合できるはずであるが, x0 以外の元から出発した元が混じっているとそれができない可能性がある.必ず,すべての 元が x0 から出発しているという条件をうまく表現してやる必要がある.


以上,方針の検討としてはかなり進めたと思う.後は,これを試行錯誤しながらでも 実現していくフェーズだ.頑張ろう.

幕間 - 集合論の数取りゲーム -

ここでちょっと気を抜いて,集合論のゲームみたいなものをやってみよう.ここのタイトル 「幕間(まくあい)」は英語では Interlude と言って, 演劇などの幕と幕の間の意味だ. ときどき,数学のテキスト (例えば, Tom Leinster の Basic Category Theory の第3章 "Interlude on sets") などでこのタイトルの章が設けてあったりして,いつか自分でも 使ってみようと思っていた.

では始めよう.

次のような2人でやるゲームを考える.このゲームをやる人を A さんと B さんとする. ゲームのルールは次の通りである.

ゲームのルール

B さんが持っている集合が有限集合の場合,A さんは毎回一番大きくなった集合を 提示すれば,B さんは新しい元を一つずつ差し出さざるを得ず,いつかは,すべての元を 含む集合が F にできて,A さんが勝つ.

では,B さんが持っている集合が無限集合だったらどうだろう?

B さんが最初に持っている集合を,すべての自然数の集合

N = {0, 1, 2, 3, ...}

としてみる.

このときは B さんは次々に偶数を出し続けることによって,奇数にはまったく手を 付けずにゲームを続けることができる.A さんは決して F に自然数の集合 N を作ることができない.

それでは再度,ほんの少しルールを変えてみる

A さんは,F の中の集合の和集合をとって,Fに 入れてよいものとする.この和集合の取り方は,無限個の和集合でもよいとする. なんで無限個の集合が F に入っているのかは,実は,出題者の私も 多少不思議に思うことがある.とにかく,このやり取りを無限回やってよいので, それで出来た無限個の集合の和集合を F に加えて,A さんの 次の番にそれを出せるとするのである.よけい混乱したら申し訳ない.

そうすると,今度は,いつの間にか A さんは偶数全部の集合を F に 持っているのである.持っている理由はこうである.まず,最初のやり取りを無限回 行うと,B さんは毎回次に大きい偶数を出し続けるので,A さんの F には {0, 2, ..., 2*n} n は自然数という偶数の有限集合でいっぱいになる.これらすべての 和集合を取ると偶数全体の集合になり,それを F にストックすることが できる.

ここで A さんはおもむろに,偶数全体の集合を提示すると,B さんは何か奇数を 出さざるを得ない.このようにして,A さんは最初の奇数 1 をゲットし,あとは 次々に残りの奇数をゲットしていって,ついには自然数全体をゲットしてしまう.

今まで仮想のゲームの話を自然語で話してきたので,曖昧なところもあったと 思う.そこで,話を数学に戻して,上の話で言いたかったことを少し正確に記述してみる.

上の話で問いたかったことの数学的表現

X を集合とする.次のような性質を持つ集合族 F には X は含まれるか?
(集合族とは集合の集合のこと)

  1. ∅∈F
  2. A∈F かつ A≠X ならば, ある B∈F が存在して A⊂B (A は B の真部分集合)
  3. 任意の DF に対して,∪ DF

答えとしては,X ∈ F は成立するのである.実は,

X = ∪ F

となる.つまり,F の全部の集合の和集合をとると X になり,それは上の 3番目の要請から,F の元でなければならないのだ.この証明には 選択公理は必要ない.純粋に ZF (Zermelo-Fraenkel) の集合論の中で証明できて しまう.なんとなれば,もし,∪ F が X と 等しくなければ,2番目の要請から ∪ F を真部分集合として含む 集合 B が F に 入っていなければならないが,それは,∪ F の定義から無理である.

もとのゲームの話に戻るが,今,行った数学上の議論から,先のゲームで A さんが最初に 持っていた自然数の集合を実数の集合 R に変えても,A さんが勝つゲームに なってしまう.

実数の集合は自然数の集合より沢山の元が入っているので,本当に長い長いゲームで ある.A さんは新しい元を次々に獲得していって,それらをまとめて新しい集合を 作る.そして作られたそれらの集合を使ってまたゲームを続ける.そしてついには B さんが持っている実数すべての集合を手にしてしまうのだ.

それでは最後にもう一回だけルールを微修正してみよう.

前回のルールでは,A さんは F の中のどんな集合の和集合でも作って 良いことにしていただ,ここで少し制約を加えてみよう.

A さんは, C が ⊆ に関してチェインになっているときだけ, ∪ CF に加えてよい.

この新しいルールでも,Zorn の補題を使えば A さんは RF に 加えることができる.つまり,A さんが勝つためには,一般には選択公理を仮定しなければならなくなるのである(最初の集合 S が特殊な集合の場合は選択公理が必要ないこともある).

同じような絵ばかりで申し訳なかったが,Zorn の補題における集合論の役割を 考えるきっかけにはなったのではないかと思う.実は,この絵は,私が Zorn の 補題の証明をあれこれ考えているときに試してみたことを絵にしてみたものである.


証明(長いチェインを作る)

一応,ここでは,

もうこれ以上,上に拡張できない,(とても長いかもしれない)チェインを作る

方法での証明を1つ挙げておく.

まず,記号の確認をしておく.この証明の章を通して,f : P → P は選択公理から作った

    f(x) = x  if x が P で極大
         > x  otherwise
なる関数とする.これはこの証明を通して f で表す.また,チェイン C に対して, その上限を ∨C で表すことにする.

証明は命題と命題の間の数学的推論に殆どジャンプが無いようにしたのと, 非常に基本的な概念だけを 使ったので,かなり長い.それらを追って行く前に,どういう戦略で証明していくのかを 述べる.こちらは本当に短い.その後は,その戦略がきちんと実現できるということを 長い証明で確かめていくだけである.

【証明の戦略】

このような長いチェインを直接作るのは難しそうなので,以前の章 「何が難しいのか(長いチェインを作る証明について)」 で検討したように, 上の元が存在するならそれを選ぶ関数 f の適用と,そうしてできた元の集合の 上限をとる操作の2つで 作成した,和集合操作で統合可能なチェインの集合を作って,それらの和集合で その(とても長いかもしれない)チェインを表現することにする.

【そのチェインの集合 C に対する我々の願望】

そのチェインは,ゆくゆくは全体の和集合をとって,(とても長いかもしれない)チェインを 作り,その上限をとることで (P, ≤) の極大値を作るチェインの集合である. ちょっと,そのチェインに対する我々の願望をまとめておこう. 願望をきちんと書くと次のようになる.

C に対する願望
  1. C のチェインが上に伸ばせるなら,伸ばしたチェインも C に入っている.
    つまり,C ∈ C なら,C ∪ {∨C} ∈ C かつ C ∪ {∨C, f(∨C)} ∈ C

  2. C のチェインは全部1つのチェインに統合でき,それは C に入っている.
    つまり,∪ C は再びチェインになる

この2つが満たされたチェインの集合 C が定義できれば,∨(∪ C) が極大元である.なぜなら,∨(∪ C) の上の元 f(∨(∪ C)) は,一番目の願望から, Cのどれかのチェインに入っているはずだから,

f(∨(∪ C)) ≤ ∨(∪ C)

一方,f は自分以上の元を割り当てる関数だから,常に x ≤ f(x). したがって,

f(∨(∪ C)) ≤ ∨(∪ C) ≤ f(∨(∪ C))

となり,

∨(∪ C) = f(∨(∪ C))

つまり,∨(∪ C) は極大である.

【願望を満たす C の定義】

【(∪C)∈C の証明】

この証明が終われば,選択公理からZorn の補題が導かれるという全体の命題の証明も 終わることになる.ほぼルーチンワークであるものの,まだ,分量はけっこうある.

証明の方法としては 超限帰納法を使うという手 もあり,その場合はここの 証明より短くなる.しかし,ここでは,本当に基本的な推論の列で上のことを 確かめてみよう.そのほうが,起こり得る状態を具体的に認識できるので, 順序集合に対する 我々自身の感覚を磨くことができると思う

一応,迷子にならないように 証明の全体像 を載せておく.

ということで始めよう.

(∪C)∈C を証明するためには次のことを 証明しなければならない.

  1. C はチェインである.
    さらに,∪C は整列集合である.
  2. C ∈ ∪C , x ∈ C ならば
    1. x = x0 または
    2. x = f(x') ∃x'∈C または
    3. x = ∨ {x'∈C | x' < x}

まず,C∈C の構造に関する次の2つの命題を認識しておく. これらは後で証明する.

命題1 (C の中に,x1 と f(x1) の間には元は存在しない

C∈C, x1∈C に対して

f(x1) ∉ C ならば x ≤ x1 for ∀x ∈C

つまり,f(x1) が C を飛び出すなら,x1 が C の最上の元であるということである. 直観的には,上限をとる操作 ∨ は,x1, f(x1), f2(f1), ... の無限列が あって,その上にくるのであって,先ほどの無限列の途中にはこないということである.

命題2 (C の部分集合の上限が C を外れる場合は上に外れる)

C∈C, D ⊆ C に対して

∨D ∉ C ならば x < ∨D for ∀x ∈C

命題2は少し分かりにくいかもしれない.つまり右の図のような状況,
チェイン C ∈C において,途中のある上限 ∨D が C の中に なくて,その上が C の中にある状況
は無いということを言っている.もっと直観的にいうなら, ∨D の下の元が f で∨D を飛び越えて上に出るということは無いということである. D⊆C は,x3 を C のある元として,x3, f(x3), f2(x3), ... というような上昇列をイメージ すればよい.

これらを頭においてまず ∪C がチェインになることを示そう. それには (C, ⊆)が順序 ⊆ について チェインになっていることを示せばよい.すなわち,

∀C2, C3 ∈ C に対して C2⊆C3 または C3⊆C2

これが示されれば,x, y ∈ ∪C のとき,∃ C2, C3 ∈ C であるから,x, y はどちらも C2, C3 の大きな方に入っており,比較可能になり,∪C は任意の二元が比較可能でありチェインであることが示される.

(C, ⊆)がチェインになっているということは,C の勝手な チェイン C2, C3 を取ったとき,次のような状況になっていないということである.

つまり,C2 も C3 も相手のチェインに含まれない元を含んでいるということである. C2, C3 は整列集合であるから,このような元の中で最小元がある.C2 のものを a , C3 のものを b とする.a, b はどちらも x0 ではありえないから,

従って,a と b のでき方4通りについて,すべてあり得ないことを言えばよい.

  1. a=f(a') a'∈C2∩C3 かつ b=f(b') b'∈C2∩C3
    命題1をC2, b'∈C2, b=f(b')∉C2 に適用すれば,C2 の元は みな,b' 以下になるから,a'≤b'. C2 と C3 の役割を変えて命題 1 を適用すれば,a'≥b'.故に a'=b'. これは

    a = f(a') = f(b') = b

    を意味し,a, b が相手のチェインに 属さないということに反する.

  2. a=f(a') a'∈C2∩C3 かつ b={b'∈C2∩C3 | b'<b}
    命題 1 を C3, a'∈C3, a=f(a')∉C3 に適用すると C3 の元は みな a' 以下になるから,b≤a'.

    一方,命題 2 を C2, b, a'∈C2 に適用すると b > a' が得られ,これらはお互いに 矛盾する.したがって,このような場合はあり得ない.

  3. a={a'∈C2∩C3 | a'<b} かつ b=f(b') b'∈C2∩C3
    すぐ上と丁度反対になっただけであり,これもあり得ない.

  4. a={a'∈C2∩C3 | a'<b} かつ {b'∈C2∩C3 | b'<b}
    命題2を a と C3, b と C2 に適用すると,C3 の元はすべて a より小さく, C2 の元はすべて b より小さい.特に,a > b かつ a < b が得られ,矛盾する. 従って,こういう場合もあり得ない.

以上で,C に属する C2 と C3 は,必ず,C2 ⊆ C3 か C3 ⊆ C2 であるということになり, 結果として,∪C は 順序集合 P の順序でチェインになる.

次に,∪C が整列集合であることを示す.

いま,空集合でない任意の D⊆∪C をとり,これに最小元が あることを示す.D は空でないので,なにかある元 d∈D がある.C の 中で d を含むチェインの一つを C1 とすると,すぐ後で書くように ∪C の d 以下の部分は C1 の d 以下の部分と一致することが証明される.したがって,D の最小元は, もし存在すればそれは D ∩ C1 の 最小元と一致し,後者は整列集合 C1 の部分集合なので,最小元が存在する.

上で仮定した

C の d 以下の部分はC1 の d 以下の部分と一致すること

を示す.

まず,C∈C の中で,d を含まないものは,(C, ⊆) がチェインであることから,C⊆C1 であり,和集合の中では無視して構わない.

d∈C とする.このとき次のような二つのチェインを定義してみる.

これらはともに d を最大限とする C のチェインである. C のチェインはお互いに包含関係があるので,これらが 一致しない場合には,片方に,もう片方には無い元がある.これを右の図の ように b∈C[d] としてみよう.b は最小にとっておく. b が b=f(b') b'∈C1[d] の場合は,C1[d] の元は全部 b' 以下になり, d も C1[d] の元であるから,d ≤ b' < b=f(b') となるが,これは d が C[d] でも 最大であることに反する.また,b={b'∈C[d] | b' < b} のときは,C1[d] の 元はみな b より小さくなり,この場合も d が C[d] で最大であることに反する. したがって,

C1[d] = C[d]

が得られ

{x∈C | x≤d} = C1[d]

であることがわかる.したがって,D の最小元 は D∩C1 の最小元と等しく,後者は C1 が整列集合であることから存在する.故に,∪C の任意の 部分集合 D が最小元を持つことから ∪C も整列集合である.

最後に,

C ∈ ∪C , x ∈ C ならば
  1. x = x0 または
  2. x = f(x') ∃x'∈C または
  3. x = ∨ {x'∈C | x' < x}
を示す.

x∈∪C とする.このときあるC1∈C が存在して, x∈C1である.したがって,

  1. x = x0 または
  2. x = f(x') ∃x'∈C1 または
  3. x = ∨ {x'∈C1 | x' < x}
のどれかが成り立っている.最初の二つの場合は,C1 を ∪C に変えても 成り立つ.3つ目が成り立っているときは,C のチェインで C1 を含んでいる チェインについては,x より小さい部分はみな同じ集合なので,やはり,この場合も C1 を∪C に変えても成り立つ.

これですべてが証明された.

いや,あと,命題1と命題2が残っているので,やはりそれも証明しておく.

命題1 再掲 (C の中に,x1 と f(x1) の間には元は存在しない

C∈C, x1∈C に対して

f(x1) ∉ C ならば x ≤ x1 for ∀x ∈C

【命題1の証明】

まず,チェイン C の中で右の図のように x < y < f(x) となるような 3つ組は存在しないことを言っておく.

もしこのような x < y < f(x) が存在したなら,C が整列集合であることから, そのような x の最小元が存在するので,x をその元にしておき,y もこの関係を満たす 最小元とする.このとき, y∈C だから,y=x0 または,y=f(y') ∃y'∈C または y={y'∈C | y' < y} であるが,x < y < f(x) の関係から, y=f(y')のケースしかあり得ない.

しかし,この場合も,左の図のように,今度は,

y' < x < f(y')

が最初に述べた関係を満たすことになり,x の最小性に反する.したがって, チェイン C の中では

x < y < f(x)

となる2つ組はない.

以上を踏まえて,命題1のように,

f(x1) ∉ C for ∃x1∈C かつ x1 < y for ∃y∈C

が成立したとする.C は整列集合で あるから,このようなx1 の最小のものが存在する.また,y もこの関係を満たす 最小元ととっておく.このとき,上と同様の議論から,y'∈C が存在して,

y' < x1 < f(x1)

という関係にならねばならないが,これは上で証明したようにあり得ない. これで命題1が証明された.

【命題1の証明終わり】

命題2 再掲 (C の部分集合の上限が C を外れる場合は上に外れる)

C∈C, D ⊆ C に対して

∨D ∉ C ならば x < ∨D for ∀x ∈C

【命題2の証明】

命題2が成立しないとすると,x∈C で,∨D と比較不能のもの, あるいは,x > ∨D なるものが存在する.

x が∨D と比較不能としてみる.このとき,D の元は C に入っているので x と比較可能である.もし,D の元で一つでも x 以上のものがあれば, ∨D はそれ以上なので,x ≤ ∨D となり,比較不能ではない.また, D のすべての元が x より小さければ,x は D の上界であり,∨D は, D の最小上界であるから,このときも比較不能にはならない.

したがって,x>∨D の場合しかない.つまり,これは右の図のように,チェイン C が D の上限 ∨D を含まずに,その上の元を含むことができるかという問題である.

x∈C で,C は整列集合であるから, x>∨D の最小元がある.x をそのような最小元としてとっておく.x∈C であるから,

  1. x = x0 または
  2. x = f(x') for ∃x'∈C または
  3. x=∨{x'∈C | x'<x}
このうち,一番目は x が D の元より大きいことからあり得ず,また三番目も x が ∨D と一致しないためには ∨D と x の間に元があることになり,これは x が ∨ D より大きな元の最小のものという仮定に反する.

もし二番目が成立しているとしたら右の図のように ∨D∉C より,

x' < y < ∨D < x

となる4元 x', y, ∨D, x が存在することになり,このうちの x', y, x は C の元になるが,これは命題1の証明で述べた関係にあり,あり得ない.したがって,C の中に ∨D より大きな元は存在しない. これで命題2が証明された.

【命題2の証明終わり】


【参考1 : チェインの集合 C の取り方】

このページの終わりにあげてある J.B.Nation 教授の束論のテキストの付録では, 極大なチェインを作るためのチェインの集合 C は次のように定義してある.
C ∈C の条件として
  1. C はチェインである
  2. x0∈C
  3. x0≤y for ∀y∈C
  4. もし A が C の空でない order ideal で z∈C∩(Au - A) ならばγ(A)∈B∩z/0
    ここで
    Au = {x∈P | x ≥a for ∀a∈A}
    γ(A)=φ(Au - A)
    φ(A) は,空でない集合 A からその要素のどれかを返す選択関数
    z/0 = {x∈P | x≤z}
    A が順序集合 P の order ideal であるとは,A⊆P が,
    x∈A, y∈P かつ y≤x ならば y∈A
    を満たすことである.

【参考2: 超限帰納法を使う方法】

CC を示すために,本ページでは 非常に長い証明を行った.これは超限帰納法を使うことである程度短くできる.それは, いま,チェイン C に対して C(x) = {y∈C | y < x} と書くことにして, C2, C3 ∈ C ならば

のどれかのケースしかないことを超限帰納法で証明する方法である. このときの証明n全体の流れを下図に示す.

本ページでは, 順序集合に対する我々自身の感覚を磨くために敢えてイバラの道を選んだ.


同値な命題

テューキーの補題 (Tukey's lemma)

Zorn の補題と同値な命題として,まず,Tukey の補題をあげるのは,実は,私が この補題を気に入っているからである.

Tukey の補題は,「有限の性質」という,なんとも分かりにくい概念を使って 記述する.しかし,分かってしまえば,「これは万能か?」というような威力を 発揮する.それでは,まず,その「有限の性質」を持つ集合族という概念の定義から始める.

定義

A を集合,FP(A) = 2A を A の部分集合のある集合とする. 集合族 A が有限の性質を持つ(to have finite property) とは,

    X ∈ F   <=>   X の有限部分集合がすべて F の元である
が成立することである(<=> は論理的な同値を表す).

この定義は少し分かりにくいかもしれないが,次に Tukey の補題を述べた後に 有限の性質を持つ集合族の例をいくつか挙げる(その方が説明の効率が良いので).

この定義の下に Tukey の補題は次のように述べられる.

Tukey の補題

A を集合,FP(A) = 2A を有限の性質を持つ集合族とするとき, F には ⊆ に関して極大元がある.

それでは,有限の性質を持った集合族の例を挙げる.

ハウスドルフの極大定理(Hausdorff's maximal principle)

これは次のような命題である.
ハウスドルフの極大定理

(P, ≤) を任意の順序集合とし,C⊆P を P の任意のチェインとする. このとき,C を含む極大なチェインがある.

ここで極大なチェインとは,もうこれ以上の元を加えると チェインでなくなってしまうようなチェインである.

最初のチェイン C の指定をなくして,

極大原理'

順序集合には極大なチェインがある


としても,選択公理や Zorn の補題と同等の命題である.

我々は,Zorn の補題の証明で,上に極大なチェインを作るのに四苦八苦した. この命題があれば,上に極大といわず,とにかく極大なチェインがあるので, その上限が P の極大元になり,あっという間に Zorn の補題の証明が終わってしまう. 結構,強力な原理であることがわかると思う.登場する順序集合に特に条件がついていないのも 私は好きだ.


選択公理と類似の命題

私自身は計算機科学の分野で長いこと仕事をしてきたので, やはり選択公理を使うか使わないかは大いに気になる.使わないで済むなら 使わないし,また,日ごろ使っている定理が,選択公理にどの程度「汚染」されて いるかは気にかかる.

ここには選択公理に類する公理,命題の情報を集めておく.私自身のメモの ような意味で設けた記述なので,あまり読む人への配慮はしていない.


考察


考察その2(二つの上昇原理 v.s. 一つの選択関数)

この節は比較的重要であり,ページの後ろに置くのはあまり格好の良いものではないが, 目次から飛べるようにしているのでご容赦願いたい.

本ページの大部分では,上に極大なチェインを求めるのに,1つの元から次の2つの 上昇原理を使ってチェインを上に伸ばしていっている.

  1. 直上の元を求める
    x∈P が極大な元で無い限り,上の元 f(x) を求めてチェインに加える

  2. 上限を求める
    無限の上昇列 x, f(x), ..., fn(x), ... の上に上限を加える

証明では,この二つの場合を区別して述べているため,量がかさんで読みにくくなっていると 思う.

一方,選択関数を,次のように P の中のチェインから P の元を割り当てるように とってみる.C を P のすべてのチェインの集合とする.

g : CC

g(C) は,P に C の中のどの元より大きい元があればそのうちのどれか, なければ C の上限(これはZorn の補題の仮定から存在は保証されている). 具体的には,上の f を使って,

g(C) := f(∨C)

として置けばよいだろう.

実は,このような関数 g : CC を考えた段階で P の各元 x に対して,そこから極大元まで登っていく整列集合が定まってしまうのである. つまり,最初は,x だけからなる集合 {x} で,次は {x} ∪ g({x}) でという具合に, 次々に出来た集合に g を提供した元を加えていく.このようにして作られた無限上昇列に 対しても g は定義されているので,上限 ∨ を個別にとらないでも上昇列は 一意に定まる.また,これは整列順序になっている.このように,選択公理を使った f や g から1本の長いチェインが定まるというのは,f や g の関数性に寄っている. つまり,任意の元 x や任意のチェイン C に対して,f(x) や g(C) が一意に定まるので 1本の整列集合が定まるのである.

これは任意の集合に対する整列可能定理でも同様である.整列可能定理は 任意の集合に整列順序を導入できるという定理であるが,A を最初の集合とし, A の任意の真部分集合 B に対して,A - B の元を与える選択関数 h を決めた 段階で∅からはじめて A のすべての元を取りつくす列がきまり,取り出した 結果をその取り出された順序で順序つければ整列順序が出来上がる(容易に わかると思うが,元を取る列そのものが結果の整列集合と同型の整列集合になる). この場合の選択関数 h と整列順序は同一のものと言っても良い.

この整列可能定理については

集合論の学習での重要なポイント:整列可能定理
に書いたのでよければ参照してほしい.

話を戻して,このページでは上に極大なチェインを求める方法を二つの上昇原理として理解し, 延々と述べて行った. 一般的にこのようなアプローチが本当に必要かどうかは自信がないが,自分自身に ついて言えば.一時,このような個別の場合分けまでどっぷりつかり, 順序集合や整列集合の細かい部分を使う練習をしたことは良かったと思っている.


歴史

このページの参考文献 にもあげた Stanford Encyclopedia of Phylosophy の Axiom of Choice の 第一章 と第3章にある年表をまとめて,
  1. 集合論
  2. パラドクス
  3. 独立性・無矛盾性
  4. 選択公理の別形態
の観点から,出来事を再整理してみました.これによると Zorn の補題は 1935 年と, Zermelo が 1904 年に選択公理を認識し,Hausdorff が1909 年に極大原理(Maximal Principle)を認識して,結構時間がたっていますね.

尚,年表の色はほぼ10年後とに変えてます.また,選択公理は AC (Axiom of Choice) と略しているところもあります.


参考文献


より良い理解のために知っておいたほうが良いこと


集合,位相,論理など へ

圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)