ゲーデルの不完全性定理 二題
昨日の不完全性定理についてのエントリ、短時間でお答えがいただけるとは思っていませんでした（(mt)^2さん、ありがとうございます）。今回は、いただいた答えの中で、気になった点を時間がないので二カ所だけコメントしたいと思います。
(3.1) 純構文論的性質と、意味論に関係する性質を混同している例
前回の問題の中で、
(3.1)「不完全性定理の意味の「完全性」が、論理の完全性の意味での「完全性」とどのように違うのかを説明せよ。また、両者の混同について、吉永良正以外の例を挙げよ。 (5点)」
というものがありました。私自身が考えていた例は、Rebecca Goldstein による "Incompleteness: The Proof and Paradox of Kurt Godel" です。彼女はその中で「ゲーデルの不完全性定理は、プラトニズムを後押しする」と主張していますが、この間違いはゲーデルの定理が構文論的な定理であることを理解していない点に原因があります。
説明が必要でしょう。不完全性定理における「完全性」の定義は以下のようなものです。すなわち、ある論理上の理論 T が完全であるとは、任意の論理式 P に対し、TがPを証明するか、TがPの否定を証明するか、どちらかであるということです。言い換えれば、Tの公理をルールに従って書き換えていけば、いつかはP、もしくは not P に到達する、というものです。この性質は純粋に Syntactical (構文論的)、つまり記号列の書き換えのみに関する性質だという点がポイントです。こちらの完全性には、「真理」などの意味論的性質はいっさい関与しません。鴨 浩靖氏にならって「証明論的完全性」という呼び名が適当かもしれません。
一方、完全性定理は、理論ではなく論理体系についてのものであり、記号列である論理体系の公理系(構文論)*1と、意味論的の範疇に入るモデル、両者の関係についての問題です。つまり、論理Lが完全であるとは、Lから証明可能であることと、Lの任意のモデルで「真」であることの両者が同値である場合を言います。この場合、L上の任意の理論は同じ性質を持ちます。このように、こちらは Semantical (意味論的)な概念である「真理」と関係します。というか、構文論と意味論の対応関係を定めています。
さて、ラッセル・パラドックスや嘘つきパラドックスは、ともに真理値の問題です。小林氏はゲーデルの不完全性定理もその一種だと思っているようで、つまり証明可能性という構文論の問題と、真理値という意味論の問題を区別していないということになります。また、吉永良正氏はその著書で、完全性定理は証明論的完全性だと言ってしまい、両者の区別に失敗しました。
さて、Goldsteinの本に話を移しましょう。実は私は彼女の本を読んでいません。ゲーデル全集の編纂者であり偉大な論理学者であるSolomon Feferman による書評を読んだだけなのです、が・・・すごい書評です。えーと、Fefermanによると、Goldsteinは
- ゲーデルの定理は「真だけど証明できない式が存在することを証明した」
- だから、全ての数学的真理は、公理や論理的手段でくみ尽くせないことを証明したことになる
- 不完全性定理はゲーデルがプラトニストとしてウイーン学団に対して行った攻撃であり、ウィーン学団の論理実証主義が抱いていた「規約による真理（公理から論理によって導出される命題こそ真）」という考え方に対する痛撃である。
- かくして、ゲーデルの不完全性定理より、プラトニズムは擁護される。
と主張しているそうなんですが、ここでFefermanが激怒して "Wrong, wrong, wrong!" と叫んでいます (p.4)。
上で述べたように、ゲーデルの定理は、純粋に構文論的なものです。つまり、実際に証明したことは、帰納的に公理化可能な自然数論 T に対し、ある論理式 G が存在し、Tは G も Gの否定も証明できない、というものです。つまり、記号列の変形についての性質であり、どこにも「数学的真理」とかが出てくる余地はありません。ところが、プラトニズムは（誤解を招く定式化ですが）「人間がこの世に存在しなくても、数学的命題は真か偽かのどちらかである」などといった、数学的真理に関する主張をします。片方は構文論的命題、もう片方は意味論に関係する命題、全く違う話です。この意味で、Goldsteinの間違いは、吉永氏のような直接的な混同とは少し違いますが*2、どちらも、純構文論的性質と、意味論に関係する性質を混同していると言えると思います。
では、不完全性定理が「真理」という意味論的性質について何かを語っているかのように見えるのはなぜか？つまりゲーデルの定理は「真だけど証明できない式が存在することを証明した」よと言われるのはなぜか？この疑問に対する Feferman の答えはふるっています(p.8)。すなわち、我々はゲーデルの証明以前に、素朴な真理概念を抱いており、任意の論理式 P は真か偽かどちらかの真理値を持つと信じています。この信念に従えば、真偽が証明できないゲーデル文 G だって真理値を持つはずです。とりあえず G が真だったと仮定しましょう。そうしたら、Gは真であって、なおかつ証明不可能だ、というだけです。すなわち、真理について我々は無根拠に素朴な信念を抱いているから、それを投影して、ゲーデル文だって真理値を持つように見えてしまう、という理由なのです。
それはそうと、Fefermanの書評は面白いです。Goldstein本の存在意義は、もしかしたらfefermanを激怒させて論説を書かせることだったのかもしれません。彼は、プラトニズムよりもっとデリケートな話題である、ゲーデルの不完全性定理とヒルベルト・プログラムの関係についても説明していますので、ぜひご一読ください。
(3.3) 不完全性定理はどのような数学的体系についてのものか、前提条件を答えよ。 (5点)
(mt)^2さんは、ここで
A3-3. 普通は自然数論を含む体系といわれているが、実際は体系自身の証明に関する記述を、体系内で記述可能な体系であれば、同様の定理が証明できる。
と答えられています。言いたいことはわかります（ZFCなどの、自然数論以外で表現力のある理論を含める、という主張でしょう）が、この書き方だと多くの反例を含んでしまうと思います。
ここでのポイントは、不完全性定理は「帰納的公理化可能な自然数論を含む体系」で証明される、という点です。たしかに、中学校でユークリッド幾何を習って以来、公理体系とは、有限個の公理で構成されるか、せめてPAやZFのように、公理の数は無限個だけど、公理図式を持ち、つまり公理を生成するコンピューター・プログラムがあるような体系であるはずだ、というイメージがあります。その点で、「帰納的公理化可能」という条件は当たり前なものとして忘れられることが多いように思います。
ですが、この条件を外すと、とんでもない公理体系の例を構成することができます。
（例）True Arithmetic Th(N)
Nを算術 PA の標準モデルとする。このとき理論 Th(N) を以下のように定義する。
Th(N)= {P: 論理式 P は標準モデル N で真}
このとき、以下が成立します。
証明は簡単、どちらも標準モデル N で真なので、定義より両方とも理論 Th(N) の公理となり、従って証明可能です。またTh(N)はPAを部分理論として含み、証明に関する記述を、体系内で記述可能な体系であることも明白です。という訳で、Th(N)が(mt)^2さんの答えの反例となります。ちなみに、Th(N)をZFCで構成するやり方を kururu_goedelさんが紹介していたと思います。
ちなみに
小林慶一郎氏が経済産業研究所の web siteに、「経済学における『ゲーデルの不完全性定理』」に関するページをアップしたようです。こちら。
ゲーデルの不完全性定理が示していることは、「ある真の命題Gが、自分自身に言及している命題である場合、その命題Gは真であるのに、それが真であることを証明することはできない」ということです（ゲーデルの定理の内容や証明のロジックに興味ある人は、Raymond M. Smullyan「ゲーデルの不完全性定理」（丸善株式会社）などを参照のこと）。
だそうです。はじめはファッションで「ゲーデル」の名前を使っているのかと思ったのですが、ガチなんですね。
後記（12月23日）
いろいろと論議を呼んだこのエントリーですが、冷静に判断できる時間が経ったので、総括をしたいと思います。自己弁護したいのはやまやまですが、客観的に考えれば、最初のエントリーを書いた時点では、やっぱり不完全性定理の意味論的証明の重要性を捉え損ねていた、と思います。もちろん、不完全性定理は構文論的手段のみでも証明でき、その意味で不完全性は真理概念と独立に定式化できる（というか特定のモデルから独立した、モデルのクラスの性質である）という点の重要性については強調しすぎてもしすぎることはない、という点に関しては意見は変わりません。Teoさんをはじめとする皆様のご指摘に感謝します。
*1:昨日までここを「公理系」と書いていましたが、「公理系」だけだと明らかに誤解を招きますね。こちらの完全性は論理についての話であり、ここでの「公理系」は論理の公理（つまりA→(B→A)とか）を意図しています。証明論的完全性は、PAやZFCのような古典論理上の理論を対象としており、まったく別のカテゴリーの問題です。
*2:・・・って、ここまで書いて思ったのですが、Goldsteinの場合は「二種類の完全性の混同」ではなく「二種類の概念の混同」で、同根ではあっても別の問題と見なされうるのですね。その意味で、私のこの回答は、5点満点で1点ぐらいしかもらえないかもしれません・・・問題文が悪かったか。この記事をご覧の皆様、もっと吉永良正的な混同の例をご存知でしたらお教えください。
