分享本文至 E-mail 信箱

學術引用格式

MLA (點一下全選)

APA (點一下全選)

EndNote(.enw)

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

credit:wiki

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) → 2n3m

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

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

〡N〡≤ 〡N × N〡且〡N × N〡≤  〡N〡的話,

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

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

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

關於作者

昌黎

中央大學哲學研究所碩士,曾籌劃本土第一場「認知科學與佛教禪修系統」對話之大型研討會,於1995年6月在法光佛教研究所舉行,並發表文章。後隱居紐西蘭,至今已20載。 長年關注「意識轉變狀態的科學」和「意識本質的科學與哲學」問題,曾與大寶法王辯經教授師拿旺桑結堪布成立「大乘佛教禪修研究中心」。其他研究興趣為「唯識學」、「超個人心理學」、「數理邏輯」、「公設化集合論」和「後設數學」等等。