小弟第一次在這個blog貼文，由於小弟還是一位中學生(也是一隻「數海中的迷途小羔羊」)，如果有錯請各位不吝更正
最近在和其他人閒談時，明白了選擇公理(Axiom of Choice, AC)為甚麼不能用數學歸納法(Mathematical Induction)去證明，特意在這兒貼出來和各位像我一樣的「數海中的迷途小羔羊」分享。 :P
首先，讓我大概說一下甚麼是選擇公理，選擇公理的正式說法是：
簡單一點來說，如果你手上有一堆集合，而且你肯定每一個集合都包含至少一個元素，那麼你一定可以在每一個集合抽一個元素出來，而不用知道每個集合的其他資訊。
說到這裏，大家可能已經在抱怨：這不是很明顯嗎？如果你有幾個籃子，每籃內都至少有一隻雞蛋，我們當然可以在每一個籃子抽一隻雞蛋吧！但是數學中一切命題都需要證明，這個也不應例外。現在大家又可能想出了以下這個證明：
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的囚犯頭頂上的帽子。每個囚犯都戴上了黑色或白色的帽子，然後每個犯人依次猜測自己頭上的帽子顏色，猜對了的予以釋放。犯人們可以事先商量，而且他們都知道自己的座位編號，但犯人們不能聽到其他人的猜測；同時，我們假設每個犯人都是聰明和有無窮記憶力的。
時間所限，有關第三個例子中的策略，我留待稍後才再討論。
最近在和其他人閒談時，明白了選擇公理(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的囚犯頭頂上的帽子。每個囚犯都戴上了黑色或白色的帽子，然後每個犯人依次猜測自己頭上的帽子顏色，猜對了的予以釋放。犯人們可以事先商量，而且他們都知道自己的座位編號，但犯人們不能聽到其他人的猜測；同時，我們假設每個犯人都是聰明和有無窮記憶力的。
時間所限，有關第三個例子中的策略，我留待稍後才再討論。
No comments:
Post a Comment