01 / 導讀
導讀
引用
Hammack, R. (2018). Book of Proof (3rd ed.). Richard Hammack. Free official edition: https://richardhammack.github.io/BookOfProof/
章節概要
第1章：集合
本書以「全部數學都可以用集合來描述」為出發點，因此第一章先建立此後各章都要用到的語彙：集合建構記號、笛卡兒積、子集合、冪集合、聯集、交集、差集與補集、文氏圖以及帶指標的集合族。本章最後把常見的數系看作集合，並簡要介紹羅素悖論，說明為什麼在「什麼算作集合」的問題上需要謹慎。
第2章：邏輯
本章講解把證明串連起來的邏輯。它定義敘述、「且」「或」「非」等連接詞、條件敘述和雙條件敘述，並用真值表確立笛摩根定律、條件敘述與其逆否敘述等價之類的邏輯等價關係。隨後討論量詞、英語與符號邏輯之間的互譯、量化敘述的否定以及推論規則；結尾一節說明學習邏輯的理由：它確定了「如果……那麼」和「對所有」等措辭的確切意義。
第3章：計數
本章在第三版中有所擴充，討論如何不逐一清點而回答「有多少」。內容依次為列表、乘法原理、加法原理和減法原理、階乘與排列、作為子集合計數的二項式係數、巴斯卡三角形與二項式定理、排容原理、多重集合計數、除法原理與鴿籠原理，最後介紹組合證明——藉由說明兩個式子計數的是同一對象來證明它們相等。導論把本章列為可選，但它為後面的例題和習題提供了素材。
第4章：直接證明
第二部分從「定理」「證明」「定義」的意義講起，並給出後續各章所依賴的精確定義（偶數與奇數、整除、質數、最大公因數等）。對於形如「如果 P，那麼 Q」的敘述，直接證明被表述為一個綱要：假設 P，推理得到 Q，並以整數性質為例反覆練習。本章還說明如何分情況證明，以及如何對類似情況只論證一次。
第5章：逆否證明
本章以第2章建立的邏輯等價為基礎，藉由證明「如果非 Q，那麼非 P」來證明「如果 P，那麼 Q」，並舉出比直接證明簡單得多的例子。它引入模 n 同餘作為新敘述的來源。隨後一節討論數學寫作，列出若干實用規則，例如句子不以符號開頭、獨立展示的公式也要加標點、用文字把符號隔開等。
第6章：反證法
第三種主要技巧是假設敘述為假，再推出荒謬的結論。本章從邏輯上說明這一方法的合理性，並用它證明經典結果，包括 √2 是無理數和質數有無窮多個，然後把它推廣到條件敘述，並與其他技巧結合使用。結尾的建議是先嘗試直接證明或逆否證明，因為反證法證明中常常隱藏著更簡單的逆否證明。
第7章：非條件敘述的證明
第三部分把工具箱擴展到不具有「如果 P，那麼 Q」形式的敘述：「若且唯若」敘述、一組相互等價的敘述、存在性證明以及存在且唯一性證明。本章還對比了構造性證明（給出對象本身）與非構造性證明（不指明對象而證明其必然存在）。
第8章：涉及集合的證明
本章把前面的技巧用於集合論的三項基本任務：證明某個元素屬於某個集合、證明一個集合是另一個集合的子集合、證明兩個集合相等（雙向包含）。一個關於完全數的長例子沿著歸於歐幾里得和歐拉的推理，說明集合相等的論證可以承載實質的數論內容，並涉及梅森質數。
第9章：反駁
本章先把敘述分為已知為真、已知為假和尚未解決三類，然後說明如何證明一個敘述為假。主要工具是反例；本章還討論如何反駁存在性敘述（證明其全稱否定）以及用反證法進行反駁。
第10章：數學歸納法
本章以「前 n 個奇數之和等於 n²」這一猜想為引子，介紹普通歸納法、強歸納法和最小反例證明法，並用這些方法證明算術基本定理（質因數分解的存在性與唯一性），以及關於費氏數的恆等式。
第11章：關係
第四部分從關係的一般理論開始，關係被定義為有序對的集合。本章研究自反性、對稱性和遞移性，等價關係，以及等價類與分割之間的對應。它以構造模 n 整數為示例，最後討論兩個不同集合之間的關係，為函數的定義做準備。
第12章：函數
函數被定義為特殊的關係，從而得到一種超越公式的一般觀點。本章討論嵌射、蓋射與雙射，用函數的語言重述鴿籠原理，並講解合成、反函數以及集合的像與原像。
第13章：微積分中的證明
本章為第三版新增，並明確標為可選，介紹分析學中使用的證明風格。它從三角不等式和極限的 ε–δ 定義出發，證明某些極限不存在，推導極限運算法則，進而討論連續性與導數、無窮遠處的極限以及數列與級數的收斂。本章假定讀者修過微積分。
第14章：集合的基數
最後一章透過雙射定義「基數相等」，並說明無窮集合也有大小之分：整數集合和有理數集合是可數無窮的，而實數集合不是。本章證明任何集合都小於其冪集合，給出判斷可數性的準則，並證明康托爾–伯恩斯坦–施洛德定理，用它說明實數集合與自然數集合的冪集合基數相同；結尾提到連續統假設。
核心概念
第1章：集合
- 集合建構記號：透過元素滿足的條件來描述集合，例如 {x ∈ ℤ : x 是偶數}。
- 冪集合：給定集合的全部子集合組成的集合；含 n 個元素的集合有 2ⁿ 個子集合。
- 羅素悖論：由「所有不屬於自身的集合組成的集合」引出的矛盾，說明並非每一種描述都能定義一個集合。
第2章：邏輯
- 條件敘述：P ⇒ Q 僅在 P 真而 Q 假時為假。
- 邏輯等價：真值表相同的兩個敘述，例如條件敘述與其逆否敘述。
- 量詞的否定：「對所有 x，P(x)」的否定是「存在 x 使 P(x) 不成立」，反之亦然。
第3章：計數
- 乘法原理：若列表分階段構造且每一階段的選擇數固定，則列表總數等於各階段選擇數之積。
- 二項式係數：n 元集合中 k 元子集合的個數，也給出二項式定理中的係數。
- 組合證明：藉由說明等式兩邊計數的是同一組對象來證明恆等式。
第4章：直接證明
- 作為工具的定義：精確的意義規定（例如若 n = 2a 對某個整數 a 成立，則 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，使得當 0 < |x − c| < δ 時 |f(x) − L| < ε，則稱 x → c 時 f(x) → L。
- 三角不等式：|a + b| ≤ |a| + |b|，是極限證明中的基本估計。
第14章：集合的基數
- 基數相等：兩個集合之間若存在雙射，則它們大小相同。
- 可數集合與不可數集合：與 ℕ 等大（或有限）的集合，以及像 ℝ 這樣更大的無窮集合。
- 康托爾–伯恩斯坦–施洛德定理：兩個集合之間若有雙向的嵌射，則必存在雙射。
評析
優點
- 按技巧編排。 第二、三部分把直接證明、逆否證明、反證法、「若且唯若」、存在性、反駁和歸納法逐一分開，每種方法先給出證明綱要再舉例。初學者很容易判斷自己要證明的是哪一類敘述、應當嘗試哪種範本。
- 既重邏輯也重寫作。 5.3 節關於數學寫作的規則，以及 6.4 節「優先選擇更簡單方法」的建議，都把證明當作寫給別人讀的文本。搭配細緻的範例證明，這有助於學生寫出不僅正確而且易讀的論證。
- 結構靈活、說明清楚。 導論給出依賴關係圖，表明第3、10、13章可以省略，還給出標明可選小節的十四週教學進度表。教師可以把課程導向離散數學（第1–12章），也可以導向分析學預備（除第3章外全部）。
- 習題豐富並附部分解答。 每節或每章末都有習題，書末給出奇數題解答，既便於自學，也把偶數題留作評量之用。
局限
- 邏輯部分較為非形式化。 第2章講授的真值表、量詞和推論規則足以支撐寫證明，但沒有形式證明系統、一階語言的語意或公理化集合論；對邏輯本身感興趣的讀者需要另找教科書。
- 例子偏重整數。 在第13章之前，大多數例子都圍繞奇偶性、整除和同餘。這降低了先修要求，但將要學習線性代數或分析的學生在這些領域裡見到的證明相對較少。
- 微積分一章要求更高。 第13章假定讀者修過微積分，並較快地講完極限、連續性、數列與級數；它是分析式證明的入門，而不能取代分析課程。
- 授權限制。 免費 PDF 採用非商業、禁止改作的創用 CC 授權，教師不能改編或重組正文。
在課程中的定位
在這份「數理邏輯與集合論」書單中，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 第一至第三部分的技巧之後，它們是自然的後續讀物或搭配讀物。
就課程的邏輯部分而言，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 第三版（Edition 3.4，© 2018 Richard Hammack，CC BY-NC-ND 4.0），閱讀的是作者官方網站 https://richardhammack.github.io/BookOfProof/ 提供的免費 PDF。導讀參考了第三版序言、導論（各部分結構、依賴關係圖和教學進度表）、完整目錄，以及全部十四章的開篇、所有小節標題和主要範例證明（包括 5.3、6.4、8.4、10.3–10.4、12.3、13.2 和 14.1–14.4 節），並參考了結語和解答部分的編排。