三関数

三関数^[1]は p進大好きbot^[2] が2020年12月25日に公開した巨大数表記である。この表記はkanrokoti^[3]とNaruyoko^[4]によって誤植や意図通りでない挙動が指摘され^[5]^[6]定義が修正されているためいくつかの版が存在するが、以下はこの記事が作成された2021年9月13日時点での最新の版^[7]のコピーであり、最新版^[1]とは異なる^[8]ことに注意する必要がある。

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

適当な順序数\(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\)変数関数であるブーフホルツのψ関数に付随する順序数表記がKanrokoti^[9]に\(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{三}\)に相当する関数を考えるということになる。

表記[]

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

\(0 \in T\)である。
いかなる\((a,b) \in PT \times (T \setminus \{0\})\)に対しても、\(a+b \in T\)である。
いかなる\((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\)の定義

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

\(s < t\)の定義

\(t = 0\)ならば、\(s < t\)は偽である。
\(t \neq 0\)かつ\(s = 0\)ならば、\(s < t\)は真である。
\(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\)と同値である。
\(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{succ} \colon T & \to & T \\ s & \mapsto & \textrm{succ}(s) \end{eqnarray*} を以下のように再帰的に定める：

\(s = 0\)ならば、\(\textrm{succ}(s) := \overline{1}\)である。
\(s \neq 0\)ならば、\(\textrm{succ}(s) := s + \overline{1}\)である。

要するに\(<\)に関する後者を取る写像である。

共終数[]

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

\(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
\(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
\(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*} [ \ ] \colon T^2 & \to & T \\ (s,t) & \mapsto & s[t] \end{eqnarray*} を以下のように再帰的に定める：

\(s = 0\)ならば、\(s[t] := 0\)である。
\(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'\)である。
\(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) \neq \textrm{三}_{\textrm{succ}(a)}(0)\)とする。
    1. \(\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)])\)である。
    2. \(\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\)が存在するとする。
        \(\beta \in T\)を以下のように定める：
        \(b' = b_0+\cdots+b_k\)かつ\(i < k\)かつ\(\textrm{dom}(d) \leq b_i\)を満たす\((i,k) \in \mathbb{N}^2\)と\((b_0,\ldots,b_k) \in PT^{k+1}\)が存在するならば、そのような\(i\)の最大値を\(i_0\)と置くと、\(\beta := b_{i_0+1}+\cdots+b_k\)である。
        
        そうでないならば、\(\beta := b’\)である。
        
        \(\Gamma \in T\)を以下のように定める：
        \(\beta < \textrm{dom}(d)\)ならば、\(\Gamma := \textrm{三}_c(d[\beta])\)である。
        
        \(\textrm{dom}(d) \leq \beta\)ならば、\(\Gamma := \textrm{三}_c(d[\textrm{三}_c(\beta)])\)である。
        
        \(s[t] := \textrm{三}_a(b[\Gamma])\)である。
      2. そうでないならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(d[0])])\)である。
  3. \(\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(a)}(0)\)ならば、\(s[t] := t\)である。

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

形式化[]

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

\(n = 0\)ならば、\(\ulcorner n \urcorner := 0\)である。
\(n = 1\)ならば、\(\ulcorner n \urcorner := \overline{1}\)である。
\(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*} を以下のように再帰的に定める：

\(m = 0\)ならば、\(F_s^m(n) := n\)である。
\(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[n]}(n)\)である。
\(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*} を以下のように再帰的に定める：

\(n = 0\)ならば、\(\Lambda(n) := 0\)である。
\(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\)を以下のように再帰的に定める：

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

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

解析[]

p進大好きbotは期待された挙動として三関数観察日記を公開している。

計算機[]

Naruyoko, 三 function Implementation（最新版の定義に関して三関数の展開を計算するjavascriptコード）

三関数

目次