巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

超越整数の拡張関数は巨大数研究 Wikiユーザー ふぃっしゅが作った計算可能巨大関数の族であり、\(\textrm{TR}\) と表記する。[1] これは超越整数の定義から自然に生じる計算可能関数の拡張である。

定義

\(T\) を算術の固定された埋め込みを持つ形式理論、および \(n\) を自然数とする。このとき \(\textrm{TR}(T,n)\) は以下のような最小の自然数 \(N\) として定義される: 任意のチューリング機械 \(M\) について、\(M\) の停止を \(T\) において \(n\) 記号以内で証明可能ならば、\(M\) は実際に \(N\) ステップ以内に停止する。


解説

\(\textrm{ZFC}\) 集合論のようなベース理論で作業し、\(T\) をベース理論内で符号化された形式理論と考える。ベース理論のチューリング機械 \(M\) ごとに、\(M\) を算術で符号化する既知の方法が存在するので、 \(T\) にも存在する。したがって \(M\) の \(T\) における停止は自然に意味をなす。この方法で、\(\textrm{TR}\) 関数は算術の固定された埋め込みを持つ形式理論 \(T\) ごとに \(n\) の部分関数を生成する。特に \(T\) が再帰的理論である時、その部分関数は計算可能である。

この関数 \(\textrm{TR}\) 自体は全域的ではない。なぜならば矛盾した形式理論が存在するからである。たとえば、ベース理論は無矛盾で、\(T\) は\(\textrm{PA}\)に反証可能な論理式 \(0 = S0\) を加えた理論で、\(M\) は停止しないと仮定する。爆発律により、\(M\) の停止は \(T\) で証明可能である。\(n\) が \(M\) の停止の \(T\) における最短の証明の記号数以上ならば、\(M\) が \(N\) ステップ以内に停止するような自然数 \(N\) は存在しない。なぜならば \(M\) は停止しないからである。したがってこの場合 \(\textrm{TR}(T,n)\) はill-definedである。

以下、定数記号も関数記号も関係記号も有限個しか持たないような \(T\) に絞って考え、\(T\) の変数記号を \(x_0, x_1, \ldots\) と番号付ける。任意の \(n\) に対し \(T\) での \(n\) 記号以下の証明全体の集合を \(P_n\) と置く。変数の置き換えは \(P_n\) の同値関係 \(\sim_n\) を定め、添字が \(n\) 未満の変数記号しか現れない証明全体のなす部分集合を \(P'_n \subset P_n\) と置くと \(P_n\) に属する任意の証明は \(P'_n\) に属するある証明と \(\sim_n\) に関して同値である。定数記号と関数記号と関係記号の有限性の仮定より\(P'_n\) は有限集合であることと合わせ、\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) は有限個しか存在しない。これにより、\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) がもし必ず停止するならば、それらの停止ステップ数全体の集合は有限集合となるため確かに上限 \(N\) を持ち、\(\textrm{TR}(T,n)\) が定義される。ここで「\(T\) において \(n\) 記号以下で停止性が証明可能なチューリング機械 \(M\) がもし必ず停止する」という仮定を置いたがこれは必ずしも成り立たないことに注意する。

たとえベース理論で \(\textrm{Con}(T)\) が成り立つという意味で \(T\) が無矛盾だったとしても、停止しないチューリング機械の停止が \(T\) において証明されるかもしれない。たとえば、ベース理論が \(\textrm{ZFC}\) で \(T\) が \(\textrm{PA} + \neg \textrm{Con}(\textrm{PA})\) ならば、\(T\) は無矛盾だが \(\textrm{TR}(T,n)\) は十分に大きな \(n \in \mathbb{N}\) に対して ill-defined である。なぜならばあるチューリング機械が存在し、その停止は \(\neg \textrm{Con}(\textrm{PA})\) と同値であり、\(\neg \textrm{Con}(\textrm{PA})\) は \(T\) で証明可能だがベース理論で反証可能だからである。

任意の \(n\) に対する \(\textrm{TR}(T,n)\) のwell-defined性を保証するには、\(T\) のベース理論における \(\Sigma_1\)-健全性と呼ばれる強い仮定が必要である。\(\textrm{TR}(T,n)\) を特定の \(n\)、たとえば \(2^{1000}\) に対して定義したいだけならば、より弱い以下の仮定だけで十分である: 任意のチューリング機械 \(M\) について、\(M\) の停止が \(T\) において \(n\) 記号以内で証明可能ならば、\(M\) は実際に停止する。

たとえば、\(T\) が \(\textrm{ZFC}\) 集合論ならば、\(\textrm{TR}(T,n)\) はベース理論における \(\textrm{ZFC}\) 集合論の \(\Sigma_1\)-健全性の仮定のもとで全域であり、\(\textrm{TR}(T,2^{1000})\) は最小の超越整数と一致する。これが \(\textrm{TR}\) を超越整数の拡張関数と呼ぶ理由である。


特殊化

ふぃっしゅは\(\textrm{I}0\) 関数と呼ばれる特定の関数を \(\textrm{TR}(\textrm{ZFC}+\textrm{I}0,n)\) として作った。ここで、\(\textrm{I}0\) は非常に強い巨大基数公理である階層内階層基数の存在公理を表す。Friedmanは特定の超越整数を作っていないので、ふぃっしゅも \(\textrm{I}0\) 関数の値を作っていない。


解析

定義により、\(\textrm{TR}(T,n)\) は \(T\) で可証全域ないかなる計算可能関数よりも速く増加する。これは、もし与えられた計算可能全域関数が「全域であると知られている」ならば、ある特定の \(T\) の選択に対して \(\textrm{TR}(T,n)\) によって抑えられることを含意する。たとえば、ほとんどすべての既知の全域計算可能関数は \(\textrm{I}0\) 関数によって抑えられる。

これが超越整数の概念の素朴な拡張であるかどうかには議論の余地があるが、ふぃっしゅが指摘したように強い理論がさらに強い理論において直接より大きな数をもたらすことの明示的な説明を与えていることは重要である。したがって \(\textrm{ZFC}\) 集合論より強い理論で作業するならばベース理論を固定して明示しておくのが合理的である。さもなければ、任意の全域計算可能関数は上記の意味で \(\textrm{TR}\) 関数よりも弱くなってしまう。

特定の \(T\) を伴う \(\textrm{TR}(T,n)\) 関数のようなものは、急増加関数において \(\textrm{PTO}(T)\)、すなわち \(T\) の証明論的順序数に「近似」されることがあるが、この「近似」には意味がない。なぜならば急増加関数は順序数に対してではなく、順序数と基本列系の組に対して well-defined だからである。より小さな順序数と異なり、\(\textrm{PTO}(T)\) は固定された基本列系を持たないので、比較に意味はない。急増加関数は基本列系の選択に強く依存するので、基本列系を固定することができたとしても、比較は極めて疑わしい。


出典

  1. Fish, 超越整数の拡張関数TR, 巨大数論 p.230, 2013.

参照

日本の巨大数論

Aeton: おこじょ数N成長階層
mrna: 段階配列表記降下段階配列表記多変数段階配列表記横ネスト段階配列表記
Kanrokoti: くまくまψ関数亜原始ψ関数ハイパー原始ψ関数TSS-ψ関数
クロちゃん: 第一クロちゃん数第二クロちゃん数第三クロちゃん数第四クロちゃん数
たろう: 多変数アッカーマン関数2重リストアッカーマン関数多重リストアッカーマン関数
Nayuta Ito: フラン数N原始東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数ペア数列数バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー恋符マスタースパーク数みくみく順序数
108Hassium: E2:B-01-HsE3:B-02-Hs
公太郎: 弱亜ペア数列肉ヒドラ数列弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記拡張ブーフホルツのψ関数に伴う順序数表記四関数三関数巨大数庭園数
ふぃっしゅ: ふぃっしゅ数バージョン1バージョン2バージョン3バージョン4バージョン5バージョン6バージョン7マシモ関数マシモスケールTR関数I0関数
ゆきと: 亜原始数列ハイパー原始数列Y数列
本: 巨大数論寿司虚空編
大会: 東方巨大数幻想巨大数即席巨大数式神巨大数
掲示板: 巨大数探索スレッド名もなき巨大数研究
外部リンク: 日本語の巨大数関連サイト

Advertisement