序文[]
この記事では、あなたが巨大数を作成する手助けとなるように、主に原始再帰法や多重再帰関数といった話題に関して解説しています。これらは (特に種々の帰納法は)、私たちが巨大数やそれを生みだす関数を定義する際のあらゆる基礎に位置するものです。従って、それぞれの方法で何ができるか、できないかを理解することは、よい定義のもの (他人に理解がしやすいとか表現が曖昧じゃないとか、いろいろ) を私たちが作る上で多大なる助けとなってくれるでしょう。
関連記事[]
- ユーザーブログ:Kanrokoti/定義のエッセンス - より実際的に、巨大数を作るためのシステムや表示を定義するステップ、「どのように定義を書くか」という観点からの解説記事。
原始再帰法[]
危険な再帰[]
例としてまず、テトレーションの定義を書いてみましょう。
| 例2.1 テトレーションの定義 |
|---|
自然数\(m (\geq 0)\)と0でない自然数\(n\)に対して、テトレーション\(n\uparrow\uparrow m\)を次で定義する：
|
定義文中に、定義すべきもの自身が登場していることを指して再帰的と言います。プログラミングをやる人にはもしかしたら馴染みがあるかもしれません。ですが、本来は定義文中に自分自身を出現させるようなことはできません。悪い例を挙げてみましょう。
| 例2.2 "定義"の定義(？) |
|---|
| 定義とは、その意味をはっきりと定義することである。 |
この例では、「定義」とは？という問いに対して「定義すること」だと答えています。間違いなく、だから何なんだ！問いに何も答えてないじゃないか！とツッコミを受ける事でしょう。国語辞典で意味を調べた場合は、例えば次のように書かれています。
| 例2.3 "定義"とは (デジタル大辞泉より一部抜粋) |
|---|
| てい‐ぎ【定義】 ［名］(スル) |
数学においても、基本はこれと変わりません。定義しようとしている事物が何であるかがはっきりしないなら、それは定義ではありません。
自然数と原始再帰[]
それでは、先ほど例に出したテトレーションの定義はなぜOKなのでしょうか？定義に沿って\(3\uparrow\uparrow 3\)を計算してみましょう。
- \(\begin{align}3\uparrow\uparrow 3&=3\uparrow\uparrow(2+1)\\&=3^{3\uparrow\uparrow 2}\\&=3^{3\uparrow\uparrow(1+1)}\\&=3^{3^{3\uparrow\uparrow 1}}\\&=3^{3^{3\uparrow\uparrow(0+1)}}\\&=3^{3^{3^{3\uparrow\uparrow 0}}}\\&=3^{3^{3^1}}\\&=3^{3^3}\\&=3^{27}\\&=7625597484987\end{align}\)
ということで、先ほど定義したテトレーションの定義と一般的な足し算・掛け算・べき乗の計算規則を使うことで、\(3\uparrow\uparrow 3\)の値が確かに計算できました。
これは、自然数が次のような性質を持っていることに起因します (詳しくはWikipediaのペアノの公理などを参照)：
- 全ての自然数\(m\)は「0」か「ある自然数\(m'\)の次の数」のどちらかが成り立つ (0と「自然数\(m'\)の次の数」は自然数である)。
- 全ての自然数\(m\)は「0」か「ある自然数\(m'\)の次の数」のどちらか一方のみが成り立つ。
- 自然数\(m\)が「ある自然数\(m'\)の次の数」であるならば、そのような\(m'\)はただ1つである。
- 自然数を引数に取る関数\(f(n)\)について、\(f(0)\)が定まっていて、\(f(n)\)から\(f(n+1)\)が定まるならば、全ての自然数\(n\)について\(f(n)\)がただ1つ定まる。
特に最後の性質があるために、私たちは原始再帰という方法によって、自然数を引数にとる関数を定義することができます。
| 定義2.4 原始再帰 (1変数版) |
|---|
\(a\)を自然数、\(g:\mathbb{N}^2\to\mathbb{N}\)は自然数上の既知の関数とする。このとき、
によって自然数上の関数\(f\)を定義することができる。この方法を(1変数の場合の)原始再帰と言う。 |
ここで\(g\)が既知の関数であるということは、\(f\)を定義する際には私たちは既に\(g(n,m)\)の値を求めることができるということです。\(g\)の値の計算にまだ定義してもいない\(f\)が紛れ込んだりしないよう気をつけてください。
定数関数、後者関数、射影関数と関数の合成、そして原始再帰のみで定義できる関数を原始再帰関数と言います。ここでは詳しくは書きませんが、方法の名前と関数の種別とを混同しないようにしてください。
原始再帰は、より変数が多い場合にも定義できます。
| 定義2.5 原始再帰 (多変数版) |
|---|
\(g(x_1,\ldots,x_N)\)は自然数上の\(N\)変数関数、\(h(x_1,\ldots,x_N,y,z)\)は自然数上の\(N+2\)変数関数とする。このとき、
によって自然数上の\(N+1\)変数関数\(f\)を定義することができる。この方法を原始再帰という。 |
原始再帰法においては、\(f(x_1,\ldots,x_N,n+1)\)の定義中に\(f(x_1,\ldots,x_N,n)\)が登場しますが、これはこの形を保たなくてはならないことに注意してください。つまり、右辺では\(f(x_1,\ldots,x_N,n)\)を登場させてよいのであって、\(f\)をどのように使ってもいいわけではありません。例えば、勝手に全変数に\(n\)を代入して\(f(n,\ldots,n)\)と言う形に変更したら、それはもはや原始再帰ではありません。原始再帰でないパターンについては後述しますので、それらのアイデアはちょっと脇に置いておきましょう。
繰り返しは強い[]
原始再帰によって定義できる操作の1つに、関数の反復適用があります。
| 定義2.6 反復適用 |
|---|
\(f(n)\)を自然数上の関数、\(k\)を自然数とする。このとき、\(f\)の反復適用\(f^n(k)\)を以下で定義する：
|
反復適用は原始帰納によって定義できますが、逆に原始帰納を反復適用によって定義することもできるため、この2つは等価であることが知られています (後者の実装はテクニカルなためここでは省略します)。
反復適用、あるいは原始再帰は、巨大関数をより大きくする (おそらく) 最もシンプルな方法です。
| 命題2.7 |
|---|
自然数上の関数\(f:\mathbb{N}\to\mathbb{N}\)が次の2つの条件を満たすとする：
このとき、\(f^n(n)\)は\(n\)に対して単調かつ\(n\geq 1\)で\(f(n)\leq f^n(n)\)であり、さらに\(n\geq 2\)で\(f(n)< f^n(n)\)。 |
| 命題2.8 |
自然数上の関数\(f:\mathbb{N}\to\mathbb{N}\)が次の2つの条件を満たすとする：
このとき、自然数\(k\)に対して\(g_k(n)=f^n(k)\)とすると、
|
関数 \(f(n)\) に対して、原始再帰を使うことにより2変数関数 \(g(m,n)=f^m(n)\) が定義できます。従って、両方に同じ変数を代入する合成により \(f^n(n)\) が定義できます。従って、急増加関数の階層を1増やす操作は原始再帰と関数の合成によって定義ができます。ここから逆に、原始再帰は (通常の) 急増加関数の階層を最大1増やすということも成り立ちます。
停止性が非自明な関数[]
原始再帰や、あるいは後述するようなよく知られた方法を使わない場合、計算の停止性は非自明になります。巨大数関連で言えば、例えばバシク行列システムの停止性は完全に証明されたわけではありません。次の例は巨大数を生成するような種類ではないですが、計算が停止することが非自明な定義を持ち、特定の分野では比較的有名な例です。
| 例2.9 マッカーシーの91関数 |
|---|
マッカーシーの91関数とは、以下で定義される1変数関数である：
この関数は全域関数である。すなわち任意の自然数に対して\(M(n)\)の値が定まる。 |
| 例2.10 竹内のたらい回し関数 |
竹内のたらい回し関数とは、以下で定義される(整数上の)3変数関数である：
|
高階数え上げから多変数関数まで[]
アッカーマン関数[]
原始帰納法を超える関数と言えばやはり最初に挙げられるものはアッカーマン関数でしょう。
| 例3.1 アッカーマン関数 |
|---|
アッカーマン関数は、以下で定義される自然数上の2変数関数である：
|
| 事実 |
| 任意の原始再帰関数\(f(n)\)に対して、十分大きい\(m\)で\(f(m)< A(m,0)\)。 これにより、アッカーマン関数は原始再帰関数ではないことが示される。 |
アッカーマン関数は原始再帰関数でない一方で、自然数\(k\)を固定したときの関数\(A_k(n)=A(k,n)\)はそれぞれ原始再帰関数です。逆に言うと、アッカーマン関数\(A(m,n)\)が原始再帰関数でないことは、主に第一変数\(m\)の働きによるものであるという事です。第一変数\(m\)は、一列に並べられた可算個の関数\(A_0,A_1,A_2,\ldots\)の中から\(m\)番目の関数\(A_m\)をピックする働きをしています。この操作に特に名前は付いていないのですが、ここでは高階数え上げと呼ぶことにします。
| 定義3.2 高階数え上げ |
|---|
自然数\(k\)を添え字に持つ\(N\)変数関数の列\(\{f_k\}_{k\in\mathbb{N}}=\{ f_0,f_1,f_2,\ldots\}\)が与えられているとき、
によって自然数上の\(N+1\)変数関数を定義することができる。この方法を (本稿では) 高階数え上げと呼ぶ。 |
高階数え上げ自体は単純な操作なので、これを行ったから必ず関数が大きくなるとは限りません (これは他の手法にも共通ですが)。しかし一方で、アッカーマン関数のように、うまく\(f_0,f_1,f_2,\ldots\)を構成して並べることができたら、原始帰納法では作ることのできない大きさの関数を作ることができます。
また、定義から、各\(f_k\)の計算がどれも停止するならば、それを数え上げただけである\(g(k,\ldots)=f_k(\ldots)\)の計算も停止することがわかります。
原始再帰関数と高階数え上げを繰り返して構成される関数は、多重再帰関数と呼ばれることもあります。おおまかな理解としては原始再帰法によって新しい関数を作る操作を数え上げると二重再帰、二重再帰を行う際の操作をまた数え上げると三重再帰……のように説明されますが、実際のところ多重再帰関数の説明はちゃんとやろうとするといろいろ簡潔に収まらなくなってしまうため、本稿ではそれらの名称は使わないでおくことにします。多重再帰関数として構成される関数は、高階数え上げを適切に繰り返すことで問題なく実装できます。興味のある人は確認してみるのもよいかもしれません。
なるべく形式的に二重再帰を定義しようとした結果どうなるかは以下のユーザーブログを参照してみてください。
多変数関数を御する[]
前節で、アッカーマン関数は可算個の関数\(A_0,A_1,A_2,\ldots\)に対して\(A(k,n)=A_k(n)\)で定義しているとも見なせるという話をしました。ここで、アッカーマン関数を\(B_0(m,n)\)として、\(B_{k+1}(m,n)\)を次で与えます：
- \(\begin{align}B_{k+1}(0,n)&=B_k(n,n)\\B_{k+1}(m+1,0)&=B_{k+1}(m,1)\\B_{k+1}(m+1,n+1)&=B_{k+1}(m,B_{k+1}(m+1,n))\end{align}\)
これは、アッカーマン関数の定義のうち\(m=0\)の場合のみを書き換えたものです。従って、\(B_k(m,n)\)の計算が停止するならば\(B_{k+1}(m,n)\)の計算は停止します。数学的帰納法によって、任意の自然数\(k\)について関数\(B_k(m,n)\)の計算は止まることが分かります。 可算個の関数\(B_0,B_1,B_2,\ldots\)が得られたので、高階数え上げによって\(B(k,m,n)=B_k(m,n)\)を定義できます。アッカーマン関数でやったことをもう一度繰り返しただけですが、あっという間にアッカーマン変数が3変数関数になりました。
逆に、例えば次のように関数\(B(k,m,n)\)の定義を書いた時に、これがちゃんと定義されているか、計算が停止するかをどのように確認したらよいでしょうか：
- \(\begin{align}B(0,0,n)&=n+1\\B(k,m+1,0)&=B(k,m,1)\\B(k+1,0,n)&=B(k,n,n)\\B(k,m+1,n+1)&=B(k,m,B(k,m+1,n))\end{align}\)
いくつかの、すぐにチェックできる、そして重要なポイントがあるのでそれを紹介します。
- 場合分けが尽くされているか
- いま\(B\)の引数である\((k,m,n)\)は自然数の3つ組を想定しているので、当然どのような自然数の3つ組に対しても定義が書いていなければなりません。特に3つのうちどれかが0である場合というのは見落としがちになるので気をつけましょう。不安ならば、例えば引数が0か0以外かの場合分けを全て (今回の例では8種類あります) 書いて確認するのがよいでしょう。
実際に全8種類書いたものは次のようになります：- \(\begin{alignat}{4}B(& &0,& &0,& &0)&=1\\B(& &0,& &0,& &n+1)&=n+2\\B(& &0,& &m+1,& &0)&=B(0,m,1)\\B(& &0,& &m+1,& &n+1)&=B(0,m,B(0,m+1,n))\\B(& &k+1,& &0,& &0)&=B(k,0,0)\\B(& &k+1,& &0,& &n+1)&=B(k,n+1,n+1)\\B(& &k+1,& &m+1,& &0)&=B(k+1,m,1)\\B(& &k+1,&\ &m+1,&\ &n+1)&=B(k+1,m,B(k+1,m+1,n))\end{alignat}\)
- 場合分けが被っていないか
- 例えば場合分けの中に\((k,0,n)\)の場合と\((k+1,m,n+1)\)の場合があったとき、\((k,m,n)=(1,0,2)\)について考えるとこれは両方に適用できてしまいます。どう適用しても同じ結果になるならそれでも問題ないのですが、そうはならない場合の方が多いと思います。なので場合分けはなるべく重複がないようにしましょう。
停止性の確認をしてみましょう。\(B(k,m,n)\)の定義で\(B(k',m',n')\)の計算が使われていることを、\((k,m,n)\succ(k',m',n')\)で表します。例えば、\((k,m+1,0)\succ(k,m,0)\)のようになります。また、\(B(0,0,n)\)の計算にはもはや\(B(\ldots)\)の計算は使わないため、\((0,0,n)\Downarrow\)で表します。これにより、例えば
- \((1,0,2)\succ(1,2,2)\succ(1,2,1)\succ(1,2,0)\succ(1,1,1)\succ\cdots\)
のように、\(B(1,0,2)\)の計算の途中でどのような計算をしているかを辿ることができます。ただし、この列は1通りではなく、途中で分岐する場合もあります。例えば、\(B\)の定義から、\((1,2,1)\succ(1,2,0)\)かつ\((1,2,1)\succ(1,1,B(1,2,0))\ (=(1,1,61))\)です。
\(B\)の計算が停止するということは、\(\succ\)で繋がったどのような列\((k_0,m_0,n_0)\succ\cdots\)であっても、ある\(I\geq 0\)が存在して\((k_I,m_I,n_I)\Downarrow\)となることと言い換えられます。これは順序集合における整礎性と同じ形の主張であるため、\(\succ\)を拡張した関係\(\succ^*\)が整礎な順序関係であれば、\(B\)の計算の停止性を示すことができます。ただしここで\(\succ^*\)が\(\succ\)の拡張であるとは、\((x\succ y)\Rightarrow(x\succ^* y)\)が成立することを言っています。
\(B\)の定義から、次のような3つ組の列が作れることが分かります：
- \((k,m+1,n+1)\succ(k,m+1,n)\succ\cdots\succ(k,m+1,0)\)
- \((k,m+1,0)\succ(k,m,1)\succ(k,m,0)\succ\cdots\succ(k,1,0)\succ(k,0,1)\succ(k,0,0)\)
- \((k,m+1,n+1)\succ(k,m,B(k,m+1,n))\)
- \((k+1,0,n)\succ(k,n,n)\)
これについて整礎性が成り立つかどうかを厳密に調べるのは大変なので、\(\succ\)の拡張\(\succ^*\)を、次のように定義します
- \(\forall k,m,n\in\mathbb{N}.(k,m,n+1)\succ^*(k,m,n)\)
- \(\forall k,m,n\in\mathbb{N}.(k,m+1,0)\succ^*(k,m,n)\)
- \(\forall k,m,n\in\mathbb{N}.(k+1,0,0)\succ^*(k,m,n)\)
- \(\succ^*\)は非反射、すなわち\(x\nsucc^*x\)
- \(\succ^*\)は非対称、すなわち\((x\succ^*y)\Rightarrow(y\nsucc^*x)\)
- \(\succ^*\)は推移的、すなわち\((x\succ^*y\succ^*z)\Rightarrow(x\succ^*z)\)
定義から\(\succ^*\)は狭義半順序であり、さらにこれは\(\langle\omega^3,\in\rangle\)に同型であることが分かるので整礎 (さらに整列集合) であることが従います。既知の整礎順序集合、特に順序数に埋め込めるような二項関係を基に関数を定義することは、停止性を保証するとてもよい方法です。例えば\(\omega^\omega\)の順序構造をあなたが知っているならば、多変数アッカーマン関数を定義することに何の恐れも感じないでしょう。
| 例3.3 \(\mathbb{N}^\omega\) |
|---|
自然数の有限個の組すべてを集めた集合を\(\mathbb{N}^\omega\)で表す。すなわち、
とする。また、\(x=(x_n,\ldots,x_1)\in\mathbb{N}^\omega\)に対して\(\vert x\vert=n\)で組の要素の個数\(n\)を表す。 このとき、\(\mathbb{N}^\omega\)の順序\(<:\)を以下で定義すると、これは整列順序\(\langle\omega^\omega,\in\rangle\)と同型になる。
|
| 例3.4 多変数アッカーマン関数 |
多変数アッカーマン関数とは、以下で定義される関数\(A(x_n,\ldots,x_1)\)である。この関数は1以上の任意有限個の変数を取る (\(n\geq 1\))。
多変数アッカーマン関数に関して先ほどと同様に計算の参照関係\(\succ\)を導入すると、これはさらに\(\langle\mathbb{N}^\omega,<:\rangle\)に埋め込めるため、この関数の計算は停止する。 |
もちろん、より複雑な定義であっても、計算での参照関係が例えば\(\mathbb{N}^\omega\)の順序関係に埋め込めるならば、計算の停止性を証明することは非常に簡単になります。多変数アッカーマン関数の増加度はWainer階層において\(<\omega^\omega\)になります。
多変数より大きな構造[]
無限変数を使えば解決だな！ガハハ[]
ここまでの内容によって、私たちは2変数、3変数、…任意有限個変数の関数を定義することができるようになりました。変数を増やした方がより強い再帰を使えるのなら、いっそ任意有限個などと変な御託を述べるよりは無限変数！非可算変数！などとやれた方がいかにも強そうです。ですが無限変数とはいったいどういう状態なのでしょうか？試しに無限変数を取る関数を考えてみましょう。先ほどの多変数アッカーマン関数などはほとんど無限に変数を並べられるのですから、少し手直しすれば大丈夫な雰囲気が出てきます。
| 例4.1 無限変数アッカーマン関数(？) |
|---|
無限変数アッカーマン関数を以下で定義 (？) する。
|
定義はほとんど多変数アッカーマン関数だからきっと問題ないはず！I WIN! と叫びたくなりますが、一応試してみましょう。無限変数ということは任意の自然数\(i\)に対して\(x_i\)の値が分かるということです。例えば\(A(\ldots,1,1,1)\)がどう計算されるか見てみましょう。
- \((\ldots,1,1,1,1)\succ(\ldots,1,1,1,0)\succ(\ldots,1,1,0,1)\succ(\ldots,1,0,1,1)\succ\cdots\)
- \(\cdots\succ(\ldots,1,1,0,0,\ldots,0,1)\succ(\ldots,1,0,1,0,\ldots,0,1)\succ\cdots\)
……この計算はいつ終わるのでしょうか？変数は無限にあるので、私たちは桁が0になるたびに次の桁に書かれた1を減らして計算を続けることができます。つまり、計算は終わりません。
例で見たように、有限と無限の間には非常に深く大きな溝が刻まれているため、少なくとも脳死で有限変数を無限変数へ拡張できることはありません。もしこのwikiや巨大数の文脈で無限変数、超限変数などと書かれている場合、無限に終わらない操作を何らかの方法で排除し、有限で終わるように技巧が凝らされているはずです。
無限を無限に繰り返して、さらにそれを無限に…[]
無限変数は実現が遠そうなので、もう少し実現可能な定義を考えてみましょう。多変数アッカーマン関数\(A(x_n,\ldots,x_1)\)に対して、次のような関数\(d_1(n)\)を考えます。
- \(d_1(n)=A(n,\ldots,n)\)、ただし\(n\)に対して\((n,\ldots,n)\in\mathbb{N}^{n+1}\)とする。
すなわち、\(n=0,1,2,3,\ldots\)に対して\(d_1(n)=A(0),A(1,1),A(2,2,2),A(3,3,3,3),\ldots\)とします。これを使って、多変数アッカーマン関数とほとんど同じ定義で関数\(A^{(1)}(x_n,\ldots,x_1)\)を定義します。
- \(\begin{align}A^{(1)}(\ldots,0,0,x_1)=A^{(1)}(x_1)&=d_1(x_1)\\A^{(1)}(\ldots,x'_2+1,0)&=A^{(1)}(\ldots,x'_2,1)\\A^{(1)}(\ldots,x'_k+1,0,0,\ldots,0,x_1)&=A^{(1)}(\ldots,x'_k,x_1,0,\ldots,0,x_1)\quad(3\leq k)\\A^{(1)}(\ldots,x'_2+1,x'_1+1)&=A^{(1)}(\ldots,x'_2,A^{(1)}(x_n,\ldots,x'_2+1,x'_1))\end{align}\)
定義から\(d_0\)は明らかに多変数アッカーマン関数を支配しています。そしてこの関数\(A^{(1)}\)は最終的に多変数アッカーマン関数よりはるかに強い関数を構成します。さらに、関数\(A^{(1)}\)は多変数アッカーマン関数のように1以上の任意有限個変数を取る関数なので、同様の手法で\(d_2(n),A^{(2)}(x_n,\ldots,x_1),d_3(n),\ldots\)を定義できます。
| 例4.2 |
|---|
自然数\(r\)に対して1変数関数\(d_r(n)\)と1以上の任意有限個変数関数\(A^{(r)}(x_N,\ldots,x_1)\)を以下で帰納的に定義する。
|
複雑な構造の「書き」方[]
前節の最後に得られた\(A^{(r)}\)によって可算個の関数の列が得られたので、高階数え上げを使えば新しい関数が作れそうです。しかし、今までと異なり各\(A^{(r)}\)は全て任意有限個の変数を取れましたから、これを新しく\(A(r,x_N,\ldots,x_1)=A^{(r)}\)などと書くと、先ほどまでの多変数アッカーマン関数での\(A(r,x_N,\ldots,x_1)\)と混同して非常に紛らわしいことになります。
紛らわしい文章や表現はなるべく回避しなければなりません。今回の場合で言えば、引数は特別なポジションにあるものが1つと、それ以外のものが\(n\)個存在するということを明示する必要があります。例えばその1個だけを別の記号で区切って、\(A(r;x_n,\ldots,x_1)\)と書けば分かりやすいですね。
| 例4.3 |
|---|
自然数\(r\)と1以上の任意の有限個の自然数\(x_n,\ldots,x_1\ (n\geq 1)\)を引数に取る関数\(A(r;x_n,\ldots,x_1)\)を以下で定義する。
|
今、新しい区切り文字で特別な扱いをする変数を1個定めたということは、繰り返せば例えば\(A(x'_{N'},\ldots,x'_1\mathpunct{;}x_N,\ldots,x_1)\)のような表記を作ることも可能な気がしますね。実際そのアイデアは実行可能です。さらに区切りを増やしたり、区切り文字の種類をさらに増やすというのもいいかもしれません。ここでひとつ問題なのは、そうして拡張した表記をどのように書くかです。区切りが増えて、区切り文字の種類を増やした状態とはどういうものでしょうか？適当に記号をそれっぽく並べて\(A(3,2\mathpunct{:}12\mathpunct{;}4/2\mid 4)\)とかを任意に書いても成立するのでしょうか？後者について答えを言ってしまうと、大抵の場合適当に記号を並べたもの全部がOKとはなりません。私たちは写像の定義域として、表記するための文字列を定義しなければなりません。
例として、任意有限個の数字の組\((x_N,\ldots,x_1)\)を任意の有限個数並べることを考えてみましょう。単純な方法としては、自然数を並べるのではなく、\(v_N,\ldots,v_1\in\mathbb{N}^\omega\)を関数に渡してやるものがあります。すなわち、\(\mathbb{N}^\omega\)の要素をまた任意の有限個数組にした集合\((\mathbb{N}^\omega)^\omega\)を考えて、定義域をそれであると指定する方法です。実際に記述する際には
- \(A(v_N,\ldots,v_1)=A((x_{NM_N},\ldots,x_{N1}),\ldots,(x_{1M_1},\ldots,x_{11}))\)
のようになるでしょう。
別の例としては、例4.3のように新たな区切り記号\(;\)を導入する方法があります。この場合は、例えば次のように書くことができるでしょう：
- \(A(t_N\mathpunct{;}\ldots\mathpunct{;}t_1)\)、このとき各\(t_i\)は1以上の有限個の自然数の組\(x_{iM_i},\ldots,x_{i1}\)。
あるいはあなたが形式言語やBNF記法に詳しければ、次のように書いてもいいでしょう：
- \(t\in T,q\in Q\)はそれぞれ次の文法で生成される記号列とする。ただし\(n\in\mathbb{N}\)である。
- \(\begin{align}t\quad&\textrm{::=}\quad n\mid n,t\\q\quad&\textrm{::=}\quad t\mid t\mathpunct{;}q\end{align}\)
- このとき、関数\(A\)は\(Q\)の要素を引数に取る自然数値関数であり、例えば\(A(3,4,1\mathpunct{;}0\mathpunct{;}0\mathpunct{;}2,1)\)などと表記される。
形式言語、特に文脈自由文法については、例えばこのスライドやこの講義資料など、オンラインにも様々な資料があります。巨大な構造を表記する際には非常にお世話になる内容ですので、勉強してみることをお勧めします。
集合の帰納的定義[]
最後に、巨大数やその表記も含め、ある集合を帰納的に定義するということについて書いておきます。
| 定義5.1 帰納的定義 |
|---|
\(\mathcal{F}\)は集合上の写像クラス、すなわち、集合\(X\)に対して集合\(\mathcal{F}X\)がただ1つ定まるような対応とする。このとき、集合\(\Sigma\)と\(\mathcal{F}\)から、集合
を定義することができる。これを集合の帰納的定義と言い、例えば実例においては以下のように記述される：
ただしこの時、集合\(\Sigma\)および写像クラス\(\mathcal{F}\)は既知のものとする。 |
帰納的に定義された集合は、その集合についての性質を帰納法によって証明することができます。特に、\(\forall x\in X.\psi(x)\)の形で表される主張 (論理式) \(\phi(X)\)を、集合\(\mathcal{F}^\omega\Sigma\)について示したいとき、
- \(\phi(\Sigma_0)\)すなわち\(\phi(\Sigma)\)であること
- 任意の集合\(A\)に対して\(\phi(A)\Rightarrow\phi(\mathcal{F}A)\)であること
の2つを証明することで、数学的帰納法により\(\phi(\mathcal{F}^\omega\Sigma)\)であることが証明できます[注 1]。
脚注[]
- ↑ より一般の場合は、前述の2つに加えて和集合での遺伝性 \(\forall a\in A.\phi(a)\Longrightarrow\phi(\bigcup A)\) が要求されます。