康MM講座
康MM講座
這句話是Hilbert說的，意思是任給一個數學命題，隻能有兩個可能：這個命題是對的，可以證明，或者這個命題是錯的，可以找出反例。做不出來是因為你自己笨，不能怪數學不好。（這個東西還有個專門名字，叫數學的完備性。）
當時所有數學家都是這樣認為的，說了類似的話的估計也有不少，但是大家隻記住Hilbert了。一個原因當然是因為Hilbert有名，他是當時最有名的數學家，但還有其他原因。Hilbert可不是說說就算了，他很認真地要證明這件事，他要把數學完全公理化：要把全部數學都建立在幾條公理上，而且這些公理要滿足1)相容性（這些公理之間沒有矛盾）；2）完備性（上麵提到的）；3）還有一條忘了叫什麽性了，是說公理中沒有多餘的，每一條都不能從其他公理推出。
Hilbert首先做了幾何的公理化，他引進了21條公理，整個2維與3維的幾何都可以建立在這些公理之上。下一步就是整個數學的公理化了，但是後來來了一個20多歲的小子，叫Godel，給了Hilbert當頭一悶棍。
Godel證明了他的不完備性定理：任一個包括所有自然數的公理係統一定是不完備的。他構造了一個命題，既不能被證明，也不能被推翻。我不知道當時Hilbert老先生是怎麽想的，大概連上吊的心都有。
數學家們還沒有放棄希望，他們說Godel的命題不過是一個邏輯遊戲，真正有數學意義的命題還都是確定的，當然Godel的悶棍也還沒有打完，他又向集合論中公認的最難的問題--連續統假設下手了。連續統假設是這樣一個問題：全體整數的個數是a，全體實數的個數是c，集合論的創始人Cantor提出的連續統假設說，a與c之間沒有其他數了。Hilbert把連續統假設列為他的第一問題，可見其分量。Godel這次作的事是構造了一個數學模型，在其中，連續統假設成立。這一來就麻煩了，我們現在知道了連續統假設不可能是錯的，但是由於Godel的不完備定理，沒人敢說它是對的，因為畢竟沒有證明。
Godel搞的東西太過奇怪，最後終於把自己也繞進去了--他犯了精神病。當時Princeton數學係有兩個著名的精神病，一個是Godel，另一個是John Nash。這兩個人每天什麽事都不做，整天遊遊逛逛，坐領工資。其實工資是家人領的，他們自己肯定不在乎。
因為Godel犯了精神病，給數學的確定性最後定上棺材板又要等幾十年了。這時來了一個家夥叫Cohen。這個家夥也是絕頂聰明，他的本行不是集合論，而是調和分析。當時有一個人（弄不清楚到底是誰）說了一句話，他說Cohen不過有點小聰明，難題是絕對做不出來的。Cohen當然不服氣，“你說什麽題最難吧，”“連續統假設最難。”“好，就是連續統假設。”於是他就去做連續統假設，一下子還真讓他給做出來了：他也構造了一個模型，在其中連續統假設不成立。這一下子，連續統假設真的成了一個Godel意義下的不可判定的問題，既不是對的也不是錯的。
這一下子，數學家們可嚇呆了，鬧了半天，不是我們無能，是共軍太狡猾了，問題根本就沒有解，你讓我們證明什麽？等到數學家緩過勁來，就開始走向另一個極端了：凡是做不出來的題，就說這可能沒有解。例如有些數學家就很認真地說Fermat大定理可能沒有解。當然後來人家做出來了，就不能再說了。但是其他問題還是在說，甚至連Erdos也說角穀猜想（3n+1問題）可能沒有解。
當然有很多問題真的就是沒有解，甚至我們壇子上出現過的問題。（大家回憶一下，看看誰能想起來？如果都想不起來就看我下一篇文章。）
注：這些大多是多年以前學的，因為後來換了專業，很多都沒學完，學完的也忘了很多。有不確切的地方，請大家指出。
選擇公理的故事
數學的完全公理化雖然失敗了，數學家們還是對數學進行了不完全的公理化。為大部分數學家所接受的Zermelo-Frankel公理係統有10條公理，其中的9條是很自然的，像兩個集合的並也是一個集合這樣的。但是有一條顯得很奇怪，就是選擇公理。
選擇公理：給定任意個集合，可以從每個集合中選出一個元素，組成一個新的集合。
一般數學係學生第一次接觸選擇公理是在實變函數課程中構造不可測集，在數學史上選擇公理是怎麽出現的我不是很清楚，但是開始的時候大家都沒有覺得有什麽不妥。可是後來出現了一些很奇怪的，違背常識的結果，其中最奇怪的是Banach-Tarski分球定理。
Banach-Tarski分球定理：可以把一個實心單位球分成5個子集A，B，C，D，E， 使得A與B可以拚成一個實心單位球，C，D，E可以拚成另一個實心單位球。
奇怪的地方是這5個子集都是剛性的，像星球大戰第三集中沒建好的死星那樣的，拚球的過程中不能改變形狀。也就是說，我們實實在在的把一個球變成了兩個球。
這些奇怪結果的根源都是用到類似於選擇公理的這樣一個步驟，因此一部分數學家要求禁止使用這樣的數學證明，即禁止使用選擇公理。但是禁止也有禁止的麻煩，首先，數學中並沒有規定一個球不能變成兩個球，雖然違反常理，卻不能說這裏引出矛盾。另外，如果不能使用選擇公理，集合論的大部分都不能成立了，甚至不能比較兩個無窮集合的大小。而且不光是集合論，像拓撲，代數，泛函分析等領域都有很重要的定理用到選擇公理。因此多數數學家還是在提心吊膽的使用選擇公理—--提心吊膽是因為不知道這樣會不會哪一天出事，也許選擇公理真的會引出矛盾呢。
打消數學家的顧慮還是要靠我們上次提到的Godel和Cohen，用他們的數學模型。他們的模型都是隻用到另外的9條公理，構造的過程中不用選擇公理。Godel的模型中，不光連續統假設成立，選擇公理也成立。而Cohen的模型中，不光連續統假設不成立，選擇公理也不成立。這下子數學家們終於知道了可以放心大膽地使用選擇公理，不用擔心會出問題，而且還知道了選擇公理本身確實是一條公理，不能由其他公理推出。
倚賴選擇公理的數學題比我們想象的要多得多，我們論壇上也有過幾次。下麵看幾個例子：
問題1。設實函數f(x)滿足對任意x,y, f(x+y)=f(x)+f(y)。f是否一定是線性函數f(x)=cx?
有選擇公理的時候，這個問題的答案是否定的，可以有很多非線性的函數滿足這個條件。而沒有選擇公理的時候，一種可能情況是所有的實數集合都是可測的，而滿足上述條件的可測函數一定是線性的。
問題2。亂彈版主曾經給出這個圓周染色題：把單位圓周染成三種顏色，證明一定存在一個等腰三角形，其三個頂點是同色的。
這個問題本身不用選擇公理。問題可以推廣成n種顏色，也不用選擇公理。但如果把問題推廣到可數無窮種顏色：把單位圓周染成可數無窮種顏色，是否一定存在一個等腰三角形，其三個頂點是同色的？
這個問題的答案就與選擇公理有關了：有選擇公理的時候，答案是否定的。而沒有選擇公理的時候，每一種顏色的集合都可以是可測的，而有正測度的可測集中一定可以構造一個等腰三角形。
問題3。腦壇前輩野菜花曾經給出這個問題：是否存在一個空間點集，與空間中每個平麵都相交，但交點都是有限個？
這個問題也是本身不用選擇公理，可以找到一個點集，與空間中每個平麵都相交，但交點最多是5個。現在考慮問題的推廣：是否存在一個空間點集，與空間中每個平麵都相交，但交點最多是３個？這個推廣的問題的解我用到選擇公理證明了這樣的點集的存在性，但是不知道不用選擇公理會有怎樣的結果。
這三個問題就作為給大家的作業。前兩題的提示：選擇公理的一個推論是任一個線性空間都有一個基，即極大的線性無關子集，使得線性空間中任意一個點都能唯一的表示成這個子集的有限線性組合。
解答
與選擇公理有關的東西非常多，但是大部分都很高深，隻有兩個適合我們論壇水平：一個是可測集的存在性：如果選擇公理不成立，可以構造一個模型，其中任意n維空間的子集都是可測的；（注意這個時候Banach-Tarski分球定理就不成立了。）另一個是把所有實數考慮成有理數的線性空間，有選擇公理的時候，這個線性空間有一組基，即一些線性無關的實數組成的一個子集，使得任一個實數都能表成這些數的有限線性組合。我們的前兩個題目就用到這兩條性質。
問題1。設實函數f(x)滿足對任意x,y, f(x+y)=f(x)+f(y)。f是否一定是線性函數f(x)=cx?
有選擇公理的時候，這個問題的答案是否定的，可以有很多非線性的函數滿足這個條件：設{x_a}是實數線性空間的一組集，對每個x_a，給它一個實數y_a，然後這樣定義f(x)：對x = q_1*x_1+q_2*x_2+…+q_n*x_n，f(x) = q_1*y_1+q_2*y_2+…+q_n*y_n。隻有當y_a = c*x_a 時f(x)才是線性函數。
而沒有選擇公理的時候，有可能所有的實數集合都是可測的，而滿足上述條件的可測函數一定是線性的。有正測度的可測集有這樣的性質：它不會是完全均勻分布的，一定會在某個區間內很集中，即對任意給定的r<1，一定存在一個小區間，使得小區間內至少有r的部分屬於該可測集。這樣我們就能找到一個常數c，使得大部分x都滿足f(x)=cx。再根據條件，剩下的x也必須滿足這個關係。
問題2。亂彈版主曾經給出這個圓周染色題：把單位圓周染成三種顏色，證明一定存在一個等腰三角形，其三個頂點是同色的。
證明： 我們證明正十三邊形中任意五個頂點 a, b, c, d, e 中必有三個是一個等腰三角形的頂點。做一個映射 f ： (x,y)
如果 f(a,b
這個問題本身不用選擇公理。問題可以推廣成n種顏色，也不用選擇公理。但如果把問題推廣到可數無窮種顏色：把單位圓周染成可數無窮種顏色，是否一定存在一個等腰三角形，其三個頂點是同色的？這個問題的答案就與選擇公理有關了。
這個問題可以放到直線上去，實際上就相當於要找一個長度為3的同色的等差數列。
對n種顏色，這個問題變成了 Van Der Waerden 定理的推論：
Van Der Waerden 定理：對任意正整數 k 和 r，存在常數 n(k,r)，使得對集合 {1,2,...,n(n,k)} 的任意分解 C_1，C_2，...，C_k，一定有一個子集 C_i 包含一個長度為 k 的等差級數。
滿足上麵條件的常數中最小的叫做 Van Der Waerden 常數。Van Der Waerden 常數中隻有非常少的幾個是已知的，例如用上麵的方法可以證明n(3,3)=27。
無窮種顏色的情況與選擇公理有關。有選擇公理的時候，答案是否定的。考慮有理數的所有可重複的有限子集：{1，1/2，1/2，1/3，1/3}這樣的子集。這種子集共有可數無窮個，每一個子集給一種顏色。再把實數表成線性空間，實數x = q_1*x_1+q_2*x_2+…+q_n*x_n 的顏色就是子集{x = q_1，q_2，…，q_n}的顏色。這樣染色就保證了任一種顏色都不存在長度為3的同色的等差數列。
而沒有選擇公理的時候，每一種顏色的集合都可以是可測的，而有正測度的可測集中一定可以構造一個等腰三角形：隻要找出這種顏色很集中的小區間，對折一下，就得到了一個等腰三角形。
問題3。腦壇前輩野菜花曾經給出這個問題：是否存在一個空間點集，與空間中每個平麵都相交，但交點都是有限個？
這個問題也是本身不用選擇公理，可以找到一個點集，與空間中每個平麵都相交，但交點最多是5個。現在考慮問題的推廣：是否存在一個空間點集，與空間中每個平麵都相交，但交點最多是３個？
證明： 這個證明用到了超限歸納法，即對無窮序數用歸納法。這種論證方法的基礎是良序原理，而良序原理與選擇公理是等價的 。
對證明中用到的術語，請參考集合論的教材。
設 c 是所有實數的基數（即連續統）。 3 位空間總共有 c 個 平麵。把這些平麵寫成 {P_alpha : alpha 是小於 c 的所有序數 } 。對每個序數 alpha ，用超限歸納法定義一個點集 S_alpha ，使得 S_alpha 與每個平麵 P_beta （ beta <= alpha ）相交，但最多相交 3 點。而且我們要求S_alpha中任意4點不共麵。
對給定的 alpha ，令 S' = U {S_beta: beta < alpha} 。如果 S’ 已經與 P_alpha 相交，令 S_alpha = S' 。否則在 P_alpha 上選一點 x 使得 x 不在 S' 中任意兩點形成的線上，也不在 S' 中任意三點形成的平麵上。因為 S' 的基數比 c 小，這樣的點一定存在。令 S_alpha = S' u {x} 。
最後令 S = U {S_alpha : alpha <= c} 。 S 滿足我們的條件：
1) 對任意平麵 P_alpha ， S 的子集 S_alpha 與 P_alpha 相交。 .
2) 設平麵 P_alpha 與 S 相交於 4 點 x_1, x_2, x_3, x_4 。這 4 點是一個一個加入 S 中的，可以假設是按以上順序。當 x_4 加入的時候， ( 在某一個 S_beta) ，前 3 個點已經在 S_beta 中了，因此 x_4 不會與他們共麵。
類似的，可以證明存在一個空間點集與任何一條直線都相交，但都不超過兩點。
最後再指出一點：實數作為線性空間是非常有用的方法，而且不是一定與選擇公理有關。例如下麵兩個問題的解都用到這個方法，但是隻涉及到有限個實數，因此不用選擇公理：
問題1。也是亂彈大汗出的題：設區間[0，1]中有有限個點，包括0和1。這些點之間的距離，除了1以外，都出現至少兩次。證明這些數都是有理數。
證明： 設這些點不都是有理點。令 r_1, r_2, ..., r_m 為 x_0, ..., x_n 的一個關於有理數的極大線性無關子集，即對任意不都是 0 的有理數 a_1, a_2, ..., a_m ， a_1*r_1 + a_2*r_2 + ... + a_m*r_m 也不是 0 。將其中的 m-1 個加到有理數集 Q 中，並擴展成實數集 R 的線性子空間 S 。存在一個實數 r (r 不在 S 中，也不一定是 x_i 之一 ) ，使得每個 x_i 都能被唯一的表示成 s+k*r ，其中 s 屬於 S ， k 是整數。令 k_1 和 k_2 為這種 k 的最大值和最小值，則這兩點 s+k_1*r 和 and s+k_2*r 之間的距離隻出現一次。
問題2。這個題原來是星星司令出的，是整數。但是可以改成實數，結果仍然成立：設有11個球，重量為實數。（這是廢話了，原題中是整數。）11個球中任意拿出一個，剩下的10個球都能分成重量相同的兩組，每組5個球。證明這11個球重量相同。
下麵按照學術路線算出來的又是必敗策略：
-------------
在NIM遊戲裏，初始狀態「3，5，7」的必勝策略是什麽？狀態「3，5，8」的必勝策略又是什麽？狀態「3，4，5，6，7」呢？
前麵已經算過這個初始狀態的NIM值N「3，5，7」為1，必勝策略就是從任何一堆拿一個就行了。
一般來說，先把NIM值表成二進位數，找一個在NIM值的最高位為1的子狀態，然後比較整個狀態和子狀態的NIM值。所有整個狀態為1的位上，子狀態是1就改成0，是0就改成1。
例如「3，5，8」的NIM值為14 = (1110)，最高位是第四位。8 = (1000)的第四位為一，所以這個子狀態的NIM值應變為(0110) = 6。必勝策略就是在8的一堆上拿兩個。
「3，4，5，6，7」的NIM值是3 = (11)。要找一個第二位為1的子狀態，3，6，7都可以。大家可以自己算一下應該拿幾個。(答案：3，7拿3個，6拿1個)
NIM還有一個變種：走最後一步為負。這種情況下，一開始還是和普通NIM一樣，但到了隻有一個子狀態的NIM值大於1時就不同了。如果有奇數個子狀態為1，就把大的一堆拿光，如果有奇數個，就剩一個。也就是說，給對手剩下奇數個1。
---------------------
我的勝策很簡單：
先拿者勝：每堆拿剩一個，最後一堆全拿光。
如果走最後一步為負，則仍在拿最後一堆時留一個。
下麵這題,一步就勝了,用得著算嗎?
問題4。(和上一題差不多。)有一塊6X8的矩形巧克力，左下角那一塊壞了。兩人分吃，每次掰時，先選定一塊，然後把這塊及其上麵和右麵的都掰掉。(剩下的是鋸齒形。)吃最後一塊為負。第一次應該掰多少？
這一題的NIM值就很難算了，要編一個程序才行。下麵是矩形的NIM值。(還不包括鋸齒形。)
5，8，12，16，21，13，28，32
4，7，11，13， 6，21，23，22
3，5， 9， 6，13，16，19，12
2，4， 5， 9，11，12，13，16
1，2， 4， 5， 7， 8，10，11
0，1， 2， 3， 4， 5， 6， 7
------------