順序型と順序数
自然数全体の集合と偶数全体の集合は, それぞれ大小の順で並べたとき, "同じ並び方" をしています.
{ 0, 1, 2, 3, ... }
{ 0, 2, 4, 6, ... }
この "並び方" を "順序型" と呼びます. より詳しく述べれば,
"同じ並び方を持つ順序付けされた集合全てから抽象される何か"
が順序型であるといえます. 一般には整列順序でない順序についても順序型の概念は存在しますが, ここでは整列順序の順序型に限って考えます.
もう少し具体例を見ていきましょう. { 0, 1, 2, 3 } と { 1, 2, 4, 8 } は同じ順序型を持ちます. また, { 2, 3, 5, 7 } と { 0, 1, 2, 3, 4, 5 } は異なる順序型を持ち, 後者の方が "長く伸びて" います.
一般に, 整列順序で並べられた集合 (これを整列集合という) が 2 つあったとき, これらは同じ順序型を持つか, そうでないならば必ず一方は他方より "長く伸びて" いることが証明されます. (整列集合の比較可能定理) また, 整列順序の順序型全体を, 長く伸びている方をより "大きい" として順序付けると, 整列順序の順序型全体が整列します. 中々に自己言及的ですが, これは後の議論で本質的です.
上の例を見れば, 同じ順序型を持つためには同じ個数の要素を持つことが必要であることは了解されるでしょう. では同じ個数の要素を持つことは同じ順序型を持つための十分条件でしょうか ?
答えは一般には No です. しかし, 有限個の要素を持つ集合に限れば Yes です.
まず有限集合の話から見ていきましょう. 例えば { 0, 1, 2, 3 } を通常の大小で並べれば (0, 1, 2, 3) の順で並んでいます. いま勝手に (2, 1, 3, 0) の順で並ぶ新しい順序をつくります. どちらの順序で並べても本質的に
○ < ○ < ○ < ○
という並び方に変わりないことがわかります.
また, 要素が 4 個である限り, どのような順で並べても "○ < ○ < ○ < ○" 以外にありえないことは直観的には明らかです.
(余談ですが全ての有限集合に対して完全に厳密に上の内容を証明しようとすると中々に面倒で, "余りに明らか過ぎると証明しづらい" という例になっています. しかしこういった主張を証明できるかどうかは理解度の良い目安になります.)
次に無限集合の話です. "無限集合では, 要素の個数が同じでも順序の入れ方が異なれば異なる順序型を持ち得る" ことを説明します. そもそも無限集合における要素の個数とは何か, というと集合の "濃度" と呼ばれる概念で, コレについても追々お話していきたいところですが, その話を始めると話が脇に逸れすぎてしまいます.
しかし, "集合として同じならば要素の個数も同じ" というのは直観的に明らかとも, "要素の個数の概念を定義する限り当然成り立つべき" ともいえます. そこで, 同じ集合に異なる順序を入れて異なる順序型となる例を挙げることで無限集合での説明としましょう.
集合としては自然数全体に新しい元 'x' を追加します. 自然数は全て通常の大小で並び, x は一方では全ての自然数より大きい (最大元) とし, もう一方では全ての自然数より小さい (最小元) とします.
(A): 0 < 1 < 2 < ... (自然数全て) ... < x
(B): x < 0 < 1 < 2 < ... (自然数全て) ...
これでどちらも整列順序になっていますが, 並び方は本質的に異なります. (A) で x は最大元, 即ち (A) の並び方は最大元を持ちますが, (B) に最大元は存在しません.
さて, 順序型の説明で "抽象される何か" とは大層あやふやで, 数学的考察の対象となるモノ (object) として扱いづらいことが困ります.
そこで, 抽象的な順序型の概念に対応する具体的なモノ (object) として, "順序数 (ordinal number)" という集合が使われます.
順序数はそれ自身の要素に対する整列順序を持ち, 自身の整列順序の順序型に対応しています. 順序型と対比して述べれば,
順序型: "同じ並び方を持つ順序付けされた集合全てから抽象される何か (概念)"
順序数: "同じ並び方を持つ順序付けされた集合全てのうち一番性質の良い集合 (集合)"
といえます. "性質の良い" とはどういう意味か述べられていませんが, その点は少しづつ説明していく予定です.
まず実際に順序数がどのような集合なのかを見ていきましょう. それが "自然" で "性質の良い" といえることの説明は後のお楽しみです.
順序数は, 集合としては "自分自身より小さい (並びが短い) 順序数全体からなる集合" です.
小さい順に見ていくのでまずは有限順序数です. 名前としては普通の自然数で目新しいものはありませんが, 集合としての構造は中々に趣深いものがあります.
0 = ∅ = {}
0 は最小の順序数で, 要素の個数 0 個の整列集合の順序数です. 要素の個数が 0 個の集合は空集合しか存在しないため, 順序数 0 自身も空集合 (とその上の trivial な順序) となります.
1 = { 0 } = {{}}
1 は 0 の次の順序数で, 要素の個数 1 個の整列集合の順序数です. 集合としての要素は順序数 1 より小さい順序数全て, 即ち 0 のみからなります.
つまり 1 = { 0 } ですが, 0 = {} といえるので 1 = {{}} とも書けます.
2 = { 0, 1 } = {{}{{}}}
順序数 2 の要素は自身より小さい順序数全て, 即ち 0, 1 からなります. つまり 2 = { 0, 1 } ですが, 0 = {}, 1 = {{}} と考えれば 2 = {{}{{}}} とも書けます.
3 = { 0, 1, 2 } = {{}{{}}{{}{{}}}}
4 = { 0, 1, 2, 3 } = {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
5 = { 0, 1, 2, 3, 4 } = {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}
このように続けることで, 全ての自然数 n について, n 個の要素を持つ整列集合の順序数をつくることが出来ます. その順序数は名前としては "n" と呼ばれますが, 集合としては 0 ~ n-1 までの順序数を要素として持ちます.
n = { 0, 1, 2, ... , n-1 }
ちなみに n の次の順序数 n+1 は, 集合としては n ∪ { n } と書けます.
n ∪ { n } = { 0, 1, 2, ... , n-1 } ∪ { n } = { 0, 1, 2, ... , n-1, n } = n+1
n+1 は n の "次の" 順序数で, n' とも書きます.
以上の順序数は要素の個数が有限のため, 有限順序数 (finite ordinal) と呼ばれます. 実際のところ通常の自然数と同じものと考えて差し支えありません.
さて, ここからが本番です. 全ての有限順序数を集めて集合とし, 順序数の大小で並べることで, 無限個の要素を持つ順序数が得られ, これを ω と呼びます.
ω = { 0, 1, 2, ... }
集合としては自然数全体の集合と同じものですが, 順序数の文脈では ω で書き表すことが多いです. またこのような文脈では, "n は自然数" を "n < ω" と書くことがよくあります.
無限個の要素を持つ順序数は "超限順序数 (transfinite ordinal)" と呼ばれ, ω はそのようなもののうち最小の順序数です.
また ω はどんな順序数 α に対しても ω = α' (= α+1) となりません. このような性質を持つ順序数は "極限順序数 (limit ordinal)" と呼ばれます. 感覚的には ω は全ての自然数の極限 (limit) です.
逆に順序数 β が, ある α に対し β = α' となるとき, β は "後継順序数 (succesor ordinal)" と呼ばれます.
ω+1 = { 0, 1, 2, ... , ω }
ω+2 = { 0, 1, 2, ... , ω, ω+1 }
ω+3 = { 0, 1, 2, ... , ω, ω+1, ω+2 }
...
ω+n = { 0, 1, 2, ... , ω, ω+1, ω+2, ... , ω+(n-1) }
...
この ω+n (n < ω) の極限として ω+ω = ω2 が得られます.
サラッと定義無しに和や積を書いてしまっていますが追々詳しく説明していきます. ここで注意する必要があるのは, 順序数の和や積は非可換, つまり一般に α+β ≠ β+α, α×β ≠ β×α であることです.
ここでの ω2 は ω×2 を表します. この ω2 は ω の次の limit ordinal です.
ω2 = { 0, 1, 2, ... , ω, ω+1, ω+2, ... }
ω2 + 1 = { 0, 1, 2, ... , ω, ω+1, ω+2, ... , ω2 }
ω2 + 2 = { 0, 1, 2, ... , ω, ω+1, ω+2, ... , ω2, ω2 + 1 }
...
またさらに ω2 + n (n < ω) の極限として ω3 が得られます. ω3 + n (n < ω) の極限として ω4 が得られます.
ωm + n (m, n < ω) の極限は何でしょうか ?
それは ω×ω = ω^2 が答えとなります. このあたりから指数表記が出始めるので, TeX → 画像で見た方が見やすいです. いろいろと手間がかかるので続きます.
