# OCME 第5冊 集合、邏輯與證明 · v0.2

網站閱讀版 · 繁體中文

![圓形等距共同署名，不分先後。](assets/signature-circle.svg)

本作採非排序共同署名。排列位置不代表先後、地位、貢獻比例或工作分工；未列名不表示不存在，也不表示未曾參與。

出版／營運單位：EVEMISS TECHNOLOGY CO., LTD.

最終權利與授權聲明另行確認，不由署名排版或出版單位名稱代為決定。

# 第1章 定義、假設與結論

## 1.1 從算出答案到說明理由

第二冊練習過合法的式子變形。本冊再向前一步：先說清楚談哪些對象、已經知道什麼，以及要證明什麼。證明不是把幾個看起來正確的式子排在一起，而是讓每一步都能回到假設、定義或已經建立的結果。

本章完成後，你應能分開定義、例子與命題，辨認假設和結論，並在動手之前固定論域。先備只需第二冊的基本代數。全書採古典邏輯；ℕ={0,1,2,…}，正整數寫成ℕ₊={1,2,3,…}。

## 1.2 定義給名稱 命題提出主張

定義約定一個詞怎麼使用。例如「整數n是偶數」的意思是「存在整數k，使n=2k」。這不是先計算幾個數再猜出來的規律，而是本書使用「偶數」的資格。

例子展示某個對象符合定義。例如6=2·3，所以6是偶數。命題則對某個範圍提出可判定真假的主張，例如「任意兩個偶數的和仍是偶數」。一般命題需要一般理由；展示6+8=14，只處理了一組輸入。

「設n為整數」固定對象範圍；「若n為偶數」增加假設；「則n²為偶數」是要得到的結論。把這三件事分開，才知道允許使用哪些理由。

![先固定整數論域，再由偶數假設推向平方仍為偶數的結論。](assets/f01-statement-structure.svg)

## 1.3 例題

### 例題1 把定義用在指定整數

判斷−8是否為偶數。偶數定義要求的是整數見證，不要求見證為正數。取k=−4，便有−8=2·(−4)，所以−8是偶數。

回查時同時核對兩件事：−4確實是整數，等式也確實成立。只寫「因為可以除以2」容易漏掉商必須是整數；例如1也能在實數中除以2，卻不是偶數。

### 例題2 從假設走到結論

證明偶整數n的平方是偶數。由假設及定義，存在整數k，使n=2k。代入得到n²=4k²=2(2k²)。

整數乘法封閉，所以2k²仍是整數。把它當作新見證，正好符合偶數定義。結論適用於所有符合假設的n，不只適用於某一次代入。

### 例題3 同一式子在不同論域的真假

考察「每個x都有x²≥x」。在ℕ中，x=0或1時取等號；x≥2時，x(x−1)≥0，故x²−x≥0。這就覆蓋所有自然數。

若論域改成ℝ，取x=1/2，便有x²=1/4<1/2，所以原句不成立。反例沒有推翻自然數版本，因為1/2不屬於那個版本的論域。

### 例題4 定義中的兩個方向

正整數p稱為質數，若p>1，且p的正因數只有1和p。判斷1與2：1不符合p>1，所以不是質數；2>1，而其正因數正是1、2，所以是質數。

「只有兩個正因數」在這裡是可檢查的特徵；不能把「看起來不能再分」當作定義。定義也不保證符合資格的對象一定存在，存在性仍需例子或證明。

![定義說明資格，例子給出對象，命題提出需要理由的主張。](assets/f02-definition-example-claim.svg)

## 1.4 讀證明時的三個問題

先問這一步使用哪個條件，再問新引入的符號屬於哪個集合，最後問所得結論是否真的就是原目標。例題2裡的2k²不是隨手改名，而是交給偶數定義的整數見證。

本書用「若P，則Q」表示P⇒Q；用「P若且唯若Q」表示P⇔Q，後者包含兩個方向。此時先認得形式，第4章再完整處理連接詞。證明一個方向，不能自動宣稱兩個方向都成立。

## 1.5 練習

1. **B05-C01-Q01** 用偶數定義判斷−14，寫出整數見證。
2. **B05-C01-Q02** 用偶數定義判斷0，說明見證的資格。
3. **B05-C01-Q03** 證明：若整數a、b均為偶數，則a+b為偶數。
4. **B05-C01-Q04** 指出「若整數n是4的倍數，則n是偶數」的論域、假設與結論，並證明它。
5. **B05-C01-Q05** 「每個x都有x²>0」在ℝ上是否成立？給出合格理由。
6. **B05-C01-Q06** 「每個非零實數x都有x²>0」與上一題有何差別？證明修正版。
7. **B05-C01-Q07** 已知2+4、4+6、6+8都是偶數，是否已證明任意兩個偶數的和是偶數？補出所缺理由。
8. **B05-C01-Q08** 依正整數質數定義，判斷9與11。
9. **B05-C01-Q09** 「若x²=1，則x=1」在ℝ與[0,∞)上分別真假如何？
10. **B05-C01-Q10** 有人寫「因為a+b是偶數，所以a、b都是偶數」。檢查這是否是第3題的同一方向。

## 1.6 完整解答

### Q01

取整數k=−7，便有−14=2k。見證在要求的整數範圍內，故−14是偶數。負號不妨礙使用定義。

### Q02

取k=0，則0=2·0，而0是整數，所以0是偶數。偶數定義沒有「必須大於0」這項限制，不能自行補上。

### Q03

由假設，存在整數r、s，使a=2r、b=2s。因此a+b=2r+2s=2(r+s)。整數加法封閉，r+s是整數，故a+b是偶數。這個見證同時處理所有符合假設的a、b。

### Q04

論域是整數n；假設是存在整數k使n=4k；結論是n為偶數。由n=4k=2(2k)且2k∈ℤ，便得到符合偶數定義的見證。證明沒有使用結論當前提。

### Q05

不成立。0屬於ℝ，而0²=0，並不大於0，所以0是合格反例。指出某個非零數平方為正，無法補救原句對0的失敗。

### Q06

修正版排除了上一題的反例，但仍需證明其餘輸入。非零實數x不是正就是負；x>0時x²>0，x<0時−x>0且x²=(−x)²>0。兩種情形覆蓋全部非零實數。

### Q07

三次計算只證明三組例子。一般理由是把任意兩個偶數寫成2r、2s，其中r、s為整數，然後將和整理成2(r+s)。既然見證不依賴某組特定數值，才可得到任意兩個偶數的結論。

### Q08

9的正因數含3，而3既不是1也不是9，所以9不是質數。11大於1；若11有非平凡正因數，其一不大於√11<4，只需檢查2、3，兩者均不整除11，故11只有1、11兩個正因數。這裡有限檢查的範圍來自因數成對的理由，不是隨意只試兩個數。

### Q09

在ℝ上不成立：x=−1滿足x²=1卻不等於1。在[0,∞)上，由x²−1=(x−1)(x+1)=0，且x+1>0，可得x−1=0，故x=1。論域限制提供了後一個論域版本所需的資格。

### Q10

不是同一方向。第3題從「兩者都偶」推出「和偶」；這裡反過來，由結論猜回原假設。取a=b=1，和為2卻兩者都不是偶數，便推翻反向敘述。原方向仍然正確。

## 1.7 本章回看

把定義展開，通常就能看見應該構造的見證。進入下一章時，仍保留這個習慣：符號的資格先於符號的操作。


# 第2章 集合與集合運算

## 2.1 元素與集合不是同一層

集合描述一群可辨識的對象。寫x∈A表示x是A的元素；寫A⊆B表示A的每一個元素也都在B中。前者在談一個對象是否屬於集合，後者在談兩個集合的包含關係。集合本身也可以當作另一集合的元素，因此要看符號兩邊實際放的是什麼。

本章學會交、聯、差與補集，也用逐元素推理證明集合相等。本書只從已給集合取子集、配對或作明示構造，不把「所有集合組成的集合」當作可隨意使用的對象。

## 2.2 聯集 交集 差集與補集

A∪B收集在A或B中至少一邊的元素；A∩B收集同時在兩邊的元素；A∖B收集在A但不在B的元素。這裡的「或」包含兩邊都符合的情形。

補集需要先固定全集U，再寫Aᶜ=U∖A，其中A⊆U。沒有固定U，單寫「不在A的所有東西」無法確定補集範圍。空集合∅沒有元素；∅與{∅}不同，後者有一個元素，就是空集合本身。

![在固定全集中標出兩集合各自獨有、共同與皆不屬的四種位置。](assets/f03-set-regions.svg)

## 2.3 例題

### 例題1 在有限全集內運算

設U={1,2,3,4,5,6}，A={1,2,4}，B={2,3,4}。逐項檢查可得A∪B={1,2,3,4}，A∩B={2,4}，A∖B={1}，Aᶜ={3,5,6}。

聯集內的2、4各只列一次，因為集合不計重複。核對Aᶜ時要對照U，而不是只對照B，所以5、6也必須列入。

### 例題2 用兩個包含關係證相等

證明A∩B=B∩A。任取x∈A∩B，定義給出x∈A且x∈B；交換「且」兩邊，得到x∈B且x∈A，故x∈B∩A。這證得A∩B⊆B∩A。

把A、B交換，同樣證得B∩A⊆A∩B。兩邊相互包含，才得到相等；只完成其中一個方向還不夠。

### 例題3 證明一條De Morgan律

在固定U內，證明(A∪B)ᶜ=Aᶜ∩Bᶜ。任取x∈U，x在左邊若且唯若它不在A∪B；這又若且唯若x既不在A也不在B；也就是x同時在Aᶜ、Bᶜ，正好是在右邊。

此處每個「若且唯若」都可雙向讀，因為只是展開同一個元素資格。區域圖幫助定位，逐元素的等價才處理任意集合。

### 例題4 空集合與包含關係

任意集合A都有∅⊆A。若要使這句失敗，必須找到某個x∈∅卻x∉A；但空集合根本沒有這樣的x，所以不存在失敗的元素。

另一方面，∅∈A不是永遠正確。例如A={1,2}不含∅；A={∅,1}才含∅。不能把剛證明的包含關係直接改成隸屬關係。

![空集合、含空集合的單元素集合，以及子集和元素的符號層次分開比較。](assets/f04-membership-subset.svg)

## 2.4 笛卡兒積與冪集合

A×B是所有有序對(a,b)的集合，其中a∈A、b∈B。有序對的座位有意義：(1,2)與(2,1)一般不同。A、B任一為空，乘積就為空。

冪集合𝒫(A)是A的所有子集所成的集合。若A={a,b}且a≠b，則𝒫(A)={∅,{a},{b},{a,b}}。取或不取每個元素，共有2·2=4種選擇；對有n個元素的有限集合，同樣得到2^n個子集。第10章會看見無窮集合不能只靠有限張表處理。

## 2.5 練習

1. **B05-C02-Q01** 設U={0,1,2,3,4}、A={0,2,4}、B={1,2}，求聯集、交集、A∖B及Bᶜ。
2. **B05-C02-Q02** 設A={∅}，判斷∅∈A、∅⊆A、A⊆∅三句的真假。
3. **B05-C02-Q03** 證明A∖B=A∩Bᶜ，明示全集條件。
4. **B05-C02-Q04** 證明A∪∅=A，不只畫圖。
5. **B05-C02-Q05** 在固定全集中證明(A∩B)ᶜ=Aᶜ∪Bᶜ。
6. **B05-C02-Q06** 若A⊆B，證明A∩C⊆B∩C。
7. **B05-C02-Q07** 列出{a}×{0,1}，並求{a}×∅。
8. **B05-C02-Q08** 列出𝒫({0,1})，並分別用隸屬和包含符號說明{0}的資格。
9. **B05-C02-Q09** 若A∪B=A，證明B⊆A；反方向是否也成立？
10. **B05-C02-Q10** 「A∖B=B∖A」是否對任意集合成立？找出反例並說明兩邊何時可相等。

## 2.6 完整解答

### Q01

A∪B={0,1,2,4}，A∩B={2}，A∖B={0,4}。Bᶜ要從U拿掉1、2，故為{0,3,4}。每項都可用元素是否通過相應資格反查，不能把A∖B誤成「兩邊不同的所有元素」。

### Q02

∅∈A為真，因為A明列的唯一元素正是∅。∅⊆A也為真，這是空集合包含於任意集合的性質。A⊆∅為假：∅是A的元素，卻不是空集合的元素，已提供不包含的見證。

### Q03

固定U並要求A、B⊆U。任取x∈U，x∈A∖B若且唯若x∈A且x∉B；又因x∈U，後半正是x∈Bᶜ。因此資格等價於x∈A∩Bᶜ，兩邊集合相等。缺了共同全集，Bᶜ的意思尚未固定。

### Q04

若x∈A∪∅，它必須在A或∅中；後者不可能，所以x∈A。反過來，若x∈A，便已符合聯集「至少一邊」的資格，故x∈A∪∅。相互包含得到相等。

### Q05

任取x∈U。x不在A∩B，表示「在A且在B」為假，也就是至少有一邊不成立：x∉A或x∉B。這等價於x∈Aᶜ或x∈Bᶜ，即x∈Aᶜ∪Bᶜ。所有步驟都是雙向資格，故得到集合相等。

### Q06

任取x∈A∩C。它同時在A及C內，而A⊆B把x∈A送到x∈B。因此x∈B且x∈C，故x∈B∩C。這證明的是包含，不必證明B∩C的元素都回到A∩C。

### Q07

有序對的第一座只能是a，第二座可為0或1，所以乘積為{(a,0),(a,1)}。若第二集合為空，就沒有可坐第二座的元素，因此{a}×∅=∅。乘積的元素是有序對，不是把兩邊元素直接合在一起。

### Q08

冪集合為{∅,{0},{1},{0,1}}。{0}是原集合的子集，所以{0}⊆{0,1}；也正因為它是子集，才有{0}∈𝒫({0,1})。前一句比較兩個集合的包含，後一句把整個子集當作冪集合的一個元素。

### Q09

任取b∈B，它一定在A∪B中；由假設A∪B=A可得b∈A，故B⊆A。反過來，若B⊆A，聯集內無論元素來自哪邊都在A，所以A∪B⊆A；又A⊆A∪B，故相等。因此兩個條件確實等價。

### Q10

不普遍成立。例如A={1,2}、B={2}，左邊為{1}，右邊為∅。若兩個差集相等，任何在其中的元素都要同時屬於A不屬於B，又屬於B不屬於A，這不可能，所以兩者都只能為空；於是A⊆B且B⊆A，即A=B。反過來A=B時兩個差集都空，確實相等。

## 2.7 本章回看

集合等式可改寫成「任意元素在左邊若且唯若在右邊」。把符號轉成資格，通常比只憑區域顏色更容易看出漏掉的條件。


# 第3章 關係與函數映射

## 3.1 從有序對到函數

A到B的關係是A×B的一個子集R。寫aRb，是說(a,b)∈R。關係可以讓同一個a連到多個b，也可以完全沒有連到。函數則要求每個a∈A恰有一個對應的b∈B。

本書把函數的定義域A、陪域B和對應規則一起保留，記作f:A→B；值域是f(A)={f(a):a∈A}，所以f(A)⊆B。相同公式配上不同論域，未必是同一個函數。本章不預設第四冊，先用有限箭頭與整數公式建立定義。

## 3.2 單射 滿射與雙射

單射要求不同輸入不撞到同一輸出；寫成證明形式是：若f(a₁)=f(a₂)，便有a₁=a₂。滿射要求陪域裡每個b都有至少一個原像，即存在a∈A使f(a)=b。雙射是兩種條件同時成立。

單射比較定義域內的兩個輸入；滿射要對照整個陪域，而不只對照已出現的輸出。有限圖可以逐點核對這些資格，但對無窮定義域仍需一般理由。

![兩個有限映射分別展示單射但非滿射，以及滿射但非單射。](assets/f05-injection-surjection.svg)

## 3.3 例題

本章有限箭頭題中寫成{a,b}的陪域，a與b用作互異的元素標籤；一般證明中的變數不因字母不同就被假設互異。

### 例題1 關係不一定是函數

設A={1,2}、B={a,b}。關係R={(1,a),(1,b),(2,a)}不是A到B的函數，因為輸入1有兩個不同輸出。把(1,b)拿掉，R₁={(1,a),(2,a)}才滿足每個輸入恰有一個輸出的條件。

R₁不是單射，因為1≠2卻映到同一個a；也不是到B的滿射，因為b沒有原像。若只改陪域為{a}，則滿射資格變真，但單射資格仍不變。

### 例題2 由等輸出證明單射

設f:ℤ→ℤ，f(n)=2n+1。若f(m)=f(n)，則2m+1=2n+1，兩邊減1再除以非零的2，得到m=n，所以f單射。

它不是到ℤ的滿射。若0有原像，就要有2n+1=0，推出n=−1/2，卻不是整數。若把陪域改為奇整數集合，任意奇整數b可寫成2k+1，取n=k便有f(n)=b，所以改後的函數是雙射。

### 例題3 合成要保留中間資格

設f:ℤ→ℤ，f(n)=n+1，g:ℤ→ℤ，g(n)=2n。先f後g的合成記為g∘f，其值為g(f(n))=2(n+1)=2n+2；先g後f則為f(g(n))=2n+1。

兩種合成都有資格，因為中間輸出仍在下一個函數的定義域，但兩個規則不一樣。一般而言，f:A→B、g:B→C可直接合成；若下一段只接受B的某個子集，就必須再限制能通過中間條件的輸入。

### 例題4 雙射的反函數

設h:ℤ→ℤ，h(n)=n−3。對每個y∈ℤ，取n=y+3便有h(n)=y，證明滿射；若m−3=n−3，則m=n，證明單射。兩項合起來保證每個y有且只有一個原像。

因此h⁻¹(y)=y+3。雙向核對：h⁻¹(h(n))=(n−3)+3=n，h(h⁻¹(y))=(y+3)−3=y。反函數是把唯一對應反過來，不是把輸出取倒數。

![合成沿輸入、中間值、輸出依序檢查，不能倒讀成交換次序。](assets/f06-composition-route.svg)

## 3.4 空定義域的邊界

從∅到任意B有一個空函數，因為沒有輸入需要違反「恰有一個輸出」。它必為單射；只有B=∅時才是滿射。若A非空，則不存在A到∅的函數，因為至少一個輸入找不到輸出。這些不是另加例外，而是原定義本身的結果。

## 3.5 練習

1. **B05-C03-Q01** 判斷R={(1,a),(2,b)}是否為{1,2}到{a,b}的函數、單射與滿射。
2. **B05-C03-Q02** R={(1,a)}是否為{1,2}到{a,b}的函數？指出缺哪個資格。
3. **B05-C03-Q03** 證明f:ℤ→ℤ，f(n)=n+5是雙射，並求反函數。
4. **B05-C03-Q04** f:ℤ→ℤ，f(n)=2n是否滿射？是否單射？
5. **B05-C03-Q05** 令f:ℤ→ℤ，f(n)=n²，用合格見證判斷單射與滿射。
6. **B05-C03-Q06** 設f(n)=n+2、g(n)=3n，兩者均為ℤ到ℤ，求g∘f與f∘g。
7. **B05-C03-Q07** 若f:A→B、g:B→C均單射，證明g∘f單射。
8. **B05-C03-Q08** 若f:A→B、g:B→C均滿射，證明g∘f滿射。
9. **B05-C03-Q09** 描述∅→{a}與∅→∅的函數，分別判斷雙射資格。
10. **B05-C03-Q10** 若f:A→B有g:B→A，使g∘f為A上的恆等函數，證明f單射；能否只憑這條件得到f滿射？

## 3.6 完整解答

### Q01

每個輸入恰好出現一次，所以R是所指定的函數。兩個不同輸入映到不同的a、b，故為單射；陪域的a、b也都被命中，故為滿射。因此它是雙射，反向關係也有每個輸入唯一輸出的資格。

### Q02

不是指定定義域上的函數。輸入2屬於定義域，卻完全沒有輸出；問題不是不夠單射，而是連函數的基本資格都沒有成立。若改定義域為{1}，才會得到另一個合格函數。

### Q03

若m+5=n+5，則m=n，所以單射。任給y∈ℤ，取n=y−5∈ℤ，便有f(n)=y，所以滿射。反函數為f⁻¹(y)=y−5，兩種次序合成都回到各自原輸入。

### Q04

若2m=2n，除以非零的2得到m=n，所以單射。它不是滿射，因為1若有整數原像n，就須n=1/2，與整數資格衝突。只需一個未命中的陪域元素，便足以推翻滿射。

### Q05

不是單射：1與−1都是整數、兩者不同，平方卻都為1。也不是到ℤ的滿射：每個整數平方皆非負，所以−1沒有原像。這兩個失敗見證分別針對不同定義，不能互相代替。

### Q06

(g∘f)(n)=3(n+2)=3n+6，而(f∘g)(n)=3n+2。代入n=0，兩者輸出分別為6與2，確認它們不是同一規則。合成的右邊函數先作用。

### Q07

取a₁、a₂∈A並假設g(f(a₁))=g(f(a₂))。由g單射及f(a₁)、f(a₂)∈B，得到f(a₁)=f(a₂)；再由f單射得到a₁=a₂。兩次使用單射，都先核對輸入屬於正確定義域。

### Q08

任取c∈C。由g滿射，存在b∈B使g(b)=c；再由f滿射，存在a∈A使f(a)=b。因此(g∘f)(a)=g(b)=c。見證先從目標c往回找，再順向代入核對。

### Q09

兩者的圖都是空關係。∅→{a}雖為單射，但a沒有原像，所以非滿射、非雙射。∅→∅既無輸入碰撞，也無未命中的陪域元素，因此是雙射。不要把空函數和「不存在函數」混成同一件事。

### Q10

若f(a₁)=f(a₂)，兩邊施以g，得到g(f(a₁))=g(f(a₂))；由g∘f=idₐ，便有a₁=a₂，故f單射。但滿射不保證：取A={0}、B={0,1}，f(0)=0，g(0)=g(1)=0，仍有g∘f=idₐ，可是1未被f命中。

## 3.7 本章回看

單射以相等輸出倒推相等輸入；滿射從任意目標構造原像。下一章把這兩種語句裡隱含的「任意」與「存在」明寫出來。


# 第4章 連接詞、量詞與論域

## 4.1 把句子的作用範圍寫出來

命題是已有明確真假意義的敘述。P∧Q表示兩者皆真；P∨Q表示至少一者真；¬P表示P為假。本書的P⇒Q只有在P真而Q假時為假，其餘情形為真；P⇔Q則要求兩者真假相同。

這是古典命題邏輯的用法。「若P則Q」在此不另外保證時間先後或因果機制。日常語言的「或」有時只許一邊，數學裡若要排除同時成立，必須另外說明。

![真值表列出前提與結論的四種組合，只有真前提配假結論使蘊涵失敗。](assets/f07-implication-table.svg)

## 4.2 全稱與存在

∀x∈D，P(x)表示D裡每個x都滿足P；∃x∈D，P(x)表示至少一個合格x滿足P。要否定全稱，只需合格反例；要否定存在，則必須說明每個合格對象都失敗。

在古典邏輯下，¬(∀x∈D，P(x))等價於∃x∈D，¬P(x)；¬(∃x∈D，P(x))等價於∀x∈D，¬P(x)。否定量詞時，量詞改變，內部性質也要否定，不能只把「每個」換成「不是每個」就停止。

## 4.3 例題

### 例題1 蘊涵與逆命題

令P為「n是4的倍數」、Q為「n是偶數」，論域為ℤ。P⇒Q成立，因為4k=2(2k)。逆命題Q⇒P卻不成立：n=2使Q真、P假。

所以知道某個充分條件能得到結論，不表示該條件也必要。用真值表觀察時，要找的是命題實際能出現的合格輸入，而不是把題意和任意代號的因果關係混在一起。

### 例題2 有兩個量詞時怎麼否定

否定「∀x∈ℝ，∃y∈ℝ，使y>x」。最外層全稱先變存在，內層存在再變全稱，最後把y>x否定成y≤x，因此否定句是「∃x∈ℝ，∀y∈ℝ，都有y≤x」。

原句為真，因為對任意x都可取y=x+1。否定句要求有一個實數能壓住全部實數，與這個構造衝突。y可以依賴已選的x，不能偷偷要求同一個y適用全部x。

### 例題3 量詞順序不同

「∀x∈ℤ，∃y∈ℤ，使y=x+1」為真，見證是依x決定的y=x+1。「∃y∈ℤ，∀x∈ℤ，使y=x+1」則為假。

若第二句為真，把x=0代入會得y=1，把x=1代入又得y=2，無法由同一個y同時滿足。量詞換序改變了見證可依賴哪些對象。

### 例題4 空論域與空真

設D=∅。「∀x∈D，x²<0」為真，因為沒有屬於D而違反性質的x；「∃x∈D，x²<0」為假，因為連一個可交出的見證都沒有。

這不表示有某個平方負數的對象存在。全稱句本身不保證D非空；若命題需要存在輸入，應把D≠∅另列為條件。

![逐列各有一個標記不等於存在同一欄讓全部列都有標記，對應不同量詞順序。](assets/f08-quantifier-grid.svg)

## 4.4 變數不能離開它的範圍

寫「∃x∈ℤ，使x²=4」時，x受到存在量詞約束，整句不指定x究竟是2還是−2。證明時可以選一個合格見證，但不能把臨時選的符號帶出作用範圍，宣稱它對另一個無關全稱句仍適用。

分配量詞也要小心。∀x(P(x)∧Q(x))等價於(∀xP(x))∧(∀xQ(x))；∃x(P(x)∧Q(x))卻不一般等價於(∃xP(x))∧(∃xQ(x))，因為後者兩個見證可能不是同一個。

## 4.5 練習

1. **B05-C04-Q01** 寫出¬(P∧Q)的等價形式，並說明與¬P∧¬Q的差別。
2. **B05-C04-Q02** 把¬(P⇒Q)寫成只含∧與否定的形式。
3. **B05-C04-Q03** 否定「每個整數都大於0」，並判斷原句真假。
4. **B05-C04-Q04** 否定「存在實數x使x²<0」，並判斷原句真假。
5. **B05-C04-Q05** 否定「∀x∈ℝ，∃y∈ℝ，使x+y=0」，並給出原句的見證規則。
6. **B05-C04-Q06** 判斷「∃y∈ℝ，∀x∈ℝ，使x+y=0」並證明。
7. **B05-C04-Q07** 在D={0,1}上，P(x)為x=0、Q(x)為x=1。比較∃x(P(x)∧Q(x))與(∃xP(x))∧(∃xQ(x))。
8. **B05-C04-Q08** 在D=∅上，判斷∀x∈D，x=x與∃x∈D，x=x。
9. **B05-C04-Q09** 證明∀x∈D(P(x)∧Q(x))等價於(∀x∈DP(x))∧(∀x∈DQ(x))，包含空論域。
10. **B05-C04-Q10** 對任意命題P、Q，P⇒Q與¬Q⇒¬P是否同真？用失敗條件說明。

## 4.6 完整解答

### Q01

等價形式是¬P∨¬Q，意思是至少有一邊失敗。¬P∧¬Q卻要求兩邊都失敗，強得多。例如P真、Q假時，¬(P∧Q)真，而¬P∧¬Q假，足以說明兩式不等價。

### Q02

¬(P⇒Q)等價於P∧¬Q。理由是蘊涵恰在P真、Q假時失敗，因此它的否定恰好挑出這一列。不是把P、Q各自同時否定成¬P⇒¬Q。

### Q03

否定句是「存在整數n，使n≤0」。原句為假，取n=0便得到否定句所需的合格見證。只說「有些整數不大於0」也可以，但必須保留整數論域。

### Q04

否定句是「對每個實數x，都有x²≥0」。這個否定句為真，因為實數平方非負，所以原存在句為假。不能只找到x=1使平方非負，就宣稱所有見證都不可能。

### Q05

否定為「∃x∈ℝ，∀y∈ℝ，都有x+y≠0」。原句則為真：對任意已給的x，取y=−x，仍為實數且x+y=0。見證明確依賴x，量詞順序因此不可交換。

### Q06

為假。假設存在這樣同一個y，取x=0得到y=0，取x=1又得到y=−1，互相矛盾。兩次選x都在要求的實數論域內，而且針對的是同一個假設中的y。

### Q07

前者為假，因為D內沒有元素同時等於0又等於1。後者為真：P的見證取0，Q的見證取1。後者並未要求兩次交出相同見證，這就是差別。

### Q08

全稱句為真，因為沒有反例；存在句為假，因為沒有見證。性質x=x雖在通常論域總是真的，也不會替空集合創造元素。

### Q09

若左式成立，任意x同時有P(x)、Q(x)，因此分別得到兩個全稱句。若右式成立，對任意x∈D，可各自套用兩句，合得P(x)∧Q(x)。若D空，兩邊涉及的全稱句都真，仍同真；證明不需要偷偷假設D裡有一個固定元素。

### Q10

同真。P⇒Q唯一的失敗條件是P真、Q假；¬Q⇒¬P的失敗條件是¬Q真、¬P假，也就是Q假、P真，正好相同。因此兩句對每個真值配置都相等。第6章會用這項等價改變證明路線。

## 4.7 本章回看

否定句要保留原論域，見證要保留依賴順序。接下來把這些句法規則放入完整證明，而不只停在真值表上。


# 第5章 直接證明

## 5.1 按目標選擇證明動作

要證明∀x∈D，先取任意合格x，不替它增加特殊性質；要證明∃y∈E，就構造一個y並檢查它屬於E。證明P⇒Q時，可暫時假設P成立，再推出Q；證明P⇔Q則要處理兩個方向。

「任意」不是「隨便試一個數」。若把待證的整數n直接設為6，就只剩一個特例。一般證明可以在n的條件下引入見證，例如由偶數假設寫n=2k，但不能因此假設k也為偶數。

## 5.2 把代數式整理成定義需要的形式

對整數a、b，記a∣b表示存在k∈ℤ使b=ak。被整除者b在等式左邊；a、b不必為正。由定義可得每個整數a都整除0，而0只整除0。若要寫b/a或約去a，則必須另有a≠0。

證明整除，通常不必做長除法；把目標整理成a乘上一個整數即可。這和用2乘整數證明偶數，實際上是同一種構造見證的方法。

![兩個偶數各帶一個整數見證，合併後明確構造出和的見證。](assets/f09-even-sum-proof.svg)

## 5.3 例題

### 例題1 偶數乘任意整數

證明：若a為偶整數、b為任意整數，則ab為偶數。由假設寫a=2r，其中r∈ℤ。於是ab=(2r)b=2(rb)。

因r、b為整數，乘積rb仍為整數，正好是目標需要的見證。這個證明沒有要求b也偶；把條件加強成兩者皆偶雖仍能得到真命題，卻未證明原來較廣的範圍。

### 例題2 整除的傳遞性

設a∣b且b∣c。由定義，存在整數r、s使b=ar、c=bs。代入得到c=(ar)s=a(rs)，而rs是整數，所以a∣c。

本證明只用乘法與代入，沒有除以a或b，因此連a=0的合格情形也涵蓋。若a=0，第一個假設已迫使b=0，第二個再迫使c=0，與結論一致。

### 例題3 分情形覆蓋全部整數

證明每個整數n的n(n+1)都是偶數。整數除以2的餘數只可能0或1，所以n必為偶或奇。若n=2k，則n(n+1)=2[k(2k+1)]；若n=2k+1，則n+1=2(k+1)，乘積為2[(2k+1)(k+1)]。

括號中在兩種情形都是整數，因此乘積為偶數。分情形需要說明情形覆蓋全部輸入，不能只處理n>0而漏掉負整數與0。

### 例題4 平方為零的等價命題

在ℝ上證明x²=0若且唯若x=0。先假設x²=0，也就是x·x=0。由第二冊用過的實數零乘積性質，至少一個因子為0；兩個因子都是x，所以x=0。

反方向，若x=0，直接代入便得x²=0。後半雖短，仍是「若且唯若」不可省略的另一個方向。此命題的背景是實數，不能不查結構就移到任意運算系統。

![整除的兩個見證沿代入鏈相乘，得到傳遞性需要的新見證。](assets/f10-divisibility-chain.svg)

## 5.4 證明草稿與成稿

找方法時可從結論往回想：若要a∣c，就要找c=a乘整數；已有c=bs、b=ar，代入自然產生rs。寫成成稿時，再順著已知到結論排列，並把rs的整數資格寫出來。

找路線的逆向思考，不等於可以在證明中把尚未證明的結論當作已知。若採雙向等價變形，每個箭頭的可逆條件仍須保留。

## 5.5 練習

1. **B05-C05-Q01** 證明兩個奇整數的和是偶數。
2. **B05-C05-Q02** 證明兩個奇整數的乘積是奇數。
3. **B05-C05-Q03** 若3∣a且3∣b，證明3∣(2a−b)。
4. **B05-C05-Q04** 若a∣b且a∣c，證明a∣(b+c)，說明a=0是否需要排除。
5. **B05-C05-Q05** 對實數x，證明x²−2x+1≥0，並找出取等號條件。
6. **B05-C05-Q06** 證明存在整數n使n²>10，並指出存在性證明是否需要列出所有解。
7. **B05-C05-Q07** 證明整數n若是6的倍數，就同時是2與3的倍數。
8. **B05-C05-Q08** 證明a∣0對每個整數a成立，並判斷0∣5。
9. **B05-C05-Q09** 證明整數n的n²+n為偶數，寫出兩種情形的見證。
10. **B05-C05-Q10** 對實數x證明x²=1若且唯若x=1或x=−1，逐方向說明。

## 5.6 完整解答

### Q01

令a=2r+1、b=2s+1，其中r、s∈ℤ。則a+b=2r+2s+2=2(r+s+1)。由整數運算封閉，r+s+1∈ℤ，所以和為偶數。原來兩個奇數可以一正一負，見證仍成立。

### Q02

由a=2r+1、b=2s+1，展開ab=4rs+2r+2s+1=2(2rs+r+s)+1。括號內為整數，符合奇數「2乘整數再加1」的定義。不能只從幾個奇數乘法例子推廣。

### Q03

寫a=3r、b=3s，其中r、s為整數。則2a−b=6r−3s=3(2r−s)，而2r−s∈ℤ。這正是3∣(2a−b)需要的見證。

### Q04

由b=ar、c=as，得到b+c=a(r+s)，且r+s為整數，所以a∣(b+c)。不需排除a=0，因為完全沒有使用除法；當a=0時，原假設本就要求b=c=0，結論也正確。

### Q05

配方得x²−2x+1=(x−1)²≥0。等號成立若且唯若x−1=0，也就是x=1。非負性和取等號條件分開核對，才沒有把「可以等於0」誤成「總是等於0」。

### Q06

取n=4∈ℤ，則n²=16>10，已完成存在性證明。不需要列出全部解；若題目改成「求所有滿足條件的整數」，才要再證明解集完整性。

### Q07

由n=6k、k∈ℤ，可寫n=2(3k)，也可寫n=3(2k)。兩個括號都為整數，因此2∣n與3∣n同時成立。證明「且」的結論時，兩項都必須交出見證。

### Q08

任取a∈ℤ，見證k=0使0=a·0，所以a∣0，含a=0。若0∣5，則須有整數k使5=0·k=0，不可能，故0不整除5。整除定義本身有意義，不代表可以實施除以0的運算。

### Q09

若n=2k，則n²+n=4k²+2k=2(2k²+k)。若n=2k+1，則n²+n=4k²+6k+2=2(2k²+3k+1)。兩個見證都在ℤ，而整數非偶即奇，故覆蓋全部情形。

### Q10

正向：由x²=1得到(x−1)(x+1)=0。實數的零乘積性質保證至少一個因子為0，所以x=1或x=−1。反向：兩個候選分別代入平方都得1。因式分解與零乘積性質也排除了其他實數解。

## 5.7 本章回看

證明的終點往往藏在目標的定義裡。若直接順推不容易，第6章會改從等價的逆否命題或矛盾假設找路線。


# 第6章 逆否與反證

## 6.1 逆命題 不等於逆否命題

原命題P⇒Q的逆命題是Q⇒P；逆否命題是¬Q⇒¬P。第4章已用失敗真值相同證明，原命題與逆否命題同真。這條規則讓我們改變起點，但不改變要證明的內容。

例如「4的倍數一定偶」與「非偶整數一定不是4的倍數」同真；「偶整數一定是4的倍數」則不是等價改寫。若只看見箭頭反向就使用規則，容易把逆命題誤當逆否。

![原命題和逆否命題共用失敗列，逆命題則在不同列失敗。](assets/f11-contrapositive-table.svg)

## 6.2 反證法的暫時假設

要證明命題T，可暫時假設¬T，並在已允許的背景條件下推出矛盾。古典邏輯據此排除¬T而得到T。矛盾必須是某句和其否定同時成立，或與已建立的事實直接衝突；「很奇怪」不是矛盾。

要證明P⇒Q時，反證可同時假設P和¬Q，再導出矛盾。與逆否證明相比，兩者常共用計算，但成稿要交代最後排除了哪個暫時假設。

## 6.3 例題

### 例題1 平方偶則原數偶

對n∈ℤ證明：若n²為偶數，則n為偶數。改證逆否：若n不是偶數，整數除以2的餘數性質使n=2k+1，k∈ℤ。

平方得到n²=4k²+4k+1=2(2k²+2k)+1，為奇數，因此不是偶數。這證明逆否，便得到原命題。此處使用的是整數的偶奇分解，不能改在任意實數上仍說「非偶即奇」。

### 例題2 √2不是有理數

反設√2為有理數，寫成p/q，其中p、q為互質整數且q>0。這樣的最簡形式可由整數分子分母除以共同最大公因數得到。平方並乘q²，得p²=2q²，所以p²偶；由例題1，p也偶，設p=2r。

代回得到4r²=2q²，整理成q²=2r²，故q也偶。於是2同時整除p、q，與兩者互質衝突。因此反設不成立，√2不是有理數。證明依賴已引入的正實數平方根，不在這裡重新構造實數。

### 例題3 不存在最大的整數

反設m是最大整數，即m∈ℤ且每個n∈ℤ都有n≤m。因整數對加1封閉，m+1也是整數，卻有m+1>m，與最大性矛盾。

這也可直接寫成「對每個整數m，都能構造更大的m+1」。選擇反證或直接證明取決於何者最清楚，不是一定要把簡單構造改寫得更長。

### 例題4 三整除平方的必要條件

對n∈ℤ證明：若3∣n²，則3∣n。採逆否，若3不整除n，整數除法餘數使n=3k+1或3k+2。

第一種平方為9k²+6k+1=3(3k²+2k)+1；第二種平方為9k²+12k+4=3(3k²+4k+1)+1。兩種平方除以3都餘1，不被3整除，所以逆否成立。不能把這條結論不加檢查地換成任意合數：4∣2²卻4不整除2。

![最簡分數假設沿平方與偶性推導，回到分子分母有共同因數的矛盾。](assets/f12-root-two-contradiction.svg)

## 6.4 不要用待證結論證明自己

例題2若開頭就說「√2不能化成分數，所以無理」，只是重述目標。合法起點是反設一個最簡分數存在，再使用整數與偶性結果導出衝突。

反證不是「找不到答案就當不存在」。要證明不存在，必須讓任意假設的合格候選都遭遇同一個矛盾。只試到分母1000仍沒找到，只是有限搜尋結果。

## 6.5 練習

1. **B05-C06-Q01** 寫出「若整數n是6的倍數，則n是3的倍數」的逆命題與逆否命題，判斷真假。
2. **B05-C06-Q02** 對整數n，用逆否證明：若n²為奇數，則n為奇數。
3. **B05-C06-Q03** 證明不存在最小的正實數。
4. **B05-C06-Q04** 由√2無理，證明3+√2無理。
5. **B05-C06-Q05** 對整數a、b，證明若ab為奇數，則a、b都為奇數。
6. **B05-C06-Q06** 以模3餘數證明√3無理，交代最簡分數資格。
7. **B05-C06-Q07** 「若4∣n²則4∣n」是否可照例題4直接推廣？
8. **B05-C06-Q08** 證明若x∈ℝ且x>0，則1/x>0；使用反設時哪些運算先有資格？
9. **B05-C06-Q09** 有人說「前一千個分母都找不到√2的分數表示，所以它無理」。指出缺口。
10. **B05-C06-Q10** 用反證證明：若有限集合A、B滿足A⊆B且有相同元素個數，則A=B。

## 6.6 完整解答

### Q01

逆命題是「若3∣n，則6∣n」，為假，n=3就是合格反例。逆否是「若3不整除n，則6不整除n」，為真，因它與原命題同真；原命題由n=6k=3(2k)直接得到。不要把「非3倍數」改成「非整數」。

### Q02

逆否是「若n不是奇數，則n²不是奇數」。整數n非奇即偶，寫n=2k，便有n²=2(2k²)為偶，故非奇。這個逆否證明完成原命題，沒有先假設n本來就是奇數。

### Q03

反設m是最小正實數，則m>0。m/2也是正實數，且0<m/2<m，與最小性矛盾。與最大整數的例子相比，這裡構造的是更小且仍留在正實數論域的對象。

### Q04

反設r=3+√2為有理數。整數3為有理數，有理數對減法封閉，所以√2=r−3也為有理數，與已證結果矛盾。因此3+√2無理。需要明說封閉性，不能只憑外觀保留根號就斷言無理。

### Q05

若a、b並非都奇，則至少一個為偶。假設a偶，依第5章得ab偶；若b偶同理。兩種情形都與ab奇矛盾，故兩者都奇。這裡把「且」的否定正確轉成了「至少一邊非奇」。

### Q06

反設√3=p/q，p、q∈ℤ互質且q>0。平方得p²=3q²，故3∣p²；由例題4得p=3r。代入後9r²=3q²，即q²=3r²，再得3∣q。於是p、q同有因數3，與互質矛盾，所以√3無理。

### Q07

不能。取整數n=2，平方為4，所以4∣n²；但2不是4的倍數，結論失敗。例題4對3的餘數分類有明確計算，並不是一條任意換除數仍成立的規則。

### Q08

x>0先保證x≠0，所以1/x已有定義。若反設1/x≤0，兩邊乘正數x不改不等號方向，得到1≤0，與實數次序矛盾。不能在尚未確定x非零前就把倒數當作合法對象。

### Q09

分母可能超過一千，有限搜尋沒有覆蓋全部正整數分母。要證明無理，須處理任意可能的整數p與正整數q；例題2的最簡分數矛盾就是一般排除理由。搜尋失敗既不是一般不存在證明，也沒有推翻可能更大的候選。

### Q10

反設A≠B。因A⊆B，必有至少一個b∈B卻b∉A。有限的B於是至少包含A的全部元素再加一個不同元素，故|B|≥|A|+1，與個數相同矛盾，得到A=B。有限性是本題關鍵；無窮集合可能與真子集有雙射，第10章會看到例子。

## 6.7 本章回看

改走逆否時保留原論域；走反證時標明暫時假設與最後的衝突。下一章把這些條件用來拆解看似合理卻無效的論證。


# 第7章 反例與錯誤推理

## 7.1 反例必須擊中原句

要推翻「對所有x∈D，只要P(x)就有Q(x)」，反例必須同時通過三關：x確實屬於D、P(x)確實成立、Q(x)確實失敗。只找到結論失敗但前提也失敗的對象，並沒有推翻蘊涵。

若命題對某個明示有限集合的全部元素成立，完整枚舉可以證明那個有限版本。若論域是所有整數或實數，任意選一個很大的有限測試範圍，都不能自動延伸為一般證明。

![反例先檢查論域，再檢查前提成立與結論失敗；三關缺一不可。](assets/f13-counterexample-gates.svg)

## 7.2 例題

### 例題1 推翻一個過強全稱句

「每個質數都是奇數」為假。取p=2：2>1且正因數只有1、2，所以它真的是質數；但2為偶而非奇。這個見證完整符合反例資格。

取p=1就不合格，因為1不是質數。修正版「每個大於2的質數都是奇數」可以另外證明：若大於2的質數為偶，2就成為不同於1與它本身的正因數，與質數資格衝突。

### 例題2 除以零藏在約分中

有人令a=b=1，由a²=ab減去b²，得到(a−b)(a+b)=b(a−b)，再約去a−b，得a+b=b，最後聲稱2=1。問題出在約去的因子a−b=0。

原等式只是0·2=0·1，兩邊同為0，不包含2=1。等式兩邊乘以0合法，但不能一般反推乘之前相等。每次約分都要先核對被約的因子非零。

### 例題3 平方後記得回查

解實數方程√(x+2)=x。原式要求x+2≥0，且左邊非負使x≥0。平方得到x+2=x²，整理為(x−2)(x+1)=0，候選是2與−1。

回查原條件，−1不符合x≥0；直接代回也有√1=1≠−1。2代回為√4=2，所以解集只有{2}。平方後的式子給必要條件，不保證每個候選都是原解。

### 例題4 有限資料不能決定所有輸入

規則f(n)=n+1與g(n)=n+1+n(n−1)(n−2)在n=0、1、2時相同，因額外因子乘積均為0。但n=3時f(3)=4、g(3)=10。

因此三個輸入輸出資料不能唯一決定整數上的一般規則。這不表示所有有限資料都毫無用途；若另加「規則為一次多項式」且給足不同點，就有另一個帶條件的唯一性問題。

![等式可以同乘零，卻不能在零因子處逆向約分；合法與非法箭頭分開。](assets/f14-zero-cancellation.svg)

## 7.3 錯誤的層次不同

反例推翻的是命題；指出某一段證明無效，只代表該段尚未建立命題。命題可能仍真，只是需要另一個有效證明。例如「所有整數n都有n²≥0」是真的，但「我試了0到100，所以全部都對」不是它的一般證明。

還有一類錯誤是結論比證據更強。找到一組使方程成立，只建立存在；要說「唯一」需再排除其他解，要說「所有解」需給完整性理由。

## 7.4 練習

1. **B05-C07-Q01** 推翻「每個偶整數都是4的倍數」，逐項核對反例資格。
2. **B05-C07-Q02** 命題是「正實數x都有1/x>0」。能否用x=0當反例？
3. **B05-C07-Q03** 推翻「所有實數x都有x²≥x」，並說明x=2為何不是反例。
4. **B05-C07-Q04** 從ac=bc推a=b，需要什麼額外條件？給出缺條件時的反例。
5. **B05-C07-Q05** 解√(x+6)=x，列條件、候選與原式回查。
6. **B05-C07-Q06** 寫出兩個不同的整數多項式規則，在n=0、1時相同，在n=2時不同。
7. **B05-C07-Q07** 「對整數n，若n²為偶數，則n為偶數」是真的。若證明只寫n=2、4、6的平方，缺了什麼？
8. **B05-C07-Q08** 「存在x∈ℝ使x²=4，所以解唯一」哪裡過強？列出全部實數解。
9. **B05-C07-Q09** 找出兩個集合A、B使A∪B的元素個數不等於|A|+|B|，並給出正確的有限集合公式。
10. **B05-C07-Q10** 推翻「若a/b=c/d，則a=c且b=d」，交代分母資格。

## 7.5 完整解答

### Q01

取n=2，它是整數且為偶數，因2=2·1；但若2=4k，則k=1/2不是整數，所以2不是4的倍數。論域、前提成立、結論失敗三項都通過，故是合格反例。

### Q02

不能。0不屬於正實數論域，而且1/0在本題沒有定義。這不是「結論為假」的合格輸入，而是根本未通過資格。原命題已可由第6章的正數倒數證明成立。

### Q03

取x=1/2∈ℝ，其平方1/4小於1/2，所以推翻原句。x=2雖屬於論域，卻有4≥2，讓結論成立，不是反例。找反例不是只找一個方便計算的輸入。

### Q04

在實數中，若c≠0，就可兩邊除以c，得到a=b。缺此條件時取a=1、b=2、c=0，便有ac=bc=0，卻a≠b。這也說明乘法相等不一定能逆向取消共同因子。

### Q05

原式要求x≥0，這也使x+6≥0。平方得x+6=x²，即(x−3)(x+2)=0，候選3、−2。−2不符非負條件且代回為2≠−2；3代回√9=3，故解集{3}。兩個候選都經過原條件核對。

### Q06

可取f(n)=n、g(n)=n+n(n−1)。n=0、1時附加乘積為0，故同值；n=2時f(2)=2、g(2)=4，確實不同。這是明確構造，不只聲稱「應該可以有別的公式」。

### Q07

那只處理三個前提成立的例子，沒有對任意整數建立理由。可以補第6章的逆否：非偶整數為2k+1，其平方仍奇，於是平方偶就排除原數非偶的可能。原命題真，不代表每個聲稱證明它的文字都有效。

### Q08

存在性沒有包含「至多一個」。由x²−4=(x−2)(x+2)=0，零乘積性質給出x=2或−2；兩個不同候選代回都成立，所以解集{−2,2}。這同時給出存在、非唯一與全部解的完整性。

### Q09

取A={1,2}、B={2,3}，聯集有3個元素，但|A|+|B|=4。共同元素2在右側被算了兩次；正確公式為|A∪B|=|A|+|B|−|A∩B|。有限集合可分成A獨有、交集、B獨有三塊，逐塊計數即可證明公式。

### Q10

取a=1、b=2、c=2、d=4，兩個分母都非零，且1/2=2/4；但a≠c且b≠d。分數表示可以不同卻是同一個有理數。若要求約分後的規範形式，才需要另列條件並證明唯一性。

## 7.6 本章回看

失敗的證明與假的命題不同；有限驗算與全稱證明也不同。下一章把「已做一段，如何保證下一段」變成有明確起點的歸納推理。


# 第8章 歸納與遞迴

## 8.1 歸納不是多試幾項

數學歸納法依靠自然數的歸納原理：若P(0)成立，且對每個k∈ℕ都能由P(k)推出P(k+1)，則每個n∈ℕ都有P(n)。也可以從1或其他固定整數起步，但結論範圍要跟著起點改變。

基底讓推理有地方開始；歸納步則對任意合格k證明一段可重複使用的連接。只計算前一百項並沒有提供後面的連接規則。本章使用自然數的歸納原理，不在這裡從集合論公理重新建造自然數。

![歸納鏈同時標出起點和任意相鄰步；缺少其中一項都不能覆蓋全部自然數。](assets/f15-induction-chain.svg)

## 8.2 例題

### 例題1 前n個正整數的和

對n≥1證明1+2+⋯+n=n(n+1)/2。基底n=1時，兩邊都為1。歸納步取任意k≥1，假設前k項和為k(k+1)/2。

加入第k+1項，得到k(k+1)/2+(k+1)=(k+1)(k+2)/2，正是n=k+1時的目標形式。基底與全部歸納步完成，故公式對每個正整數成立。

### 例題2 由遞迴規則猜到並證明公式

設a₀=1，aₙ₊₁=2aₙ+1。逐項得1、3、7、15，提示公式aₙ=2^(n+1)−1，但這串數字本身不是證明。基底n=0時右邊為1。

假設aₖ=2^(k+1)−1，代入遞迴式得到aₖ₊₁=2[2^(k+1)−1]+1=2^(k+2)−1，符合下一項公式。遞迴式保證逐項定義，歸納證明則把封閉公式連回那條規則。

### 例題3 強歸納證明質因數分解的存在

證明每個整數n≥2都能寫成有限個質數的乘積。採強歸納：基底2本身為質數。對任意n>2，假設2到n−1的所有整數都已有所需分解。

若n為質數，單獨的n就是分解。若n非質數且n>1，可寫n=ab，其中2≤a,b<n。強歸納假設分別給a、b有限個質數的乘積，合併兩串便得到n的分解。本題只證存在，不宣稱不同分解的唯一性已由此建立。

### 例題4 二階遞迴需要兩個初值

定義F₀=0、F₁=1，且Fₙ₊₂=Fₙ₊₁+Fₙ。前幾項為0、1、1、2、3、5。若另一序列G有相同兩個初值與同一遞迴規則，則兩序列逐項相同。

證明時讓歸納性質同時包含Gₖ=Fₖ與Gₖ₊₁=Fₖ₊₁。基底k=0由兩個初值給出；歸納步利用相加得到Gₖ₊₂=Fₖ₊₂，與已知的第k+1項配成下一對。只給F₀而未給F₁，不能唯一決定這個二階遞迴。

![三個和式值由各自的有限遞迴展開取得，樹的展示不代替對任意指標的歸納。](assets/f16-recursion-expansion.svg)

## 8.3 怎麼找出假的歸納步

若只證明P(k)⇒P(k+2)並給P(0)，最多沿這條鏈到達偶數位置；奇數位置還缺基底或連接。若歸納步需要k≥2，就要另外處理起點到這項限制之間的情形。

強歸納不是允許直接使用未證明的目標。它假設比目前指標小的全部情形；例題3的a、b都嚴格小於n，才有使用資格。若分解時出現a=n，就形成循環而非歸納下降。

## 8.4 練習

1. **B05-C08-Q01** 用歸納證明前n個奇正整數之和為n²，n≥1。
2. **B05-C08-Q02** 用歸納證明1+2+4+⋯+2ⁿ=2^(n+1)−1，n≥0。
3. **B05-C08-Q03** 用歸納證明n³−n被3整除，n≥0。
4. **B05-C08-Q04** 設b₀=2、bₙ₊₁=bₙ+3，求b₀到b₃並證明bₙ=2+3n。
5. **B05-C08-Q05** 設c₀=0、cₙ₊₁=cₙ+n+1，求c₃並證明cₙ=n(n+1)/2。
6. **B05-C08-Q06** 計算例題4的F₂到F₆，逐次指出用了哪兩項。
7. **B05-C08-Q07** 若只知道P(0)與對所有k≥0有P(k)⇒P(k+2)，能否推出每個自然數的P？給出失敗模型。
8. **B05-C08-Q08** 有人證明對n≥1的2ⁿ≥n，只做了歸納步，沒有基底。補出完整證明。
9. **B05-C08-Q09** 只有a₀=0、aₙ₊₂=aₙ₊₁+aₙ是否決定唯一序列？給出兩組前四項。
10. **B05-C08-Q10** 將30寫成質數乘積，並說明例題3的一般證明為何不能到「存在」就宣稱「唯一」。

## 8.5 完整解答

### Q01

基底n=1時和為1=1²。假設前k項和為k²，下一個奇數是2k+1，所以新和為k²+(2k+1)=(k+1)²。對任意k≥1都能完成此步，故所有n≥1成立。加入的是第k+1個奇數，不能誤寫成2(k+1)+1。

### Q02

n=0時左邊只有1，右邊2−1=1。若截至2ᵏ的和為2^(k+1)−1，再加2^(k+1)得到2·2^(k+1)−1=2^(k+2)−1，正是下一個指標的公式。基底與步驟的指標範圍一致。

### Q03

基底n=0時為0，確實被3整除。假設k³−k=3r，其中r∈ℤ；則(k+1)³−(k+1)=(k³−k)+3k²+3k=3(r+k²+k)。新見證仍為整數，完成歸納步，所以每個n≥0皆成立。

### Q04

前四項為2、5、8、11。公式在n=0給2，符合初值。若bₖ=2+3k，遞迴式給bₖ₊₁=2+3k+3=2+3(k+1)。因此公式對每個n≥0成立；前四項只是幫助觀察與核對。

### Q05

c₁=1、c₂=3、c₃=6。基底n=0時公式為0。若cₖ=k(k+1)/2，則cₖ₊₁=k(k+1)/2+(k+1)=(k+1)(k+2)/2，完成歸納步。因此c₃=6也和公式一致。

### Q06

F₂=F₁+F₀=1，F₃=F₂+F₁=2，F₄=F₃+F₂=3，F₅=F₄+F₃=5，F₆=F₅+F₄=8。每一步都只使用已定義的前兩項，沒有把求出的後項當成先前已知。

### Q07

不能。令P(n)為「n為偶數」，則P(0)真，且偶數加2仍偶，使全部指定步驟成立；但P(1)假。這個模型同時滿足已給條件與失敗結論，因此清楚顯示奇數鏈尚未接上。

### Q08

基底n=1時2≥1。對任意k≥1，假設2ᵏ≥k，則2^(k+1)=2·2ᵏ≥2k≥k+1，末步使用k≥1。因此歸納步成立，加上基底後才得所有n≥1的結論。這個歸納步沒有在k=0使用2k≥k+1。

### Q09

不唯一。若另外選a₁=0，前四項為0、0、0、0；若選a₁=1，前四項為0、1、1、2。兩者都符合已給的a₀和遞迴式，卻不是同一序列，說明第二初值不可省略。

### Q10

30=2·15=2·3·5，三個因子都是質數，給出一個存在見證。例題3的歸納只保證可找到一串質因數，沒有比較兩串不同分解。唯一性需要另證例如質數整除乘積時的性質，不能僅憑這一串算例宣稱所有整數的分解唯一。

## 8.6 本章回看

歸納確保規則沿全部自然數延續；遞迴規定如何由先前資料產生下一項。兩者常一起使用，但一個是證明原理，另一個是定義方式。


# 第9章 等價關係與商集

## 9.1 哪些不同對象可以歸為同一類

相等要求是同一對象，等價則可以依明示標準把不同對象分到一類。設關係∼定義在A上，若對所有x、y、z∈A同時具有自反性x∼x、對稱性x∼y⇒y∼x，以及傳遞性(x∼y且y∼z)⇒x∼z，就稱為等價關係。

三個性質都必要。「看起來很接近」通常不傳遞；「小於或等於」雖自反、傳遞，卻不對稱。不能只因某個分類直覺方便就跳過資格檢查。

## 9.2 等價類與分割

對x∈A，定義[x]={y∈A:y∼x}，稱為x的等價類。因自反性，x∈[x]，所以每個由元素產生的類都非空；全部等價類覆蓋A。商集A/∼是這些等價類所成的集合，而不是隨便抽出幾個代表元的集合。

兩個等價類若相交，就相等。若z∈[a]∩[b]，由z∼a、z∼b及對稱、傳遞，得a∼b。對任意y∈[a]，y∼a再接a∼b，得到y∈[b]；反向同理。故不同類必互不相交，形成A的分割。

![整數按除以3的餘數分為三類，有限標記只是每個無窮類的一部分。](assets/f17-residue-classes.svg)

## 9.3 例題

### 例題1 同奇偶形成等價關係

在ℤ上定義a∼b若2∣(a−b)。自反性來自a−a=2·0；若a−b=2k，則b−a=2(−k)，得對稱性；若a−b=2k、b−c=2ℓ，相加得a−c=2(k+ℓ)，得傳遞性。

因此等價類只有偶整數類[0]與奇整數類[1]。例如[−1]=[1]，因−1−1=−2為2的倍數；但−1與1不是同一個整數。類相等不表示代表元相等。

### 例題2 模3的類與商映射

在ℤ上定義a∼b若3∣(a−b)。三項性質與例題1同樣由0、負號、加法的整數見證得到。每個整數除以3的唯一餘數為0、1或2，所以ℤ/∼={[0],[1],[2]}。

商映射q:ℤ→ℤ/∼定義q(a)=[a]。它是滿射，因商集的每個元素本來就是某個[a]；它不是單射，因q(0)=q(3)但0≠3。這個滿射理由是對任意等價類的一般理由，不是只試三個箭頭。

### 例題3 從有限分割建立關係

設A={1,2,3,4,5}，分成非空區塊{1,4}、{2,5}、{3}，兩兩不交且聯集為A。定義x∼y當它們在同一區塊。

每個元素和自己同區塊，故自反；同區塊不分次序，故對稱。若x、y同塊且y、z同塊，因兩塊若共含y就必是同一塊，所以x、z也同塊，得傳遞。商集就是這三個區塊的集合。

### 例題4 代表元運算需要良定性

在模3商集上想定義[a]+[b]=[a+b]，必須證明換代表元不改結果。若a'∼a、b'∼b，則a'−a=3r、b'−b=3s，其中r、s∈ℤ。

因此(a'+b')−(a+b)=3(r+s)，故[a'+b']=[a+b]。這就證明了加法的良定性。只算出[1]+[2]=[0]是一個例子，不能代替任意代表元變換的理由。

![兩條不同代表元路線在取類後必須同結果，才可定義商集上的加法。](assets/f18-well-defined-addition.svg)

## 9.4 類 代表元與記號

[a]是一整個集合，a只是其中一個代表。在模3情形，可用0、1、2標記三個類，但這是簡寫，不會讓[1]={1}。類內還有−2、4、7等無窮多整數。

從A到商集的操作會忘記部分差異，因此商集上的新函數或運算必須尊重等價關係。若同一類的不同代表能算出不同目標類，就不能把它當成類本身的良定操作。

## 9.5 練習

1. **B05-C09-Q01** 在A={1,2,3}上，普通相等是否為等價關係？列出商集。
2. **B05-C09-Q02** 在ℤ上，a∼b定義為|a|=|b|，證明為等價關係，並求[0]、[2]。
3. **B05-C09-Q03** 在ℤ上，aRb定義為a≤b，哪個等價關係資格失敗？
4. **B05-C09-Q04** 在ℝ上，aRb定義為|a−b|<1，逐項檢查三種性質。
5. **B05-C09-Q05** 在模3關係下，求[−2]、[4]是否相等，並判斷[4]與[0]。
6. **B05-C09-Q06** 設a、b、c、d為四個互異元素，A={a,b,c,d}，分割為{a,c}、{b,d}。列出對應關係的全部有序對。
7. **B05-C09-Q07** 在模3商集上計算[2]+[2]，再改用代表元5與−1核對，說明一般良定理由。
8. **B05-C09-Q08** 依第2題的絕對值等價關係，試用[a]+[b]=[a+b]定義加法，是否良定？
9. **B05-C09-Q09** A=∅時，空關係是否為等價關係？商集是∅還是{∅}？
10. **B05-C09-Q10** A={1,2,3}，R含所有自反對，再含(1,2)、(2,1)、(2,3)、(3,2)。它是否等價？若要保留原有關係，最少還需加哪些對？

## 9.6 完整解答

### Q01

相等具自反、對稱與傳遞三性質，因此是等價關係。每個數只和自己相等，所以商集為{{1},{2},{3}}。商集有三個元素，而每個元素是一個單元素類，不要漏掉外層集合括號。

### Q02

由實數相等的三性質，|a|=|a|、等號可反向、相等可傳遞，得到此關係的三性質。[0]={0}；[2]={−2,2}，因整數滿足|y|=2恰有這兩種可能。一般非零類將正負兩個整數歸為一類。

### Q03

自反與傳遞成立，但對稱失敗：1≤2卻2不小於等於1。只要一項失敗就不是等價關係，不需把已成立的兩項也判錯。

### Q04

自反成立，因|a−a|=0<1；對稱成立，因|a−b|=|b−a|。傳遞失敗：取a=0、b=3/4、c=3/2，前兩段距離都為3/4<1，但|a−c|=3/2≥1。因此「相距不到1」不能直接產生互不相交的等價類分割。

### Q05

−2與4之差為−6，被3整除，所以[−2]=[4]，其餘數標記皆為[1]。4−0=4不被3整除，所以[4]≠[0]。判斷類相等時比較兩個代表是否等價，而不是代表的數值是否相等。

### Q06

同在第一塊產生(a,a)、(a,c)、(c,a)、(c,c)；第二塊產生(b,b)、(b,d)、(d,b)、(d,d)。聯集共8對。跨不同塊的有序對不屬於關係，且每個自反對都保留。

### Q07

[2]+[2]=[4]=[1]。5與−1都同2模3，所以改算5+(−1)=4仍落在[1]。這次代入只是核對；一般良定性由(a'+b')−(a+b)=3(r+s)建立，確保任何合格換代表元都得到相同類。

### Q08

不良定。因[1]=[−1]，同樣的兩個輸入類可用1、1或−1、1作代表。第一路得到[2]，第二路得到[0]；在絕對值關係中這兩類不同。所以不能把代表元相加自動當作類的加法。

### Q09

空關係在空集合上三種全稱資格都空真，因此是等價關係。商集定義為{[x]:x∈A}，此時沒有x可以產生等價類，故商集為∅，不是含一個空類的{∅}。每個實際產生的等價類非空，並不迫使商集一定有元素。

### Q10

它自反且對稱，但不傳遞，因1R2且2R3卻沒有1R3。必須補(1,3)；為對稱還須補(3,1)。補完後就是A×A，三項資格全部成立，商集只有一類A。這兩對都由原關係的必要性迫使加入，故已是最少。

## 9.7 本章回看

等價關係把集合分成互不重疊的非空類；商集以類作元素。把分類壓成一個記號時，代表元選擇不能悄悄改變運算結果。


# 第10章 可數性與閱讀長證明

## 10.1 用配對比較集合大小

有限集合可數元素個數；無窮集合不能靠「數到目前還沒結束」來比較。我們用雙射定義等勢：兩集合能一對一、沒有遺漏地配對，就說它們等勢。與ℕ有雙射的集合稱為可數無窮；本書把有限或可數無窮統稱為至多可數。

「可數」在不同教材可能專指可數無窮，也可能包含有限。本書在需要時明寫這兩種名稱，避免把空集合和無窮集合混為一談。本章只建立可核對的代表性構造，不發展完整基數理論。

## 10.2 例題

### 例題1 真子集仍可與全體等勢

設E={0,2,4,…}。函數f:ℕ→E，f(n)=2n是單射，因2m=2n推出m=n；又每個E內元素本來就可寫成2k、k∈ℕ，所以滿射。故E與ℕ等勢。

E卻是ℕ的真子集，因1∈ℕ而1∉E。這不推翻有限集合的計數結果，而是指出有限性在「真子集一定較少」這種說法中不可省略。

### 例題2 把全部整數排進自然數位置

按0、1、−1、2、−2、3、−3、…排列ℤ。明確規則為g(0)=0；對k≥1，g(2k−1)=k、g(2k)=−k。每個正整數出現在自己的奇數位置，每個負整數出現在自己的正偶數位置，0只出現在位置0。

因此沒有漏掉整數，也沒有不同位置碰到同一整數。逆向位置是：z>0時2z−1，z<0時−2z，z=0時0。配對規則而非寫出來的前七項，才證明ℤ可數無窮。

### 例題3 沿對角線列出有序對

在ℕ×ℕ中按m+n=s分組，每組依m=0到s排列。開頭是(0,0)、(0,1)、(1,0)、(0,2)、(1,1)、(2,0)。第s組前共有Tₛ=s(s+1)/2項，所以配對公式為π(m,n)=Tₘ₊ₙ+m。

每組恰好使用從Tₛ到Tₛ₊₁−1的位置。給定任意位置k，存在唯一s使Tₛ≤k<Tₛ₊₁；可在有限候選0到k中找到它，因T₀=0且Tₖ₊₁>k。取m=k−Tₛ、n=s−m，兩者均為自然數且π(m,n)=k。不同組的位置區間不交，組內m也唯一，所以這是雙射。

![自然數有序對依座標和分成有限對角線，每個點都有唯一有限位置。](assets/f19-diagonal-enumeration.svg)

### 例題4 沒有一張清單能列完ℕ的全部子集

反設能列出ℕ的全部子集，寫成A₀、A₁、A₂、…，每項Aₙ⊆ℕ。構造D={n∈ℕ:n∉Aₙ}，它是ℕ的一個合格子集。若清單完整，就有某個m滿足D=Aₘ。

此時問m是否屬於D。由構造，m∈D若且唯若m∉Aₘ；再用D=Aₘ，得到m∈D若且唯若m∉D，兩種可能都矛盾。所以沒有任何以ℕ編號的清單能列完𝒫(ℕ)。即使允許清單重複，也無法逃過同一個對角構造。

𝒫(ℕ)也不是有限集合，因為它至少包含無窮多不同的單元素子集{0}、{1}、{2}、…；因此它不是至多可數。這段論證沒有使用實數小數展開，也不需要處理小數表示不唯一的問題。

![從第n列的第n格反轉歸屬，得到與每一列至少一格不同的新子集。](assets/f20-diagonal-membership.svg)

## 10.3 有理數的列舉與重複表示

每個有理數可寫成a/b，其中a∈ℤ、b∈ℕ₊。先用前兩個配對構造，逐一列出所有(g(m),n+1)，再輸出g(m)/(n+1)，便能讓每個有理數在某個有限位置出現。因1/2=2/4，這張清單可能重複。

從前往後只保留首次出現的值，便得到無重複列舉：每個有理數的某次出現位置有限，首次出現不晚於它；之前只有有限項，刪去重複後仍會在有限位置保留它。有理數含全部整數，所以不會只剩有限個值，故ℚ可數無窮。這個構造沒有把無窮多行逐行走完；若永遠先列完第一行，其他行反而到不了。

## 10.4 閱讀長證明的工作方法

以例題4為例，先圈出目標「不存在完整清單」，再標出暫時假設「有一張完整清單」。D的構造只用已給的Aₙ與ℕ，因此有資格放進𝒫(ℕ)；完整性假設才允許找出m。最後的矛盾發生在同一個m，不是任意兩個不同指標混用。

讀完每段後，用一句話寫它替後面提供什麼。若中間引用一個結果，先核對其前提是否在當前論域成立。這樣可把長證明拆成有輸入條件的短段，而不是把關鍵步驟一律省略成「顯然」。

## 10.5 練習

1. **B05-C10-Q01** 證明ℕ與正整數集合ℕ₊等勢，給出雙射與反向核對。
2. **B05-C10-Q02** 依例題2求g(7)、g(8)，以及−6在清單的位置。
3. **B05-C10-Q03** 證明奇正整數集合{1,3,5,…}可數無窮。
4. **B05-C10-Q04** 用π(m,n)求(2,1)的位置，並找出位置8的有序對。
5. **B05-C10-Q05** 為何逐行先列完(0,0)、(0,1)、(0,2)、…再列第二行，不能列完ℕ×ℕ？
6. **B05-C10-Q06** 給有限清單A₀={0,2}、A₁={1}、A₂=∅，在U={0,1,2}中構造D={n∈U:n∉Aₙ}並逐列比較。
7. **B05-C10-Q07** 反設例題4清單中有重複，是否使對角證明失效？說明用到清單的哪個條件。
8. **B05-C10-Q08** 解釋有理數列舉如何處理1/2與2/4，為何刪重後不會漏掉某個有理數。
9. **B05-C10-Q09** 「已列出前十萬個子集，所以𝒫(ℕ)可數」為何無效？與ℤ的明確列舉證明比較。
10. **B05-C10-Q10** 把例題4整理成四段：反設、合格構造、利用完整性、矛盾及結論。每段寫出依賴什麼。

## 10.6 完整解答

### Q01

取f(n)=n+1，將ℕ映到ℕ₊。若m+1=n+1則m=n，故單射；任給k≥1，n=k−1∈ℕ且f(n)=k，故滿射。反函數k↦k−1雙向合成都回到原數，所以等勢。

### Q02

7=2·4−1，故g(7)=4；8=2·4，故g(8)=−4。負整數z=−6的位置為−2z=12，代回g(12)=−6。位置和輸出都是整數，但角色不同，不要把負整數當作負的位置。

### Q03

取f:ℕ→{1,3,5,…}，f(n)=2n+1。等輸出推出2m+1=2n+1，故m=n，為單射；每個奇正整數可寫2k+1且k≥0，因此有原像k，為滿射。由雙射定義得到可數無窮。

### Q04

(2,1)的座標和為3，T₃=6，所以π(2,1)=6+2=8。反向從k=8找6=T₃≤8<T₄=10，得到s=3、m=8−6=2、n=3−2=1。兩路核對一致，而不是只用圖上某個點猜位置。

### Q05

第一行有無窮多點，沒有某個有限步驟會走到「第一行最後一點」，所以(1,0)永遠不會取得有限位置。可數列舉要求每個對象都在某個自然數位置出現；對角線方法讓每組有限，才真正跨到後續各行。

### Q06

0∈A₀，所以0不在D；1∈A₁，所以1不在D；2∉A₂，所以2在D，故D={2}。它與A₀在0的位置不同，與A₁在1不同，與A₂在2不同。這只驗證該有限三列；一般無窮結論仍靠任意指標的構造論證。

### Q07

不會失效。證明只要求清單對𝒫(ℕ)滿射，亦即每個子集至少出現一次，並不要求單射。對角構造仍使D與每個Aₙ至少在n不同，所以連允許重複的完整清單都不可能存在。

### Q08

兩個分數是同一值；列到第二次相同值時略過，只保留首次。任意有理數r有一個整數分子和正分母，該對在某有限位置出現，因此r的首次出現也在有限位置。刪重只刪後來的副本，不刪首次，所以不漏值；又有無窮多整數值，保留清單不會提前結束。

### Q09

有限清單沒有給出任意子集出現的位置，也無法覆蓋全部子集。ℤ的證明不是只有列出開頭幾項，而是給每個正數、負數及0唯一位置，並核對逆規則。對𝒫(ℕ)，對角論證更進一步排除了任何候選完整清單，不只是排除目前這十萬項。

### Q10

反設段：假設有以ℕ編號且覆蓋全部子集的清單Aₙ。構造段：用這張清單定義D={n∈ℕ:n∉Aₙ}，由D⊆ℕ得到D∈𝒫(ℕ)。完整性段：因每個子集都在清單，取得某個m使D=Aₘ。矛盾段：同一個m滿足m∈D⇔m∉Aₘ⇔m∉D，不可能，所以排除原反設。四段的依賴順序清楚，便不會先把待找的m拿來定義D。

## 10.7 本冊回看

現在可以從定義、條件與量詞出發，讀寫直接證明、逆否、反證、反例與歸納；也能分清類與代表元、有限驗算與無窮構造。之後閱讀其他分冊時，先核對前提，再追蹤每個見證和變數的範圍，就是同一套基本功。