[mathjax] エンジニアであれば誰もが一度は手に取るであろう(?)Noam Nissen著『コンピュータシステムの理論と実装』では、NANDゲートからコンピュータを作り上げます。 [blogcard url=htt[…]
ゲーデルの不完全性定理の前提条件
ゲーデルの不完全性定理は「神の存在を否定した。」だとか「人間の理性には限界がある。」といった風に誤解されることが多いと聞きます。これらの言説はゲーデルの不完全性定理のある前提を見落としているのですが、この記事ではその前提条件に迫ります。
私が初めて論理学に触れたテキスト、野矢茂樹著『論理学』ではゲーデルの不完全性定理について以下のように記載しています。
Amazonで茂樹, 野矢の論理学。アマゾンならポイント還元本が多数。茂樹, 野矢作品ほか、お急ぎ便対象商品は当日お届け…
ゲーデルの不完全性定理 (再掲)
SEPの記事にてRaatikainen Pはゲーデルの不完全性定理を以下の様に定義しています。
ロビンソン算術( Q )
ロビンソン算術について語るにはまず、ペアノ算術について触れておかねばなりません。
ペアノ算術(PA)は、1891年にジュゼッペ・ペアノ(Giuseppe Peano, 1858-1932)が『Arithmetices principia, nova methodo exposita』にてまとめた公理系です(ペアノの公理とも呼ばれています)。
元々1, 2, 3, … と自然に定義されていた自然数を、0と後者(successor)、そして数学的帰納法から厳密に定義しました。
ロビンソン算術(Q)は1950年にラファエル・ロビンソン (Raphael M. Robinson, 1911-1995)が発表した算術で、PAから数学的帰納法を取り除いたものとなります。具体的には以下の7つの公理からなる公理系です。
- \(\neg(0 = x’)\)
- \(x’ = y’ \rightarrow x = y\)
- \(\neg(x = 0) \rightarrow \exists y(x = y’)\)
- \(x + 0 = x\)
- \(x + y’ = (x + y)’\)
- \(x \times 0 = 0\)
- \(x \times y’ = (x \times y) + x\)
ここで\(‘\)はPAで言うところの後者(successor)を表しています。そのため例えば\(0′, (0′)’, ((0′)’)’\)はそれぞれ自然数の\(1, 2, 3\)に対応します。
原始帰納的算術( PRA )
原始帰納的算術(PRA)はトアルフ・スコーレム(Thoralf Skolem, 1887-1963)が1950年に発表した算術で、Qに原始帰納的関数が加わったものです。
原始帰納的関数とは\(x \in \mathbb{N} \)において、\(x=0\)における定数項(base case)と\(x>0\)において”巻き戻し的に”計算される項からなる関数です。エンジニアにとっては単純に再帰処理と言った方が理解しやすいでしょう。
例えば、\(x\)の階乗を計算する原始帰納的関数\(fact(x)\)を以下に示します。
$$ \begin{eqnarray} fact(0) &=& 1 \\ fact(x+1) &=& (x+1) \times fact(x) \end{eqnarray} $$
\(x=4\)を例として実際に計算してみると以下のようになります。
$$ \begin{eqnarray} fact(4) &=& 4 \times fact(3) \\ &=& 4 \times (3 \times fact(2)) \\ &=& 4 \times (3 \times (2 \times fact(1))) \\ &=& 4 \times (3 \times (2 \times (1 \times fact(0)))) \\ &=& 4 \times (3 \times (2 \times (1 \times (1)))) \\ &=& 24\end{eqnarray} $$
試しにC言語で書いてみると、次のようになりますね。
int fact(int x) {
if (x == 0) return 1;
return x * func(x-1);
}
形式体系のInterpretaion
さて、何やら見慣れないQやらPRAやら出てきましたが、これらがゲーデルの不完全性定理が言えるための前提条件として必要であることは一旦受け入れるとしましょう。QやPRAは不完全な公理系、即ちその公理系の中だけでは肯定も否定もできない命題が存在するそうです。
…数学自体の不完全性の話はどこに行ってしまったのでしょうか? 現代数学はZFC公理系の上に成り立っていましたが、QやPRA(ZFCよりも弱い公理系)の不完全性が示されることで何か影響を受けるのでしょうか?
ZFC公理系においてQとPRAは”表現”される
ZFC公理系は非常に強い公理系であり、QやPRAの内容を”表現”(interpret)することができます。訳語が適切かは分からないのですが、ある論理\(T_1\)の概念や変数が別の論理\(T_2\)でも定義でき、\(T_1\)の定理が全て\(T_2\)の定理として表せるのであれば、\(T_1\)は\(T_2\)で表現可能(interpretable)と言います。表現可能性(interpretability)を有するとき、\(T_1\)の性質の一部が\(T_2\)にも移されるのですが、その性質の1つに(不)完全性が含まれます。すなわち\(T_1\)が(不)完全であり\(T_2\)で表現可能なとき、\(T_2\)もまた(不)完全となります。
ここで\(T_1\)をQ/PRAとし、\(T_2\)をZFC公理系と置き換えるとどうなるでしょう? Q/PRAはZFC公理系で表現可能であり、Q/RPAはゲーデルの不完全性定理から不完全です。即ちZFC公理系も不完全となる、という訳です。
ZFC公理系が不完全であるということは、現代数学が不完全であるということと同義であると言ってよいでしょう。
終わりに
「自然数論の公理系」とは、QまたはPRAのことであると分かりましたが、具体的になぜそれらの算術が前提となっているのかについては、ゲーデルの不完全性定理の証明をたどる必要があります。
この記事では触れることができませんでしたが、いずれはゲーデルの不完全性定理の証明についても詳細に見てみたいですね。
また今回取り上げたQやPRAといった算術には算術的階層(Arithmetical hierarchy)という、複雑さに関する階層があるそうです。まだまだ初学者のため分からないことだらけですが、引き続き学んでいこうと思います。
参考
- 野矢茂樹, 論理学, 東京大学出版会, 1994, 261p, 4130120530
- Stanford Encyclopedia of Philosophy “Gödel’s Incompleteness Theorems”
- Stanford Encyclopedia of Philosophy “Recursive Functions”