0

0
0

文字

分享

0
0
0

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

翁 昌黎
・2015/02/28 ・2670字 ・閱讀時間約 5 分鐘 ・SR值 536 ・七年級

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 其尺寸仍然是可數無限。突破可數無限的集合運算方式似乎近在咫尺又瞬間擦身而過,這個施洛德—伯恩斯坦定理的證明又暗藏甚麼玄機?就讓我們下回再分解吧!

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

0

1
1

文字

分享

0
1
1
康托爾誕辰|科學史上的今天:3/3
張瑞棋_96
・2015/03/03 ・960字 ・閱讀時間約 2 分鐘 ・SR值 559 ・八年級

對數學家與哲學家而言,無限大就像個怪物。哲學碰上無限就會產生一堆悖論,例如芝諾悖論、無限大飯店、⋯⋯等等。無限大更是在數學製造了一堆矛盾,例如:無限序列 1 – 1 + 1 – 1 + ⋯⋯的總和到底是等於 0 或 1、或是 1/2?我們可以讓自然數與平方數的數列彼此一一對應(1→1, 2→4, 3→9, ⋯⋯),但平方數顯然又只占自然數的一小部分,那麼自然數的集合究竟比平方數的集合大還是兩者一樣大?

面對這些令人困惑的矛盾,大家的共識就是:無限只能當作一種概念,一個持續的未完成狀態,所以不能計算或比較大小。數學王子高斯就嚴肅表示:「我反對將無限量看成真實的實體來運用,這在數學之中是永遠不被允許的。無限只是一種說法而已。」直到不信邪的德國數學家康托爾出現,祭出集合論這面照妖鏡,才讓無限這個怪物現出原形,扭轉了千年以來對於無限的認知。

康托爾創立集合論,將無限當成可以一一對應其中元素的集合來處理。經由他無懈可擊的證明,無限的確有大小等級不同之分。自然數、平方數、整數、有理數的集合都是「可數無限」,屬於最初級(第零級)的無限,它們都一樣大。但無理數、實數的集合就是另一種「不可數無限」,硬是比第零級的無限還大,屬於第一級的無限。不只如此,還有更大的無限,一級一級往上沒有止盡。也就是說,世人以為無限是一隻神秘的怪物,但康托爾卻撥開迷霧,指出無限其實是一群數不完的大小不同的怪物。

然而康托爾天才般的洞見卻被當時的學界權威批評為「並無重要意義」、「騙局」。康托爾一方面承受極大的壓力,一方面又受困於自己提出來的疑問──存不存在大小介於第零級與第一級之間的無限?他試圖證明並不存在這樣的無限集合(稱為「連續統假設」),但搏鬥多年卻始終未果,乃數度精神崩潰住院治療。到了一次大戰,因實施食物配給而健康更加惡化,終於在 1918 年於精神療養院中過世,享年 73 歲。

如今康托爾的貢獻已被普遍認同,他開創的集合論已成為現代數學的基石。大數學家希爾伯特曾捍衛地宣稱:「沒有人能將我們從康托爾為我們創造的樂園中驅逐出去」。他的連續統假設仍列於有待解決的 23 個最重要的數學問題之首,等待後人征服。

本文同時收錄於《科學史上的今天:歷史的瞬間,改變世界的起點》,由究竟出版社出版。

張瑞棋_96
423 篇文章 ・ 659 位粉絲
1987年清華大學工業工程系畢業,1992年取得美國西北大學工業工程碩士。浮沉科技業近二十載後,退休賦閒在家,當了中年大叔才開始寫作,成為泛科學專欄作者。著有《科學史上的今天》一書;個人臉書粉絲頁《科學棋談》。

0

0
0

文字

分享

0
0
0
公設化集合論的奧秘(13) 追查有理數失蹤之謎
翁 昌黎
・2015/02/27 ・1766字 ・閱讀時間約 3 分鐘 ・SR值 528 ・七年級

國民法官生存指南:用足夠的智識面對法庭裡的一切。

credit:wiki
credit:wiki

「一尺之棰,日取其半,萬世不竭」       莊子

如果我們把莊子以上的想法稍作改變,不要把木棍每天鋸掉一半,而是在本該鋸掉的地方刻上一道細線,這樣一直刻劃下去,有一天是否能把木棍劃滿呢?如果你拿一枝美工刀實際去做的話,幾秒鐘刻上一道刀痕,估計木棍很快就會佈滿刀的刻跡,因為刻痕是有寬度的。若是刻痕真能像幾何學所說的那樣寬度等於零的話,直覺上木棍或許不會被蓋滿,在取1/2不斷縮小的眾多段落裡總是會有間隙存在。

但如果增加刀痕的切刻密度,比如把棍子按1/3比例切刻,然後將被切成1/3的部分再切1/3這樣無限執行下去呢?若將1/4, 1/5, 1/6, …, 1/n , … 的切刻比例都加進來如法炮製呢?你的直觀還能那麼確定棍子不會被刻痕佈滿嗎?

讓我們回到那個由無限顆白沙顆粒所形成的海灘,還有那條發出橙色亮光的實數線,數學證明告訴我們,這些與有理數等量的沙粒確實無法填滿實數線(請參考《公設化集合論的奧秘(11)》),同理以上的方法也無法將刻痕佈滿莊子家那根棍子。

僅管我們在《公設化集合論的奧秘(11)》中已經證明實數是不可數的,也就是說實數比有理數多,但我們並不清楚實數到底比有理數多多少?將這些美麗的白沙填充到橙色的實數彩虹時,彩虹到底變白了多少?是整個實數彩虹都呈現灰白狀,還是只有白色的帶狀,或者更像量子力學的双狹縫實驗中的細干涉條紋線呢?

答案我們前文已經說過,實數彩虹完全不會改變顏色,那似乎暗示無限顆白沙就像憑空消失一樣,即使請菩提祖師加持讓每顆沙粒再變成無窮的沙粒也於事無補,無數美麗的白沙消失在實數線的橙光之中。於是我們面臨一宗最詭異的疑案,這些數量等同於一切有理數的美麗白沙為何消失了?它們跑到哪裡去了?有數學上的方法能說明這個怪異現象嗎?

要破解這件玄案,首先要知道無數白沙失蹤等同於有理數失蹤,因為它們是等量的,有著相同的基數。所以我們的目標是要追查失蹤的有理數,看它們為何消失,但一個好的偵探不會被表象蒙蔽,或許這些有理數並沒有消失,只是被藏了起來罷了,甚麼情況下能將這麼多的東西藏起來?除非有比它們多得多的東西將其淹沒,所以我們才看不到有理數,讓我們來驗證這個猜測是否屬實。

由於已經證明整體實數跟(0, 1)區間裡的實數一樣多,所以只要處理開區間(0, 1)就相當於處理了整個實數。假設這個區間內所有有理數的集合為S,因為其尺寸為可數無限,所以我們可以將其成員編碼成S={x1, x2, x3,…},S就是灑到實數線上的沙粒集合。接著找一段1/10長的開區間I1將第一粒沙x1包住,然後用更小的一段 1/100長的開區間I2將第二粒沙x2包住,依此類推,我們用10n 長的開區間In來覆蓋第xn粒沙。這樣做的結果就是用來覆蓋S元素的區間總長必定大於x1, x2, x3, …的總和,因為每段In總是把某個xn覆蓋住。

現在我們把所有的In加起來看看占有多少比例,它等於:

1/10 + 1/102 + 1/103 +… + 1/10n   +… = 1/9

用簡單的等比級數公式就可以得出以上的結果。這個結果令人驚訝,因為我們發現沙粒的總和S頂多只占有區間的1/9,其餘的部分都不屬於S,合理的猜測就是8/9以上的區域屬於無理數的領地。

但更驚爆的事情還在後面,第一個開區間I1的長度1/10是我們任意選取的,我們可以選得更小,比如說1/102同樣可以包住x1,之後的區間長度也是依比例遞減。這樣覆蓋S所有元素的開區間總合就等於:

∑In = 1/102 + 1/103 + 1/104 … + 1/10n   +… = 1/90

經過這個調整,有理數S所占的比例只剩不到1/90,其餘89/90以上的區域都是無理數。

敏銳的讀者已經發現,我們可以將選取的覆蓋區間不斷縮小,因而有理數集合S所占實數區間(0, 1)的比例也就會依照1/900, 1/9000, 1/90000逐漸下降而最後趨近於0。難怪那麼多沙粒都消失不見,原來與實數相比它們所占的比例是零。

這是甚麼意思呢?這是不可數無限集合最深奧難解的性質之一,雖然同屬於無限集合,但若把有理數全數放到實數堆裡的話,它們將完全被淹沒而看不到蹤影。有理數的「數量」跟實數相比實在太過渺小,幾乎可以忽略不計,這就是整個白沙星球「失蹤」的真正原因。

經由以上的推演,我們不但證明了實數比有理數多,還進一步知道由於它們之間懸殊的比例,導致有理數無法被觀察到而造成失蹤的假象。那麼這種遠遠超出我們直觀經驗的不可數無限集合 R和由全體自然數集合N所形成冪集合 P (N) 是否一樣大呢?我們能找到方法來證明它們誰大誰小嗎?這只有等下回再分解了!

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

0

0
0

文字

分享

0
0
0
公設化集合論的奧秘 (3) 摧毀傳統集合論的重磅炸彈 — 羅素詭論
翁 昌黎
・2014/12/09 ・1959字 ・閱讀時間約 4 分鐘 ・SR值 535 ・七年級

國民法官生存指南:用足夠的智識面對法庭裡的一切。

伯特蘭·亞瑟·威廉·羅素,第三代羅素伯爵 photo source:wikipedia
伯特蘭·亞瑟·威廉·羅素,第三代羅素伯爵
photo source:wikipedia

文 / 翁昌黎(《孔恩vs.波普》中文譯者)

在數學和邏輯的領域裡有許多詭論存在,所謂詭論就是那種正反答案都有道理,但顯然不可能兩個答案都對。比如我對你說: 「我正在說謊」,如果這句話是真的,那表示我說的是謊話,因此它就是假的。如果這句話是假的,那表示我說了實話,因此這句話又是真的。像這種真假莫辨的語句就構成了詭論。

著名的羅素詭論(Russells paradox)就是一個具有簡單的數學形式,卻帶有強大的破壞力,它困擾了20世紀早期的許多數學家和邏輯學家。雖說羅素詭論終結了被稱為素樸集合論(naïve set theory)的早期數學理論,但這顆炸彈卻促成了以徹美洛為先導的公設化集合論。如果以徹美洛1908年的論文作為分水嶺,那麼素樸集合論的存活期限大約在1870年到1908年之間。

早期的素樸集合論只有兩個公設,一個就是之前談到過的外延公設,它規定兩個集合在什麼情況下可被視為等同的條件—如果它們有相同的成員的話,這一公設仍然被保留在ZF裡。另一個稱之為概括公設(Axiom of Comprehension),它的數學陳述極為簡單,但惹出大麻煩的正是這個公設。它說如果P是一個性質,那麼具有性質P(x) 的所有物體x就構成一個集合,寫成Y = {x: P(x)} 。

但嚴格來講,所謂具有性質P(x)這個表述顯得模糊而又不夠具體,什麼樣的東西可以作為P(x)呢? 它又具有什麼性質? 如果稍加思考我們還是可以從直觀上掌握它的一些特徵。比如我們將範圍限定在自然數,那所有偶數所成的集合就可以寫成E = { x : x 是偶數}。在這個例子裡性質P(x) 說的就是「x 是偶數」,它利用偶數這個性質建造起了E這個集合。來看另一個例子, 所有質數所形成的集合P = { x : x 是質數}= {2, 3, 5, 7, 11…}。這裡所謂的性質P(x)指的就是「x是質數」。

按照上面所舉的兩個例子來看,概括公設還挺好用的,只要將想要的東西用某個性質描述鎖定,然後將符合這個性質的東西通通抓出來放到我們設想的集合裡就萬事大吉了。多麼美妙簡潔的方法,多麼清楚明瞭的數學形式! 從表面上看不到任何破綻也沒有違背常理之處。但到了1901年,羅素不知怎麼地突發奇想,把一池春天的水硬給弄皺了。這個看起來簡單,稍嫌詭異但又不太起眼的東西,最終卻將原先被認為四平八穩的集合論體系給徹底掀翻,所以千萬不要以貌取人。

羅素詭論有何神奇魔力? 它就是在概括公設的許可下利用上述的性質P製造出來的集合,其數學形式相當簡單,依據概括公設,我們可以設計出一個集合R = { X : X X}。這個外表平凡無奇的集合乍看之下讓人有點摸不著頭腦,X ∉ X到底是什麼意思? 如果用麻袋隱喻來理解的話,它說的不就是一個集合不能把自己裝進去嗎,這不是理所當然嗎? 一個袋子怎麼能夠把自己當成元素放進去呢? 這不就像一條蛇想把自己吞進去? 這個看似廢話的集合到底能有什麼破壞性?我們就來研究羅素無聊時製造出來的這個魔怪到底具有什麼性質吧。

用我們之前說過的協會比喻就容易理解了。剛剛說過當時的素樸集合論只有兩條公設—外延公設概括公設,但這兩條「協會登記管理辦法」並沒有說不能把自己登記為自己的社團成員,所以理論上可以存在這樣型態的集合: 中區科學協會 = {中區物理協會,中區生物協會,中區化學協會,中區科學協會} 。像這種把自己登記為自己成員的社團組織就是ā = { X : X X},而不具有這種型態的集合,也就是成員中不包含自己在內的集合就是羅素的集合R = { X : X X}

事情到此似乎已經圓滿解決,羅素製造出來的這種集合顯然沒有異常。雖然「法規」沒有禁止,但一般情況下把自己登記成自己的成員似乎顯得相當怪異,又不是湊人頭黨員,還把自己放進去多數一個人頭,這不是欺詐嗎! 羅素所列舉的性質P(X ∉ X)顯然更符合我們對集合的常識要求,尤其是麻袋比喻下的集合。

但正所謂生死一線間,如果我們繼續往下追問,剛剛羅素的那個集合R是否是它自己的成員呢? 如果是的話則必然R ∈ R,因為R也必須在自己的成員當中。既然它在這個集合裡,那根據定義就要滿足性質P,也就是P(X ∉ X),我們得到R R這個結論。

糟糕,自相矛盾了! 那表示R不能是自己的成員,必須把它趕出這個集合,因此R R才對。可是根據羅素集合的定義R = {X: X X} ,R本身又滿足這個集合所具有的規定,因此必須把R看成是自己的成員,所以R ∈ R。這下可真是裡外不是人了,不論我們把R怎麼擺放,都會得出矛盾,走到這進退維谷的田地,看來原來的素樸集合論是徹底沒救了。

問題到底出在哪裡? 整套現代數學地基的集合論,居然被這個貌不驚人的詭論搞得灰頭土臉瀕臨破產,應該如何解決呢? 只有等下回分解了。

延伸閱讀

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