変更：ユーザーブログ:Kanrokoti/弱K-ψ関数

2021年9月24日 (金) 07:59時点における版

英語版:

概要

弱K-ψ関数を定義します。拡張Buchholz OCFに伴う順序数表記を3変数に拡張した表記です。

Special thanks: p進大好きbot

弱K-ψ関数

表記

$0$と$+$と$\psi$と$($と$)$のみからなる文字列の集合$T$と$PT$を以下のように同時に再帰的に定める:

$0 \in T$である。
いかなる$(a,b) \in PT \times (T \setminus \{0\})$に対しても、$a+b \in T$である。
いかなる$(a,b,c) \in T^3$に対しても、$\psi_a^b(c) \in PT \cap T$である。

$0$を$$0$と略記し、$\psi_0^0(0)$を$$1$と略記し、$n \in (\mathbb{N} \setminus \{0,1\})$に対し$\underbrace{$1+ \dots +$1}_{$1がn個}$を$$n$と略記し、$\psi_0^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,c) \in \mathbb{N}^2 \times RT$に対しても、$\psi_{$a}^{$b}(c) \in RPT \cap RT$である。

順序

$RT$上の$2$項関係$s \le t$と$s \lt t$を以下のように同時に再帰的に定める:

$s \le t$の定義

$s = t$ならば、$s \le t$は真である。
$s \neq t$ならば、$s \le t$は$s \lt t$と同値である。

$s \lt t$の定義

$t = 0$ならば、$s \lt t$は偽である。
$t \neq 0$かつ$s = 0$ならば、$s \lt t$は真である。
$t \neq 0$かつ$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するとする。
1. $t = c+d$を満たす$(c,d) \in RPT \times (RT \setminus \{0\})$が存在するならば、$s \lt t$は以下のいずれかが成り立つことと同値である:
  1. $a \lt c$である。
  2. $a = c$かつ$b \lt d$である。
2. $t = \psi^{$c}_{$d}(e)$を満たす$(c,d,e) \in \mathbb{N}^2 \times RT$が存在するならば、$s \lt t$は$a \lt t$と同値である。
$t \neq 0$かつ$s = \psi^{$a}_{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $t = d+e$を満たす$(d,e) \in RPT \times (RT \setminus \{0\})$が存在するならば、$s \lt t$は$s \le d$と同値である。
2. $t = \psi^{$d}_{$e}(f)$を満たす$(d,e,f) \in \mathbb{N}^2 \times RT$が存在するならば、$s \lt t$は以下のいずれかが成り立つことと同値である:
  1. $a \lt d$である。
  2. $a = d$かつ$b \lt e$である。
  3. $a = d$かつ$b = e$かつ$c \lt f$である。

共終数

計算可能全域写像 \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}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{dom}(c) = 0$ならば、$\textrm{dom}(s) := s$である。
2. $\textrm{dom}(c) = $1$ならば、$\textrm{dom}(s) := $\omega$である。
3. $\textrm{dom}(c) \notin \{0,$1\}$とする。
  1. $\textrm{dom}(c) \lt s$ならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。
  2. $s \le \textrm{dom}(c)$とする。
    1. $a = 0$ならば、$\textrm{dom}(s) := $\omega$である。
    2. $a \neq 0$ならば、$\textrm{dom}(c) = \psi^{$d}_{$e}(f)$を満たす$(d,e,f) \in \mathbb{N}^2 \times RT$が存在する。
      1. $a \lt d$ならば、$\textrm{dom}(s) := s$である。
      2. $d \le a$ならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。

探索関数

計算可能全域写像 \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}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{CP}(c) = 0$ならば、$\textrm{CP}(s) := s$である。
2. $\textrm{CP}(c) \neq 0$ならば、$\textrm{CP}(s) := \textrm{CP}(c)$である。

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

$s = 0$ならば、$\textrm{BP}(s,t) := 0$である。
$s = \psi^{$a}_{$b}(c)+s'$を満たす$(a,b,c,s') \in \mathbb{N}^2 \times RT \times (RT \setminus \{0\})$が存在するとする。
1. $t \lt $b$ならば、$\textrm{BP}(s,t) := s$である。
2. $$b \le t$ならば、$\textrm{BP}(s,t) := \textrm{BP}(s',t)$である。
$s = \psi^{$a}_{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{dom}(c) = 0$ならば、$\textrm{BP}(s,t) := s$である。
2. $\textrm{dom}(c) \neq 0$とする。
  1. $t \lt $b$ならば、$\textrm{BP}(s,t) := s$である。
  2. $$b \le t$ならば、$\textrm{BP}(s,t) := \textrm{BP}(c,t)$である。

基本列

計算可能全域写像 \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]$と置く。
1. $b' = 0$ならば、$s[t] := a$である。
2. $b' \neq 0$ならば、$s[t] := a+b'$である。
$s = \psi^{$a}_{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{dom}(c) = 0$ならば、$s[t] := t$である。
2. $\textrm{dom}(c) = $1$とする。
  1. $t = t[0]+$1$ならば、$s[t] := s[t[0]]+s[$1]$である。
  2. $t \neq t[0]+$1$ならば、$s[t] := \psi^{$a}_{$b}(c[0])$である。
3. $\textrm{dom}(c) \notin \{0,$1\}$とする。
  1. $\textrm{dom}(c) \lt s$ならば、$s[t] := \psi^{$a}_{$b}(c[t])$である。
  2. $s \le \textrm{dom}(c)$とする。
    1. $a = 0$ならば、$\textrm{CP}(c) = \psi^{$d}_{$e}(0)$を満たす$(d,e) \in \mathbb{N}^2$が存在する。
      1. $t = 0$とする。
        $e = 0$ならば、$s[t] := \psi^{$a}_{$b}(c[\psi^{$d[0]}_{$d[0]}(0)])$である。
        
        $e \neq 0$ならば、$s[t] := \psi^{$a}_{$b}(c[\psi^{$d}_{$e[0]}(0)])$である。
      2. $t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$と$s[t[0]] = \psi^{$a}_{$b}(\Gamma)$を満たす$\Gamma \in RT$が存在するとする。
        $e = 0$ならば、$s[t] := \psi^{$a}_{$b}(c[\psi^{$d[0]}_{$d[0]}(\textrm{BP}(\Gamma,$d[0]))])$である。
        
        $e \neq 0$ならば、$s[t] := \psi^{$a}_{$b}(c[\psi^{$d}_{$e[0]}(\textrm{BP}(\Gamma,$e[0]))])$である。
      3. 上記のいずれの条件も満たさないならば、$s[t] := \psi^{$a}_{$b}(c[0])$である。
    2. $a \neq 0$ならば、$s[t] := \psi^{$a}_{$b}(c[t])$である。

急増加関数

計算可能部分写像 \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$とする。
1. $\textrm{dom}(s) = 0$ならば、$f_s^m(n) := n+1$である。
2. $\textrm{dom}(s) = $1$ならば、$f_s^m(n) := f_{s[0]}^n(n)$である。
3. $\textrm{dom}(s) \notin \{0,$1\}$ならば、$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_0(\psi^{$n}_{$n}(0)) \in OT$である。
いかなる$(s,n) \in OT \times \mathbb{N}$に対しても、$s[$n] \in OT$である。

私の期待は$(OT,\lt)$が順序数表記になること、すなわち$OT$が再帰的かつ$\lt$の$OT$への制限が整列順序になることである。

命名

計算可能全域写像 \begin{eqnarray*} F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & F(n) \end{eqnarray*} を$F(n) := f_{\psi^0_0(\psi^{$n}_{$n}(0))}(n)$と定める。

$F^{10^{100}}(10^{100})$を「弱K-ψ数」と名付ける。

表記の限界に対応する順序数を「Weak K-psi ordinal」(WKPO)と名付ける。

@@ 13行目: / 13行目: @@
 # \(0 \in T\)である。
 # いかなる\((a,b) \in PT \times (T \setminus \{0\})\)に対しても、\(a+b \in T\)である。
-# いかなる\((a,b,c) \in T^3\)に対しても、\(\psi^a_b(c) \in PT \cap T\)である。
+# いかなる\((a,b,c) \in T^3\)に対しても、\(\psi_a^b(c) \in PT \cap T\)である。
 \(0\)を\($0\)と略記し、\(\psi_0^0(0)\)を\($1\)と略記し、\(n \in (\mathbb{N} \setminus \{0,1\})\)に対し\(\underbrace{$1+ \dots +$1}_{$1がn個}\)を\($n\)と略記し、\(\psi_0^0($1)\)を\($\omega\)と略記する。
@@ 19行目: / 19行目: @@
 # \(0 \in RT\)である。
 # いかなる\((a,b) \in RPT \times (RT \setminus \{0\})\)に対しても、\(a+b \in RT\)である。
-# いかなる\((a,b,c) \in \mathbb{N}^2 \times RT\)に対しても、\(\psi^{$a}_{$b}(c) \in RPT \cap RT\)である。
+# いかなる\((a,b,c) \in \mathbb{N}^2 \times RT\)に対しても、\(\psi_{$a}^{$b}(c) \in RPT \cap RT\)である。