ブーフホルツのψ関数の簡易的な定義

英語版: https://googology.fandom.com/wiki/User_blog:Kanrokoti/Easy_definition_of_Buchholz%27s_psi

概要

日本の巨大数界隈において、Ψ₀(Ωω)(\(\mathrm{BO}\))までの順序数を記述するのにブーフホルツのψ関数が一般に用いられているが、ブーフホルツのψ関数そのものがどのように計算されるかを把握するのは、(OCFそのものは計算不可能であることも加味して)これから\(\mathrm{BO}\)レベルを学びたい人にとって容易ではない。なぜなら、計算規則を構成する要素が多いため、計算の練習に取り組むのに大きな壁を感じやすいからである。一方で、ブーフホルツのψ関数と同じ強さを持つブーフホルツのヒドラを見てみると、ブーフホルツのψ関数に比べて計算規則が簡単なように見える。しかし、グラフ理論の用語を使って説明されており、グラフ理論に馴染みが無ければ意味を理解するのが少し難しくなっている。

このブログ記事では、これから\(\mathrm{BO}\)レベルを学びたい人でも扱えるような、ブーフフルツのψ関数に伴うことが期待される計算可能な表記を作成する。具体的には、\(\mathrm{BO}\)までを記述できる簡単で計算可能な基本列付き表記を、次のような手順で定義する:

• p進大好きbot氏によって定義された拡張Buchholz OCFに伴う順序数表記を、\(\mathrm{BO}\)までに弱めて簡易化する。
• 簡易化した定義を、三関数を参考にして更に簡潔にする。
• ブーフフルツのヒドラの計算規則がラベルのみの比較で構成されている点に注目し、同様にこの表記も\(\psi\)の添字のみの比較で構成する。
• \(\mathrm{BO}\)までを記述するためには添字が自然数であればよいので、3と合わせると定義から大小関係を省くことができる。言い換えると、自然数に元々備わっている大小関係を使うことによって、項同士の大小関係を代替することができる。
• 大小関係を省いた表記は既にTSS-ψ関数やハイパー原始ψ関数で実現されている。特に、ハイパー原始ψ関数は「数列を添字に埋め込む」という発想によって実現されている。この表記でも、ブーフフルツのψ関数の添字を「先頭に0がくっついているだけのベクレミシェフの虫」と見なした定義を構成する。

なお、このブログ記事を通して読者が成長できるように、表記を3種類に分けて定義する。

1. #数列の添字化型定義
2. #共終数型定義
3. #順序付き定義

1は、ベクレミシェフの虫の計算方法に寄せた定義方法である。ベクレミシェフの虫が理解できれば、この定義にも取り組みやすいだろう。2は、1の「数列の添字化」成分を「共終数」(を、計算可能にするために形式的文字で翻訳したもの)で置き換えた定義である。dom型表記と呼ばれている表記で用いられている定義方法であり、配列・ネスト型表記の最前線に立つ表記にも用いられている手法である。是非1の定義が理解出来たら2の定義に挑戦してほしい。3は、2の表記に「項同士の大小比較」の定義を加えたものである。1と2では\(\psi\)の添字を比較していたが、3では大小比較を表記の項同士で行うようになっている。表記の項同士の大小比較は、TSS-ψ関数やハイパー原始ψ関数のような特別な例を除いて、\(\mathrm{BO}\)レベル以降の配列・ネスト型表記ではほぼ必須の概念となる。2の定義が理解できた人には、今後の為にも是非3の定義に慣れておくことをお勧めする。

数列の添字化型定義

表記

まずは表記に用いる文字列を決定し、その文字列全体の集合を定義する。文字列全体の集合を定義する理由は、計算規則を写像で定義したいからである。1つ1つの文字列は「項」と呼ばれることが多い。

\(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)\)と略記する。

次に、先ほど表記に使用すると決めた文字列の内、自然数から自然数に対応することが意図される項への変換写像を定義する。すなわち、何らかの自然数を入力するとそれに対応する表記の項が返ってくる写像である。この手順は「自然数の形式化/符号化/コード化」と呼ばれることが多い。

計算可能全域写像 \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 \notin \{0,1\}\)ならば、\($n := $(n-1)+$1\)である。

最後に、表記に使う実際の文字列全体の集合を定義する。これは、この表記で使う項が先に定義した写像によって添字が自然数と同一視できるようなものに限られるためである。添字に入る文字列が自然数と同一視できるものに限らなくてよい場合は、このステップは不要である。実際に欲しい文字列全体の集合を、事前に定義した集合の部分集合として定義してしまう手法は利便性が高いため、是非習得しておきたい。

部分集合\(RT \subset T\)と\(RPT \subset PT\)を以下のように同時に再帰的に定める:

1. \(0 \in RT\)である。
2. いかなる\((a,b) \in RPT \times (RT \setminus \{0\})\)に対しても、\(a+b \in RT\)である。
3. いかなる\((a,b) \in \mathbb{N} \times RT\)に対しても、\(\psi_{$a}(b) \in RPT \cap RT\)である。

探索関数

ここでは、ベクレミシェフの虫でいうところの「良い部分」か「悪い部分」かを判定する写像を定義する。ベクレミシェフの虫では、「良い部分」か「悪い部分」かの判定には数列の末項の情報を使用している。そこで、まずは数列の末項に相当する部分を抽出する写像を定義する。なお、数列の末項はヒドラになぞらえて「切る部分(cut part)」と呼ばれることが多い。

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

1. \(s = 0\)ならば、\(\textrm{cp}(s) := 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{cp}(s) := \textrm{cp}(b)\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{cp}(b) = 0\)ならば、\(\textrm{cp}(s) := s\)である。
   2. \(\textrm{cp}(b) \neq 0\)ならば、\(\textrm{cp}(s) := \textrm{cp}(b)\)である。

次に、切る部分を抽出する写像を元に、「良い部分(good part)」か「悪い部分(bad part)」かを判定する写像を定義する。悪い部分の最初の要素は「悪い根(bad root)」と呼ばれることが多い。

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

1. \(s = 0\)ならば、\(\textrm{br}(s) := bp\)である。
2. \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{br}(s) := \textrm{br}(b)\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{br}(b) = gp\)ならば、\(\textrm{br}(s) := gp\)である。
   2. \(\textrm{br}(b) = bp\)とする。
      1. \(\textrm{cp}(b) = 0\)ならば、\(\textrm{br}(s) := bp\)である。
      2. \(\textrm{cp}(b) = $1\)ならば、\(\textrm{br}(s) := gp\)である。
      3. \(\textrm{cp}(b) \notin \{0,$1\}\)ならば、\(\textrm{cp}(b) = \psi_{$c}(0)\)を満たす\(c \in \mathbb{N} \setminus \{0\}\)が存在する。
         1. \(c \le a\)ならば、\(\textrm{br}(s) := bp\)である。
         2. \(a \lt c\)ならば、\(\textrm{br}(s) := gp\)である。

基本列

ここでは、展開規則となる基本列を写像によって定義する。

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

1. \(s = 0\)ならば、\(s[t] := 0\)である。
2. \(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'\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{br}(b) = gp\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
   2. \(\textrm{br}(b) = bp\)とする。
      1. \(\textrm{cp}(b) = 0\)ならば、\(s[t] := t\)である。
      2. \(\textrm{cp}(b) = $1\)とする。
         1. \(t = t[0]+$1\)ならば、\(s[t] := s[t[0]]+s[$1]\)である。
         2. \(t \neq t[0]+$1\)ならば、\(s[t] := \psi_{$a}(b[0])\)である。
      3. \(\textrm{cp}(b) \notin \{0,$1\}\)ならば、\(\textrm{cp}(b) = \psi_{$c}(0)\)を満たす\(c \in \mathbb{N} \setminus \{0\}\)が存在する。
         1. \(c \le a\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
         2. \(a \lt c\)とする。
            1. \(t = $i\)を満たす\(i \in \mathbb{N} \setminus \{0\}\)と\(s[t[0]] = \psi_{$a}(\Gamma)\)を満たす\(\Gamma \in RT\)が存在するならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(\Gamma)])\)である。
            2. そうでないならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(0)])\)である。

急増加関数

最後に、表記に付随する急増加関数を定義する。

計算可能部分写像 \begin{eqnarray*} f \colon RT \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:

1. \(m = 0\)ならば、\(f_s^m(n) := n\)である。
2. \(m = 1\)とする。
   1. \(s = 0\)ならば、\(f_s^m(n) := n+1\)である。
   2. \(s = $1\)または\(s = t+$1\)を満たす\(t \in T\)が存在するならば、\(f_s^m(n) := f_{s[0]}^n(n)\)である。
   3. 上記のいずれの条件も満たさないならば、\(f_s^m(n) := f_{s[$n]}^1(n)\)である。
3. \(m \notin \{0,1\}\)ならば、\(f_s^m(n) := f_s^1(f_s^{m-1}(n))\)である。

共終数型定義

表記

\(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)\)と略記する。

計算可能性に意味を持たせるために\(\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\)である。

部分集合\(RT \subset T\)と\(RPT \subset PT\)を以下のように同時に再帰的に定める:

1. \(0 \in RT\)である。
2. いかなる\((a,b) \in RPT \times (RT \setminus \{0\})\)に対しても、\(a+b \in RT\)である。
3. いかなる\((a,b) \in \mathbb{N} \times RT\)に対しても、\(\psi_{$a}(b) \in RPT \cap RT\)である。

共終数

共終数はとても便利な概念で、切る部分の抽出と良い部分、悪い部分の判定、悪い根の決定を1つの写像で行うことができる。

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

1. \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)ならば、\(\textrm{dom}(s) := s\)である。
   2. \(\textrm{dom}(b) = $1\)ならば、\(\textrm{dom}(s) := $\omega\)である。
   3. \(\textrm{dom}(b) = $\omega\)ならば、\(\textrm{dom}(s) := $\omega\)である。
   4. \(\textrm{dom}(b) \notin \{0,$1,$\omega\}\)ならば、\(\textrm{dom}(b) = \psi_{$c}(0)\)を満たす\(c \in \mathbb{N}\)が存在する。
      1. \(c \le a\)ならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
      2. \(a \lt c\)ならば、\(\textrm{dom}(s) := $\omega\)である。

基本列

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

1. \(s = 0\)ならば、\(s[t] := 0\)である。
2. \(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'\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)ならば、\(s[t] := t\)である。
   2. \(\textrm{dom}(b) = $1\)とする。
      1. \(t = t[0]+$1\)ならば、\(s[t] := s[t[0]]+s[$1]\)である。
      2. \(t \neq t[0]+$1\)ならば、\(s[t] := \psi_{$a}(b[0])\)である。
   3. \(\textrm{dom}(b) = $\omega\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
   4. \(\textrm{dom}(b) \notin \{0,$1,$\omega\}\)ならば、\(\textrm{dom}(b) = \psi_{$c}(0)\)を満たす\(c \in \mathbb{N}\)が存在する。
      1. \(c \le a\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
      2. \(a \lt c\)とする。
         1. \(t = $i\)を満たす\(i \in \mathbb{N} \setminus \{0\}\)と\(s[t[0]] = \psi_{$a}(\Gamma)\)を満たす\(\Gamma \in RT\)が存在するならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(\Gamma)])\)である。
         2. そうでないならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(0)])\)である。

急増加関数

計算可能部分写像 \begin{eqnarray*} f \colon RT \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:

1. \(m = 0\)ならば、\(f_s^m(n) := n\)である。
2. \(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)\)である。
3. \(m \notin \{0,1\}\)ならば、\(f_s^m(n) := f_s^1(f_s^{m-1}(n))\)である。

順序付き定義

表記

\(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)\)と略記する。

計算可能性に意味を持たせるために\(\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\)である。

部分集合\(RT \subset T\)と\(RPT \subset PT\)を以下のように同時に再帰的に定める:

1. \(0 \in RT\)である。
2. いかなる\((a,b) \in RPT \times (RT \setminus \{0\})\)に対しても、\(a+b \in RT\)である。
3. いかなる\((a,b) \in \mathbb{N} \times RT\)に対しても、\(\psi_{$a}(b) \in RPT \cap RT\)である。

順序

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

共終数

順序を定義することで、共終数をさらに便利に定義できる。

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

1. \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
2. \(s = a+b\)を満たす\((a,b) \in RPT \times (RT \setminus \{0\})\)が存在するならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)ならば、\(\textrm{dom}(s) := s\)である。
   2. \(\textrm{dom}(b) = $1\)ならば、\(\textrm{dom}(s) := $\omega\)である。
   3. \(\textrm{dom}(b) \notin \{0,$1\}\)とする。
      1. \(\textrm{dom}(b) \lt s\)ならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
      2. \(s \le \textrm{dom}(b)\)ならば、\(\textrm{dom}(s) := $\omega\)である。

基本列

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

1. \(s = 0\)ならば、\(s[t] := 0\)である。
2. \(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'\)である。
3. \(s = \psi_{$a}(b)\)を満たす\((a,b) \in \mathbb{N} \times RT\)が存在するとする。
   1. \(\textrm{dom}(b) = 0\)ならば、\(s[t] := t\)である。
   2. \(\textrm{dom}(b) = $1\)とする。
      1. \(t = t[0]+$1\)ならば、\(s[t] := s[t[0]]+s[$1]\)である。
      2. \(t \neq t[0]+$1\)ならば、\(s[t] := \psi_{$a}(b[0])\)である。
   3. \(\textrm{dom}(b) \notin \{0,$1\}\)とする。
      1. \(\textrm{dom}(b) \lt s\)ならば、\(s[t] := \psi_{$a}(b[t])\)である。
      2. \(s \le \textrm{dom}(b)\)ならば、\(\textrm{dom}(b) = \psi_{$c}(0)\)を満たす\(c \in \mathbb{N}\)が存在する。
         1. \(t = $i\)を満たす\(i \in \mathbb{N} \setminus \{0\}\)と\(s[t[0]] = \psi_{$a}(\Gamma)\)を満たす\(\Gamma \in RT\)が存在するならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(\Gamma)])\)である。
         2. そうでないならば、\(s[t] := \psi_{$a}(b[\psi_{$c[0]}(0)])\)である。

急増加関数

計算可能部分写像 \begin{eqnarray*} f \colon RT \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:

1. \(m = 0\)ならば、\(f_s^m(n) := n\)である。
2. \(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)\)である。
3. \(m \notin \{0,1\}\)ならば、\(f_s^m(n) := f_s^1(f_s^{m-1}(n))\)である。