前回からの続きです。
まず「完全性」という概念について整理を試みましょう。まず取り扱うものには形式的体系(公理系)とそれに何らかの対象を当てはめたモデルという２つのものがあります。形式的体系は決められた記号からなる論理式の集合で、それらの論理式のうちのいくつか(無限個でもいい)を「公理」と定め、公理から「定理」を導く(証明する)ための「推論規則」を定めたものです。各論理式は「証明できる」か「証明できない」かのどちらかです。そして論理式はモデルに含まれる対象について述べた何らかの命題に対応していますが、命題については真であるか偽であるかはモデルを調べることにより定まるものとします。すると以下の３つの概念があります。
健全性 証明できる論理式に対応するモデルにおける命題は真である
意味論的完全性(Semantical completeness) モデルにおいて真である命題に対応する論理式は証明できる
統語論的完全性(Syntactical completeness) 全ての閉論理式Aについて「Aが証明できる」か「￢A(Aの否定)が証明できる」かのどちらかである
統語論的完全性は「強完全性(strong comp1eteness)」、「ポスト完全性(Post completeness)」などとも呼ばれます(Ref5,p9)。「証明論的完全性」と呼んだ人もいますが、あまり一般的ではなさそうです(web-2)。最近翻訳された『スマリヤンのゲーデル・パズル』[Ref-7]では「構文論的」と訳してありました[2015/10/11追加]。「統語論的」という訳も付け加えてありましたが、確かに辞書的には「構文論的」の方が普通の日本語かも知れません。
統語論的不完全性(統語論的に完全でないこと)と混同しそうなのが「矛盾」という概念です。これはある公理系が「Ａも￢Ａも証明できる」ような論理式Ａを持つことを言います。矛盾する公理系は現実を反映しないことは明らかですが、統語論的に不完全なだけなら「Ａも￢Ａも証明できない」論理式Ａがあるだけですから非現実的ではありません。真偽がわからないことはいくらでもあるのが現実というものですから(^_^)
統語論的に不完全な公理系の例には、ユークリツド幾何学の公理系から平行線の公理を除いたものがあります。平行線の公理は他の公理から独立ですから、この公理系では明らかに平行線の公理もその否定も証明できません。
なおRef5,p9によれば統語論的完全性は以下のように定義されています。ちょっとすっきりしない定義のようにも思えますが、背理法により導出できてしまったことになるのでしょう。すなわち、論理式Aを仮定して矛盾が生じたということなので、背理法により￢Aが証明できます。
=============================
(無矛盾な)理論が完全であるというのは,そこから導出できない論理式を一つでもそれに加えると矛盾することをいう
=============================
ゲーデルの第一不完全性定理は、「自然数の公理系を含む、無矛盾な公理系」についての統語論的完全性を否定したものです。つまり「自然数の公理系を含む、無矛盾な公理系」の閉論理式の中には、その閉論理式もその否定も共に証明できないものが必ずあるというものです。なお「自然数の公理系を含む公理系」として具体的に有名なものはペアノ算術と呼ばれるものです。
これに対して完全性定理の方は、「１階述語論理では健全性および意味論的完全性が成り立つ」というものです。ただしこのとき「真」というのは特定のモデルでは「真」で別のモデルでは「偽」であるものではなく、その形式的体系(公理系)に当てはまる全てのモデルについて「真」である(これを「恒真」とよぶ)という意味です。つまりゲーデルの完全性定理における健全性および完全性の意味は次のようになります。(Ref4)
------------
健全性 証明できる論理式は全て恒真式である(p86)
完全性 全ての恒真式は証明できる(p94)
------------
簡潔に次のような表現もされています。(Web-1c,P56)
------------
健全性 全ての定理は恒真式である
完全性 全ての恒真式は定理である
------------
健全性と意味論的完全性を合わせて単に完全性と呼ぶことも多く、完全性定理も「健全性および意味論的完全性が成り立つ」ではなく単に「(意味論的)完全性が成り立つ」と表現されることの方が多そうです。そもそも「１階述語論理」とは何じゃいという向きもあるかと思いますが、今のところは、階数が多い方が扱える対象が多いのだ、と言うだけにしておきす。
このように不完全性定理と完全性定理は、当てはめる形式的体系も完全性の意味も違うのです。なお閉論理式というところが大事なのですが、その意味は後述します。
さて統語論的完全性は形式的体系の中だけのことしか言っていませんから意味ははっきりしています。対して意味論的完全性はモデルにおける真偽を使っていますが、ではモデルにおける真偽はどうやって決めるのでしょうか？ 無数に考え得るモデルの全てについて真であるという恒真などどうやって確認できるのでしょうか？ と考えだして、私は悩んでいました。おまけに不完全性定理についても、「数学的には真であるにもかかわらず証明できない論理式が存在する」などと表現している人もいます。「数学的には真である」ことの定義は一体何？ と思ってしまうわけです。それにこれでは不完全性定理の方も「意味論的完全性」についての定理のようではありませんか。
ということで「真であることの定義」の謎も解きたいのですが、次回にはそういう回り道よりも先に、不完全性定理の本質にまず迫ってみたいと思います。
－－－－－－－－－－－－－－－－－－－－－－－
References
1) 野崎昭弘『不完全性定理―数学的体系のあゆみ(ちくま学芸文庫)』筑摩書房(2006/05)
2) 日本数学会『岩波数学辞典-第3版』岩波書店(1985/12) [71.記号論理]の項
3) 前原昭二『数学基礎論入門』朝倉書店(1977)
4) 上江洲忠弘『述語論理・入門―基礎からプログラムの理論へ』遊星社(2007/04)
5) 田中一之他『ゲーデルと20世紀の論理学(第2巻)完全性定理とモデル理論』東京大学出版会(2006/10)
6) 田中一之他『ゲーデルと20世紀の論理学(第3巻)2不完全性定理と算術の体系』東京大学出版会(2007/03)
7) Raymond M. Smullyan; 川辺治之(訳)『スマリヤンのゲーデル・パズル』日本評論社(2014/11/20) :原著は2013年らしい。
webs
1) 平賀譲[筑波大学・図書館情報メディア研究科・教授]の講義資料
http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/print.shtml
1a) 命題論理 http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/prop1.pdf
1b) 述語論理１ http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/pred1.pdf
1c) 述語論理２ http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/pred2.pdf
2) 吉永良正『ゲーデル・不完全性定理』(1992) 講談社ブルーバックス、の辛口書評
http://taurus.ics.nara-wu.ac.jp/staff/kamo/shohyo/logic-2.html
まず「完全性」という概念について整理を試みましょう。まず取り扱うものには形式的体系(公理系)とそれに何らかの対象を当てはめたモデルという２つのものがあります。形式的体系は決められた記号からなる論理式の集合で、それらの論理式のうちのいくつか(無限個でもいい)を「公理」と定め、公理から「定理」を導く(証明する)ための「推論規則」を定めたものです。各論理式は「証明できる」か「証明できない」かのどちらかです。そして論理式はモデルに含まれる対象について述べた何らかの命題に対応していますが、命題については真であるか偽であるかはモデルを調べることにより定まるものとします。すると以下の３つの概念があります。
健全性 証明できる論理式に対応するモデルにおける命題は真である
意味論的完全性(Semantical completeness) モデルにおいて真である命題に対応する論理式は証明できる
統語論的完全性(Syntactical completeness) 全ての閉論理式Aについて「Aが証明できる」か「￢A(Aの否定)が証明できる」かのどちらかである
統語論的完全性は「強完全性(strong comp1eteness)」、「ポスト完全性(Post completeness)」などとも呼ばれます(Ref5,p9)。「証明論的完全性」と呼んだ人もいますが、あまり一般的ではなさそうです(web-2)。最近翻訳された『スマリヤンのゲーデル・パズル』[Ref-7]では「構文論的」と訳してありました[2015/10/11追加]。「統語論的」という訳も付け加えてありましたが、確かに辞書的には「構文論的」の方が普通の日本語かも知れません。
統語論的不完全性(統語論的に完全でないこと)と混同しそうなのが「矛盾」という概念です。これはある公理系が「Ａも￢Ａも証明できる」ような論理式Ａを持つことを言います。矛盾する公理系は現実を反映しないことは明らかですが、統語論的に不完全なだけなら「Ａも￢Ａも証明できない」論理式Ａがあるだけですから非現実的ではありません。真偽がわからないことはいくらでもあるのが現実というものですから(^_^)
統語論的に不完全な公理系の例には、ユークリツド幾何学の公理系から平行線の公理を除いたものがあります。平行線の公理は他の公理から独立ですから、この公理系では明らかに平行線の公理もその否定も証明できません。
なおRef5,p9によれば統語論的完全性は以下のように定義されています。ちょっとすっきりしない定義のようにも思えますが、背理法により導出できてしまったことになるのでしょう。すなわち、論理式Aを仮定して矛盾が生じたということなので、背理法により￢Aが証明できます。
=============================
(無矛盾な)理論が完全であるというのは,そこから導出できない論理式を一つでもそれに加えると矛盾することをいう
=============================
ゲーデルの第一不完全性定理は、「自然数の公理系を含む、無矛盾な公理系」についての統語論的完全性を否定したものです。つまり「自然数の公理系を含む、無矛盾な公理系」の閉論理式の中には、その閉論理式もその否定も共に証明できないものが必ずあるというものです。なお「自然数の公理系を含む公理系」として具体的に有名なものはペアノ算術と呼ばれるものです。
これに対して完全性定理の方は、「１階述語論理では健全性および意味論的完全性が成り立つ」というものです。ただしこのとき「真」というのは特定のモデルでは「真」で別のモデルでは「偽」であるものではなく、その形式的体系(公理系)に当てはまる全てのモデルについて「真」である(これを「恒真」とよぶ)という意味です。つまりゲーデルの完全性定理における健全性および完全性の意味は次のようになります。(Ref4)
------------
健全性 証明できる論理式は全て恒真式である(p86)
完全性 全ての恒真式は証明できる(p94)
------------
簡潔に次のような表現もされています。(Web-1c,P56)
------------
健全性 全ての定理は恒真式である
完全性 全ての恒真式は定理である
------------
健全性と意味論的完全性を合わせて単に完全性と呼ぶことも多く、完全性定理も「健全性および意味論的完全性が成り立つ」ではなく単に「(意味論的)完全性が成り立つ」と表現されることの方が多そうです。そもそも「１階述語論理」とは何じゃいという向きもあるかと思いますが、今のところは、階数が多い方が扱える対象が多いのだ、と言うだけにしておきす。
このように不完全性定理と完全性定理は、当てはめる形式的体系も完全性の意味も違うのです。なお閉論理式というところが大事なのですが、その意味は後述します。
さて統語論的完全性は形式的体系の中だけのことしか言っていませんから意味ははっきりしています。対して意味論的完全性はモデルにおける真偽を使っていますが、ではモデルにおける真偽はどうやって決めるのでしょうか？ 無数に考え得るモデルの全てについて真であるという恒真などどうやって確認できるのでしょうか？ と考えだして、私は悩んでいました。おまけに不完全性定理についても、「数学的には真であるにもかかわらず証明できない論理式が存在する」などと表現している人もいます。「数学的には真である」ことの定義は一体何？ と思ってしまうわけです。それにこれでは不完全性定理の方も「意味論的完全性」についての定理のようではありませんか。
ということで「真であることの定義」の謎も解きたいのですが、次回にはそういう回り道よりも先に、不完全性定理の本質にまず迫ってみたいと思います。
－－－－－－－－－－－－－－－－－－－－－－－
References
1) 野崎昭弘『不完全性定理―数学的体系のあゆみ(ちくま学芸文庫)』筑摩書房(2006/05)
2) 日本数学会『岩波数学辞典-第3版』岩波書店(1985/12) [71.記号論理]の項
3) 前原昭二『数学基礎論入門』朝倉書店(1977)
4) 上江洲忠弘『述語論理・入門―基礎からプログラムの理論へ』遊星社(2007/04)
5) 田中一之他『ゲーデルと20世紀の論理学(第2巻)完全性定理とモデル理論』東京大学出版会(2006/10)
6) 田中一之他『ゲーデルと20世紀の論理学(第3巻)2不完全性定理と算術の体系』東京大学出版会(2007/03)
7) Raymond M. Smullyan; 川辺治之(訳)『スマリヤンのゲーデル・パズル』日本評論社(2014/11/20) :原著は2013年らしい。
webs
1) 平賀譲[筑波大学・図書館情報メディア研究科・教授]の講義資料
http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/print.shtml
1a) 命題論理 http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/prop1.pdf
1b) 述語論理１ http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/pred1.pdf
1c) 述語論理２ http://www.slis.tsukuba.ac.jp/~hiraga/mathinfo/docs/pred2.pdf
2) 吉永良正『ゲーデル・不完全性定理』(1992) 講談社ブルーバックス、の辛口書評
http://taurus.ics.nara-wu.ac.jp/staff/kamo/shohyo/logic-2.html
