これはen:User_blog:P進大好きbot/List_of_common_mistakes_in_googologyの和訳です。


同じ説明の繰り返しを避けるため、巨大数論に現れるよくある間違いやそれに関する質問をまとめます。


目次

はじめに

なぜ∞を巨大数とみなせないのですか?

有限の数を定義することが、巨大数論における共通ルールだからです。∞をあなたの数として発表してもよいですが、このルールに従っている人たちはほとんど注目しないでしょう。


なぜ全てを定義しないといけないのですか?

定義の完成していない数の大小に意味がないからです。定義を固定せずにあなたの数を発表してもよいですが、それが既存の定義された数より大きいか否か、例えば1より大きいか否かを問うことは無意味となります。


なぜ巨大数論における数学概念は難しく見えるのですか?

それらが実際に難しいからです。あなたがどこかのウェブページで素晴らしく単純明快な解説を目にすることがあるかもしれませんが、それらはたいてい間違った説明をしています。なぜでしょう? それは単に、「明快すぎる」解説を書いている人がその対象を理解していない初学者であることが多いからです。厳密な定義を理解できなかった初学者は、そういった「明快すぎる」解説を探し求め、それらを素晴らしい解説と思い込んで鵜呑みにしてしまう傾向があります。その後、誤った解説を学んだ初学者は自分が十分に理解できたと錯覚し、自分のウェブサイトに新たな誤った解説を書き始めてしまいます。このように、正しい事実に基づかない記事が世界中に量産されていくのです。

特に、グラハム数と順序数とFGHとOCFと順序数表記と \(\textrm{TREE}\) と \(\omega_1^{\textrm{CK}}\) に関する多くの説明は間違っています。私(訳注: p進大好きbot)の知る限り、このwiki(訳注: 英語版gwiki)でさえ多くの記事が間違っていました。そのため「僕の主張は明らかに正しい! だってwikiにそう書いてあるから!」などといった主張には意味がありません。

人々が巨大数論において難しい数学概念を使う際に、その定義をまだ知らないということが頻繁に起こります。そういう状況では、他者から指摘される誤りを理解することさえできないことに起因して、同じ誤りを繰り返し続ける傾向があります。彼らはウェブサイトに載っている誤った解説に基づく直感をただ頼りにし、正しい解説を無視してしまうのです。結果として、「数学的体系で定義可能な順序数表記で\(1000000000\)文字以下で定義できる最大の順序数\(\alpha\)を用いて\(f_{\psi_0(\omega_α^{\textrm{CK}})}(G_{\textrm{TREE}})\)と定める」といったような意味のないものを生み出し、誤りの指摘を全て無視することになるのです。そのような事態を避けるため、自分が理解しているものだけを誠実に使うと良いです。何のことだかさっぱり分かっていない難しい概念をあたかも知っているかのように振る舞う必要はないのです。


形式理論

なぜ形式論理が巨大数論で重要なのですか?

なぜならば議論を正確なやり方で行う助けになるからです。たとえば、「私の巨大数 \(N \in \mathbb{N}\) は \(10^{100}\) 文字以下で定義可能な自然数だ! I win!」 のようなベリーのパラドックスや、類似の素朴で直感的な説明を却下できるようになります。


数学における「定義」とはどういう意味ですか?

一階述語論理における項(たとえば巨大数)の定義とは、単に 自由変数 \(x\) を持つ論理式 \(D\) で、 \(\exists ! x(D)\) が作業中の公理系のもとで証明可能であるようなものです。これは[Kun][1]の8節と13節で説明されている定義の定式化の1つに過ぎません。しかし他の定式化も本質的にはこれと同値です。とくに、自明でない項を公理なしで定義することは、一階述語論理以外の強力な形式系で作業していない限り、決してできません。

あなたは「私の巨大数 \(N \in \mathbb{N}\) は \(10^{100}\) 文字以下の \(\textrm{FOST}\) の論理式で定義可能な最大のものだ! I win!」と言うかもしれません。しかしこれは \(\textrm{FOST}\) で書かれたいかなる理論でも有効な定義ではありません。\(\textrm{FOST}\)の文字による定義可能性がどの公理系に基づいているかと、 \(N\) を実際に定義可能なメタ理論を宣言して指定する必要があります。メタ理論についての詳しい説明はここを参照してください。

さらに、あなたは集合論のモデル \(M\) に相対化された巨大数を論理式で命名することができます。自由変数 \(x\) を持つ集合論の論理式 \(D\) は、\(M \models \exists ! x((x \in \mathbb{N}) \wedge D)\) ならば、\(M\) に相対化された自然数を命名します。\(M\) に相対化された自然数とは、単に \(n \in^M \mathbb{N}^M\) を充足する \(M\) の元 \(n\) にすぎず、したがって自然数、すなわち \(\mathbb{N}\) の元であるとは限らないことに注意してください。ここで \(\in^M\) と \(\mathbb{N}^M\) は、それぞれ \(\in\) と \(\mathbb{N}\) の \(M\) における解釈を表します。モデルについて詳しくは、ここの説明をを参照してください。


巨大数の計算可能性とはどういう意味ですか?

巨大数の計算可能性は数学で定義されておらず、通常完全な定義なしで参照されています。たとえば、計算可能巨大数とは計算可能巨大関数に計算可能巨大数を入力として与えたときの出力を意味すると言われることがありますが、この基準ではうまくいきません。なぜならばすべての自然数は定数写像の出力であり、定数写像は定義により計算可能だからです。代わりに、「計算可能自然数の定義式」の概念の定義の候補を与えます。

  1. 論理式 \(n = 0\) は計算可能自然数 \(n\) の定義式である。
  2. 論理式 \(n = 1\) は計算可能自然数 \(n\) の定義式である。
  3. 論理式 \(n = 2\) は計算可能自然数 \(n\) の定義式である。
  4. 論理式 \(n = 3\) は計算可能自然数 \(n\) の定義式である。
  5. 論理式 \(n = 4\) は計算可能自然数 \(n\) の定義式である。
  6. 論理式 \(n = 5\) は計算可能自然数 \(n\) の定義式である。
  7. 論理式 \(n = 6\) は計算可能自然数 \(n\) の定義式である。
  8. 論理式 \(n = 7\) は計算可能自然数 \(n\) の定義式である。
  9. 論理式 \(n = 8\) は計算可能自然数 \(n\) の定義式である。
  10. 論理式 \(n = 9\) は計算可能自然数 \(n\) の定義式である。
  11. 論理式 \(n = 10\) は計算可能自然数 \(n\) の定義式である。
  12. 任意の計算可能自然数 \(x\) の定義式 \(F(x)\) に対して、「任意の \(x \in \mathbb{N}\) に対して、\(F(x)\) は \(f\) が \(x\) で符号化された計算可能関数であることを含意する」として与えられる論理式 \(\textrm{Code}(F)(f)\) は計算可能関数 \(f\) の定義式である(ここで、計算可能関数から自然数への符号化を固定する)。
  13. 任意の計算可能関数 \(f\) の定義式 \(F(f)\) および任意の計算可能自然数 \(x\) の定義式 \(G(x)\) に対して、論理式 \(\forall f(\forall x((F(f) \land G(x)) \to (n = F(x))))\) は計算可能自然数の定義式である。

自然数 \(n\) の整形式の式 \(E\) は自然に \(n\) の定義式 \(F(n)\) を与えるので、\(E\) の計算可能巨大数論における妥当性を \(F(n)\) は計算可能自然数の定義式であるという文によって定義できます。

たとえば、計算不可能関数 \(f\) に伴う式 \(f(0)\) は、計算可能自然数 \(n\) の 定義式 \(F(n)\) で、論理式 \(F(f(0))\) が \(\textrm{ZFC}\) 集合論で証明可能であるようなものが存在するかもしれませんが、ここで定義した意味で妥当な計算可能巨大数ではありません。(たとえば、\(\textrm{BB}(0)\) や \(\textrm{Rayo}(0)\) を考えてください。この wiki におけるほとんどすべての「計算可能巨大数」は計算可能自然数の定義式によって定義されているので、この定式化はそう悪くないと思います。


すべての無矛盾な一階の理論は不完全ですか?

いいえ。 不完全性定理の条件を注意深く読んでください。たとえば、 実閉体の理論\(\textrm{RCF}\) がその条件を満たさないことはよく知られています。残念ながら、不完全性定理と完全性定理はよく混同されます。

さらに、不完全ではなく無矛盾な一階の理論が存在します。固定された形式言語で書かれた無矛盾な公理系の集合を \(\Sigma\) で表します。このときツォルンの補題により、\(\Sigma\) の包含関係に関する極大元 \(A\) が存在します。もし \(A\) から独立な閉論理式 \(F\) が存在したら、\(A \cup \{F\}\) は無矛盾です。これは \(A\) の極大性に矛盾します。よって \(A\) は不完全ではありません。

二階の理論は一階の理論より強いですか?

場合によります。 これは強さの意味や、考えている理論に依存します。

  • 二階論理は一階論理の一般化である。(この意味では強い?)
  • すべての二階の理論は形式言語で記述され、形式言語は一階の理論の項である。(この意味では弱い?)
  • 超準モデルの存在のため、自然数の標準モデルの構造を一階算術 \(\textrm{PA}\) で特徴づけることはできないが、算術の二階述語論理の標準意味論により特徴づけることはできる。(この意味では強い?)
  • 一階算術 \(\textrm{PA}\) の特定のモデル \(N\) に相対化された、メタ理論から導出される \(N\) への相対化であるいかなる自然数よりも大きい自然数 \(\infty\) を使うことはできるが、二階の解釈の場合はできない。(この意味では弱い?)
  • もし二階の変数が公理図式の記述にのみ現れる公理を持つ二階集合論で一階の論理式が証明可能ならば、\(2\)-ソート一階集合論でも証明可能である。(この意味では弱い?)
  • \(2\)-ソート一階集合論 \(\textrm{NBG}\) と \(\textrm{MK}\) の二階の解釈の無矛盾性は、一階集合論 \(\textrm{ZFC} + \textrm{Inaccessible}\)のもとで証明可能である。(この意味では弱い?)
  • 一階算術 \(\textrm{PA}\) の無矛盾性は二階算術 \(\textrm{ACA}_0 + \textrm{Con}(\textrm{PA})\) のもとで証明可能である。(この意味では強い?)
  • 二階算術 \(\textrm{ACA}_0\) の無矛盾性は一階算術 \(\textrm{PA} + \textrm{Con}(\textrm{ACA}_0)\) のもとで証明可能である。(この意味では弱い?)
  • 一階算術 \(\textrm{PA}\) の証明論的順序数はその二階化 \(\mathsf{ACA}_0\)の証明論的順序数と等しい。 (この意味では同等?)
  • 一階算術 \(\textrm{PA}\) の証明論的順序数はその定義に用いる二階の公理図式を追加した二階算術の証明論的順序数と定義から等しい。 (この意味では同等?)
  • 一階算術 \(\textrm{PA}\) の証明論的順序数は同じ公理を持つ二階算術の証明論的順序数より大きい。 (この意味では弱い?)

したがって、正確な意味を宣言する必要があります。同じ問題は高階の理論を参照するときにも発生します。

メタ理論

メタ理論とはなんですか?

おおざっぱに言うと、メタ理論とはその中で与えられた理論が定義される理論を意味します。もっと正確な説明が必要でしょう。

\(T\) を \(\textrm{ZFC}\) 集合論のような集合論、\(L\) を \(T\) で定義された形式言語、そして \(A\) を \(L\) で記述された公理の集合であるとします。たとえば、\((L,A)\) は形式言語と群論の公理の対、もしくは形式言語 \(\textrm{FOST}\) と \(\textrm{FOST}\) で書かれた \(\textrm{ZFC}\) の公理の対です。このとき、\(T\) を \((L,A)\) によって記述される符号化された理論のメタ理論と呼びます。\((L,A)\) 上のメタ理論的命題は \(T\) の論理式として述べることができます。たとえば、\(A\) における \(L\) の論理式の証明可能性は \(T\) の論理式です。

いま \(T\) が集合論の場合に限定しましたが、ペア関数とゲーデル対応を使って、符号化された理論を算術の中に定義することもできます。このときは算術を符号化された理論のメタ理論と呼びます。

もちろん、\(T\) 自身も別の理論内に符号化された理論、すなわち \(T\) のメタメタ理論 \(MT\) かもしれません。さもなければ、\(T\) は純粋に構文論的に列を比較する素朴な有限の記号の集まりかもしれません。

\(T\) のメタ理論を考えないとき、証明可能性や無矛盾性のようなメタ理論的議論を \(T\) で形式化できるように、\(T\) の論理式はしばしば \(T\) 自身のゲーデル数を意味します。この意味で \(T\) は \(T\) 自身のメタ理論になることができます。したがって、メタ理論を巨大数の定義に使わない限り、通常はメタ理論が何であるか気にかける必要はありません。詳しくは、これを参照してください。

\(MT\) は \(T\) を考える前に固定されていることに注意してください。したがって \(T\) を固定するときには、 理論 \(T,MT,MMT,\ldots\) の塔の高さの最大は固定されています。とくに、巨大数を \(T\) で定義したいとき、メタ理論の塔の高さを「メタ理論、メタメタ理論、メタ \(\times \infty\) 理論を取る! それらすべてを使って、巨大数を定義する! I win!」などと言って変えることは認められません。そうしたければ、それができるようにするための規則を宣言してください。そうすれば他のグーゴロジストもその規則で公正に楽しめるでしょう。


メタ自然数とはなんですか?

おおざっぱに言うと、\(0\) に適用される後者の繰り返しとして構文論的に記述される自然数です。すなわち、\(0, 0+1, 0+1+1, 0+1+1+1, \ldots\) です。これは任意の算術で項とみなせる自然数です。「すべての自然数 \(n\) は \(0 + \underbrace{1+ \cdots + 1}_n\) と表されるのでは?」と聞きたくなるかもしれません。それは正しいですが、\(+1\) の繰り返しが構文論的な方法で与えられていません。それらを区別するには、メタ理論を明確化する必要があります。

\(T\) で作業中のベース理論を表し、\(MT\) で \(T\) のメタ理論を表します。すなわち、すべての \(T\) の論理式は \(MT\) で形式文字列か自然数に符号化されます。さらに、定義可能な \(1\)-項関数 \(S(n)\) が \(T\) に存在し、算術の後者関数と解釈します。もし \(T\) 自身が算術なら、\(S(n)\) は通常の後者です。もし \(T\) が十分に強い集合論なら、\(S(n)\) は \(n \cup \{n\}\) と定義されます。より正確には、\(S(n)\) は \(m = n \cup \{n\}\) として与えられる \(2\)-項関数論理式 \(F(n,m)\) によって定義されます。これは \(T\) のヘンキン拡大の論理式で、\(T\) では論理式 \(\forall x((x \in m) \leftrightarrow ((x \in n) \lor (x = n)))\) と解釈されます。

\(a\) を \(MT\) の自然数とします。その \(T\) での形式化を \(MT\) の符号として定義される定義式 \(F_a(n)\) によって定義される \(T\) の自然数 \(\textrm{Formalise}(a)\) として、以下のように再帰的に定義します:

  1. \(a = 0\) ならば、 \(F_a(n)\) は \(T\) の論理式 \(n = 0\) である。
  2. \(a > 0\) ならば、 \(F_a(n)\) は \(T\) の論理式 \(\forall x(F_{a-1}(x) \to (n = S(x)))\) である。

すなわち、\(\textrm{Formula}(a)\) は論理式 \(F_a(n)\) によって特徴づけられる一意な自然数 \(n\) です。この方法で、すべての \(MT\) の自然数は \(T\) の自然数(の定義式)に対応します。おおざっぱに言うと、\(\textrm{Formula}(a)\) は \(T\) で \(0 + \underbrace{1 + \cdots + 1}_a\) として与えられます。ポイントは、\(a\) が \(MT\) の自然数であり、 \(\textrm{Formula}(a)\) の定義式 \(F_a(n)\) が \(MT\) で構文論的に定義されていることです。メタ自然数は \(MT\) のある自然数 \(a\) に対して \(F_a(n)\) によって定義される \(T\) の自然数です。直感的な述語「\(n\) はメタ自然数である」自体は \(T\) で形式化されていませんが、 文 \(F(n)\) は \(MT\) で形式化されたメタ自然数の \(T\) での定義式です。すなわち、\(MT\) で論理式「自然数 \(a\) が存在し、\(T\) の論理式 \(\forall n(F(n) \to F_a(n))\) は \(T\) で証明可能である」を意味します。

たとえば、\(T\) が \(\textrm{ZFC}\) 集合論である場合を考えてください。\((\textrm{CH} \to (n = 0)) \wedge ((\neg \textrm{CH}) \to (n=1))\) として与えられる定義式 \(F(n)\) によって定義される自然数 \(n\) はどうでしょうか? \(\forall n(F(n) \to (F_0(n) \lor F_1(n)))\) は \(T\) で証明可能ですが、\(\textrm{Con}(\textrm{ZFC})\) が \(MT\) で成り立つ限り \(\forall n(F(n) \to F_0(n))\) も \(\forall n(F(n) \to F_1(n))\) も \(T\) で証明可能ではありません。\(F(n)\) はこの意味でメタ自然数の定義式ではありませんが、\(F(n)\) はメタ自然数 \(0\) か \(1\) のどちらか片方に一致する自然数を定義します。


標準自然数とはなんですか?

数学において、標準自然数とは \(\mathbb{N}\) の元を意味します。「すべての自然数は標準自然数ではないのですか?」と聞きたくなるかもしれません。符号化された理論について考えない限り、それは正しいです。\(T\) で現在作業中のベース理論を表し、\(FT\) で \(T\) 内に符号化された理論を表すとします。言い換えると、\(T\) は \(FT\) のメタ理論です。\(T\) は \(\mathbb{N}\) が意味を持つような十分に強い集合論であり、\(FT\) は「\(n\) は自然数である」を意味する \(FT\) の述語 \(R(n)\) を認めるような算術を含むと仮定します。\(M\) を \(FT\) のモデルとします。\(R(n)\) の \(M\) への相対化により、\(M\) の自然数の集合 \(M^{\mathbb{N}}\) は意味を持ちます。ここで \(n \in M^{\mathbb{N}}\) が与えられたとき、\(n\) は標準自然数かどうか尋ねたくなるかもしれません。これは自明ではありません。なぜならば \(M^{\mathbb{N}}\) は \(\mathbb{N}\) と一致するとは限らないからです。

たとえば、\(FT\) が符号化された \(\textrm{PA}\) であり、\(M\) が \(\{n \cup \{n\} \mid n \in M\} \subset M\) を充足し、\(0\) の解釈が \(\emptyset\) であり、後者の解釈が \(1\)-項写像 \(M \to M, \ n \mapsto n \cup \{n\}\) によって与えられるモデルであると仮定します。この場合、\(\mathbb{N} \subset M^{\mathbb{N}}\) は帰納法により得られますが、\(\mathbb{N}\) に属さない \(n \in M^{\mathbb{N}}\) が存在するかどうかはわかりません。そのような \(n\) は超準自然数と呼ばれます。超準自然数を認めるモデルは \(\textrm{PA}\) の超準モデルと呼ばれ、存在することが知られています。

\(T\) は \(FT\) のメタ理論なので、\(T\) の自然数 \(a\) に対して、\(a\) の \(FT\) における形式化 \(\textrm{Formalise}(a)\) として与えられる \(FT\) のメタ自然数を考えることができます。ここで \(T\) における \(a\) に関する帰納法により、\(\textrm{Formalise}(a)\) の \(M\) への相対化は \(a\) と一致するので、標準自然数です。この意味で、メタ自然数は自然に標準自然数とみなせます。


すべての計算可能巨大数はメタ自然数ですか?

この答えは極めてあいまいな「計算可能」の意味に依存します。代わりに、ここでの意味の計算可能自然数 \(n\) の定義式 \(F(n)\) が与えられたとき、\(F(n)\) がここでの意味でメタ自然数の定義式かどうか尋ねることができます。そして答えは「通常」はいですが、常にそうとは限りません。この問題について正確なやり方で論じるためには、ベース理論を固定する必要があります。

\(T\) で作業中のベース理論を表し、\(MT\) で \(T\) のメタ理論を表します。\(y_i = f_i(x_i)\) で計算可能関数への参照を含む \(F(n)\) の原子部分論理式の枚挙を表すとします。もしメタ自然数の定義式を伴う自然数によって符号化されない \(f_i\) が存在するなら、自然数の定義式ではない計算可能関数自然数の定義式が存在します。なぜならば \(f_i\) は計算可能関数自然数の定義式によって定義される自然数によって符号化されるからです。したがってすべての \(f_i\) はメタ自然数で符号化されると仮定できます。同様に、すべての \(y_i\) と \(x_i\) はメタ自然数の定義式によって定義されると仮定できます。この場合、原子論理式 \(y_i = f_i(x_i)\) は \(MT\) での等しさ(これも \(y_i = f_i(x_i)\) で表します)の形式化として得られます。問題は、たとえ \(y_i = f_i(x_i)\) が \(T\) で証明可能でも、\(MT\) で証明可能であるとは限らないことです。もし \(MT\) で証明可能でなければ、定義式 \(F(n)\) は \(MT\) の定義式の形式化ではありません。

たとえば、\(MT\) が \(\textrm{ZFC}\) 集合論に \(\textrm{Con}(T)\) を加えたもので、\(T\) が符号化された \(\textrm{ZFC}\) 集合論に \(\neg \textrm{Con}(\textrm{ZFC})\) を加えたものならば、\(T\) の自然数を \(\textrm{ZFC}\) 集合論における \(\perp\) の証明を符号化する最小の自然数と定義できます。これはメタ自然数の定義式で定義されていません。なぜならば \(T\) における \(\perp\) の証明の符号化である \(MT\) の自然数は存在しないからです。.

通常は、計算可能関数 \(f\) と、\(f(x)\) の計算の停止が弱い算術で証明可能であると「期待される」ような入力 \(x\) についてのみ \(f(x)\) を使うので、このような問題は起きません(\(f\) の全域性と異なり、\(f\) の各点well-defined性は、たとえ \(f\) が急増加してもしばしば弱い算術で証明可能です)。しかし、各点well-defined性は通常極めて検証が困難であり、「期待」は通常いかなる理論的背景にも基づきません。


いかなるメタ自然数よりも大きい巨大数は存在しますか?

場合によりはい。 ここで説明されているLittlePeng9の \(N\) が、算術におけるそのような巨大数の例です。加えて、もし \(\textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})\) (ゲーデルの不完全性定理により、\(\textrm{ZFC}\) が無矛盾である限り無矛盾です)で作業しているなら、符号化された \(\textrm{ZFC}\) 集合論のもとでの矛盾の証明の最小のゲーデル数 \(p\) はwell-definedな自然数で、不等式 \(p > n\) が任意のメタ自然数 \(n\) に対して証明可能であるという意味でいかなるメタ自然数よりも大きくなります。これは \(p > p\) であることを意味しません。なぜならば \(p\) はメタ自然数として与えられていないからです。同様に、同じ理論上で作業しているとき、\(S(1919)\) はいかなるメタ自然数よりも大きいことが知られています。


論理式

ベース理論の論理式の性質を取り扱うことはできないのですか?

場合によります。 ベース理論の論理式はベース理論の項ではないので、それらの性質をベース理論で取り扱うことは認められません。一方、ゲーデル対応と呼ばれるゲーデル数を使った方法がよく知られており、その方法で、証明可能性などの論理式の性質の形式化を取り扱うことができるようになります。


自然数を公理なしで取り扱うことはできますか?

いいえ。まず第一に、形式論理における定義の定義を知らないなら、ここの説明を参照してください。もし自然数の概念を適切な方法で(たとえば \(0 \neq 1\))公理なしの一階述語論理で定義できるなら、同じ方法で群論や圏論などいかなる一階述語論理の理論でも定義できることがわかります。これは、それらの理論に台集合が単元集合であるようなモデルが存在するという明らかな事実と矛盾します。

公理を推論規則に変換する方法はいくつかあり、一階の集合論以外の形式系もいくつか存在することに注意してください。したがって論理学者は公理を明示的に使うことを回避できます。一方、本当に論理学者であれば、この節の見出しにあるような質問はしないでしょう。


計算可能関数を公理なしで取り扱うことはできますか?

いいえ。はじめに、もし巨大数の定義に公理が必要な理由を知らないならば、ここの説明を参照してください。グーゴロジストはときどき「計算可能関数を取り扱っているので、公理の選択はこの文脈では関係ない!」と言いますが、完全に間違っています。

通常は、\(\textrm{ZFC}\) 集合論で作業を行います。\(T\) を \(\textrm{ZFC}\) 集合論より強い集合論であり、\(f\) を十分弱い算術で定義される再帰的関数で、\(f\) の計算手続きの各ステップがメタ自然数をメタ自然数に置き換えるようなものであるとします。\(f(n)\) の計算手続きの停止が \(n = 10^{100}\) の場合に \(T\) で証明可能であると仮定します。このとき \(f(10^{100})\) は \(T\) でwell-definedです。

\(f\) の計算手続きの各ステップの妥当性は十分弱い算術で証明可能であり、したがって \(\textrm{ZFC}\) 集合論で証明可能です。それではこれらの証明をうまくつなぎ合わせることで、\(\textrm{ZFC}\) 集合論における \(n = 10^{100}\) の場合についての \(f(n)\) の計算手続きの停止証明になるでしょうか? そうとは限りません。この証明の構成を正当化するには、ステップ数のメタ理論的有限性、すなわちメタ理論での計算手続きの停止について知る必要があります。

前の段落の議論で \(T\) での停止性の仮定を使わなかったことを思い出してください。\(T\) での停止性はメタ理論での停止性を保証するでしょうか? そのような性質は \(T\) の \(\Sigma_1\)-健全性と呼ばれ、成り立つとは限りません。もし \(T\) が \(\omega\)-無矛盾ならば、\(T\) は \(\Sigma_1\)-健全です。一方、\(\omega\)-無矛盾性は通常の無矛盾性よりも強い性質であり、メタ理論が \(T\) より弱いか同等で、\(T\) が実際に \(\omega\)-無矛盾ならば、\(\omega\)-無矛盾性の形式化はメタ理論のもとで証明可能ではありません。

結論として、この文脈で公理の選択が無関係だと信じているグーゴロジストは以下の異なる概念を混同しているかもしれません:

  • \(\textrm{ZFC}\) 集合論での有限性
  • \(T\) での有限性
  • メタ理論での有限性
  • 現実世界での直感に基づく有限性


符号化された理論の論理式はすべてベース理論の論理式ですか?

いいえ。たとえ両方の理論が同じ公理を持つ集合論でも成り立ちません。理由を説明するために、\(\textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})\) のメタ理論での無矛盾性を仮定します。これは合理的な仮定でしょうか? ええ、通常の数学ではしばしば \(\textrm{ZFC}\) の無矛盾性が形式化されない意味で仮定されます。もし実際に無矛盾ならば、すなわち \(\textrm{ZFC}\) における \(\perp\) の形式的証明のゲーデル数であるようなメタ自然数が存在しないなら、不完全性定理により、形式化された意味での無矛盾性は \(\textrm{ZFC}\) 自身のもとで証明可能ではありません。したがって \(\textrm{ZFC}\) の無矛盾性を形式化されていない意味で信じることしかできません。ですから\(\textrm{ZFC}\) の無矛盾性(およびそれによって \(\textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})\) の無矛盾性) を形式化されていない意味で信じるのは自然です。ええ、これは極めて複雑で、しばしばこれらの議論に関する誤りが発生します。

もとの質問に戻りましょう。実際、もし一般にそのようにできるなら、完全性定理により、メタ理論での仮定のもとで \(\textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})\) のモデル \(M\) が存在するので、 \(M\) での \(\perp\) の証明を形成する論理式の列はベース理論の論理式の列から導出され、メタ理論の論理式の列からも導出されます。これはメタ理論における \(\textrm{ZFC}\) の無矛盾性の仮定と矛盾します。

何が起きたのでしょうか? では、以下の論理式を考えてください。 \begin{eqnarray*} \textrm{ZFC} + \textrm{Con}(\textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})) \vdash \left(\exists M(M \models \textrm{ZFC} + \neg \textrm{Con}(\textrm{ZFC})) \right) \end{eqnarray*} ここで \(M\) を含む理論をベース理論と呼びます。これはベース理論のメタ理論で証明可能な論理式です。論理式をより明確にするため、\(\textrm{ZFC}\) が出現するたびに番号を振ります。 \begin{eqnarray*} \textrm{ZFC}_1 + \textrm{Con}(\textrm{ZFC}_2 + \neg \textrm{Con}(\textrm{ZFC}_3)) \vdash \left(\exists M(M \models \textrm{ZFC}_4 + \neg \textrm{Con}(\textrm{ZFC}_5)) \right) \end{eqnarray*} ここで \(\textrm{ZFC}_1\) はメタ理論の論理式の集合であり、\(\textrm{ZFC}_2 = \textrm{ZFC}_4\) はベース理論の論理式の集合であり、\(\textrm{ZFC}_3 = \textrm{ZFC}_5\) は符号化された理論の論理式の集合です。

とくに、\(\textrm{Con}(\textrm{ZFC}_2)\) は \(\textrm{Con}(\textrm{ZFC}_5)\) と同じではありません。このような問題は、メタ自然数から導出されない自然数の存在と同じ理由で発生します。


モデル

モデルとはなんですか?

あなたは「モデルの真理を使う! 証明可能性より強い! I win!」と言うかもしれません。モデルの概念の定義をよく理解していれば、それは正しいかもしれません。しかしグーゴロジストはモデルを数学的に間違った方法で参照することがあります。

一階述語論理でのモデルの概念にはいくつかの定義があります。\(T\) を集合論とおきます。

  1. \(T\) の形式言語 \(L\) と、\(L\) で記述される論理式の集合 \(A\) に基づいて \(T\) で符号化される理論を \(FT\) とおきます。
    1. 自由変数 \(M\) を持つ \(T\) の論理式 \(M \models A\) は、適切な埋め込み \(L \hookrightarrow L_M\) で \(M\) に関連付けられた形式言語 \(L_M\) を使って表される \(A\) の充足性として与えられる \(T\) の論理式として定義されます。
    2. \(FT\) も集合論であると仮定します。このとき定義可能クラス \(X\) を伴う \(T\) の論理式 \(X \models A\) は、 \(FT\) での \(X\) の形式化へ相対化した \(A\) の論理式それぞれの証明可能性として定義されます。
  2. \(MA\) を \(T\) の論理式の集合とします。これはメタ理論のメタ集合であるか、ここでの意味で対応する \(T\) のゲーデル数で識別されます。
    1. \(MA\) が有限集合であると仮定します。\(MA\) のすべての論理式を \(\wedge\) でつなげることによって与えられた \(T\) の論理式を \(F\) で表します。自由変数 \(M\) を持つ \(T\) の論理式 \(M \models MA\) は \(T\) の論理式 \(F^M\) として定義されます。
    2. 定義可能クラス \(X\) を伴う \(T\) の論理式 \(X \models MA\) は、\(X\) に相対化された \(MA\) の各論理式の証明可能性として定義されます。
      1. \(T\) のメタ理論を考える場合、論理式 \(X \models MA\) はメタ論理式です。
      2. ゲーデル数を使って \(T\) の形式化された証明可能性を考える場合、論理式 \(X \models MA\) は \(T\) の論理式です。
    3. \(T\) がメタ理論内の符号化された理論でもある場合、自由変数 \(M\) を持つ \(T\) の「\(M\) が \(MA\) のモデルならば」という宣言は、「追加の公理図式 \(\{ M^F \mid F \in MA\}\) において」を意味することがあります。

さらに、二階論理や高階論理にもモデルの概念があります。一階述語論理と異なり、モデルを考えるには意味論を指定する必要があり、対応する議論ははるかに難しくなります。したがってモデルの用語法は極めて曖昧です。

通常の数学では、このような用語法の曖昧さはそれほど大きな問題を起こしません。なぜならば同じ文脈での他の正確な議論がどの用語法を使っているかの理解の助けになるからです。一方、巨大数論では、計算不可能関数の議論はしばしば直感に基づくおおざっぱな考えの概略を含むので、用語法の曖昧さは深刻なものになる可能性があります。


充足性は相対化と同値ですか?

場合によります。その理由を形式的に説明するために、メタ理論を\(MT\)と置き、\(MT\)内で形式化された1階集合論の言語を\(L\)と置きましょう。

\(\varphi\)を\(L\)論理式とし、\(S\)を\(L\)の項とします。\(L\)は1階集合論の言語でしたので、\(S\)は要するに集合です。この時、相対化\(\varphi^S\)は\(MT\)の中で\(L\)論理式として定義されます。

一方で、充足性\(S \models \varphi\)を定義するためには、追加の仮定を明示する必要があります。\(L\)論理式の集合として理論\(T\)を十分強く取っておき、標準的な方法で述語\(\models\)が\(T\)において形式か可能であるとしましょう。定義から、\(\models\)は\(L\)の項と\(T\)における何らかのゲーデル数の組に対してのみ適用可能な述語です。\(T\)におけるゲーデル数もまた、\(L\)の項であることに注意しましょう。\(\varphi\)は\(L\)論理式であり、それは文字通りには\(L\)の項ではないため、記法\(S models \varphi\)を正当化する必要があります。

そのためには、\(L\)が\(MT\)における自然数を用いて形式化されている、つまりゲーデル数化されている、と仮定すべきで、その他の文字列の実装の類をしていないとしましょう。その場合は、いかなる\(L\)論理式\(\varphi\)も、標準的な方法で自然数を形式化することで\(T\)における何かしらのゲーデル数\(\ulcorner \varphi \urcorner\)に対応し、\(T\)における\(L\)の形式化を言語として記述される論理式を定めることになります。すると\(S \models \varphi\)は\(S \models \ulcorner \varphi \urcorner\)の略記として意味を持ちますね。更に、「\(L\)のいかなる項\(S\)といかなる\(L\)論理式\(\varphi\)に対しても\(\varphi^S\)と\(S \models \ulcorner \varphi \urcorner\)の同値性が\(T\)で証明可能である」というメタ定理が\(MT\)で証明可能であるということが、\(T\)を十分強く取っておくことで成立します。この意味で、\(\varphi^S\)と\(S \models \varphi\)は同値と言えます。

この状況は\(\varphi\)をスキーマ\(\Gamma\)、つまり無限個かもしれない\(L\)論理式の集合、に置き換えると劇的に変化します。\(\Gamma^S\)を、相対化されたスキーマ\(\{\varphi^S \mid \varphi \in \Gamma\}\)のことと定義して意味を持たせましょう。一方で\(S \models \Gamma\)は直接は意味を持ちません。何故ならば、\(\varphi \mapsto \ulcorner \varphi \urcorner\)という構成は単に\(L\)論理式から\(T\)におけるゲーデル数の定義文である\(L\)論理式へ送る写像として\(MT\)において定義されているだけで、\(T\)における写像として定義されてはいないからです。もし\(\Gamma\)が有限集合であれば、\(\Gamma\)の代わりに\(\Gamma\)に属する論理式たちを論理積で結んで得られる1つの論理式を使うことでこの問題は避けることが出来ます。もし\(\Gamma\)が無限集合であるならば、\(\Gamma\)の再帰的数え上げを計算するチューリングマシン\(M\)を固定して、\(S \models \Gamma\)を\(\forall n \in \mathbb{N}, S \models \ulcorner M \urcorner(n)\)という\(L\)論理式として形式化すべきです。ここで\(\ulcorner M \urcorner\)とは\(M\)の形式化であり、それは\(M\)のコードの形式化をコードに持つものと定めます.

スキーマ\(\{\varphi^S \mid \varphi \in \Gamma\}\)は1つの\(L\)論理式でない一方で、形式化された充足関係\(S \models \Gamma\)は一意でない\(M\)のとり方に依存して決まる1つの\(L\)論理式です。残念ながら、それらは必ずしも互いに同値ではありません。\(T\)において形式化された\(L\)で記述される論理式が必ずしも\(L\)論理式の形式化ではないことに関する問題も参照してください.


ベース理論のモデルは同じ公理を持つ符号化された理論のモデルを形成しますか?

場合によります。まず第一に、もしモデルの定義を知らないなら、ここの説明を参照してください。\(MA\) でベース理論 \(T\) の公理の集合を、\(A\) で \(MA\) の形式化として与えられる符号化された集合論の公理の集合を表します。

\(MA\) が有限集合であるとき、\(T\) での集合 \(M\) に対する \(M \models MA\) の充足性は[Dev][2]の補題9.11により、 \(M \models A\) の充足性と同値な \(T\) の論理式です。したがってこの文脈では、ベース集合論の集合モデルは符号化された理論の集合モデルです。

\(MA\) が有限集合であるとは限らず \(MA\) をゲーデル数の集合とみなすとき、\(T\) での集合 \(M\) に対する \(M \models MA\) の充足性は、定義により形式化された \(M \models A\) の充足性と同値な \(T\) の論理式です。したがってこの文脈では、ベース集合論の集合モデルは符号化された理論の集合モデルです。

一方、\(MA\) が有限集合であるとは限らず \(T\) もメタ理論内で符号化された理論であるとき、自由変数 \(M\) を持つ \(T\) の「\(M\) が \(MA\) のモデルならば」という宣言は「\(T\) への追加の公理図式 \(\{ F^M \mid F \in MA\}\) のもとで」を意味することがあります。ここで追加の公理図式は、\(T\) の論理式でそのゲーデル数がメタ自然数であるようなものからなります。したがって非メタ自然数の存在の表現不能性により、仮定は形式化された充足性 \(M \models MA\) を含意しません。したがってこの文脈では、ベース集合論の集合モデルは符号化された理論の集合モデルではありません。

最後の場合について、例を説明したほうがいいでしょう。\(T\) が \(\textrm{ZFC}\) 集合論であると仮定します。\(\textrm{FOST}\) を \(T\) で定義される集合論の形式言語とします。このとき \(\textrm{FOST}\) で記述された \(\textrm{ZFC}\) 集合論の形式化された公理 \(A\) は、もとの公理 \(MA\) と「異なる」かもしれません。したがってモデルの意味が最後のものである文脈では、「\(M\) が \(MA\) のモデルならば」という宣言は \(M \models A\) を含意しません。

あなたは「は? でも \(\textrm{FOST}\) は集合論の言語だ。だから \(\textrm{FOST}\) で書かれた論理式はすべて \(T\) から導出される!」と言うかもしれません。しかし間違っています。ベース理論の論理式から導出されない符号化された理論の論理式の例についてはここを参照してください。

ベース集合論のクラスモデル \(X\) を考えるとき、2つの異なる充足性が存在します。1つはメタ理論的な充足性で、もう1つは形式化された充足性です。

メタ理論的な充足性について考えるなら、メタ理論的な論理式 \(X \models MA\) と \(T\) の論理式 \(X \models A\) を比べる方法はありません。したがってこの文脈では、ベース集合論のクラスモデルは符号化された理論のクラスモデルではありません。

形式化された充足性について考えるなら、論理式 \(X \models MA\) と \(T\) の論理式 \(X \models A\) は互いに同値です。したがってこの文脈では、ベース集合論のクラスモデルは符号化された理論のクラスモデルです。


モデルを巨大数の定義に使うことはできますか?

場合によります。以下のどちらかが成り立つ限り、モデル \(M\) を巨大数の定義に含めることができます:

  • 集合論 \(T\) で作業しており、\(M\) を使う論理式がこの節の意味で実際に \(T\) における定義である。
  • \(M\) 自身の上で作業しており、論理式がこの節の意味で \(M\) に相対化された自然数を実際に命名する。

たとえば、集合論 \(T\) で作業していることを想像してください。「群論の有限モデル \(G\) の濃度を \(N\) で表す」のような文は、\(G\)の定義が \(T\) で指定される限り、 \(N\) を定義する \(T\) の閉論理式ではありません。

同様に、たとえ \(T\) が \(\textrm{ZFC}\) 集合論であっても、同じ理由により\(\textrm{ZFC}\) 公理系のモデル \(M\) を使うことは、そのような \(M\) の使用を指定するルールのない巨大数コンテストに参加している限り認められません。「\(T\) の論理式 \(D\) が存在し、\(M \models (\exists ! x(D)) \wedge D[k/x]\) であるような自然数 \(k\) の最小の集合を \(N \in \mathbb{N}\) (警告: \(\mathbb{N}^M\) ではない)によって表す」のような文は、\(M\) が指定されない限り \(T\) における定義文ではありません。

もちろん、\(T\) 自身ではなく \(T\) のモデル \(M\) 上で作業しているなら、\(M\) を使うことはできます。これはあなたが楽しんでいる巨大数論のルールに依存します。この場合、「\(T\) の\(10^{100}\)文字以下のある論理式 \(D\) で命名されるいかなる自然数 \(k\) よりも大きい自然数の集合の最小値を、 \(N \in \mathbb{N}^M\) によって表す」のような文は、メタ理論や充足の形式化を使って容易に \(T\) の定義と解釈できます。

実際、自由変数 \(x\) を持つ長さ \(10^{100}\) 以下の \(T\) の論理式(の完全な表現)の有限集合を \(\Sigma\) で表し、各 \(\delta \in \Sigma\) に対する \(\forall x \in \mathbb{N}, ((\exists ! x(\delta)) \to (\delta \to (x < y))\) を \(\wedge\) で連結することで与えられる自由変数 \(y\) を持つ論理式を \(D\) で表すとします。これらは \(T\) の論理式であり、分出公理によって \(D^M\) が定義する \(\mathbb{N}\) の部分集合の最小値として \(N\) を定義できます。

さらに、\(T\) 上で作業しており、自然数 \(N \in \mathbb{N}\) (\(\mathbb{N}^M\) ではない) の定義にモデル \(M\) を使うことが認められているなら、似た方法で定義を解釈できます。

通常の数学では、\(T\) 上のモデル \(M\) が指定されていなくても \(M\) を使うことが認められているのを思い出してください。それは単に \(M\) が暗黙に量化されているからです。これは量化されておらず指定されていないモデル \(M\) を自由に使えることを意味しません。たとえば、「\(M\) が \(\textrm{CH}\) を充足するなら、\(\textrm{CH}\) を充足しない \(M\) の拡大 \(M'\) が存在する」のような、適切に量化された文を扱います。

さらに、「\(T\) の任意の推移モデル \(M\) について、\(D^M\) が \(k\) を命名するような、長さ \(10^{100}\) 以下の \(T\) の論理式 \(D\) が認容する任意の自然数 \(k\) よりも大きい自然数の集合の最小値を \(N \in \mathbb{N}\) で表す」のような文は容易に \(T\) における定義であると解釈できます。そのような \(D\) は完全性定理により実際に \(T\) で \(k \in \mathbb{N}\) を定義するので、量化されたモデル \(M\) の使用は実質的に取り除けることに注意してください。

一方、モデル \(M\) を \(T\) の論理式 \(D_M\) (のゲーデル数)へ送る関数 \(D_{\bullet}\) であり、\(D^M\) が \(M\) に相対化された自然数を命名するようなものを定義するなら、\(D_{\bullet}\) は \(T\) における自然数の定義ではありません。\(T\) のモデル依存の自然数は、単一の(モデルに依存しない) \(T\) の論理式によってのみ定義できます。


FOSTの論理式は自然数を定義できますか?

場合によります。まず第一に、巨大数の定義に公理が必要な理由を知らないなら、ここの説明を参照してください。自然数を定義するには具体的な公理が必要であることがわかるでしょう。一方、\(\textrm{FOST}\) 自体は単なる形式言語なので、具体的な公理は付属していません。ふつうは、\(\textrm{ZFC}\) 集合論と呼ばれる通常の集合論の公理を使用します。しかし曖昧さがあるならば公理の選択は明確に宣言されるべきです。


計算不可能関数

有限ステップで定義される任意の関数は計算可能ですか?

いいえ。超限順序数を返す関数は計算可能になりえません。更に自然数を返す関数であっても、定義が超限順序数や関数の増大度の比較や無限集合内での探索結果を参照している場合は自然にはそれを計算するアルゴリズムが得られません。運よく計算可能になるかもしれませんが、実際のアルゴリズムを書き下すかその方法を提示しない限りは計算可能性を自明な事実と主張すべきではありません。FGHの計算可能性OCFの計算不可能性巨大数論でよくある失敗#Infinite Searching も参照してください。


任意の計算不可能関数はすべての計算可能関数を支配しますか?

いいえ。たとえば、ビジービーバー関数の像の特性関数など、\(0\) か \(1\) しか値を取らない計算不可能関数はたくさんあります。それらの関数は計算可能全域関数である定数関数を支配しません。


ビジービーバー関数はill-definedですか?

いいえ。単に計算不可能なだけであり、\(\textrm{ZFC}\) 集合論のような十分に強い理論でwell-definedです。計算不可能関数に関するここの説明も参照してください。


ビジービーバー関数はFGHのω_1^CKと比較可能ですか?

基本列系を具体的に選ばない限りFGHの順序数はill-definedなので、質問が意味をなしません。たとえクリーネの \(\mathcal{O}\) 記法に伴う基本列系を考えたとしても、チューリング機械の枚挙の選択に強く依存します。たとえチューリング機械の枚挙を固定したとしても、FGHの \(\omega_1^{\textrm{CK}}\) が Wainer 階層における \(\omega+3\) より早く増加するとは限らないことが知られています[3]FGHの順序保存性に関する問題も参照してください。


n-階ビジービーバー関数はFGHのω_n^CKと比較可能ですか?

基本列系を具体的に選ばない限りFGHの順序数はill-definedなので、質問が意味をなしません。上で説明したように、\(n = 1\) の場合に反例となる基本列系の存在が知られています。


ペアノ算術で定義可能な関数はすべて計算可能ですか?

いいえ。たとえば、ビジービーバー関数はペアノ算術で定義可能であることが知られています。とくに、ペアノ算術で定義可能な関数が Veblen 階層の基本列系に関するFGHの \(\varepsilon_0\) に抑えられるとは限りません。


計算不可能数

計算不可能数とはなんですか?

まず第一に、関数の計算可能性の定義を理解する必要があります。論理式が \(\mathbb{N}\) 上の部分写像 \(f\) を定義し、その写像に対してチューリング機械 \(M\) が存在し、任意の\(f\) の定義域である \(n \in \mathbb{N}\) について \(f(n)\) が \(M(n)\) の出力と一致するならば、その論理式は計算可能関数を定義すると言います。したがって関数の計算可能性とは単なる制限であり、well-definedな計算不可能関数はたくさん存在します。

計算可能数とは、おおざっぱに「ある計算可能関数 \(f\) とメタ自然数 \(n\) について、\(f(n)\) と記述される数」を意味します。すべての自然数は定数関数の出力として表現でき、定数関数は定義により計算可能なので、上記のおおざっぱな説明はそれほど意味がありません。実際、この用語法は数学的なものではなく、直感的なものです。したがって計算可能数の概念に正確な定義は存在しません。しかしその曖昧さが多くの問題を起こすことはないので、しばしば使われます。なので計算不可能数とは計算可能でない数のことにすぎません。

そのような定数関数を排するための簡単で公平な解決方法の1つは、計算可能巨大数の製作者に計算アルゴリズムを明記することを要求することです。逆に、もし計算アルゴリズムの明記のない計算可能関数を自由に認める立場である場合は、そのような定数関数も許容せざるを得ないということです。


計算不可能巨大数は互いに比較可能ですか?

場合によります。まずはじめに、ここで説明した理由により、巨大数を定義するには形式理論を固定する必要があります。\(N_0\) を形式理論 \(T_0\) で定義される巨大数、\(N_1\) を形式理論 \(T_1\) で定義される巨大数とします。

まず、\(T_0\) と \(T_1\) が算術 \(A\) を共有すると仮定します。\(T_0\) と \(T_1\) の両方から \(A\) に関して互換性があるように拡大した理論 \(T_2\) が存在するならば、\(N_0\) と \(N_1\) の比較は \(T_2\) で意味を持ちます。このような \(T_2\) は一意ではないので、比較の結果は \(T_2\) の選択に依存します。

たとえば、\(\textrm{ZFC}\) 集合論は二階の集合論に埋め込み可能なので、\(\textrm{ZFC}\) 集合論で定義された \(BB(10^{100})\) は、二階の \(\textrm{NBG}\) 集合論のような、十分に強い二階の集合論で定義された \(\textrm{Rayo}(10^{100})\) と比較可能です。

しかし、\(T_0\) と \(T_1\) が \(A\) 上で矛盾するなら、\(T_2\) で矛盾が証明可能なので、比較は結局無意味です。すなわち、不等式 \(N_0 < N_1\) と \(N_0 > N_1\) が両方とも \(T_2\) で証明可能です。

次に、\(T_0\) と \(T_1\) が算術を共有していないと仮定します。状況はもっと悪くなります。\(N_0\) と \(N_1\) を比較する方法は存在しません。たとえば、\(BB(10^{100})\) はこのロビンソン算術の拡大で定義される超準自然数 \(N\) と比較できません。\(\textrm{ZFC}\) 集合論の自然数の集合 \(\mathbb{N}\) はペアノ算術を充足しますが、ペアノ算術とこのロビンソン算術の拡大は矛盾します。2つの理論は自然数の概念を共有していません。

少なくとも、計算不可能巨大数とメタ自然数の比較は意味があります。これは計算不可能巨大数が定義されているベース理論の論理式であり、証明可能であるか、反証可能であるか、独立であるかのいずれかです。

ところで、このような問題は計算可能巨大数を扱っているときにはめったに起きません。なぜならば計算可能巨大数は通常メタ自然数だからです(自然数の計算可能性の概念は数学で厳密に定義されていないので、非メタ自然数が計算可能数として参照されることもありますが)。このトピックの見出しを計算不可能巨大数に限定したのはこのためです。もちろん、類似の(ただしそれほど深刻ではない)問題は計算可能巨大数についても起きます。詳しくは、これを参照してください。


計算不可能巨大数を加えることはできますか?

場合によります。計算不可能巨大数の足し算、掛け算、およびべき乗は(計算不可能巨大数の組み合わせ、たとえば合成に関して)ここで説明した、計算不可能巨大数同士が比較可能であるとは限らないのと同じ理由により、well-definedであるとは限りません。とくに、Sam's numberや、Croutonillionや、多くの他の類似の「素朴な」既知の計算不可能巨大関数の組み合わせを初心者が作りますが、完全にill-definedです。

少なくとも、計算不可能巨大数 \(N\) とメタ自然数 \(n\) の和 \(N + n\) には意味があります。これは \(N\) が定義されているベース理論で定義される計算不可能巨大数であり、\(n \neq 0\) である限り \(N\) より大きくなります。とくに、既知の巨大数に \(1\) を加えることは常に可能です。たとえば、「私の巨大数はラヨ数プラス \(1\) だ! これはラヨ数より大きい! I win!」と言うことはできます。残念ながら、巨大数論のコミュニティでは伝統的にそのような「新しい」巨大数はあなた自身の作品とみなしません。なぜならばそのよう巨大数の作成には何の努力も必要ありませんし、その結果は妥当な巨大数論になんら貢献しないからです。


前節の最終段落で説明した、計算可能巨大数が互いに比較可能であるのと同じ理由により、計算可能巨大数は自由に加え合わせることができます(「計算可能巨大数」がこの文脈で具体的なメタ自然数を意味する限り)。このトピックの見出しを計算不可能巨大数に限定したのはこのためです。


ラヨ数は一階の集合論で形式化可能ですか?

場合によります。オリジナルの定義は、\(\textrm{FOST}\) 論理式に対する真理値の割り当てという二階の対象を使うので、代替の定式化を固定する必要があります。真理述語を形式化したいなら、ここで説明したように、もっともよく使われる一階の集合論、すなわち \(\textrm{ZFC}\) 集合論では不十分です。言い換えると、真理述語を使う一階のラヨ数の代替物は、\(\textrm{ZFC}\) 集合論ではill-definedです。一方、\(\textrm{MK}\) 集合論と呼ばれるより強い集合論は \(V\) 内の対象ではないクラスを直接扱えるので、\(V\) に対する真理述語を形式化できます。このような真理述語は一意ではないので、これを一階の集合論での標準的な代替とみなすのは不自然です。真理述語の代わりに構文論的な定義可能性に基づく代替も存在します。これは \(\textrm{ZFC}\) 集合論で形式化可能ですが、定義式の存在の見地からの定義可能性は神託チューリング機械で判定可能なので、この代替はビジービーバー関数と比べてそれほど強くありません。したがってこれを一階の集合論での標準的な代替とみなすのは不自然です。


ラヨ数は公理なしで定義されていますか?

いいえ。まず第一に、ここの議論を参照してください。ラヨ数を定義するにはベース理論に具体的な公理が必要であることがわかります。もしラヨのオリジナルの説明が二階の集合論を使っていると考えるなら、FOST論理式に対する真理値の割り当てが意味を持つように、二階の集合論の正確な公理を固定する必要があります。構文論的定義可能性による一階の弱い代替について考えるなら、それに加えて\(\textrm{FOST}\)で書かれる符号化された集合論の具体的な公理も固定する必要があります。さらに詳しくは、ここの議論を参照してください。


ラヨ数は公理に依存しますか?

場合によります。ベース理論をより強い理論に置き換えても、ラヨ関数の値は変わりません。なぜならば定義式が変わらないからです。この意味で、ラヨ数の値はベース理論の公理に依存しません。一方、ここで説明したように、ラヨ数を定義するには実際に公理を固定する必要があります。この意味で、ラヨ数の形式化可能性(そしてそのためwell-defined性)は公理に強く依存します。しかも、もし構文論的定義可能性による一階の弱い代替について考えるなら、符号化された集合論の置き換えは構文論的定義可能性を変えるので、代替ラヨ数の値を変えるかもしれません。その意味で、ラヨ数の値は符号化された集合論の公理に依存しますが、このような一階の代替はビジービーバー関数と比べてそれほど強くないので、通常は考えません。


ラヨ数はwell-definedですか?

場合によります。まず第一に、巨大数の定義に公理が必要な理由を知らなければ、ここの説明を参照してください。ベース理論の具体的な公理が必要であることがわかります。その公理は明確に宣言されていないので、オリジナルの定義は未完成です。

一方、公理の宣言は通常のもの、すなわち(一階の) \(\textrm{ZFC}\) 集合論の公理を使う場合、伝統的に省略されます。したがって「ベース理論は省略されているのだから通常のものに違いない! だからラヨ数はwell-definedだ!」と言うかもしれません。残念ながら、誤りです。原作者によると、ラヨ数は二階論理上で定義されています。これは具体的に指定されておらず、通常の集合論でもありません。しかも、\(\textrm{ZFC}\) 集合論への素朴な解釈はうまくいきません。なぜならば必要な真理述語はここで説明した理由により \(\textrm{ZFC}\) 集合論においては定義可能でないからです。したがって具体的な二階の集合論の公理か、少なくとも \(\textrm{ZFC}\) 集合論における具体的な代替の定義を実際に指定する必要があります。その後で、ラヨ数はwell-definedになります。一階の代替については、構文論的定義可能性による一階の弱い代替を参照してください。


BIG FOOTはwell-definedですか?

いいえ。まず第一に、真理述語を使用する計算不可能巨大数(たとえばラヨ数)の定義でどのように公理が使われるか知らないならば、ここの説明を参照してください。ラヨ数と同様、具体的なベース理論の公理と、別の具体的な \(\textrm{FOOT}\) で書かれる符号化された集合論の公理が必要です。一方、BIG FOOTの定義で作成者は "We also assume that oodles satisfy all the properties which are considered "natural" properties, e.g. extensionality or existence of full power set" としか書いていません。これは極めて曖昧です。なぜならばいかなる自然な公理の選択も、\(\textrm{BIG FOOT}\) の定義と衝突するからです。詳しくは、ここのコメントを参照してください。\(\textrm{BIG FOOT}\) はどのような公理で定義されているのか作成者に二度尋ねましたが、答えは得られていません。したがって作者は定義をどう修正すればいいか見当もついていない可能性があります。これは \(\textrm{BIG FOOT}\) が完全にill-definedであることを意味します。深く関連する議論がここにあります。


FGH

FGHは計算可能ですか?

場合によります。通常のFGHは可算順序数 \(\alpha\) とそれに伴う基本列系に対する写像 \(\alpha \times \mathbb{N} \to \mathbb{N}\) なので、\(\alpha > \omega\) ならば定義により計算不可能です。計算可能写像は写像 \(\mathbb{N}^n \to \mathbb{N}\) として定義されるので、その定義域は \(\alpha \times \mathbb{N}\) という形ではないことを忘れないでください。\(\beta \in \alpha\) を固定したなら、通常のFGH \(\alpha \times \mathbb{N} \to \mathbb{N}\) の断片 \(\mathbb{N} \to \mathbb{N}\) は計算可能になりえます。しかし、これは計算方法が定義されていることを意味しません。なぜならば\(\beta\) に対応するFGHの断片は、たとえ \(\beta\) が再帰的でも計算可能であるとは限らないからです。明らかに計算不可能な例は、基本列 \(\omega[n] = \textrm{BB}(n)\) に関連付けられたFGHです。

計算可能性を検証せずに「各順序数ごとに計算可能だ!」と言うことは、「私の数は計算可能だ、その定義は教えないけどな!」と言うようなものです。公正に計算可能巨大数論を楽しみたいなら、どうか計算方法を指定してください。さらに、「再帰的に定義されているから計算可能だ」のように言うことに意味はありません。それは単に計算可能性の定義を理解すらしていないと言っているにすぎません。通常のFGHが行っていることは、算術での再帰的定義ではなく、集合論での帰納的定義です。これは計算可能性を含意しません。「\(\textrm{BB}\) を使った反例はインチキだ! 私の基本列は再帰的だから、私の関数は明らかに計算可能だ!」と言うかもしれません。しかし順序数に対する基本列の「再帰性」とはどういう意味でしょうか? それには意味がありません。なぜならば \(\alpha\) 未満の順序数に対する基本列系は写像 \((\alpha \cap \textrm{Lim}) \times \mathbb{N} \to \mathbb{N}\) であり、\(\alpha > \omega\) ならば、再び定義により計算不可能だからです。

一方、順序型が \(\alpha\) である固定された順序数表記 \(OT\) と、再帰的で \(OT\) の固定された枚挙に関してその再帰性が意味を持つような基本列系を使うなら、その結果得られる FGH \(OT \times \mathbb{N} \to \mathbb{N}\) は、固定された枚挙 \(\mathbb{N} \to OT\) との合成 \(\mathbb{N} \times \mathbb{N} \to \mathbb{N}\) が計算可能であるという意味で、計算可能です。通常、枚挙を自然に選ぶ限り、基本列系の再帰性は枚挙の選択に依存しないので、しばしば枚挙は省略されます。もちろん、順序数表記の構造の再帰性は必要です。たとえば、クリーネの \(\mathcal{O}\) はこの文脈での順序数表記ではありません。このような再帰的でない表記を使うなら、結果として得られるFGHは計算可能であるとは限りません。


FGHは任意の可算順序数に対してwell-definedですか?

いいえ。FGHは順序数とその順序数までの基本列系の組に対して定義されます。順序数に対してではありません。結果として得られる関数は基本列系の選択に強く依存するので、具体的な基本列系を選択しない議論は無意味です。特に、与えられた関数\(f\)に対して「FGHで\(f\)に近似できる順序数」や「FGHで\(f\)に対応する順序数」といった何かはill-definedです。順序数への対応を考える際はFGHではなく、順序数表記の順序型や展開規則と整合的な写像などを用いる必要があります。FGHの増大度の基本列系への依存に関する問題も参照してください。


より大きな順序数は、FGHでより早く増加する関数に対応しますか?

そうとは限りません。\(f_{\omega^{\omega}}\) が \(f_{\omega+1}\) より弱いような \(\omega^{\omega}+1\) 未満の基本列系の例として、これを参照してください。基本列系にゆるい条件を課したときに望んだ性質が得られることの証明はこれを参照してください。


FGHの関数は狭義単調増加ですか?

そうとは限りません。この問題についてはこれを参照してください。


PTO(ZFC)に対応するFGHの関数は計算可能ですか?

質問が無意味です。なぜならば \(\textrm{PTO}(\textrm{ZFC})\) は自然に基本列系を伴わないからです。FGHの基本列系への依存に関する問題とFGHの\(\textrm{PTO}\)に関する問題を参照してください。「\(\textrm{PTO}(\textrm{ZFC})\) は再帰的だから、FGHはいかなる基本列系の選択に対しても明らかに計算可能なはずだ!」と言うかもしれません が、2つの理由により間違った推論です。

まず、ここで説明したように、固定された基本列系を伴う再帰的順序数に対応するFGHが計算可能であるとは限りません。次に、ここで説明したように、\(\textrm{PTO}\) はwell-definedな再帰的順序数であるとは限りません。


基本列の違いはFGHの増大度に影響しませんか?

いいえ、基本列の違いは実際にFGHの増大度に影響します。たとえば、特定の関数 \(f \colon \mathbb{N} \to \mathbb{N}\) に対して \(\omega[n] = f(n)\) を定義したら、結果となるFGHは \(\omega\) において \(f\) を超えます。したがって \(\alpha\) までの基本列系を指定しない限り、「\(f_{\alpha}\) の増大度」は無限順序数 \(\alpha\) について意味をなしません。


最小のcatching順序数はwell-definedですか?

いいえ。まず、具体的な基本列系を伴わない順序数に対するFGHのill-defined性に関する問題と、具体的な基本列系を伴わない順序数に対するFGHの増大度のill-defined性に関する問題を参照してください。したがって基本列系を固定する必要があります。すべての可算順序数に対する既知の基本列系は存在しないので、Vel!LittlePeng9がすぐに指摘したように、Catching関数の概念もill-definedであることが知られています。

たとえ基本列系を固定しても、最小のcatching順序数の定義に対して適用可能な計算可能性の定義は合意されていません。確かに、候補はたくさんありますが、そのどれもこの目的に適しません。なぜならばBuchholzのOCFと正規の基本列系に関して、最小のcatching順序数が \(\psi_0(\Omega_{\omega})\) であることの証明に誰も成功していないからです。もしおおざっぱに「任意の \(n \in \omega\) について、FGHの \(\psi_0(\Omega_n)\) はSGHの \(\psi_0(\Omega_{n+1})\) と比較可能である」と述べるならば、計算可能性の実際の証明は存在しません。仮にそれが検証できたとしても、この文は \(\psi_0(\Omega_{\omega})\) の最小性を保証しません。


与えられた順序数未満の全ての順序数を表せる表記はFGHにおけるその順序数で近似できますか?

いいえ。 まず与えられた順序数\(\alpha\)に対し、「FGHにおける\(\alpha\)」は\(\alpha\)までの基本列系を固定しないと意味を持ちません。詳しくはこちらをご参照下さい。もし\(\alpha\)までの基本列系\([]\)を固定したとしても、その主張が成り立つとは限りません。何故なら、\(\alpha\)までの別の基本列系に関するFGHを実装した表記は\([]\)に関するFGHで近似されるとは限らないからです。詳しくはこちらをご参照下さい。この問題は、例えばtreeやTREEやSCGに関する表記など、基本列系を用いた同様の関数階層の構造を持たない表記を扱う際に遥かに深刻となります。更に、もし\([]\)と等価な基本列系に関する関数階層の構造を持つ表記であったとしても、この主張が成り立つとは限りません。何故なら、それらの基本列に関してハーディ階層における\(\alpha\)はFGHにおける\(\alpha\)より真に抑えられることがあるからです。更に、もし\(\alpha\)が"catching"であると仮定しても、catchingという性質を完全に定式化しない限りはこの主張が意味を持ちません。詳しくはこちらをご参照下さい。みなさんは、巨大数研究の主張の多くがこのような誤った推論に基づいていることに最新の注意を払って下さい。


PTO

FGHのPTO(T)に意味はありますか?

いいえ。FGHは順序数で添字付けられた階層ではなく、順序数とそれに伴う基本列系で添字付けられた階層です。\(\textrm{PTO}(T)\) 自体は基本列系を正規に伴わないので、FGHの \(\textrm{PTO}(T)\) は基本列系を指定しない限り意味をなしません。FGHの増大度の基本列系への依存に関する問題FGHの \(\textrm{PTO}(\textrm{ZFC})\) の計算可能性に関する問題も参照してください。


PTO(T)は整礎性がTで証明可能な順序数の上限として定義されていますか?

いいえ。メタ理論の順序数は符号化された理論 \(T\) の項を与えないので、この質問の順序数とは \(T\) の順序数を意味するはずで、\(T\) はこの場合集合論であるはずです。一方、文「すべての順序数は整礎である」が符号化された理論で証明可能なので、この定式化は無意味です。さらに、\(T\) の順序数のクラスの上限をメタ理論に持ち込む方法もないので、「上限」も無意味です。


PTO(T)は対応するFGHの全域性がTで証明可能な順序数の上限として定義されていますか?

いいえ。 クライゼルの定理[4] 命題2.24により、\(\textrm{PA} + \textrm{Th}(\Sigma^1_1)\) はカントール正規形の基本列系に関して \(f_{\varepsilon_0+1}(n)\) の全域性を証明しますが、\(\textrm{PTO}(\textrm{PA} + \textrm{Th}(\Sigma^1_1))\) は \(\textrm{PTO}(\textrm{PA}) = \varepsilon_0\) と一致します。


PTO(T)はTの可証整礎な可証全順序である再帰的整列順序の順序型の上限として定義されていますか?

場合によります。二項関係の整礎性にはいくつかの異なる概念があります:

  1. 原始再帰的無限下降列の不存在。
  2. 無限下降列の不存在。
  3. 一階の文に関する超限帰納法の公理図式。
  4. 固定された自由集合変数 \(X\) に関する超限帰納法の公理(これは \(T\) が十分に強い算術で、その言語が \(\textrm{Z}_2\) の言語である場合にのみ意味を持ちます)。
  5. 任意の空でない部分集合に対する最小元の存在(これは \(T\) が十分に強い集合論である場合にのみ意味を持ちます)。

4番目や5番目の定式化を参照しているなら、答えははいです。さもなければ、答えはいいえです。詳しくは、証明論的順序数に関する記事を参照してください。


PTO(T)は任意の理論Tでwell-definedですか?

いいえ。まず、上記の \(\textrm{PTO}\) の定義を読んでください。\(\textrm{PTO}(T)\) は \(\textrm{Z}_2\) の部分系と十分に強い集合論に対してのみ定義されていることがすぐにわかるでしょう。それでは \(\textrm{PA}\) はどうでしょうか? \(\textrm{Z}_2\) の部分系ではない算術、たとえば、その言語が \(\textrm{Z}_2\) の言語ではない算術を扱うときは、公理図式の代わりに固定された集合変数 \(X\) を使うように変更することにより、人工的に \(\textrm{Z}_2\) の部分系へ拡張します。

とくに、「言語が \(n\) 個以下の記号からなり、公理の集合が \(n\) 個以下の長さ \(\leq n\) の論理式からなるような形式理論の \(\textrm{PTO}\) として与えられる再帰的順序数の上限を \(\alpha[n]\) で表す」のような文はill-definedです。


PTO(T)は再帰的順序数ですか?

場合によります。\(\textrm{PTO}\) は多くの有名な理論では再帰的順序数ですが、再帰的ではない \(\omega_1^{\textrm{CK}}\) になる場合もあります。\(\textrm{PTO}(\textrm{ZFC})\) が再帰的順序数であるかどうかさえ知られていません。\(\textrm{PTO}\) が自動的に再帰的になるように定義を変更したら、元の定義では \(\textrm{PTO}(T)\) が \(\omega_1^{\textrm{CK}}\) になるような理論 \(T\) に対する \(\textrm{PTO}\) は単にill-definedになります。

\(\textrm{PTO}\) が再帰的ではないような算術の単純な例は、\(\textrm{PA}\) に反証可能な文 \(0 = 1\) を加えたものです。無矛盾な例がよければ、\(\textrm{PA}\) に \(\textrm{Con}(\textrm{PA})\) の否定を加えたものが無矛盾な例です(\(\textrm{PA}\) がメタ理論で無矛盾である限り)。一般に、\(\Pi^1_1\)-健全性[4] 定理2.21の概念を使った \(\textrm{PTO}\) の再帰性の基準が存在します。


より強い理論のPTOはより大きくなりますか?

いいえ、そうとは限りません。たとえば、ゲーデルの不完全性定理により(\(\textrm{PA}\) がメタ理論で無矛盾である限り)、\(\textrm{PA}+\textrm{Con}(\textrm{PA})\) は \(\textrm{PA}\) より(証明力の強さと無矛盾性の強さの両方に関して)真に強いですが、その \(\textrm{PTO}\) は \(\textrm{PTO}(\textrm{PA})\)[4] 注意2.25と一致します。


基数

基数は順序数ですか?

はい、定義から順序数となります。 初学者には気を付けていただきたいのですが、人々が時々「基数は順序数ではない」といった誤った主張をすることがあります。これはその人達が定義を確認せずに基数について語っているに過ぎません。集合論は難しいので、巨大数界隈では基本概念の正確な定義をスキップし、正確な定義より直感を意図せず信じ込んでしまいがちになります。

順序数や基数は本当に難しい概念である一方で、巨大数界隈ではそれらを単純な概念とみなしてしまいがちです。それらは有限または無限の数を実際に数学的に定式化したものであって、無限というものは私達の直感を遥かに凌駕しています。従って無限順序数について述べる際は、正確な定義と証明に基づく必要があります。そうでなければ、順序数に対する未定義な演算子を用いたり(ハイパー演算子の未定義な拡張)、相異なる関数を区別せずに考えてしまったり(2種類のOCFを混同したり、ハイパー演算子の2種類の拡張を混同したり、順序数演算と基数演算を混同したり)、といったよくある失敗に陥ることでしょう。


基数は文字に過ぎませんか?

いいえ。 初学者には気を付けていただきたいのですが、人々が時々「基数はただの文字で、崩壊を記述するために使われる」といった誤った主張をすることがあります。これはその人達が順序数と文字列で表された順序数表記を混同しているに過ぎません。OCFの計算不能性への誤解OCFと順序数表記の混同についても参照して下さい。上述したように、基数は順序数です。不幸なことに、基数を順序数と関係のない文字と勘違いしている人は、基数やOCFを非常に単純なものだと思い込み、その喜びを分かち合うために他の初心者に誤った知識を広める傾向があります。

この手の誤解に伴う典型的な誤りの1つは、順序数の関数\(\psi(\alpha)\)を\(\omega^{\alpha}\)と定義しておきながら\(\psi(\Omega) = \psi(\cdot \psi(0) \cdot) = \varepsilon_0\)としてしまうことです。もしあなたの意図が「任意の順序数\(\alpha\)に対して\(\psi(\alpha)\)を\(\omega^{\alpha}\)と定める」ということでしたら、定義から\(\psi(\Omega) = \omega^{\Omega} = \Omega \neq \varepsilon_0\)となってしまいます。基数は文字ではなく、れっきとした順序数ですから。もしあなたの意図が「明記されていない順序数の集合であって\(\Omega\)が属さないものに属する任意の順序数\(\alpha\)に対して\(\psi(\alpha)\)を\(\omega^{\alpha}\)と定める」ということでしたら、\(\psi(\Omega)\)を特徴付ける情報を与えていないので、単にそれがill-definedとなります。関数を定義するためには、その定義域と、定義域内の任意の入力に対する値の両方を定義する必要がありますので、限られた入力に対する値のみを明記しても関数を定めたことにはなりません。関数の定義の仕方の詳細については、再帰的表記の作成ガイドラインの"General Setting"の章を参照して下さい。その他OCFにおけるΩは「ネストする」という意味ですか?巨大数論でよくある失敗#Non-Unique Expression巨大数論でよくある失敗#Intuitive Use of Expressionsも参照して下さい。


OCFにおけるΩは「ネストする」という意味ですか?

いいえ。 まず初めに、\(\Omega\)が形式的な記号であるという誤解に関する問題を参照して下さい。すると\(\Omega\)は順序数であり何らかの固定した順序数の表現方法において\(\Omega\)を含む表示を持つ入力値をOCF\(\psi\)に代入した出力値が\(\psi\)の定義に基づいて定まるものであるということを理解できるでしょう。\(\psi\)の出力値は時々そういった表現方法において\(\Omega\)部分をネストするような基本列を持つことがあります。しかしながr,そういった基本列を持たないこともあります。

例えば、ブーフホルツのψ関数を用いて\(\psi_0(\varphi_{\Omega}(1))\)と表される順序数は\(\psi_0(\psi_1(\psi_1(\cdots \psi_1(0) \cdots))\)と展開され、「自然な」ネスト\(\psi_0(\varphi_{\psi_0(\varphi_{\cdot_{\cdot_{\cdot_{\psi_0(\varphi_{\psi_0(0)}(1))}\cdot}\cdot}\cdot}(1))}(1))\)とは異なります。en:Rathjen's psi functionを用いて\(\psi_{\Omega}(\varphi_{\Omega}(1))\)と表される順序数は\(\psi_{\Omega}(\varphi_{\psi_{\Omega}(\varphi_{\cdot_{\cdot_{\cdot_{\psi_{\Omega}(\varphi_{\psi_{\Omega}(0)}(\Omega+1))}\cdot}\cdot}\cdot}(\Omega+1))}(\Omega+1))\)と展開され、「自然な」ネスト\(\psi_{\Omega}(\varphi_{\psi_{\Omega}(\varphi_{\cdot_{\cdot_{\cdot_{\psi_{\Omega}(\varphi_{\psi_{\Omega}(0)}(1))}\cdot}\cdot}\cdot}(1))}(1))\)とは異なります。

初学者はこの誤りを犯しがちです。というのも、基数やOCFという概念は初学者の理解の範疇を超えてしまうからです。その場合、初学者は正確な定義を無視し、より「単純明快な」方法でそれらの概念を説明してくれるウェブページを探し求めます。しかしながら、世の中には他の初学者らによって書かれた誤りの情報が大量に存在するため、初学者は誤ってはいるが「単純明快」ではある説明文を掴まされてしまうのです。すると初学者は喜び、それらの概念を完全に理解したと思い込んでしまいます。「おお、これらは本当は単純明快だったじゃないか! このウェブページは素晴らしいのに、それに引き換え不快で可読性の低い定義を説明している他の数学記事は本当に使い物にならないな」いいえ、そうではないのです。残念ながら、その初学者は正確な定義に立ち戻らず、そして誤った解説文を疑うこともありません。結局、初学者は他の初学者にそういった誤りの解説文を「教えて」あげてしまい、新たなウェブページにそれを記載して広めていくのです。


I, M, K, 等を形式的定項記号とみなすことで、巨大基数の使用を回避できますか?

場合によります。巨大基数を使わずにOCFの規則を「記述」することはできるかもしれません。しかし、そのwell-defined性を証明するには、しばしば巨大基数の存在の仮定が追加の公理として必要になります。実際に巨大基数が必要かどうか判定するには、well-defined性の証明を完成させなければなりません。ここで巨大基数の再帰的類似物に関する議論も参照してください。.

巨大基数の解析におけるよくある間違いについて注意しておきます。弱到達不能基数のようなものを伴うオリジナルのOCFはRathjenが定義しました。オリジナルの定義は極めて複雑なので、ここのグーゴロジストはいかなる合理的な比較もなしに定義だけを真似ました。したがって彼らが「われわれのOCF弱マーロ/コンパクト基数レベルのものでもある!」と言ったとしても、それらが実際にRathjenのOCFと同等の強さであることを意味しません。類似の記号と類似の展開規則を使っているからRathjenのOCFに似て見えるというだけです。さらに、このようなOCFはwell-definedであるとは限りません。たとえば、UNOCFは\(I\), \(M\), と \(K\)のような記号を使い、OCFのように見えるものとして有名ですが、まだ完全に定義されていません。推測ですが、非常に単純に見えるが類似の記号を持つここのいかなるOCFも、RathjenのOCFよりはるかに弱い単純な順序数表記へ委譲されないでしょう。関連付けられた順序数表記がなければ、OCFは定義により計算可能巨大数論で役に立ちません。多くのグーゴロジストは関連付けられた順序数表記なしでOCFを作っていますが。たとえば、それらはここで説明した理由により解析の役に立ちません。


巨大基数の再帰的類似物は元の巨大基数と似た役割を果たしますか?

場合によります。巨大基数の再帰的類似物は、非常に注意深く使う必要があります。順序数表記の定義で巨大基数を使用する際のガイドラインはここを参照してください。


計算可能関数は巨大基数公理に依存しませんか?

通常はそのとおりです。もし計算手続きがメタ自然数の定義式をメタ自然数の定義式へ送る明示的な構文論的操作によって表現可能なら、標準的な入力に対する計算可能関数の出力は完全に巨大基数公理とは独立です(それらが無矛盾である限り)。これは、単に各計算手順の振る舞いの証明可能性によります。とくに、同じことは各メタ自然数から始めたときの停止性にも成り立ちます。

一方、これは巨大基数公理のもとでの停止性の証明をそれを使わない証明に還元できることを含意しません。任意のメタ自然数に対する「\(n\) から始まる計算が停止すること」の証明可能性は「任意の \(n \in \mathbb{N}\) に対して\(n\) から始まる計算が停止すること」の証明可能性を含意しません。証明可能でなければ、不完全性定理により恒真ではありません。すなわち、停止が実際に成り立たない \(\textrm{ZFC}\) のモデルが不完全性定理により存在します。

この場合、計算可能関数の増加率はwell-definedではありません。なぜならば増加率は支配で定義される半順序によって与えられるからです。できるのはそれぞれの値を比較することだけです。もちろん、増加率の定義をいつでも意味を持つようなものに置き換えることもやりたければできますが、代替の定義を明示的に宣言する必要があります。代替の定義の候補は、支配 \(f < g\) がメタ理論的な文で、メタ自然数 \(N\) の定義式が存在し、任意の \(N < n\) であるメタ自然数 \(n\) の定義式について、不等式 \(f(n) < g(n)\) が \(\textrm{ZFC}\) において証明可能であることです。

増加率の定義を適切に置き換えなければ、その解析はill-definedな概念か \(\textrm{ZFC}\) より強い暗黙の公理を使っているため、正しくありません。最強の公理 \(0 = 1\) に強く基づくいかなる解析も正しくないことは、誰しも同意するでしょう。

おそらく計算手続きがメタ自然数の定義式をメタ自然数の定義式へ送る明示的な構文論的操作によって表現可能な計算可能関数の例を挙げたほうがいいでしょう。すべての定数関数は計算可能であることを思い出してください。以下の関数 \begin{eqnarray*} \textrm{CH}(n) := \left\{ \begin{array}{ll} 0 & (\textrm{if } \forall m \in \mathbb{N}, \aleph_m \neq 2^{\aleph_0}) \\ m & (\textrm{if } \exists ! m \in \mathbb{N}, \aleph_m = 2^{\aleph_0}) \end{array}\right. \end{eqnarray*} は実際に計算可能関数ですが、その値はメタ自然数の定義式で記述されていないことがわかるでしょう。もし「でも誰もこれを計算できない!」と言うなら、チューリング機械と計算可能関数の概念の正確な定義を探す必要があります。自然言語の意味での「計算可能性」は関数の計算可能性と関係ありません。

これは自明な例ですが、計算可能関数の可証停止性の対角化を通したり、\(\textrm{ZFC}\) へ近づくために可証整礎な再帰的順序数を集合論の形式言語を通したりして計算可能巨大数を構成するときには常に現れます。このような対角化の自明な例を回避するのは簡単だと言う前に、どうかこの \(\textrm{ZFC}\) のPTOを使う計算可能巨大数を定義するための努力を読んでください。これは私(訳注: p進大好きbot)にとってそんなに簡単なことではありませんでした。もし \(\textrm{ZFC}\) のPTOに対応する計算可能巨大関数を使って最大級の計算可能巨大数を本当に定義できるなら、あなたにとっては簡単なことかもしれません。

グーゴロジストが計算可能関数に言及するとき、万能チューリング機械を通して対応する自然数がモデルに依存しないメタ自然数の定義式によっても記述される場合だけを暗黙に考えていると推測しています。この場合計算手続きは純粋に構文論的に記述され、入力がメタ自然数の定義式で記述されるなら出力もメタ自然数の定義式で記述されます。したがってこれは自然な仮定です。

たとえば、\(\textrm{CH}(n)\) に対応する自然数はメタ自然数の定義式として記述されません。一方、超越整数の概念を定義する体系は、万能チューリング機械を通してメタ自然数の定義式で記述される自然数へ対応するように計算可能関数を対角化するので、入力がメタ自然数の定義式で記述される限り、\(\textrm{CH}(n)\) は決して対角化に現れません。

\(\textrm{ZFC}\) のPTOを使う計算可能巨大数の構成でも、\(\mathbb{N}\) 上の再帰的整列順序によって定義される順序数間の順序の決定不能性から導出される計算不可能性を回避するために、類似の構文論的な制限を明示的に使っています。結果として、その計算手続きはメタ自然数の定義式をメタ自然数の定義式へ送る明示的な構文論的操作によって表現可能です。

まとめ:

  1. 計算可能関数の値は巨大基数公理から独立であるとは限りません。
  2. 計算可能関数の値は、その計算手続きがメタ自然数の定義式をメタ自然数の定義式へ送る明示的な構文論的操作によって記述されるときに巨大基数公理から独立です。
  3. 2番目の場合の固定されたメタ自然数から始まる計算可能関数の停止は巨大基数公理から独立です。
  4. 2番目の場合の(任意の自然数から始まる)計算可能関数の停止の証明可能性は巨大基数公理に強く依存するかもしれません。もし巨大基数公理なしでは証明できないなら、あるモデル上で偽です。
  5. 増加率の通常の定義は全域性を仮定しています。したがって明示的に増加率の定義を置き換えない限り4番目の場合の計算可能関数に基づく解析は正しくありません。


Stage基数はwell-definedですか?

いいえ。これははじめにHyp cosがここで導入しましたが、記述されているとおりに機能しませんでした。その後、他のグーゴロジストがその用語を固定された定義なしに使っています。。これは巨大基数でも、巨大基数の再帰的類似物でも、巨大基数に代わる役割を果たす形式的文字列でもありません。


OCF

OCFは計算可能ですか?

いいえ。OCFは定義域が非可算な写像です。定義により、計算可能写像の定義域は可算です。したがってOCFはいかなる意味でも計算不可能です。


OCFは順序数表記ですか?

いいえ。違いについてはこれを参照してください。このコミュニティ(訳注: 英語版gwiki)で「順序数表記」と呼ばれているものの多くが実際には順序数表記ではないので、計算可能巨大数の定義で役に立たないことが説明されています。


私のOCFは既存のものよりクールですか?

通常は違います。人々が自分のOCFの美しさについて説明するとき、通常はそれに伴う順序数表記が作成されていません。解析の目的には順序数表記が必要なので、それが存在しないなら、そのOCFは期待するほど役に立ちません。彼らが順序数表記とは何かを理解していない場合すらあります。彼らはしばしば、既存のOCFは証明に興味がない限り不必要に複雑であるか、いくつかの構成要素は役に立たないと言い、それらを「単純化」します。しかし、複雑さのほとんどの部分は順序数表記を作るために実際に使われています。したがって人々が自分のOCFはその単純さがクールだと言うなら、彼らが順序数表記の重要性を理解しているか疑わしいものがあります。特にRathjenの\(\psi\)の単純化に関する問題はen:User blog:p進大好きbot/List of common misconceptions about Rathjen's psi#Is my simplification cooler than the original one?をご覧下さい。


UNOCFはwell-definedですか?

いいえ。オリジナルの考えは最初にUsername5243がここで導入しましたが、UNOCF自体はまだ完全に定義されていません。(巨大基数レベルではない) \(\textrm{TFB}\)未満に限定してさえ、(特定の有限の例ではなく)すべての順序数に適用可能な明記された既知の展開規則は存在しません。一方、何人かのグーゴロジストは十分大きな順序数に対するおおざっぱな展開のパターンを理解しているので、それらの文脈では便利な略記として使われています。

少なくとも、定義は BuchholzのOCFに関する \(\psi_0(\Omega_{\omega})\) を超えたところですら形式化されていないので、UNOCFは巨大基数を伴うOCFに関連付けられた計算可能巨大関数の正確な議論では役に立ちません。詳しくは、これを参照してください。


ψ_0(ψ_I(0))とはなんですか?

この質問は \(\psi\) の定義を指定しない限り無意味です。定義について聞かれたら、それはBuchholzのOCF、拡張BuchholzのOCF、もしくはRathjenのOCFであると言うかもしれません。しかしそれは ψ_I(0) が最小のオメガ不動点であるという期待に反します。例えばイェーガー・ブーフホルツのψ関数に於いてはψ_I(0) が最小のオメガ不動点になります.この問題はコミュニティで広く知られていますが、初心者はこの罠に陥る傾向があります。詳しくは、メイン記事en:User blog:p進大好きbot/List of common misconceptions about Rathjen's psi#Does ψI(0) coincide with the least omega fixed point?en:User blog:p進大好きbot/List of common misconceptions about Rathjen's psi#Does ψΩ(ψI(0)) coincide with the countable limit of Extended Buchholz's function?を参照してください。


インチキ

それは自明だ!

人々は実際の証明がないときでも、望ましい文が明白な事実であるとみなす傾向があります。事例はたくさんあります:

  1. BM1は誰かがそう言ったという理由で明らかに停止するとされていましたが、 その後無限ループがあることが発見されました。
  2. BM2は「自然」に見えるので明らかに停止するとされていましたが、 その後無限ループがあることが発見されました。
  3. BIG FOOTはこの記事がそう言っているという理由で明らかにwell-definedであるとされていましたが、その後ill-definedであることが判明しました
  4. UNOCFは強力な基数 \(T\)を使うので明らかに他のいかなるOCFよりも強いと言われていましたが、ill-definedであることが知られています
  5. BEAFは誰かがそう言ったという理由で、多くの他の計算可能な表記より明らかにも強いと言われていましたが、ill-definedであることが知られています。
  6. R-関数はその定義がかっこいい形式的に見える文で書かれているので明らかにwell-definedであると言われていましたが、ill-definedであることが知られています。

さらに、OCFに関する実に多くの誤った情報が明らかな事実とみなされています。たとえば、「Buchholzの関数に関して、\(\psi_0(\psi_1(\psi_2(\psi_3(0))))) = \psi_0(\psi_3(0))\) である」や「BuchholzやRathjenのOCFに関して、\(\psi_I(0)\) は最小のオメガ不動点である」などです。

なぜ人々は誤った情報を自明なものとみなすのでしょうか? それは単に証明とは何であるか理解していないからです。彼らの直感的な議論を伴う証明の慣習では、ある文をその否定と同時に証明できます。すなわち、矛盾しています。

「明らかである」とは、期待ではなく実際に証明があるときにだけ言うことができます。さもなければ、それはある種のインチキです。証明に関するインチキも参照してください。


この文を示すのは容易だ!

証明を書き下してください。自明だと思っていたことが証明できないことに気づくでしょう。典型的な例の1つは、ペア数列システムの停止性です。人々はしばしば実際に証明を書き下すことなしに、証明は容易であると言いますが、ひとたび証明を書き下すよう求められると、「\(\pi\) は \(3.14\) に似て見えるので、 \(\pi\) は有理数である」のような残念な何かを示します。

「容易に示せる」とは、実際に正確な証明を書き下したときにだけ言うことができます。さもなければ、それはある種のインチキです。この態度は何もしないよりも悪いです。なぜならば他者が実際に与えられた文を証明しようとする動機を減じたり、証明しようとする努力を侮辱してさえいるからです。


関数を大きくするのは簡単だ!

正確な定義を書き下してください。容易に定義できると思っていた定義を書き下すことさえできないことに気づくでしょう。

「容易に定義できる」や「容易に大きくできる」とは、実際にそれらを定義したときにだけ言うことができます。さもなければ、それはある種のインチキです。この態度は何もしないよりも悪いです。なぜならば他者が実際に新しい関数を作成しようとする動機を減じたり、定義しようとする努力を侮辱してさえいるからです。


脳内では動くよ!

正確な定義を書き下せないことを理解しているならば、それが単にill-definedであることに気付いて下さい。「他の有名な関数より明らかに強い新しい関数の素晴らしいアイデアを持っていると主張するグーゴロジストは大量に存在しますが、その考えが正しい保証はありません。何の努力もなく「脳内の関数が世界で一番強い」と単に言うだけなら初心者を含む誰もができます。だからこそ、グーゴロジストが何を脳内に持っているかではなく何が実際に書かれているかが真に重要なのです。

「動く」ということはどのように動くかを実際に書き下したときにだけ言うことができます。さもなければ、それはある種のインチキです。この態度は何もしないよりも悪いです。なぜならば他者が実際に脳内にあるものを完成させようとする動機を減じたり、かね井させようとする努力を侮辱してさえいるからです。


そんなことはもう終わらせたよ!

終わらせたと言うだけでなく、その素晴らしい成果を私達に共有して下さい。世の中には、有名なOCFを拡張したとか、有名な表記より強い表記を作り上げたとか、有名な計算可能関数の停止性を示したといった、素晴らしい成果を成し遂げたとだけ主張してその成果を公開しない人がいっぱいいます。実際にそれがなされたことを、誰が分かるでしょうか?

「終わらせた」とは、実際にそれを終わらせたときにだけ言うことができます。さもなければ、それはある種のインチキです。この態度は何もしないより悪いです。なぜならば他者が実際にそれを完全に終わらせようとする動機を減じるからです。#脳内では動くよ!en:User blog:p進大好きbot/List of common misconceptions about Rathjen's psi#Does my extension/simplification in my mind work?もご覧下さい。


正確な定義は知らなくても理解は十分だよ!

正確な定義を知らないのでしたら、その概念を正しく理解できているかどうかも判断できないことに留意して下さい。実際、このコミュニティ(訳注: 英語版gwiki)にはOCFを十分理解していると言いながら基数の定義すら知らない人が多く存在しました。すると何が起こったでしょう? その人達は誤った情報を拡散し、多くの初学者たちを騙してしまったのです。私(訳注: p進大好きbot)が論文の正確な定理番号を引用してその人達の誤りを説明しても、その人達は私の説明を否定して自分たちの直感を信じてしまいました。正確な定義を知らなければ、正確な定義に基づいた説明が正しいかどうかさえ判断できないかもしれないのです。

「理解した」とは、定義を知っているときにだけ言うことができます。さもなければ、それはある種のインチキです。定義を知らない概念について話す時は、他者から指摘された誤りを理解することさえ出来ないかもしれないのです。この態度は何もしないより悪いです。なぜならば誤った情報の拡散による汚染が生じるからです。


私の予想はこうです!

数学的な文脈における予想(訳注:conjecture)という言葉は、あなたが真偽を知らない命題を好き勝手に指す言葉ではないことに留意して下さい。グーゴロジストは命題を予想と表現する際に、その主張の正確な意味さえ知らないことがあるのです。例えば、その主張が巨大基数、証明可能性、整礎性、PTO、実在のOCF、\(\models\)などといった極めて難解な概念に言及していてそれらの正確な定義を把握していないことさえあります。何故でしょう? 「専門的な」用語を交えた予想を表明することが自らをクールに見せ付けてくれると信じているのかもしれません。

残念ながら、もし正確な定義を知らない概念を使ってしまうと、他の人はそのインチキに簡単に気付けるのです。想像してみてほしいのですが、初学者が「OCFは単純な表記だよ。\(\Omega\)はネストを表す形式的な記号だもの、順序数が単にネストされた順序数に置き換わるだけさ」と言ったとしましょう。その初学者が自分の知らないことについて語っているのだということがすぐに分かるでしょう。それと似たようなもので、正確な定義を知らない概念について話しているときは他の人から即座に見抜かれてしまうのです。

数学的な文脈において「予想」と述べることができるのは、自身が何を話しているのか分かっていることや、そのような期待を裏付ける理論的な証左が必要です。さもなければ、それはある種のインチキです。この態度は何もしないより悪いです。なぜならば他の初学者にそういった根拠のない主張を多かれ少なかれ信じ込ませてしまうからです。例えば、RathjenのOCFの定義を知らない人たちが、それらがいかに弱いと思われているかを指し示すような比較を予想として拡散してきました。その結果、多くの初学者が実在のOCFを本当に弱いものであると信じ込んでしまい、また拡散者らの称賛する概念たちが素晴らしいものであると信じ込んでしまったのです。そんな概念たちはill-definedであったにもかかわらず、です。この事態は恐らくOCF絡みの巨大数研究を2・3年遅らせたでしょう。

同じことがBMSに対しても起こりました。大勢の人が自分たちの表記をBM2.3より強いと豪語してきましたが、それらのうちBM2.3より実際に強いことが判明したものは現在に至るまで1つもなく、それどころかTSSと呼ばれる部分系にすら勝てているかも不明です。にもかかわらず、そういった予想たちの存在によって他の人達は自分たちの表記がきっとBMSより強いはずだと思い込むようになってしまい、そういった比較を予想し始めるのです。


出典

  1. K. Kunen, Set Theory: An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics, Volume 102, North Holland, 1983.
  2. Keith J. Devlin, Constructibility, Perspectives in Mathematical Logic, Volume 6, Springer-Verlag, 1984.
  3. T. Kihara, omega-1-ck.pdf.
  4. 4.0 4.1 4.2 M. Rathjen, The Realm of Ordinal Analysis, S.B. Cooper and J.K. Truss (eds.): Sets and Proofs. (Cambridge University Press, 1999), pp. 219--279.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。