Book of Proof（証明の本）

引用

Hammack, R. (2018). Book of Proof (3rd ed.). Richard Hammack. Free official edition: https://richardhammack.github.io/BookOfProof/

章の要約

第1章：集合

本書は「数学のすべては集合で記述できる」という前提から出発し、第1章で以後すべての章で使う語彙を整える。内包的記法（集合の条件による記述）、直積、部分集合、べき集合、和集合・共通部分・差集合・補集合、ベン図、添字付きの集合族を扱う。最後に標準的な数の体系を集合として見直し、ラッセルのパラドックスを短く紹介して、何を集合とみなすかに注意が必要な理由を示す。

第2章：論理

証明をつなぎとめる論理を説明する章である。命題、「かつ」「または」「でない」という結合子、条件文と双条件文を定義し、真理値表を用いてド・モルガンの法則や、条件文とその対偶の同値といった論理的同値性を確かめる。続いて量化子、日常の英語と記号論理の相互翻訳、量化された命題の否定、推論規則を扱い、最後の節では論理を学ぶ理由――「ならば」や「すべての」といった言葉の意味を確定させること――をまとめている。

第3章：数え上げ

第3版で拡充された章で、対象を一つずつ数えずに「いくつあるか」に答える方法を扱う。列（リスト）、積の法則・和の法則・差の法則、階乗と順列、部分集合の個数としての二項係数、パスカルの三角形と二項定理、包除原理、多重集合の数え上げ、割り算の原理と鳩の巣原理を順に展開し、二つの式が同じものを数えていることを示して等式を証明する「組合せ論的証明」で締めくくる。序論ではこの章を省略可能としているが、後の例や演習で使われる素材を提供している。

第4章：直接証明

第II部は「定理」「証明」「定義」の意味から始まり、以降の章が依拠する厳密な定義（偶数と奇数、整除、素数、最大公約数など）を定める。「PならばQ」の直接証明は、Pを仮定してQまで推論する、という手順の型として提示され、整数に関する事実で練習する。さらに証明を場合分けする方法と、似た場合を一度だけ扱う方法を示す。

第5章：対偶による証明

第2章で確かめた論理的同値性を土台に、「PならばQ」を「QでないならばPでない」を示すことで証明する方法を学ぶ。直接証明よりずっと簡単になる例が示される。新たな命題の題材として、nを法とする整数の合同を導入する。後半の数学的文章の節では、文を記号で始めない、数式の後にも句読点を打つ、記号同士を言葉で区切るといった実践的な規則を列挙している。

第6章：背理法

三つ目の主要な技法は、命題が偽であると仮定して矛盾を導くことである。本章はこの方法を論理的に正当化し、√2の無理性や素数が無限に存在することといった古典的な結果に適用したうえで、条件文への応用や他の技法との組み合わせを扱う。結びの助言は、背理法の証明の中にはより簡単な対偶証明が隠れていることが多いので、まず直接証明か対偶証明を試すべきだというものである。

第7章：条件文でない命題の証明

第III部では、「PならばQ」の形をしていない命題へと手法を広げる。「…のとき、かつそのときに限り」の命題、互いに同値な命題の列、存在証明、存在と一意性の証明を扱う。また、対象を実際に構成する構成的証明と、対象を特定せずに存在しなければならないことを示す非構成的証明を対比する。

第8章：集合に関する証明

これまでの技法を集合論の三つの基本作業――ある要素が集合に属することの証明、ある集合が別の集合の部分集合であることの証明、二つの集合が等しいこと（両方向の包含）の証明――に適用する。完全数を扱った長い例では、集合の等式を示す議論が実質的な整数論の内容を担いうることを、ユークリッドとオイラーに帰される推論に沿って示し、メルセンヌ素数にも触れる。

第9章：反証

命題を、真と知られているもの、偽と知られているもの、未解決のものに分けたうえで、命題が偽であることをどう示すかを説明する。主な道具は反例であり、存在命題の反証（その否定である全称命題を証明する）や、背理法による反証も扱う。

第10章：数学的帰納法

最初のn個の奇数の和がn²になるという予想を動機として、通常の帰納法、強い帰納法、最小反例による証明を提示する。これらの方法を用いて算術の基本定理（素因数分解の存在と一意性）を証明し、フィボナッチ数に関する恒等式を導く。

第11章：関係

第IV部は、順序対の集合として定義される関係の一般理論から始まる。反射律・対称律・推移律、同値関係、同値類と分割の対応を学ぶ。具体例としてnを法とする整数を構成し、最後に二つの異なる集合の間の関係を扱って関数の定義への準備をする。

第12章：関数

関数を特別な関係として定義することで、公式にとどまらない一般的な見方を可能にする。単射・全射・全単射、関数の言葉による鳩の巣原理の言い換え、合成、逆関数、集合の像と逆像を扱う。

第13章：微積分における証明

第3版で新設され、明示的に省略可能とされている章で、解析学で使われる証明のスタイルを紹介する。三角不等式とイプシロン・デルタによる極限の定義から始め、ある極限が存在しないことを証明し、極限法則を導き、さらに連続性と微分、無限遠での極限、数列と級数の収束を扱う。微積分の履修経験を前提としている。

第14章：集合の濃度

最終章では全単射によって「濃度が等しい」ことを定義し、無限集合にも異なる大きさがあることを示す。整数や有理数は可算無限であるが、実数はそうではない。どんな集合もそのべき集合より小さいことを証明し、可算性の判定基準を与え、カントール＝ベルンシュタイン＝シュレーダーの定理を証明して、実数全体と自然数のべき集合が同じ濃度をもつことを示す。最後に連続体仮説に言及している。

主要概念

第1章：集合

• 内包的記法：{x ∈ ℤ : x は偶数} のように、要素が満たす条件によって集合を記述する方法。
• べき集合：与えられた集合のすべての部分集合からなる集合。n個の要素をもつ集合には2ⁿ個の部分集合がある。
• ラッセルのパラドックス：「自分自身を要素としない集合全体の集合」から生じる矛盾で、あらゆる記述が集合を定めるわけではないことを示す。

第2章：論理

• 条件文：P ⇒ Q は、Pが真でQが偽のときに限って偽となる。
• 論理的同値：条件文とその対偶のように、同じ真理値表をもつ二つの命題。
• 量化子の否定：「すべてのxについてP(x)」の否定は「P(x)でないxが存在する」であり、逆も同様である。

第3章：数え上げ

• 積の法則：各段階の選択肢の数が決まった段階的な手順で列を作るとき、列の総数は各段階の選択肢の数の積になる。
• 二項係数：n個の要素をもつ集合のk個の要素からなる部分集合の個数で、二項定理の係数にもなる。
• 組合せ論的証明：両辺が同じものを数えていることを示して恒等式を証明する方法。

第4章：直接証明

• 道具としての定義：「ある整数aによってn = 2aと書けるときnは偶数」のような厳密な意味の規定で、証明はこれを一歩ずつ展開する。
• 直接証明：Pを仮定し、定義と既知の事実からQを導く。
• 場合分けによる証明：仮定をもれのない場合に分け、それぞれで結論を示す。

第5章：対偶による証明

• 対偶：「QでないならばPでない」という命題で、「PならばQ」と論理的に同値である。
• nを法とする合同：nがa − bを割り切るとき a ≡ b (mod n) と書く。

第6章：背理法

• 背理法：命題の否定を仮定し、「CかつCでない」という形の結論を導く方法。
• 隠れた対偶：背理法による証明の多くは、より簡単な対偶証明に書き直せるという観察。

第7章：条件文でない命題の証明

• 「…のとき、かつそのときに限り」の証明：P ⇒ Q とその逆 Q ⇒ P の両方を証明する。
• 構成的証明と非構成的証明：対象を具体的に示すか、特定せずに存在しなければならないことを示すか。

第8章：集合に関する証明

• 部分集合の証明：Aの任意の要素をとり、それがBに属することを示す。
• 二重包含による集合の等式：A ⊆ B と B ⊆ A を両方示す。
• 完全数：6や28のように、自分より小さい正の約数の和に等しい自然数。

第9章：反証

• 反例：全称命題が偽であることを示すただ一つの事例。
• 存在命題の反証：その否定である全称命題を証明して、「…が存在する」という命題が偽であることを示す。

第10章：数学的帰納法

• 帰納法：基底の場合と、各場合が次の場合を導くことを示し、すべての自然数について命題が成り立つことを結論する。
• 強い帰納法：帰納段階で直前の場合だけでなく、それ以前のすべての場合を用いる。
• 最小反例：成り立たない最小の場合が存在すると仮定して矛盾を導く。

第11章：関係

• 同値関係：反射的・対称的・推移的な関係。
• 分割：集合を互いに交わらない空でない部分に分けること。同値関係の同値類は分割をなす。
• nを法とする整数：nを法とする合同による整数の同値類全体の集合。

第12章：関数

• 単射と全射：異なる入力が異なる出力をもつとき単射、終域のすべての要素が出力となるとき全射という。
• 逆関数：関数が全単射であるときに限って存在する。
• 像と逆像：定義域の部分集合の出力全体と、終域の部分集合に入る入力全体。

第13章：微積分における証明

• イプシロン・デルタによる極限：任意のε > 0に対し、0 < |x − c| < δ ならば |f(x) − L| < ε となるδ > 0が存在するとき、x → c で f(x) → L という。
• 三角不等式：|a + b| ≤ |a| + |b|。極限の証明における基本的な評価である。

第14章：集合の濃度

• 濃度が等しい：二つの集合の間に全単射があるとき、同じ大きさをもつという。
• 可算集合と非可算集合：ℕと同じ大きさ（または有限）の集合と、ℝのようにそれより大きい無限集合。
• カントール＝ベルンシュタイン＝シュレーダーの定理：二つの集合の間に両方向の単射があれば、全単射が存在する。

批判的分析

長所

• 技法ごとの構成。 第II部と第III部は、直接証明、対偶、背理法、同値性、存在、反証、帰納法といった方法を一つずつ取り出し、例を示す前にそれぞれの証明の型を提示する。初学者は、どの種類の命題を証明しようとしているのか、どの型を試すべきかを見分けやすい。
• 論理だけでなく文章にも注意を払う。 5.3節の数学的文章の指針や、より簡単な方法を優先せよという6.4節の助言は、証明を他人が読む文章として扱っている。丁寧に書かれた証明例と合わせて、正しいだけでなく読みやすい議論を書く力を育てる。
• 柔軟で、使い方が明示された構成。 序論には、第3章・第10章・第13章を省略できることを示す依存関係図と、省略可能な節に印をつけた14週間の授業計画が載っている。教員は授業を離散数学寄り（第1〜12章）にも、解析学への準備（第3章以外すべて）にも組み立てられる。
• 豊富な演習と部分的な解答。 各節または各章の終わりに演習があり、奇数番号の問題の解答が巻末に収録されている。独習に向く一方、偶数番号の問題は評価用に残しておける。

短所

• 論理の扱いは非形式的。 第2章は証明を書くのに十分な真理値表、量化子、推論規則を扱うが、形式的な証明体系、一階言語の意味論、公理的集合論は含まない。論理そのものを学びたい読者には別の本が必要である。
• 例が整数に偏っている。 第13章までは、例の多くが偶奇、整除、合同に関するものである。前提知識を低く抑えられる反面、線形代数や解析学に進む学生がそうした分野の証明に触れる機会は比較的少ない。
• 微積分の章はより多くを前提とする。 第13章は微積分の履修を前提とし、極限、連続性、数列と級数を速いペースで進む。解析学風の証明への入門であり、解析学の授業の代わりにはならない。
• ライセンス上の制約。 無料PDFは非営利・改変禁止のクリエイティブ・コモンズ・ライセンスで公開されているため、教員が本文自体を改変・再構成することはできない。

コースにおける位置づけ

この「数理論理学と集合論」のリストの中で、Book of Proof は証明中心の数学への橋渡しテキストであり、Daniel Velleman の How to Prove It（一般に証明戦略への体系的な入門書とされる）と並ぶ位置にある。どちらも最初のテキストとして互いに置き換えて使えるし、一方を他方の追加演習の供給源として使うこともできる。Peter Eccles の An Introduction to Mathematical Reasoning、Allenby の Numbers and Proofs、Liebeck の A Concise Introduction to Pure Mathematics は、一般に数・集合・関数を通じた純粋数学への入門書とされる。Hammack の第I〜III部の技法に慣れた後の次の段階、あるいは併読書として自然である。

コースの論理学の側面については、Hammack は準備であって代わりにはならない。Leary と Kristiansen の A Friendly Introduction to Mathematical Logic や Enderton の A Mathematical Introduction to Logic は形式言語、演繹、完全性を研究するもので、本書が身につけさせる量化子、帰納法、集合記法への習熟をまさに前提としている。学生はまず Hammack を読み、その後これらの論理学のテキストに進むとよい。

本書の使い方

本書は、計算中心の数学から証明中心の数学へ移行する学生――典型的には最初の「証明入門」や移行科目の受講者――のために書かれている。ほぼすべての内容は中等教育の代数で足りる。第13章は微積分の履修を必要とし、他の章の一部の例や演習も微積分や線形代数を使うが、飛ばしてかまわない。

実践的な読み方は著者自身の授業計画に従うものである。第1章と第2章は手早く、しかし丁寧に（論理はあらゆる場面で使われる）、第4〜6章を中核とし、次に第7〜10章、最後に第11・12・14章を読む。第3章は省略可能だが後の演習で使われる例を提供し、第13章は最初の解析学の授業の直前に読むと役に立つ。独習者は、各証明例を読む前に自分で試み、各技法に示された型に従い、各節の演習のいくつかを5.3節の規則に沿って完全な文章で書き、奇数番号の答えを巻末の解答と照らし合わせるとよい。著者のウェブサイトには無料PDFと印刷版の情報も掲載されている。

版と出典

本ガイドは Book of Proof 第3版（Edition 3.4、© 2018 Richard Hammack、CC BY-NC-ND 4.0）に基づいており、著者の公式サイト https://richardhammack.github.io/BookOfProof/ の無料PDFを読んで作成した。第3版の序文、序論（部の構成、依存関係図、授業計画）、目次全体、全14章について各章の冒頭部分、すべての節見出し、主要な証明例（5.3節、6.4節、8.4節、10.3〜10.4節、12.3節、13.2節、14.1〜14.4節を含む）、および結びと解答編の構成を参照している。