集合的大小：基數（勢）－劉應興的部落格

集合的大小可能不是重要的課題，不過有時它也是一個被關心的課題。排列組合可說就是關於集合元素個數的算術，測度論是以一個宇集 (universal set) 為基礎討論如何賦予其子集一個「大小」測度的課題。本文要談的，所謂集合大小類似排組數學中的元素個數，只是真正的重點在元數個數是無限的情形。

我們知道空集合 { } 沒有任何元素，或說有 0 個元素；{1}, {a}, {{}} 都是含有一個元素。我們可把一個集合有幾個元數稱之為此集合的「基數 (cardinal number)」, 集合 A 的基數可以用 #A 來表示，兩集合 A, B 有一樣多的元素，也就是兩集合基數相等，#A = #B。如果 A, B 是有限集合，也就是 #A, #B 是有限值，則 #A = #B 的充要（充分且必要）條件是存在 A, B 之間一個一對一且映成 (one-to-one and onto) 的函數 f: A → B。因此，如果存在 A → B 的一對一函數，就是 #A ≦ #B。那如果集合的元素個數無限呢？直接用一個 ∞ 表示嗎？集合論不這麼看待，例如自然數集 N = {1,2,3,...} 或 (0,1,2,...} 與實數集 R 就是有不同的基數，或說其「勢 (cardinality)」不同。為此，我們定義何謂兩個集合有相同基數或相同的勢：

　　兩集合 A, B 之間若存在一個一對一且映成的函數 f: A → B,
　　則稱兩集合等勢，或兩集合基數相等，#A = #B。
　　若存在 A → B 的一對一函數，就是 #A ≦ #B；
　　若 #A ≦ #B 但 #A≠#B 則 #A < #B。

等勢是個對等關係，所以兩集合之基數關係只能 #A < #B, #A = #B 或 #B < #A 三者恰一成立。

若集合 A 是集合 B 的子集，顯然 #A ≦ #B; 但其逆命題 (converse) 並不成立。另，集合運算與基數存在下列關係：

#(A∪B) = #A + #B - #(A∩B)
#(A×B) = (#A)．(#B)
#(A^B) = (#A)^(#B)

其中集合 A×B 則是兩集合的笛卡爾積 (cartesian product)；而 A^B 代表從 B 到 A 的所有函數所形成的集合。若 A 非空，則因 { }^A = { }, 故 0^n = 0, 不管 n 是正整數或無窮集的基數；但 0^0 則被定為 1，n^0 也是 1。

自然數集 N 做為一個基準，其基數被表示為 $\aleph _{0}$ , 唸 aleph-0, 與 N 等勢的集合被稱為可數無限集合；比此小的基數都是 0 或正整數，有非負整數為基數的集合都是有限集合，有限集合與可數無限集合並稱可數集合；基數比 $\aleph _{0}$ 大的集合是不可數（無限）集合。

有限集不可能與其真子集等勢，但無限集合卻總是與其許多真子集都等勢。例如 {n+1; n in N}, {2n; n in N}, {n^2; n in N} 都與 N 等勢。另外，我們可以證明 N × N 與 N 等勢，意思就是 N^2 是可數集，也就是可以把 N^2 的元素一一排列出來而不會遺漏：

N^2 = {(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...}

但實數線 R 或單純看區間 (0,1) 卻是不可數的。事實上 (0,1) 與 2^N 等勢。首先，(0,1) 內每個元素可以用任意整常數進位制小數表示，例如二進制或十進制。假設二進制，則除了有限位數小數有兩種表現式如

0.1011 = 0.10101111...

以外，都有唯一的表示式，如

0.1010101... 或 0.1010010001...

分別是二進位循環與不循環小數的例子。如果把前述有限小數表示法拿掉，則二進位的小數表示法是唯一的。這也就是說：所有二進位無窮小數所形成的集合與 (0,1) 等勢。所有二進位小數只有可數無限多，因此可以說 2^N 與 (0,1) 或 R 等勢，記為 $c=2^{\aleph_0}$ 。假設 c = $\aleph _{0}$ , 即 (0,1) 可數，則前述二進位無限小數是可數的，令 Xn 是 (0,1) 的第 n 個元素，n 是自然數，利用諸 Xn 的二進位小數展式建立一個二進位小數展式 Y 如下：

若 Xn 的第 2n-1, 2n 位小數是 01, 則 Y 的對應位置設為 10；否則設為 01。

則 Y 的值與每個 Xn 都不等，但顯然 Y 在 (0,1) 中，也就是 {Xn; n in N} 並沒有列盡 (0,1) 的元素，換言之，#N < #(2^N) = #(0,1)。R 或 (0,1) 的基數也記為 $c=\aleph_1$ 。有一個假說或稱猜想，名為「連績統假說 (continuum hypothesis)」:

若 #N ≦ #S ≦ #R, 則兩不等式之一成立等式。

換言之，不存在一個基數大於 $\aleph _{0}$ 又小於 c。更廣義的連續統假說是：

對任意 α， $2^{\aleph _{\alpha }}=\aleph _{\alpha +1}.$

其中 $\aleph _{0}<\aleph _{1}<\aleph _{2}<...$ 代表一系列逐次增大的基數，沒有任何一個集合的基數嚴格的落在此序列連續兩個基數之間。由於對任意集合 A 都有 #A < #(2^A) = 2^#A, 這也暗示不存在一個最大的基數，同時也暗示不存在一個包含一切的集合。

如何證明「對任意集合 A 都有 #A < #(2^A)」? 顯然 #A ≦ #(2^A), 需要證明的就是 #A ≠ #(2^A), 也就是不存在 2^A 和 A 之間的 1-1 對應關係（即一對一且映成的函數關係）。仿上面證明 2^N 不可數的方法，2^A 的元素都是 A 映至 {0, 1} 的函數。設 f: A → 2^A 是一對一函數，取 2^A 的一元素 y, 定義如下：

　　對 A 中任意 a，設 f(a) = x, 若 x(a) = 0 則取 y(a) = 1, 否則取 y(a) = 0。

如此一來，對任意 a 都有 y ≠ f(a), 因為 y(a) ≠ (f(a))(a), 也就是說 f 不是映成的。