φ関数
前提
超限順序数で$ \omegaとか$ \epsilonとかの順序数を扱った 自然数の極限として$ \omegaが生まれ、$ \omegaによる計算の極限として$ \epsilonが生まれた
当然$ \epsilonにも限界は来るので新しい記号が必要となる（一応$ \zetaという順序数がある）
その記号にもいつか限界が来る
限界が来る度に新しい記号を作っていたのではキリが無いのでこれらの順序数を関数で表せるようにしたものがφ関数
ここでの表記
$ \omega=\{0,1,2,\cdots\}
収束列は集合の形で表現する
集合には本来順序は無いが、順序数の集合は必ず大小関係によって順序集合となるので問題ない
$ \omega\lbrack 3 \rbrack = 3
極限順序数の後ろに$ \lbrack\alpha\rbrackと付けたら収束列の$ \alpha番目の要素を取り出すことを意味する
場合によっては$ \alphaが有限の数でないこともある
宗教上の理由でインデックスは0から始まるものとします（巨大数wikiの方は多分1からとして書いてあるっぽい）
.$ \#
定義の時に使う
1個以上の任意の引数の列
等号の前後でそのまま引き継がれる部分を表す
.$ \vec{0}
定義の時に使う
0個以上の0の引数の列
「0個以上」なのでその場所に引数が無い状態も含む
用語
極限順序数
"前者"を持たない順序数
.$ x+1=\alphaを満たすような$ xが存在しない順序数
例えば$ \omegaとか$ \epsilon_0とか$ \omega^{\omega^2}+\omega\cdot3とか
後継順序数
極限の逆で"前者"がある順序数
.$ x+1=\alphaを満たすような$ xが存在する順序数
例えば$ \omega+1とか$ \epsilon_0+2とか$ \omega^{\omega^2}+\omega\cdot3+4とか
基本的に末尾に自然数が加算されてたら後継順序数
収束列
$ 0,1,2,\cdotsという自然数の並びの果に$ \omegaという極限順序数が定義される
$ \omega以降も$ \omega,\omega+1,\omega+2,\cdotsという数列の果に$ \omega+\omega=\omega\cdot2がある
同様にして$ \omega\cdot3,\omega\cdot4,\cdotsと極限順序数が作られ、その列の果に$ \omega^2が現れる
ある数列の極限として新たな極限順序数が作られる
その極限順序数を並べて更に新しい極限順序数を作れる
定義
Rule 1. 引数が1つのとき
.$ \phi(\alpha)=\omega^\alpha
Rule 2. 引数が2つ以上で1つ目が0のとき
.$ \phi(0,\#)=\phi(\#)
Rule 3. 引数がちょうど2つで最初の引数が1、後の引数が後継順序数のとき
.$ \phi(1,\beta+1)\lbrack0\rbrack=\phi(1,\beta)
.$ \phi(1,\beta+1)\lbrack n\rbrack=\phi(1,\beta)^{\phi(1,\beta+1)\lbrack n-1\rbrack}\ \ \ \ (n>0)
Rule 4. 2つ以上の引数で後ろの方に極限順序数があり、その後末尾まで0が1個以上続くとき
.$ \phi(\#,\alpha,0,\vec0)\lbrack n\rbrack=\phi(\#,\alpha\lbrack n\rbrack,0,\vec0)
Rule 5. 2つ以上の引数で後ろの方に極限順序数があり、その後0個以上の0の列を挟んで末尾が後継順序数のとき
.$ \phi(\#,\alpha,\vec0,\beta+1)\lbrack n\rbrack=\phi(\#,\alpha\lbrack n\rbrack,\phi(\#,\alpha,\vec0,\beta),\vec0)
Rule 6. 2つ以上の引数で後ろの方に後継順序数があり、その後末尾まで0が1個以上続くとき
.$ \phi(\#,\alpha+1,0,\vec0)\lbrack0\rbrack=\phi(\#,\alpha,0,\vec0)
.$ \phi(\#,\alpha+1,0,\vec0)\lbrack n\rbrack=\phi(\#,\alpha,\phi(\#,\alpha+1,0,\vec0)\lbrack n-1\rbrack,\vec0)\ \ \ \ (n>0)
Rule 7. 2つ以上の引数で後ろの方に後継順序数があり、その後0個以上の0の列を挟んで末尾が後継順序数のとき
.$ \phi(\#,\alpha+1,\vec0,\beta+1)\lbrack1\rbrack=\phi(\#,\alpha+1,\vec0,\beta)+1
.$ \phi(\#,\alpha+1,\vec0,\beta+1)\lbrack n\rbrack=\phi(\#,\alpha,\phi(\#,\alpha+1,\vec0,\beta)\lbrack n-1\rbrack,\vec0)
Rule 8. 末尾が極限順序数のとき
.$ \phi(\#,\beta)\lbrack n\rbrack=\phi(\#,\beta\lbrack n\rbrack)
2変数
$ \phi(0,\alpha)=\phi(\alpha)=\omega^\alpha(Rule 2, 1)
$ \phi(1,0)=\{\phi(0,0),\phi(0,\phi(1,0)\lbrack0\rbrack),\phi(0,\phi(1,0)\lbrack1\rbrack),\phi(0,\phi(1,0)\lbrack2\rbrack),\cdots\}(Rule 6)
$ \ \ \ =\{1,\phi(0,1),\phi(0,\phi(0,1)),\phi(0,\phi(0,\phi(0,1))),\cdots\}
$ \ \ \ =\{1,\phi(1),\phi(\phi(1)),\phi(\phi(\phi(1))),\cdots\}
$ \ \ \ =\{1,\omega,\phi(\omega),\phi(\phi(\omega)),\cdots\}
$ \ \ \ =\{1,\omega,\omega^\omega,\omega^{\omega^\omega},\cdots\}
$ \ \ \ =\epsilon_0
.$ \alpha=\phi(0,\alpha)\Leftrightarrow\alpha\ge\phi(1,0)
$ \phi(1,1)=\{\phi(1,0),\phi(1,0)^{\phi(1,0)},\phi(1,0)^{\phi(1,0)^{\phi(1,0)}},\cdots\}(Rule 3)
$ \ \ \ =\{\epsilon_0,\epsilon_0^{\epsilon_0},\epsilon_0^{\epsilon_0^{\epsilon_0}},\cdots\}
$ \ \ \ =\epsilon_1
.$ \alpha=\phi(1,0)^\alpha\Leftrightarrow\alpha\ge\phi(1,1)
$ \phi(1,n+1)=\{\phi(1,\alpha),\phi(1,n)^{\phi(1,n)},\phi(1,n)^{\phi(1,n)^{\phi(1,n)}},\cdots\}(Rule 3)
$ \ \ \ =\epsilon_{n+1}
.$ \alpha=\phi(1,n)^\alpha\Leftrightarrow\alpha\ge\phi(1,n+1)
$ \phi(1,\omega)=\{\phi(1,0),\phi(1,1),\phi(1,2),\cdots\}(Rule 8)
$ \ \ \ =\{\epsilon_0,\epsilon_1,\epsilon_2,\cdots\}
$ \ \ \ =\epsilon_\omega
$ \phi(1,\phi(1,0))=\phi(1,\epsilon_0)=\epsilon_{\epsilon_0}
$ \phi(1,\phi(1,\phi(1,0))=\epsilon_{\epsilon_{\epsilon_0}}
$ \phi(2,0)=\{\phi(1,0),\phi(1,\phi(1,0)),\phi(1,\phi(1,\phi(1,0))),\cdots\}(Rule 6)
$ \ \ \ =\{\epsilon_0,\epsilon_{\epsilon_0},\epsilon_{\epsilon_{\epsilon_0}},\cdots\}
$ \phi(2,\omega)=\{\phi(2,0),\phi(2,1),\phi(2,2),\cdots\}(Rule 8)
.$ \alpha=\phi(1,\alpha)\Leftrightarrow\alpha\ge\phi(2,0)
$ \phi(2,1)=\{\phi(2,0)+1,\phi(1,(\phi(2,0)+1)),\phi(1,\phi(1,(\phi(2,0)+1))),\cdots\}(Rule 7)
$ \phi(2,n+1)=\{\phi(2,n)+1,\phi(1,(\phi(2,n)+1)),\phi(1,\phi(1,(\phi(2,n)+1))),\cdots\}
$ \phi(2,\phi(1,0))=\{\phi(2,1),\phi(2,\phi(1)),\phi(2,\phi(\phi(1))),\phi(2,\phi(\phi(\phi(1)))),\cdots\}(Rule 8)
$ \phi(2,\phi(2,0))=\{\phi(2,\phi(1,0)),\phi(2,\phi(1,\phi(1,0))),\phi(2,\phi(1,\phi(1,\phi(1,0)))),\phi(2,\phi(1,\phi(1,\phi(1,\phi(1,0))))),\cdots\}
$ \phi(2,\phi(2,\phi(2,0)))=\{\phi(2,\phi(2,\phi(1,0))),\phi(2,\phi(2,\phi(1,\phi(1,0)))),\phi(2,\phi(2,\phi(1,\phi(1,\phi(1,0))))),\cdots\}
$ \phi(3,0)=\{\phi(2,0),\phi(2,\phi(2,0)),\phi(2,\phi(2,\phi(2,0))),\cdots\}(Rule 6)
$ \phi(n+1,0)=\{\phi(n,0),\phi(n,\phi(n,0)),\phi(n,\phi(n,\phi(n,0))),\cdots\}
.$ \alpha=\phi(n,\alpha)\Leftrightarrow\alpha\ge\phi(n+1,0)
$ \phi(\omega,1)=\{\phi(0,\phi(\omega,0)),\phi(1,\phi(\omega,0)),\phi(2,\phi(\omega,0)),\cdots\}(Rule 5)
$ \phi(\omega,0)=\{\phi(0,0),\phi(1,0),\phi(2,0),\phi(3,0),\cdots\}(Rule 4)
$ \ \ \ =\{1,\epsilon_0,\phi(2,0),\phi(3,0),\cdots\}
$ \phi(\omega,\omega)=\{\phi(\omega,0),\phi(\omega,1),\phi(\omega,2),\cdots\}(Rule 8)
$ \phi(\omega,\phi(\omega,0))=\{\phi(\omega,\phi(0,0)),\phi(\omega,\phi(1,0)),\phi(\omega,\phi(2,0)),\cdots\}(Rule 8)
$ \phi(\omega+1,0)=\{\phi(\omega,0),\phi(\omega,\phi(\omega,0)),\phi(\omega,\phi(\omega,\phi(\omega,0))),\cdots\}(Rule 6)
$ \phi(\phi(1,0),0)=\{\phi(1,0),\phi(\phi(1),0),\phi(\phi(\phi(1)),0),\phi(\phi(\phi(\phi(1))),0),\cdots\}
$ \phi(\phi(\phi(1,0),0),0)=\{\phi(\phi(1,0),0),\phi(\phi(\phi(1),0),0),\phi(\phi(\phi(\phi(1)),0),0),\phi(\phi(\phi(\phi(\phi(1))),0),0),\cdots\}
3変数以上
$ \phi(1,0,0)=\{\phi(0,0,0),\phi(0,\phi(0,0,0),0),\phi(0,\phi(0,\phi(0,0,0),0),0),\phi(0,\phi(0,\phi(0,\phi(0,0,0),0),0),0),\cdots\}(Rule 6)
$ \ =\{\phi(0),\phi(\phi(0),0),\phi(\phi(\phi(0),0),0),\phi(\phi(\phi(\phi(0),0),0),0),\cdots\}(Rule 2)
$ \ =\{1,\phi(1,0),\phi(\phi(1,0),0),\phi(\phi(\phi(1,0),0),0),\cdots\}
.$ \alpha=\phi(\alpha,0)\Leftrightarrow\alpha\ge\phi(1,0,0)
$ \phi(1,0,1)=\{\phi(1,0,0)+1,\phi(0,(\phi(1,0,0)+1),0),\phi(0,\phi(0,(\phi(1,0,0)+1),0),0),\cdots\}(Rule 7)
$ \ =\{\phi(1,0,0)+1,\phi((\phi(1,0,0)+1),0),\phi(\phi((\phi(1,0,0)+1),0),0),\cdots\}(Rule 2)
$ \phi(1,0,\omega)=\{\phi(1,0,0),\phi(1,0,1),\phi(1,0,2),\phi(1,0,3),\cdots\}(Rule 8)
$ \phi(1,0,\phi(1,0,0))=\{\phi(1,0,1),\phi(1,0,\phi(1,0)),\phi(1,0,\phi(\phi(1,0),0)),\phi(1,0,\phi(\phi(\phi(1,0),0),0)),\cdots\}
$ \phi(1,1,0)=\{\phi(1,0,0),\phi(1,0,\phi(1,0,0)),\phi(1,0,\phi(1,0,\phi(1,0,0))),\cdots\}(Rule 6)
.$ \alpha=\phi(1,0,\alpha)\Leftrightarrow\alpha\ge\phi(1,1,0)
$ \phi(1,1,1)=\{\phi(1,1,0)+1,\phi(1,0,(\phi(1,1,0)+1)),\phi(1,0,\phi(1,0,(\phi(1,1,0)+1))),\cdots\}(Rule 7)
$ \phi(1,1,\omega)=\{\phi(1,1,0),\phi(1,1,1),\phi(1,1,2),\phi(1,1,3),\cdots\}(Rule 8)
$ \phi(1,1,\phi(1,1,0))=\{\phi(1,1,\phi(1,0,0)),\phi(1,1,\phi(1,0,\phi(1,0,0))),\phi(1,1,\phi(1,0,\phi(1,0,\phi(1,0,0)))),\cdots\}
$ \phi(1,2,0)=\{\phi(1,1,0),\phi(1,1,\phi(1,1,0)),\phi(1,1,\phi(1,1,\phi(1,1,0))),\cdots\}(Rule 6)
$ \phi(1,n+1,0)=\{\phi(1,n,0),\phi(1,n,\phi(1,n,0)),\phi(1,n,\phi(1,n,\phi(1,n,0))),\cdots\}
.$ \alpha=\phi(1,n,\alpha)\Leftrightarrow\alpha\ge\phi(1,n+1,0)
$ \phi(1,\omega,0)=\{\phi(1,0,0),\phi(1,1,0),\phi(1,2,0),\phi(1,3,0),\cdots\}
$ \phi(1,\phi(1,0,0),0)=\{\phi(1,1,0),\phi(1,\phi(1,0),0),\phi(1,\phi(\phi(1,0),0),0),\cdots\}
$ \phi(2,0,0)=\{\phi(1,0,0),\phi(1,\phi(1,0,0),0),\phi(1,\phi(1,\phi(1,0,0),0),0),\cdots\}
$ \phi(n+1,0,0)=\{\phi(n,0,0),\phi(n,\phi(n,0,0),0),\phi(n,\phi(n,\phi(n,0,0),0),0),\cdots\}
.$ \alpha=\phi(n,\alpha,0)\Leftrightarrow\alpha\ge\phi(n+1,0,0)
$ \phi(\omega,0,0)=\{\phi(0,0,0),\phi(1,0,0),\phi(2,0,0),\phi(3,0,0),\cdots\}
$ \phi(\phi(1,0,0),0,0)=\{\phi(1,0,0),\phi(\phi(1,0),0,0),\phi(\phi(\phi(1,0),0),0,0),\cdots\}
$ \phi(1,0,0,0)=\{\phi(1,0,0),\phi(\phi(1,0,0),0,0),\phi(\phi(\phi(1,0,0),0,0),0,0),\cdots\}
.$ \alpha=\phi(\alpha,0,0)\Leftrightarrow\alpha\ge\phi(1,0,0,0)
まとめ
.$ x=\phi(x,\vec0)\Leftrightarrow x\ge\phi(1,0,\vec0)
.$ x=\phi(\#,\alpha,x,\vec0)\Leftrightarrow x\ge\phi(\#,\alpha+1,0,\vec0)