不完全性定理についてまとめ

ゲーデルの「不完全性定理」の持つ意義について述べる為に、まずは「ラッセルのパラドクス」についての説明から始めることにしたい。 

　「ラッセルのパラドクス」とは、「数学を論理学で基礎づける」という論理主義と呼ばれる構想の為にフレーゲが自身で開発した述語論理をこれまでの論理学で扱っていた一階の述語論理から二階の述語論理へと拡張しようとした際に生じた、ラッセルがフレーゲに指摘したパラドクスである。 
　二階の述語論理とは、フレーゲが数という対象を述語論理へと取り入れるために考えたもので、例えば或る命題関数Fxに対してそのFxについて言及するような命題関数を扱うことを言う。 
つまり従来の一階の述語論理が命題関数の自由変項xの定義域として個体のみを扱ったのに対して、自由変項xの定義域として個体だけでなく命題関数を扱うことも認めたものが二階の述語論理なのである。 
そして変項に関数を入れることを無制限に認めた結果、ラッセルのパラドクスが生じることになった。 
　先程述べた考えでは、命題関数Fxの変項xとしてFx自身を扱うF(Fx)という自己言及の形の命題関数も認めることになる。 
そしてF(Fx)が偽であるような場合、すなわち「述語Fが自分自身に述語づけられないような述語である」場合を考えると矛盾が生じてしまうのである。 
　まず、「述語Fが自分自身に述語づけられないような述語である場合」をまとめて扱うために命題関数で表現して、 

ω(x) 「xは自分自身に述語づけられない述語である」　とする。 
ω(x)の定義より、 
ω(x)≡¬x(x)　であり、 
このxにω自身を代入すると、 
ω(ω)≡¬ω(ω)　となって、 
証明は省くがこれから、ω(ω)∧¬ω(ω)という矛盾式が導かれてしまうのである。これがラッセルのパラドクスである。 
　また、論理学における命題関数と数学における集合は同等のものであるので、集合についても同様のパラドクスが導かれてしまう。 
　このラッセルのパラドクスは論理主義だけの問題に留まらず、論理学・数学一般にまで大きな影響力を持った。 
そして、そのラッセルのパラドクスに対する反応の主だったものは三つの立場から為された。すなわち、論理主義、直観主義、形式主義である。 

　初めに、論理主義ではラッセルのパラドクスを発見した本人であるラッセル自身がパラドクスを回避する為の方法として「タイプ理論」を提案した。 
タイプ理論とは「個体を扱う表現をタイプ０、タイプ０の表現に対する述語をタイプ１、タイプ１の述語に対する述語をタイプ２…」というように表現についてタイプを定め、その上で「或る述語が述語づける相手は必ずその述語よりもタイプの低いものとする」という規則を設けて自己言及を禁止することでパラドクスを避けるという理論である。 
ただし、全ての自己言及表現がパラドクスを引き起こすわけではないので、タイプ理論は処置としては少し強すぎる等の問題もあり、現代では、タイプという考えは生きているが、主流ではなくなっている。 

　次に、直観主義では数学者ブラウアーによって、ラッセルのパラドクスは無限という対象を実在論的に扱った結果生じたものであるという考えが提案された。 
直観主義とは、無限という”完成された”対象が存在するわけではなく、或る操作を際限なく繰り返すことで無限は”構成される”とする立場である。 
　この構成主義的見方に従うとラッセルのパラドクスは、無限集合M={x|x∉x}を完成された集合として扱っているのであり、そこに問題があるということになる。 
構成された集合Mに新たに要素としてM自身を加えたならば、その時点でMは構成し直され新たに集合M’となり、M∈MではなくM∈M’となる。 
　命題関数で同様に考えようとするならば、まず変項となる対象xを集めて関数Fxが構成され、次に今構成されたFx自身が新たに変項となる対象xとして加えられたので定義域の変化に伴い関数FxはF’xとなるため、ラッセルのパラドクスで自己言及とされた表現F(Fx)はF’(Fx)となり自己言及ではなくなるのである。 
　また直観主義では証明もまた構成主義的手法に限定されることになる。 
そこでは無限へとアプローチする為の手法として数学的帰納法が認められるが、しかし一方で排中律が無条件で成立するわけではなくなるという制限も受けてしまうことになるのである。 

　この直観主義の考え方に反対したのがヒルベルトである。 
ヒルベルトの考えでは制限されるべきなのは証明の手法ではなく、重要なのはそこに矛盾が生じないことをきちんとチェックすることであり、むしろこのチェックの段階において構成主義的手法が用いられるべきだとされる。 
こうして提案された、形式的体系としての数学とメタ数学的チェックという二本立てのアイデアがヒルベルトの唱えた形式主義の立場である。 
　形式的体系としての数学という考えでは、公理的方法により数学を形式的体系として整理する。公理系とは単なる記号変形のシステムであり”意味抜き”された形式的体系であるから「無限」などといった観念の”意味”を考える必要はなくなり、直観主義のように排中律を拒否する必要もなくなるため従来通りの述語論理が採用できる。 
また無限集合においては、パラドクスを回避できるように公理系を整備する。 
ラッセルのパラドクスに対しては、無限集合を集合の対象として無制限に認めたことにより引き起こされたものなので、問題が起きないような性質の良い無限集合だけに対象を制限した公理を設けることで回避できるのである。 
　またメタ数学とは公理系に対して「有限の立場」と呼ばれる構成主義的手法でその無矛盾性を証明するというものである。 
ここでもやはり、証明とは”有限回”の手続きに従った一連の式変形に他ならないものとして捉えられるので、排中律を拒む理由はなく、メタ数学においても排中律は許容されるのである。 
　しかし、この形式主義の立場にも問題があるということがゲーデルによって示されてしまう。 
具体的には「有限の立場」に限定されたメタ数学という考えが、公理的方法とそれに対するメタ的チェックという考えが現代まで生き残っているという一方で、挫折することになるのである。

ヒルベルトの計画に拠ると、 
① 数学について“意味抜き”された形式的な公理系を整理し、 
② メタ数学の立場からその無矛盾性を、つまりどの命題もその体系内でそれ自身の肯定と否定が同時に証明されないことを示す。 
これにより、体系が健全であることが保証されるからである。 
③ メタ数学の立場から公理系の完全性、すなわちどの命題であってもその肯定か否定が体系内で証明されることを示す。 
これにより、数学の命題が必ず解決することが保証されるからである。 
　という以上のことが上手くいけば、数学が完全であることが確立されるということであった。 
　そしてこれらの証明は「有限の立場」のメタ数学で行われる。 
つまり、無矛盾性を証明したい体系と同等の体系を用いて証明を行うことになる。 
なぜなら、証明したい体系よりもより強力な体系で証明を行えばより不確実なもので確実なものについて証明することになってしまうからである。 
　この計画はゲーデルの「不完全性定理」により実効深野であることが示される。この「不完全性定理」の中核は以下の二つの主張から成る。 

　第一不完全性定理：自然数論の公理系Nがω無矛盾ならば、ある自然数nが存在し、Pr(n)も￢Pr(n)も公理系Nでは証明不可能となる。 
　第二不完全性定理：自然数論の公理系Nが無矛盾ならば、その無矛盾性は公理系Nでは証明できない。 

　第一不完全性定理により、「自然数論の公理系が不完全である」ということが主張され、第二不完全性定理により「有限の立場でのメタ数学では自然数論の無矛盾性は証明できない」ということが主張される。 
　数学の最も基礎的な部分である自然数論においてこの結果である以上、数学全体において完全性を主張出来る道理はなく、ヒルベルトの計画は実行不可能ということになるのである。 

　不完全性定理はまず、「私は証明不可能だ」というメタ数学の命題を表現する自然数論の式￢Pr(g(A))≡Aを構成することを一つの目標とする。 
ここでg(A)は式Aのゲーデル数であり、Pr(n)は「ゲーデル数Aの式は自然数論の公理系Nで証明可能である」というメタ数学的命題を表現する自然数論の式である。 
　そして証明及び詳しい説明は省略させてもらうが、公理系Nの任意の一変数の式について対角線論法を用いることで次の補助定理が導かれる。 
任意の式F(x)に対して、次のような式Aが存在する。 
F(g(A))≡A 
ここでF(x)は任意の式であるので、F(x)として￢Pr(x)をとることで先程の式、 
￢Pr(g(A))≡A となるような式Aが存在する。 
という定理(#)を得る。 
また、公理系Nに式Aが存在するならAは証明可能なはずであり、「Aは証明可能である」というメタ数学の命題が成立するので、それを表現する自然数論の式Pr(g(A))をAから導出して良いことになる。 
　さらに、その逆にPr(g(A))からAを導出しても良いが、こちらは公理系Nがω無矛盾であることが必要となる。 
これは式Aが公理系Nの定理ならば式Aは証明可能であり、式Aが証明可能ならば式Aは公理系Nの定理であるということを表している。 

　そしてこれらを踏まえて考えると、 
(#)より、￢Pr(g(A))≡A を満たす式Aが存在し、g(A)=nとして、 
￢Pr(n)≡Aである。 
　ここで、￢Pr(n)が証明可能であると仮定し、￢Pr(n)≡AよりAも証明可能。 
Aが証明可能なのでPr(g(A))が導出され、g(A)=nよりPr(n)。 
　従って、￢Pr(n)が証明可能であると仮定するとPr(n)も証明可能になり矛盾式を導くので、公理系Nが無矛盾ならば￢Pr(n)は公理系Nにおいて証明不可能であり、またω無矛盾は無矛盾よりも強い条件であるので、公理系Nがω無矛盾ならば￢Pr(n)は公理系Nで証明不可能である。 
　そして、Pr(n)が証明可能であると仮定すると、g(A)=nよりPr(g(A))も証明可能。 
　公理系Nがω無矛盾ならばPr(g(A))からAを導出して良いのでAを導出し、￢Pr(n)≡Aより、￢Pr(n)も導出される。 
　従って、Pr(n)が証明可能であると仮定すると、￢Pr(n)も証明可能となり矛盾式を導くので、公理系Nがω無矛盾ならばPr(n)は公理系Nにおいて証明不可能。 
　以上より、第一不完全性定理を得る。 

　また公理系Nが無矛盾であるならば定理として証明できないような式が存在するはずである。 
なので、「公理系Nは無矛盾である」というメタ数学の命題は「証明不可能なあるゲーデル数xの式が存在する」ということと同値であり、公理系Nの式として表現すると、∃x￢Pr(x)である。 
　 
　先程の第一不完全性定理より、 
　公理系Nが無矛盾ならば￢Pr(n)は公理系Nで証明不可能であり、 
￢Pr(n)≡Aより、Aも証明不可能。 
　また、g(A)=nより公理系Nが無矛盾ならばゲーデル数nの式は証明不可能である。 
　「公理系Nが無矛盾である」は公理系Nの式では∃x￢Pr(x)なので、 
以上は、∃x￢Pr(x)⊃￢Pr(n)　と書ける。 
　これより、公理系Nにおいて∃x￢Pr(x)が証明可能ならば公理系Nにおいて￢Pr(n)も証明可能。 
　この対偶をとって、公理系Nにおいて￢Pr(n)が証明不可能ならば公理系Nにおいて∃x￢Pr(x)も証明不可能。 
　そして、公理系Nが無矛盾ならば￢Pr(n)はNでは証明不可能なので、従って、公理系Nが無矛盾ならば∃x￢Pr(x)はNでは証明不可能となり、以上より第二不完全性定理を得る。 

　このようにして、有限の立場に限定されるメタ数学では自然数論の公理系Nの完全性を証明できないということが示され、ヒルベルトの数学を基礎づける為の計画は上手く行かないことが宣告されたのである。 
　とは言え、このことに「人間の知性の限界が示された」などと過大な解釈を与えるのは全く余計なことである。 
不完全性定理は、公理系の“中で”証明できないことがあるという事実を示したのであり、その証明できないことも非形式的な、つまり真であるということが判明したなら証明されたとするような一般的な意味で証明することは不可能ではないからである。 
公理系からはみ出るからと言って人間の知性からはみ出すというわけではないのである。 
　数学内の命題は論理命題と同様、特定の事実や思考内容を表現するものではない。 
なので、数学的何事か、勿論公理系の無矛盾性も含むを証明するという時にどのような数学的規則・道具立てが許容されるかということは結局、人間の実際的知性により判断されるのである。 
　数学の公理系の完全性がその中で証明できないことが示されたことにより「人間の知性の限界が示された」のではなくむしろ、「数学的真理の限界が人間の知性に因っている」ということが再確認されたのではないかと思う。 



参考文献：『論理学』　著 野矢茂樹 　東京大学出版