形式システムの文字列を自然数によって表現すること 3

「形式システムの文字列を自然数によって表現すること 2」においてMIUシステムと呼ばれる形式システムの文字列に数字を対応させて、システムの文字列の記述を算術的な計算に翻訳することを考えた。文字列の書き換えという思考の展開を数字の書き換えに置き換え、さらにその数字の書き換えが計算として記述できるということを見てきた。

これは形式システムの構造を自然数論の算術の中に写像したものになる。自然数論は非常に強力な記述能力を持っているので、システムの構造を写像することによって、そのシステム自体に言及するようなメタ数学的な命題も、自然数論の算術的命題として記述できる。つまり、算術的命題は、それがある計算を表しているという点で算術的な面を持つと同時に、その計算を解釈することによって、システム自体への言及の意味を読み取ることが出来る。

かけ算や足し算をしたりするのは算術的な計算だが、その計算がある規則に従ったものであることが分かると、それは規則に従った導出をしていると解釈され、その計算の結果得られた数字に対応する形式システムの文字列は、その形式システムでの定理であると判断される。その文字列が定理であるという判断は、形式システムの文字列の生成を語るものではなく、形式システムの全体を捉えた性質に対する言及になる。つまり、この計算はメタ的な意味を持つものとして解釈される。




前回のエントリーでは、MIUシステムを使って、形式システムの自然数論への埋め込みの雰囲気を味わったが、今回はその埋め込みによる計算がどのようなメタ的な言説の意味を持つかという、算術的な式をメタ的な命題として解釈するという意味の側面を考えてみたいと思う。さて、文字列をqという記号で表して、次のような対応を考える。


 q:MIを表す → 31と数値化される


この31をゲーデル数だというふうに考えて、g(q)で文字列qのゲーデル数を表す。そうすると、上の対応は次のような等式、すなわち算術的な式で書かれる。


   g(q)=31


この式は、qという文字列のゲーデル数が31であるという数値関係を表す算術的な式である。そしてそれと同時にqという文字列が公理であるというメタ的な言説の意味を持っている。

それでは次に、MIUシステムの書き換え規則によって生成される文字列に対応する数列について考えてみよう。前回例に出した次の文字列を考えてみよう。


1 MI …… 公理
2 MII …… 規則2においてxとしてIを用いた。
3 MIIII …… 規則2においてxとしてIIを用いた。
4 MUI …… 規則3によって最初のIIIをUで置き換えた。
5 MUIU …… 最後の文字がIだったので規則1を適用してUを付け加えた。
6 MUIUUIU …… 規則2においてxとしてUIUを用いた。
7 MUIIU …… 規則4を適用してUUを取り除いた。


これを数値化して計算に書き直すと、


1 31=10×3+1
2 311=10×31+1=3×10^2+11
3 31111=10^2×311+11=3×10^4+111×10+1
4 301=3×10^2+1
5 3010=10×301=3×10^3+10
6 3010010=10^3×3010+10=301×10^4+10
7 30110=301×10^2+10


上の等式における二つの計算は、最初のものがそれ以前の数から生成規則に従って計算したことを示す計算式であり、あとのものは、次の数を生成するための根拠となる、生成規則で言えば仮言命題の前件に当たる数であることを示す等式になっている。つまり、上のような計算式が成り立つから、この数列は、形式システムにおいて正しい生成規則に従っているのだということが判る。正しい生成規則に従うというメタ的な言説が、この等式の意味として読み取れる。

この数列をメタ的な視点で眺めれば、それぞれがMIUシステムでの定理であるという解釈がされる。7番目の30110という数字は文字列に戻してやればMIUシステムの定理であると解釈される。この数値化によってMIUシステムの証明の構造も自然数論の中に埋め込まれたように感じる。しかし、上の数列はそのままでは自然数論の命題にはならない。一つ一つは自然数論の数式だが、それが並んでいるだけでは、全体としては数式とは呼べない。

自然数論の命題では、ある数が計算できて、その数が何かに等しいとか、そのような命題は直接表現できるものの、数列の前後の関係がある導出規則に従っているということを記述するような言語はない。それはメタ的な表現をする日本語の中にあるもので、上の数列のままでは、メタ的な表現は日本語に頼らなければならない。メタ的な表現までも自然数論の中に埋め込むにはどうしたらいいだろうか。

ゲーデル数を個々の記号に当てはめただけではメタ的な言説の意味をそこに読み取ることが出来ない。記号列の系列である数式の列にもゲーデル数が対応するような工夫をしなければならない。数列を、複数の数字として記述するのではなく、数列も一つの数字に対応するという写像が必要になる。それが素数のべきによって表現するというものになるのだろう。2から始めて素数を小さい方から順に7つ並べると

    2,3,5,7,11,13,17

になる。^という記号でべきを表して、上のMIUシステムの文字列に与えたゲーデル数を、この素数のべきとして用いて次の計算を考える。

  2^31×3^311×5^31111×7^301×11^3010×13^3010010×17^30110

この数は、実際に計算することはたいへんだが、理論的には計算可能だし上の形のように素因数分解することも出来る。そして、素因数分解は一意性があるので、この数は上の数列に対応した唯一の数であるということも判る。つまり、この数を使えば、数列ではなく一つの数で上の証明式のMIUシステムの文字列に対応した数列を表現することが出来る。ある数の解釈として、それが証明図式になっているかどうかが決定できそうだ。

ある文字列の系列としてQが与えられたとき、つまりQというのは次のように文字列として

  q1
  q2
  q3
  ……
  qn

というMIUシステムの文字列が並んだものと考える。このQのゲーデル数をg(Q)とすると、この文字列の系列がMIUシステムでの正しい証明になっているというのは、g(Q)が算術の計算として上のような規則に従っているかどうかで決定される。それはまず

1 g(Q)を素因数分解する。
2 素因数分解の結果が、小さい素数から順に並んだ形になっている。
3 素数のべきがすべて3,1、0の数字からなっている。
4 小さい素数のべきから一つ大きい素数のべきにいたる計算が、計算規則を満たしている。

ということが確認されると、最後のqnという文字列が定理であるという判断が決定できる。これらは、すべて有限の手順で決定できるものだと思われる。なぜなら最初のゲーデル数が有限の大きさを持った具体的な数だからだ。

実際に与えられた数値が有限であっても、現実的には計算できないことがあるかもしれないが、理論的には可能だ。素因数分解は、その数よりも小さい数で順番に割っていって決定するが、それは有限の手順で終了する。

素数のべきに当たる数字が、MIUシステムの導出規則に従っているかどうかという問題は、その数が有限の大きさのものであれば、10のべきの大きさによって、つまり対象の数を10倍、100倍、1000倍などの場合に分けて導出規則を試してみることで、それに正しく従っているかが決定できるだろう。有限の大きさの数であれば場合分けは有限の個数になり、これも決定可能だと思われる。

ある文字列の系列Qが与えられたとき、そのゲーデル数g(Q)を考えることで、Qが証明の列であるかどうかが決定できる。そうすると、その証明の列の最後の文字列qnが定理であるかどうかも決定できる。そうするとあるゲーデル数の最後のべきの指数に当たる文字列が導出規則に従った定理になっているかどうかということは、決定可能なものになる。式の系列の最後に当たるMIUシステムの文字列をqとしておくと、g(Q)からg(q)を求めて、それが導出規則に従っていれば1を返し、そうでないときは0を返すような関数を考えることが出来る。


  Dem(g(Q),g(q))=1…式の系列Qがqの証明になっている
  Dem(g(Q),g(q))=0…式の系列Qがqの証明になっていない


この関数そのものはどのように記述されるかは具体的に示すことが出来ないが、決定可能であるということから算術の関数として定義できると思われる。素因数分解は理論的には一意に決定できるように行える。その最後のべきを指定することも算術式として存在記号を使うことで何とかなるだろう。導出規則に従っているかどうかも、存在記号の助けを借りて記述可能になるものと思われる。上の関数は、形式システムの中で記述できるものだと思われる。上の関数が1に等しければ、ここからqが定理であることの意味を読み取ることが出来、qが証明可能であるというメタ的な言説を得ることが出来る。

この証明可能性を

   Pr(q)

などというような式だと考えれば、証明可能性ということが自然数論の中に埋め込まれたと考えることが出来るだろう。ただ、この記号表現には一つ難しい問題がある。Qという式系列が具体的に与えられていれば、それは有限の範囲で決定可能になるのだが、Qが具体的に与えられていないときに、Qを探すことを含めてqの証明可能性を考えると、それが無限のループになって決定できないかもしれないという心配が出てくる。具体的なQがあればいいのだが、それが見つからないときは、いくら探しても見つからないのだというのを有限の範囲で決定できるかどうか。この証明可能性があらゆる式qに対して決定可能であれば、その形式システムは完全だと言えるのではないだろうか。そしてまた、決定できないqが存在すればその形式システムは不完全だと言われるだろう。次は、このことを考察してみようと思う。
[PR]
by ksyuumei | 2008-10-31 09:17 | 論理


<< 主張の正当性がなぜ報道されないのか? 図と地という視点 >>