01.3 證明方法學：直接、反證、歸納與對角線法#

1. 證明是什麼，為什麼需要方法學#

一個證明是：從公理與已證定理出發，依有效推論規則（01.1 節的 Modus Ponens 等）逐步推出結論的有限序列。Gödel 完備性定理（01.2 節）保證：一階邏輯中凡是語意成立的，就存在這樣的序列——證明的存在性沒問題，難的是「如何找到」。證明方法學就是前人累積的「尋找策略」。

歷史上，歐幾里得《幾何原本》（約 BC 300）首創公理化體系；十九世紀末 Hilbert 重整幾何公理後更進一步提出綱領：把整個數學放進一個一致、完備、可機械判定的形式系統。每一種證明方法的發明，都是為了對付某類「用先前方法證不出」的定理——本節將沿這條動線介紹四種基本方法，再深入兩種改寫數學史的超級技術：對角線法與自指構造。

2. 直接證明與條件式#

方法 2.1（直接證明）：證明 $p \to q$ 時，假設 $p$ ，經有限步推導得出 $q$ 。

定理 2.2：兩奇數之和為偶數。

證明：設 $m, n$ 為奇數，則存在整數 $a, b$ 使 $m = 2a+1$ 、 $n = 2b+1$ 。於是 $$m + n = 2(a+b+1)$$ 由偶數定義（形如 $2k$ ）知 $m+n$ 為偶數。 $\blacksquare$

直接證明的技術核心是從定義出發展開符號：把「奇數」翻成 $2a+1$ ，把「偶數」翻成 $2k$ ，再代入計算。多數代數類定理走這條路。

範例 2.3（含量詞的結構，銜接 01.2）：證明「任兩實數間存在無理數」。取 $x < y$ ，若 $y - x > \sqrt{2}$ 則 $x + \sqrt{2}$ 即為所求；否則 $y - x > \sqrt{2}/2$ ，取 $x + \sqrt{2}/2$ 。此證明展示 $\forall x \forall y\, \exists z$ 型敘述的證明範式：**先接收任意 $x, y$ ，再構造（而非僅斷言） $z$ **。

3. 反證法：從矛盾中獲利#

方法 3.1（反證法，Proof by Contradiction / 歸謬法）：要證 $p$ ，先假設 $\neg p$ ，推得矛盾（ $q \land \neg q$ ），由矛盾律知 $\neg p$ 不成立。

它的邏輯根據是： $(\neg p \to (q \land \neg q)) \to p$ 為恆真式（可用 01.1 節真值表驗證）。哲學上這依賴排中律 $p \lor \neg p$ ——直覺主義者（Brouwer）不接受非構造性的反證，他們認為「證明不存在矛盾」不等於「構造出對象」。這條異議在計算機科學裡獲得意想不到的支持：Curry–Howard 對應下，直覺主義證明恰好對應可執行程式，而經典反證法對應的程式不能直接求值。

定理 3.2（ $\sqrt{2}$ 是無理數；古希臘的震撼）：設 $\sqrt{2} = a/b$ ， $a, b$ 互質。則 $a^2 = 2b^2$ ，故 $a$ 為偶，寫 $a = 2c$ ；代入得 $2c^2 = b^2$ ，故 $b$ 亦為偶——與 $a, b$ 互質矛盾。 $\blacksquare$

傳說 Hippasus 因發現不可公度長而被 Pythagoras 學派投入海中——第一次「數學危機」。這個證明的策略值得背誦：假設最簡形式存在，推出更簡形式也存在，得無窮下降矛盾。Fermat 的無窮下降法與此同源。

範例 3.3（存在無窮多質數；歐幾里得 BC 300）：設質數只有 $p_1, \dots, p_k$ 。令 $N = p_1 p_2 \cdots p_k + 1$ 。 $N > 1$ 必有質因數 $p$ ；但 $p$ 若是 $p_i$ 之一，則 $p \mid N$ 且 $p \mid p_1\cdots p_k$ ，得 $p \mid 1$ ，矛盾。故恆有清單之外的新質數。 $\blacksquare$

# 歐幾里得構造的程式版：用前 k 個質數製造不在清單中的新質因數
from math import prod

def new_prime(primes):
    N = prod(primes) + 1
    for d in range(2, N + 1):
        if N % d == 0 and all(d % p for p in primes):
            return d
print(new_prime([2, 3, 5, 7, 11]))  # 13，清單之外的質數

注意反證法的建設性一面：歐幾里得的論證不只是「質數有限會矛盾」，還給出由舊質數找新質數的演算法。

4. 數學歸納法#

方法 4.1（數學歸納法）：設 $P(n)$ 為關於自然數的命題。若 1. （基底） $P(0)$ 成立， 2. （歸納步）對所有 $k$ ， $P(k) \to P(k+1)$ ，

則對所有 $n$ ， $P(n)$ 成立。

證明原理：歸納法依賴良序原理（自然數的非空子集有最小元）。假設有某 $n$ 使 $P(n)$ 假，則 $\{n : \neg P(n)\}$ 非空，有最小元 $m$ ； $m \ne 0$ （基底成立），故 $m = j+1$ 且 $P(j)$ 真，由歸納步 $P(m)$ 真——矛盾。 $\blacksquare$

強歸納法：歸納步改為「 $\forall k{<}n\, P(k) \to P(n)$ 」。適用於 $P(n)$ 依賴所有較小情形的問題（如質數分解、Fibonacci 性質）。

定理 4.2： $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ 。

證明： $n=1$ ： $1 = \frac{1 \cdot 2}{2}$ 。設對 $n$ 成立，則 $$\sum_{i=1}^{n+1} i = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$$ 恰為 $n+1$ 時的公式。 $\blacksquare$

常見錯誤警示：只驗基底不證歸納步（如「所有馬同色」謬誤——歸納步在 $n=1\to 2$ 時失效）；只證歸納步不驗基底（遞迴沒有終止條件）。歸納法與遞迴程式、結構歸納法（對樹、鏈表等歸納）完全平行，是程式正確性證明的基礎：

def tri(n):                       # 對應定理 4.2 的「公式」
    return n * (n + 1) // 2

def tri_loop(n):                  # 對應「定義」
    return sum(range(1, n + 1))

# 歸納式驗證：基底 + 逐步檢查（數值版歸納步）
for n in range(1, 1000):
    assert tri(n) == tri_loop(n)
    assert tri(n + 1) - tri(n) == n + 1   # 歸納步的代數恆等式

5. Pigeonhole：存在性證明的效率之王#

定理 5.1（鴿籠原理）：把 $n+1$ 隻鴿子放進 $n$ 個籠子，必有某籠至少兩隻。

形式化：不存在從 $\{1,\dots,n+1\}$ 到 $\{1,\dots,n\}$ 的單射。這條原理看似膚淺，卻是非構造性存在證明的典範：它保證某物存在，卻不告訴你在哪。歷史上它與 Diophantus（三世紀）的問題遙相呼應：丟番圖研究「整數解的存在性」；而鴿籠原理正是證明整數解存在的最低門檻工具——存在性有時根本不需要構造。

範例 5.2：任取 $n+1$ 個整數，必有兩數之差可被 $n$ 整除。

證明：整數除以 $n$ 的餘數只有 $n$ 種（ $0$ 到 $n-1$ ）。 $n+1$ 個數、 $n$ 種餘數，由鴿籠原理必有兩數 $a, b$ 同餘，即 $n \mid (a - b)$ 。 $\blacksquare$

範例 5.3（丟番圖式應用）：證明對任意 $n$ ，存在 $n$ 的某個倍數，其十進表示只含 $0$ 與 $7$ 。

證明：考慮 $7, 77, 777, \dots, \underbrace{7\cdots7}_{n+1}$ 共 $n+1$ 個數。它們除以 $n$ 的餘數必有兩個相同（鴿籠），其差形如 $77\cdots700\cdots0$ ，恰為所求倍數。 $\blacksquare$

鴿籠原理也直接導出重要極限：任何比較排序需要 $\Omega(n \log n)$ 次比較—— $n!$ 種排列要被二叉比較區分， $\log_2 n! = \Theta(n\log n)$ 。存在性的下界證明，往往就是鴿籠。

6. 對角線法：Cantor 的超級武器#

方法 6.1（Cantor 對角線法，1891）：證明 $\mathbb{R}$ 不可數——不存在把實數排成一列的方法，使每個實數恰出現一次。

證明（反證 + 對角線）：假設 $(0,1)$ 的實數可列為 $r_1, r_2, r_3, \dots$ 。寫出小數展開：

\[ \begin{aligned} r_1 &= 0.\,\mathbf{d_{11}}\, d_{12}\, d_{13} \cdots\\ r_2 &= 0.\, d_{21}\, \mathbf{d_{22}}\, d_{23} \cdots\\ r_3 &= 0.\, d_{31}\, d_{32}\, \mathbf{d_{33}} \cdots \end{aligned} \]

構造新數 $d = 0.\,e_1 e_2 e_3\cdots$ ，其中 $e_i = (d_{ii} + 1) \bmod 10$ （避免 $9$ 歧義）。則 $d$ 與每個 $r_i$ 在第 $i$ 位不同，故 $d$ 不在列表中——矛盾。 $\blacksquare$

對角線法是構造性反證的極致：它不只說「排不完」，還明確製造漏網之魚。1891 年 Cantor 用它證實了自己 1874 年的結果：無限有大小之分。這條方法在後世不斷重生：

Turing（1936）：對角線法證明停機問題不可判定——不存在判定任意程式是否停機的演算法。
Gödel（1931）：對角線技術把「本語句不可證」編碼成算術語句 $G$ ，證明任何一致且含算術的系統中， $G$ 真而不可證——Hilbert 綱領的完備性目標自此坍塌。
計算複雜性：時間階層定理仍用對角線法分離複雜度類。

# 對角線法的模擬：給定「聲稱完備」的列表，製造漏網實數
def diagonal_escape(rows, width=8):
    # rows[i][j] 為第 i 個數的第 j 位小數數字
    return [((rows[i][i] + 1) % 10) for i in range(width)]

rows = [[1,4,1,4,2,1,3,5],
        [1,7,3,2,0,5,0,8],
        [4,1,4,2,1,3,5,6],
        [2,7,1,8,2,8,1,8]]
print("".join(map(str, diagonal_escape(rows))))
# 此數與每一列在第 i 位都不同 —— 不在列表中

與鴿籠的對照：鴿籠證「放不下的存在」（有限、計數）；對角線證「列不完的存在」（無限、自指）。兩者都是非構造性或半構造性存在證明，但後者開啟了無限基數理論（02.3 節）。

7. 唯一存在與證明策略選擇#

證明「存在唯一的 $x$ 使 $P(x)$ 」的標準兩段式：

\[\exists x\, P(x) \quad\land\quad \forall y \forall z\, \big(P(y) \land P(z) \to y = z\big)\]

範例 7.1：證明方程 $2x + 6 = 10$ 有唯一實數解。存在性： $x = 2$ 滿足。唯一性：若 $2y = 4$ 且 $2z = 4$ ，則 $2y = 2z$ ，兩邊除以 $2$ 得 $y = z$ 。 $\blacksquare$

策略總表：

目標類型	首選方法	備註
$\forall x\, (P(x) \to Q(x))$	直接證明	從定義展開
$\neg \exists x\, P(x)$	反證法	假設存在推矛盾
$\forall n \in \mathbb{N}\, P(n)$	數學歸納	先驗基底！
$\exists x\, P(x)$ （不要求構造）	鴿籠原理	存在但難定位
「不可數」「不可判定」	對角線法	製造漏網之魚
唯一存在	存在 + 兩者相等	兩段式

8. 習題#

直接證明：若 $n$ 為奇數，則 $n^2 \equiv 1 \pmod 8$ 。
用反證法證明 $\sqrt{3}$ 是無理數（模仿定理 3.2，注意 $3 \mid a^2 \Rightarrow 3 \mid a$ 需要質數性質）。
用強歸納法證明：每個 $n \ge 2$ 可寫成質數之積。
證明：任意 13 人中，必有兩人生於同月。（這是鴿籠的「 $n$ 與 $n+1$ 」原始形式嗎？寫出鴿數與籠數。）
用對角線法證明： $[0,1]$ 上所有只在 $\{0,1\}$ 取值的數列構成的集合不可數。（提示：對第 $i$ 個數列，翻轉其第 $i$ 項。這是 Cantor 定理的雛形，直接通往 02.3 節。）
模仿 Gödel 的自指思路（不必形式化）：構造一句中文句子，使其為真當且唯當它不可被證明。討論：這句話能證明嗎？

9. 小結與下一步#

四種基本方法各有戰場：直接（代數恆等）、反證（不存在性）、歸納（自然數全體）、鴿籠（無構造的存在）。
反證法依賴排中律；直覺主義的異議在 Curry–Howard 對應中轉譯為「證明即程式」的構造性要求。
對角線法是數學史的轉折點：Cantor 1891 分層無限 → Turing 1936 停機問題 → Gödel 1931 不完備定理，一脈相承。
證明方法的選擇由命題的邏輯形狀決定——先看量詞結構，再選策略。

下一步：對角線法證明「無限也有大小」的前提，是先說清楚「大小」如何比較——這需要集合論的語言。02.1 節回到 Boole、Frege 想用的「樸素集合論」，親眼目睹 Russell 悖論如何把整座大廈逼到重構，並引出 ZFC 公理體系。

目標類型	首選方法	備註
\(\forall x\, (P(x) \to Q(x))\)	直接證明	從定義展開
\(\neg \exists x\, P(x)\)	反證法	假設存在推矛盾
\(\forall n \in \mathbb{N}\, P(n)\)	數學歸納	先驗基底！
\(\exists x\, P(x)\) （不要求構造）	鴿籠原理	存在但難定位
「不可數」「不可判定」	對角線法	製造漏網之魚
唯一存在	存在 + 兩者相等	兩段式