01 / 読書ガイド
読書ガイド
引用
Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press.
章の要約
第3版は序論と8つの章からなり、本文は約450ページで、そのあとに選ばれた演習の解答（約50ページ）、読書案内、1ページの証明技法のまとめが続く。初版は1994年、第2版は2006年に刊行された。序文が示す本書の中心的な考え方は「構造化された証明」である。構造化プログラムがいくつかの基本構文を入れ子にして組み立てられるように、証明もいくつかの基本構造を入れ子にして組み立てられ、証明すべき命題の論理形式がどの構造を使うべきかを教えてくれる、というものである。
序論
理論に入る前に証明を味わう部分である。素数と 2ⁿ − 1 の形の数を題材に、表に現れたパターンが予想になり、1つの反例がある予想を否定し、証明が別の予想に決着をつけるようすを示す。素数が無限に存在するというユークリッドの証明も紹介し、第3章のあとでこれらの証明に立ち返って、どのように組み立てられたかを分析すると予告している。
第1章：命題論理
演繹的推論と論理結合子、真理表、条件文と双条件文を扱う。同じ章で変数、集合、集合演算も導入される。集合論は本書全体で使われるうえ、論理の例としても役立つからである。
第2章：量化論理
量化子、量化子を含む同値性（「すべての」と「存在する」に否定がどう作用するかなど）、そして集合演算の続きの節からなる。
第3章：証明
本書の核心である。命題がとりうる形を順にたどり、それぞれに適した証明の構造を示す。まず証明戦略一般を扱い、次に否定と条件文、量化子、連言と双条件文、選言を含む証明、さらに存在と一意性の証明、そして追加の例の節が続く。序文は、初期の例は内容ではなく例示する構造のために選ばれており、そのためかなり自明であると断っている。使える技法が増えるにつれて、証明は数学的にも興味深くなる。
第4章：関係
順序対と直積、関係とその性質、順序関係、同値関係を扱う。序文によれば、第4章と第5章は、第3章の技法を練習する題材であると同時に、数学のあらゆる分野で使われる概念への入門でもある。
第5章：関数
関数、単射と全射、逆関数、関数のもとでの集合の閉包（この版で新設された節）を扱い、像と逆像についての「研究プロジェクト」と題した短い節で終わる。
第6章：数学的帰納法
帰納法による証明、さらなる例、再帰、強い帰納法、そして閉包への再訪からなる。この章は、序文がこの時点までに習得されていることを期待する第3章の技法の上に組み立てられている。
第7章：整数論
第3版で新たに加わった章で、最大公約数、素因数分解、合同算術、オイラーの定理、公開鍵暗号を扱う。第8章とともに、証明のさらなる練習の場であり、より進んだ数学がどのようなものかを垣間見せることを意図している。
第8章：無限集合
対等な集合、可算集合と非可算集合、カントール–シュレーダー–ベルンシュタインの定理を扱う。
主要概念
第1–2章：論理と集合
- 論理形式：結合子と量化子からみた命題の構造。それによって命題の証明のしかたが決まる。
- 真理表と論理的同値：2つの命題が常に同じ真理値をとるかどうかを確かめる方法。
- 量化子：「すべての」と「存在する」、およびそれらを否定し組み合わせる規則。
- 集合演算：和集合、共通部分、差集合などを、論理結合子と量化子を通じて定義したもの。
第3章：証明
- 証明の構造：P を仮定して Q に至る（「P ならば Q」の場合）、あるいは x を任意にとる（「すべての x について」の場合）といったパターン。これらを入れ子にして複雑な命題を証明する。
- 否定と選言：証明する際にも、仮定として使う際にも独自の戦略を必要とする命題で、別々の節で扱われる。
- 存在と一意性：ある性質をもつ対象がちょうど1つであることを証明すること。
第4–6章：関係、関数、帰納法
- 同値関係と半順序：対象を分類したり順に並べたりする関係。
- 単射と全射：1対1の関数と上への関数、およびそれらが可能にする逆関数。
- 閉包：与えられた要素を含み、ある関数について閉じている最小の集合。
- 帰納法と再帰：すべての自然数についての命題を証明し、数列を一歩ずつ定義すること。強い帰納法を含む。
第7–8章：整数論と無限集合
- 合同算術とオイラーの定理：余りの算術で、公開鍵暗号の基礎となる。
- 可算集合と非可算集合：1対1対応を通じて無限集合の大きさを比べること。
- カントール–シュレーダー–ベルンシュタインの定理：互いに逆向きの2つの単射があれば、2つの集合の大きさは等しい。
批判的分析
長所
- 例だけでなく方法を教える。 本書の中心的な主張は、証明の構造は証明すべき命題の論理形式から導かれるというものである。まず論理を教え、第3章で各形式とそれが要求する構造を体系的にたどることで、初学者がひらめきを待つのではなく証明を書き始める手がかりを得られるようにしている。1ページの証明技法のまとめが、この方法を一か所に集めている。
- 目標は普通の証明。 序文は、構造を示すための字下げされた概略は教育上の工夫にすぎず、目指すのは数学者が書くような段落形式の証明だと強調している。
- 豊富な演習と部分的な解答。 すべての節が演習で終わる。第3版では150題以上が追加され、星印付きの演習には約50ページの付録で解答またはヒントが与えられているので、独学にも使える。
- 無料のソフトウェアによる補助。 PD印の演習は著者の無料ソフト Proof Designer で取り組むことができ、著者はその後、本書と節番号が対応し、同じ技法を証明支援系 Lean で教える無料のオンライン教材 How To Prove It with Lean も公開している。
短所
- 意図的にゆっくり始まる。 序文自身が、第3章の初期の証明は構造を示すために選ばれているためかなり自明だと認めている。すでに簡単な証明を書ける読者には、前半は丁寧すぎると感じられるかもしれない。
- 扱う範囲のわりに長い。 400ページを超える分量が、論理、集合、関係、関数、帰納法、そして整数論と無限集合についての短い章に充てられている。ほかの移行期向けの本に見られる実数、極限、組合せ的な数え上げといった話題は扱われない。
- 論理は道具であって主題ではない。 第1–2章の論理は非形式的で、証明を書くために役立てられる。形式体系、健全性、完全性は数理論理学の本に委ねられている。
コースにおける位置づけ
本書はこのコースで最初に読む本として自然であり、数理論理学の本より前に読むとよい。無料で公開されている Richard Hammack の Book of Proof は、集合、論理、標準的な証明法、関係、関数、濃度という似た範囲を扱っており、代わりの教科書としても、演習の追加の供給源としても使える。Velleman ならではの貢献は、第3章における論理形式と証明の構造との体系的な結びつけにある。Peter Eccles の An Introduction to Mathematical Reasoning、R. B. J. T. Allenby の Numbers and Proofs、Martin Liebeck の A Concise Introduction to Pure Mathematics は、数体系やその他の純粋数学により重きを置いた証明への入門書で、方法とあわせて数学的な内容も多く学びたい読者に向いている。
Velleman のあと、コースは論理学そのものを主題とする段階に進む。Leary と Kristiansen の A Friendly Introduction to Mathematical Logic は一階論理、完全性、ゲーデルの不完全性定理を展開し、Herbert Enderton の A Mathematical Introduction to Logic は、すでに数学的推論に慣れた学生向けに、命題論理と一階論理をより厳密に扱う。本書の第1–3章は、そのどちらに対してもよい準備になる。
本書の使い方
本書は、数学や計算機科学で初めて本格的に証明に取り組む学生、典型的には1、2年生を対象としており、高校までの代数で十分である。星印付き演習の解答があるので、独学者にも向いている。
読書計画：
- 中核： 序論、第1–3章、第6章。第3章は急がないこと。本書の残りが適用する方法そのものであり、最後の節では序論の証明に立ち返って、それがどのように組み立てられたかを示している。
- 練習と語彙： 第4章と第5章。後の授業が前提とする関係と関数を与えてくれる。
- 1つまたは両方を選ぶ： 関心に応じて、第7章（公開鍵暗号で終わる整数論）か第8章（無限集合）。第8章は解析学や集合論の授業で扱う濃度の話題に自然につながる。
各節の演習に取り組み、まず付録で答え合わせができる星印付きのものから始めるとよい。証明を書く前に、第3章が教えるとおり、与えられているものと証明すべきものの論理形式を書き出し、証明技法のまとめを手元に置いておくこと。すぐにフィードバックを得たいなら、Proof Designer で PD 印の演習を試すか、第3章に入った段階で無料の How To Prove It with Lean の対応する節に取り組むとよい。