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

『ゲーデル、エッシャー、バッハ』という本には、MIUシステムと呼ばれる形式システムが紹介されている。これは3個の記号「M,I,U」と、文字列を並べる4つの規則が提示されているものだ。出発点となる公理は一つだけで、その文字列から書き換え規則によって得られる文字列がどのようになるかを考える。まとめておくと次のようになる。


記号  M,I,U
公理  MI
規則
 Ⅰ xIが定理ならば、xIUは定理である。
 Ⅱ Mxが定理ならば、Mxxは定理である。
 Ⅲ 任意の定理において、IIIはUで置き換えることが出来る。
 Ⅳ 任意の定理において、UUは除くことが出来る。


ここで「定理」と呼ばれているのは、上の規則によって書き換えが可能な文字列のことを呼んでいる。「公理」とは、前提なしに・無条件に「定理」とされる文字列で、これを出発点に規則によって書き換えが出来るものがこのシステムの「定理」となる。この本では、パズルとして「MU」が定理となるかどうかを考察せよという問題が提出されている。この問題に解答するには、もし「MU」が定理ならば、実際にそれを導く書き換えの文字列を構成することによって解決する。しかし、これが「定理」でなかった場合は、「いくらやっても出来なかった」ということを示すだけでは、それが「定理」ではないということを示したことにはならない。合理的な理由によって、それが決して「定理」にならない、すなわち上の書き換え規則では導出できないのだということを示さなければならない。



「MU」が定理であれば、それは偶然にそのような文字列の構成を見つけられる可能性があるが、これが「定理」でない場合は、このシステムの全体の構造を把握して、そこから「MU」が定理でないことを導かなければならない。実際には「MU」は定理ではないので、そのような説明が出来る。この説明の考察に伴って、「MUシステム」の記述を、文字列から数字の表現に転換するということがこの本では説明されている。このアイデアが、ゲーデルが自然数の形式的表現の文字列に「ゲーデル数」を割り当てたアイデアとよく似ている。ここからゲーデルの発想の雰囲気が感じ取れないかと思う。

さて「MIUシステム」によって導出される定理の様子をちょっと見てみよう。書き換え規則の適用によって得られる文字列を並べてみると次のようになるだろう。


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


この文字列において、規則が正しく適用されている2から7までの文字列はすべて「定理」になる。4によって「MUI」を作ることが出来たので、このIを取り除くことが出来れば「MU」は「定理」となる。しかし、「MIUシステム」ではこのIを取り除くことが出来ない。

「MU」が「定理」になるかどうかを考察するには、このシステムの構造がどうなっているかを把握しなければならない。個々の規則の適用が正しいかどうかということではなく、どのような特徴を持った「定理」が導出されるかという、構造に関する考察が必要になる。この本では、どのような性質が「遺伝的性質」を持っているかというような問題設定をして、システム全体の構造を把握しようとしている。

まずすぐに分かることは、この規則においてはMの書き換えについては何も語っていないということだ。規則Ⅰでは、先頭のxについては不変のままである。ⅡにおいてもMはそのままだ。ⅢとⅣはIとUに関する規則であってMは無関係だ。また公理はMIだけであって、Mはここにしか登場しない。つまり、Mはこのシステムにおいては文字列の先頭に登場し、文字列の先頭だけにしか登場しない。この性質はすべての「定理」に受け継がれる「遺伝的性質」だ。

Iについては、その追加規則はⅡにおけるxがxxに書き換えられるところで追加されるだけである。UはⅠとⅢにおいて一つずつ追加することが可能だが、Iについては、書き換え前の2倍の数になるような追加しかこのシステムでは許されていない。つまり書き換え後のIの数は必ず偶数になるということだ。しかもこの偶数にも制限がある。

出発点となる公理「MI」ではIは一つしかない。だから、この公理を書き換えれてIを追加すればそれは2になる。以下、どのようにがんばってみても、Iの数は

  1、2,4,8,16,32,……

のような2のべきの数にしかならない。Iが3個の文字列は公理ではないので、それ以前の文字列から導出しなければならないが、Iは常に2倍の個数になるという性質が「遺伝的性質」としてあることを考えると、Iが3個になるようなその前の文字列は、Iを1.5個持っていなければならないが、個数における小数点は意味を持たない。つまり、Iが3個になるような文字列はこのシステムでは構造的に追加をして生成することが出来ない。同様に、Iが5個、6個、7個、9個、……となるような、2のべきではない個数のIを持つ文字列は、このシステムからはIの追加だけによっては導出できない。Iが常に2倍の個数になるように文字列が書き換えられるという性質を逆にたどると、その先祖としてIが小数点の個数を持つような文字列を想定しなければならなくなるからだ。

さて、Iを追加する規則に関してはこのような性質があるので、Iを3個作ることが出来ない。しかし、Iにはそれを取り除く規則のⅢもある。これを利用すればIが3個になるような文字列を作ることが出来るだろうか。これは、Iの追加によって出来るIの個数は2のべき乗の個数になるので、これから3の倍数を引いた数がちょうど3の倍数になることがあるかどうかということを考察することから解答できる。これは、

  2×2×…(n個の2)…×2-3×m

という計算が3の倍数になることがあるかどうかという問題になる。もしこのようなことが成立して、あるhに対して

  2×2×…(n個の2)…×2-3×m=3×h

となったとするとおかしなことになる。上の式を少し書き換えると

  2×2×…(n個の2)…×2=3×m+3×h
                =3×(m+h)

となる。そうすると左辺は2のべき乗で2という素因数しかないのに、右辺では3という素因数が出てきてしまう。これは素因数分解の一意性に反するものになる。

以上の考察から得られる結論は、このシステムでは、連続して3つIが並ぶような文字列は生成が出来ないということだ。もし3つ続けてIが並ぶような文字列があれば、そのIをUで置き換えることが出来る(Ⅲの規則)。そうすれば、そのようなことを繰り返せば、いつかはIを含まない文字列を作ることが出来るだろう。そうすればⅣの規則によってUは取り除くことが出来るので、どこかで「MU」という文字列が定理として登場する可能性がある。

しかしIという文字は、このシステムの文字列から取り去ることが出来ない。公理に入っている最初のIは決して消えることなくどの定理にも少なくとも一つは含まれてしまう。そのような「遺伝的性質」をこのシステムは持っている。Iが決して消せない文字であるなら、Iを含まない「MU」という文字列は、このシステムでは決して「定理」となることはないであろう。

以上の考察は、すべて日本語によって進められた論理の展開だ。「MU」が「定理」になるかどうかという考察は、「MIUシステム」という形式システムの中では、それが「定理」になるのなら、いつかは生成されるということで解決される。しかし、それが「定理」にならないときは、いくらシステムで文字列を生成しても、システムの中ではその問題の解決が出来ない。システムの外から、システムそのものを考察するという視点が必要になる。「メタ的」な考察と呼ばれるこのような思考は、システムについて語る、システムの言語ではないもっと豊かな内容を持った言語が必要だ。

このシステムを考察するのに、普通の日本語は十分豊かな内容を持っていると言えるだろう。上のようにして「MU」が「定理」ではないことが示される。この考察の中では、途中で整数の性質の考察も含まれていた。これは、上のシステムそのものの考察を、整数の性質を考える自然数論で表現する可能性を示唆する。「MIUシステム」では、上の考察を表現することは出来ないが、M,I,Uの文字列に適当に数字を振り分けて、文字列の書き換えという規則の展開を、自然数の計算の解釈して表現することを考えてみる。これがゲーデルのアイデアの核心に近づくものになるのではないかと思う。

自然数論というのは、文字列の書き換え規則というシステムそのものを考察できるくらいに豊かな内容を持っていると言えるのではないかと思う。自然数論によって「MIUシステム」が考察できるなら、自然数論そのものも形式システムとして展開できれば、そのシステムそのものに対する考察も自然数論の中で行えるだろう。これがゲーデルのアイデアはないかと思われる。

しかし、単純な「MIUシステム」と違って、自然数論はその内容が豊かで強力なために、自己言及としてちょっと具合の悪いところが出てきてしまうというのがゲーデルの定理が示すものでもあるのではないだろうか。「MIUシステム」には、完全とか不完全とかいうことを考察の対象にするほどの豊かな内容はないのではないかと思う。そこから導かれる「定理」はごく単純なものばかりで、もしその解釈が求められたとしても、その解釈において正しいとされる文字列はすべて「定理」となるのではないかと思う。もし「定理」とならない正しい文字列を含む解釈があれば、それはその解釈が「MIUシステム」に比べて、複雑すぎる解釈になっているのだろう。それは、システムが単純であるから、おそらくすぐに見て取れるに違いない。

自然数論は、形式システムとして記述するには複雑で内容が豊かなために、完全か不完全かという問題がはっきりと出てきてしまうのではないかと思う。

次回は、「MIUシステム」に実際に数を割り当てて、文字列の解釈を自然数の計算で表すというゲーデルのアイデアを感じ取る考察をしてみたいと思う。その方法が、どのようにしてゲーデルの証明につながっているのか、単純なシステムでの類似性としてその理解を深めていけないかということを考えてみたい。
[PR]
by ksyuumei | 2008-10-20 10:24 | 論理


<< 関数・写像の考え方とゲーデルの定理 ブログ・エントリーのための覚え書き >>