2002年10月16日 作成 原始帰納的関数 >> 目次 (作成日順)
2007年12月 1日 補遺  


 
 今回は、ゲーデル の不完全性定理を読むための前提を扱う。

 
1. モデル

 Σ を T の文 (自由変数をふくまない) の集合とし、T が Σ のなかの任意の文 φ について、φ が 「恒真」 であるような 「解釈」 が成立するなら、「T は Σ の モデル である」 という。

 
2. 「解釈」

 形式的体系 T の 「解釈」 とは、T = ( U, R ) のことである。
 U は空でない集合とし、R は、U 上の関係 (2項関係) とする [ ただし、述語 P を関係 R とする ]。

 
3. 帰納的な定義

 自然数 x に対して、論理式 φ (x)を考える。

 (1) φ (0).
 (2) ∀x { x ∈ N | φ (x) } ⇒ φ (Sx). [ S は N の関数であり、「後続」 という意味である。]

 以上が成立すれば、φ (x) はすべての自然数 x について正しい。
 これを帰納的な定義という。

 
4. 原始帰納的関数

 以下の関数を原始帰納的関数という。

 (1) f (x) = x + 1.
 (2) f (x1, ..., xn) = q. (q は定数)
 (3) f (x1, ..., xn) = xi. (1 ≦ i ≦ n)
 (4) f (x1, ..., xn) = g (h1 (x1, ..., xn), ..., hm (x1, ..., xn)).
 (5) f (0) = q.
    f (y + 1) = h (y, f (y)).

 (1)、(2) と (3) は、(基本的な関数なので) 始関数と呼ばれている。
 (4) は「合成関数」、(5) は 「帰納的な定義」 を使って生成された関数である。
 始関数を使って、合成と帰納法 (帰納的な定義) を繰り返して生成した関数を 「原始帰納的関数」 という。
 原始帰納的関数は 「計算可能」 である。

 
5. 帰納的に可算 (計算可能性)

 自然数の集合 A が原始帰納的関数 g: N → N を使って、A = { g (0), g (1), g (2), ... } と記述されるなら、A は 「帰納的に可算である」 という。ただし、大きさの順に並んでいなくてもよいし、同じ値が繰り返されてもよい。

 言い換えれば、「帰納的に可算である」 ということは、A の メンバー を並べる計算手順がある、ということを意味している。ただし、「空集合も帰納的に可算である」 とする。 □

 



[ 補遺 ] (2007年12月 1日)

 本 エッセー の テーマ は、「原始帰納的関数」 です。ただ、本文中、「解釈」 という ことば に対して、あえて、「 」 を付与しているのは、「解釈 (あるいは、理解)」 という行為が、「哲学上」、争点になることを示すためです。

 哲学上、「解釈学 (Hermeneutik)」 という領域があるそうです (「岩波 哲学・思想 事典」、205ページ)。この領域では、ディルタイ (W. Dilthey) 氏・ハイデガー (M. Heidegger) 氏・ガダマー (HG. Gadamer) 氏が思想系譜になるそうです。

 ディルタイ 氏は、シュライアーマッハー (F.E.D. Schleiermacher) 氏の考えかたを継承して、「理解 (あるいは、解釈)」 を精神科学に固有な現象とみなして、理解の対象を (文献 [ 言語的記述 ] のみにかぎらず、) あらゆる種類の 「表現」 に拡大して、「解釈学」 を 「理解の理論」 として 「精神科学の方法論」 とみなしました。

 ハイデガー 氏の考えかたは、キルケゴール (S. Kierkegaard) 氏・フッサール (E. Husserl) 氏の考えかたを継承して、「事象 (ことがら) そのものへ」 という モチーフ を中核にして、「現象学的解釈学 (あるいは、解釈学的現象学)」 とよばれています。

 ガダマー 氏の考えかたは、ハイデガー 氏の考えかたにもとづいて、「理解」 を 「人間の一つの認識様式ではなくて、人間の基本的な存在様式 (人間の世界経験と生活実践の全体)」 とみなしていて、「哲学的解釈学」 とよばれています。

 「解釈」 に関する説は、様々、提示されてきましたが、いずれにしても、「解釈学」 の基本的 モチーフ は、以下の点にあるようです。

  (1) われわれの知識・規範は、歴史的に形成された共通の意味を前提にして成立している。
  (2) 歴史的な事実性・有限性が、解放性・創造性の源である。

 そういう視点から観れば、ウィトゲンシュタイン 氏の後期哲学 「言語 ゲーム」 説も 「解釈学的」 と云われるのでしょうね。数学が 「記号」 を扱う学問であっても、「解釈学」 の (1) を免れる訳ではないでしょうね。この点を ウィトゲンシュタイン 氏は、「哲学探究」 のなかで、争点にしていました。「解釈」 に関する哲学は、この辺で止めます--興味を抱いたひとは、ここに述べた哲学者たちの著作を読んで下さい。

 さて、「帰納的関数」 は、われわれ シロート には、なかなか、理解しにくい概念です。「帰納的関数」 として、いくつもの関数が定義されています (本 ホームページ の 168 ページ を参照して下さい)。私は システム・エンジニア なので、それらの関数のなかで、、チューリング 氏が示した 「Turing 機械」 を使った 「計算可能な関数」 概念を理解しやすかった。それぞれの 「帰納的関数」 を説明することは避けて--それぞれの 「帰納的関数」 を詳細に説明できるほどの数学的知識は、私にはないので、それらのなかから、--、ゲーデル 氏が示した 「原始帰納的関数」 と チューリング・マシーン を念頭に置いて、「帰納的関数の考えかた」 を以下に説明します。

 まず、「数論的関数 (number-theoretic function)」 という概念を覚えて下さい。「数論的関数」 とは、自然数 { 0, 1, 2, ... } の上で定義され、自然数の値をとる関数のことを云います。ゲーデル 氏は、この関数 (原始帰納的関数) を使って、「メタ 数学の算術化」 という技術を考え出しました。「メタ 数学」 というのは、ヒルベルト 氏が、「数学の 『無矛盾性』 を有限的手続きで証明するために」 考えた概念ですが、ゲーデル 氏は、「数論的関数」 を使って、「算術的体系が無矛盾であっても、完全ではない」 ことを証明しました。すなわち、「メタ 数学」 のなかでおこなわれる有限的手続きを 「数論的」 に--「数論的関数」 として--記述することができる、ということを ゲーデル 氏は示しました。この技術が、いわゆる 「不完全性定理」 の証明のなかで使われました。ゲーデル 氏の 「不完全性定理」 (のなかで使われた 「帰納的関数」) が起点になって、「『有限手続き』 とはなにか」 言い換えれば 「『実際に計算可能な』 ということは、どういうことか (『アルゴリズム』 とは、どういうことか)」 を、「数論的関数」 を使って数学的に定式化することが検討されました。そして、本 ホームページ の 168 ページ に示した様々な 「計算可能な関数」 が提示されました。それらの 「計算可能な関数」 は、いずれも、同値であることが証明されています。この 「計算可能な関数」 の延長線上で、コンピュータ (計算機) が実現されました。

 これらの 「帰納的関数」 が、どうして、重視されるのかと言えば、「数学的帰納法」 の基礎となるからです。すなわち、「数学的証明」 の役立つ手段になるからです。というのは、「自然数 n をふくむ或る命題 P (n) が、『すべての』 自然数 n について 『真』 である」 ことを主張するには、以下の 2つのことを証明すれば良いのです。この証明法を 「数学的帰納法」 と云います。

 (1) P (1) は、「真」 である。
 (2) P (k) が 「真」 であると仮定すれば--これが 「帰納法の仮定」 ですが--、P (k + 1) も 「真」 である。
   (ただし、k は、任意な自然数とします。)

 この 「数学的帰納法」 は、「ペアノ の公理系」 の第五番目にもとづいています。「ペアノ の公理系」 の第五番目は、以下の公理です。

    S が自然数全体の集合の 或る部分集合であるとして、(@) 1 ∈ S、(A) x ∈ S ならば、かならず、
    x ∈ S である--「+」 は後続を示して、x に対して、xが一つ、しかも、ただ一つ (one and only)
    対応することを意味しています。この 2つの条件を満たせば、S は自然数全体の集合である。

 さて、ゲーデル 氏は、「PM や、その関連体系での形式的に決定不能な命題について」 という論文--この論文が、いわゆる 「不完全性定理」 とよばれていますが--で、「PM の公理系」 と 「ペアノ の公理系」 を前提にして、「形式的体系を原始記号の有限列として扱い、それらの原始記号に対して自然数 (ゲーデル 数) を対応して、PM の体系のなかに、自然数として扱うことができるけれども、PM のなかで 『証明できない』 式を作ることができる」 ことを証明しました。この論文のなかで、かれは、40数個ほどの 「帰納的関数」 を定義しています。この論文が、「計算可能関数」 を導く契機となりました。ゲーデル 氏は、「計算可能関数」 のことを 「アルゴリズム が存在する関数」 のこととしています。「アルゴリズム が存在する」 こととは、単純に言えば、いわゆる 「決定問題」 のことです。
 したがって、この 「帰納的関数」 が、「証明」 や 「モデル」 に対して、大切な役割を演じていることが理解できるでしょう。「数学的帰納法」 の証明法を 1つ示してみましょう。たとえば、すべての自然数 n について、P (n) で-- P は、「そういう性質がある」 という述語だと思って下さい--、「1 + 3 + 5 + ... + (2n − 1) = n2 が成立することを証明してみましょう。

 (1) P (1) では、1 = 12 は、明らかに 「真」 です。
 (2) P (k) では、1 + 3 + 5 + ... + (2k − 1) = k2 が 「真」 であると仮定します。

 そして、「2k + 1」 を両辺に加えます。
 1 + 3 + 5 + ... + (2k − 1) + { 2 (k + 1) − 1 } = k2 + 2k + 1 = (k + 1)2.

 この証明は、P (k + 1) が成立することを示しています。
 したがって、P (n) は、すべての自然数 n についても、つねに、成立します。

 ちなみに、ウィトゲンシュタイン 氏は、ゲーデル 氏の 「不完全性定理」 (の証明法) に関して、以下のように述べています。

    いかに奇妙に思われようとも、ゲーデル の不完全性定理に関する私の課題は、ただ単に、
    「これは証明可能である、と仮定せよ」 といった命題は数学においては何を意味するのか、
    ということを明確にすることであるように見える。




  << もどる HOME すすむ >>
  ベーシックス