"Weak theories and essential incompleteness" (Vitezslav Svejdar)

logic 論文 読了

The Logica Yearbook 2007, pp.213-224. 著者のwebsiteはこちら。

ゲーデルの不完全性定理は魔力を持つようで、先日の一件のように、誰もが（深く考えもせずに）何か気の利いたことを言いたがります。ご多分に漏れず、当Blogでも、不完全性定理について、エラそうにいろいろ書いてきました。しかし、今回のような論文を読むたびに、知らないことばかりだ、ということを痛感します。
たとえば、普通の教科書では、第一不完全性定理はPA で証明されます。多くの方は、PAから数学的帰納法を除去した体系であるロビンソン算術Qでも不完全性定理が導出可能であることはご存知かと思います。QもPAも、その任意の拡張された理論が、もしも再帰的拡張であれば、その理論は不完全であるという性質を持ちます（これを「本質的に不完全」と呼びます）。それでは、本質的に不完全な、最も弱い理論って何なのでしょうか？
この論文では、Qより真に弱い、本質的に不完全な3つの算術体系を紹介しています。

ひとつは、Grzegorczyk（どう発音するんだ？）のQ^-で、これは、Qの足し算・掛け算を三項述語に置き換えた体系です。つまり、新しい述語A(x,y,z)とM(x,y,z)をもち、

  • A(x,y,z) ⇔ x+y=z
  • M(x,y,z) ⇔ x×y=z

をあらわします。だから、たとえばQの公理は

  • \forall x\forall y(S(x)=S(y)\to x=y)

という形ですが、Q^-では

  • \forall x\forall y \forall z_1\forall z_2(A(x,y,z_1)\& A(x,y,z_2)\to z_1=z_2)

という形です。
この体系では、足し算・掛け算が全域関数になる必要がない点が特色です。
さて、著者が別論文で示したように、Q^-の中にQの翻訳を作ることが可能です。したがってQ^-も本質的に不完全ということになります。またこの体系は\Sigma-完全性が成立しないこともわかっています。
さて、このQ^-の公理を一部強めた体系 FQ^- はハジェクが別に考察し、ファジイ論理 BL∀上で本質的に不完全です。また、\Sigma-完全でもあることがわかっています。私が関心を持つファジイ論理上で包括原理を持つ集合論 H で展開される算術では、再帰定理により、関数ではなく、FQ^- と同じく関係として足し算・掛け算が定義されるため、Hと、FQ^- は深く関係がありそうです。実際、自然数全体の集合\omegaがクリスプ集合であれば、Hに、FQ^- を埋め込むことができることがハジェクによって示されており、私にとっても目が話せない分野です。

（内容は後で追加します）