利用者:Nayuta Ito/巨大数における有限と無限

この記事では、巨大数における有限と無限について解説する。

前提知識

• 知らないと厳しい: 数学的帰納法
• 知ってると便利: ペアノの公理
• 知ってると便利: 公理的集合論

第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):

1. もしa≠1なら、a-2階にリダイレクトする。
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):

1. もしa≠1,2なら、a-3階にリダイレクトする。
2. もしa=1なら、カウンターの値を取得し、それを3倍した数の階にリダイレクトする。
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)となる。

もっと複雑な構造を用意すればnの2次以上の式も生み出せるが、自然数だけでは説明が面倒なのでシンタックスシュガーを導入する。

シンタックスシュガー

自然数だとこの後の議論が面倒なので、塔の階数は適当なエンコーディングでデコードされた文字列で表示されているものとする。文字列として不適当なバイナリデータ(UTF-8エンコーディングにおける11000000 11000000など)に対応する解には、最弱のモンスターを置いておく。文字列として不適当な階数には今後の議論で行くことはないので、これはさほど問題ではない。

特に断りのない限り、文字列のエンコーディングはUTF-8とする。

シンタックスシュガーを用いた例

強さの序列は「文字列の先頭のSの個数」で決まるものとする。

a階のモンスターのリダイレクト規則が以下であるとする (aは任意の文字列):

1. もしa="S"+bと書けるなら、b階にリダイレクトする。ただし、+は文字列の連結である。
2. もしa="0"なら、0階にリダイレクトする。
3. 上記のどちらでもないなら、0階にリダイレクトする。

a階のモンスターのインクリメントパラメータが以下であるとする (aは任意の文字列):

1. もしa="S"+bと書けるなら、trueである。ただし、+は文字列の連結である。
2. もしa="0"なら、falseである。
3. 上記のどちらでもないなら、falseである。

下2つのケースはまとめられそうだが、2.は正常系の境界値、3.は異常系というお気持ちがあるため別にしている。

このとき、この塔に付随する巨大関数f(α,n)はf(α,n)=n+(αの先頭に並ぶSの数)である。

これ自体は大きくないが、文字列を使うことでさらに複雑な構造(特にnの2次以上の項を伴う場合)が直感的に書けるというメリットがある。

この塔をシンタックスシュガーを用いずに定義する場合は、次のように書ける。

a階のモンスターのリダイレクト規則が以下であるとする (aは正の自然数):

1. もしa=83×256^n+bと書けるなら、b階にリダイレクトする。ただし、nは0以上の自然数、bはb<256^nを満たす自然数である。
2. もしa=48なら、0階にリダイレクトする。
3. 上記のどちらでもないなら、0階にリダイレクトする。

a階のモンスターのインクリメントパラメータが以下であるとする (aは任意の文字列):

1. もしa=83×256^n+bと書けるなら、trueである。ただし、nは0以上の自然数、bはb<256^nを満たす自然数である。
2. もしa=48なら、falseである。
3. 上記のどちらでもないなら、falseである。

第2章 無限

[ここに順序数の話を挿入]

第3章 非可算順序数

[ここにOCFを挿入]

第4章 巨大基数

[ここにやばいやつを挿入]