第 I 部 証明

はじめに

本書では情報科学の分野で生じる問題を解析するための数学的なモデルと手法を解説する。証明は本書で中心的な役割を果たす。なぜなら、数学的事実を本当に理解するには証明が不可欠であるという考えを多くの数学者と同様に著者らが持っているからである。情報科学で証明が用いられる機会は増加している: ソフトウェアやハードウェアが常に正しく振る舞うことは、どれだけ多くのテストを実行しても示せない。

簡単に言えば、証明とは真理を立証するための手法である。「真理」は美しさと同じように観察者によって変化する。そのため分野によって証明の構成要素が異なっていても驚くことではない。例えばアメリカの司法制度では、裁判において認められた証拠から陪審員が法的な真理を決定する。ビジネスの世界では、信頼できる人物や組織 (または単に上司) が権威的な真理を決定する。物理学や生物学といった分野では、実験によって科学的な真理¹が確かめられる。統計学では、サンプルデータの統計的解析により蓋然性の高い真理が計算される。

哲学的な証明はもっともらしい短い議論をいくつか含んだ注意深い説明と説得から構成される。最もよく知られた哲学的な証明はラテン語 Cogito ergo sum (「我思う、ゆえに我あり」) から始まる。この一節は十七世紀の数学者・哲学者 Renéルネ Descartesデカルト が記した文章の冒頭であり、世界で最も多く引用されるフレーズの一つである: ウェブで検索すれば大量の使用例が見つかるだろう。

自身の存在について考えられるという事実から自身の存在を結論付ける議論は非常にクールで、説得力もそれなりにありそうに思える。しかし、ここから数行の議論の後 Descartes は「神の慈悲は無限である」と結論付けている。神が無限に慈悲深いと信じるかどうかは別にして、これほどに短い「証明」は強引なこじつけでしかないことには同意できると思う。つまり優れた頭脳の持ち主であっても、このアプローチでは説得力のある証明を生み出せない。

数学者も彼ら固有の「証明」の概念を持っている:

この定義には三つの重要な概念が含まれている: 命題、公理、そして論理的演繹である。第 1 章では、これら三つの概念を定義し、証明の基本的な作法を説明する。第 2 章では整列原理 (well ordering principle) と呼ばれる証明の基礎的なツールを紹介し、第 5 章では整列原理と密接に関連する証明技法である数学的帰納法を紹介する。

命題を証明するには、その命題の意味を正確に理解しなければならない。普段の言葉に含まれる曖昧性や不正確な定義を避けるため、数学者は厳密に言葉を使用し、命題を論理式 (logical formula) を使って表現することが多い。論理式は第 3 章で解説される。

最初の三つの章では、読者が集合や関数といった基本的な数学的概念を知っていることが仮定される。第 4 章と第 8 章では、そういった数学的データ型を詳しく解説し、無限集合に関する性質を証明するための性質や手法を見る。第 7 章では再帰的に定義されるデータ型を解説する。

参考文献

[14], [49], [1]