差分

前提知識 * 知らないと厳しい: 数学的帰納法* 知ってると便利: ペアノの公理* 知ってると便利: 公理的集合論 ==第0章 ダンジョンRPGの塔==無限のモンスターが住まう無限の塔を考える。ただし、'''この塔はイギリスにあるものとする。''' 塔の0階には受付の人間がいて、それより上の階には1匹ずつモンスターがいる。モンスターの強さには、以下のような関係があるものとする。* 全てのモンスターは人間より強い。* XがYより強く、YがZより強いなら、XはZより強い。すなわち、強さに3すくみのような「ループ」は存在しない。* 任意のモンスターに対し、そこから「それより弱いモンスターを選ぶ」という操作をいつか繰り返すと、必ずいつかは弱いモンスターがいなくなる。 ===具体例=== ====つまらない例==== 上に行くほど強くなる無限の塔を考える。 すなわち、強さの序列が0階<1階<2階<・・・と無限に続いていく。 この塔は上の条件を全て満たしている。3つ目の条件を満たすことを厳密に示すためには数学的帰納法が使用される。 ====多少は面白い例==== 偶数階・奇数階ごとに上に行くほど強くなる無限の塔を考える。また、奇数階は上級者向けであり、奇数階のどのモンスターも偶数階の全てのモンスターを一撃で倒せるものとする。 このときの強さの序列は0階<2階<4階<・・・<1階<3階<5階<・・・となり、無限をさらに超えて続いていく。 この塔は上の条件を全て満たしている。3つ目の条件を満たすことを厳密に示すためには数学的帰納法を拡張した超限帰納法と呼ばれる証明法が使用される。 ==第1章 クエスト== あなたは絶対にオーバーフローしないカウンターを持っている。そのカウンターを持って、ヘリコプターでこの塔に窓から乱入したとする。カウンターの初期値は任意とするが、一般にnという記号が用いられるためこの記事でもそれに従う。 あなたはプレイヤーなのでモンスターに負けることはないとする。 さて、あなたがモンスターを瀕死にまで追い込むと、モンスターはカウンターの値を要求する。 あなたがカウンターを見せると、モンスターは「302 Found......」と断末魔を上げながら倒れ、最期に自分より弱いモンスターがいる階数を1つ提示する。いないときは0階を提示する。 また、カウンターをインクリメントするかしないかのbooleanパラメータ(この記事だけの用語として'''インクリメントパラメータ'''と呼ぶ)もあなたに渡される(実際には常にtrueでもいいのだが、巨大数の慣習に合わせてfalseになるケースもサポートしておく)。 このリダイレクトはカウンターの値と現在の階数だけで決まり、時刻や乱数といった外部の要素は用いないものとする。 あなたはモンスターから渡されたパラメータによってカウンターをインクリメントするかしないかし、その階に向かう。 0階に降りるまでこれを繰り返す。 注意: ヘリコプターで乱入した階数をα、カウンターの初期値をnとすると、0階に降りたときのカウンターの値はαとnの関数として表される。この関数をこの記事だけの用語としてこの'''塔に付随する巨大関数'''と呼ぶことにする。第1引数がαで第2引数がnである。 ===具体例=== 強さの序列だけではなく、モンスターのリダイレクトも定義しなければならない。 ====つまらない例==== 上に行くほど強くなる無限の塔を考える。 すなわち、強さの序列が0階<1階<2階<・・・と無限に続いていく。 a階のモンスターはa-1階にリダイレクトするものとする。(a>=1) また、インクリメントパラメータは常にtrueであるものとする。 このとき、この塔に付随する巨大関数はf(α,n)=α+nである。このことはαに関する数学的帰納法で示せる。せっかくなので証明しておこう。 =====証明===== (i) α=0のとき: f(0,n)は定義から明らかにnである。0+nは(足し算の定義から示そうとすると)そこまで自明ではないがnである。よって両辺は等しい。 (ii) α=kのときの成立を仮定してα=k+1のとき(k>=0): カウンターがnの状態でk+1階のモンスターを倒すとカウンターがn+1になってk階にリダイレクトされる。よってf(k+1,n)=f(k,n+1)=k+(n+1)である。いっぽう(k+1)+nも足し算の定義からk+(n+1)であるから、両辺は等しい。 (i)(ii)より、f(α,n)=α+nが示された。 ====多少は面白い例==== 偶数階・奇数階ごとに上に行くほど強くなる無限の塔を考える。また、奇数階は上級者向けであり、奇数階のどのモンスターも偶数階の全てのモンスターを一撃で倒せるものとする。 このときの強さの序列は0階<2階<4階<・・・<1階<3階<5階<・・・となり、無限をさらに超えて続いていく。 a階のモンスターのリダイレクト規則が以下であるとする (a>=1):# もしa≠1なら、a-2階にリダイレクトする。# もしa=1なら、カウンターの値を取得し、それを2倍した数の階にリダイレクトする。 また、インクリメントパラメータはa≠1と同値(i.e. a=1のときfalse、a≠1のときtrue)であるものとする。 リダイレクトした先の方が弱いことは明らかである。 このとき、この塔に付随する巨大関数はf(α,n)=α/2+n (αが偶数のとき)、α-1+2n (αが奇数のとき)である。 当然強いモンスターがいる階から始めるほど関数は大きくなる。αが奇数のときはnの係数に2が付いているが、これはこの塔の構造から来る本質的なものである。 ====もっと面白い例==== 塔を偶奇ではなく3で割った余りで分割し、階数を3で割った余りが0なら初心者向け、1なら上級者向け、2ならエンドコンテンツ、という仕様にする。 強さの序列は0階<3階<6階<・・・<1階<4階<7階<・・・<2階<5階<8階<・・・となり、無限の階層が3個積み重なっている。 a階のモンスターのリダイレクト規則が以下であるとする (a>=1):# もしa≠1,2なら、a-3階にリダイレクトする。# もしa=1なら、カウンターの値を取得し、それを3倍した数の階にリダイレクトする。# もしa=2なら、カウンターの値を取得し、それを3倍して1を足した数の階にリダイレクトする。 また、インクリメントパラメータはa≠1,2と同値であるものとする。 このとき、この塔に付随する巨大関数f(α,n)は以下の通りである。* α/3+n (αが3の倍数のとき)* 2((α-1)/3+n) (αが3で割って1余るとき)* 4((α-2)/3+n) (αが3で割って2余るとき) αが3で割って2余るとき、αを定数とみるとこの関数は4n+(定数)となる。係数の4はこの塔の構造から来る本質的なものである。 一般に、無限の階層がk個積み重なっているとき、nの最大の係数は2^(k-1)となる。 もっと複雑な構造を用意すればもっと大きな関数も生み出せるが、自然数だけでは説明が面倒なのでシンタックスシュガーを導入する。 ===シンタックスシュガー=== 自然数だとこの後の議論が面倒なので、塔の階数は適当なエンコーディングでデコードされた文字列で表示されているものとする。文字列として不適当なバイナリデータ(UTF-8エンコーディングにおける11000000 11000000など)に対応する解には、最弱のモンスターを置いておく。文字列として不適当な階数には今後の議論で行くことはないので、これはさほど問題ではない。 特に断りのない限り、文字列のエンコーディングはUTF-8とする。 ====シンタックスシュガーを用いた例==== 強さの序列は「文字列の先頭のSの個数」で決まるものとする。 a階のモンスターのリダイレクト規則が以下であるとする (aは任意の文字列):# もしa="S"+bと書けるなら、b階にリダイレクトする。ただし、+は文字列の連結である。# もしa="0"なら、0階にリダイレクトする。# 上記のどちらでもないなら、0階にリダイレクトする。 a階のモンスターのインクリメントパラメータが以下であるとする (aは任意の文字列):# もしa="S"+bと書けるなら、trueである。ただし、+は文字列の連結である。# もしa="0"なら、falseである。# 上記のどちらでもないなら、falseである。 下2つのケースはまとめられそうだが、2.は正常系の境界値、3.は異常系というお気持ちがあるため別にしている。 このとき、この塔に付随する巨大関数f(α,n)はf(α,n)=n+(αの先頭に並ぶSの数)である。 これ自体は大きくないが、文字列を使うことでさらに複雑な構造(特に1次関数を超える場合)が直感的に書けるというメリットがある。  この塔をシンタックスシュガーを用いずに定義する場合は、次のように書ける。 a階のモンスターのリダイレクト規則が以下であるとする (aは正の自然数):# もしa=83×256^n+bと書けるなら、b階にリダイレクトする。ただし、nは0以上の自然数、bはb<256^nを満たす自然数である。# もしa=48なら、0階にリダイレクトする。# 上記のどちらでもないなら、0階にリダイレクトする。 a階のモンスターのインクリメントパラメータが以下であるとする (aは任意の文字列):# もしa=83×256^n+bと書けるなら、trueである。ただし、nは0以上の自然数、bはb<256^nを満たす自然数である。# もしa=48なら、falseである。# 上記のどちらでもないなら、falseである。 ====シンタックスシュガーを用いた別の例==== XとYからなる長さ1以上の文字列を正常系とみなし、それ以外は異常系とみなす。異常系は0階にリダイレクトしインクリメントパラメータはfalseであるとし、以下では正常系の挙動のみを扱う。 a階のモンスターのリダイレクト規則が以下であるとする (aは正常系の文字列):# もしa=b+Xと書けるなら、b階にリダイレクトする。ただし、+は文字列の連結であり、bは空文字列ではない。# もしa=b+Yと書けるなら、b+X+...+X階にリダイレクトする。ただし、## bは空文字列でもよい。## +は文字列の連結である。## Xはカウンターの値の個数だけ存在する。# もしa=Xなら、0階にリダイレクトする。 a階のモンスターのインクリメントパラメータが以下であるとする (aは正常系の文字列):# もしa=b+Xと書けるなら、trueである。ただし、+は文字列の連結であり、bは空文字列ではない。# もしa=b+Yと書けるなら、falseである。ただし、+は文字列の連結であり、bは空文字列でもよい。# もしa=Xなら、trueである。 最初に入った階にYが多いほど最終的なカウンター値が増加し、その値はカウンターの初期値をnとすると、n×2^(Yの個数)で近似される。 さらに、異常系である1階を正常系とし、「カウンターの値と同じ個数のY」階にリダイレクトし、そのときのインクリメントパラメータをfalseとすれば、Yの個数がカウンターの値によって変化するため2の指数にnを入れることができ、指数関数レベルの巨大数を生み出すことができる。 ==第2章-甲 無限== 非常にわかりやすい動画(この記事と微妙に説明が違う上合計で1時間以上あるので注意): [https://t.co/Ck3Z9ecACp 前編] [https://t.co/Lk6wJEr8rQ 後編] これらの塔の構造は、順序数と呼ばれる種類の無限を用いて表現される。 この順序数が、巨大数における《無限の世界》の住人である。 ===第1節 順序数=== 厳密な定義は非常に難しいため、かなり簡略化して説明する。'''この説明は正確ではないことに注意せよ。''' 順序数は、塔の中でモンスターの強さの序列を数として表したものである。例えば、第0章の「つまらない例」の場合は、0階<1階<2階<・・・という強さの序列があるが、これはそのまま0<1<2<・・・という自然数の大小関係に対応する。 「多少は面白い例」の序列は、0階<2階<4階<・・・<1階<3階<5階<・・・であった。偶数階は0<1<2<・・・という普通の自然数に対応するが、1階のモンスターには0,1,2,・・・の全てより大きい順序数が与えられる。この順序数にはωという記号が与えられている。すなわち、0<ω,1<ω,2<ω,・・・の全てが成り立つ。 残りの奇数階のモンスターにはωよりさらに大きい順序数が与えられる。すなわち、ω+1,ω+2,・・・とωの先に無限に続いていく。 すなわち、「多少は面白い例」の序列を順序数で表すと0<1<2<・・・<ω<ω+1<ω+2<・・・となる。 さらに複雑な構造の塔にはもっと大きな順序数が対応する。順序数は、以下のように並ぶ: 0<1<2<・・・<ω<ω+1<ω+2<・・・<ω×2<ω×2+1<・・・<ω×3<・・・・・・<ω^2<ω^2+1<・・・<ω^2+ω<・・・・・・<ω^2×2<・・・・・・<ω^3<・・・・・・・・・・ もちろんω^3より大きな順序数もたくさんある。 ===第3節 塔の強さ=== 塔自体の強さも順序数で表すことができる。すなわち、塔自体の強さは「その塔にいるどのモンスターよりも強い」と考える。 例えば、「つまらない例」の塔の強さはωであり、「多少は面白い例」の塔の強さはω+1,ω+2,・・・のどれよりも大きい順序数ω+ω=ω×2である。 第1章の最後に紹介した「シンタックスシュガーを用いた別の例」の塔の強さは、ω^2に達する。 ==第2章-乙 ハーディー階層== 順序数にはデフォルトで大小関係が入っているため、これを強さの序列とみなし、それぞれに適当な自然数へのエンコーディングを与えることにより、塔にモンスターの代わりに順序数を配置することができる。 順序数を塔に配置した場合は、インクリメントパラメータは「その順序数がα+1と表されるときtrue、そうでないときfalse」とするのが一般的である。 残りはリダイレクト規則だけであるが、このリダイレクト規則を適切に定めるのが非常に難しい。 ここまでのアイデアを数式にしたのがハーディー階層\( H \)である。 \( \alpha \)を順序数、\( n \)を自然数とする。 * \( \alpha = 0 \)のとき: \( H_0(n) = n \)* \( \alpha = \beta + 1 \)と書けるとき: \( H_{\alpha}(n) = H_{\beta}(n + 1) \)* それ以外のとき: \( H_{\alpha}(n) = H_{\alpha[n]}(n) \) \( \alpha[n] \)という記号は後述する基本列という概念を表す記号である。 \( H_{\alpha}(n) \)は、「カウンターが\( n \)のときに順序数\( \alpha \)のいる階に着いた」ことを表す。また、順序数\( 0 \)は受付の人間に対応する。 ===第1節 基本列=== \( n \)をカウンターの値とする。 基本列とはいい感じのリダイレクト規則である。 例えば、ω×2のリダイレクト規則として\( n \)を採用した場合、\( n \)がいくら大きくてもω以上の順序数に行くことはなく、ω2の強さが「生かし切れていない」といえる。 一方、ω×2のリダイレクト規則として\( \omega + n \)を採用した場合、ω×2以下のどんな順序数に対しても、\( n \)を大きくすればそれより大きな順序数に行く。 このように、「強さを生かし切れたリダイレクト規則」を基本列と呼ぶ。 順序数の表現(正確にはカントール標準形というものである)が・・・+ω^aであるとき、その基本列は・・・+ω^(a-1)×nとすることが多い(正確にはワイナー階層というものである)。ただし、ω^0=1、ω^1=ωである。 ===第2節 具体例=== \( \begin{align*}& H_3(5) \\=& H_2(6) (\because 3 = 2 + 1)\\=& H_1(7) (\because 2 = 1 + 1)\\=& H_0(8) (\because 1 = 0 + 1)\\=& 8\end{align*} \)  \( \begin{align*}& H_{\omega}(5) \\=& H_5(5) (\because \omega = \omega^1, \omega^0 \times 5 = 1 \times 5 = 5)\\=& H_4(6) \\=& \cdots \\=& 10\end{align*} \)  \( \begin{align*}& H_{\omega \times 2}(3) \\=& H_{\omega + 3}(3) (\because \omega \times 2 = \omega + \omega)\\=& H_{\omega + 2}(4) \\=& H_{\omega + 1}(5) \\=& H_{\omega}(6) \\=& H_6(6) \\=& H_5(7) \\=& \cdots \\=& 12\end{align*} \)  \( \begin{align*}& H_{\omega^2}(3) \\=& H_{\omega \times 3}(3) \\=& H_{\omega \times 2 + 3}(3) \\=& H_{\omega \times 2 + 2}(4) \\=& H_{\omega \times 2 + 1}(5) \\=& H_{\omega \times 2}(6) \\=& H_{\omega + 6}(6) \\=& \cdots \\=& H_{\omega}(12) \\=& H_{12}(12) \\=& \cdots \\=& 24\end{align*} \) ==第2章-丙 カントール標準形== ここでは、\( \varepsilon_0 \)までの順序数について解説する。 これは直感的な説明であることに注意すること。 === 第1節 \( \omega^{\omega} \)まで===* \( 1, 2, 3, \cdots \)と進んだ先には\( \omega \)がある。* \( \omega \)から再び\( \omega+1, \omega+2, \omega+3, \cdots \)と進み、\( \omega \times 2 \)に到達する。* 「無限に数える」という操作を繰り返すことで、\( \omega, \omega \times 2, \omega \times 3 \cdots \)という階層を辿ることができる。これを無限回繰り返して、\( \omega^2 \)となる。* \( \omega^2 \)からまた無限に数えると、\( \omega^2 + \omega \)である。* \( \omega^2 \)から\( \omega^2 \)の構造をもう一度数えることで、\( \omega^2 \times 2 \)となる。* \( \omega^2 \)の構造を無限に数えることで、\( \omega^3 \)となる。* \( \omega^3 \)の構造を無限に数えることで、\( \omega^4 \)となる。* \( \omega^n \)の構造を無限に積み上げて、\( \omega^{\omega} \)となる。 \( \omega^{\omega} \)未満の順序数は\( \omega \)の「多項式」のように表される。すなわち、 \( \omega^4 + \omega^3 \times 6 + \omega \times 2 + 3 \) のような形で表される。この表し方が、カントール標準形の\( \omega^{\omega} \)未満の部分である。\( \omega^{\omega} \)以上の部分については後述する。 === 第2節 大きな順序数=== * \( \omega^{\omega} \)の次の順序数は\( \omega^{\omega} + 1 \)である。* \( \omega^{\omega} \)から無限に数えた先が\( \omega^{\omega} + \omega \)である。* \( \omega^{\omega} \)からさらに\( \omega^{\omega} \)まで数えると\( \omega^{\omega} \times 2 \)である。* \( \omega^{\omega} \)を無限回重ねると\( \omega^{\omega+1} \)である。* \( \omega^{\omega+1} \)を無限回重ねると\( \omega^{\omega+2} \)である。* 「無限回重ねる」という操作を無限回重ねると\( \omega^{\omega \times 2} \)である。 ・・・・・・・・・ * 指数をどんどん増やしていって、えげつない無限の操作の先にあるのが\( \omega^{\omega^{\omega}} \)である。 さらに無限の階層を登って、\( \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}} \)と無限の指数タワーの先にあるのが\( \varepsilon_0 \)である。 ===第3節 ヒドラゲーム=== \( \varepsilon_0 \)は非常に大きな順序数であるため、そのまま扱うのは分かりにくい。そのため、visualizationが用意されている。 ==第3章 非可算順序数== [ここにOCFを挿入] ==第4章 巨大基数== [ここにやばいやつを挿入][待った、本気でここまでやるつもりなのか?]