證明診斷、依賴關係與唯一性

1. 檢查依賴關係，而不只看最後一行

審查一份證明時，可以依次問：

1. 量化的對象是甚麼，定義域與量詞次序是甚麼？
2. 哪些事實是已知假設，哪些是待證結論？
3. 所構造的每個表達式是否在所述定義域上存在？
4. 每一步推論是否由先前已建立的事實推出？
5. 得到候選對象後，是否將其代回以證明存在性？
6. 聲稱唯一時，怎樣才算同一對象：完全相等、不計次序的因子，還是同一個等價類？

反例否定命題；找到第一個無效推論則診斷證明。二者都重要，但回答不同問題。正確命題也可能有錯誤證明；發現論證有誤，本身並不使結論為假。

例題：奇偶性證明中的循環。 為證明“若 $n^2$ 為偶數，則 $n$ 為偶數”，學生寫：“令 $n=2k$，則 $n^2=4k^2$，所以結論成立。”第一行假設了待證結論：尚未證明平方為偶數的任意整數等於某個整數的兩倍。該計算實際證明的是反向命題：$n$ 為偶數蘊含其平方為偶數。

正確修復可用逆否命題：若 $n$ 為奇數，則對某整數 $k$ 有 $n=2k+1$，故 $n^2=2(2k^2+2k)+1$ 為奇數。因此平方為偶數時，$n$ 不可能為奇數。這裡的表示來自已給假設，而非所需結論。

例題：求候選值不等於構造解。 從 $ax=b$ 形式上相除得到 $x=b/a$，但只有 $a\ne0$ 時才得到候選值；代回後才能證明它是解。為證唯一性，若 $ax=ay=b$，相減得 $a(x-y)=0$，再消去非零的 $a$。若 $a=0$，結論分兩種：$b\ne0$ 時無解，$b=0$ 時每個實數都是解。沒有說明就除以 $a$ 會漏掉這兩種情況。

2. 見證對象的依賴關係是數學內容

在實數範圍內，$\forall x\exists y:y>x$ 允許見證對象 $y=x+1$ 依賴 $x$，卻不能證明 $\exists y\forall x:y>x$。審查時可畫箭頭，表示後續選擇允許依賴哪些先前選擇。存在量詞的見證對象可以使用已選輸入，不能使用只在其後才量化的變量。

稍不直觀的例子。 令 $A=(0,1]$；對每個正整數 $n$，當 $x=1/n$ 時定義 $f_n(x)=n$，其他處為零。每個固定的 $n$ 對應的函數都被 $n$ 所界。每個固定的 $x$ 對應的數列 $f_n(x)$ 隨 $n$ 變化也有界：至多一項非零。但不存在對所有 $n$ 和 $x$ 都有效的共同界，因為 $f_n(1/n)=n$。

因此 $\forall n\exists M_n\forall x:|f_n(x)|\le M_n$ 與 $\forall x\exists M_x\forall n:|f_n(x)|\le M_x$ 都成立，而 $\exists M\forall n\forall x:|f_n(x)|\le M$ 不成立。若取上確界時沒有證明它有限，就掩蓋了缺失的一致界。這個邏輯例子沒有假設，也不需要連續性。

3. 歸納法需要每一個遞推步驟

考慮錯誤斷言：“每個有限非空實數集合的元素都相等。”一個所謂的歸納證明說：單元素情形成立；對一個 $(n+1)$ 元集合，刪除一元素得到 $n$ 個相等元素，再刪除另一個得到另外 $n$ 個相等元素，利用兩組重疊可使兩個公共值相同。

當 $n\ge2$ 時，兩個 $n$ 元子集確實重疊；但關鍵的第一步 $n=1$ 中，一個兩元素集合的兩個單元素子集沒有交集，無法用共同元素連接它們的值。故沒有對每個所需的 $n\ge1$ 證明歸納蘊涵。反例 $\{0,1\}$ 證實斷言為假，而空交集指出具體失效的步驟。

這不同於強歸納：在歸納步驟中假設所有較小情形成立是合法的，但仍須有效的基礎情形及覆蓋每個下一指標的證明。遞歸構造必須下降到已建立的基礎情形；只說“更小”而不說明遞減的正整數，不能證明終止。

4. 質因數分解的規範化

這裏取 $\mathbb N=\{0,1,2,\ldots\}$。

定理

除法算法

設 $a,b\in\mathbb Z$ 且 $b\ne0$。則存在唯一整數 $q,r$ 使得

$$a=bq+r,\qquad 0\le r\lt|b|.$$

$q$ 稱為商，$r$ 稱為餘數。

條件 $0\le r\lt|b|$ 不是附加裝飾，而是唯一性的核心。例如

$$17=5\cdot3+2$$

符合除法算法；但

$$17=5\cdot2+7$$

不符合，因為餘數 $7$ 不小於 $5$。

先證明存在性。設 $a\ge0$、$b>0$，考慮

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}.$$

因為 $a\in S$，良序原理給出最小成員 $r=a-bq$。若 $r\ge b$， 則 $r-b=a-b(q+1)$ 是更小的非負成員，矛盾。因此 $0\le r\lt b$。 若 $a\lt0$、$b>0$，則 $A=a+(-a)b=(-a)(b-1)$ 非負。 用已證情形寫成 $A=bQ+r$，整理得 $a=b(Q+a)+r$，餘數範圍不變。 若 $b\lt0$，先用正除數 $B=|b|$，再把商 $Q$ 換成 $-Q$。 所有符號情形都不需要負餘數。

再證明唯一性。設 $a=bq+r=bq'+r'$，兩個餘數都在規定範圍內。 於是 $b(q-q')=r'-r$，但 $|r'-r|\lt|b|$。$b$ 的非零整數倍 絕對值至少是 $|b|$，故 $r'=r$。再由 $b\ne0$ 得 $q'=q$。 嚴格上界保證唯一性；僅要求餘數非負並不足夠。

定理

最大公因數的一步不變性

若 $a=bq+r$，則

$$\gcd(a,b)=\gcd(b,r).$$

證明: 保留整個共同因數集合

目標是證明兩個最大公因數相等。先證明更強的中間命題，論證會更直接： 整數 $h$ 同時整除 $a,b$，當且僅當它同時整除 $b,r$。 正向用 $r=a-bq$，反向用 $a=bq+r$，兩者都用整數線性組合的整除性質。

輸入不同時為零時，兩個因數集合相同，所以最大元素相同。若 $a=b=0$， 則 $r=0$，兩邊按約定都是 $0$。這個恆等式本身不要求餘數範圍； 餘數範圍的作用是保證算法向前推進。

概念視角算法

不變量與遞減計算

每次替換 $(a,b)\mapsto(b,r)$，最大公因數保持不變，餘數則變小。 兩者各有作用：不變性保證最後答案就是原本的最大公因數，嚴格遞減則保證 計算會結束。先取輸入的絕對值，把較大的正數放在前面；若另一輸入是零， 立即停止。其餘每次帶餘除法都使用正除數。

算法必然停止，因為餘數形成嚴格遞減的非負整數列：

$$r_1>r_2>r_3>\cdots\ge0.$$

非負整數不可能無限地嚴格遞減。

倒代也可整理成向前更新的係數。對正輸入設 $r_0=a$、$r_1=b$， 保存 $r_k=s_ka+t_kb$，初始係數為 $(s_0,t_0)=(1,0)$、 $(s_1,t_1)=(0,1)$。若 $r_{k+2}=r_k-q_{k+1}r_{k+1}$，則

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

代入兩個已知線性組合即可證明更新式。係數始終是整數，最後非零餘數那一行 便給出最大公因數所需的係數。

定理

Bézout 恆等式

對任意整數 $a,b$，存在整數 $x,y$ 使得

$$\gcd(a,b)=ax+by.$$

對帶符號的非零輸入，先用 $|a|,|b|$ 計算，再把原本符號吸收到係數中。 若一項為零，用 $|a|=a\operatorname{sgn}(a)$ 或 $b$ 的對應等式； 若兩項皆零，取 $x=y=0$。這樣便證明恆等式的全部情形。

輸入不同時為零時，最大公因數也是最小的正整數線性組合。恆等式保證它 確實是一個組合；其他正組合都是它的正倍數，不可能更小。若輸入是 $(0,0)$， 則沒有正組合。

定理

Euclid 引理

設 $p$ 是質數。若 $p\mid ab$，則 $p\mid a$ 或 $p\mid b$。

若 $p\nmid a$，則 $\gcd(a,p)=1$，所以存在整數 $m,n$ 使

$$am+pn=1.$$

兩邊乘以 $b$ 得

$$abm+pbn=b.$$

因為 $p\mid ab$，左邊兩項都被 $p$ 整除，所以 $p\mid b$。

定理

算術基本定理

每個大於 $1$ 的正整數都可以寫成質數乘積，而且這個乘積在不計因子次序下唯一。

存在性仍然來自最小反例法。若存在最小的、大於 $1$ 且不能寫成質數乘積的整數，它不可能是質數，因此可分解成兩個更小的因數；但這兩個較小因數已經可以分解成質數乘積，矛盾。

唯一性使用 Euclid 引理。若

$$p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

則 $p_1$ 整除右邊乘積，所以 $p_1$ 必整除某個質因數 $q_j$，從而 $p_1=q_j$。消去後重複同樣論證。

反覆使用 Euclid 引理，可以從整除有限乘積推到整除其中一個因子。 消去過程不能只耗盡一邊的質數：否則 $1$ 會等於非空質數乘積，而該乘積 大於 $1$。因此兩邊因子數相同，計入重數後的因子也相同。

對負的非零整數，先提出總因子 $-1$，再分解其正的絕對值。一對應空的質數乘積，零沒有這種質因數分解；這些邊界情形須明確處理。

5. 最簡有理數表示的唯一性

設整數 $a,c$ 和正整數 $b,d$ 滿足 $a/b=c/d$ 與 $\gcd(a,b)=\gcd(c,d)=1$，則 $a=c$ 且 $b=d$。

證明。 交叉相乘得 $ad=bc$。由 $\gcd(a,b)=1$，Bézout 恆等式給出整數 $u,v$ 使 $ua+vb=1$。兩邊乘以 $d$ 得 $d=uad+vbd=ubc+vbd$，說明 $b\mid d$。交換兩個分數同理得到 $d\mid b$。兩個分母均為正，所以它們相等；交叉乘積等式再給出分子相等。此論證包含分子為零的情形：互素性迫使其正分母為一。

存在性是另一項證明。從任意分母非零的整數分數出發，先把分母變為正，再用正的最大公因數同時除分子和分母。因最大公因數整除兩者，所得商仍是整數，值不變，也不再有公因數。完成此構造後，唯一性定理才使“最簡分數”有確切含義。

分級證明練習

1. 正向與逆向。 對整數 $n$，證明 $n$ 為奇數當且僅當 $n^2\equiv1\pmod8$。
2. 修復。 在實數範圍診斷“若 $ab=ac$，除以 $a$ 得 $b=c$”。陳述並證明正確的定理，分類例外情形。
3. 一致界。 對上述函數 $f_n$，寫出存在共同界的否定，並按所需量詞次序構造見證。
4. 存在與唯一。 解釋為甚麼質因數唯一性論證本身不能證明每個 $n\ge2$ 都存在質因數分解，並完整給出強歸納的存在性論證。
5. 規範化。 若分母允許為負，最簡分數的唯一性哪裡失效？陳述並證明適當的修正唯一性描述。
6. 單側逆。 若 $f\circ g$ 是 $Y$ 上的恆等映射，證明 $f$ 映滿 $Y$ 且 $g$ 單射。$f$ 必須單射嗎？$g$ 必須映滿其另一個已聲明集合嗎？給出驗證過的反例。

完整解答

1. 若 $n=2k+1$，則 $n^2=4k(k+1)+1$。相鄰整數 $k,k+1$ 之一為偶數，因此 $8\mid4k(k+1)$ 且 $n^2\equiv1$。反過來，該同余式使 $n^2$ 為奇數。偶整數的平方為偶數，故 $n$ 不能為偶數，只能是奇數。兩個方向均已證明。
2. 相除需要 $a\ne0$；在該假設下乘以 $1/a$ 得 $b=c$。若 $a=0$，前提變為 $0=0$，對 $b,c$ 沒有限制；例如 $b=0,c=1$ 否定無條件斷言。第一個無效步驟是除以未經驗證為非零的數。
3. 否定式是 $\forall M>0\exists n\ge1\exists x\in(0,1]:|f_n(x)|>M$。給定 $M$，取整數 $n>M$，再取 $x=1/n$，於是 $|f_n(x)|=n>M$。整數依賴所給的界，點依賴該整數；不需要同一個固定點擊敗所有界。
4. 唯一性從兩個已給分解出發，不能構造出其中任何一個。存在性以 $n=2$ 為基礎，它本身是質數。假設從二到 $n-1$ 的每個整數均為質數乘積。若 $n$ 是質數即完成；否則有 $n=ab$，其中 $2\le a,b<n$。歸納假設給出二者的質數分解，合併即得到 $n$ 的分解。每次遞歸使用更小的正整數，強歸納證明所有情形。
5. 即使分子、分母互素，$a/b=(-a)/(-b)$ 仍給出兩種符號選擇，例如 $1/2=(-1)/(-2)$。把兩個分母規範化為正後，由定理得到唯一的規範對。因此不規定符號時，兩對要麼相等，要麼同時取負。反之，同時取負總保持分數值和互素性，故這正是全部歧義。
6. 對任意 $y\in Y$，有 $y=f(g(y))$，故 $f$ 映滿。若 $g(y_1)=g(y_2)$，作用 $f$ 得 $y_1=y_2$，所以 $g$ 單射。其他結論不一定成立：令 $f:\mathbb R\to[0,\infty)$ 為 $f(x)=x^2$，令 $g:[0,\infty)\to\mathbb R$ 為 $g(y)=\sqrt y$。則 $f\circ g$ 是恆等映射，但 $f(1)=f(-1)$，且 $g$ 從不取負值。因此 $f$ 不單射，$g$ 不映滿 $\mathbb R$。

總結與術語

循環論證假設了它要證明的結論。依賴關係記錄一次選擇可以使用哪些先前數據。規範化消除允許的歧義，例如因子次序或分母符號。不計次序的唯一性不同於有序列表唯一性。應定位第一個無效推論，再修復確切缺失的條件或構造；有說服力的最後一行不能取代這些步驟。