|
ゲーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理の一つで、クルト・ゲーデルが1930年に証明したものである。 ; 第1不完全性定理 : 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。 ; 第2不完全性定理 : 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。 == 概要 == ゲーデルの定理でいう証明不能命題Gは、「Gは証明できない」という命題と同値である。Gはゲーデル文と呼ばれる。 Gが証明可能であれば、Σ1完全性により命題「Gは証明できる」もまた証明可能である。一方Gは命題「Gは証明できない」と同値であることが証明可能であるので、両者から矛盾が導かれる。 つまり *「Gが証明できる」ならば「矛盾が証明できる」 ... (A) したがって、対偶を取れば *「矛盾が証明できない」ならば「Gが証明できない」 ... (B) となる。 また、￢Gが証明可能であれば、Gの性質から命題「Gは証明できる」も証明可能である。この際、もしGそのものが証明不能だとすると、ω矛盾ということになる。ω無矛盾であればGも証明可能である。しかしGが証明可能であれば「Gは証明できない」も証明可能であるので、やはり両者から矛盾が導かれる。したがってω無矛盾であれば￢Gも証明できないのである。よってω無矛盾であれば、Gも￢Gも証明できない（第一不完全性定理）。 なお、証明可能性の代わりに真理性を用いるならば、パラドックスが導かれる。このことから、自然数論における真理性は自然数論の中では表現できないことが示される（タルスキの定理）。 ゲーデル文を構成するためには自然数論の式を自然数に変換するゲーデル数および自己言及で用いられる対角化の技法（を形式化したもの）が必要である。後者は対角化補題と呼ばれる。 自然数を変数とする述語「xは…である」の対角化は、左記の述語のxに「xは…である」のゲーデル数を代入した命題である。その意味は「「xは…である」は…である」となる。 ゲーデル文Gは「「xで表される述語の対角化は証明できない」で表される述語の対角化は証明できない」と表される。「xで表される述語の対角化は証明できない」の対角化は、G自身と同値になる。 さて、自然数論の無矛盾性とは、「自然数論において矛盾が証明できない」ということである。そして、自然数論による自然数論の無矛盾性証明とは、「」内が、自然数論で証明できるということである。 「自然数論で矛盾が証明できない」と自然数論で証明できれば、第一不完全定理での議論中の(B)より「Gが証明できない」と証明できる。 しかし、「Gが証明できない」とはGと同値であるから、Gも証明されることとなり、そこから第一不完全定理での議論中の（A)により、矛盾が証明される。 したがって自然数論が無矛盾、すなわち自然数論で矛盾が証明されないならば、そのこと自体も自然数論では証明できない（第二不完全性定理）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゲーデルの不完全性定理」の詳細全文を読む スポンサード リンク
|