完全性定理についての不完全な説明

二月になりました。あけましておめでとうございます。
サークルのごたごたしたこととかが片付いて、昨日一日寝て、やっと春休みを始められるかなという気持ちです。

今日から数学を頑張りますが、とりあえずこの一週間でゼミの内容をまとめるという課題がありますのでそれについて今回は軽く触れます。

デザイン変えてみたのですが、重いかもしれません。（気分も）

概要

科目・分野：数理論理学、数学基礎論、証明論（などと言えばよろしいのだろうか）
教科書：数理論理学（現代基礎数学シリーズ15）（著者:鹿島亮）（出版：朝倉書店）

目的としては「ゲーデルの完全性定理および不完全性定理の意味を理解し、自然演繹についての証明をなぞる。」
と言ったところでしょうか。

数理論理学の目的

数理論理学と言い切ってしまっては語弊があるかもしれませんが、広い意味で捉えていただき、ゲーデルやヒルベルトが何をしたかったかを簡単に述べていると理解していただければ幸いです。

まず、数学がありました（？）
数学はとても研究が盛んな学問であり、様々な有効な結論を得てきました。紀元前からです。
そして時は流れ、割と最近の1900年ごろの話です。
ヒルベルトという数学者が
「数学っていう学問そのものについて研究して、数学が完璧だってことを証明しちゃわない？」と言い出しました。

数学という学問において重要なことは「証明」であり、演繹的に議論を繰り返していくことが数学です。
となると、この演繹的推論を数学的に定式的に表現することができれば、数学という学問の性質について研究できるんじゃないか？
数学という学問の性質を研究して、数学という学問が完璧（全部の主張をかならず証明できて、矛盾が起きることもない）であることを示せるんじゃないか？
と、ヒルベルト達は考えたわけです。

何故こんなことを考え出したのかといいますと、ちょうどその頃数学界にはたくさんの「矛盾」が存在していたのです。
その矛盾が何故起きるかを見つめなおし、矛盾の起きないような完璧な数学をつくり、保障しようとしていたんですね。

その頃の矛盾で有名なものを一つ紹介します。
ラッセルのパラドックスというものです。

ラッセルのパラドックスとは、自分自身を要素として含まない集合全体の集合の存在から矛盾が導かれるというパラドックスである。（wikipediaより）

ある集合がありまして、その集合に含まれないものだけを集めた集合について考えるということです。
数式で書くと
${ R=\{x|x\notin x\} }$
こんな集合です。

これについて、 ${R}$ が ${R}$ の中の一部だとします（ ${R}$ という集合自体は ${R}$ という集合の中に含まれている ${R\in R}$ ）。
とすると、 ${R}$ の中に ${R}$ が入っているので
${R\notin R}$ でなければいけません。これはおかしいですね。
入っていると仮定したのに入っていてはいけなくなりました。
では元々入っていなかったのだろうということで ${R\notin R}$ について考えても、元々の ${R}$ の定義から ${R}$ に入っていないためには ${R}$ に入っている必要があります。
つまり ${R\in R}$ となってしまい矛盾してしまいます。
つまり ${R}$ の中に ${R}$ は入っていても入っていなくてもおかしい、つまり矛盾しているということがわかりました。

ではそもそもなんでこんな矛盾が起きてしまったのか。
それは集合の定義が曖昧だったからです。
集合というものはこういうもので、こういうものしか集合と呼んではいけません。という条件がちゃんと与えられていなかったことが問題だったと考えられ、正しい定義と向き合う必要があったのです。

（"入っている"と表現していますが数学的には"属している"などと言います。）

このような矛盾がいっぱい出てきてしまったので、ヒルベルト達が完璧を求めて動き出しました。

そこにやってきたのがゲーデルです。
ゲーデルさんは頑張りました。
まず、第一階述語論理というものを適用している数学については何でも証明できる、つまり完全だよ。ということを証明しました。
これがかの有名な完全性定理です。

一部の数学が完璧に近づきました。

次に、自然数が公理に入ってる理論では正しいか正しくないのかわからない結論がかならず存在する。また、その理論が矛盾しないことを証明できない。
ということを証明してしまいました。（少し仮定が雑なので正しい定理が気になる人は調べてみてください。）
これがかの有名なゲーデルの不完全性定理です。

つまり、自然数が入っているようなかなり一般的な数学においては、その数学の中に矛盾が存在しないことを示せないということがわかってしまいました。

ヒルベルトもゲーデルももう発狂です。
簡単に使える万能細胞を作ろうと思ってたら、そんな細胞作れないことがわかってしまったようなもんです。
もうビッグニュースですよ。

しかし、ここで誤解しないでほしいのは、「数学は矛盾を孕んだやべえ学問だ」というわけではないことです。
「ある条件下では矛盾が示せないことが明らかになった。」と理解すれば、ゲーデルの不完全性定理は確実にヒルベルトプログラムを正しい方向へと一歩進めたとわかるでしょう。

ただでさえこんなカッコいい名前なので誤解されやすいです。「理性の限界を証明した。」とか比喩表現だと思いますので鵜呑みにしないでください。
僕自身勉強途中なので誤解しているところがあるかもしれません。
気になった人は独学で理解し直すことを進めます。

完全性定理証明の前準備

ここからが今回の記事のメインです。
自分のゼミの予習を兼ねているので人に説明するように書いていないかもしれません。
まずはいくつか定理と定義を紹介していきます。
以下、仮定となる論理式の集合 ${\Gamma}$ は（閉）論理式の集合

健全性定理：証明されたものは必ず正しい
完全性定理：正しいものは必ず証明できる（健全性定理の逆）
補題：以下の２つは同じことである
・ ${\Gamma \cup \{ \varphi\}}$ から矛盾が導ける
・ ${\Gamma}$ から ${\neg \varphi}$ が証明できる
モデル存在定理：無矛盾ならモデルが存在する
モデル： ${\Gamma}$ を真にするストラクチャーのこと
ストラクチャー：以下の３つを合わせたもの（つまり記号をどう扱うか定めたもの）
・命題記号の真理値が割り当て（ｆ：{記号}→｛真,偽｝みたいな）
・対象領域：空でない集合（変数の値の集合）
・対象領域の中での定数、関数、述語の解釈

教科書に則った場合の証明は

モデル存在定理⇒完全性定理
モデル存在定理＋α⇒モデル存在定理
極大無矛盾集合などを用いてモデル存在定理＋αを証明

となっています。
つまり、モデル存在定理＋α⇒モデル存在定理⇒完全性定理
というわけです。他にも色々な証明があるらしい。

今回は1.を適当に説明します。~~（3.はまだやってない。明日（今日）ゼミ。）~~

1.モデル存在定理⇒完全性定理

モデル存在定理から完全性定理の対偶（証明できないものは正しくない）を示します。

つまり、無矛盾ならモデルが存在することを利用して「証明できないものは正しくない」ことを示せば良いです。

証明できない命題は ${\varphi}$ とでもおきます。

補題を用いる（対偶を考える）と
「$Gamma$から証明できない命題 ${\varphi}$ が存在するとき、その証明できない ${\varphi}$ の否定を加えた*1$Gamma$は無矛盾」といえます。
${\Gamma}から{\varphi}$ が証明できない⇒ ${\Gamma \cup \{\neg \varphi\}}$ は無矛盾
${\Gamma \cup \{\neg \varphi\}}$ は無矛盾なのでモデル存在定理より ${\Gamma \cup \{\neg \varphi\}}$ のモデルが存在します。
つまり、 ${\Gamma \cup \{\neg \varphi\}}$ を真にするストラクチャーが存在します。
${\Gamma \cup \{\neg \varphi\}}$ が真になるということは ${\Gamma が真かつ \neg \varphi が真}$ になるということなので、
${\varphi}$ が偽になります。
つまり ${\varphi}$ は正しくないので、モデル存在定理を用いて証明できないものが正しくないことがいえました。 ${\Box}$