dom型表記における横ネスト要素に対する私の考え方

英語版: https://googology.wikia.org/wiki/User_blog:Kanrokoti/My_thought_about_side_nesting_in_dom-type_notation

概要[]

横ネストとはMrna den氏によって導入された概念であり、横ネストについてで解説が行われている。現在(2020～2021年)、ネスト・配列系表記の研究対象としてはメインストリームの1つであり、注目度の高い概念である。

解説のブログ記事を見てもらえれば分かるが、横ネストは広い対象に対して定義されており、私の専門とするdom型ネスト表記で横ネストを捉えるのは大変難しい。一方で私の最近の研究である程度の知見を得られたため、dom型ネスト表記から見た横ネスト要素とは何なのかを現在の私が持っている知識を元に書こうと思う。

横ネスト、dom型ネスト表記共に私が考えたものではなく、あくまで私が捉え直したものであるため、考案者の意図から外れている可能性が高い。したがって、私の解説は塩一つまみ程度に受け取って欲しい。無論ミスの指摘や質問があれば歓迎する。

dom型ネスト表記とは[]

まず、dom型ネスト表記とは何かについて固定しておこうと思う。dom型ネスト表記(あるいはdom型、dom型定義、dom型表記)はp進大好きbot氏が導入した用語で、dom型と対になる概念としてnorm型がある。表記系$T$がdom型であるとは、$T$における共終数を返す役割が期待された写像 \begin{eqnarray*} \textrm{dom} \colon T & \to & T \\ s & \mapsto & \textrm{dom}(s) \end{eqnarray*} が定義されているということである。なお、もちろん写像名がdomである必要はないし、1変数である必要もない。$T$における共終数を返す役割が期待された写像であれば何でもよい。

この意味では、横ネストはdom型ネスト表記に対して導入された概念ではないということが分かる。

この記事内では、$\textrm{dom}(s) = s$を満たす$s \in T$を正則基数と呼ぶことにする。

domの定義から見た横ネスト要素[]

横ネストは展開規則に強く結びつく概念であるため、同様に展開規則に強く結びつくdomとはある程度の親和性がある。domの定義に注目することで、横ネストの段階数を測ることが可能である。以下、議論を簡単にするために表記系$T$の項を次のように固定する:

$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$である。

表記系$T$において、順序数$0$、$1$、$\omega$の役割が期待された項をそれぞれ$$0$、$$1$、$$\omega$で表すとする。今回は$$0 = 0$、$$1 = \psi_0(0)$、$$\omega = \psi_0(\psi_0(0)) = \psi_0($1)$とする。また、項同士の大小関係である$T$上の2項関係$\lt$が何らかの方法で定められているものとする。

もちろん$$0$、$$1$、$$\omega$への対応はこれにこだわる必要はなく、例えば$$0 = 0$、$$1 = \psi_0(0)$、$$\omega = \psi_0(0)+\psi_0(\psi_0(0)) = \psi_0(0)+\psi_0($1)$という対応や、$$0 = 0$、$$1 = \psi_0(0)$、$$\omega = \psi_{\psi_0(0)}(0) = \psi_{$1}(0)$という対応でもよい。つまり、ここは自身の表記に合わせて変えるところである。ただし、この対応が変われば以下の考察で用いられている条件文も変わることに注意してほしい。また、今回は$T$が2変数だが、もちろん1変数やn変数に対しても横ネスト要素を見出すことは可能である。

横ネスト0段階[]

表記系$T$が0段階横ネスト表記であるとは、

正則基数$s \in T$は$$0,$1,$\omega$のみである。

が成り立つということである。

$$0,$1,$\omega$を0段階正則基数と呼び、0段階正則基数の集合$\{$0,$1,$\omega\}$を$R_0 \subset T$で表すとする。

横ネスト1段階[]

表記系$T$が1段階横ネスト表記であるとは、

$s \notin R_0$を満たす正則基数$s \in T$が存在する。これを1段階正則基数と呼び、1段階正則基数の集合を$R_1 \subset T$で表すとする。
いかなる$s \in R_1$に対しても、$s = ψ_a(0)$を満たす$a \in (T \setminus \{0\})$が存在する。

が成り立つということである。

例えば拡張Buchholz OCFに伴う順序数表記では、$\textrm{dom}(a) = $1$を満たす$ψ_a(0)$が1段階正則基数となる。

横ネスト2段階[]

表記系$T$が2段階横ネスト表記であるとは、

$s \notin (R_0 \cup R_1)$を満たす正則基数$s \in T$が存在する。これを2段階正則基数と呼び、2段階正則基数の集合を$R_2 \subset T$で表すとする。
いかなる$s \in R_2$に対しても、$s = ψ_a(b)$かつ$s \lt \textrm{dom}(b)$かつ$\textrm{dom}(b) \in R_1$を満たす$(a,b) \in T^2$が存在する。

が成り立つということである。

横ネスト3段階[]

表記系$T$が3段階横ネスト表記であるとは、

$s \notin (R_0 \cup R_1 \cup R_2)$を満たす正則基数$s \in T$が存在する。これを3段階正則基数と呼び、3段階正則基数の集合を$R_3 \subset T$で表すとする。
いかなる$s \in R_3$に対しても、$s = ψ_a(b)$かつ$s \lt \textrm{dom}(b)$かつ$\textrm{dom}(b) \in R_2$を満たす$(a,b) \in T^2$が存在する。

が成り立つということである。

横ネスト4段階[]

表記系$T$が4段階横ネスト表記であるとは、

$s \notin (R_0 \cup R_1 \cup R_2 \cup R_3)$を満たす正則基数$s \in T$が存在する。これを4段階正則基数と呼び、4段階正則基数の集合を$R_4 \subset T$で表すとする。
いかなる$s \in R_4$に対しても、$s = ψ_a(b)$かつ$s \lt \textrm{dom}(b)$かつ$\textrm{dom}(b) \in R_3$を満たす$(a,b) \in T^2$が存在する。

が成り立つということである。

ここまで来れば、横ネストn段階がどうなるかや、横ネストω段階がどうなるかを推測できるだろう。筆者の技術不足でそれらの定義はここには書けないため、dom型ネスト表記における横ネストn段階や横ネストω段階の定義を書くのは読者への演習とする。

以上を元にdomの定義のみに注目した場合、私はTSS-ψ関数とハイパー原始ψ関数が最低横ネストω段階以上の表記であると考えている。

基本列の定義から見た横ネスト要素[]

横ネストは展開規則に強く結びつく概念であるため、dom型ネスト表記が実際に横ネストの展開を持つかどうかは結局のところ基本列の定義に強く依存する。

現状どのような基本列を取ると良いのかは見当がついていない状態である。そこで、現在私が採用している基本列の実装を紹介する。ここからはかなり怪しい部分なので、特にミスがあれば指摘してもらいたい。

以下、2段階横ネスト表記に限定して話を進める。まず、現在2段階横ネスト表記には標準形の取り方が2種類ある。

標準形1: $\psi_0(\psi_1(0))$
標準形2: $\psi_0(\psi_0(\psi_1(0)))$

標準形1は横ネスト段階配列表記や2-シフトψ関数で採用されている標準形で、標準形2は三関数で採用されている標準形である。

この2つの標準形の違いは、基本列の「自然」な定め方に影響を与える。その違いはちょうど原始数列とベクレミシェフの虫の違いに対応する。次で説明のために純粋な基本列のルールのみを書き出すが、分かりずらいと思うので各自で各々の表記の定義を見に行って私の意味するところを確かめてもらいたい。

標準形1は正則性崩壊を用いる$\Gamma$ルールを

$t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$が存在し、かつ$s[t[0]] = \Gamma$を満たす$\Gamma \in T$が一意に存在するならば、$s[t] := \psi_a(b[\Gamma])$である。
そうでないならば、$s[t] := \psi_a(b[0])$である。

と定めるのが自然である。これは原始数列型である。

標準形2は正則性崩壊を用いる$\Gamma$ルールを

$t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$が存在し、かつ$s[t[0]] = \psi_a(\Gamma)$を満たす$\Gamma \in T$が一意に存在するならば、$s[t] := \psi_a(b[\psi_{c[0]}(\Gamma)])$である。
そうでないならば、$s[t] := \psi_a(b[\psi_{c[0]}(0)])$である。

と定めるのが自然である。これはベクレミシェフの虫型である。

例えば、2-シフトψ関数は標準形1を採用しているにもかかわらず標準形2の正則性崩壊を用いる$\Gamma$ルールを使用しているため、定義に不自然な部分が発生してしまっている。

今のところ、私が作成に成功した表記は標準形1を採用している。標準形1での基本列の定め方の簡単な指針を示しておくが、あくまで指針であって場合分け不完全なので、定義を作る際は各自で表記に合わせて調整してもらいたい。

$\textrm{dom}(t) = 0$ならば、$s[t] := \psi_a(b[0])$と定める。
$\textrm{dom}(t) = $1$かつ$s[t[0]] = \Gamma$を満たす$\Gamma \in T$が一意に存在するならば、$s[t] := \psi_a(b[\Gamma])$と定める。
$\textrm{dom}(t) \notin \{0,$1\}$ならば、$s[t] := \psi_a(b[t])$と定める。

1段階横ネスト表記と異なるのが、3つ目のルールである。このルールによって、$\psi_0(\psi_1(0))$の$\psi_1(0)$を正則基数として正則性崩壊を用いる展開(1段階横ネストの展開)と、$\psi_0(\psi_1(0))$そのものを正則基数として正則性崩壊を用いる展開(2段階横ネストの展開)を両立させている。

基数への対応[]

以上の議論から横ネストは表記系に対する概念であり、基数やOCFの構成への関係性を見出すことは困難である。