第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也唯一，所以這是雙射。
例題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}、…；因此它不是至多可數。這段論證沒有使用實數小數展開，也不需要處理小數表示不唯一的問題。
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 練習
- B05-C10-Q01 證明ℕ與正整數集合ℕ₊等勢，給出雙射與反向核對。
- B05-C10-Q02 依例題2求g(7)、g(8)，以及−6在清單的位置。
- B05-C10-Q03 證明奇正整數集合{1,3,5,…}可數無窮。
- B05-C10-Q04 用π(m,n)求(2,1)的位置，並找出位置8的有序對。
- B05-C10-Q05 為何逐行先列完(0,0)、(0,1)、(0,2)、…再列第二行，不能列完ℕ×ℕ？
- B05-C10-Q06 給有限清單A₀={0,2}、A₁={1}、A₂=∅，在U={0,1,2}中構造D={n∈U:n∉Aₙ}並逐列比較。
- B05-C10-Q07 反設例題4清單中有重複，是否使對角證明失效？說明用到清單的哪個條件。
- B05-C10-Q08 解釋有理數列舉如何處理1/2與2/4，為何刪重後不會漏掉某個有理數。
- B05-C10-Q09 「已列出前十萬個子集，所以𝒫(ℕ)可數」為何無效？與ℤ的明確列舉證明比較。
- 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 本冊回看
現在可以從定義、條件與量詞出發，讀寫直接證明、逆否、反證、反例與歸納；也能分清類與代表元、有限驗算與無窮構造。之後閱讀其他分冊時，先核對前提，再追蹤每個見證和變數的範圍，就是同一套基本功。