公設化集合論的奧秘(14) 笛卡爾乘積與可數無限

credit:wiki

我們曾經用等量於自然數尺寸的集合企圖製造更大的集合，結果發現即使把這種尺度的集合聯集無數次（可數有限次） ，得到的還是可數無限集合，這就是說聯集這種運算無法讓N突破其尺寸限制。當所屬集合之間沒有共同元素，也就是它們互不相交時，聯集就相當於加法，所以我們也可以說用加法這種運算無法增加可數無限集合的尺寸，詳細證明過程請參考《公設化集合論的奧秘 (10)》。既然加法不行，那很自然會想到乘法或許可以突破這種限制，因為在算術的領域裡，乘法得出的結果要比加法來得大。

接下來就來尋找這種乘法吧。但有甚麼數學構造相當於集合的乘法呢？相信很多人馬上會想起有個外型看起來很像乘法的東西，那就是笛卡爾乘積（Cartesian Product）：

定義4：對任意集合A和B，我們將笛卡爾乘積A × B定義為集合 {z〡∃a ∃b (a∈A ∧ b∈B) ∧ z = (a, b)}。

仔細一看，這個看起來很熟悉的笛卡爾乘積不就是之前介紹過的序對(a, b)所構成的集合嗎？這個笛卡爾乘積的前半部元素從A得來而後半部的元素則從B而來。

雖然這個定義就像我們所熟知的平面座標系一樣清楚明白，但對真正公設化集合論的內行人來說，她會馬上提出一個質疑，那就是雖然A和B都是集合，但我們無法確定A × B是否也是集合，所以必須在公設系統之內驗明正身。我們之前給過的序對定義為：

定義2： (a, b)= {{a}, {a, b}}

可參考《公設化集合論的奧秘 (8)》

由於a和 b分別屬於A和B集合，所以a, b ∈ A ∪ B。這樣的話，以a和b為元素所形成的集合就會成為A ∪ B的子集，也就是 {a, b} ⊆A ∪ B。而冪集合P(X) 的定義剛好是把X的子集合拿來當成P(X) 的元素，所以我們把A ∪ B看成P(X) 中的X就會得到

{a, b}∈ P (A ∪ B)

同理，更小的集合{a}也是A ∪ B的子集合，{a} ⊆A ∪ B，所以

{a}∈ P (A ∪ B)

以上用紅字標註的兩個集合{a , b}和{a}既然都是P (A ∪ B)的成員，那表示它們兩者所形成的集合{{a}, {a , b}}必定是P (A ∪ B)的子集，也就是

{{a}, {a, b}} ⊆ P (A ∪ B)

仔細觀察會發現左邊的部分正是序對(a, b)，也就是笛卡爾乘積的構成元素z 的基本形態，現在終於知道我們為何要不辭勞苦地繞那麼一大圈，為的就是要得出這個序對的形態，然後才能判別它是否符合集合的合法身分。

把這些定義關係整理一下可以得到：

z = (a, b) = {{a}, {a, b}} ⊆ P (A ∪ B)

再運用一次冪集合到P (A ∪ B)身上，根據它把子集當成元素的規定，我們發現

z = (a, b) = {{a}, {a, b}} ∈ P (P (A ∪ B))

終於把笛卡爾乘積的「真身」找到了，它就是構成A × B的集合形態，把A和B的聯集連續取兩次冪集合之後得到的P (P (A ∪ B))就是以z為元素的笛卡爾乘積。

現在只剩下最後一步確認程序了，那就是P (P (A ∪ B))是否為集合？由於A和B都是集合，所以根據ZF5聯集公設（請參考《公設化集合論的奧秘 (5)》），兩個集合的聯集也是集合，所以A ∪ B是集合沒錯。

再根據ZF7冪集合公設 (請參考《公設化集合論的奧秘 (7) 》) ，把一個集合X的所有子集蒐集起來所構成的類P(X)也是集合，所以P (A ∪ B) 是集合沒錯。(關於類的概念請參考《公設化集合論的奧秘 (12) 》) 現在讓我們根據ZF7把這個程序再 一次用到P (A ∪ B) 身上，結果發現P (P (A ∪ B)) 也仍然是集合。到此我們可以確定笛卡爾乘積A × B 為集合無誤，定義4完全符合ZF公設的「法定」標準。

確定了A × B為集合之後，我們才能放心大膽地測試由自然數集合N所構成的笛卡爾乘積N × N的尺寸是否能突破可數無限的限制，如果N × N連集合都不是的話，那我們就不用這麼辛苦白忙這一大圈了。

最後讓我們檢查一下笛卡爾乘積A × B是否真正捕捉到乘法算術的本質，就用有限集合來實驗一下吧。假設A和B都是由3個元素所構成的集合，比如A = {a, b, c} 而 B = {1, 2, 3} ，那麼A × B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)} ，點算一下剛好是9個元素，等於3 × 3，確實是乘法沒錯。

接下來能否找到N × N與N 之間的大小關係呢？我們發現可以找到一個一對一函數從N到N × N，只要取：

ƒ : N → N × N

n → (n, 0)

就成了。可惜ƒ不是映成函數，因為比如(17, 3)這個序對就不在ƒ的值域（range）裡，因此我們目前無法確定N × N 和N是否等量。但我們觀察到一個令人驚喜的現象，那就是當函數是一對一而沒有映成時，不就表示前面的集合N小於或等於後面的集合N × N嗎？因為不映成表示後面的集合N × N 存在著配對之後剩餘的元素，因此它有可能比前面的集合來得大。

於是我們據此做出一個集合之間小於或等於的定義：

定義5：如果在集合A和B之間存在一個一對一函數  ƒ : A→B，則說A小於或等量於B，寫成A ≤ B。相當於〡A〡≤  〡B〡，也就是A的基數小於等於B的基數。

根據以上定義，前面的函數ƒ告訴我們〡N〡≤  〡N × N〡，但若要確定〡N × N〡真的大於〡N〡的話，我們還需要證明N和N × N不等量才行。也就是若〡N〡≤ 〡N × N〡，則必須加上N和N × N不等量這個條件才能說〡N〡<〡N × N〡。

在這緊要關頭我們卻發現有一個函數g：N × N → N恰好是一對一函數，這怎麼可能呢？才剛剛發現〡N〡≤  〡N × N〡，為何半路又殺出一個搗蛋的函數g？口說無憑，我們就把函數g亮出來吧：

g：N × N → N

(n , m) → 2ⁿ3^m

有證據證明這個函數是一對一嗎？有的，根據算術基本定理，任何大於1的正整數都可以唯一分解為依序排列的質數乘積模式如：P₁^aP₂^bP₃^c…P_k^k…，其中P₁ < P₂ < P₃< P_k <… 為由小到大的質數，而a, b, c, …, k 等為正整數。由於值域裡的2和3正好是最小的兩個質數，因此一個序對(n, m)決定一個唯一的2ⁿ3^m值，故知道函數g為一對一函數。根據定義5，〡N × N〡≤ 〡N〡。於是我們同時有〡N〡≤ 〡N × N〡和〡N × N〡≤  〡N〡兩種情況。

如果是任意兩個實數r₁, r₂的話，如果r₁≤ r₂ 且 r₂ ≤ r₁則r₁ = r₂。但對於包含N在內的任意集合來說，以上的算術規則是否仍然正確？也就是如果

〡N〡≤ 〡N × N〡且〡N × N〡≤  〡N〡的話，

〡N〡=〡N × N〡是否成立？

答案是肯定的，這就是著名的施洛德—伯恩斯坦定理（Schröder-Bernstein theorem），它是關於集合尺寸的一個非常重要的定理，我們目前尚未證明它，所以只能暫時假裝它是對的。但施洛德—伯恩斯坦定理一旦成立，我們剛才的美夢就全泡湯了，原本期待笛卡爾乘積可以突破可數無限的藩籬，現在卻得到〡N〡=〡N × N〡這個結論。

不僅如此，我們還能夠進一步證明推廣到任意整數n的笛卡爾乘積C₁ × C₂ × C₃ × C₄ × … × C_n 其尺寸仍然是可數無限。突破可數無限的集合運算方式似乎近在咫尺又瞬間擦身而過，這個施洛德—伯恩斯坦定理的證明又暗藏甚麼玄機？就讓我們下回再分解吧！