§3-3  不可數的 ℝ

對角線讓有理數整列排得完,那實數呢?0 與 1 之間的實數,有沒有辦法也排成一列——若排不成,兩種「無限」就從此分了層級。

不可數的 ℝ 與 I

班上玩一個小遊戲:每個人在紙上寫一串數字,然後你要當場寫出一串「跟每個人都不一樣」的。人一多,逐張檢查會來不及——但有個穩贏的辦法:看第一張的第 1 個字、故意寫個不同的;看第二張的第 2 個字、再故意不同;第三張看第 3 個字⋯⋯你寫出來的那一串,跟第 n 張至少在第 n 個字上不同,一張都逃不掉。

這一招你其實見過——§3-2 例 4 的對角線。但方向反了:在例 4,對角線是清點的路線,幫我們把 ℚ 整列排完;在這裡,對角線是逃脫的路線——不管誰交出一列實數,沿著對角線逐位避開,就能造出一個名單上沒有的數。同一條斜線,一次證明「排得完」,一次證明「排不完」。

動手前先備妥工具:0 ≤ x ≤ 1 的每個實數都能寫成小數展開 x = 0.a₁a₂a₃⋯,每個 aₙ 是 0 到 9 的一個數字(這件事本身要到實數系建好之後才能嚴格證明,本篇先當作已知)。

同一個數、兩件外衣:有些實數有兩種小數展開——0.1000⋯ = 0.0999⋯ 是同一個數。這不是小事:若只比對「展開的第 n 位不同」,兩個數仍可能相等(外衣不同、本體相同)。等一下的證明特地讓造出來的數避開 0 與 9,讓它只有一件外衣,這個漏洞就堵死了。
THEOREM · CANTOR'S DIAGONAL ARGUMENT
The unit interval I — the set of real numbers x with 0 ≤ x ≤ 1 — is not countable, and therefore neither is ℝ: every enumeration x₁, x₂, x₃, ⋯ of real numbers in I omits at least one member of I.
單位區間 I = [0, 1] 不是 countable:任何一列實數,都必定漏掉 I 裡的某個數。因此 ℝ 也不可數。(本讀本把它立成定理卡;它在通行的教科書編排裡多半寫成 §3 收尾的一段論證,不掛編號——所以你在別處看到它時不會有編號可對。)
正例(對照組):I ∩ ℚ——只收 I 裡的有理數——是 countable 的(ℚ countable,定理 3.3 傳給子集)。反例本體:整個 I 不行。同一段區間,把無理數放回來,「排成一列」就從辦得到變成辦不到——多出來的重量全在無理數上。
PROOF · 對角線論證

先確認 I 不是 finite:I 裡光是有理數就有無限多個(1/2, 1/3, 1/4, ⋯ 兩兩相異)。所以依定義 3.1,剩下唯一要排除的身分是 denumerable——以下用反證法。

證明計畫 · 由所求想起
要證:I 排不成一列。
⇢ 反證:假設排成了 x₁, x₂, x₃, ⋯。
⇢ 沿對角線逐位避開,造一個數 y ∈ I:第 n 位故意與 xₙ 的第 n 位不同。
⇢ 同時避開 0 與 9,堵住「兩件外衣」的漏洞。
⇢ y 不在列上——與「排成了一列」矛盾。
Proof.  Suppose, to the contrary, that some list x₁, x₂, x₃, ⋯ contains every real number of I. Write out a decimal representation for each entry: x₁ = 0.a₁a₂a₃⋯, x₂ = 0.b₁b₂b₃⋯, x₃ = 0.c₁c₂c₃⋯, and so on.
反證的假設先擺上桌:這一列號稱一個不漏。因為每個 I 裡的實數都有小數展開,把每一項的展開逐列寫開,就得到一張往右、往下都無限延伸的數字表——第 n 列是 xₙ 的展開。接下來的論證只看這張表的對角線:第 1 列的第 1 位、第 2 列的第 2 位、第 3 列的第 3 位⋯⋯。
Choose a digit y₁ different from 0, from a₁, and from 9; choose y₂ different from 0, b₂, 9; choose y₃ different from 0, c₃, 9; and continue in this way. Since ten digits are available and only three are forbidden at each step, such choices always exist. Let y = 0.y₁y₂y₃⋯; then y belongs to I.
構造 y:第 n 位要同時避開三個數字——對角線上那一位(跟 xₙ 劃清界線用)、0 與 9(堵外衣漏洞用)。十個數字扣掉至多三個,每一位都還剩至少七個可選,所以 y 造得出來。拿一組具體數字走一遍:若 x₁ = 0.5000⋯、x₂ = 0.3333⋯、x₃ = 0.1428⋯、x₄ = 0.9999⋯,對角線讀出 5, 3, 2, 9,於是可取 y₁ = 6(避開 0、5、9)、y₂ = 4(避開 0、3、9)、y₃ = 3、y₄ = 1——y = 0.6431⋯,正是下圖畫的那一橫列。
Because the digits of y avoid 0 and 9, the number y has exactly one decimal representation. For every n, the n-th digit of y differs from the n-th digit of the given representation of xₙ; since y admits no second representation, this forces y ≠ xₙ. Hence y belongs to I yet appears nowhere in the list — contradicting the assumption that the list contains every member of I. Therefore I is not denumerable, and being infinite, it is not countable. Finally, if ℝ were countable, Theorem 3.3 would make its subset I countable as well; hence ℝ is not countable either.∎
收口分三小步。第一步驗 y 確實不在名單上:y 與 xₙ 的展開在第 n 位不同——但上面的陷阱框提醒過,「外衣不同」還不等於「本體不同」。這時避開 0 與 9 的安排兌現:y 的每一位都不是 0 也不是 9,這樣的數只有一件外衣,於是外衣不同就足以斷定 y ≠ xₙ,對每個 n 都成立。第二步收反證:y 落在 I 裡(每一位都是普通數字、整數部分是 0)卻不在名單上,「一個不漏」破功——所以 I 排不成一列,不是 denumerable;setup 又驗過它不是 finite,依定義 3.1,I 不是 countable。第三步把結論推上 ℝ:因為若 ℝ countable,定理 3.3 會逼得子集 I 也 countable,與剛才矛盾——所以 ℝ 也不可數。
x₁x₂x₃x₄ 0 .0 .0 .0 . 000… 333… 148… 999… 5329 y 0 . 6431… 避開紅字與 0、9 y 與第 n 列至少在第 n 位不同

這張圖在證 y 為什麼必定逃脫:紅色對角線讀出每一列的「查核位」5, 3, 2, 9,藍色的 y 在每個查核位都故意選了不同的數字(並且避開 0 與 9,讓自己只有一種展開)。於是 y 與 x₁ 差在第 1 位、與 x₂ 差在第 2 位⋯⋯名單再長,每一列都至少有一位抓不住它。

I 與 ℝ 都不可數。「無限」從此分成兩層:ℕ、ℤ、ℚ 住在數得完的一層,ℝ 住在數不完的一層。
一條先押著的公理:反過來的方向也值得知道——任何無限集合,都包含一個 denumerable 的子集。這句話是「選擇公理」的一個弱形式,本讀本把它當作暫時的公理接受,不做證明。它的意思是:denumerable 是無限之中最小的層級——任何無限集至少裝得下一份 ℕ 的複本,而本篇證明了 ℝ 嚴格超出這個層級。
—— 第三階段到此結束,整個 §3 收工 ——

導論三節到此全部走完:集合的語言、函數的機制、以及今天的結論——無限有層級,ℚ 數得完而 ℝ 數不完。這道鴻溝正是下一章的入口:實數究竟比有理數多出了什麼?§4 起,我們動手把 ℝ 的性質一條一條立成公理。閤上螢幕,起來伸展一下肩頸和手腕,喝口水再繼續。臨走前把旅館的故事說完:可數多輛滿載的巴士都住得下的無限旅館,來了實數團就只能掛出客滿——今天你親眼看過原因了。