原始再帰的(リカーシヴ)関数と加法、乗法
最初に書いておくと、この記事は、ペアノの自然数論や公理を多少理解し
てる人向けの内容になってる。それらを知らない方は、ペアノの公理、足し
算(加法)の構成、掛け算(乗法)の構成を先に一通り見ておくことをお勧
めする。ちなみにペアノとは、数学基礎論の代表的先駆者の一人であっ
て、自然数とは何か、足すとはどうゆう操作か、といった根本的問題を、
深く巧みに考えた数学者である。
さて、ペアノの自然数論では、まず0(ゼロ)が自然数とされ、「自然数 n
の次の数 n´ も自然数」とされる。この時、0、0´、0´´、0´´´・・・と次々
に自然数が決まって行くことになる。これがいわゆる自然数、0、1、2、
3・・・と同一視される。
また足し算の定義では、まず「n+0=n」とされ、次に「n+m´=(n+m)´」
とされる。この時、n+0´=(n+0)´=n´と計算できるし、順に計算して行
けば、n+0´´、n+0´´´・・も計算できることになる。これがいわゆる n+1、
n+2、n+3・・・と同一視される。さらに、掛け算は、0との掛け算(=0)と
足し算から定義される。
結局どれも、一つ前のものから次のものが順に構成されていく手続きに
なっている。簡単に言うと、こうゆう手続きを通じて作られる自然数関数全
体が、「原始リカーシヴ関数」(primitive recursive function)と呼ばれ
るものである。これに関しては、足し算や掛け算同様に、正しい命題を有
限回の手続きで論理的に証明することが出来そうだ。
証明とか「計算可能性」といった話は高次元のものだから、しばらく後に
別記事で扱うことにして、今回はとりあえず、原始リカーシヴ関数の定義
と、その使い方を見ることにしよう。手元の2冊の参考書、『現代数学小
辞典』(講談社)、『新版 現代論理学』のどちらにも、具体的な説明が無
いので、私は自分で考えて補った。つまり、足し算や掛け算はなぜ原始
リカーシヴなのか、それを定義にしたがって証明したわけで、以下それ
を書き記しておく。
なお、「リカーシヴ」(recursive)という英語は、ラテン語の語源まで遡る
と、「前へと走る」、つまり「戻る」という意味だ。「帰納的」とも訳されるが、
有名な数学的「帰納法」の英語は「induction」なので、念のため。ネット
検索だと「再帰(的)」と訳してる方が主流みたいだから、記事タイトルに
も「再帰的」と入れておいた。。
☆ ☆ ☆
ではまず、前掲『現代論理学』から、原始リカーシヴ関数の定義を引用
しておこう。ただし、原文では関数を表す記号がギリシア文字φ(ファイ)、
ψ(プサイ)、χ(カイ)になってるが、ここではより一般的で分かりやすい、
F、G、Hを使うことにする。あと、例えば「1)」の代わりに「(1)」と書く。カッ
コは左右両方で閉じる方が見やすくて自然だからだ。
更に、途中で引用者による簡単な説明も少し入れ、原文の「表わす」は「表
す」に直した。入力文字の制限で小さい添字が打てない場合は、適当に小
文字を使って補ってある。「・・・・・・」は短くして、「・・・」と直した箇所もある。
大前提として、扱う関数は「数論的関数」のみ。つまり、自然数の組合せ
(1個~n個)に対して、ある1つの自然数を値として対応づける関数の
みである。簡単な例は、2つの自然数の組合せに対して1つの値を与え
る、足し算や掛け算である。
『定義』 以下の(1)~(6)の操作を有限回繰り返すことによって構成
される関数を原始リカーシヴ関数という。ただし、F、G、Hは
数論的関数、n、mは正の整数、1≦ i ≦n、qは自然数(0を
含む)である定数を表す。また引続き、x´は x+1 を示す。
(1) F(x) = x´
(2) F(x₁,x₂,・・・,xn) = q
(3) F(x₁,x₂,・・・,xn) = x i
☆引用者による説明
(1)は要するに、次の数への対応付け、F(x)=x+1。これ
そのものは、(1)の操作を「1回繰り返す」ことによって構成
されると言いたいわけだ。この参考書には、やや不自然な日
本語が時々あるが、そのまま引用しておいた。(2)は、何で
も定数qに対応付ける定数関数。(3)は、与えられた自然数
の組から i 番目の数を取り出す関数だから、n=1の時には
F(x₁) = x₁。つまり、恒等関数も原始リカーシヴである。
では引き続き、(4)~(6)を引用しよう。この3種の操作によっ
て、次々に原始リカーシブ関数が増えて行くことになる。
(4) 原始リカーシヴ関数G(y₁,y₂,・・・,ym)、H₁(x₁,x₂,・・・,xn)、
・・・・・・、Hm(x₁,x₂,・・・,xn)から
F(x)=G( H₁(x₁,x₂,・・・,xn),・・・,Hm(x₁,x₂,・・・,xn) )
を作る。
☆引用者による説明
添字の「m」と「n」に注意。m変数関数Gに、n変数関数H₁~
Hmの値を代入することで、n変数の合成関数Fを作っている。
(5) 定数qと原始リカーシヴ関数G(x,y)から
F(0) = q
F(x´) = G( x,F(x) )
を作る。
☆引用者による説明
言葉が省略されてるが、F(0)とF(x´)がそう定義されるよう
なF(x)を作る、という意味で、次の(6)も同様。(5)では、1個
定数 q と2変数関数Gを用いて、1変数関数Fを作っている。
(6) 原始リカーシヴ関数G(x₂,・・・,xn)、H(y,x₁,x₂,・・・,xn)から
F(0,x₂,・・・,xn) = G(x₂,・・・,xn)
F(y´,x₂,・・・,xn) = H(y,F(y,x₂,・・・,xn),x₂,・・・,xn)
を作る。
☆引用者による説明
添え字や変数の個数に注意。n-1変数関数Gと、n+1変数
関数Hから、n変数関数Fを作っている。ただし、n≧2。
これで定義は終了。
☆ ☆ ☆
以上の定義で、(1)~(3)は簡単だが、(4)~(6)はなかなかピンと来な
い構成法だろう。『そこで以下、具体的にいくつかの原始リカーシヴ関数を
作ることで、正確な理解を目指したい。その作業はやがて、足し算(加法)
の関数x+yが原始リカーシヴ関数であることの証明にもつながる。
まず、F(x₁,x₂,x₃) = x₂´ 、つまり3つ組の変数に対して、中央の
変数の次を与える関数は、原始リカーシヴ関数である。証明は、定義(4)
で簡単に可能だ(式の右端は、次の数を表すダッシュ)。
原始リカーシヴ関数G(y) = y´、H(x₁,x₂,x₃) = x₂から、
定義(4)にしたがって新たな原始リカーシヴ関数Fを、
F(x₁,x₂,x₃) = G( H(x₁,x₂,x₃) ) と作る。
すると、 F(x₁,x₂,x₃) = G(x₂)=x₂´ となり、ここで作った
Fが証明すべき関数であることが分かる。
よって、「F(x₁,x₂,x₃) = x₂´ 」は原始リカーシヴ関数である。
(証明終了)
次に、ペアノの足し算の定義を意識しつつ、
A(0,x₂) = x₂
A(y´,x₂)= ( A(y,x₂) )´
によって定まる2変数関数A(x₁,x₂)が原始リカーシヴ関数であることを
証明する。先ほど原始リカーシヴだと証明した関数Fを、新たにHと名付け
直して、定義(6)を利用する。
原始リカーシヴ関数G(y) = y (恒等関数)、H(y,x₁,x₂) = x₁´
から、定義(6)にしたがって新たな原始リカーシヴ関数Aを、
A(0,x₂) =G(x₂)
A(y´,x₂)=H(y,A(y,x₂),x₂) と作る。
すると、A(0,x₂)=G(x₂)=x₂
A(y´,x) = H(y,A(y,x₂),x₂)=( A(y,x₂) )´。
となり、ここで作ったAが証明すべき関数であることが分かる。
よって、 A(0,x₂) = x₂
A(y´,x₂)= ( A(y,x₂) )´
によって定まる関数A(x₁,x₂)は原始リカーシヴ関数である。
(証明終了)
このAを用いて、ペアノの足し算が原始リカーシヴであることを証明する。
原始リカーシヴ関数A(x₁,x₂)、B₁(x₁,x₂) = x₁、
B₂(x₁,x₂) = x₂ から、定義(4)にしたがって新たな原始リカー
シヴ関数Cを、
C(x₁,x₂) = A( B₂(x₁,x₂),B₁(x₁,x₂) ) と作る。
すると、C(x₁,0) = A(B₂(x₁,0),B₁(x₁,0))
= A(0,x₁)
= x₁
C(x₁,y´) = A( B₂(x₁,y´),B₁(x₁,y´) )
= A(y´,x₁)
= ( A(y,x₁) )´
= (A(B₂(x₁,y),B₁(x₁,y)))´
=( C(x₁,y) )´
よって、ペアノの足し算の定義を用いると、
C(x₁,x₂)=x₁+x₂
したがって、足し算は原始リカーシヴ関数である。
(証明終了)
☆ ☆ ☆
最後に、ペアノの掛け算が原始リカーシヴ関数であることの証明は、足し
算の場合と同様の流れだから、少し省略して書くことにしよう。掛け算の
定義に足し算が使われてるから、上で足し算を表した原始リカーシヴ関
数Cをそのまま用いる。
まず、原始リカーシヴ関数C、H₁(x₁,x₂,x₃)=x₂、
H₂(x₁,x₂,x₃)=x₃から、定義(4)にしたがって新たな原始リカー
シヴ関数Fを、
F(x₁,x₂,x₃)=C(H₁(x₁,x₂,x₃),H₂(x₁,x₂,x₃))
=C(x₂,x₃)
=x₂+x₃
と作る。
次に、FとG(x)=0(定数関数)から、定義(6)にしたがって新たな原始リ
カーシヴ関数Dを、
D(0,x₂)=g(x₂)=0
D(y´,x₂)=F(y,D(y,x₂),x₂)
=D(y,x₂)+x₂
と作る。
さらに、D、B₁(x₁,x₂) = x₁、B₂(x₁,x₂) = x₂から、
定義(4)にしたがって新たな原始リカーシヴ関数Eを、
E(x₁,x₂)=D(B₂(x₁,x₂),B₁(x₁,x₂))
=D(x₂,x₁)
と作る。この時、
E(x₁,0)=D(0,x₁)=0
E(x₁,y´)=D(y´,x₁)
=D(y,x₁)+x₁
=E(x₁,y)+x₁
よって、ペアノの掛け算の定義を用いると、
E(x₁,x₂) = x₁× x₂
したがって、掛け算は原始リカーシヴ関数である。
(証明終了)
☆ ☆ ☆
なお、ここまでの説明で定義(5)だけは一度も用いてない。(5)は、変数
が0の時と x´ の時を分けて、1変数関数を定義するためのものである。
それに対して定義(6)は、変数が0の時とx´の時を分けて、n変数関数
(n≧2)を定義するためのものである。『小辞典』やネット情報を見ると、ど
うも(5)は必要ないみたいだから、他の定義でカバーできるのだろう。後
で、(5)が不要であることの証明にチャレンジしてみたい。
以上、原始リカーシヴ関数の定義と、加法・乗法が原始リカーシヴである
ことの証明を中心に説明した。しばらく後に、一般リカーシヴ関数とか、計
算可能性、決定可能性の問題について記事を追加する予定。
それでは、今日の所はこの辺で。。☆彡
自然数に関するペアノの公理~論文『数の概念について』に即して
0、1、「次の数」に関する哲学的考察~フレーゲ『算術の基礎』
・・・・・・・・・・・・・・・・・・・・
(計 4687文字)
| 固定リンク | 0
「数学」カテゴリの記事
- パズル「ナンスケ」の解き方、考え方14~難易度3、ニコリ作、朝日新聞be、2025年2月8日(2025.02.09)
- かけ算の九九の表で、長方形で囲まれた数を足して315になる場合~灘中学校2025年入試、算数1・問題6の解き方(2025.02.07)
- 動画配信のおすすめ作品など、商業サイトでお薦めを決める方法と計算回数~2025年共通テスト・旧情報関係基礎・第2問(2025.02.04)
- パズル「絵むすび」33、解き方とコツ、考え方(難易度4、ニコリ作、朝日新聞be、2025年1月25日)(2025.01.26)
- くじ引き3回の参加料と景品代の期待値、金額設定の妥当性 ~ 2025年共通テスト・数学 Ⅰ A・第4問(2025.01.22)
コメント