2008年3月20日 星期四

選擇公理

小弟第一次在這個blog貼文,由於小弟還是一位中學生(也是一隻「數海中的迷途小羔羊」),如果有錯請各位不吝更正

最近在和其他人閒談時,明白了選擇公理(Axiom of Choice, AC)為甚麼不能用數學歸納法(Mathematical Induction)去證明,特意在這兒貼出來和各位像我一樣的「數海中的迷途小羔羊」分享。 :P

首先,讓我大概說一下甚麼是選擇公理,選擇公理的正式說法是:
設X是非空集合的集合。則我們可以從X中的每個集合中選擇一個元素

簡單一點來說,如果你手上有一堆集合,而且你肯定每一個集合都包含至少一個元素,那麼你一定可以在每一個集合抽一個元素出來,而不用知道每個集合的其他資訊。

說到這裏,大家可能已經在抱怨:這不是很明顯嗎?如果你有幾個籃子,每籃內都至少有一隻雞蛋,我們當然可以在每一個籃子抽一隻雞蛋吧!但是數學中一切命題都需要證明,這個也不應例外。現在大家又可能想出了以下這個證明:

1.設P(n)為命題“在n個非空集合中可以在每個集合中抽一個元素出來”;
2.考慮P(1),我們可以在那一個非空集合中任意抽一個元素出來,故P(1)成立;
3.假設P(k)對於一些自然數k成立,考慮k+1個非空集合,由歸納假設知我們可以在頭k個集合中抽一個元素出來,而我們又可以在第k+1個中任意抽一個元素出來,故P(k+1)成立;
4.由數學歸納法原理知P(n)對一切自然數成立;
5.證明完畢。

這個也是我初次聽到選擇公理時想到的「證明」,然而,以上的「證明」有兩個大漏洞,第一個是:甚麼叫「任意抽一個元素出來」;第二個是:對一切自然數n證明了選擇公理,代表選擇公理對於一切情況成立嗎?


先說前者,「任意」這個字用於集合論之類的數學基礎時是十分含糊的,數學上不存在一個明顯的函數f(X),可以在任何一個非空集合X中準確地抽出一個元素。例如定義f(X) = (X中最小的元素)吧,讓我們考慮X’為0至1中所有實數但不包括0和1,容易看到X’中不存在最小的元素,f(X’)沒有定義!又或者考慮一下「古今中外所有的流浪貓」或是「世界上所有曾經/現在/將會看這篇文章的人」之類的集合,你便明白是否存在所謂的選擇函數,並不是一件容易證明的事。

再說後者,使用以上的數學歸納法時,我們假設了可以把一大堆集合排成一列,或至少貼上1,2,3,…的編號。然而,我們知道自然數是一個可數(countable)的集合,但如果我們遇上一堆數目是不可數(uncountable)的集合時,數學歸納法的正確性是值得商榷的。可惜的是,這樣的一堆集合是存在的,例如把每一個正實數x對應一個集合{-x,x}並把所有集合組成一個新的集合,康托(G . Cantor)證明了,以上集合的數目是多於自然數的,即是把它們逐一加上唯一的正整數編號是不可能的。

事實上,在二十世紀中期,科恩(P . Cohen)用一種叫力迫法(forcing)的技巧,證明了選擇公理是不能用策梅羅-弗蘭克爾集合論(ZF,現代數學的基礎之一)內其他公理證明;但又由於選擇公理的表達非常明顯,很多數學證明是在它成立的前提下做的,所以我們唯有把它當成一條公理使用。

說回來,如果選擇公理已經成為公理,又是如此明顯,為甚麼我們還要花時間討論這條「公理」的正確性呢?一個很重要的原因,是如果選擇公理成立,會推出一些看似瘋狂的結果,幾個例子包括:

1. 巴拿赫-塔斯基悖論:存在一個方法,可以將一個三維實心球分成有限個部分,然後通過旋轉和平移,重新組合為兩個半徑和原來相同的完整的球;
2. 塔斯基分割圓問題:存在一個方法,可以將平面上的一個圓分割成有限多塊,然後通過平移,重新拼合成面積相同的正方形;
3. 在以下情況中,存在一個策略令只有有限個犯人不被釋放:

無窮個犯人面向數軸的正方向依次就座,第i個犯人坐在數軸上座標為i的地方,他可以看見所有座標大於i的囚犯頭頂上的帽子。每個囚犯都戴上了黑色或白色的帽子,然後每個犯人依次猜測自己頭上的帽子顏色,猜對了的予以釋放。犯人們可以事先商量,而且他們都知道自己的座位編號,但犯人們不能聽到其他人的猜測;同時,我們假設每個犯人都是聰明和有無窮記憶力的。

時間所限,有關第三個例子中的策略,我留待稍後才再討論。

4 則留言:

Dan 提到...

補充一下,axiom of choice 其實在很多範疇也需要應用,如Banach algebra,而這些algebra得出的結果正是某些量子力學理論的根基...

如果axiom of choice有Banach-Tarski 等 Paradox 的出現,數學家絕對有必要釐清其歧義,否則量子力學的理論基礎也岌岌可危。

(我好像踏過界了,如有錯誤請賜教)

ychjae 提到...

我的想法是,這些paradox應該不會和已有的東西有矛盾(否則我們可以透過其他公理去反證它,這和AC與ZF獨立的事實矛盾!),而只是和我們的「常理」矛盾,所以不見得有問題。
事實上,量子力學本身極大部份都是和「常理」矛盾,但當中有一部份已經為實驗證實,至少,你我所用的電腦或多或少都是量子力學的產品。

Kenneth 提到...

可否這樣看?
AC 其實在 N 的範圍內是可以用 ZC 證的,即
[wiki]Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box.[/wiki]

Singmay 提到...

“選擇公理” 想得多真的會令人發癲,Jerry Bona的話實在合理得太容易令人相信
"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"
第三個例子很有趣,期待著你的答案!