たくさん進んで一歩下がる

第22話 いろいろな順序数

「はっかせー！きたよー！」

「あれ？今日はロクリアちゃん一人？」

「うん、お姉ちゃんは、なんだかすることがあるんだって」

　なんだか寂しいような、ほっとしたような。

「お姉ちゃんいたほうがよかった？」

「いや、大丈夫だよ、いろんな順序数の話をするんだったね。

　まずは、順序数とはそもそもどういうものか、という話を軽くしておきたい。とはいえ、小難しい話だし、いろいろ定義の仕方はあるので、興味がないという場合は、※まで飛ばしてもらってかまわないよ。

　順序数とは、集合論を使って定義するのが普通だ。集合論というと難しく聞こえるけど、無限を扱うのには非常に適している。理解できるかどうかはさておき、少しだけ、様子を見てみよう。

　集合というのは、

{ }

　というカッコの中に、いろいろな要素をいれたものだ。例えば、

　A={a,b,5}

　なら、

　Aという集合にはaという要素、bという要素、5という要素が属している、という意味だ。ここで、集合の中に書かれている要素の順番は気にしない。つまり、

{a,b,5}={a,5,b}

　ということだ。そして、Aの部分を取ってきた

{a}　{b}　{5}　{a,b}　{a,5}　{b,5}

　や、それ自身

{a,b,5}

　や、何も要素が無い集合（空集合という）

{}

　を、Aの部分集合という。

ここで、空集合をφと書くことがある。これは単純に{}の省略だ。

　まず、順序数0に相当するのは、空集合だ。

{}=0

　ちなみに要素の数はもちろん0個。

　いろいろ誤解を招きやすいので、一応補足説明をしよう。

{}=φ=0

だが、一つ目の「=」と二つ目の「=」は少し事情がちがう。一つ目の「=」は単純に集合論の中での省略記号の定義だ。二つ目の「=」は、集合論と、順序数という2つの別の数学の対象の同一視だ。もしくは、集合論をつかった順序数の定義だ。

話を進めよう。

この集合{}を要素として持つ集合が、次の順序数だ。

{{}}=1

　だ。要素の数は1個だよ。空集合という要素が1個ということだ。なんだか気持ち悪いけどね。記号φを使えば、

{φ}

とも書けるし、順序数0を使って

{0}

と書いても良い。

そして、今までに出てきた順序数を要素として持つのが、次の順序数だ。

{0,1}={{},{{}}}={φ,{φ}}=2

要素の数は2つであることに注意しよう。

そして、今までに出てきた順序数を要素として持つのが次の順序数だ。

{0,1,2}={{},{{}},{{},{{}}}}={φ,{φ},{φ,{φ}}}=3

非常に見辛いけど、要素は、φと、{φ}と、{φ,{φ}}の3つだよ。

以下同様にして、4,5,6...も定義できる。

そこで、次のような集合がωだ。

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

要素の個数は自然数の個数と等しい。自然数の個数は、ℵ_0とも書くよ。

そして、ωは無限に要素を持つが、有限順序数はそれに対応している自然数の個数しか要素をもたない。なので、ωはどんなそれ以下の順序数とも異なっている。さらに、ω自身はωを要素には持っていない（有限順序数しか要素でない）。

つまり、次の順序数はωとしっかり異なっている。

{0,1,2,3,...,ω}=ω+1

ここでいう+1とは、次の順序数を得る記号ということだ。

　順序数を集合で見るのは一旦ここまでにしよう。ちなみに、集合にあまり触れたことが無い人は、ここまで読んだら、もう一度読み直してほしい。少し不思議に見えるかもしれない。

※

　さて、ここまでは前置きだった。

　さて、いろいろな順序数を見てみよう。

　0

　これは一番初めの順序数という特徴を持った、非常に大事な順序数だ。0以外のどんな順序数よりも小さいといえる。

　1

　これは、じつはすごく大切な特徴があり、この順序数より小さい順序数と+を使っても到達できない最小の順序数、というものだ。なぜなら、0+0+0...とやっても0で、1には届かないからね。当たり前？でも、次はωまで待たなくてはいけない。

　2

　これはこれより小さい順序数と+を使って表すことができる最小の順序数だ。つまり、1+1ということだね。

　ω

　先ほど書いた通り、この順序数より小さい順序数と+を使っても届かない2番目に小さい順序数だ。異なる値を取り続ける収束列をもつ最小順序数ともいえる。収束列とは、その値には届かないものの、その値には近付き続けるような順序数の列のことで、具体的には、1,2,3,4,...だ。なお、そのような性質を持つ順序数を、極限順序数という。また、ωより大きい順序数を超限順序数と呼ぶ。超限順序数は、1+α=αが成り立つような順序数αとも定義できる。

　ω+1

　超限順序数でありながら、極限順序数でない最小の順序数だ。

　ω+ω=ω×2

　極限順序数で、基本列は、ω+1,ω+2,ω+3,...

　なお、超限順序数でありながら、それ以下の順序数と+を使って作ることができることに注意しよう。

　ω×ω=ω^2

　これも極限順序数で、基本列は、ω×1,ω×2,ω×3,...

　この順序数より小さい順序数と+を使ってこの順序数を作ることはできない。そのような性質を持つ3番目の順序数だ。なお、ω+α=αを満たす最小の順序数でもある。

　ω×(ω+1)=ω^2+ω

　ちょっとこんな複雑な順序数も作ることができる。なお、順序数には、和と積について、和が積の右側の時に限り、分配法則が成り立つ。これも極限順序数で、基本列は、ω^2+1, ω^2+2, ω^2+3, ...

　ω×ω×ω=ω^3

　簡単には示せないが、順序数の乗算は結合法則を満たす。すなわち、(ω×ω)×ω=ω×(ω×ω)である。左辺を見ると、基本列がわかり、

　ω×ω×1, ω×ω×2, ω×ω×3, ...である。

　※ω×(ω+1)×ωは計算すると、

　=(ω^2+ω)×ωで、極限順序数である。この基本列を見てみると、

(ω^2+ω)×1, (ω^2+ω)×2, (ω^2+ω)×3, ...

　である。和が左側では分配法則は使えないので、注意深く計算しよう。

(ω^2+ω)×1=ω^2+ω

(ω^2+ω)×2=ω^2+ω+ω^2+ω=ω^2×2+ω

(ω^2+ω)×3=ω^2×3+ω

　この順序数列はω^3を超えることがないが、ω^3より小さいどのような順序数よりも大きくすることができる。よって、この列はω^3に収束する。ゆえに、

　ω×(ω+1)×ω=ω^3

　ω^ω

　これは、ω×α=αを満たす、2番目の順序数だ。なお、1番目は0である。基本列は、ω^1, ω^2, ω^3, ...

　※ω×ω^ωの基本列を見ると、

　ω×(ω), ω×(ω×ω), ω×(ω×ω×ω), ...

　で、積には結合法則が成り立つので、結局この収束先はω^ωであるから、

ω×ω^ω=ω^ω

　ω^ω×ω

　これは、ω^ωより真に大きい。まず基本列を見よう。

　ω^ω×1, ω^ω×2, ω^ω×3, ...

　これは、

　ω^ω, ω^ω+ω^ω, ω^ω+ω^ω+ω^ω, ...

　ということを言っている。ω^ω+1はω^ωの次の順序数なので真に大きく、ω^ωは1よりも大きいため、ω^ω×ωもω^ωより大きいことがわかる。

　ω^ω^2

　計算すると、ω^(ω×ω)で、これの収束列は

　ω^(ω×1), ω^(ω×2), ω^(ω×3), ... である。

　ω^ω^ω

　収束列は

　ω^ω^1, ω^ω^2, ω^ω^3, ...

　ε_0

　これが、イプシロンゼロと呼ばれる順序数だ。これは一つの到達地点で、数多くの順序数の中でも燦然とした輝きを放つ。まず基本列を見て、実態をつかもう。

　ω, ω^ω, ω^ω^ω, ...

　こう書き直したほうが、もはや馴染み深いかもしれない。

　ω^^1, ω^^2, ω^^3, ...

　つまり、ε_0=ω^^ωと書いてもよい。ただし、順序数に通常テトレーション^^は定義されていないので、若干危険な書き方ではある。

　ε_0の重要な性質は、それ以下の順序数と、和、積、冪乗を使って表せない二番目の順序数というものだ。（なお、1=0^0とする。一番目の順序数はω）

　さて、ここから少し順序数を眺めながら練習だ。

　ε_0×2

　順序数はいつでも基本列を求めることが、性質に直結している。この基本列を求めるために、まず書き直そう。

　ε_0+ε_0

　和の形にできたら、一番右側の順序数の基本列を求めればよい。いつでも、一番最後に計算する演算の右側の順序数を極限順序数にして、その基本列を求める、というのが定跡だ。

　ε_0+ω,ε_0+ω^ω,ε_0+ω^ω^ω, ...

　ε_0^(ω+1)

　これも極限順序数だが、最後に計算する項の右側が、ω+1と極限順序数でない。指数法則は、いつでも実数と同じようには使えないが、今回はうまくいく。

　ε_0^ω×ε_0と書き直して、その基本列は、

　ε_0^ω×ω, ε_0^ω×ω^ω, ε_0^ω×ω^ω^ω...

　ε_0^ε_0+ε_0×6+ω×2+4

　こんなものももちろんある。これは極限順序数ではない。

　ε_1=ε_0^^ω=ε_0^ε_0^ε_0...

　イプシロン1。これは、それ以下の順序数と、和、積、冪乗で作ることのできない二番目の順序数だ。つまり、この性質をもつものを順番に並べたのが、ε_nということだ。テトレーションは順序数には定義されていないが、式の形を見るために便宜的につかうことはできる。基本列は式の形からあきらかなので、割愛する。

　ε_1^(ε_0×2)

　計算練習としては面白い形ををしていると思う。さて、これも指数法則を注意深く使うと、

(ε_1^ε_0)^2=(ε_1^ε_0)×(ε_1^ε_0)

　となる。基本列は一番右側のε_0を崩すことによって得る。

(ε_1^ε_0)×(ε_1^ω) , (ε_1^ε_0)×(ε_1^ω^ω) , ...

　ε_4=ε_3^^ω

　こういうのを見るのも楽しい。テトレーションの形を使うと、基本列が分かりやすい。

　ε_ω

　そこに自然数が書かれていれば、それ自体を基本列にしたくなってしまうだろう！？

　これは、ε_nという形と、和と積と冪乗をつかって表すことのできない最小の順序数だ。基本列はわかりやすいが、一応書いておこう。

　ε_0, ε_1, ε_2, ...

　ε_(ω+1)

　まあ、こういうのも作れる。これは、テトレーションを借りよう。ε_(n+1)=ε_n^^ωだったことを利用して

　ε_(ω+1)=ε_ω^^ω=ε_ω^ε_ω^ε_ω...

　基本列は

　ε_ω, ε_ω^ε_ω, ε_ω^ε_ω^ε_ω, ...

　ε_(ε_0)

　もう冗談みたいな話だが、ε_(n)っていう関数みたいに見えてこないかい？じゃあ、実際そのように扱ってしまおう。ε_nの性質を思い出すと、それ以下の順序数と、和と積と冪乗を使って表すことのできないn-1番めの順序数であった。つまり、nから順序数を得る関数として使ってしまっている。

　ζ_0=ε_ε_ε_ε_...

　おっと、これは豚が逃げた後の模様かな？

　基本列を見て納得しよう。

　ε_0

　ε_(ε_0)

　ε_(ε_(ε_0))

　なんだいロクリアちゃん。関数の合成を使いたいかい？ならこの順序数はこのように表せる。

　ε^ω_0

　これは、それ以下の順序数と、関数εと和と積と冪乗を使って表すことのできない最小の順序数だ。関数εと開き直っているが、実にε_0ぶりの、和、積、冪乗に次ぐもう一つの演算だ。そう思うと、ζ_0は非常に美しい順序数だ。

　さて、ここからはいろんな一般化の仕方がある。この演算の数、つまり、ある超限順序数がそれ以下の順序数とこの演算を使って書けない最小の数、という言い方をしたのは、

　ε_0 (冪乗)

　ζ_0 (ε)であった。

　1番目、2番目と数えて、

　ε_0=φ(1,0)

　ζ_0=φ(2,0)

　と書こうじゃないか。そうすると、

　ε_n=φ(1,n)

　ζ_n=φ(2,n)

　と書ける。もうわかっただろう。

　φ(3,0)

　ζとεと冪乗と積と和とそれ以下の順序数で表せない最小の数だ。

　φ(ω,0)

　もうここまでじっくり付き合ってくれたロクリアちゃんなら、言わんとすることはわかるよね。

　一応一般化しておこう。

　φ(a,0)の基本列は

　φ(a,0), φ(a-1,φ(a-1,0)), φ(a-1,φ(a-1,φ(a-1,0)))...

　といった具合で、

　φ(ω,0)の基本列は

　φ(1,0), φ(2,0), φ(3,0) ,...

　である。0から始めたり1から始めたりしているのは僕の趣味の問題だ。

　Γ_0 = φ(1,0,0)

　さて、これはなにかな？察しがよいロクリアちゃんなら気づいたかな。

　それ以下の順序数と、(2変数関数としての)φとそれ以下の関数を使って表せないような最小の順序数だ。基本列は、

　φ(1,0)

　φ(φ(1,0),0)

　φ(φ(φ(1,0),0),0)

　...

　である。楽しい。

　Γ_1 = φ(1,0,1)

　あー、つまり、 それ以下の順序数と、(2変数の)φとそれ以下の関数を使って表せないような2番目の順序数だ。

　Γ_Γ_Γ_... = φ(1,1,0)

　なんだろう、これは高速道路に立っている電灯かな？Γのほうを見ると基本列が分かりやすくてよい。

　・・・ここで突然わかりにくくなったと思わないかい？2変数のφまでは簡単だったにも関わらずだ。しかも、二つの系統に分かれてしまっている。しかし、φを使うほうはともかく、Γを使うほうは文字数がそれこそω個、いやもっと必要になってしまって、うまくいかない。厳密な理解は専門書に任せて、雰囲気だけ眺めよう。

　φ(1,0,0,0)

　三変数φとそれ以下の演算で以下略

　φ(1,0,0,0,0,...)=ϑ(Ω^ω)

　うーん、左はわかりやすいが、右が分かりにくい。実は違う系統で進んできたϑ（シータ）(Ω^n)という系統があって、簡単にいうとφの変数の数を表すのがΩ^nのnの役割であった。なお、ϑ(Ω^0)が、φ(1,0)で、すでに2変数なので、実際の変数の個数とは2個ずれてしまう。しかし、問題はない。2+ω=ωなのだから！

　なお、小ウェブレン順序数という名前がついている。かっこいいけど、小・・・？ってことは・・・

　ϑ(Ω^Ω)

　これが大ウェブレン順序数だ。ここまでは、まだφの名残で理解できる。

　つまり、それ以下の順序数と、ϑ(Ω^n)のnを変数とした関数(つまりφの変数の数)とそれ以下の関数を使っても表すことができないような最小の順序数ということだ。

　ちなみに、φというのは本質的で、その限界超えてしまった大ウェブレン順序数はある意味で急増加関数に使えるレベルでは限界といえる。（小ウェブレン順序数で、すでに限界は迎えている）ここから先は、順序数そのものを使える順序数にする関数、というものを考えなきゃいけない。実はすでに出てきているϑがそれだ。そして、Ωという記号が未定義のまま使われていて意味不明だったと思うけど、これは非可算順序数というもので、実はそのままでは急増加関数に使うことができない。

　これは、超限順序数は自然数ではないので、巨大数とは言えないから、急増加関数を使って自然数に落としてあげたのと同じ構造を、非可算順序数では急増加関数に適した順序数とは言えないので、可算順序数に落としてあげた、ということだ。

　とはいえ、どんなに大きな自然数を作っても、それより本質的に大きいといえる、つまり巨大数のパラドックスの誤差の範囲にされてしまうような自然数が存在するように、可算順序数はまだまだ続く。最後にずば抜けて大きい可算順序数を一つだけ紹介して終わりにしよう。

　ω^CK_1

　チャーチクリーネ順序数だ。これは、上でやってきたようなどのような繰り返し手順を用いてもたどり着けない順序数だ。・・・つまりわかりやすい基本列が存在しなくなってしまった。実際には別の数学の力を借りて基本列をつくることはできる。

　少々異常な順序数で、巨大数論ではここはひとつの境目となっている。もちろん、このまま急増加関数に使うことは収束列が自明でないためできないのだが、収束列を定義してやれば急増加関数にできる。これはあらゆる再帰的に計算できる関数より早く増加するので、計算不可能関数という分野になる。

　・・・あれ、

　・・・おーい

　・・・ロクリアちゃん？

　・・・うーん、、、

　・・・寝てしまったか」