« 乗鞍ヒルクライム2012、またも当選♪ | トップページ | フルマラソンから1ヶ月、ようやく25km走まで回復♪ »

原始再帰的(リカーシヴ)関数と加法、乗法

最初に書いておくと、この記事は、ペアノの自然数論や公理を多少理解し

てる人向けの内容になってる。それらを知らない方は、ペアノの公理足し

算(加法)の構成、掛け算(乗法)の構成を先に一通り見ておくことをお勧

めする。ちなみにペアノとは、数学基礎論の代表的先駆者の一人であっ

て、自然数とは何か、足すとはどうゆう操作か、といった根本的問題を、

深く巧みに考えた数学者である。

      

さて、ペアノの自然数論では、まず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)が不要であることの証明にチャレンジしてみたい。

      

以上、原始リカーシヴ関数の定義と、加法・乗法が原始リカーシヴである

ことの証明を中心に説明した。しばらく後に、一般リカーシヴ関数とか、計

算可能性、決定可能性の問題について記事を追加する予定。

それでは、今日の所はこの辺で。。☆彡

    

    

    

cf.1+1=2はなぜか?~ペアノの自然数論(足し算)

  「1×1=1」はなぜか?~ペアノの自然数論2(掛け算)

  集合論における自然数の表記と計算

  自然数に関するペアノの公理~論文『数の概念について』に即して

  0、1、「次の数」に関する哲学的考察~フレーゲ『算術の基礎』

  引き算の証明、負の数~ペアノの整数論(減算=減法)

    

      ・・・・・・・・・・・・・・・・・・・・

  「1+1=2」はなぜか~小学1年生の算数の教科書

  引き算、足し引き連続、0(ゼロ)~小学1年生の算数2

  掛け算の導入、足し算・引き算との関係~小学校の算数3

  同じ数ずつ分ける計算、割り算(除法)~小学校の算数4

              

                                 (計 4687文字)

| |

« 乗鞍ヒルクライム2012、またも当選♪ | トップページ | フルマラソンから1ヶ月、ようやく25km走まで回復♪ »

数学」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« 乗鞍ヒルクライム2012、またも当選♪ | トップページ | フルマラソンから1ヶ月、ようやく25km走まで回復♪ »