数学ガール ゲーデルの不完全性定理 その１ 結城浩
◆概要
数学ガールとは結城浩さんの著作で、学生が数学について考えていくストーリーとなっている。ストーリーが面白いだけでなく、ガロワ理論やフェルマーの最終定理など様々な数学にまつわる話を書いている。数学を読む本であるというのが私の印象である。
本書はゲーデルの不完全性定理について書いている。ゲーデルの不完全性定理は以下の2つから構成される。
第1不完全性定理とは、ある条件を満たす自然数論は、 どんなに工夫してもその中に証明も反証もできない論理式が存在するというもの。
第2不完全性定理とは、数学的帰納法が扱える自然数論では、それが無矛盾なら、 自分自身が無矛盾であることを証明することはできないというもの
昔、岩波文庫のゲーデルの不完全性定理を読んでまったく理解できなかったので、今度こそと思い、とっかかりとして本書を読む。
◆本記事の内容
◆論理ゲーム
◆例
冷蔵庫のプリンが誰かに食べられてしまった。
幼女Aは「犯人はBです」と発言した。
幼女B,Cもある発言をした。
その後、
『犯人はABCのうち誰か1人』
『犯人だけが発言で本当のことを言った』
ということが分かった。
犯人は誰？
◆ポイント
条件が多すぎるとダメ。少なすぎるとダメ
多すぎると問題が簡単になってしまう。
少なすぎると、答えが分からない。または数パターン発生する。
微妙な塩梅を出すのが難しい。
◆論理の限界
「私はうそつきだ」
という人はうそつきか、正直者か？
この問いに対しては答えることができない。
正直者だとしたら私は正直者だと答える。
うそつきだとしたら私は正直者だ（＝うそつきではない）とこたえる。
つまり、私はうそつきだという人はいないのである。
個人的な印象だが、このような自己言及的な論理、再帰的な論理はループにはまりやすく、複雑になりがちだと思う。
◆ペアノの公理とは
自然数は次の5条件を満たす。
１．自然数 0 が存在する。
２．任意の自然数 a にはその後者 (successor)、suc(a) が存在する（suc(a) は a + 1 の "意味"）。
３．0 はいかなる自然数の後者でもない（0 より前の自然数は存在しない）。
４．異なる自然数は異なる後者を持つ：a ≠ b のとき suc(a) ≠ suc(b) となる。
５．0 がある性質を満たし、a がある性質を満たせばその後者 suc(a) もその性質を満たすとき、すべての自然数はその性質を満たす。
◆ポイント
公理を導出するには、既存の知識を使用できない。
なぜならば、我々の知識は公理の上に成立しているからである。
自然数とは何かということを我々は直感的に知っているし、おそらく99％程度は正しい理解をしていると思う。
しかし、自然数とは何かを一般化できることはないだろう。
◆集合と写像
◆集合
集合論は一種の言語であり、明確な呼び方をしてあげる必要がある。
例えば、１は整数という集合に属している。
偶数という集合と奇数という集合の積集合は空集合である。etc.
ポイントは包含関係、積集合、和集合
◆写像
ある集合に何らかの操作を加えて別の集合に移すことを考える。
例えばXという集合とYという集合があるとする。Xという集合の構成要素ｘに対し、F(x)という操作を行い、Yという集合の中に移されるとすると、以下のような関係になることが考えられる。
（１）全単射
ｘとｙが1対1で決まる。
例えば、X、Yを整数全体の集合とする。
構成要素についてy=xとすれば全単射といえる。
当然、XとYの構成要素数は同じとなる。
（２）全射
ｘが決まるとｙが決まるが、逆にｙがわかってもｘが決まらない。
平たく言えば、ダブりを許容するということ。
例えば、Xを整数全体の集合とし、Yを0と自然数の集合とする。
構成要素についてy=|x|とすれば全射となる。
（３）単射
xが決まればyが決まるが、Yのすべてを埋め尽くせるわけではない。
平たく言えば、漏れを許容するということ。
例えば、X、Yを自然数全体の集合とする。
構成要素についてy=x^2とすれば単射となる。
◆ガリレオのためらい
◆矛盾
すべての自然数という集合Xとすべての自然数の2乗という集合Y。
この集合は全単射に該当する。
すると不思議なことが起こる。
1→1, 2→4, 3→9, 4→16, ……
すべての自然数の集合Xとすべての自然数の集合Yの個数は本当に一致するのか？
少なくとも両方の集合に10までの値という制約を与えてやると、
X ＝ ｛1,2,3,4,5,6,7,8,9｝
Y ＝ ｛1,4,9｝
なので明らかに全単射ではない。
しかし、考えを無限に拡張すると成立するのである。
（Xの無限とYの無限では表現は同じ無限でも、意味は違うということ）
◆まとめ
つらつらと読んだことをまとめていった。
ここまでは高校数学や大学1年の数学レベルなので、聞いたことはある話だった。
これらが、どうやってゲーテルの不完全性定理につながるか、見ていきたい。
（つづく）
