てくてく

【論理学】ゲーデルの不完全性定理が前提とする自然数論の公理系とは？【ロビンソン算術と原始帰納的算術】

哲学 アイキャッチ_【論理学】ゲーデルの不完全性定理が前提とする自然数論の公理系とは？【ロビンソン算術と原始帰納的算術】
この記事はすでに「ゲーデルの不完全性定理」の概要をご存じの方向けの内容となっております。そのため定理の大まかな意味や、誕生した歴史的背景などを知りたい場合は、まず以下の記事からご覧ください。
関連記事
【論理学】ゲーデルの不完全性定理を解説！ラッセルのパラドクスとの違いは？【簡単ではない】

[mathjax] エンジニアであれば誰もが一度は手に取るであろう(?)Noam Nissen著『コンピュータシステムの理論と実装』では、NANDゲートからコンピュータを作り上げます。 [blogcard url=htt[…]

アイキャッチ_【論理学】ゲーデルの不完全性定理を解説！ラッセルのパラドクスとの違いは？【簡単ではない】
目次

ゲーデルの不完全性定理の前提条件

ゲーデルの不完全性定理は「神の存在を否定した。」だとか「人間の理性には限界がある。」といった風に誤解されることが多いと聞きます。これらの言説はゲーデルの不完全性定理のある前提を見落としているのですが、この記事ではその前提条件に迫ります。

私が初めて論理学に触れたテキスト、野矢茂樹著『論理学』ではゲーデルの不完全性定理について以下のように記載しています。

論理学

現代論理学という知の風景へ誘う、文科のための入門書。初心者の素朴な疑問と驚きに満ちた、不思議の国への旅だち。豊富な問題・…

自然数論の公理系\(N\)が\(\omega\)無矛盾であるならば、\(A\)も\(\lnot A\)も公理系\(N\)においては証明できないような\(N\)の閉じた式\(A\)が存在する。
自然数論の公理系\(N\)の無矛盾性は公理系\(N\)においては証明できない。
本書はあくまでも「ずぶの素人のための現代論理学への初めの一歩」であり、初学者がなるべく躓くことのないよう細かい記述はある程度省略されています。「自然数論の公理系」については「数学」と置き換えて差し支えないようですが…どのようなものか気になってしまいますね。
そこで本記事ではThe Stanford Encyclopedia of Philosophy (SEP) “Gödel’s Incompleteness Theorems” を参考に、「自然数論の公理系」とは具体的に何であるかを学んでいこうと思います。

ゲーデルの不完全性定理 (再掲)

SEPの記事にてRaatikainen Pはゲーデルの不完全性定理を以下の様に定義しています。

Any consistent formal system \(F\) within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of \(F\) which can neither be proved nor disproved in \(F\).
For any consistent system \(F\) within which a certain amount of elementary arithmetic can be carried out, the consistency of \(F\) cannot be proved in \(F\) itself.
第一、第二不完全性定理のいずれも意味としては『論理学』に記載の定義と変わりないのですが、Raatikainenの記述では「自然数論」に相当する部分が「a certain amount of elementary arithmetic」となっています。直訳すると「一定程度の初等演算」となります。
第一、第二不完全性定理共に「一定程度の初等演算がなされる無矛盾の形式体系」が前提となっておりますが、実はその「一定程度の初等演算」については異なるものが当てはまります。
第一不完全性定理ではロビンソン算術(Robinson arithmetic; Q)が、第二不完全性定理では原始帰納的算術(Primitive Recursive Arithmetic; PRA)が「一定程度の初等演算」となります。

ロビンソン算術( 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\)に対応します。

$$ \phi(0) \wedge \forall x[\phi(x) \rightarrow \phi(x’)] \rightarrow \forall x\phi(x) $$ \(\phi\)が\(0\)で成り立つ and 任意の\(x\)で\(\phi(x)\)が成り立つとき\(\phi(xの次)\)も成り立つ ならば 任意の\(x\)で\(\phi\)が成り立つ。

原始帰納的算術( 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)という、複雑さに関する階層があるそうです。まだまだ初学者のため分からないことだらけですが、引き続き学んでいこうと思います。

参考