Hilbert旅館的故事——集合的勢（二）

03-04

一家擁有無窮多個（可列多個）客房的旅店每個房間恰能住一位旅客，並已經客滿。

當日又有一位旅客投宿…

於是旅館主人把1號房間的旅客移到2號房間，2號房間的旅客移到3號房間，3號房間的旅客移到4號房間等等，這樣繼續移下去。

這樣一來，新客就被安排住進了已被騰空的1號房間。

事實上。它表述的是集合 $mathbb{Z}^+={1,2,3...}$ 與集合 $mathbb{Z}^+-{1}={2,3,4...}$ 具有「同樣多的」元素。

「禍」不單行，又來了可數多位旅客投宿…

於是店主東把1號房間的旅客移到2號房間，2號房間的旅客移到4號房間，3號房間的旅客移到6號房間，如此等等，這樣繼續下去。現在，所有的單號房間都騰出來了，新來的無窮多位客人可以住進去。

事實上。它表述的是集合 $mathbb{Z}^+={1,2,3...}$ 與集合 $2mathbb{Z}^+={2,4,6...}$ 具有「同樣多的」元素。

「屋漏偏逢連夜雨，船破又遇頂頭風」緊接著發生了更為嚴重的情況，來了無窮（可數）多個具有無窮（可數）多名遊客的旅遊團，這便如何是好？

店主人把#1房的客人移到#2房，把#2房的客人移到#4房，#3房的客人移到#6房，等等，所有奇數號的房間全部騰空

第一個旅遊團遊客住的房間編號為 $3,3^2, 3^3, 3^4,$ ……

第二個旅遊團客人住的房間編號為 $5,5^2, 5^3, 5^4,$ ……

接著是 $7, 7^2, 7^3, 7^4,$ ……

......

一般地，設第 $m$ 個奇素數是 $p_m$ ，則第 $m$ 個旅遊團的成員依次住在 $p_m , p_m^2, p_m^3, p_m^4,$ ……

這樣不僅安排了無窮多個旅遊團的住宿，而且還空出了很多房間。

事實上。它表述的是集合 $mathbb{Z}^+={1,2,3...}$ 沒有比集合 $mathbb{Z}^+ imesmathbb{Z}^+$ 「元素個數少」。

對於一個無窮集合，向其中添加有限個元素，甚至「無窮多個」元素得到的新集合，元素數目不變？！

這事實上就是「從一道概率題到「一一對應」——集合的勢（一）」中介紹的「等勢」概念。

下面給出一些基本結果：

(1) 自然數集 $mathbb{N}={0, 1, 2, …}$ 和整數集 $mathbb{Z}$ 是等勢的。雙射函數為

示意圖如下：

(2) 自然數集 $mathbb{N}={0, 1, 2, …}$ 和集合 $mathbb{N} imesmathbb{N}$ 等勢。

如下圖所示，將 $mathbb{N} imesmathbb{N}$ 中元素排成一個二維表格，

而後沿箭頭方向建立 $mathbb{N}$ 和集合 $mathbb{N} imesmathbb{N}$ 的一一對應關係： $f(x,y)=frac{left( x+y ight)left( x+y+1 ight)}{2}+y$ 。

類似地可以證明 $mathbb{Z}$ 和 $mathbb{Z} imesmathbb{Z}$ 等勢。

(3) 下面討論有理數集合 $mathbb{Q}$ 和整數集合 $mathbb{Z}$ 之間元素「數目」的關係。需要先介紹兩個定義和兩個結果：

定義——假設 $A,B$ 是兩個集合，

(a) 如果存在 $A$ 到 $B$ 的單射，則稱集合 $A$ 劣勢於集合 $B$ ，記作 $Aleq B$ ；或稱 $A$ 的基數小於等於 $B$ 的基數，記作 $|A|leq|B|$ 。

(b) 如果存在 $A$ 到 $B$ 的單射，但不存在 $A$ 到 $B$ 的雙射，則稱集合 $A$ 嚴格劣勢於集合 $B$ ，記作 $A<B$ ；或稱 $A$ 的基數小於 $B$ 的基數，記作 $|A|<|B|$ 。

策梅羅(Zermelo)定理——設 $A,B$ 為任意兩個集合，其基數的關係必符合以下三條之一。

(a) $|A|<|B|$ ；

(b) $|A|>|B|$ ；

（簡單說就是：任意兩個集合的元素數一定可以「比較」）

康托－伯恩斯坦－施羅德(Cantor–Bernstein–Schroeder)定理——設 $A,B$ 為任意兩個集合，若有 $|A|leq|B|$ 且 $|B|leq|A|$ ，則有 $|A|=|B|$ 。

做好了準備工作，下面來證明 $|mathbb{Q}|=|mathbb{Z}|$ 。

(a) $f(x)=x$ 給出了 $mathbb{Z}$ 到 $mathbb{Q}$ 的單射函數，因此 $|mathbb{Z}|leq|mathbb{Q}|$ ；

(b) 每一個非零的有理數都可以表示成 $frac{a}{b}$ ，其中 $ainmathbb{Z}^+$ ， $binmathbb{Z}$ ， $ext{GCD}(a, b)=1$ 。於是可以構造一個單射函數 $g$ ： $gleft( frac{a}{b} ight)=(a,b)$ 、 $g(0)=(0,0)$ 。因此 $|mathbb{Q}|leq|mathbb{Z} imesmathbb{Z}|=|mathbb{Z}|$ 。

於是 $|mathbb{Q}|=|mathbb{Z}|$ 。

(4) 下面暫別自然數、整數、有理數，而先來回答「開區間 $(0, 1)$ 與閉區間 $[0, 1]$ 是否等勢？」

答案是肯定的。主要是處理端點0、1的對應，選擇一個無限序列 $0,1,frac{1}{2},frac{1}{2^2},frac{1}{2^3},frac{1}{2^4},...$ ，建立對應關係：

其他的數對應到自己。

(5) "單位長度的線段上的點和單位大小的正方形中的點哪個多？"

下面證明開區間 $(0, 1)$ 與 $(0, 1) imes(0, 1)$ 是等勢的。

將每一個實數 $xin(0, 1)$ 表示成無限小數形式 $x=0.x_1x_2…x_i…$ （例如0.5可表示成0.4999……，0.781可表示為0.780999……）。

於是可以建立 $(0, 1)$ 與 $(0, 1) imes(0, 1)$ 之間的雙射： $f(0.x_1x_2x_3x_4x_5x_6x_7x_8...)=(0.x_1x_3x_5x_7...,0.x_2x_4x_6x_8...)$ ，因此 $(0, 1)$ 與 $(0, 1) imes(0, 1)$ 等勢。

雙射示意圖：

(6) 實數集與複數集是等勢的。

由 $mathbb{R}approx(0,1)$ 易證明 $mathbb{R} imesmathbb{R}approx(0,1) imes(0,1)$ 。

於是由 $mathbb{C}approxmathbb{R} imesmathbb{R}$ （複平面）、 $mathbb{R} imesmathbb{R}approx(0,1) imes(0,1)$ 、 $(0,1) imes(0,1)approx(0,1)$ 、 $mathbb{R}approx(0,1)$ 即得 $mathbb{C}approxmathbb{R}$ 。

最後遺留的問題是：

1 自然數（整數、有理數）和實數哪個多？

2 什麼樣的集合包含的元素「最多」？

將在下一篇文章中討論。