ハイパー原始ψ関数[1]は Kanrokoti[2] が2021年8月14日に公開した巨大数表記である。
ハイパー原始ψ関数は拡張ブーフホルツのψ関数に伴う順序数表記の添字にハイパー原始数列を組み込んだ表記である。ネスト表記と数列表記を組み合わせた数少ない表記の一つであり、添字上昇システムを持つ数少ない表記の一つである。ハイパー原始ψ関数はその構成より、\(\psi_0(\psi_{$n}(0))\)がバシク行列システム\((0,0,0)(1,1,1)(2,2,2)(3,3,3) \dots (n,n,n)\)に対応すると考えられている。
概要
ハイパー原始ψ関数を定義します。拡張Buchholz OCFに伴う順序数表記を元に、\(\psi\)の添字にハイパー原始数列を組み込んだ表記です。
Special thanks: p進さん大好きbot, ゆきと
ハイパー原始ψ関数
表記
ここでは、表記に用いる文字列について定義する。
\(0\)と\(+\)と\(\psi\)と\((\)と\()\)のみからなる文字列の集合\(T\)と\(PT\)を以下のように同時に再帰的に定める:
- \(0 \in T\)である。
- いかなる\((a,b) \in PT \times (T \setminus \{0\})\)に対しても、\(a+b \in T\)である。
- いかなる\((a,b) \in T^2\)に対しても、\(\psi_a(b) \in PT \cap T\)である。
\(0\)を\($0\)と略記し、\(\psi_0(0)\)を\($1\)と略記し、\(n \in (\mathbb{N} \setminus \{0,1\})\)に対し\(\underbrace{$1+ \dots +$1}_{$1がn個}\)を\($n\)と略記し、\(\psi_0($1)\)を\($\omega\)と略記する。
部分集合\(RT \subset T\)と\(RPT \subset PT\)を次のように同時に再帰的に定める:
- \(0 \in RT\)である。
- いかなる\((a,b) \in RPT \times (RT \setminus \{0\})\)に対しても、\(a+b \in RT\)である。
- いかなる\((a,b) \in \mathbb{N} \times RT\)に対しても、\(\psi_{$a}(b) \in RPT \cap RT\)である。
上昇関数
ここでは、上昇関数を定義する。
計算可能全域写像 \begin{eqnarray*} \Delta \colon RT \times (\mathbb{N} \setminus \{0\}) \times \mathbb{N} \times \{0,1\} & \to & RT \\ (s,\delta,br,pr) & \mapsto & \Delta(s,\delta,br,pr) \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(\Delta(s,\delta,br,pr) := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\Delta(s,\delta,br,pr) := \Delta(a,\delta,br,pr)+\Delta(b,\delta,br,pr)\)である。
- \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
- \(br \lt a\)ならば、\(\Delta(s,\delta,br,pr) := \psi_{$a+$\delta}(\Delta(b,\delta,br,pr))\)である。
- \(br \ge a\)とする。
- \(pr = 0\)ならば、\(\Delta(s,\delta,br,pr) := \psi_{$a+$\delta}(\Delta(b,\delta,br,1))\)である。
- そうでないならば、\(\Delta(s,\delta,br,pr) := \psi_{$a}(b)\)である。
共終数
ここでは、表記における共終数を定義する。
計算可能全域写像 \begin{eqnarray*} \textrm{cp} \colon RT & \to & RT \\ s & \mapsto & \textrm{cp}(s) \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(\textrm{cp}(s) := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{cp}(s) := \textrm{cp}(b)\)である。
- \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
- \(\textrm{cp}(b) = 0\)ならば、\(\textrm{cp}(s) := s\)である。
- \(\textrm{cp}(b) \in \{$1,$\omega\}\)ならば、\(\textrm{cp}(s) := $\omega\)である。
- \(\textrm{cp}(b) \notin \{0,$1,$\omega\}\)ならば、\(\textrm{cp}(b) = \psi_{$c}(d)\)を満たす\((c,d) \in \mathbb{N} \times RT\)が存在する。
- \(d = 0\)とする。
- \(a \lt c\)ならば、\(\textrm{cp}(s) := s\)である。
- そうでないならば、\(\textrm{cp}(s) := \textrm{cp}(b)\)である。
- \(d \neq 0\)ならば、\(\textrm{cp}(s) := \textrm{cp}(b)\)である。
- \(d = 0\)とする。
計算可能全域写像 \begin{eqnarray*} \textrm{dom} \colon RT & \to & RT \\ s & \mapsto & \textrm{dom}(s) \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
- \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
- \(\textrm{dom}(b) = 0\)ならば、\(\textrm{dom}(s) := s\)である。
- \(\textrm{dom}(b) \in \{$1,$\omega\}\)ならば、\(\textrm{dom}(s) := $\omega\)である。
- \(\textrm{dom}(b) \notin \{0,$1,$\omega\}\)ならば、\(\textrm{dom}(b) = \psi_{$c}(d)\)を満たす\((c,d) \in (\mathbb{N} \setminus \{0\}) \times RT\)が存在する。
- \(a \lt c\)ならば、\(\delta_0 := c-a-1\)と置く。
- \(\textrm{dom}(d) = 0\)とする。
- \(\delta_0 \lt 1\)ならば、\(\textrm{dom}(s) := $\omega\)である。
- そうでないならば、\(\textrm{dom}(s) := s\)である。
- そうでないならば、\(\textrm{cp}(b) = \psi_{$e}(f)\)かつ\(\textrm{cp}(f) = \psi_{$g}(0)\)を満たす\((e,f,g) \in (\mathbb{N} \setminus \{0\}) \times RT \times (\mathbb{N} \setminus \{0\})\)が存在する。\(\delta_1 := g-e-1\)と置く。
- \(\delta_0 \lt \delta_1\)ならば、\(\textrm{dom}(s) := $\omega\)である。
- そうでないならば、\(\textrm{dom}(s) := s\)である。
- \(\textrm{dom}(d) = 0\)とする。
- そうでないならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
- \(a \lt c\)ならば、\(\delta_0 := c-a-1\)と置く。
基本列
ここでは、表記の基本列を定義する。
計算可能全域写像 \begin{eqnarray*} [ \ ] \colon RT^2 & \to & RT \\ (s,t) & \mapsto & s[t] \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(s[t] := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(b' := b[t]\)と置く。
- \(b' = 0\)ならば、\(s[t] := a\)である。
- そうでないならば、\(s[t] := a+b'\)である。
- \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
- \(\textrm{dom}(b) = 0\)ならば、\(s[t] := t\)である。
- \(\textrm{dom}(b) = $1\)とする。
- \(t = t[0]+$1\)ならば、\(s[t] := s[t[0]]+s[$1]\)である。
- そうでないならば、\(s[t] := \psi_{$a}(b[0])\)である。
- \(\textrm{dom}(b) = $\omega\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
- \(\textrm{dom}(b) \notin \{0,$1,$\omega\}\)ならば、\(\textrm{dom}(b) = \psi_{$c}(d)\)を満たす\((c,d) \in (\mathbb{N} \setminus \{0\}) \times RT\)が存在する。
- \(a \lt c\)ならば、\(\delta_0 := c-a-1\)と置く。
- \(\textrm{dom}(d) = 0\)とする。
- \(\delta_0 \lt 1\)とする。
- \(t = $i\)を満たす\(i \in (\mathbb{N} \setminus \{0\})\)が存在し、かつ\(s[t[0]] = \Gamma\)を満たす\(\Gamma \in RT\)が一意に存在するならば、\(s[t] := \psi_{$a}(b[\Gamma])\)である。
- そうでないならば、\(s[t] := \psi_{$a}(b[0])\)である。
- \(\delta_0 \ge 1\)とする。
- \(t = 0\)ならば、\(s[t] := \psi_{$a}(b[0])\)である。
- \(t = $i\)を満たす\(i \in (\mathbb{N} \setminus \{0\})\)が存在し、かつ\(s[t[0]] = \Gamma\)を満たす\(\Gamma \in RT\)が一意に存在するならば、\(s[t] := \psi_{$a}(b[\Delta(\Gamma,\delta_0,a,0)])\)である。
- そうでないならば、\(s[t] := \psi_{$a}(b[t])\)である。
- \(\delta_0 \lt 1\)とする。
- そうでないならば、\(\textrm{cp}(b) = \psi_{$e}(f)\)かつ\(\textrm{cp}(f) = \psi_{$g}(0)\)を満たす\((e,f,g) \in (\mathbb{N} \setminus \{0\}) \times RT \times (\mathbb{N} \setminus \{0\})\)が存在する。\(\delta_1 := g-e-1\)と置き、\(\delta_2 := g-a-1\)と置く。
- \(\delta_0 \lt \delta_1\)とする。
- \(t = $i\)を満たす\(i \in (\mathbb{N} \setminus \{0\})\)が存在し、かつ\(s[t[0]] = \Gamma\)を満たす\(\Gamma \in RT\)が一意に存在するならば、\(s[t] := \psi_{$a}(b[\Delta(\Gamma,\delta_2,a,0)])\)である。
- そうでないならば、\(s[t] := \psi_{$a}(b[0])\)である。
- \(\delta_0 \ge \delta_1\)とする。
- \(t = 0\)ならば、\(s[t] := \psi_{$a}(b[0])\)である。
- \(t = $i\)を満たす\(i \in (\mathbb{N} \setminus \{0\})\)が存在し、かつ\(s[t[0]] = \Gamma\)を満たす\(\Gamma \in RT\)が一意に存在するならば、\(s[t] := \psi_{$a}(b[\Delta(\Gamma,\delta_2,a,0)])\)である。
- そうでないならば、\(s[t] := \psi_{$a}(b[t])\)である。
- \(\delta_0 \lt \delta_1\)とする。
- \(\textrm{dom}(d) = 0\)とする。
- そうでないならば、\(s[t] := \psi_{$a}(b[t])\)である。
- \(a \lt c\)ならば、\(\delta_0 := c-a-1\)と置く。
急増加関数
ここでは、表記を使った急増加関数を定義する。
計算可能部分写像 \begin{eqnarray*} f \colon RT \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:
- \(m = 0\)ならば、\(f_s^m(n) := n\)である。
- \(m = 1\)とする。
- \(s = 0\)ならば、\(f_s^m(n) := n+1\)である。
- \(s \neq 0\)とする。
- \(\textrm{dom}(s) = $1\)ならば、\(f_s^m(n) := f_{s[0]}^n(n)\)である。
- そうでないならば、\(f_s^m(n) := f_{s[$n]}^1(n)\)である。
- \(m \notin \{0,1\}\)ならば、\(f_s^m(n) := f_s^1(f_s^{m-1}(n))\)である。
標準形
ここでは、表記の標準形を定める。
部分集合\(OT \subset RT\)を次のように再帰的に定める:
- いかなる\(n \in \mathbb{N}\)に対しても、\(\psi_0(\psi_{$n}(0)) \in OT\)である。
- いかなる\((s,n) \in OT \times \mathbb{N}\)に対しても、\(s[$n] \in OT\)である。
命名
計算可能全域写像 \begin{eqnarray*} F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & F(n) \end{eqnarray*} を\(F(n) = f_{\psi_0(\psi_{$n}(0))}(n)\)と定める。
\(F^{10^{100}}(10^{100})\)を「ハイパー原始ψ数」と名付ける。
表記の限界に対応する順序数を「Hyper Primitive psi ordinal」(HPPO)と名付ける。