ヴェブレン関数→ブーフホルツのψ関数→？

ヴェブレン関数とブーフホルツのψ関数には以下の事実が広く知られています。

• 適当な順序数\(a,b\)に対し\(\varphi_a(b) \approx \psi_0(\psi_1(0)^a \times b)\)という大雑把な近似関係がある。
• \(\psi\)は\(2\)変数で超限変数ヴェブレン関数を凌駕する。

ここでの「大雑把な近似」というのは変数が\(1\)ずれたりとか十分小さい値でしか成り立たないことを無視した近似ということです。さて、超限変数ヴェブレン関数が\(2\)変数ヴェブレン関数を「自然に」拡張していることから、１つ目の事実から２つ目の事実がある程度推測できることにお気付きでしょうか？

実際、１つ目の事実を繰り返し適用すると\(2\)変数ヴェブレン関数の入れ子もブーフホルツのψ関数の入れ子で大雑把に表すことができ、それによって\(3\)変数ヴェブレン関数の大雑把な近似式 \begin{eqnarray*} \varphi(a_1,a_0,c) \approx \psi_0(\psi_1(0)^{\psi_1(0) \times a_1 + a_0} \times b) \end{eqnarray*} を得ます。同様にカントール標準形と配列の対応により多変数ヴェブレン関数の大雑把な近似式 \begin{eqnarray*} \varphi(a_n,\cdots,a_0,b) \approx \psi_0(\psi_1(0)^{\psi_1(0)^n \times a_n + \cdots + \psi_1(0)^0 \times a_0} \times b) \end{eqnarray*} を得ます。従って多変数ヴェブレン関数で表記できる限界であるSVOが\(\psi_0(\psi_1(0)^{\psi_1(0)^{\omega}})\)で近似されることが推測され、同様に超限変数ヴェブレン関数で表記できる限界であるLVOが\(\psi_0(\psi_1(0)^{\psi_1(0)^{\psi_1(0)}})\)で近似されることが推測されるわけです。

さて、\(2\)変数関数であるヴェブレン関数がひとたび自然に\(3\)変数に拡張されるとそこからは大体同じ手順で超限変数へも拡張されたことと同様に、\(2\)変数関数であるブーフホルツのψ関数に付随する順序数表記が甘露東風さんに\(3\)変数に拡張されたことで大体同じ手順で超限変数ψ関数に拡張することができました。まだ実際に\(3\)変数ψと超限変数ψが整合的であるかどうかは確認していませんが、今回の記事では実際に整合的であるかどうかはあまり重要でないので気にしないことにしましょう。

ヴェブレン関数とブーフホルツのψ関数に関する上記の推論を踏まえると、もし新たな\(2\)変数関数\(\textrm{三}\)を

• 適当な順序数\(a,b\)に対し\(\psi_a(b) \approx \textrm{三}_0(\textrm{三}_1(0)^a \times b)\)という大雑把な関係がある。

を満たすように構成できれば、結果的に

• \(\textrm{三}\)は\(2\)変数で超限変数ブーフホルツのψ関数を凌駕する。

という事実が成り立つだろう推論できるわけです。つまり\(\varphi\)を\(\textrm{一}\)、\(\psi\)を\(\textrm{二}\)、と思った時の\(\textrm{三}\)に相当する関数を考えるということです。とはいえOCFとして作るのは少し手間が掛かりそうなので、今回は単に順序と基本列付きの表記として定義しようと思います。やっつけ仕事なのでバグがあったり意図通りの展開になっていなかったりするかもしれませんので、何かおかしいなと思ったら遠慮なくご指摘下さい。

表記

\(0\)と\(+\)と\(\textrm{三}\)と\((\)と\(,\)と\()\)のみからなる文字列の集合\(T\)と\(PT\)を以下のように同時に再帰的に定める：

1. \(0 \in T\)である。
2. いかなる\((a,b) \in PT \times (T \setminus \{0\})\)に対しても、\(a+b \in T\)である。
3. いかなる\((a,b) \in T^2\)に対しても、\(\textrm{三}(a,b) \in PT \cap T\)である。

例のごとく関数記号が嫌いな人は\(0\)を\(()\)で置き換え、\((a,b) \in PT \times (T \setminus \{0\})\)に対する\(a+b\)を\(ab\)で置き換え、\((a,b) \in T^2\)に対する\(\textrm{三}(a,b)\)を\(\langle a, b \rangle\)なり\((a)(b)\)なり\((a)_b\)なりで置き換えると良い。

略記

各\((a,b) \in T^2\)に対し、\(\textrm{三}(a,b)\)を\(\textrm{三}_a(b)\)と略記する。\(\textrm{三}_0(0)\)を\(\overline{1}\)と略記し、\(\textrm{三}_0(\overline{1})\)を\(\overline{\omega}\)と略記する。

順序

\(T\)上の\(2\)項関係\(s \leq t\)と\(s < t\)を以下のように同時に再帰的に定める：

\(s \leq t\)の定義

1. \(s = t\)ならば、\(s \leq t\)は真である。
2. \(s \neq t\)ならば、\(s \leq t\)は\(s < t\)と同値である。

\(s < t\)の定義

1. \(t = 0\)ならば、\(s < t\)は偽である。
2. \(t \neq 0\)かつ\(s = 0\)ならば、\(s < t\)は真である。
3. \(t \neq 0\)かつ\(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとする。
   1. \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s < t\)は以下のいずれかが成り立つことと同値である：
      1. \(a < c\)である。
      2. \(a = c\)かつ\(b < d\)である。
   2. \(t = \textrm{三}_c(d)\)を満たす\((c,d) \in T^2\)が存在するならば、\(s < t\)は\(a < t\)と同値である。
4. \(t \neq 0\)かつ\(s = \textrm{三}_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s < t\)は\(s \leq c\)と同値である。
   2. \(t = \textrm{三}_c(d)\)を満たす\((c,d) \in T^2\)が存在するならば、\(s < t\)は以下のいずれかが成り立つことと同値である；
      1. \(a < c\)である。
      2. \(a = c\)かつ\(b < d\)である。

要するに\(0\)と\(+\)と\(\textrm{三}\)と\((\)と\(,\)と\()\)を\(( < , < ) < 0 < + < \textrm{三}\)の順に整列させ文字列に辞書式順序を与えただけである。特に\(\leq\)は全順序である。

加法

計算可能全域写像 \begin{eqnarray*} \textrm{add} \colon T^2 & \to & T \\ (s,t) & \mapsto & \textrm{add}(s,t) \end{eqnarray*} を以下のように再帰的に定める：

1. \(s = 0\)ならば、\(\textrm{add}(s,t) := t\)である。
2. \(s \neq 0\)かつ\(t = 0\)ならば、\(\textrm{add}(s,t) := s\)である。
3. \(s \neq 0\)かつ\(t \neq 0\)ならば、\(\textrm{add}(s,t) := s+t\)である。

要するに\(<\)に関する加法である。\(\textrm{add}\)そのものは単射でないが、\(\textrm{add}\)の\(T \times PT\)への制限や\(s,t\)のうち一方を固定した写像は単射であり、それらの終域を像に制限して得られる全単射のの逆写像も計算可能である。

計算可能全域写像 \begin{eqnarray*} \textrm{succ} \colon T & \to & T \\ s & \mapsto & \textrm{succ}(s) \end{eqnarray*} を\(\textrm{succ}(s) := \textrm{add}(s,\overline{1})\)と定める。要するに\(<\)に関する後続である。

計算可能全域写像 \begin{eqnarray*} \textrm{sep}_0 \colon T^2 & \to & T \\ (s,t) & \mapsto & \textrm{sep}_0(s,t) \end{eqnarray*} を以下のように再帰的に定める：

1. \(s \in PT\)かつ\(t \leq s\)ならば、\(\textrm{sep}_0(s,t) := s\)である。
2. \(s = a+b\)かつ\(t \leq a\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(\textrm{sep}_0(s,t) := \textrm{add}(a,\textrm{sep}_0(b,t))\)である。
3. 上記のいずれの場合でもないならば、\(\textrm{sep}_0(s,t) := 0\)である。

要するに\(s\)が\(<\)に関する降順の和である場合に\(s\)のadditive principal成分のうち\(t\)以上のものである。

\begin{eqnarray*} \textrm{sep}_1 \colon T^2 & \to & T \\ (s,t) & \mapsto & \textrm{sep}_1(s,t) \end{eqnarray*} を以下のように再帰的に定める：

1. \(s \in PT\)かつ\(s < t\)ならば、\(\textrm{sep}_1(s,t) := s\)である。
2. \(s = a+b\)かつ\(b < t\)を満たす\((a,b) \in T \times PT\)が存在するならば、\(\textrm{sep}_1(s,t) := \textrm{add}(\textrm{sep}_1(a,t),b)\)である。
3. 上記のいずれの場合でもないならば、\(\textrm{sep}_1(s,t) := 0\)である。

要するに\(s\)が\(<\)に関する降順の和である場合に\(s\)のadditive principal成分のうち\(t\)未満のものである。

共終数

計算可能全域写像 \begin{eqnarray*} \textrm{dom} \colon T & \to & T \\ s & \mapsto & \textrm{dom}(s) \end{eqnarray*} を以下のように再帰的に定める：

1. \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
3. \(s = \textrm{三}_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)とする。
      1. \(\textrm{dom}(a) \in \{0,\overline{1}\}\)ならば、\(\textrm{dom}(s) := s\)である。
      2. \(\textrm{dom}(a) \notin \{0,\overline{1}\}\)ならば、\(\textrm{dom}(s) := \textrm{dom}(a)\)である。
   2. \(\textrm{dom}(b) = \overline{1}\)ならば、\(\textrm{dom}(s) := \overline{\omega}\)である。
   3. \(\textrm{dom}(b) \notin \{0,\overline{1}\}\)とする。
      1. \(\textrm{dom}(b) < s\)ならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
      2. \(s \leq \textrm{dom}(b) \neq \textrm{三}_{\textrm{succ}(a)}(0)\)ならば、\(\textrm{dom}(s) := \overline{\omega}\)である。
      3. \(\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(a)}(0)\)ならば、\(\textrm{dom}(s) := s\)である。

\(\textrm{dom}\)の定義3-3-3がブーフホルツのψ関数に付随する順序数表記との相違点である。横ネストの好きな人達は\(\textrm{三}_{\textrm{succ}(a)}(0)\)だけでなく\(\textrm{三}_{\textrm{succ}(a)+\overline{1}}(0)\)なども例外処理をする方向での拡張を考えたいだろうが、定義の発散を防ぐため今回は考えないことにする。

\(\textrm{dom}\)の像は定義から、 \begin{eqnarray*} \{0,\overline{1},\overline{\omega}\} \cup \{\textrm{三}_{\textrm{succ}(c)}(0) \mid c \in T\} \cup \{\textrm{三}_c(d) \mid (c,d) \in T^2 \land \textrm{dom}(d) = \textrm{三}_{\textrm{succ}(c)}(0)\} \end{eqnarray*} と一致する。この第\(3\)項目がブーフホルツのψ関数に付随する順序数表記との相違点である。

基本列

計算可能全域写像 \begin{eqnarray*} \textrm{subst}_0 \colon T^5 & \to & T \\ (s,t,e,e',f) & \mapsto & \textrm{subst}_0(s,t,e,e',f) \end{eqnarray*} と \begin{eqnarray*} \textrm{subst}_1 \colon T^3 & \to & T \\ (s,t,c) & \mapsto & \textrm{subst}_1(s,t,c) \end{eqnarray*} と \begin{eqnarray*} [ \ ] \colon T^2 & \to & T \\ (s,t) & \mapsto & s[t] \end{eqnarray*} を以下のように同時に再帰的に定める：

\(\textrm{subst}_0(s,t,e,e',f)\)の定義

1. \(s = 0\)ならば、\(\textrm{subst}_0(s,t,e,e',f) := 0\)である。
2. \(s = \textrm{三}_a(0)\)を満たす\(a \in T\)が存在するとする。
   1. \(a = \textrm{succ}(e)\)ならば、\(\textrm{subst}_0(s,t,e,e',f) := \textrm{三}_e(t)\)である。
   2. \(a \neq \textrm{succ}(e)\)ならば、\(\textrm{subst}_0(s,t,e,e',f) := \textrm{三}_{\textrm{subst}_0(a,t,e,e',f)}(0)\)である。
3. \(s = \textrm{三}_a(\textrm{add}(b,\textrm{三}_c(d)))\)を満たす\((a,b,g,h) \in T^4\)が存在するとする。
   1. \(c = \textrm{succ}(e)\)かつ\(d = 0\)とする。
      1. \(t = \textrm{add}(t',\textrm{三}_{e'}(\textrm{add}(f,d')))\)を満たす\((t',d') \in T^2\)が存在するならば、\(\textrm{subst}_0(s,t,e,e',f) := \textrm{add}(\textrm{subst}_0(s,t',e,e',f),\textrm{三}_a(\textrm{add}(b,d')))\)である。
      2. そうでないならば、\(\textrm{subst}_0(s,t,e,e',f) := 0\)である。
   2. \(c \neq \textrm{succ}(e)\)または\(d \neq 0\)ならば、\(\textrm{subst}_0(s,t,e,e',f) := \textrm{三}_a(\textrm{subst}_0(\textrm{add}(b,\textrm{三}_c(d)),t,e,e',f))\)である。
4. \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(\textrm{subst}_0(s,t,e,e',f) := \textrm{add}(a,\textrm{subst}_0(b,t,e,e',f))\)である。

要するに\(s\)の部分文字列であって\(\textrm{三}_{e'}(\textrm{add}(b',\textrm{三}_{\textrm{succ}(e)}(0))\)の形をしているもののうち最も右に位置するものを形式的に\(\textrm{三}_{\textrm{succ}(e)}(b') \times \textrm{三}_{\textrm{succ}(e)}(0)\)とみなしこの\(\textrm{三}_{\textrm{succ}(e)}(0)\)部分に\(t\)の\(\textrm{三}_{\textrm{succ}(e)}(f)\)に関するカントール標準形の係数を代入するものである。ただし\(\textrm{subst}_0(\textrm{三}_1(\textrm{三}_0(\textrm{三}_1(0))),\textrm{三}_1(\textrm{三}_0(0)),0,0)\)なども扱えると便利なので便宜的に\(\textrm{三}_e(\textrm{add}(b',\textrm{三}_{\textrm{succ}(e)}(0))\)の形にも適用可能にしている。

\(\textrm{subst}_1(s,t,c)\)の定義

1. \(s = \textrm{add}(s',\textrm{三}_{\textrm{add}(a,\textrm{三}_e(f))}(0))\)かつ\(t = \textrm{add}(s',\textrm{三}_{\textrm{add}(a,\textrm{三}_{e'}(f'))}(0))\)を満たす\((s',a,e,f,e',f') \in T^6\)が存在するとする。
   1. \(e = c\)ならば、\(\textrm{subst}_1(s,t,c) := \textrm{add}(s',\textrm{三}_{\textrm{add}(a,\textrm{三}_c(f[\textrm{三}_c(t)]))}(0))\)である。
   2. \(e \neq c\)ならば、\(\textrm{subst}_1(s,t,c) := \textrm{add}(s',\textrm{三}_{\textrm{subst}_1(\textrm{add}(a,\textrm{三}_e(f)),\textrm{add}(a,\textrm{三}_{e'}(f')),c)}(0))\)である。
2. \(s = \textrm{add}(s',\textrm{三}_a(\textrm{add}(b,\textrm{三}_e(f))))\)かつ\(t = \textrm{add}(s',\textrm{三}_a(\textrm{add}(b,\textrm{三}_{e'}(f'))))\)を満たす\((s',a,b,e,f,e',f') \in T^7\)が存在するとする。
   1. \(e = c\)ならば、\(\textrm{subst}_1(s,t,c) := \textrm{subst}_0(s,t,c,a,\textrm{sep}_0(b,\textrm{三}_{\textrm{succ}(c)}(0)))\)である。
   2. \(e \neq c\)ならば、\(\textrm{subst}_1(s,t,c) := \textrm{add}(s',\textrm{三}_a(\textrm{subst}_1(\textrm{add}(b,\textrm{三}_e(f)),\textrm{add}(b,\textrm{三}_{e'}(f')),c)))\)である。
3. 上記のいずれの場合でもないならば、\(\textrm{subst}_1(s,t,c) := 0\)である。

要するに\(s\)の部分文字列であって\(\textrm{add}(b,\textrm{三}_c(d))\)と表せるもののうち適切な意味で極大なものの１つ外側の\(\textrm{三}\)をadditive principal成分に含む最大の項を取り出し、それに\(\textrm{subst}_0\)を適用するものである。なお基本列の計算時には分岐3を通らない想定である。

\(s[t]\)の定義

1. \(s = 0\)ならば、\(s[t] := 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとし、\(b' := b[t]\)と置く。
   1. \(b' = 0\)ならば、\(s[t] := a\)である。
   2. \(b' \neq 0\)ならば、\(s[t] := a + b'\)である。
3. \(s = \textrm{三}_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)とする。
      1. \(\textrm{dom}(a) \in \{0,\overline{1}\}\)ならば、\(s[t] := t\)である。
      2. \(\textrm{dom}(a) \notin \{0,\overline{1}\}\)ならば、\(s[t] := \textrm{三}_{a[t]}(0)\)である。
   2. \(\textrm{dom}(b) = \overline{1}\)とする。
      1. \(t = t[0] + \overline{1}\)ならば、\(s[t] := s[t[0]] + s[\overline{1}]\)である。
      2. \(t \neq t[0] + \overline{1}\)ならば、\(s[t] := \textrm{三}_a(b[0])\)である。
   3. \(\textrm{dom}(b) \notin \{0,\overline{1}\}\)とする。
      1. \(\textrm{dom}(b) < s\)ならば、\(s[t] := \textrm{三}_a(b[t])\)である。
      2. \(s \leq \textrm{dom}(b) = \textrm{三}_{\textrm{succ}(c)}(0)\)かつ\(a < c\)を満たす\(c \in T\)が存在するとする。
         1. \(t = \textrm{succ}(t[0])\)かつ\(s[t[0]] = \textrm{三}_a(b')\)を満たす\(b' \in T\)が存在するならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(b')])\)である。
         2. そうでないならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(0)])\)である。
      3. \(s \leq \textrm{dom}(b) = \textrm{三}_c(d)\)かつ\(\textrm{dom}(d) = \textrm{三}_{\textrm{succ}(c)}(0)\)を満たす\(d \in T\)が存在するとする。
         1. \(t = \textrm{succ}(t[0])\)かつ\(s[t[0]] = \textrm{三}_a(b')\)を満たす\(b' \in T\)が存在するとする。
            1. \(\textrm{sep}_1(b',\textrm{三}_{\textrm{succ}(c)}(0)) = 0\)ならば、\(s[t] = \textrm{三}_a(\textrm{subst}_1(b,b',c))\)である。
            2. \(\textrm{sep}_1(b',\textrm{三}_{\textrm{succ}(c)}(0)) \neq 0\)ならば、\(s[t] = \textrm{三}_a(b[\textrm{三}_c(d[\textrm{sep}_1(b',\textrm{三}_{\textrm{succ}(c)}(0))])])\)である。
         2. そうでないならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(d[0])])\)である。
      4. そうでないならば、\(s[t] := t\)である。

ブーフホルツのψ関数に付随する順序数表記の上に定める各種基本列との重要な違いは、\(\textrm{dom}\)の定義3-3-3により\(\textrm{三}_0(\textrm{三}_1(0))\)などが正則基数の役割を持つため基本列の定義3-3-2が通常のネストと違い１段深いネストになっていることで、これはゆきとさんのψ関数を横ネストするアイデアにも通ずるところであると思う。

形式化

計算可能全域写像 \begin{eqnarray*} \ulcorner \bullet \urcorner \colon \mathbb{N} & \mapsto & T \\ n & \mapsto & \ulcorner n \urcorner \end{eqnarray*} を以下のように再帰的に定める：

1. \(n = 0\)ならば、\(\ulcorner n \urcorner := 0\)である。
2. \(n = 1\)ならば、\(\ulcorner n \urcorner := \overline{1}\)である。
3. \(n \notin \{0,1\}\)ならば、\(\ulcorner n \urcorner := \ulcorner n-1 \urcorner + \overline{1}\)である。

形式化を経由することにより基本列を自然数にも適用できるようになる。

急増加関数

計算可能部分写像 \begin{eqnarray*} F \colon T \times \mathbb{N} \times \mathbb{N} & \to & \mathbb{N} \\ (s,m,n) & \mapsto & F_s^m(n) \end{eqnarray*} を以下のように再帰的に定める：

1. \(m = 0\)ならば、\(F_s^m(n) := n\)である。
2. \(m = 1\)とする。
   1. \(\textrm{dom}(s) = 0\)ならば、\(F_s^m(n) := n+1\)である。
   2. \(\textrm{dom}(s) = \overline{1}\)ならば、\(F_s^m(n) := F_{s[0]}^n(n)\)である。
   3. \(\textrm{dom}(s) \notin \{0,\overline{1}\}\)ならば、\(F_s^m(n) := F_{s[\ulcorner n \urcorner]}(n)\)である。
3. \(m \notin \{0,1\}\)ならば、\(F_s^m(n) := F_s^1(F_s^{m-1}(n))\)である。

要するにFGHである。

限界関数

計算可能全域写像 \begin{eqnarray*} \Lambda \colon \mathbb{N} & \to & T \\ n & \mapsto & \Lambda(n) \end{eqnarray*} を以下のように再帰的に定める：

1. \(n = 0\)ならば、\(\Lambda(n) := 0\)である。
2. \(n \neq 0\)ならば、\(\Lambda(n) := \textrm{三}_{\Lambda(n-1)}(0)\)である。

\(T\)において\(\sup_{n \in \mathbb{N}} \textrm{三}_0(\textrm{三}_0(\Lambda(n))) = \textrm{三}_0(\textrm{三}_{\overline{1}}(0))\)が成り立つ。

計算可能部分写像 \begin{eqnarray*} \textrm{lim}_{\textrm{三}} \colon \mathbb{N} & \to & T \\ n & \mapsto & \textrm{lim}_{\textrm{三}}(n) \end{eqnarray*} を\(F_{\textrm{三}_0(\textrm{三}_0(\Lambda(n))) }^1(n)\)と定め、計算可能部分関数 \begin{eqnarray*} \textrm{Lim}_{\textrm{三}} \colon \mathbb{N} & \to & T \\ n & \mapsto & \textrm{Lim}_{\textrm{三}}(n) \end{eqnarray*} を\(\textrm{lim}_{\textrm{三}}^n(n)\)と定める。

標準形

部分集合\(OT \subset T\)を以下のように再帰的に定める：

1. いかなる\(n \in \mathbb{N}\)に対しても、\(\textrm{三}_0(\textrm{三}_0(\Lambda(n))) \in OT\)である。
2. いかなる\((s,n) \in OT \times \mathbb{N}\)に対しても、\(s[\ulcorner n \urcorner] \in OT\)である。

定義から\(OT\)は再帰的枚挙可能だが、再帰的であるかどうかは不明である。期待としては\((OT,<)\)が順序数表記となること、すなわち\(OT\)が再帰的かつ\(<\)の\(OT\)への制限が整列順序となってほしい。

解析

長くなったので記事を分けました。三関数観察日記をご参照下さい。