巨大数研究 Wiki
Advertisement

巨大数界隈ではしばしば

  1. OCF(順序数崩壊関数)
  2. 順序数表記
  3. 順序数へ対応を持つだけの表記
  4. 基本列系を持つだけの表記
  5. 順序数に対する基本列系

という互いに相異なる概念が用いられますが、これらは巨大数の解析が得意な人であっても混同しがちなものです。英語版巨大数wikiで「新しい順序数表記を作りました!」と宣言しながら順序数へ対応を持つだけの表記を載せているブログ記事も何度も見てきました。恐らくは

  • 順序数が何かを知らずに万能な呪文として使ってきたか(「順序数とは単なる記号だ」とか「説明に集合論を使うな」と主張する人さえ見かけます)
  • 順序関係の再帰性が何を意味するかを知らずに自動的に成り立つものと思い込んで使ってきたか(算術ではなく集合論で実際の順序数を用いて構成した非再帰な順序を持ち出してくることがたびたびあります)
  • 整礎性の役割を知らずに自動的に成り立つものと思いこんで使ってきたか(整礎性がないと超限再帰出来ないので順序数にも関数にも対応させられない場合がほとんどなのですが整礎性を気にしない人が少なくありません)
  • 順序数表記という言葉を何度も聞いたことがあるからその意味を何となく推測していたが、その定義を一度も読もうとしたことがなかったか

といったところでしょう。そしてそういった人たちが大量に誤ったブログ記事を量産してきたため、新たにこれらを学ぶ人達が検索をする時に誤った情報を掴み同じような理解をしてしまいやすいという負の循環を生んでいるのだと考えられます。

順序数表記は、単なる表記ではなく(原始)再帰的整列順序が定義されたものです。定義さえ知ってしまえば、UNOCFやBMSやその他の「順序数表記」と界隈で称されるものが明らかに順序数表記ではないことがよく分かります。実際、それらの定義において(原始)再帰的整列順序が一切構成されていないからです。順序数表記を作る上で(原始)再帰的整列順序を構成することがかなり重い要素となることは、TONやRathjenの順序数表記でいかに苦労して(原始)再帰的整列順序を構成されているかを読めばすぐに分かります。

(原始)再帰的整列順序を作っていない表記を「順序数表記」と称してTONやRathjenの順序数表記より強いと主張することは例えるならば、計算可能関数の展開規則を作らずにBMSより強いと主張しているようなものです。厳しい言い方をしてしまいましたが、少なくとも英語版巨大数wiki界隈における順序数表記の誤解による汚染はもはや深刻で新規参入者がどうあがいても大量の誤った情報を掴んでしまうという状況です。せめて日本ではそうならないように、正しい定義が広く認識されることを願っています。

というわけで今回は、これらの概念について、巨大数に関わる部分のみに絞って概説しようと思います。


OCF

OCFとは順序数崩壊関数(ordinal collapsing function)の略称で、集合論で定義されるものです。OCFは順序数を代入して順序数を返す関数であって、濃度なり共終数なり到達不能性の指数なりといったある種の「大きさ」を減らす機能を持つものを広く指す用語です。なので「関数\(\psi\)は順序数崩壊関数である」といった時、これは数学における厳密な論理式を主張しているのではなく、単に\(\psi\)の用途を述べていると思いましょう。


目的

計算可能巨大数を作るために、計算可能巨大関数を作るために、FGHやHHを適用するための順序数表記と再帰的基本列系を得るために、巨大な再帰的可算順序数を作るために、OCFで可算順序数へ崩壊させるための巨大な基数を作るために、OCFで\(I\)未満の基数に崩壊させるための到達不能基数を作るために、OCFで\(M\)未満の到達不能基数に崩壊させるための弱マーロ基数を作るために……。


構成

適切な順序数\(\kappa\)と\(\alpha\)に対し、新しい順序数\(\psi_{\kappa}(\alpha)\)を定義します。そのために、まずは以下を定めます:

  1. 有限個の(\(1\)変数あるいは多変数の)関数\(F_0, F_1, \ldots, F_m\)であって、順序数を順序数に対応させるもの(例:加法\((\alpha,\beta) \mapsto \alpha+\beta\)、乗法\((\alpha,\beta) \mapsto \alpha \times \beta\)、ヴェブレン関数\((\alpha,\beta) \mapsto \varphi_{\alpha}(\beta)\))
  2. 順序数の集合\(C_{\kappa}^0\)


\(\psi_{\kappa}(\alpha)\)を\(\alpha\)に関する超限帰納法により定義するには、本質的に2種類の方法があります:

  1. \(C_{\kappa}(\alpha)\) を、以下の組み合わせで表現できる順序数の全体集合として定め、\(\psi_{\kappa}(\alpha)\)を\(C_{\kappa}(\alpha)\)に属さない最小の順序数として定める:
    1. \(C_{\kappa}^0\)に属する順序数
    2. 関数\(F_0, F_1, \ldots, F_m\)
    3. 順序数\(\beta < \alpha\)と\(\pi\)に対する\(\psi_{\pi}(\beta)\)
  2. \(C_{\kappa}(\alpha)\)を上と同様の方法で定める。ただし、\(C_{\kappa}^0\)に属する順序数、関数\(F_0, F_1, \ldots, F_m, \psi_{\pi}(\beta)\)の組み合わせのうち、「標準形」であるもののみが\(C_{\kappa}(\alpha)\)に属するとする。

後者の場合、順序数の表示に対する標準形という概念を定義する必要があります。順序数の「表示」とは厳密にはどういう意味なのか気になるかもしれませんが、集合論では表示という概念を定数と関数からなる列として形式的に定義することができます。

表示を使わずに定義されたOCFは読者にとって分かりやすいものとなります。一方で、OCFを定義する際には少し努力しなければなりません。何故なら「\(\psi_{\kappa}\)に入力された順序数の最後に登場する\(\omega\)を\(\cdots\)という規則に従って書き換える」という要領でOCF を定義することができないからです。

表示を使って定義されたOCFは、読者にとってはそれほど分かりやすくありません。更には、標準形の概念を注意深く定義して、任意の順序数(必要に応じて上限を定めても構いません)に対してただ1つの標準形が存在するようにしなれけばなりません。しかし標準形が定義できさえすれば、OCFを「\(\psi_{\kappa}\)に入力された順序数の最後に登場する\(K\)を\(\cdots\)という規則に従って書き換える」という要領で定義することが可能となるのです。

表示を使ってOCFを定義することは、OCFと順序数表記とを同時にお互いを用いて定義することによく似ています。従って、たとえOCFの定義に表示を使っていなかったとしても、それに対応する順序数表記を定義するためには形式的な文字列に対する標準形の概念を定義しなければならなくなるケースが実際に多いです。


\(F_0\)を加法\((\alpha,\beta) \mapsto \alpha+\beta\)とし、\(\kappa\)は\(0\)のみを許容する(従って\(\kappa\)は動かないので\(\psi_{\kappa}\)と\(C_{\kappa}^0\)を\(\psi\)と\(C^0\)と略記する)とし、\(C^0\)を\(\{0,\Omega\}\)とした時の順序数崩壊関数を計算してみましょう。




順序数\(\alpha\)と自然数\(n\)に対し以下のように同時に再帰的に集合\(C^{\infty}\)と順序数\(\psi(\alpha)\)を定める:

  1. \(C^{\infty}(\alpha)\)は以下を満たす最小の集合である:
    1. \(0,\Omega \in C^{\infty}(\alpha)\)である。
    2. いかなる\(\beta, \gamma \in C^{\infty}(\alpha)\)に対しても\(\beta + \gamma \in C^{\infty}(\alpha)\)である。
    3. いかなる\(\beta \in \alpha \cap C^{\infty}(\alpha)\)に対しても\(\psi(\beta) \in C^{\infty}(\alpha)\)である。
  2. \(\psi(\alpha)\)は\(C^{\infty}(\alpha)\)に属さない最小の順序数である。




使う関数\(F_0,\ldots,F_{m-1}\)や許容される\(\kappa\)が多ければOCFの定義も複雑になりますが、加法だけで\(\kappa\)も\(0\)のみだとこのようにとても簡単になります。\(\psi\)が以下の性質を満たすことが容易に確認できます:

  1. \(\alpha < \beta\)を満たすいかなる順序数\(\alpha\)と\(\beta\)に対しても、\(\psi(\alpha) \leq \psi(\beta)\)である。
  2. いかなる順序数\(\alpha\)に対しても、\(\psi(\alpha) < \Omega\)である。
  3. \(\alpha < \varepsilon_0\)を満たすいかなる順序数\(\alpha\)に対しても、\(\psi(\alpha) = \omega^{\alpha}\)である。
  4. \(\varepsilon_0 \leq \alpha \leq \Omega\)を満たすいかなる順序数\(\alpha\)に対しても、\(\psi(\alpha) = \varepsilon_0\)である。
  5. \(\psi(\Omega + 1) = \varepsilon_0 \times \omega\)である。

OCFを理解する上である程度は例を計算しておくことが大切だと思いますので、ぜひ上の性質を自力で確認してみましょう。


注意

まず最もありがちなことして、OCFに伴う何かしらの基本列系とFGHを組み合わせて得られる関数\((\alpha,n) \mapsto f_{\alpha}(n)\)が計算可能であるという誤りがあります。実際はOCFそのものが集合論内で真に無限を用いる概念であるため、それ自体はチューリングマシンに翻訳することの出来ない計算不可能な関数です。そのため、計算可能巨大数を定義するためにはOCFだけでは不十分で、実際には順序数表記を用いる必要があります。特に巨大数界隈では順序数とその表記である文字列の区別がついていない人が多いために「何故OCFが駄目で順序数表記なら良いのか」は説明しにくいのですが、順序数表記はOCFと違って一切無限を用いず有限の数の並びを算術的に操作するだけで定義されているために計算可能性が保証できる、と考えて下さい。

これはOCFとは関係ないことですが、中には「自分は\(\textrm{PTO}(\textrm{ZFC}+\textrm{I}0)\)等の非常に大きな可算順序数の名前を知っているのでそれだけでFGHにより実質究極の計算可能巨大数が作れる」と勘違いしている人もいて、もはや\(\textrm{PTO}\)とは何かすら理解していないためにどう誤っているのかを説明したところで説明の意味すら分からなくなってしまいます。こうならないためにも、せめて定義を知っている概念を使うことを強くおすすめします。

また巨大数界隈には、上に述べたような意味での標準形を適切に定義していないにもかかわらず、表示の概念を用いてOCF(または順序数に関係した一般の関数)をしばしば「定義」してしまう人がいます。そういったOCFは通常、ill-definedとなります。

例えば、順序数に関係した関数\(\psi\)を次のような規則で定めようとしても、うまくいきません:

  • 任意の極限順序数\(\beta\)、および順序数を順序数に写す(いくつかの条件を満たすような)任意の関数\(f\)に対し、\(\psi(f(\beta))\)を\((\psi(f(\beta[n])))_{n=0}^{\infty}\)で定義される基本列\((\psi(f(\beta))[n])_{n=0}^\infty\)の極限と定める。

\(f(\beta)\)と表される順序数\(\gamma\)から\(f\)と\(\beta\)を復元することはできないので、\(f\)や\((\beta[n])_{n=0}^{\infty}\)を\(\psi(\gamma)\)や\((\psi(\gamma)[n])_{n=0}^\infty\)の定義に使うことができないのです。

もちろん、もしOCFに付随する順序数表記を定義したい場合には、標準形の概念を再帰的な方法で定義する必要があります。巨大数界隈では標準形の導入をせずに済ませようとすることがしばしばありますが、標準形の導入はOCFを考える上で最も重要かつ難しいステップの1つです。数学の論文でOCFの再帰的定義に現れるいくつかの条件は標準形を再帰的に定めるために実際に用いられているのですが、巨大数界隈ではそういった複雑な条件がオリジナルの著者らによって何故課されていたのかを理解することなく削り、それらのOCFを「簡略化」ないし「拡張」したと称してしまうことがあります。するともしより大きな巨大基数やより高階の対角化を駆使していたとしても、結果的にOCFはとても弱くなってしまうか、または対応する順序数表記がill-definedとなってしまうでしょう。


順序数表記

順序数表記(または順序数表記系)とは、算術で定義される表記の一種です。この用語の使い方にも色々な流儀があり、狭いものでは「\(\mathbb{N}\)の上の再帰的整列順序\(<\)」という定義が採用されます。ただしこの記事では順序と言ったら狭義順序、つまり反射律と反対称律でなく非反射律と非対称律を満たす(\(\leq\)でなく\(<\)と書かれることが多い)ものを指すこととします。

さて、この流儀だと表記に自然数しか使えないので扱いにくいため、もう少し広げて「あらかじめ固定した可算個の記号のみからなる文字列の再帰的集合\(OT\)とその上の(原始)再帰的整列順序\(<\)の組」とすることが多いと思います。\(OT\)の要素は「項」や「順序数項」と呼ばれ、これ自体は順序数とは限らず、単に順序数を表記するために使える文字列に過ぎません。文字列によく使われる記号は\(0, \omega, \Omega, I, M, K, T, +, \varphi, \psi\)などですが、別にこれらに限らずあらかじめ決めさえすれば好きな記号を使うことができます。

「記号」や「文字列」という概念が数学的にどう扱われるのか気になる人のためにより正確に書くと、記号は単なる集合です。集合をどういう用途で用いたいかを示す時に「記号」と表現するだけで深い意味はありません。そして文字列というのはその記号たちのみからなる有限配列のことです。ただ、好きな記号を用いて良いとは言っても、\(x\)と\(\chi\)とか\(o\)と\(\circ\)とか\(\epsilon\)と\(\varepsilon\)といった紛らわしい文字を同時に用いるのは視認性が悪いので避けたほうが良いと思います。また表記に関する伝統的な慣習をある程度踏襲した方が理解されやすく、例えば\(0\)という記号を\(<\)に関する最小要素でない項を表すのに使ったり、\(I\)を弱到達不能基数と関係ない項を表すのに使ったりするとそれだけで混乱を生みやすくなりますので気をつけましょう。逆に\(0\)という記号を使ったから自動的に\(<\)に関する最小要素であることを暗に課すことができる、とか\(I\)という記号を使ったからには自動的に弱到達不能基数レベルの順序数表記になる、とかそういうことはありませんので、伝統的慣習を踏襲したとしてもきちんと定義を書き、解析をする必要があります。当たり前なことのようですが、後者については(基数を単なる記号のことと勘違いしている層が英語版巨大数wiki界隈に存在するせいか)実際にそういう誤解を生んでしまっているようです。

さて、文字列の集合は一見すると\(\mathbb{N}\)と関係ないように見えるので、(再帰性はチューリングマシンを用いて定義される概念であり特に自然数に関係する話題でしか意味をなさないはずのものであるため)\(OT\)が再帰的であるということの意味が気になるところですね。あらかじめ用いる記号が固定されていることから、記号に番号を付すことで\(OT\)を自然数の有限配列のみからなる集合と具体的な全単射で結ぶことが出来ます。自然数の有限配列は素因数分解を用いた具体的な基本操作で自然数と全単射で結ぶことが出来るので、結局\(OT\)は\(\mathbb{N}\)の部分集合と同一視することが出来ます。それが再帰的部分集合であれば良い、つまりその部分集合に入るか否かを判定するアルゴリズムがあれば良い、ということです。

また\(\mathbb{N}\)の再帰的部分集合は\(\mathbb{N}\)と具体的で計算可能な一対一対応を持つので、その上の整列順序が再帰的であるということも全単射で\(\mathbb{N}\)に移して得られる整列順序が再帰的であること、つまり\(<\)が成り立つか否かを判定するアルゴリズムがあることとして定義されます。要するに結局\(\mathbb{N}\)上の再帰的整列順序を定めていることに他ならないので、狭い意味の順序数表記と広い意味の順序数表記は等価なものになります。

ちなみに他の等価な定式化としては例えば、「全単射\(i \colon \mathbb{N} \to X\)が定義された集合\(X\)とその上の整列順序\(<\)であって\(a,b \in \mathbb{N}\)に対する関係\(a \prec b \Leftrightarrow f(a) < f(b)\)が再帰的であるものの組」等が挙げられます。いずれにしても、狭い意味の順序数表記を適切な全単射で翻訳しただけのものですね。

著者によっては\(<\)が原始再帰的であることや\(i\)が恒等写像であることを課したりしますが、著者によっては\(<\)が非再帰的であったり整礎半順序であることを許したりします。また著者によっては順序数表記の項のことを順序数表記と呼びます。巨大数の研究における順序数表記は主に計算可能巨大数の研究で使われるものなので、ここでクリーネの\(\mathcal{O}\)などの計算不可能な表記を排除するためにあくまで再帰的整列順序のみを考えます。

\(<\)を判定するアルゴリズムが存在することは極めて重要で、順序数への対応や基本列が与えられているだけの表記が順序数表記とみなせない理由はここにあります。詳しくは順序数への対応を持つだけの表記と順序数表記の関係基本列系を持つだけの表記と順序数表記の関係をご覧下さい。\(<\)を判定するアルゴリズムが存在しなくても良いなら、クリーネの\(O\)表記のように整列順序が計算不可能だけど順序数への対応を持つ表記でさえ許されてしまいます。


目的

和訳疲れました。誰か代わりに訳してほしいです。

We want a computable large number!

Constructing a large recursive countable ordinal is not sufficient. We also need a recursive system of fundamental systems, and a way to describe it in arithmetic, in order to define a computable large function. Therefore we need an ordinal notation in order to use it as a domain of a recursive system of fundamental sequences which will be defined in another step. Otherwise, enjoy Busy Beaver function. It is also cute, and far beyond computable large functions.


構成

文字列を数列に変換して素因数分解で自然数に変換して再帰性を確認する、というのは非常にめんどくさそうに見えますが、これは「文字列に関するアルゴリズムで実装可能である」ということと同義なので、定義さえ理解してしまえばいちいち自然数に変換せずとも確認することが出来ます。固定した記号のみからなる文字列が\(OT\)に属するか否かを判定するアルゴリズムがあれば\(OT\)は再帰的ですし、\(OT\)に属する文字列\(s\)と\(t\)に対して\(s < t\)か否かを判定するアルゴリズムがあれば\(<\)もまた再帰的となるわけです。なので順序数表記\((OT,<)\)を構成しそれが実際に順序数表記であることを確認するためには以下のような手順を踏めば十分となります:

  1. 表記に使用する可算個の記号を列挙する。
  2. 固定された記号のみからなる文字列が\(OT\)に属するか否かを判定するアルゴリズムを書き下す。
  3. \(OT\)に属する文字列\(s\)と\(t\)が\(s < t\)を満たすか否かを判定するアルゴリズムを書き下す。
  4. \(<\)が\(OT\)上の整列順序であることを確認する。

こうしてやるべきことを列挙してみると簡単そうに見えるかもしれませんが、実際は闇雲に作ると\(<\)が整列順序でなくなり失敗してしまいます。きちんと\(<\)が整列順序となるようにするために、以下に更にもう少し具体的な手順を紹介します。もちろんこれはあくまで順序数表記を構成する戦略の1つに過ぎないため、必ずしもこの方法に従う必要はありません。

To begin with, choose

  • finitely many function symbols \(f_0,f_1,\ldots,f_m, f_{m+1}\), e.g. a constant term symbol \(0\) (i.e. a function symbol of arity \(0\)), the addition symbol \(+\) (i.e. a function sysmbol of arith \(2\)), and other function symbols such as \(D\), \(\psi\), \(\varphi\), \(\Phi\), \(\chi\), and so on,
  • finitely many brace symbols, e.g. \((,),\{,\},\langle,\rangle\),
  • finitely many separator symbols, e.g. comma, colon, and semicolon, and
  • a recursive set \(T\) of formal strings called terms consisting of brace symbols, separator symbols, and \(f_0,f_1,\ldots,f_m,f_{m+1}\) satisfying syntax theoretic restrictions on the arity, e.g. if \(f_0\) is of arity \(0\) and \(f_3\) is of arity \(1\), \(f_3(f_0)\) and \(f_3(f_3(f_0))\) are allowed but \(f_3(f_3)\) or \(f_0(f_0)\) are not allowed.

There are essentially two ways to define an ordinal notation \((OT,<)\). One is purely arithmetic, and the other one is partially set theoretic.

  1. Define a binary relation \(<\) on \(T\) by a (primitive) recursive computation using the syntax theoretic structure on terms, and a recursive subset \(OT \subset T\) to which the restriction of \(<\) is a strict well-order.
  2. Define an OCF \(\psi\) by choosing other data \(F_0, F_1, \ldots, F_m\) and using a notion of expressions of normal form. Then denote by \(o\) the map from \(T\) to the class of ordinals associated to the correspondence \((f_0,f_1,\ldots,f_m,f_{m+1}) \mapsto (F_0,F_1,\ldots,F_m,\psi)\), and by \(OT \subset T\) the subset of terms \(a\) such that the canonical expression of \(o(a)\) by \(F_0,F_1,\ldots,F_m,\psi\) is of normal form. Finally, "interprete" the relation \(o(a) \in o(b)\) for terms \(a\) and \(b\) into a recursive relation \(<\) on \(T\). More Precisely, define a recursive relation \(<\) on \(T\) such that \(o(a) \in o(b)\) is equivalent to \(a < b\) for any \(a,b \in OT\) (not \(T\)).

The benefit of the first approach is that it is purely arithmetic. However, it is not so easy to prove that \((OT,<)\) is actually an ordinal notation, i.e. \(<\) is a well-order on \(OT\), and that it presents a sufficiently large countable ordinal. Of course, it does not mean that it were impossible.

For example, see my ordinal notation here. I directly defined an ordinal notation with \(\textrm{PTO}(\textrm{ZFC})\) without using set theory itself. If what Rathjen stated without proof on the provability of the well-foundedness of his ordinal notation with the smallest weakly Mahlo cardinal, then I guess that my ordinal notation goes beyond it.

The benefit of the second approach is that the well-foundedness immediately follows from that of ordinals. However, it is not so easy to define an OCF by using expressions of normal form. At least, defining the notion of normal forn and interpreting \(\in\) into a recursive order \(<\) is not uniquely done even if we have an OCF. Therefore there is no canonical way to define an ordinal notation from an OCF. Namely, an OCF is not actually a specific ordinal notation at all.


OCFの例として構成した\(\psi\)に付随する順序数表記を考えます。\(F_0\)を加法\((\alpha,\beta) \mapsto \alpha+\beta\)としたため対応する関数記号\(f_0 = \oplus\)の引数は\(2\)となります。\(\psi\)の引数は\(1\)であるため、対応する関数記号\(f_1 = D\)の引数は\(1\)となります。




記号\(0\)と\(\Omega\)と\(\oplus\)と\(D\)と\((\)と\()\)のみからなる有限配列の集合\(T\)を以下のように再帰的に定める(すなわち以下を満たす最小の集合である):

  1. \(0,\Omega \in T\)である。
  2. いかなる\(s \in T\)に対しても、\(D(s) \in T\)である。
  3. いかなる\(s \in T\)に対しても、\(\Omega \oplus s \in T\)である。
  4. いかなる\(s,t \in T\)に対しても、\(D(s) \oplus t \in T\)である。

通常は引数\(2\)の関数記号\(\oplus\)を使う場合\(s \oplus t\)の代わりに\((s) \oplus (t)\)という表記を用いた方が\(s\)や\(t\)に\(\oplus\)が現れる場合に文字列としての扱いが簡単になるが、今回は\(\oplus\)の左に\(\Omega\)か\(D(s)\)の形の項しか許していないためそのような結合律の煩わしさを気にする必要がない。

部分集合\(PT \subset T\)を以下のように再帰的に定める(すなわち以下を満たす最小の部分集合である):

  1. \(\Omega \in PT\)である。
  2. いかなる\(s \in T\)に対しても\(D(s) \in PT\)である。


\(s,t \in T\)に対する関係\(s < t\)を以下のように再帰的に定める:

  1. \(t = 0\)ならば、\(s < t\)でない。
  2. \(t \neq 0\)とする。
    1. \(s = 0\)ならば、\(s < t\)である。
    2. \(s = \Omega\)ならば、\(s < t\)とある\(t' \in T\)を用いて\(t = \Omega \oplus t'\)と表せることは同値である。
    3. ある\(s' \in T\)を用いて\(s = D(s')\)と表せるとする。
      1. \(t = \Omega\)ならば、\(s < t\)である。
      2. ある\(t' \in T\)を用いて\(t = D(t')\)と表せるならば、\(s' < t'\)と\(s < t\)は同値である。
      3. ある\(t_1 \in PT\)と\(t_2 \in T\)を用いて\(t = t_1 \oplus t_2\)と表せるならば、\(s < t_1\)または\(s = t_1\)であることと\(s < t\)は同値である。
    4. ある\(s_1 \in PT\)と\(s_2 \in T\)を用いて\(s = s_1 \oplus s_2\)と表せるとする。
      1. \(t \in PT\)ならば、\(s_1 < t\)と\(s < t\)は同値である。
      2. ある\(t_1 \in PT\)と\(t_2 \in T\)を用いて\(t = t_1 \oplus t_2\)と表せるとする。
        1. \(s_1 < t_1\)ならば、\(s < t\)である。
        2. \(s_1 < t_1\)でないとする。\(s_1 = t_1\)かつ\(s_2 < t_2\)であることと\(s < t\)は同値である。

再帰的関係\(<\)は\(T\)上の全順序を定めるが、これ自体は整列順序でないことに注意する。以下で定義する再帰的部分集合\(OT \subset T\)に制限して初めて\(<\)は整列順序となる。


標準形という概念を定義するために、\(s \triangleleft t\)という\((s,t) \in T\)の\(2\)項関係を以下のように再帰的に定める:

  1. \(s \in \{0,\Omega\}\)ならば、\(s \triangleleft t\)は成り立つ。
  2. \(s = D(s')\)を満たす\(s' \in T\)が存在するならば、\(s' \triangleleft t\)かつ\(s' < t\)であることと\(s \triangleleft t\)は同値である。
  3. \(s = s_1 \oplus s_2\)を満たす\((s_1,s_2) \in PT \times T\)が存在するならば、\(s_1 \triangleleft t\)かつ\(s_2 \triangleleft t\)と\(s \triangleleft t\)は同値である。

部分集合\(OT \subset T\)を以下のように再帰的に定める(すなわち以下を満たす最小の部分集合である):

  1. \(0,\Omega \in OT\)である。
  2. いかなる\(s \in T\)に対しても、\(s \triangleleft s\)ならば、\(D(s) \in OT\)である。
  3. \(2\)以上のいかなる整数\(m\)と\((s_i)_{i=1}^{m} \in (OT \cap PT)^m\)に対しても、\((s_i)_{i=1}^{m}\)が\(<\)に関して広義単調減少ならば、\((s_i)_{i=1}^{m}\)の\(\oplus\)による結合は\(OT\)に属す。(言い換えると、いかなる\(m \geq 2\)と\(s_1,\ldots,s_m \in OT \cap PT\)に対しても、「\(m\)未満のいかなる正整数\(i\)に対しても\(s_{i+1} < s_i\)または\(s_{i+1} = s_i\)」が成り立つならば、\(s_1 \oplus \cdots \oplus s_m \in OT\)である。)


\(<\)の\(OT\)への制限は整列順序である。このことを示すために、\(s \in T\)に対し順序数\(o(s)\)を以下のように再帰的に定める:

  1. \(s = 0\)ならば、\(o(s) = 0\)である。
  2. \(s = \Omega\)ならば、\(o(s) = \omega_1\)である。
  3. ある\(s' \in T\)を用いて\(s = D(s')\)と表せるならば、\(o(s) = \psi(o(s'))\)である。
  4. ある\(s_1 \in PT\)と\(s_2 \in T\)を用いて\(s = s_1 \oplus s_2\)と表せるならば、\(o(s) = o(s_1) + o(s_2)\)である。

ここで注意すべきであることは、この再帰は\(<\)に関する超限再帰ではなく、\(T\)の構文に関する木構造(または文字列の長さ)に関する再帰であるということである。実際、\(<\)の整礎性はまだ証明していないため、\(<\)の整礎性を証明するために導入している\(o\)の定義で\(<\)に関する超限再帰を行うことは致命的な循環論法となる。ちなみに\(T\)の構文に関する木構造(または文字列の長さ)を用いた再帰は\(OT\)や\(<\)の再帰的定義にも用いている。この辺が分からなかった場合は文字列に対する再帰的定義をうまく理解していない可能性があるので、何故\(OT\)や\(<\)が再帰的に定義できているか(\(OT\)に属するか否かや\(<\)が成り立つか否かを判定するアルゴリズムが存在するか)を確かめると良い。

さて、\(\psi\)と\(OT\)の再帰的定義から\(s,t \in OT\)に対し\(s < t\)と\(o(s) \in o(t)\)が同値となる。従って、\(\in\)の整礎性から\(<\)の\(OT\)への制限は整列順序である。




このように、OCFを用いて直接表記系\(T\)を構成し、それに\(\in\)の(原始)再帰的翻訳となる関係\(<\)を定義することで順序数表記\((OT,<)\)を得ることが出来ました。\(OT\)や\(<\)の定義をどうしてこうしたかが一番理解し難いところだと思いますが、

  1. 順序数の表示を(降順とは限らない)\(+\)と\(\psi\)を用いて定義し、表示が標準形であることを\(+\)の降順性で再帰的に定義する。
  2. 順序数の\(\in\)関係を、標準形表示における\(+\)と\(\psi\)の中身の関係で再帰的に記述し、それを文字列の再帰的関係に\(o\)を通じて翻訳することで\(<\)を\(T\)全体で再帰的に定義する。(ただし\(T\)全体では\(o\)に代入して得られる順序数の自然な表示が標準形とならないため、この翻訳では\(s < t\)と\(o(s) \in o(t)\)が同値にならないことに注意する)
  3. 順序数の表示が標準形であるという\(\in\)を用いて再帰的に判定可能な性質を、\(<\)を用いて再帰的に判定可能な文字列の性質に\(o\)を通じて翻訳することで\(OT \subset T\)を再帰的に定義する。(\(OT\)に制限して初めて\(o\)に代入して得られる順序数の自然な表示が標準形表示となるため、\(s < t\)と\(o(s) \in o(t)\)が同値になる)

という手順を踏んでいます。こういう手順をきちんと命題の形で書いて証明したものはOCFが複雑になるほどかなり長くなりますので、興味がある人はBuchholzやRathjenの論文を読んでみましょう。今回のOCFはだいぶ簡単なので、自力で証明に挑戦してみるのも理解が深まって良いと思います。


強さ

I need to add an explanation of what the strength of an ordinal notation \((OT,<)\) is. Almost all ordinal notations are constructed by using an OCF. and then we have a canonical map \(o\) as explained above. Be careful. The strength of \((OT,<)\) is not the limit of \(o(a)\)'s, but is the ordinal type of \((OT,<)\). Also, the strength of the segment \((\{b \in OT \mid b < a\},<)\) of \((OT,<)\) below \(a \in OT\) is not necessarily \(o(a)\) or \(\sup_{b < a} o(b)\), but is the ordinal type of the segment.

For example, consider the ordinal notation below:

ordinal term \(a\) \(0\) \(00\) \(000\) \(0000\) \(00000\) \(000000\) \(0000000\) \(\cdots\)
ordinal \(o(a)\) \(0\) \(\varepsilon_0\) \(\varepsilon_0 \times 2\) \(\varepsilon_0 \times 3\) \(\varepsilon_0 \times 4\) \(\varepsilon_0 \times 5\) \(\varepsilon_0 \times 6\) \(\cdots\)

The order \(<\) associated to \((o,\in)\) is just the comparison of the length, and hence the strength of \((OT,<)\) is \(\omega\), but not \(\varepsilon_0 \times \omega\).

In order to ensure that the strength of \((OT,<)\) is actually the limit of \(o(a)\)'s, we need to show that \(o\) gives a one-to-one correspondence to the limit. Recall that when we use cardinals, the limit obviously goes beyond \(\omega_1\), and hence is not bijective with a countable set \(OT\).

We often consider a segment of \((OT,<)\). Suppose that \(o(W) = \Omega\) for some \(W \in OT\). By the reason above, the strength of the segment below \(W\) is not \(\Omega\). Then you may expect that the strength of the segment below \(a \in OT\) is actually the limit of \(o(b)\)'s with \(b < a\). As I said above, it is also incorrect. Look at the table above again. The limit of \(o(b)\)'s with \(b < 000\) is \(\varepsilon_0\), but the ordinal type of the segment is just \(2\).

As a consequence, the limit of values of \(o\) is not necessarily the strength of the segment. At least, only when you proved that \(o\) gives a one-to-one correspondence between the segment below \(a\) and the limit of \(o(b)\)'s with \(b < a\), the strength coincides with the limit.

Remember that we used \(C_{\kappa}^0\) in the construction of an OCF. If \(C_{\kappa}^0\) contains a large ordinal \(\gamma\) as a subset, then values of \(\psi_{\kappa}\) always go beyond \(\gamma\). Then the system loses the presentability of ordinals by expressions of normal form using \(\psi\)'s. As a result, \(o\) enjoys awfully many skippings below \(\Omega_1\). Then the strength of \((OT,<)\) is seriously reduced, because \(o\) does not give a one-to-one correspondence between a segment and the limit.

Therefore in order to ensure the strength of \((OT,<)\), we need to be very careful to control the growth of an OCF, so that \(o\) spreads ordinal terms into sufficiently large countable ordinals without skippings. Also, this tells us why defining the notion of normal form is so useful to define an ordinal notation. If we have a canonical way to express sufficiently large countable ordinals, then it automatically ensures that \(o\) is surjective onto those.


その他の構造

Given an ordinal notation system \((OT,<)\), you can define a map \(o_{(OT,<)}\) just by assigning each \(s \in OT\) to the ordinal type of the segment below \(s\) as I explained above. Therefore, an ordinal notation system canonically forms a notation with a correspondence to ordinals.

For the purpose to apply FGH, it is better to equip a system of fundamental sequences with an ordinal notation system. If whether a term is successor or not can be determined in a recursive way, you can define a fundamental sequence of each non-zero limit term \(a\) by recursively numbering all terms and setting \(a[n]\) as the \(n\)-th successor of the greatest term below \(a\) which is zero or whose corresponding number is smaller than \(n\) with respect to the fixed numbering.

We note that this method works even when the numbering is a finitely multi-valued, and depends on \(a\). In other words, given a recursive map \begin{eqnarray*} S \colon OT \times \mathbb{N} & \to & \textrm{FinSub}(OT) \setminus \{\emptyset\} \\ (a,n) & \mapsto & S_{a,n} \end{eqnarray*} with \(\{a' \in OT \mid a' < a\} \subset \bigcup_{n \in \mathbb{N}} S_{a,n}\), where \(\textrm{FinSub}(OT)\) denotes the set of finite subsets of \(OT\), we can define a recursive system of fundamental sequence for \(OT\) as \begin{eqnarray*} [] \colon OT \times \mathbb{N} & \to & OT \\ (a,n) & \mapsto & a[n] := \max \{a' \in OT \mid a' < a \land a' \in S_{a,n}\} \end{eqnarray*} under a mild assumption which ensures that \(a[n]\) is strictly increasing on \(n \in \mathbb{N}\) for any \(a \in OT\) corresponding to a limit ordinal.

For example, a norm function[1] gives a typical exmaple of such an \(S\). We can construct a norm function using the length map \(\textrm{Lng} \colon OT \to \mathbb{N}\), if it makes sense, i.e. the length of an expression is not ambiguous. The resulting map \(S\) is given as \begin{eqnarray*} OT \times \mathbb{N} & \to & \textrm{FinSub}(OT) \setminus \{\emptyset\} \\ (a,n) & \mapsto & \{a' \in OT \mid \textrm{Lng}(a') \leq \textrm{Lng}(a) + Nn\} \end{eqnarray*} for a constant \(N \in [1,\infty)\) under a mild condition. For example, I defined a recursive system of fundamental sequences for a side nesting notation here.

Of course, this construction of a system of fundamental sequences is not so intuitive that we can handle easily. Therefore it is better to define a system of fundamental sequences in more intuitive ways.

A similar construction works for an OCF, if we do not care about the computability of the resulting FGH. For example, I defined a system of fundamental sequences for an OCF based on a large cardinal given by applying \(\omega\) times the Mahlo operator for the class of weakly compact cardinals here.


順序数へ対応を持つだけの表記

It is a pair \((OT,o)\) of a set of \(OT\) of formal strings and a map \(o\) which assigns each \(s \in OT\) to an ordinal. Many googologists are confounding it with an ordinal notation system, but these two notions are completely different to each other.


目的

Unlike an ordinal notation, a notation with a correspondence to ordinals does not necessarily yield a computable large function. FGH? No way! If you do not have a surjectivity of \(o\), then FGH does not work even if you fixed a system of fundamental sequences. Of course, creating a notation with a correspondence itself is attractive for other purposes. For example, we can shortly express a known ordinal.

I emphasise that I do not mean that it is impossible to create a computable large function using a notation with a correspondence to ordinals. I just meant a simple application of the FGH construction does not necessarily work.For example, my notation with a correspondence to ordinals and a system of fundamental sequences introduced in my Japanese blog post yields a computable large function, even though it is not derived from an ordinal notation system. A summary of the resulting computatble large function is available here.

At least, you need careful arguments on specific system of fundamental sequences containing transfinite inductions along specific strict well-orderings in order to define a computable large function using a notation with a correspondence to ordinals. Therefore if you stated "Since I defined a notation of ordinals, I can create a computable large function by FGH", then it would be completely incorrect.


順序数表記との関係

An ordinal notation system \((OT,<)\) canonically forms a notation with a correspondence \(o_{(OT,<)}\) to ordinals. On the other hand, a notation system \(OT\) with a correspondence \(o\) to ordinals is not necessarily derived from an ordinal notation, i.e. there does not necessarily exists a (primitive) recursive strict well-ordering \(<\) on \(OT\) with \(o = o_{(OT,<)}\) does . For example, forgetting the strict well-ordering \(<\) from the notation system \((OT,<,o)\) above, you obtain a notation system with a correspondence to ordinals. Since the map \(o\) is not surjective onto \(\varepsilon_0 \times \omega\), it is not derived from an ordinal notation.

If you want to regard it as an ordinal notation, you need to define a (primitive) recursive strict well-ordering \(<\) on \(OT\) satisfying \(o = o_{(OT,<)}\) in an explicit way. As I emphasised above, defining the relation \(s_0 < s_1\) as \(o(s_1) < o(s_2)\) does not work. It is not necessarily recursive, and \(o\) does not necessarily coincide with \(o_{(OT,<)}\).


注意

Many googologists abbreviate \(o\). For example, if an \(s \in OT\) corresponding to an ordinal \(\alpha\), they often write \(s = \alpha\). Some of them just deleted \(o\) in order to type fast, but this abbreviation might cause beginner's confusion. Say, some others confound ordinals with symbols, and hence they regard the equality as a true relation.

Moreover, such an abbreviation might cause serious errors in the definition of the system itself. Therefore I strongly recommend to distinguish the equality as formal strings and the equality of the image of \(o\).


UNOCF

UNOCF is a well-known but ill-defined system. It is not fully formalised. At least, it is not a map at all, and hence is not an OCF. One solution is to deal UNOCF as a notation (whose underlyiing set \(OT\) is just a finite set because of the finiteness of its defining table) with a correspondence to known ordinals. Then it is not an ordinal notation, either. Therefore it does not yield a new ordinal, or a new computable large function.


基本列系を持つだけの表記

It is a pair \((OT,[])\) of a set of \(OT\) of formal strings and a (primitive) recursive function \begin{eqnarray*} [] \colon OT \times \mathbb{N} & \to & OT \\ (s,n) & \mapsto & s[n] \end{eqnarray*} satisfying several desired properties. What are desired properties? I explain details in the next subsection.


目的

I would like to focus on two main reasons for googologists to define a notation with a system of fundamental sequences:

  1. To generate a computable large number by applying FGH to it.
  2. To express a recursive large ordinal through the notation.

In order to explain what conditions you need to assume for these purposes, I introduce terminology:

  1. An \(s \in OT\) is said to be a {\it zero} if \(s = s[n]\) for any \(n \in \mathbb{N}\).
  2. An \(s \in OT\) is said to be a {\it successor} if \(s \neq s[0] = s[n]\) for any \(n \in \mathbb{N}\).
  3. An \(s \in OT\) is said to be a {\it limit} if \(s\) is not a successor.

For convenience, I would like to assume the following additinal conditions which helps us to determine whether an \(s \in OT\) is a successor or not:

  1. For any \(s \in OT\), \(s = s[0]\) implies that \(s\) is a zero.
  2. For any \(s \in OT\), \(s \neq s[0] = s[1]\) implies that \(s\) is a successor.

Now, it is time to consider what desired properties are.

To begin with, suppose that you want to generate a computable large number by applying FGH to it. For this purpose, you need to verify the termination of the resulting computable function. For this purpose, you need to construct a strict partial-ordering \(<\) on \(OT\) satisfying the following:

  1. For any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(s[n] < s\) holds.
  2. The relation \(<\) is well-founded.

Otherwise, FGH does not work even if it is described as if it is "recursively defined". The resulting computable function might not terminate. It is not so difficult to define \(<\) satisfying the first condition, but is very difficult to ensure the second condition. How could you? There are essentially two solutions:

  1. To create an ordinal notation \((OT,<)\) first, and define a system \([] \colon OT \times \mathbb{N} \to OT\) of fundamental sequences using the strict well-ordering itself such that for any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(s[n] < s\) holds.
  2. To create a map \(o \colon OT \to \textrm{On}\) such that for any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(o(s[n]) \in o(s)\) holds.

In particular, you do not have to mind such a strict partial ordering if you have already acquired a well-defined ordinal notation or a well-defined correspondence to ordinals satisfying the condition above. But if you do not have, it is a serious problem.

Several googologists state "Do I need an ordinal notation? Ok. Since I defined a system of fundamental sequences, it expresses ordinals!" Wait. It is a serious circular logic. A system of fundamental sequence does not necessarily yield a structure of an ordinal notation, unless you have a desired strict partial ordering. Therefore it is impossible to use the resulting "ordinal notation" in order to define such a strict partial ordering. For more details, see the relation to an ordinal notation.

Several other googologists state "Since it is impossible for me to define an ordinal notation or a correspondence to ordinals, I just define a system of fundamental sequences. It is very strong, and yields a computable large function obviously larger than extensions of BEAF, BMS, DAN, and so on!" Wait. It is far from a solution. If you do not have a desired strict partial ordering, you have no evidence of the termination of FGH. Actually, there are many elementary counterexamples of a system of fundamental sequences (without such a desired strict partial ordering) such that FGH is ill-defined. Is that what you really want? Even though you have an analysis table with \(10000\) entries, it can never be an evidence of the termination because sufficiently complicated system of fundamental sequences might yield an infinite loop after \(10^{100}\) entries. Nevertheless, should we search for an explicit infinite loop in order to point out the absence of the evidence of the termination?

Next, suppose that you want to express a recursive large ordinal through the notation. Then you need a strict partial-ordering \(<\) on \(OT\) satisfying the same conditions above, too. For more details, see the relation to a notation with a correspondence to ordinals.

Several googologists state "Since it is impossible for me to define an ordinal notation or a correspondence to ordinals, I just define a system of fundamental sequences. It is very strong, and goes beyond any notations which I know!" Wait. As I wrote above, a system of fundamental sequences without a desired strict partial ordering does not necessarily express ordinals. In addition, even if you have a desired ordinal notation or a desired correspondence to ordinals, the notation with a system of fundamental system does not express ordinals beyond the expression limit of the stuff. Therefore, it is impossible for you to express all ordinals below a fixed ordinal beyond the limits of existing well-defined notations.

By the reason above, a notation with a system of fundamental sequence (without a proof of the specific property above) rarely yields a computable large function. On the other hand, an ordinal notation (NOT just a notation) with a fundamental sequence is great. By the well-foundedness of the ordering, it gives a well-defined FGH as long as the system of fundamental sequences satisfies the desired properties above. Such a system of fundamental sequences always exists by the construction here, and hence ordinal notation system is very useful in googology.

Of course, I do not mean that it is impossible to create a computable large function from a notation with fundamental sequences which is not equipped with a suitable well-founded partial ordering. As I wrote above, I created a computable large function using a notation with a correspondence to ordinals and a system of fundamental sequences.

At least, you need careful arguments containing transfinite inductions along specific desired strict partial orderings. Therefore if you stated "Since I defined a system of fundamental sequence, I can generate a computable large number by FGH" without such arguments, then the logic is completely incorrect.


順序数表記との関係

An ordinal notation system \((OT,<)\) (canonically and non-canonically) forms a notation with a system of fundamental sequences. On the other hand, does it naturally form an ordinal notation system? For example, how about defining the relation \(s_0 < s_1\) by the property that there exists a finite sequence \((n_0,n_1,\ldots,n_k)\) of natural numbers satisfying \(s_0 = s_1[n_0][n_1] \cdots [n_k]\)? Unfortunately, the relation does not necessarily recursive, because the searching process does not necessarily terminates. On the other hand, if the relation is a strict total ordering as a result, then it is recursive. Therefore you need to show that the relation is a total ordering first. In order to verify it, you need to show the anti-symmetry, which is equivalent to the non-existence of an infinite loop, i.e. \(s \neq s[n_0][n_1] \cdots [n_k]\) for any non-zero \(s \in OT\) and any finite sequence \((n_0,n_1,\ldots,n_k)\) of natural numbers. We only have the following two generic strategies to verify the property:

  1. Define another (not necessarily recursive) strict well-ordering \(\prec\) on \(OT\) satisfying \(s[n] \prec s\) for any \(s \in OT\) with \(s \neq z\) and any natural number \(n\).
  2. Define a map \(f \colon OT \to OT'\) to another notation \(OT'\) with a system of fundamental sequences whose halting problem has already been solved satisfying that for any \(s \in OT\) and any natural number \(n\), there is a natural number \(n'\) with \(f(s[n]) = f(s)[n']\).

In the first strategy, you need a correspondence \(o\) to ordinals and an OCF compatible to your system in the sense that \([]\) actually gives the system of fundamental sequences of the image of \(o\). Then it would be better to define an ordinal notation from the beginning. Well, since you did not choose the way (you have created a notation with fundamental sequences but not an ordinal notation), I guess that you do not have such a compatible OCF.

In the second case, we need to use a known halting system. Therefore even if you can show the halting problem in this way, the resulting large function obtained by FGH seems not to go beyond a known one.

As a conclusion, if you could verify that \(<\) is a strict well-ordering, then your function does not grow so fast unless you are a set theorist who can create a new OCF. Therefore defining \(<\) in this way is not a good strategy for the use of googology. Instead, it is better to define \(<\) in another distinct way, and to verify the two properties which I listed here.


順序数へ対応を持つだけの表記との関係

Let \((OT,[])\) be a notation with a system of fundamental sequences satisfying several desired properties. Then does the following "recursive definition" of a map \(o \colon OT \to \textrm{On}, \ s \mapsto o(s)\) work?

  1. If \(s\) is a zero, then \(o(s) := 0\).
  2. If \(s\) is a successor, then \(o(s) := o(s[0]) + 1\).
  3. If \(s\) is a non-zero limit, then \(o(s) := \sup_{n \in \mathbb{N}} o(s[n])\).

The answer depends on what "desired" properties are. If you have a partial well-ordering on \(OT\) satisfying desired properties explained in the beginning of this section. then \(o\) is well-defined. Otherwise, \(o\) might be ill-defined. Actually, there are many elementary counterexamples. Several googologists state "Of course, I have a desired partial ordering defined by \(s < t \Leftrightarrow o(s) \in o(t)\)." Wait. It is a circular logic. You need a desired partial ordering in order to verify the well-definedness of \(o\), and hence defining a partial ordering using \(o\) itself is obviously invalid for this purpose.

For example, if \((OT,[])\) forms a tree in the sense explained here, then the binary relation \(<\) defined in the previous section forms a well-founded strict partial orderring, and hence the transfinite induction along \(<\) proves the well-definedness of \(o\). Therefore the "corresponding ordinal" always makes sense as long as we assume that \((OT,[])\) forms a tree. Of course, it is quite difficult to show that \((OT,[])\) forms a tree. Needless to say, using the well-foundedness of \(o\) in the proof that \((OT,[])\) forms a tree is an obvious circular logic, because we used the assumption that \((OT,[])\) forms a tree in order to ensure the well-definedness of \(o\).


注意

The system of fundamental sequences should be defined as a map \(OT \times \mathbb{N} \to OT\), but not a function symbol which is used in order to define \(OT\). The following is a bad example:

  1. Every natural number \(n\) belongs to \(OT\).
  2. For any integer \(n > 1\) and any finite sequence \(s_0,\ldots,s_{n-1}\) of length \(n\) in \(OT\), \(s_0 + \cdots + s_{n-1}\) belongs to \(OT\).
  3. For any \(s \in OT\), \(\omega^s\) belongs to \(OT\).
  4. For any \(s \in OT\) and any natural number \(n\), if \(s\) is expressed as \(\omega^t\) for some \(t \in OT\), then \(s[n]\) belongs to \(OT\).
  5. For any \(s \in OT\) and any natural number \(n\), if \(s\) is the sum of a finite sequence of length \(> 1\) whose rightmost entry is expressed as \(\omega^t\) for some \(t \in OT\), then \(s[n]\) belongs to \(OT\).

You might regard \((s[0],s[1],s[2],\ldots)\) as a fundamental sequence of \(s\), it does not work because they are just formal strings.

For example, you might add the follwing "rules":

  1. For any \(s \in OT\) and any natural number \(n\), \(\omega^{s + 1}[n] = \underbrace{\omega^s + \cdots + \omega^s}_n\).
  2. For any \(s \in OT\) and any natural number \(n\) such that \(s[n]\) is defined, \(\omega^s[n] = \omega^{s[n]}\).

They do not work, because the equalities are false. Both hand sides are just formal strings, and hence the equalities hold only when they coincide with each other as formal strings. If you want to state the coincidence of the "corresponding values as ordinals" in your mind, you need to define a correspondence \(o\) in a recursive way so that the following rules actually hold:

  1. For any \(s \in OT\) and any natural number \(n\), \(o(\omega^{s + 1}[n]) = o \left( \underbrace{\omega^s + \cdots + \omega^s}_n \right)\).
  2. For any \(s \in OT\) and any natural number \(n\) such that \(s[n]\) is defined, \(o(\omega^s[n]) = o(\omega^{s[n]})\).

The abbreviation of \(o\) is quite harmful as long as you deal with equalities of distinct formal strings. For more details, see the explanation here.


順序数に対する基本列系

It is a map which assigns an ordinal \(\beta[n]\) to each pair \((\beta,n)\) of an ordinal \(\beta\) below a fixed ordinal \(\alpha\) and an ordinal \(n\) below the cofinality of \(\beta\) satisfying similar conditions above.


目的

We want a large number!

Constructing a large countable ordinal below \(\alpha\) is not sufficient. We also need a system of fundamental sequences for ordinals below \(\alpha\) in oder to define (possibly uncomputable) large functions through FGH for ordinals below \(\alpha \cap \omega_1\).


表記との関係

A system of fundamental sequences for ordinals below \(\alpha\) naturally corresponds to a notation with a correspondence to ordinals in the case where \(\alpha \subset \omega_1\). Namely, the identity map forms a correspondence to ordinals.

On the other hand, a notation with a system of fundamental sequences in the sense above is required to be recursively defined. Therefore a system of fundamental sequences for ordinals below \(\alpha\) does not necessarily corresponds to a notation with a system of fundamental sequences even if we assume \(alpha \subset \omega_1\).


注意

If you want to define a computable large number, you need to interpret a system of fundamental sequences for ordinals into a notation with a system of fundamental sequences. Otherwise, the resulting large function might be uncomputable.

Also, "defining" a system of fundamental sequences by using expressions without defining appropriate normal forms does not make sense by the same reason as why "defining" OCFs by using expressions without defining appropriate normal forms does not make sense explained here.

One example is the following rule to define a system of fundamental sequences does not make sense:

  • For any non-zero countable limit ordinal \(\beta\) and any strictly increasing continuous function \(f\), the fundamental sequence \((f(\beta)[n])_{n=0}^{\infty}\) is defined as \((f(\beta[n]))_{n=0}^{\infty}\).

Since it is impossible to reconstruct \(f\) and \(\beta\) from the ordinal \(\gamma\) expressed as \(f(\beta)\), the use of \(f\) and \((\beta[n])_{n=0}^{\infty}\) in the definition of \((\gamma[n])_{n=0}^{\infty}\) is completely invalid.

Another example is the following rule to "define" of a system of fundamental sequences below \(\varepsilon_0\), which does not work:

  1. \((\alpha + \beta)[n] := \alpha + (\beta[n])\) for any ordinal \(\alpha\) and any non-zero limit ordinal \(\beta\)
  2. \((\alpha \times \beta)[n] := \alpha \times (\beta[n])\) for any ordinal \(\alpha\) and any non-zero limit ordinal \(\beta\)
  3. \(\omega[n] = n\)
  4. \(\omega^{\alpha + 1}[n] = \omega^{\alpha} \times n\) for any ordinal \(\alpha\)
  5. \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) for any non-zero limit ordinal \(\alpha\)

Since the right hand sides heavily depend on the non-canonical expressions of the left hand sides, which are not necessarily unique, the system is completely ill-defined. In order to avoid such a problem derived from the non-uniqueness, we usually restrict expressions to Cantor normal forms. Similarly, when you use expressions of ordinals by functions such as operators, Veblen functions, and OCFs, then you need to define the notion of a normal form which gives you a unique way to express a given ordinal by them.

Of course, if you want to define a recursive system of fundamental sequences, the notion of a normal form should also be defined in a recursive way. Although googologists often forget to set normal forms, this is one of the most important and the most difficult steps to study a recursive system of fundamental sequences by the same reason explained here.


参考文献

  1. Wilfried Buchholz, Adam Cichon, Andreas Weiermann, A Uniform Approach to Fundamental Sequences and Hierarchies, Mathematical logic quarterly, Volume40, Issue2, 1994.
Advertisement