ψコードを用いて拡張ブーフホルツのψ関数に伴う順序数表記の基本列系を決定する (2024)

\(\newcommand\a{\alpha}\newcommand\b{\beta}\newcommand\g{\gamma}\newcommand\d{\delta}\newcommand\x{\xi}\newcommand\n{\nu}\newcommand\m{\mu}\newcommand\k{\kappa}\newcommand\c{\chi}\newcommand\p{\psi}\newcommand\vp{\varphi}\newcommand\o{\omega}\newcommand\O{\Omega}\newcommand\e{\epsilon}\newcommand\z{\zeta}\newcommand\G{\Gamma}\)\(\newcommand\On{\textrm{On}}\newcommand\AP{\textrm{AP}}\newcommand\CARD{\textrm{CARD}}\newcommand\Reg{\textrm{Reg}}\newcommand\dom{\textrm{dom}}\newcommand\Enum{\textrm{Enum}}\newcommand\Mah{\textrm{Mah}}\newcommand\N{\mathbb{N}}\newcommand\Trans{\textrm{Trans}}\)\(\newcommand\add{\textrm{add}}\newcommand\Trans{\textrm{Trans}}\)

動機[]

高階記述不可能性の崩壊では、許容パラメータ\((i,j)\)で崩壊対象と崩壊先を表す超限引数の制限を決定している。

また、2種類の閉点による多変数配列の分類や3種類の閉点による多変数配列の分類では、\(\p\)コードを用いて、どの変数がどんな種類の閉点を数え上げるかを一般化して表している。

これらに触発された筆者は
「\(\p\)コードの文字の種類を増やせば、閉点以外も表せる」
「そうすれば、崩壊やAPや極限の処理を\(\p\)コードで決定できる」
「ならば\(\p\)コードで拡張ブーフホルツのψ関数に伴う順序数表記の基本列系を決定するようにすれば、拡張性・可読性に優れた表記ができるはず」
という案を思いついた。

本記事では、上の案を元に

1. 拡張ブーフホルツのψ関数に伴う順序数表記に、\(\p\)コードを組み込んだ表記(Buchholz式コードψ関数)
2. 1.の表記を\(\textrm{Rathjen's}\p\)の形式にした表記(Rathjen式コードψ関数)

の2つの表記を作成した。

Buchholz式コードψ関数[]

\(\p\)コード[]

形式的な文字列の集合\(S:= \{N,1,A,L_a,L_b,C,R\}\)に対して、\(S\)の要素からなる有限長文字列のうち空文字でないものを\(\p\)コードと呼ぶ。\(\p\)コード全体の集合を\(\mathbf{C}\)とおく。

\(\psi\)コード\(\mathbf{c}\)の長さを\(L(\mathbf{c})\)と表す。

また、任意の\(L(\mathbf{c})\)未満の非負整数\(k\)について、\(\mathbf{c}\)の右から数えて\(k\)番目の文字を\(\mathbf{c}_k\)と表す。

\(\p\)コード\(\mathbf{a},\mathbf{b}\)を

\(\mathbf{a}:= 1RL_a\)

\(\mathbf{b}:= NAL_bC\)

と定める。

全体集合[]

\(0\)と\(+\)と\(\psi\)と\((\)と\(,\)と\()\)のみからなる文字列の集合\(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\)に対しても、\(\psi(a,b) \in PT \cap T\)である。

各\((a,b) \in T^2\)に対し、\(\psi(a,b)\)を\(\psi_a(b)\)と略記する。

非負整数全体の集合を\(\N\)とおく。

計算可能性に意味を持たせるために\(\omega\)を単なる文字列として扱い、\(\mathbb{N}^+:= \mathbb{N} \cup \{\omega\}\)と定める。

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

1. \(n = 0\)ならば、\($n:= 0\)である。
2. \(n = 1\)ならば、\($n:= \psi_0(0)\)である。
3. \(n = \omega\)ならば、\($n:= \psi_0($1)\)である。
4. \(n \notin \{0,1,\omega\}\)ならば、\($n:= $(n-1)+$1\)である。

順序[]

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

\(s \le t\)の定義

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

\(s \lt t\)の定義

1. \(t = 0\)ならば、\(s \lt t\)は偽である。
2. \(t \neq 0\)かつ\(s = 0\)ならば、\(s \lt 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 \lt t\)は以下のいずれかが成り立つことと同値である:
      1. \(a \lt c\)である。
      2. \(a = c\)かつ\(b \lt d\)である。
   2. \(t = \psi_{c}(d)\)を満たす\((c,d) \in T^2\)が存在するならば、\(s \lt t\)は\(a \lt t\)と同値である。
4. \(t \neq 0\)かつ\(s = \psi_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s \lt t\)は\(s \le c\)と同値である。
   2. \(t = \psi_{c}(d)\)を満たす\((c,d) \in T^2\)が存在するならば、\(s \lt t\)は以下のいずれかが成り立つことと同値である:
      1. \(a \lt c\)である。
      2. \(a = c\)かつ\(b \lt d\)である。

加法[]

計算可能全域写像\begin{eqnarray}\add: T^2 &\to& T\\(s,t) &\mapsto& \add(s,t)\end{eqnarray}

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

コード読み取り関数と共終数[]

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

\(C(s)\)の定義

1. \(s = \p_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(\dom(b) = 0\)とする。
      1. \(\dom(a) = 0\)ならば、\(C(s):= \mathbf{a}_0\)である。
      2. \(\dom(a) = $1\)ならば、\(C(s):= \mathbf{a}_1\)である。
      3. \(\dom(a) \notin \{0,$1\}\)ならば、\(C(s):= \mathbf{a}_2\)である。
   2. \(\dom(b) = $1\)ならば、\(C(s):= \mathbf{b}_1\)である。
   3. \(\dom(b) \notin \{0,$1\}\)とする。
      1. \(\dom(b) < s\)ならば、\(C(s):= \mathbf{b}_2\)である。
      2. \(s \leq \dom(b)\)ならば、\(C(s):= \mathbf{b}_3\)である。

\(\dom(s)\)の定義

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 = \psi_{a}(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(C(s) \in \{1,R\}\)ならば、\(\dom(s):= s\)である。
   2. \(C(s) \in \{A,C\}\)ならば、\(\dom(s):= $\o\)である。
   3. \(C(s) = L_a\)ならば、\(\dom(s):= \dom(a)\)である。
   4. \(C(s) = L_b\)ならば、\(\dom(s):= \dom(b)\)である。

基本列[]

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

1. \(s = 0\)ならば、\(s[t]:= 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s[t]:= \add(a,b[t])\)である。
3. \(s = \psi_{a}(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
   1. \(C(s) \in \{1,R\}\)ならば、\(s[t]:= t\)である。
   2. \(C(s) = A\)とする。
      1. \(t = t[0]+$1\)ならば、\(s[t]:= \add(s[t[0]],s[$1])\)である。
      2. \(t \neq t[0]+$1\)ならば、\(s[t]:= \p_a(b[0])\)である。
   3. \(C(s) = L_a\)ならば、\(s[t]:= \p_{a[t]}(b)\)である。
   4. \(C(s) = L_b\)ならば、\(s[t]:= \p_a(b[t])\)である。
   5. \(C(s) = C\)ならば、\(\dom(b) = \p_c(0)\)を満たす\(c \in T\)が存在する。
      1. \(t = $i\)を満たす\(i \in \N\)と\(s[t[0]] = \p_a(\G)\)を満たす\(\G \in T\)が存在するならば、\(s[t]:= \p_a(b[\p_{c[0]}(\G)])\)である。
      2. そうでないならば、\(s[t]:= \p_a(b[\p_{c[0]}(0)])\)である。

Rathjen式コードψ関数[]

\(\p\)コード[]

形式的な文字列の集合\(S:= \{N,1,A_a,A_b,L_a,L_b,C\}\)に対して、\(S\)の要素からなる有限長文字列のうち空文字でないものを\(\p\)コードと呼ぶ。\(\p\)コード全体の集合を\(\mathbf{C}\)とおく。

\(\psi\)コード\(\mathbf{c}\)の長さを\(L(\mathbf{c})\)と表す。

また、任意の\(L(\mathbf{c})\)未満の非負整数\(k\)について、\(\mathbf{c}\)の右から数えて\(k\)番目の文字を\(\mathbf{c}_k\)と表す。

\(\p\)コード\(\mathbf{a},\mathbf{b}\)を

\(\mathbf{a}:= 1A_aL_a\)

\(\mathbf{b}:= NA_bL_bC\)

と定める。

全体集合[]

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

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

各\((a,b) \in T^2\)に対し、\(\psi(a,b)\)を\(\psi_a(b)\)と略記し、各\(a \in T\)に対し、\(\O(a)\)を\(\O_a\)と略記する。

非負整数全体の集合を\(\N\)とおく。

計算可能性に意味を持たせるために\(\omega\)と\(\O\)を単なる文字列として扱い、\(\mathbb{N}^+:= \mathbb{N} \cup \{\omega,\O\}\)と定める。

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

1. \(n = 0\)ならば、\($n:= 0\)である。
2. \(n = \O\)ならば、\($n:= \O_0\)である。
3. \(n = 1\)ならば、\($n:= \psi_\O(0)\)である。
4. \(n = \omega\)ならば、\($n:= \psi_\O($1)\)である。
5. \(n \notin \{0,1,\omega\}\)ならば、\($n:= $(n-1)+$1\)である。

順序[]

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

\(s \le t\)の定義

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

\(s \lt t\)の定義

1. \(t = 0\)ならば、\(s \lt t\)は偽である。
2. \(t \neq 0\)かつ\(s = 0\)ならば、\(s \lt 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 \lt t\)は以下のいずれかが成り立つことと同値である:
      1. \(a \lt c\)である。
      2. \(a = c\)かつ\(b \lt d\)である。
   2. \(t = \O_c\)を満たす\(c \in T\)が存在するならば、\(s \lt t\)は\(a \lt t\)と同値である。
   3. \(t = \psi_{c}(d)\)を満たす\((c,d) \in RT \times T\)が存在するならば、\(s \lt t\)は\(a \lt t\)と同値である。
4. \(t \neq 0\)かつ\(s = \O_a\)を満たす\(a \in T\)が存在するとする。
   1. \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s \lt t\)は\(s \le c\)と同値である。
   2. \(t = \O_c\)を満たす\(c \in T\)が存在するならば、\(s \lt t\)は\(a \lt c\)と同値である。
   3. \(t = \psi_{c}(d)\)を満たす\((c,d) \in RT \times T\)が存在するならば、\(s \lt t\)は\(s \lt a\)と同値である。
5. \(t \neq 0\)かつ\(s = \psi_a(b)\)を満たす\((a,b) \in RT \times T\)が存在するとする。
   1. \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s \lt t\)は\(s \le c\)と同値である。
   2. \(t = \O_c\)を満たす\(c \in T\)が存在するならば、\(s \lt t\)は\(a \leq t\)と同値である。
   3. \(t = \psi_{c}(d)\)を満たす\((c,d) \in RT \times T\)が存在するならば、\(s \lt t\)は以下のいずれかが成り立つことと同値である:
      1. \(a \lt c\)である。
      2. \(a = c\)かつ\(b \lt d\)である。

加法[]

計算可能全域写像\begin{eqnarray}\add: T^2 &\to& T\\(s,t) &\mapsto& \add(s,t)\end{eqnarray}

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

コード読み取り関数と共終数[]

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

\(C(s)\)の定義

1. \(s = \p_a(b)\)を満たす\((a,b) \in RT \times T\)が存在するとする。
   1. \(\dom(b) = 0\)ならば、\(a = \O_c\)を満たす\(c \in T\)が存在する。
      1. \(\dom(c) = 0\)ならば、\(C(s):= \mathbf{a}_0\)である。
      2. \(\dom(c) = $1\)ならば、\(C(s):= \mathbf{a}_1\)である。
      3. \(\dom(c) \notin \{0,$1\}\)ならば、\(C(s):= \mathbf{a}_2\)である。
   2. \(\dom(b) = $1\)ならば、\(C(s):= \mathbf{b}_1\)である。
   3. \(\dom(b) \notin \{0,$1\}\)とする。
      1. \(\dom(b) < s\)ならば、\(C(s):= \mathbf{b}_2\)である。
      2. \(s \leq \dom(b)\)ならば、\(C(s):= \mathbf{b}_3\)である。

\(\dom(s)\)の定義

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 = \O_a\)を満たす\(a \in T\)が存在するならば、\(\dom(s):= s\)である。
4. \(s = \psi_{a}(b)\)を満たす\((a,b) \in RT \times T\)が存在するとする。
   1. \(C(s) = 1\)ならば、\(\dom(s):= s\)である。
   2. \(C(s) \in \{A_a,A_b,C\}\)ならば、\(\dom(s):= $\o\)である。
   3. \(C(s) = L_a\)ならば、\(\dom(s):= \dom(a)\)である。
   4. \(C(s) = L_b\)ならば、\(\dom(s):= \dom(b)\)である。

基本列[]

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

1. \(s = 0\)ならば、\(s[t]:= 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s[t]:= \add(a,b[t])\)である。
3. \(s = \O_a\)を満たす\(a \in T\)が存在するならば、\(s[t]:= t\)である。
4. \(s = \psi_{a}(b)\)を満たす\((a,b) \in RT \times T\)が存在するとする。
   1. \(C(s) = 1\)ならば、\(s[t]:= t\)である。
   2. \(C(s) = A_a\)ならば、\(a = \O_c\)を満たす\(c \in T\)が存在する。
      1. \(t = t[0]+$1\)ならば、\(s[t]:= \add(s[t[0]],s[$1])\)である。
      2. \(t \neq t[0]+$1\)ならば、\(s[t]:= \O_{c[0]}\)である。
   3. \(C(s) = A_b\)とする。
      1. \(t = t[0]+$1\)ならば、\(s[t]:= \add(s[t[0]],s[$1])\)である。
      2. \(t \neq t[0]+$1\)ならば、\(s[t]:= \p_a(b[0])\)である。
   4. \(C(s) = L_a\)ならば、\(s[t]:= \O_{c[t]}\)である。
   5. \(C(s) = L_b\)ならば、\(s[t]:= \p_a(b[t])\)である。
   6. \(C(s) = C\)ならば、\(\dom(b) = \O_c\)を満たす\(c \in T\)が存在する。
      1. \(t = $i\)を満たす\(i \in \N\)と\(s[t[0]] = \p_a(\G)\)を満たす\(\G \in T\)が存在するならば、\(s[t]:= \p_a(b[\p_{\O_c}(\G)])\)である。
      2. そうでないならば、\(s[t]:= \p_a(b[\p_{\O_c}(0)])\)である。

備考[]

2つの\(\p\)コード\(\mathbf{a},\mathbf{b}\)に対し、共終数を用いて\(\p_a(b)\)の基本列系が定まった。ただし\(\mathbf{a},\mathbf{b}\)の内容次第では容易に停止しない表記となってしまう。

順序数との対応[]

\(\p\)コードでの文字を順序数と対応させると以下のようになる。

\(N\)

その基本列系では用いないことを示す。これだけ順序数ではないことに注意。

\(1\)

順序数\(1\)と対応することを示す。

\(A_a\)

正則基数の次の\(AP\)数であることを示す。

\(A_b\)

ある\(AP\)数の次の\(AP\)数であることを示す。

\(A\)

\(A_b\)と役割は同じなので割愛する。

\(L_a\)

極限基数であることを示す。

\(L_b\)

\(AP\)数の極限であることを示す。

\(C\)

数え上げ引数(\(\p_a(b)\)の\(b\))が崩壊することを示す。

\(R\)

非可算正則基数であることを示す。

\(\mathbf{b}_0 = N\)としている理由[]

Buchholz式コードψ関数、Rathjen式コードψ関数の両方で\(\mathbf{b}_0 = N\)としているが、これは

\(\mathbf{a},\mathbf{b}\)は、それぞれ\(\p_a(b)\)の\(a,b\)の\(\dom\)が、\(0,$1,\notin\{0,$1\}\)であるときの役割を示す

という目的で\(\mathbf{a},\mathbf{b}\)を用いているからである。
しかし、\(\dom(b) = 0\)のときはすべて\(\mathbf{a}\)で役割を示しているため、\(\mathbf{b}\)は用いない。
なので、つじつまを合わせるために\(\mathbf{b}_0 = N\)としている。

既存の表記との関係[]

Buchholz式コードψ関数は、\(0\)を\(()\)に、\(\p_a(b)\)を\(\langle a,b \rangle\)に、\(a_0+...+a_m\)を\((a_0,...,a_m)\)に置き換えることで、拡張ブーフホルツのψ関数に伴う順序数表記と対応する。
Rathjen式コードψ関数はというと、以下のようにしてRathjen式コードψ関数からBuchholz式コードψ関数への対応写像を作成できるので、Rathjen式コードψ関数も拡張ブーフホルツのψ関数に伴う順序数表記と対応させることができる。

\(\p\)コードの拡張[]

Buchholz式コードψ関数とRathjen式コードψ関数は、\(\p\)コードの文字を追加したり\(\p\)コードに対応した基本列系を変えたりすることで様々な拡張ができる。
以下はその一例である。読者もぜひ、自分なりの拡張法を考えて欲しい。

Buchholz式コードψ関数

1. 多変数化して、各変数ごとに\(\p\)コードを設定する。(多変数〇関数、くまくま(大嘘)多変数ψ、オメガ不動点3変数ψ)
2. 弱マーロ基数であることを示す文字\(M\)を、\(\p\)コードに追加する。(三関数)
3. \(\p_a(b)\)の\(a\)で崩壊することを示す文字列\(C_a\)を、\(\p\)コードに追加する。

Rathjen式コードψ関数

1. 巨大基数の文字翻訳物と、巨大基数であることを示す文字を\(\p\)コードに追加する。(弱到達不能基数\(I\)、弱マーロ基数\(M\)など)

参考文献[]

• 2種類の閉点による多変数配列の分類

本記事の構成はこちらの記事を参考にした。

• 拡張ブーフホルツのψ関数に伴う順序数表記と同じと思われる関数

表記の定義はこちらの記事を参考にした。

• 新しい標準形と基本列

拡張ブーフホルツのψ関数ともRathjen's\(\p\)とも違った方法で、\(\p\)の基本列系を定めている。こちらに基本列系を合わせるのも、拡張のアイデアの一つだろう。