Some Important Topics in Basic Set Theory
私自身は計算機科学の分野の人間であるが，
これは集合論のお題目上の抽象的な位置付けだけではなく，計算機科学の日常的な活動の中でも 集合論は
など，重要な役割を果たしている．
一方，数学を専攻する学生や研究者ではなく
各自でハードルは違うかもしれないが，冪集合の濃度，Bernstein の定理や整列集合の概念と諸定理， Zorn の補題などが難しいかと思う．
また，これらは同時に面白いところでもある．
ここではそういった集合論のトピックスをとりあげ，それらの習得を支援するための 教材を作っていこうと思う（あとがき でも書くが，私自身は教材のネタの作成と蓄積に 興味がある）．
内容
これは対角線論法の分かりにくさと裏腹に証明自体は驚くほど簡単である．
右の図のように集合 X からその部分集合すべての集合 P(X) = 2X へ なんらかの対応を決める関数 f があったとする． ここでは，P(X) の元がすべて X の元に結びつくかに関心があるので， 一応，f は 全単射(bijection) つまり，全射 (surjection) かつ 単射 (１対１対応 (injection))としておく． このとき X の部分集合 Ef を
Ef := {u∈X | u∉f(u)}
と定義する．この Ef に f で対応する v∈X はあるだろうか？
対応する v が存在したとする．v∈f(v) かどうかを考えると f(v)=Ef と Ef の定義から，
v∈f(v)=Ef => v∉f(v)となり，矛盾が導かれる．したがって，f(v) = Ef∈P(X) となる v は無く，これは P(X) の元をすべて X の元に結びつけることはできないことを意味し， |X| < |P(X)| であることがわかる．
v∉f(v) => v∈Ef=f(v)
この証明で，f は 全単射 としたが，特にこの仮定はいらない．とにかく f がどんな関数でも，Ef = f(v) となる v は存在しないのだ．
証明の戦略を振り返ってみると，こうである．f で X のどんな元とも対応しない P(X) の元を 作るには既存の任意の f(u) とどこかで違う集合を作ればよい．集合の同等性は，どんな元が所属しているかで 完全に決るから（外延性公理）．その差異を丁度 u の所属で実現するのである．つまり
f(u) に u が入っていれば，u を入れないで，u が入っていなければ u を入れる
つまり 少なくとも u の部分が f(u) と異なるようにする
これでどの f(u) とも異なる集合ができるはずということである．
よく中学高校生向けの数学啓蒙書などに書いてある「自然数が実数と対応が付かない」 説明はこれより少し込み入っている感じを与える．試しに，ここにもそれらしいものを 書いてみる
自然数の集合 N と 0 以上 1 以下の実数の集合 [0, 1] は 1:1に過不足なく対応付けることはできない
[0, 1] の数は 0.x0 x1 x2 ... というように２進数で 表現できるはずである．ここで，x0 x1, ... は 0 か 1 である．
今，次の図のように自然数と [0, 1] の数が１対１に過不足なる対応付いたとする． このとき，新たに数 y=0.y0 y1 y2 ... を，x nn≠yn となるように作る．これには xnn=1 なら yn=0，xnn=0 なら yn=1 とすればよい．こうしてできた y はすでに自然数と対応が付いた [0, 1] の実数とは n ケタ目で必ず異なるので， まだ対応がついていない数である．したがって，自然数と [0, 1] の実数は対応が付かない．
（注意）ここでは簡単にするために 0.01111...= 0.1000... など，同じ数に二つの表現が ある場合があることを無視した．
以上が，数学の啓蒙書などによく書いてある説明である．少し，込み入った感じがするのと， 対角線論法と呼ばれるのがより分かる雰囲気の説明になっている．ところで，なんで こちらでは同じ数の２つの表現なんかが問題になって，最初の部分集合の証明の方では 問題にならないんでしょうね？ あっ！ 分かった．[0, 1] と P(N) が 完全に同型じゃないんだ．[0, 1] は P(N) をある種の同値律で割った商空間なんですね．:-)
で，我々の最初の証明，|X| ≠ |P(X)| は対角線らしさがあまり出てなかった． 対角線の要素が，定義
Ef := {u∈X | u∉f(u)}
に押し込められてしまっているからである．図としても対角線らしさを出してみよう． 上の啓蒙書に載っていそうな図とほとんど同じであるが，次のようなものでどうだろう．
右の表の各行が X の部分集合を表す．x ∈X がその部分集合に入っていれば，表の セルには 1 が入っていて，そうでなければ 0 が入っている．では，対角線の 0/1 を 引っくり返した部分集合は，この表に載っているだろうか？ まあ，表の中の bx,x全部の 0/1 を引っくり返したので，この表には載ってないのである．
計算機科学でも，対角線論法を使って，考えている対象の範囲に求める性質を 持つものがないことを示すことがよくある．例えば，プログラム（アルゴリズム）の 停止性問題や Gödel の不完全性定理などである．ここでは停止性問題を述べる．
停止性問題は，与えられたプログラムが，与えられたデータに対して停止して答えを 出すかどうかを判定する問題であり，それを判定する一般的なアルゴリズムは 存在しないというのが，計算機科学での初期の成果である．
この問題については，「停止性問題」，「対角線論法」などで検索すれば，Wikipedia など の簡単な解説が見つかると思う．ここでは Wikipedia にある解説をもとに多少補充しながら 説明しようと思う（日本語版 2018 年 8 月 23日時点の「停止性問題」および「カントールの対角線論法」を参照した）．
そこに書いてある証明はかなり単純である．「へぇー，こんなに簡単に証明できるの！」と 思うと同時に，多少，「これ，プログラムの停止性に固有の話？」と言った 違和感を覚える（すくなくとも私自身はそんな感覚を持った）．まずは，すべての場合に停止性判定ができるプログラムはないことを示した後に，その「違和感」について議論することにする．
まず，「停止性問題」を Wikipedia などよりほんの少し正確に述べた方が良いと思う． あちらは直観的に分かりやすい説明になっているが，プログラムをデータとして 扱うことなどが，計算機科学以外の人には少し分かりにくいと思う．
問題の枠組みは下の図のようになっている．
まず，プログラムとして自然数の集合 N のいくつかの組から自然数の集合 N へ計算結果を返すものの集合を考える．つまり，
Nn → N, n=0, 1, 2, ...
の関数を定義するプログラムの集合である．このプログラムはある文法に従った文字の 列で書かれるものとする．文法としては例えば，関数型言語の Haskell とか，ほか， 自分たちで勝手に作ったものでもなんでもよいが，何か定まっているとする．正確に言うと 関数 Nn → N とプログラムは別のもので，プログラムは あくまで文字の列，関数は数学の空間の中での抽象的なものであり，これらを結びつけるのは プログラム意味論など難しい分野があるが，ここでは簡単のためにそれらを混同しておく．
プログラムは自然数の集合の中に埋め込むことができる．上の図で encode と書いたところだ． これにはいろいろな方法があるが，もっとも簡単なものは，プログラムの文字列を直接数値と 見なすことだ．文字にはコード（ASCII コードなど）と呼ばれる数値が割り当ててあるので， プログラムの文字列の順番でそれらのコードを並べて，それを１つの巨大な数と思うことである． その逆に数値は，コードの並びと考えて，文字列に直し，コンパイラやインタープリタがやっているような方法で実際に動くプログラムにすることができる．これが decode 側である．
「停止性問題」は，次のようなプログラム halt : N2 → N で，それ自身常に停止して答えを出すものが存在するかどうかという問題である．
halt 自身が，N2 → N のプログラムであることに注意して欲しい． また， Wikipedia では halt の結果は {0, 1} になっていると思うが，Yes か No かの２値を 区別できれば良いので，すこしオーバースペックだが結果としても自然数の集合 N を とっておく．こうすれば考えるプログラムはすべて Nn → N の 形なので，上の図のようにプログラムの集合が統一的に扱える．halt(A, d) = データ A が一引数のプログラムに対応する場合，そのプログラム decode(A) をデータ d に適用して停止すれば 1，そうでなければ 0 を返すプログラム （A が一引数のプログラムに対応しない場合もこちらに含めておくことにする)
このお膳立てができていれば，後は簡単である．
[Proof
(プログラムの停止性を常に判定するプログラムが存在しないこと）]halt(A, d) が常に停止して，プログラムの実行 decode(A)(d) の停止性を判定できると 仮定すると，
は，N1 → N のプログラムである．ここで loop_forever は 無限ループを起こすプログラムのコードであるとする． このとき，g を自分自身に適用した g(encode(g)) はどんな結果を返すだろうか？ g が無限ループに陥るときの条件はg(A) = loop_forever if halt(A, A) = 1 0 otherwise が 1 を返すこと，つまりhalt(encode(g), encode(g)) g(encode(g)) が停止すること だから，これは矛盾なので，常に停止して decode(A)(d) の停止性を正しく判定するプログラム halt(A, d) は存在しない．g(encode(g)) はそれが停止するときに無限ループで停止せず，停止しないときは 0 を返して停止する ．
[Q.E.D.]
以上が，常に停止する halt が存在しない証明である．お膳立て以降はずいぶんとあっさりと終わった感じが
するのではないだろうか？ また，最後は何か言いくるめられた感じがするのではないだろうか．
対角線論法はいつも若干そんな感じはあるが，この停止性問題の対角線論法は
次は，停止性問題に対する対角線論法の適用の考察である，
上の証明のどこが「言いくるめられ感」が強いか考えてみる．
上に書いた疑問は，別に「停止性の判定を行うアルゴリズムはない」という証明自体を 疑うものではなく，簡易に書かれた記述では上のような疑問がでてくるので，もう少し 本質を突き詰めてみようというだけである．
証明の構造を少し，典型的な対角線論法に寄せてみる．上では，プログラム A が データ d に対して停止するかどうかを判定する関数 halt(A, d) を使ったが， 2X と X の間に全単射がないという証明と形を合わせるために， h : N → P(N) の形で議論する．つまり，
h(A) = {x∈N | halt(A, x) = 1}
のように，プログラム A が停止する値の集合を返す関数を考える．
この設定では，以前に冪集合がもとの集合と全単射の対応が付かないことを 証明したときのことを思い出せば，P(N) の中の集合，
Eh={x∈N | x∉h(x)}
に対応が付く元は N に存在しないはずである．しかし，halt(A, d) が 全域の関数だとすると，
を encode したもの b=encode(g) が h(b)=Eh を満たしてしまい，矛盾を 引き起こすということである．つまり，冪集合の証明では， Eh∈P(N) に対応する N の元が無いということの 証明に使われていた枠組みだが，今回は，halt(A, d) が全域の関数なら，その性質から Ehに対応する N の元が存在してしまうという形で使われている．g(A) = loop_forever if h(A, A) 0 otherwise
最後に，「停止性」ということを完全に頭から追い出して，なにかしら
h : N→P(N)
があるという状況で，h にどんな条件を課せば，Eh の元像が N に 存在してしまうか（つまり矛盾してしまうか）を考えてみる．そのような条件は 「停止性の判定」と同様に矛盾を起こすので，起こり得ない条件なのである．
まず，簡単なところで，Dh={x∈N | x∈h(x)} を h の
h の対角線成分をとる d0 があり，h(d0)を反転させることができる
なら，Eh に対応する h の元像の存在が言えてしまう．つまり，
h(d0) = Dh となる d0 があり，
さらに
not : N→N で，h(not(x)) = N - h(x) となる N 上の関数がある
場合である．直前の例とほとんど変わらないが，not の部分を N→Nの関数に変えた点が異なる．
次に，もう少し，停止性の例に近づけつつ，N→P(N) の 形に保った例を出す．
下の図では，図の下部に関数の空間 N→P(N) が書いてあって， これが自然数の集合 N に埋め込まれている状況を書いている．基数の制限から N→P(N) 全部を N に埋め込むことはできないから，ごく 一部のF ⊆ (N→P(N)) が埋め込まれている． また，埋め込みの関数 enc2 は enc2(f, x) と 自然数の引数 x を取るようにしてある． これは，全体の枠組みを対角線論法のもともとの枠組み N→P(N) に したため，この左側にプログラムを埋め込んだ部分の N とそのデータの N の 二つを書けなかったためである．
この図で下の F はプログラムの集合を意図したものである． この設定で，Eh={x∈N | x∉h(x)} の h の元像が N の中に存在することが要求されてしまう十分条件（つまり，矛盾を引き起こす十分条件）としては
つまり，（１）N→P(N) の関数の一部分を模倣する関数の集合 Fがあり，（２）その集合 F が h を模倣でき，（３）関数の 対角線成分をとる能力と，（４）結果の集合を反転させる能力があれば，矛盾を起こせるという ことである．
以上，私自身で考えながら例を作ってみただけなので，あまりエレガントでもないし， 分かりにくいところもあると思う．もし，今後さらに考えてみたり，調べたりして より分かりやすい表現があったらここの例や説明を改善するかもしれないが，とりあえず 説明を終わる．
ここらあたりで，対角線論法について多少整理しておいた方が良いかもしれない．
なぜわざわざ，これをここに書いているかというと，この無限和は後ででてくる カントール・ベルンシュタインの定理で使うからである．そのときの違和感を 少しここで和らげておこうという意図である．
集合の概念や操作を理解するのは，やはり最終的には公理に寄ることになり， そこでは人間の感覚から抜け出ないといけない．しかし，完全に人間の感覚から 抜け出るとまったく進むべき方向が分からなくなるから，必要な時戻って 身体的感覚を，自分をガイドする手段として使い，また，必要な時は 感覚から抜け出て公理や数学的推論に忠実に従うことが必要だと思う．
ということで，
次のような集合 Y のことである．
全部論理式で書けば，
x∈Y を主にして表現すると，
つまり，x が Y に属するというのは，F の中に一つでも x を含む集合 X があることである．
まあ，これは ∪ の定義そのものだが．実際，ZFC の公理的集合論の中でも，和集合に 関する公理は上のような Y が存在するという内容である．また，存在すれば 外延性の公理（ちょうど同じ要素を持つ集合同士は等しいという公理）から一意となる．
記法
と同等と思えば良い．
で，具体例に触れてみると，
A := ∪ n=1 to ∞ {x∈R | 1/(n + 1) < x ≤ 1/n }
B := ∪ n=0 to ∞ {x∈R | n ≤ x < n + 1}
とする．記述を簡単にするために，今後，実数の区間の記号
[a, b] := {x∈R | a ≤ x ≤ b}を使うことにする．この記号を使うと，A は区間 (0, 1] で， B は実数の中の 0 以上の部分すべて [0, ∞) である．どんな n をとっても，これらの集合の部分しかカバーしていないのに，全体では [0, ∞) をカバーして いるというのはなんとなく納得いかない気がするかもしれない．それは，[a, b) := {x∈R | a ≤ x < b}
(a, b] := {x∈R | a < x ≤ b}
(a, b) := {x∈R | a < x < b}
0.99999…
とどこまでも続く数が 1 と等しいと言われると
「え？ そうなの？」
と思うのと 似ている．
「いや，いつまでいっても数は 9 であって，0 にはなってないんだから どこかで違うはず」という気持ちが付きまとう．例えば，上の B = ∪ n=0 to ∞ {x∈R | n ≤ x < n + 1} の場合もそうだろう．
「どこまでいっても n 以下の数の集合なんだから，0 以上の実数全体とはちがうんじゃない？」でも，定義上は 0 以上の実数全体 [0, ∞) なのだ．
分かりやすくする解説か，混乱させるための解説か分からない解説になった．
和集合操作 ∪ にはこういう極限として集合を定義する機能がある訳だが．これは，∪ の双対の ∩ にもある．
C := ∩n=1 to ∞ (0-1/n, 1+1/n)
とすると，C は閉区間 [0, 1] である．それぞれは開区間 (0-1/n, 1+1/n) だったのに， いつの間にか閉区間に化けているのはずるいと感じるかもしれない．
上の絵で，開区間になったのは，やはり，一番最後の瞬間なんだろうか． なんかこう言うのを考えてると，宇宙の果てはどうなっているのかみたいな ことを考えてるような気になってくる．この絵の左側の列は，後で出てくる 整列集合 {1, 2, 3, ..., ∞}
1 < 2 < 3 < ... < ∞
の上と下をひっくり返したような形になっている（∞が集合に元として入っていることに注意）．∞は，直下の元を持たない 極限の元である．対応する開区間 (0, 1) も直下の元を持たない極限の区間である．
内容
これは集合間のカーディナリティの比較が，実際に順序になっていることの根拠になる 重要な定理である．
このまま証明してもよいのだが，絵がごちゃごちゃするので，とりあえず，次の命題を 経由して証明する．
f : A → C
があれば， 全単射
g : A → B
も存在する．
この命題が証明されたなら，Cantor-Bernstein の定理の状況は，次のようになるので A から g・f(A) へは 全単射 が存在するから，A から g(B) へも何か 全単射 h が 存在する．g(B) から B へは 全単射 g-1が存在するから，これらを まとめると A から B への 全単射 g-1・h が存在する．
では，命題１の証明に取り掛かる．
まず，命題の状況と目的を確認しておく．次の図のように
状況では
A → B にも 全単射 がある
少し，図を簡単にして，おさらいしながら状況を整理してみよう．
A から B への 全単射 を作るのに，A - B の部分が邪魔である．B の部分だけなら 恒等写像 id : B → B で済む．
仕方がないので，A - B の部分は，全単射 f で集合 C の中に飛ばす． そうすると，A - B の部分は解消できたが，飛ばされた先の f(A - B) の部分は もともと，図左の f(A - B) ⊆ C から id で飛ばされていた訳で，この 行き先を決めなければならない．
これも f で飛ばしてみると，次の図のようになる．つまり，
しかし，これをずっと続けていくと，次の図のように
先ほど，すでに集合の直和 Σ の記号を使ったが，これができるためには
{fn(A - B) | n = 0, 1, 2, ...}
がお互いに交わらないことを 言わなければならないが，これは帰納法で証明できる．まず，A - B は C の 外であるから，C 内部の f(A - B) とは交わらない．また，n > m に対して， fn(A - B) と fm(A - B) が交われば，f が単射であること から，C の外にある A - B と C の中にある fn-m(A - B) が交わる ことになってしまい，矛盾が起こる．
A から B への 全単射 g は次のように定義できる．
g が１対１写像であることは f と id が１対１であることと，上の定義で f を使う時の領域と id を使う時の領域に重なりがないことから分かる． 全射であること，すなわち，g(A) = B であることは，g(a) = f(a) if a∈ (A - B) + Σ n=1 to ∞fn(A - B) = a otherwise
f((A - B) + Σ n=1 to ∞fn(A - B)) = Σ n=1 to ∞fn(A - B))
であることから，g の適用において，f を適用する部分の適用結果は (A - B) だけ元の領域より少なくなり，
g(A) = A - (A - B) = B
となることからわかる．
Cantor-Bernstein の定理は，基数の比較が順序になっているという理論的な価値だけでなく， 何度も証明を追ったり，実際に具体例で対応を作ってみたりすることにより， 無限集合に対する我々の感覚を磨くことができると思う．
その意味で，集合 A と B の間に相互の１対１対応があるときの 全単射 の構成も やってみる価値はある．
いま，f:A→B，g:B→A の単射があるとする．f が全単射ならそれで A と B の元を 全部一対一に結びつけられて万々歳なのだが，あいにくそうではなく，f は B の真に 中への単射とする．B-f(A)≠∅ である．A と B の元を f で対応付けようとすると， この B-f(A)⊆B が対応付けられずに残ってしまうことになる．これは f で対応付けられないので，g:B→A で対応つけてみる．そうすると，f:A→B で対応付けていた，元の g(B-f(A))の 部分が減って，再度 f・g(B-f(A))⊆Bが対応付かないことになってしまう．
これは実は最初の状況と一緒だ．これを繰り返していくと，B の中の
B - f(A), ｆ・g(B-f(A)), (f・g)2(B-f(A)), ...(f・g)n(B-f(A)), ...
が f で対応付かないので g:B→A で対応付けないといけない．これらを合わせた和集合，
B' := ∪n=0 to ∞(f・g)n(B - f(A))
を考えると，B の中の B-B' は A と f で対応させ，B' の部分は g で対応させると うまく全単射で対応が付くのではないかという予想が立つと思う．実はこれがうまく 行くのである．証明は読者が各自でやって欲しい．和集合の要素
(f・g)n(B-f(A))
は，異なる n=n1 と n=n2 では交わりが無いことに注意してほしい（これは数学的 帰納法で証明できる）．
結果としては，上の図のような全単射の対応が構成できる．
この Bernstein の定理は不動点定理でも証明できる．
集合 A, B のそれぞれを，f で対応付ける部分と g で対応付ける部分（集合 A からだと，g-1 での対応）に分ける．上のお医者さんの絵と合わせるために 集合 B の中で，g で A の元と対応付ける部分を B'⊆B としておこう． 集合 A と B を分割している部分の絵だけ再掲しておく．
つまり，集合 B の中から B' という部分集合を切り出して
ようにするわけである．f も g も単射であるから，上のように限定した場合， 全射になるような B'が存在する ことが示せれば，全体としても A から B への全単射が存在する訳である． この図の中で問題になるのは A の上の部分 A - g(B') の f による像が B - B' に なるかだけである．つまり，
f(A - g(B')) = B - B'
左辺は f(A) - f・g(B') であるから，この式は
B' = (B - f(A)) + f・g(B')
と同値である（「+」は直和を表す）．
このような B' の存在を束論の不動点定理を使って証明するのである．もう少し 詳しく言うと，P(B) を B のすべての部分集合の集合とするとき，上の B' が解になるような関数 F
F : P(B)→P(B)
F(X) := (B - f(A)) + f・g(X)
f・g(X)⊆f・g(B)⊆f(A) なので，直和「+」は常に可能
を定義して，この F が不動点を持つことを
上記の結果から 逆に導出するのは少々ずるいが，
B' := ∪n=0 to ∞(f・g)n(B - f(A))
は，
B' = (B - f(A)) + f・g(B')
の解になることが容易に確かめられる(「+」は直和，つまり，交わりの無い和集合とする）． 逆に，もしこの集合の方程式に解があれば，上のお医者さんの絵を満たす分割を作ることが 出来て，f と g (A→B に方向を合わせるなら g-1）をつなぎ合わせることにより， A→B の全単射を作ることができる．
この方程式に解があることを上では，具体的な解を構成することで示したが， 先ほど述べたように，束論などの中で論じられる不動点定理でもその解を保証することができる． それには束論の知識がいるが，Knaster-Tarski の定理を使う．ここでは， その定理の内容だけを書いておく．
L を完備束*とし，F:L→L を単調写像（順序を保存する写像，すなわち， x≤y => F(x)≤F(y) が成立する写像）とする．このとき，
∧{x∈L | F(x)≤x}
は，F の最小の不動点である．また，
∨{x∈L | F(x)≥x}
は，F の最大の不動点である．
* 順序集合 (L, ≤) が完備束であるとは，その任意の部分集合 S⊆L に上限 ∨Sと 下限 ∧S が存在することである．ただし，∨∅ は最小元，∧∅ は最大限とする．したがって， 完備束の場合は必ず１つ以上の元が存在するものとする．
いま，F : P(B)→P を F(X):=(B - f(A)) + f・g(X) で定義すると， (P(B), ⊆) は完備束であり，F は， X⊆Y => F(X)⊆Y を満たすから単調写像であり，上の定理から，F は最小不動点 B' を 持つ．したがって，上のお医者さんの絵のようなA, B の分割ができて，それぞれ，f と g で対応をとれば，A と B は全単射で結ばれる．
尚，Knaster-Tarski の不動点定理は選択公理を使わないで証明できるので， この Bernstein の定理の証明も選択公理とは独立に証明されたことになる．
もう一つ，Bernstein の定理に関しては，選択公理絡みのコメントを書いておく必要があると思う．
ここでは，集合 A と B の間に双方から１対１対応がある場合は 全単射 が構成できる ということを証明したのだが，証明には選択公理は使っていないことに注意する必要が ある．選択公理を使う場合は，この定理の１対１対応を全射に変えても，全単射 が存在する． つまり，
選択公理を仮定している場合は，集合 A と集合 B の間に，相互に全射がある 場合は，A と B の間に 全単射 がある．
証明は簡単である．全射 f : A → B がある場合は，
∀b∈B ∃a∈A f(a)=b
だから，選択公理から
f' : B → A で f'(b1)≠f'(b2) for b1≠b2
なぜなら f'(b1) = f'(b2) なら b1 = f(f'(b1)) = f(f'(b2)) = b2
即ち，単射が存在する． 同様に，g' : A → B の単射も存在するので，カントール・ベルンシュタインの定理から A と B の間には全単射が存在する．
目次
W(x) := {y∈W | y < x}
のこと．W<x> で表すテキストが多いと思うが，HTML では < > は面倒なので，( ) で代用させていただく．
この逆に
が成立するが，この証明には選択公理の弱い版である「従属選択公理」を要する．つまり， チェインが整列集合でない場合は，任意の元より小さい元が存在するが， それを可算無限回選ぶのに選択公理の弱い版が必要になる．チェインに無限下降列がなければ整列集合である
では，この記法で切片のイメージをもう一度．
集合の中の個々の元をあまり強調しなくてよければ，次のような二つの 表示の仕方もあるだろう．
雑感：整列集合では，一つの元からその最初の上限まで（⑤の部分）は 高々可算無限個であり，全体は，この繰り返しである．しかし， 選択公理を仮定すると，任意の集合を整列集合にしてしまえる訳だから，その 可算無限個のチェインの繰り返しでどんな基数の集合でも元を尽くしてしまえる というのは不思議である．
超限帰納法 (transfinite induction) は整列集合で使える帰納法である （実は，整列集合より弱い整礎集合 (well-founded set) で使えるらしい）．数学的帰納法 (mathematical induction) のように自然数だけに使える手段と違って， たとえ，実数サイズでも，またどんなサイズの集合でも，整列されて いさえすれば使えるすごい証明手段なので，私は，使用に若干心理的抑制がかかる．
しかし，考えてみると，数学的帰納法は，それが使えることは公理系（例えば ペアノの公理系）で保証しなければならないのに対して，超限帰納法は 普通の集合論を仮定するだけで使うことができる．これから考えるに， どちらかというと数学的帰納法の方が危ういのである．
これは自然数の集合が整列集合であるということが，公理なしに成り立たないと いうことであろう．超限帰納法はとにかく整列集合だと適用できるのだから．
超限帰納法という言葉に対する（私自身）の警戒感と公理的体系の取り扱いの 差がちょっと気になったのでこれを書いてみた．
整列集合はかなり簡単な形をしている．最小値から直上・直上へと上がっていって いく．それが無限に続く場合は，その上に元を置いてよく，そうすると，さらに その直上・直上へと昇っていくことができる．このように作られた整列集合同士の 関係は次の定理で示されるような３つの場合に集約できる．
W1, W2 を整列集合とすると，次の３つのうちのどれかが成立する．
ただし，W(x) は上で定義したように，切片 W(x) := {y∈W | y<x}
この定理の証明を見ると，Zorn の補題の証明とかなり似ている．実際，Zorn の補題の 証明は，この定理を使うとずいぶんと短く，すっきりした形になる．ただし，この定理は Zorn の補題と異なり，選択公理を使わなくて証明できる．
証明に使ういくつかの概念を定義しておこう．
順序集合 W の部分集合 I ⊆ W が，W の
y∈I かつ z≤y ならば z∈I
を満たすことである．x = min(W - I) と置くと，
I = W(x)
となることに注意しておこう．
また，I が W と一致するか，W の initial segment になるとき，
次に二つの整列集合 W1 と W2 の間の拡張セグメント間で同型の対応がとれるものの 集合を次の図のように
とする．I1, I2 は拡張 initial segment なので，W1, W2 の場合もあることに注意してほしい． 想像できると思うが，証明では，Equiv に，(W1, I2, f) あるいは (I1, W2, f') の形の 要素が含まれていることを言うのである．Equiv := {(I1, I2, f) | I1 は W1 の拡張 initial segment， I2 は W2 の拡張 initial segment，
f : I1 → I2 は同型写像}
準備の最後に，Equiv の中の順序を次のように定義する．
(I1, I2, f) ≤ (I1', I2', f') ⇔ I1⊆I2 かつ f(x)=f'(x) x∈I1
つまり，I1 が I1' に含まれ，I1'→I2' の同型写像は I1→I2 の同型写像を拡張したものに なっているということである．
上で定義したように，Equiv を整列集合 W1 の 拡張 initial segment I1 から，W2 の 拡張 initial segment I2 と，それらの間の同型写像 f: I1 → I2 の集合とする．
Equiv の任意のチェイン D⊆Equiv に対して
m(D) := (V1, V2, g) = (∪(I1, I2, f)∈DI1, ∪(I1, I2, f)∈DI2, ∪(I1, I2, f)∈Df)
と置けば，m(D) は D の中の同型関係の上限になる（証明は後に書いた）．
したがって，Zorn の補題から，Equiv には極大元 (V1, V2, g) が存在する． この V1, V2 について， V1≠W1 かつ V2≠W2 ならば，V1∪{min(W1-V1)} と V2∪{min(W2-V2)} も 同型であるから，(V1, V2, g) が極大であることに反する．したがって， V1=W1 または V2=W2 である．
V1=W1, V2=W2 の組み合わせで場合分けをすると，
となり，定理は証明された．
上の証明の中で使ったEquiv の任意のチェイン D⊆Equiv に対して
(V1, V2, g) = (∪(I1, I2, f)∈DI1, ∪(I1, I2, f)∈DI2, ∪(I1, I2, f)∈Df)
が，D の中の同型関係の上限になることの証明
[Proof] V1, V2 が D の中の (I1, I2, f) のそれぞれ I1, I2 の上限になっていることは すぐわかる．g が V1 → V2 の同型写像となっていることを示す．
まず，g が well-defined であることを示す．(I1, I2, f), (I1', I2', f') ∈D とする．D はチェインだから，この２つには順序関係がある．
(I1, I2, f)≤(I1', I2', f')
としておく．Equiv の定義から，x∈I1 については f'(x)=f(x)であるから g も f(x) となり，値が決まる．
さらにこれが順序を保つことは，x, y∈V1 なら， (I1, I2, f), Equiv の定義から I1⊆I1' のとき，x, y∈I' である．x, y は 同じ f' は順序同型であるから，g も x と y の順序を保ち，順序同型である．
[Q.E.D.]
(V1, V2, f)∈Equiv で V1=W1 になるもの，あるいは V2=W2になるものが存在することを 証明する．
V1=W1 とならないと仮定する．
次の図のように，任意の整列集合 W1, W2 に対して，W1(a) ≅ W2(b) となる a, b は存在する．例えば， a を W1 の最小元，b を W2 の最小元とすればこの 二つの切片は同型である．
しかし，仮定から，W1 全体は，W2 の中に同型の拡張 initial segment を持たない から，図のように
の二つの場合に分かれる．
上の (1) の場合は W1(a') が W2 のどの initial segment とも同型にならないものの 中から最小の a' を a1 とする．さらに，(1-1) の a1 に直下の元 a0 がある場合と， (1-2) の a1 に直下の元が無い場合の二通りがある．
場合 (1-1) の直下の元 a0 がある場合は，
W1(a0)≅W2(b0) for ∃b0∈W2
であるから，
W1(a1)=W1(a0)∪{a0}≅W2(b0)∪{b0}=W2(b1)
b1 は b0 の直上の元
となり，W1(a1) が W2 の同型の initial segment を持たないことに反する．
(1-2) a1 が直下の元を持たない場合には，a0<a1 の任意の a0 について， W1(a0)≅W2(b0) となる b0∈W2 があることになり，上で Equiv の中のチェインが上限を持つことを証明したのと同様に W1(a1) は W2 の 拡張 initial segment に同型のものを持つことが言えて，(1) の仮定に反する．
したがって，(1) の場合はないことが示された．次に (2) の場合もありあえないことを 示す．
まず，(2-1) W1 に最大元 m がある場合を考える．W1 自身は W2 の initial segment に 同型の部分を持たないが，W1(m)≅W2(b) なる b があるか，W1(m)≅W2 のどちらか である．前者の場合は，
W1=W1(m)∪{m}≅W2(b)∪{b}
となり，W1 全体が W2 の initial segment と同型にならないという仮定に反する．後者の場合は そのまま定理が成立するということである．
最後に (2-2) の，W1 に最大元がない場合であるが，これは a∈W1 のすべてに対して W1(a) 同型な W2 の initial segment を持つということであり， 上で Equiv の中のチェインが上限を持つことを証明したのと同様に W1 が W2 のいずれかの 拡張 initial segment と同型であることが示せる．
任意の集合 X に対して，(X, ≤) が整列集合になる順序 ≤ が存在する．
この定理では集合 A に整列順序の存在を保証しているが，このような整列順序は 一つではない．それこそ無数にある．ちょっと具体例を見ておこう．これは，後で述べる ツォルンの補題でも出てくる例だが，自然数の集合
N = {0, 1, 2, 3, ...}
に２つの整列順序を導入してみる．
これは普通の順序である．
これはまず，偶数をすべて並べて，その後ろに基数をならべたものである． これも整列順序である．
この例は，元の選び方を工夫すれば，二つの無限列を並べたものでなく，１つの 無限列になる例だった．
次に実数の集合 R を整列することを考えてみよう．こちらは具体的に どのように並べるかは指定することはできないのであるが，少なくとも， 基数の違いから，自然数と同型の整列集合１つではすべての元を尽くすことは できない．
これらの例を心に留めながら，次を読み進めていこう．
まず，自然数などの特殊な例を除き，一般的な集合の場合，整列可能定理は 選択公理を使わないと証明できない．証明方法としては，選択公理から直接 これを導く方法と，Zorn の補題を使う方法がある．しかし，直観的には やっていることは次の図のようなことである．
つまり，整列すべき集合 A が与えられたら，適当に元をとって次々に並べていく． それをずっと繰り返して，集合 A の元が尽きれば，それでよいが．ちょっと前にみた 偶数が尽きた後，奇数を並べた整列集合を思い起こしてほしい．例えば，自然数の 集合を整列しようとして，元を取っていくとき，偶数だけをとっていってしまうと このプロセスだけで自然数をすべて尽くすことはできない．こうやって無限に 並べていったあと，尽きなければ いままで繰り返したその上に１つ元を置き，そこからまた次々に上に元を置いて いくというプロセスが必要である．これを繰り返すことで，集合 A の上に整列順序を構築する．
ここではすごく直観的に集合 A を整列集合にする方法を述べたが，これは 実は Zorn の補題の状況にすごく似ている．
つまり，A の任意の部分集合 C が A と等しくないときは集合 A - C は空でないので 選択公理から，C に対して A - C の元を一つ選ぶ関数 f が存在する．この f が すでに作ったチェイン C の上の元を A から選ぶ，次の図の人の行為に該当する．
今，ここで直観的に話した内容を一応次の節「Zorn の補題を使った証明」で きちんと証明の形にしておこう．
W を A の部分集合に整列順序を入れた集合と定義する．
W := {(W, ≤) | W ⊆ A かつ (W, ≤) は整列集合}
ここで (W, ≤) の ≤ は全部同じ記号で書いてあるが，集合 W ごと， また同じ W に対しても (W, ≤) が整列集合になる順序は複数あることに 注意されたい．実体としては ≤ は，W × W の 部分集合である．(W1, ≤1), (W2, ≤2)∈W に対して，順序を
(W1, ≤1) ≤ (W2, ≤2) iff (W1 ⊆ W2) and (≤1 ⊆ ≤2)
と決める．この順序に対して，D ⊆ W が チェインなら，D の上限 ∨D は，
∨D = (∪(W, ≤)∈DW, ∪(W, ≤)∈D≤)
となる(これが，また整列集合であることは証明を要するがここでは省略する）．
すこし，記号が多いので分かりにくい人もいるかもしれない．多少でも絵にしてみよう．
図の左側はいま整列しようとしている集合 A である．その中には x0, x1, x2, x3, ... といった元がある．有限集合なら整列できるのは当たり前なので 無限集合と思っておこう．
真ん中の四角はイメージが楽になるように書いた．集合 A から適当に元，例えば，x0 を取り出す．そして，その上における可能な元を x0 の上に置いてみる．このように 上に枝を伸ばしていった可能な木をすべて考える．
右の W がこの証明で用いられている W と同じものである． これは左にある，上に伸びた木の一部分で整列集合になるものをすべて集めたものである． この部分集合 D ⊆ W はお互いに包含関係があり， 交わった部分で順序が一致しているなら，和集合をとることができて，結果も 整列集合である．
したがって，W は，包含関係 ⊆ に関して，任意のチェインが 上限を持つ．これは Zorn の補題の条件，そのものであるので，W は 極大元 (B, ⊆) を持つが，もし，B ≠ A なら，B - A から なにか元 c を持ってきて，B の上におけば，B ∪ {c} が整列集合になり， B の極大性に反する．したがって，B = A となり，集合 A が整列されたことになる．
まず，選択公理を使って，A 以外の P(A) の集合，すなわち A の真部分集合 X ⊂ A に対して，X 以外の元を 選ぶ関数 f
f : P(A) - {A} → Aを一つ決めておく．f(X) ∈ A - X
実は，この関数を決めた段階で．A の上に一つの整列順序がすでに決まっているのである． それは，X が整列されたとしたら，その後ろに f(X) を置くという順序である．
もし，X を整列した部分に最後の元 y があれば，f(X) はその直後の元であり，y は f(X) の直前の元である．また，もし，X を整列した部分に最後の元が無い場合， つまり，... と無限に続く場合は，f(X) の直前の元はない．どちらにしても， f を決めた段階で，このように A の整列順序が１つ定まるはずである．
整列可能定理の証明は，この直観が正しいことを丁寧に示していくことになる．
以下，上の直観的な議論を実際に証明に落としていく．
任意の集合 A に整列順序を入れることができることを証明する．
実は，この証明は次の節の Zorn の補題の証明を焼き直した ものである．
A の部分集合 X⊆A にある順序を入れた順序集合 (X, ≤) で次のようなものの すべての集合を C とする．
(X, ≤)∈C について
- (X, ≤) は整列集合である
- x = f({x'∈X | x' < x}) for ∀x∈X
このような (X, ≤) としては，({f(∅)}, ≤) がある．ここに ≤ は，f(∅) ≤ f(∅) とした順序である．
このように定義すると，C に含まれる２つの整列集合は どちらかが他方の切片になっており，C の中の整列集合の 和集合もまたCの元であり，実はそれが A 自身であることが 証明できる．以下でこのことを１つずつ証明していく．
(W1, ≤), (W2, ≤)∈C なら，
である．
[Proof]
- (W1, ≤) ≅ (W2, ≤) または
- W1(x1) ≅ W2 for ∃x1∈W1 または
- W1 ≅ W2(x2) for ∃x2∈W2
である．この同型写像が実は恒等写像であることを示せばよい．
これには超限帰納法を使えばよい．どれでも同じような方法で示せるので， 今，W1(x1) ≅ W2 for ∃x1∈W1 としてみる．
x∈W1(x1) に対して，X := {x'∈W1(x1) | x'<x} について W1(x1)→W2 の同型写像 f が恒等写像 id であったとする．
このとき，x=f(X)∈W1(x1) は f(X)=x∈W2 と対応するので， f(x) = x が言える．したがって，超限帰納法により，f は W1(x1) 全域で 恒等写像 id となる．
他の２つの場合も同様に証明できる．
[Q.E.D.]
(∪(X, ≤)∈C X, ≤) ∈ C
この順序集合の順序 ≤ は，式で書くと ∪(X, ≤)∈C ≤．すなわち，(X, ≤)∈C の順序 ≤ をすべて合わせたものである．
[Proof] B := ∪(X, ≤)∈C X とする．
命題１で，C の中の順序はすべて互換性があることが 示されている．すなわち，(X, ≤), (X', ≤')∈C ならば，x, y∈X∩X' については，x≤y iff x≤'y である．したがって，
≤B := ∪(X, ≤)∈C ≤．
とすると，これは順序になる．(B, ≤B)∈C で あることを示すためには，
を示せばよい．
- (B, ≤B) は整列集合である
- x = f({x'∈B | x' < x}) for ∀x∈B
まず，B が整列集合であることを示す．任意の空集合でない D ⊆ B をとると D には何か元 d∈D がある．d を含む (X, ≤)∈C を 一つとると，min D = min (D ∩ X) であり，後者は X が整列集合であること から存在する．したがって，B は任意の部分集合の最小元があり，整列集合である．
次に
x = f({x'∈B | x' < x}) for ∀x∈B
を示す．x∈B
に対して，x を含む(X, ≤)∈C を 一つとる．
x = f({x'∈X | x' < x})
であるが，X(x)=B(x) であるから，
x = f({x'∈B | x' < x})
が成立する．
よって，(B, ≤B)∈C が示された．
[Q.E.D.]
∪(X, ≤)∈C X = A
すなわち，これは A に整列順序が導入されたことになる．
[Proof] B := ∪(X, ≤)∈C X が A でないとする． このとき，(B ∪ {f(B)}, ≤') ∈ C となる．ここの順序 ≤' は，B のすべての元の上に f(B) を置いた順序とする．
しかし，この整列集合が C に入っているのは，元 f(B) を含む 整列集合が C に属していないことと反する． したがって，B=A であり，A 全体に整列順序が導入されたことになる．
[Q.E.D.]
以上で，任意の集合に整列順序が導入できることが示された．
これについては結構の分量があるので下記のページに，選択公理からこの 補題が導けることや応用などについて書いた．
Zorn の補題と選択公理のお話
正確には（∈について）整礎な集合すべての集まりという定義とのことだが，ZFC では 正則性公理(Foundation の公理， または，Regularity の公理)から， 集合はすべて整礎になるので 結果的にすべての集合の集まりになる．
さらに V 自身は集合ではない．これは，任意の集合 X は正則公理を満たす ことが要求されているから，X∉X だが，V は逆にすべての集合に対して X∈V である．集合の等しさは外延性公理（属する要素がまったく同じ集合が 同じ集合）によるので，V はどの集合とも異なる．つまり，V と等しい 集合は無い，ということは，Vは集合ではない．
ところで，冪集合の基数がもとの集合の基数より真に 大きくなること（|A| < |2A|）のところで述べた，A の 元から関数 f で対応の付かない A の部分集合として
Ef={X∈A | X∉f(X)}
があったが，A をV に変え，f を恒等写像 id に変えると，Eid=V になっている．また，これはラッセルの集合 {X | X∉X} とも同じ形であることは 興味深い．
最後に，V は整礎なクラスなので超限帰納法が使えるということを認識して おくとよいと思う．
そこで，順序数，基数あたりのローカルな関連を図にする努力をしてみた．以下は， 私自身の試論であり，不十分なところ，勘違いをしているところも多いだろうと いうことを念頭に置き，読んで欲しい．
まず，集合論が「数」学に寄与するとして，数の役割は順序付けることと 量を測ることであると，色々な書物に書いてあるような気がする．とりあえず， それを受け入れるとする．それぞれの役割に対して，順序数と基数が考え出された とする．
順序数は集合論では整列集合に支えられた表現を持っている．特にこの中の 自然数は，集合で
0=∅, 1={∅}, 2={∅, {∅}}, ...
と表すことができる．これらに対しては，集合としての表現があるだけでなく， 我々が 数学で行う演算が定義されなければならない．ここを支えるのが， 再帰定義の原理であり，さらにそれらは整礎集合と超限帰納法に支えられている．
一方，量を測るための基数は，直観的には集合間の全単射で同等性を把握するが 技巧的には（？），全単射のある順序数の中の最小の順序数を使って表現すると いった扱いがなされることが多いようだ．つまり，基数を理解するためには 順序数をきちんと理解しないといけない．
有限の数については，順序数でも基数でも一緒なので自然数は順序数の枠組みの 中から，基数にそのまま導入される．自然数が実現できたら，その上に整数の 集合，有理数の集合，実数の集合，複素数の集合を構築する方法は，１９世紀 から２０世紀にかけて結構研究され確立されている．こちらは集合論の教科書では さわりだけ論じている．詳細はそれぞれの分野で論じれば良いからだろう．
我々の学習という観点から言えば，順序数の学習に入った段階で，そこで 完結するといった気持ちで学習するのではなく，周辺のこのような諸概念と 深く結びつくと言った心構えで学習すべきだろうと思う．
また，順序数，基数の扱いの枠組みで，自然数の扱いはそれら全体の扱いのミニチュアを 演じる．したがって，自然数の扱いについてはきちんと学習することが必要である．
従来の数学を再度，集合論を使って構築するには少なくとも自然数の集合を 構築することが必要である．また，自然数の集合が構築できれば，それから 整数，有理数，実数，複素数などの構築ができ，従来の数学で扱っている 数の体系が構築できる．
ここでは自然数がどのように集合を使って表現できるか，また， 再帰定義を使って，自然数の集合の上にどのような関数が定義できるかを 見ていく． これらは後で，順序数 (Ordinals) などの展開にも参考になる．
ここの内容は主に National University of Singapore の Course Notes
Frank Stephan : Set Theory, 2009-2010, pp. 0-94を参考に書いた．
目次
まず，いくつかの概念を定義する．
集合 X が
が成立することとする．
inductive set に要素 x が入っていれば，x, S(x), S2(x), ... が 入っている．また，この系列に含まれない y が入っていれば，y から始まる 系列 y, S(y), S2(y), ... も入っている．
どんな inductive set にも ∅ が入っているので，系列 ∅, S(∅), S2(∅), ... はどんな inductive set にも入っている．
inductive set は，∅ から始めて，S(∅), ...,Sn(∅), ... と 無限の要素を含んでいる．公理的集合論では，無限集合の存在を保証するために 最低限１つの inductive set が存在することを公理として設けている．
無限集合の存在 少なくとも１つの inductive set が存在する（これを
ω で表すことにする）．
集合は入れ子になっている．例えば，ある集合は要素が１個しかなくても，その１個の 要素が集合でその中に沢山の要素が含まれていることもある．さらにそれぞれの 要素がまた集合でそれらがさらに要素を含んでいるといった具合にである．
こういう集合の要素に含まれている要素を全部１番はじめの集合に含ませてしまうと
全体の集合が最初の集合から直接見えて，色々な用途に扱いやすい場合がある．
transitive set とはそのような性質を持った集合である．定義としては，集合 X が
y∈X かつ z∈y ならば z∈X
が成り立つことである．あるいは
y∈X ならば y⊆Xと言いかえても良い．
一応，上に図で書いたが，下のようにもう少し図形的に表現した方が 分かりやすいかもしれない．
あとで証明するが，ZFC の集合論では Axiom of Foundation があるので すべての集合 X に対して，それを transitive にした集合 TC(X) が 存在する．
また，
ここでは，自然数の集合（相当）の N を定義する．
X を inductive set とするとき，
N(X) := ∩ {Y⊆X | Y は inductive}
と定義する．つまり，X に含まれるすべての inductive set の共通部分である． 後で証明するが，実は，X, X' を任意の inductive set とすると，
N(X)=N(X')
が証明できる．この一意に決まる N(X) を N と書くことにする． 我々の集合の体系 (ZFC) には inductive set ω が存在するので，N も 存在する．N はすべての集合のクラス V に存在するすべての inductive set の共通集合に なっている．
一応，任意の inductive set X, X' に対して，N(X)=N(X') であることを 証明しておく．X と X' が inductive set のとき， X ∩ X' も inductive set であることから，inductive set X1, X2 に対して
X1⊆X2 ならば N(X1) = N(X2)
を証明すれば，
N(X) = N(X∩X') = N(X')
となり，任意の inductive set X に対して N(X) が等しいことが分かる．
いま，X1⊆X2 として，N(X1) - N(X2) ≠ ∅ としてみる．
y∈N(X1) - N(X2) とすると，y∉N(X2) であるから， X2 には y を含まない inductive set Y⊆X2 が存在するが，X1∩Y⊆X1 も inductive set であるため， y∉N(X1) のはずである．これは，y∈N(X1) - N(X2) に 反する．
N は最小の inductive set だったが，これは transitive でも ある．つまり，その要素の要素は N にみな含まれている． これは次のようにして分かる．N の中の元で，その要素がすべて N に含まれているものの集合を A とする．A = N を 示せば，N の要素はすべて N の部分集合となり，N は transitive であることが分かる．
まず，∅⊆N であるから，∅∈A である．次に，X∈A ならば X⊆N であるから，S(X)=X∪{X}⊆N であるから， S(X)∈A．これは A が inductive set であることを意味し，A を含む N は最小の inductive set であったから，A と一致せざるを得ない．つまり， N 自身，transitive である．
[Q.E.D]
この証明は数学的帰納法でも出来そうだ．なにしろ，
であることを利用している訳だから．でも，その前に数学的帰納法がこの N に使えることを証明しておく必要がある．なにしろ，この N は 「我々の」N ではなく，最小の inductive set たる N なのだから．
P(n) を集合 n に関する論理式とする．このとき，
P(∅) and (P(n) ならば P(S(n)))が示せるなら，
∀n∈N P(n)が成り立つ．
N の要素 n のうち，P(n) が成り立つ要素の集合を A とする．つまり，
A := {X∈N | P(X) }
A は ∅∈A かつ X∈A ならば S(X)∈A を満たすので inductive set である． N は最小の inductive set なので，N=A．
ということで，上で N が transitive である証明に数学的帰納法を 使うというアイデアは正当化された．まあ，一応，証明を書いておく．
(1) ∅⊆N
(2) X∈N が X⊆N とする．このとき
S(X) = X∪{X} ⊆ N∪{X} = N
もう一つ，集合が N と一致するための必要十分条件を書いておく．
N の中身はどうなっているだろうか？
N の中には， ∅ から始まって，X∪{X} を次々に作っていった
つまり，我々の馴染みのある書き方をすると
が入っているのは分かる．しかし，これ以外に何か入っていないの だろうかという疑問である．
結論から言うと，我々が使っている表現体系（一階述語論理）では， ちょうどこれらが N の内容であるということを記述することは できない（これについては別のページ Löwenheim-Skolem の定理 でも多少は書いている）．つまり，ZFC 集合論の公理を満たす集合の世界として， 自然数の集合 N が，0, 1, 2, ... 以外も含むものが作り得ると いうことである．そのような可能性は複数あり得る．中には， N が非可算個の要素を含むものもあり得る．
しかし，そのような 0, 1, 2, ... 以外の要素を含んだとしても，数学的帰納法
が成り立つ．これは安心してよい．P(0) が成り立ち，P(n) が成り立つなら P(n+1) も成り立つならば，任意の n∈N に対して P(n) が成り立つ
これらについては，次のキーワードの組み合わせで検索してみるとよい．
自然数, 超準モデル
(英語では natural numbers, non-standard model)
色々面白い情報が集まると思う．
次の定理は，自然数の集合 N から V への関数を再帰的に 定義できると言うことを主張している．
g を N×V→V の関数，a∈Vとするとき， 次の性質を満たす関数 f : N→V が唯一存在する．
ここでは自然数の集合 N を，最小の inductive set として定義した． N の定義方法としては他にもある．例えば，
William A. R. Weiss : Introduction to SET THEORY, 2008, pp. 1-119
では，次のように定義されている（2018.09.08 時点）．
自然数の集合 N
n (∈V) 注) が自然数である とは次のことが成立することであるとする．(n=∅ ∨ ∃x∈n n=S(x)) ∧
(∀m∈n (m=∅ ∨ ∃y∈n m=S(y)))ここで S(x) := x∪{x}
N := {n | n は自然数}
注： テキストをざっと見た限りでは，n の範囲は特に書いていないので， 我々のイメージとしては V としておく．
この定義だと，N が集合なのかクラスなのかさえ，（私には）すぐには 分からない．私はまだこれらの定義が同等かどうかは検討していないが， 自分の備忘録と，ここを読む人の参考のために N のこの定義をあげておく．
有限集合，無限集合に関していくつか用語を導入する．
TC(X) := ∩{Y | {X}⊆Y かつ Y は transitive}
直観的な言葉で言えば，集合 {X} から始め，その要素である集合の 中身をすべてそれに加え， またその中身をそれに加えということを続けていって，transitive set に したものである．
有限集合はトップレベルの要素が有限個であればよいが，遺伝的有限集合では さらに要素である集合も有限で，そのまた要素である集合も有限でという ように続いていく．
遺伝的有限集合は有限集合であるが，逆は必ずしも 真ではない． 例えば，{N} は，1 = {0} と全単射がある有限集合だが，N が無限集合であり，遺伝的有限集合ではない．
Vω := {x∈V | x は遺伝的有限}
自然数の一般化．
集合 X が
例：
順序数は整列集合であるという条件を付けたが，これは次の定理のように transitive かつ ∈ について全順序集合であれば，∈ について 整列集合になるので，transitive かつ ∈ について全順序集合という条件 だけでよい．
X は順序数 ⇔ X は transitive かつ ∈ に関して全順序集合
=> は当たり前だから，<= を証明する．それには，
X は transitive かつ ∈ に関して全順序集合ならば X は∈ に関して整列集合
を示せばよい．
D⊆X を X の任意の空でない部分集合とする．正則性の公理から，∃z∈D z∩D=∅．
この z が ∈ に関してD の最小元になる．なぜなら，u∈D かつ u∈z なる u があったとすると，u∈z∩D となり，z∩D=∅ に反するからである． したがって，X の任意の部分集合には最小元が存在し，X は整列集合になる．
順序数（Ordinals）は順番を表す数であったが，基数（Cardinals）は量を表す ための数である．
基数を定義する前に，すでに定義してある集合同士の基数の大小と，これから 定義する，集合の基数と用語が重なり，紛らわしいので，集合同士の大きさの定義を復習しておく．
X, Y を集合とするとき，
また，|X|≤|Y| で |X|≠|Y| の場合は，|X|<|Y| と 書く．
これらの準備の元に，集合同士の比較の文脈でなく，単独の集合に対する 基数の概念を定義する．
順序数αは，
であるとき，
言い換えればお互いに全単射を持つ順序数の中で最小の順序数を基数と言う．
集合 A に対して，|A| = |α| となる基数（A とαの間に全単射がある基数）が
あれば，それを
任意の基数αに対して，それより大きい最小の基数が存在する．それを
いったん，誰かが，このようにイメージを掴みやすくなるまでかみ砕いてしまえば 他の人の学習はかなり楽になると思う．これはいわば知識のコンパイル作業 なのだ．一度，ソースプログラムを高度に最適化しながらコンパイルして しまえば，そのときは時間がかかっても，そのコンパイルした結果が色々な 場所で，色々な人によって，何度も実行されるなら，コンパイルに掛けた 時間や費用の元は取れるのである．
私は，計算機科学の基礎となる数学で複数の人，特に企業にいて，「学習しなければ」 と思いつつ，十分な時間が取れない人の学習を効率化できる ような教材を整理していき，できれば，その提供やをれを利用した教育を生業と できたらと考えている．このページはそのための教材のネタ作りと蓄積， ブラッシュアップの活動の一環である．
集合，位相，論理など へ
圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)