康托爾著名的對角線證明？

01-08

看到網上很多所謂的數學愛好者，基層講師，副教授在反對康托爾的對角線論證，即康托爾關於[0, 1]區間里的元素的個數不是可數的無窮的對角線證明法。雖然這個已經是教科書上的東西了，但是是否數學界到目前為止真的存在爭論？如果有那麼爭論點在哪兒？
附，詳見什麼杜立智，楊正瓴，沈衛國等的新浪微博
http://blog.sciencenet.cn/home.php?mod=spaceuid=327757do=blogquickforward=1id=557053

不要在傻瓜身上浪費你的時間，他們連定義都沒搞明白，看他們一個公式都沒列就知道是什麼成色了

不專業，說一下我的看法：我覺得這些反駁是比較無力的。

第一，是邏輯上的問題，當他試圖構造一個完全不一樣的實數的時候，這一試圖本身就與前面已經列出了「所有」的實數相矛盾，或者說，這一試圖本身的前提是，前面並沒有完全列出「所有」的實數。若是在有窮領域，你當然可以通過這樣的方式來反證，因為有窮領域是很直觀的、看得很清的。但請注意這是在無窮領域，跟有窮領域的思維方式是不一樣的。邏輯上無窮領域只要包含了「所有」，你就無法再構建「新的」了。這個如同下述問題，上帝能製造一塊連他自己都搬不動的石頭嗎？此問題常被用來「證明」不存在萬能的上帝。但因小前提已假設了結論（「自己都搬不動」），故這樣的證明是無聊的。如同「上帝能搬動一塊連他自己都搬不動的石頭嗎？」一樣的無聊，為了避免後者明顯的荒謬可笑，將其中之一的「搬動」改成了「製造」，但本質是一樣的。你既然假定了上帝萬能（無窮），你就不能再在其他前提表述中暗含上帝不能。請注意，從邏輯上，萬能（無限能）是壓倒一切的，正如康托爾那個假設包含了「所有」本身就意味著壓倒了一切一樣。

這是否認了反證法的邏輯。

IF $S cup { eg P} vdash F$

Then $S vdash P$

這裡是有兩個元素的，S是已有的條件，P是要證的東西。

康托的證明的要點就在於成功構造了一個沒有被那個陣列列出的數，從而達到了矛盾。假設了自然數和實數在數表裡一一對應，產生矛盾，所以假設不成立，所以不一一對應，所以不可數。這是證明邏輯。如果一上來就否認一一對應關係，那麼是直接給出了實數不可數的結論啊（因為如果可數，那麼一定可以構造一一對應的）。

上帝的例子是羅素悖論，我覺得這裡並不嚴重的涉及。可數的性質與雙射對應關係矛盾，並不是實數內部的選擇問題。

第二，他的對角線法是建立在假定寬和高嚴格相等的前提下，而在無窮領域，這樣的假設是有問題的。即使是同級無窮大，這樣的假設也說不過去。因為你是要構造一個具體的「對角線數」，以兩個無窮領域的元素個數嚴格相等為前提基礎來構建一個有窮領域的具體的數，邏輯上是站不住腳的，因為有窮領域的任何常數個數等同於無窮領域的0個數。他用增加了一行來反證原假設不成立，就好像是在說，無窮大甲比無窮大乙多一個，這樣的說法無疑是荒謬的。換句話說，康托爾的對角線法，相當於主張如下不等式成立：∞+1 &> ∞，而這樣的不等式顯然是錯誤的。並且，直覺上，他那個列表的高明顯大於寬，否則實數就不連續了，也就是說不包含全部了。而為了使寬等於高，注意這裡因為要構造一個具體的「對角線數」，寬和高就必須嚴格相等，為了達到這一目的，惟一的方法就是補零。而一旦補零，其潛在的含義就是，那個列表並沒有包含全部的實數。

這點有點業餘，「對角線法」只是個形象說法來表示這個數是怎麼構造的，又不是真的是一個方陣。再說等高等寬也是顯然的，由於我們假設了實數可數，每個數的各個數位的序列又是可數的（自然數），那麼可以橫豎一一對應。

小數末尾補零對結果也不產生任何影響，實數中0.5 和 0.5000000000是一個數

第三，他那個列表假定左邊是全部的自然數，與右邊全部的實數一一對應。既然右邊他假定實數全部列出，然後構建一個新的實數來否決這個假定，那我左邊為什麼不能這樣做呢？假定左邊的自然數也全部列出來了，這個時候，若按照這個荒謬的對角線法，我們將自然數全部用二進位表示。同樣，這個時候，直覺上，或者說按照有限領域的理解，高明顯大於寬，解決的辦法是左邊全部補零，這樣一來，問題來了，我們也可以在對角線上（按取反）構建一個與前面所有自然數都不相同的自然數。總之，由於左邊的全部自然數的寬和高也都是無窮的，因而也可以用對角線法予以否定。請注意，在寬和高的關係上，左邊的自然數和右邊的實數是有一定不同的，但你不能以此不同為根據來認定左邊無對角線。而右邊有對角線，否則就意味著你是前提裡面包含了結論（自然數可數而實數不可數的結論）

對角線法誤用，康托這個證明裡面數的是0到1的實數，全體二進位的自然數是沒有上界的，這個證明只證明了自然數的確是沒有上界，沒有對「自然數可數」的題設造成威脅

我解釋不太清楚，參見Matrix67大神寫的一篇博文：對角線方法之後的故事

前面幾個例子很清楚

第四，我們再從另一個角度來看康托爾證法的荒謬。我們假定右邊那個陣列列出了全部的小數，並且是從小到大排序，第一個小數各位全部是0，「最後」一個小數各位全部是9，中間無縫連續。請注意，你不能否定我這個假設，若是你認為我這個假設不成立，那就意味著你的前提裡面包含了結論（不可列的結論）。所以，到目前為止，我這個假設沒有任何問題。此時你能不能找到一個不在這個陣列當中的小數呢？毫無疑問不能。那麼，康托爾為什麼能構建出這樣一個小數呢？關鍵是他設想了一條荒謬的根本不存在的對角線。在有窮領域，對角線必須是寬和高嚴格相等。而在無窮領域，寬和高相等的含義是什麼呢？答案是：寬等於高是相等，寬等於高加1和高等於寬加1其實也是相等的。也就是說，在無窮領域，根本不存在一條確定的對角線，若一定要說有對角線，那對角線也是不確定的。用不存在或不確定的對角線來構造一個確定的小數無疑是荒謬的。

「此時你能不能找到一個不在這個陣列當中的小數呢？毫無疑問不能。」這句話是對的，也是反證法得到的矛盾的原因，作者認識到了這點，但是後面還是太抱住寬和高的定義來說無法構造對角線數了。這個論點和第二條其實是一樣的。

我覺得Cantor"s Diagonal Argument　這個完整的證明更清楚一點說明了原證明與作者想像的不同。康托的證明目的是構造一個不雙射的對應關係，從而說明實數不能與自然數對應，那麼先建立了一一對應（數表）之後由於證明不射滿。而這篇文章作者似乎一直在扣一一對應就是射滿這件事

他的第五條不列了，和第四沒區別。

第六，他假定那個小數陣列的寬和高完全相等，實際上是運用了他自己的無窮集合元素一一對應的理論，而一一對應理論之所以有效，取決於對角線證明的結論，也就是說，他使用的是循環證法。

「無窮集合元素一一對應理論」不知道指的是可數無窮集合一一對應，還是不可數無窮也一一對應。如果這句話指的是這個證明不合理地用了「可數無窮集與自然數一一對應」的話，這是可數集的定義啊...

如果這句話指的是這個證明不合理地用了「不可數無窮集與自然數一一對應」的話，這個「理論」不對不依賴於實數不可數，而是依賴於可數集定義。可數集的性質，是和實數集性質沒因果關係的。並不是根據「能跟實數集一一對應」而定義的。

如果指的是不能用假設的條件參與反證的話，這是錯誤的。因為再次依照反證法的邏輯式，必須有外部條件（這裡是可數集的性質）（公式里的S）來參與制造這個矛盾。

第七，無窮大無形狀定理：無窮大沒有確定的形狀。

到這裡有點跑題了。

總結：

我覺得想得挺好的，我第一次看康托的證明沒想過這麼多。

但是具體的反駁論點犯了兩個錯誤：

1. 對於反證法里哪個是已知，哪個是假設，哪個是結論，搞得不太清楚，於是用了結論（無法一一對應）去反對假設（數表射滿）

2. 對於對角線的幾何意義太執著，數表的「長和寬」一一對應是從假設條件直接推出的，根據可數集性質

本人數學水平十分半瓶醋，歡迎指出我的錯誤

在討論這個問題前，請先讀一遍較為詳細的證明。只看過那張對角線的圖，只對對角線證明有個粗糙的理解，就來反駁的話，你都不知道你反駁的是什麼。

由於問題里鏈接的博客已經設成好友可見了，我只能從 AQUA 的回答里看到他說了什麼。

實數集不可數是ZF的定理。我讀過這個命題的非形式證明，並且相信轉換成形式證明是不會遇到困難的，大部分數學家也承認它是定理。所以如果你要反駁這個證明是錯的話，是沒有可反駁的地方的；如果你認為ZF公理系統是錯的，那你應該去討論ZF公理而不是討論對角線證明。

雖然康托證明的是不存在自然數集到所有可數無窮長的{0,1}序列的集合 ${0,1}^{mathbb{N}}$ 的雙射，然後用了一個 ${0,1}^{mathbb{N}}$ 到實數集的單射（這樣可以解決實數的小數表示不唯一的問題），但為了配合原文作者的表述，我下面直接把可數無窮長的{0,1}序列和實數看作等同的。

接下來看為什麼原文作者的反駁是錯的。他的第一條理由似乎說明他沒有搞懂反證法。對角線證明中的反證法實際是把證明 $eg A$ ，轉換成了證明 $A ightarrow ot$ ，A是「存在自然數集到康托集的雙射」，在一些形式系統里否定的定義就是這樣的，在所有經典邏輯的形式系統里都是合法的推理規則。

邏輯上無窮領域只要包含了「所有」，你就無法再構建「新的」了。

因為我們假設了這個實數序列，所以確實無法再構造新的實數了，這個沒有問題。我們可以用對角線法構造一個新的實數，這也是沒有問題的。我們的目標就是要推出矛盾，用「可以推出矛盾」來否定「可以構造新」是荒謬的。

不存在萬能上帝的那個證明也是沒有問題的。如果萬能的定義包括「可以搬起所有的石頭」和「可以造一塊上帝搬不動的石頭」的話，這樣萬能的上帝確實不存在。如果你相信上帝存在但又想避免這樣的悖論的話，可以把「可以造一塊上帝搬不動的石頭」從上帝的能力中去掉。哥德爾在他的上帝存在的證明（G?del"s ontological proof）里就是這麼做的，他把所有的性質分為積極性質和消極性質，「可以造一塊上帝搬不動的石頭」就屬於消極性質，然後證明存在一個滿足所有積極性質的上帝。

第二條反駁完全是從他自己對無窮的直觀理解出發的，是不嚴謹的。首先「寬」和「高」都是有窮的，構造對角線數的時候用到了第n個實數的第n位，n是自然數。「寬」和「高」相等在這個證明裡也不是必要的，對於任意自然數到自然數的單射f，用第n個實數的第f(n)位，一樣能構造一個不屬於序列的實數。寫出∞+1 &> ∞這種記號表示他對集合論是完全不熟悉的，大概對這裡的大於的定義也不知道。集合的勢是衡量集合大小的一個概念，集合X的勢|X|等於集合Y的勢|Y|當且僅當存在X到Y的雙射， $|X|le |Y|$ 當且僅當存在X到Y的單射， $|X|<|Y|$ 當且僅當 $|X|le|Y|$ 且 $|X| eq |Y|$ 。對角線法證明的其實是自然數集和實數集之間沒有雙射。

第三條這個自然數上的對角線法是胡扯，因為這樣構造出來的是一個無窮長的{0,1}序列，根本不是一個自然數。

第四條，如果這個實數序列還是排好序的，連對角線都不需要就能構造一個不屬於這個序列的實數，只要用實數的稠密性就行了。

第六條，自然數集和自然數集之間有雙射這個太顯然了，完全和實數集不可數無關。

其他回答里的一些問題：

黃汝廣：因為假設了康托集可數，而康托集的元素也都是可數序列，所以對角線構造用到了序列的所有項，不存在漏項。不是所有的有窮集的性質都可以推廣到無窮集，否則有窮集和無窮集有什麼區別？ $aleph_1$ 的定義不是 $2^{aleph_0}$ 。 $aleph_1=2^{aleph_0}$ 稱為連續統假設，哥德爾和科恩證明了連續統假設在ZFC中既不能被證明，也不能被證否。對角線數的構造是成功的由替換公理保證，並不是隱形假設。對角線法的變體很多，絕不限於可數無窮。

黃汝廠：這個是小號吧？只是構造一個不能推出矛盾的{0,1}序列並不能證明所有序列都是可計算的。你的證明思路是錯的。如果要駁倒對角線證明，最直接的證明方法是構造一個自然數集到康托集的雙射，你的證明裡並沒有做到這一點。

mr.蔣：有理數集是稠密的（因此滿足你說的不存在相鄰的數的性質），但它是可數的，可數性和是否有相鄰的數無關。「無限細分」指的應該是實數的稠密性。先得有一個線序才能定義稠密性，一般的不可數集是否稠密和你定義的序有關，而它的不可數性和稠密性是無關的，與連續性也無關。

阿龍：這實際上是有窮主義的想法。但如果採取有窮主義的立場的話，康托的超窮序數和超窮基數就沒什麼好研究的了，實數集也不存在（因為它是無窮對象），也沒法表示任意的實數（戴德金割也是無窮對象），也沒有可數和不可數的概念。

對角線法還有很多變體，在遞歸論、集合論、數理邏輯中經常出現，包括圖靈證明存在不可及算集， $|X|<|2^{X}|$ ，寇尼希定理（ $(forall i in I (kappa_i < lambda_i)) ightarrow igoplus_{i in I} kappa_i < igotimes_{i in I} lambda_i$ ）。力迫法也可以看作一個大的對角線證明（這個只是聽說，沒有學過）。

可是，那篇證明並沒有錯誤啊；所以無論是講師還是副教授，哪怕是外星人來了，也沒法推翻這篇證明。

最近在看michele friend的《數學哲學導論》，其中就詳細談到康托爾的「對角線論證法」。其中有這樣一段描述：

「Since we are listing all the real numbers, it should turn up in the list at some point.

Now let us modify the diagonal number. For each digit in the diagonal number,

add 1 to it, unless it is 9; if it is 9, then turn it into the digit 1. Call this new

number 「Cantor』s diagonal number」. Cantor』s diagonal number will not turn

up on the list above: it is different from the first number on the list in at least

the first digit; it is different from the second number at least at the second

digit; it is different from the third number on the list at least at the third digit

and so on. It does not appear in the original list at all.」

我試著翻譯一下：

「從我們列舉出所有實數之後，這個數（對角線數）應該會出現在這個清單的某處。現在，讓我們修改這個對角線數。遍歷對角線數的每一位，將每一位的數字加1，除9之外。如果這一位的數字為9，則將這一位的數字替換為1。我們把得到的新數字叫做『康托爾對角線數』。康托爾對角線數將不會出現在以上的實數清單里：這個數不同於清單的第一個數，至少與第一個數的第一位數字不同；也不同於第二個數，至少與第二個數的第二位數字不同，也不同於第三個數，至少與第三個數的第三位數字不同，以此類推。它根本不會出現在這個原始的實數清單上」。

我不清楚michele friend的這段解釋是否與康托爾的論證相符，但是至少說明，康托爾假設的實數清單這個前提，是一個完成時狀態的實體概念，也就是康托爾的「實無窮」概念：無限是一個整體，是一個已經構造完成的實體，但內部還在不停地延展。所以理解「對角線論證法」，「實無窮」是最大的前提。實數清單就是一個內部無限延展，但整體完善的實體，實體清單之外再無任何實數。而「對角線數」被尋找到，反證出，實數按照序數一一對應的方式延展所有實數，卻延展不出「對角線數」這個數字。因此，前提錯誤，實數不可數，不可以按照序數1,2,3這樣一一對應。

我的數學水平仍然徘徊於高中數學那點家底上，都是自己從數學哲學角度出發的一些粗淺理解，請大家指正。

實際上，在《論可計算數及其在判定性問題上的應用》一文中，圖靈曾反駁過一個模仿康托爾的「可計算序列不可數」的證明，在適當改造後，同樣也可以用來反駁康托爾。

「假設可計算序列是可數的，令an為第n個可計算序列，Xn(m)為an中的第m個數。令b是以1- Xn(n)為其第n個數的序列。由於b是可數的，則存在數K，使得1- Xn(n)= Xk(m)對任意n成立。令n=k，我們有1=2 Xk(k)，即1是偶數。而這是不可能的，因此可計算序列是不可數的。這個證明的謬誤在於假設b是可計算的。」但實際上，這個證明的真正謬誤與康托爾一樣，是由於隱含地假設了對角線的遍歷性！

需要強調的是，這個論證採用的是二進位，Xk(k)只有0或1兩種取值可能，而「1- Xn(n)」表示不同於Xn(n)的取值，是一個不可分割的整體。因此，對「1- Xk(k)= Xk(k)」進行移項而得到「1=2Xk(k)」，完全是概念混亂的結果。但奇怪的是，圖靈似乎沒有意識到這一點。

當然，根據筆者的解讀，「1- Xk(k)= Xk(k)」只能理解為「0=1」或「1=0」，矛盾同樣存在。但適當做些改進，矛盾是可以避免的：「假設可計算序列是可數的，由於奇數同樣可數，故可令a2n-1為第n個可計算序列，X2n-1(m)為a2n-1中的第m個數。令b=a2是以1- X2n-1(n)為其第n個數的序列，顯然存在數K=2，使得1- X2n-1(n)= X2(n)對任意n成立。再令n=2，則有1- X3(2)= X2(2)。根本不存在任何矛盾。」

這個改進後的方法對於康托爾的證明也同樣適用：即把其無窮序列的行標都改為奇數，而用對角線法構造的數的行標都用偶數。按照康托爾的理論，奇數與偶數均可數，兩者加起來也同樣可數！根本不能推出不可數的結論。真正的謬誤是康托爾的「可數」概念：對於一個無窮集合，區分可數與不可數根本就毫無意義！

一個有效的反證法論證，應該符合下列要求：(1)排除一切隱性假設，保證想要否定的假設是唯一的；(2)推理過程有效，並能在有限步驟內完成，或者符合完全歸納法；(3)矛盾和假設必須有邏輯關係，否定假設後，矛盾應也隨之消除。康托爾關於(0,1)不可數的對角線反證法，儘管在數學史上大名鼎鼎，然而其論證實際上卻是無效的。

1 對角線的漏項問題

康托爾的論證說起來也比較簡單：假設(0,1)可數，用十進位無限小數表示，可得如下序列

1→0.a11 a12…a1n…

2→0.a21 a22…a2n…

……

n→0.an1 an2…ann…

……

然後構造數b=0.b1 b2…bn…（當ann=1時，取bn=2；當ann≠1時，取bn=1）。康托爾認為，b屬於(0,1)卻不屬於該序列，矛盾，故(0,1)不可數。

然而，對於十進位小數，每一數位都有十種不同的取值可能，這會導致上述矛盾根本不存在：先考慮(0,1)內所有的n位小數，其序列只有n列但遠遠不止n行，而對角線僅能貫穿n列n行，佔總行數的比例很小；再令n趨於無窮大，則比例的極限為0，換言之，對角線無限延伸時，其漏項率幾乎是100%！

有網友認為，對角線法只適用於無限，不適用於有限，從有限推無限的思考方式，是沒有想像力的表現。然而眾所周知，康托爾集合論中「基數」(或者「勢」)的概念，就是從有限推廣來的；自然數集基數???與實數集基數??之間的關係????=2^ ??，也是推廣得到的（實際上，按康托爾的奇怪法則，對任何n&>1，都有????= 2^ ??=n^ ??）。

更有趣的是，從康托爾的基數理論看，對角線也必然漏項：因為(0,1)的基數是???，即共有???
個元素，但對角線只能貫穿??個；而且按康托爾的奇怪法則，應該有??/???=0，（???-??）/???=1，即漏項率可達100%。

實際上，只在一種情況下，對角線法才可以構造出矛盾，那就是它違反同一律的時候：對「A=A」實施對角線法，可得「A=非A」；然而，這種矛盾與要否定的假設沒有任何關係，在反證法中無用武之地。

2 對角線的隱性假設

仔細分析康托爾的論證，不難發現：其無窮小數序列只是對(0,1)的具體展示，兩者是等價的；否則，「b屬於(0,1)卻不屬於該序列」就不可能構成矛盾。很顯然，「b屬於(0,1)」的結論，是由b=0.b1 b2…bn…自身形式決定的，而與假設無關；因此，假設與另一結論「b卻不屬於該序列」，必須有邏輯關係，不然反證法否定它的理由是什麼呢？

然而，筆者實在看不出這兩者有什麼邏輯關係，要推論「b卻不屬於該序列」，反倒是這樣一個前提不可或缺：對角線必須遍歷序列中的任何一個，也即不能存在漏項。我們認為，康托爾對此需要給出一個證明，否則它就不過是一個隱性假設而已。請不要說這是不言自明的，因為在康托爾的理論中，無窮有太多違反直覺的不可思議的性質了。

事實上，只要承認對角線的遍歷性，即使否定康托爾的原始假設，矛盾依然存在。有網友說，如果不假設(0,1)可數，就無法排出那個序列，也就不能使用對角線法；這種辯解其實意味著，對角線只適用於可數無窮序列，但它同樣需要證明。

我們知道，(0,1)內的有理數是可數的，因此可以排成一個康托爾形式的序列，然後從a11開始，依次實施對角線構造：當ann=1時，令bn=2；當ann≠1時，先將該行與後面ain=1(i&>n)的行對調位置，顯然對調後ann=1，然後再令bn=2。這種位置對調，並不會改變序列的個數，因而也不改變其可數性。但按康托爾的邏輯，如此構造出的數b=0.222…，顯然不屬於該序列：也即對角線無法遍歷可數無限序列！

****幾點說明：

1、要注意，我們「令n趨於無窮大，則比例的極限為0」，不管這裡的無窮大是潛無窮還是實無窮，極限都為0！

2、在康托爾的論證中，「對角線必須遍歷序列中的任何一個」這個必須的前提條件是一個隱性假設，而康托爾對角線構造出的所謂「新」數，恰恰否定了對角線的遍歷性假設，並不能否定其原始假設，原始假設只是一個替罪羊而已！

3、哥德爾不完全性定理據說也是對角線法的一個應用成果，但兩者是有所不同的：正如前面所說，康托爾所謂的矛盾其實並不存在！而哥德爾構造的所謂不可證公式是一種否定式的自我指涉，它在本質上是一個矛盾式（A=非A），根本不可能有東西滿足它（事實上，塔斯基正是利用A=非A來定義空集的），因而其論證不過是屠龍術而已！而且更加嚴重的是，從哥德爾的原始論文看，其所謂的定理Ⅴ根本就是一個矛盾！

4、看上面一位朋友的翻譯，就有所謂「遍歷對角線數的每一位」，但是這是不可能的！！！！

數學渣強答求不噴。。。

證明

首先，舉的例子應該是在（0， 1）的開區間，即實數的一個小子集，如果能證明這個小子集的元素uncountable, 那麼就可以安全的總結出實數uncountable。

0. 自然數這個集合N是countable的，如果我們能找到某一個集合S，與N有同樣的size （one-to-one correspondence），就可以證明S也是countable。

舉個，自然數奇數集Nodd是countable的因為它和N有同樣的size。well, you may argue，明明看起來大小不一樣好么！

我們來定義這樣一個mapping，f(n) = 2*n-1, n為N的所有元素，那我們可以順利的得到Nodd和N的一一對應，如圖

有了這個認識，我們來繼續。

1. 假設（0， 1）區間的所有實數的集合R是countable噠

我們來畫一張表如下，一行一行列出所有的實數（二進位表示），縱坐標是N（我們已經知道它是countable的）。

2. 現在，我們拿出對角線，然後flip每一位，得到了一個實數。

我們可以確定這個數不在我們之前列的集合R里。

為啥呢？因為它的第一位和第一行的不一樣，第二位和第二行的不一樣，第三位和第三行的不一樣。。。隨便找一行，我都可以確定至少有一位是不一樣的。這個數的新的，不存在於我們表格里的任何一行。

3. 由2可知，假設被推翻，（0，1）內的實數集uncountable, 從而得出整個實數集uncountable。

證畢

問題？

Cantor大師的證明好精妙，對於我這種沒有數學造詣的同學，看完這個證明簡直驚呆了。

但是換個角度這樣想，如果每次我用對角線的辦法都能得到一個新的實數，那我可不可以想成其實我在用對角線的辦法不斷枚舉實數呢？看起來也沒有證明實數集的uncountable呀。而且對於一個無窮的集合，我總是能找到新元素加進去，那這樣是不是一開始就有悖於無窮的定義呢？這是我的一些質疑，我覺得挺有道理的。

歷史上很多大師都對 Cantor"s Diagonal Argument 表示過不買賬，具體的我就不列了。然而很多教科書還是把它當範例寫，我也承認證明太太精妙了，不過目前還是保持open，坐等有生之年學界能撕出什麼結果。

引用

[1] [Introduction to the Theory of Computation, Third Edition](https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X)

按照我們實變老師的話說，不會用對角線法則，你真的學過大學數學嗎……

在通常公理體系下沒有問題，沒有爭議，他們自己把過強的預設當成必不可少，反駁處處槽點，不值一駁。

關於實數域元素是否可數的問題，第一聯想到的是 $0. dot{9} =1$ 這個事實，它本身反映了實數域不存在相鄰的兩個元素。所以個人觀點是，實數不可數。

康托爾對角論證法的前提是假設實數和自然數一一對應，即實數與自然數形成雙映射，並以列表形式給出。然後在此基礎上找出一個實數不在這個列表內，以證明前面的假設錯誤。而如何找出這樣一個數的方法即是對角線法。但是關於康托爾的對角線論證，這裡提兩點疑問：

第一，這裡注意到無論實數和自然數都是不可窮舉的，而對角線法實際上是一種從有限推廣到無限的思想，問題就在於用該方法得到的數是否還屬於之前假定的映射列表。

我們可以這樣來思考，首先因為二進位數只有0和1的區別，並且任何十進位小數都可用二進位表示，因此這裡將康托爾方法用在二進位小數上來說明問題。

對於任意一個二進位小數 $xin left[ 0,1 ight]$ ，它的小數點後一位只有兩種情形

$x={ egin{matrix} 0.0...\ 0.1... end{matrix}$

同理，它的小數點後2位有4種情形

$x={ egin{matrix} 0.0...{ egin{matrix} 0.00...\ 0.01... end{matrix}\ 0.1...{ egin{matrix} 0.10...\ 0.11... end{matrix} end{matrix}$

以此類推...

也就是說任意一個 $x$ ，它的小數點後有限位數的組合總是可數的

假設列表前五位是

$a_1=0.001011...\ a_2=0.001100...\ a_3=0.101101...\ a_4=0.110011...\ a_5=0.010101...$

...

那麼根據對角線法，得

$b=0.11011...$

發現 $b$ 的小數點後2位必然是不同於 $a_1,a_2$ 的組合，並且根據一開始的假設，該列表包含了所有的實數，因此小數點後兩位為「0.11」組合的數必然存在於該列表內。以此類推，對列表內的任意 $n$ 個數用對角線法獲取的一個新數，其小數點後 $n$ 位的組合必然存在於該列表其他位置，當 $n ightarrow infty$ 時該結論仍然成立。

也就是說用 $n$ 位小數表示的數至少有 $2^n$ 種情形（二進位數情形，十進位下有 $10^n$ 種），而一條對角線只能囊括 $n$ 個數，兩者不在一個數量級。用康托爾方法得到的數必然是剩餘的其中一種情形。

第二，不可數的概念實際上是指可無限細分，而可數既可以是有限，也可以是無限，它們的關係可以用連續和離散來描述，康托爾的方法並沒有對兩者做出本質的區分。

用更深一步的眼光去看對角線法，它其實是自然數域到實數域的一類映射

例如，使用 $0 ightarrow 1,1 ightarrow 2,2 ightarrow 0$ 這樣的變換關係，設 $a_1=0. dot{1} dot{2} dot{0}$

$a_1=0.120120...\ a_2=0.220120...\ a_3=0.200120...\ a_4=0.201120...\ a_5=0.201220...$

...

$a_n$ 的小數點後n-1位使用對角線法則根據 $a_1$ 到 $a_{n-1}$ 變換，從第n位往後照抄 $a_{n-1}$

可以發現用此方法可以拓展出無限的數列，並且按照一定的規律排列，對這樣的數列使用康托爾方法，即使n足夠大，總可以找到 $a_{n+1}$ 滿足條件，且 $a_{n+1}$ 滿足排序規律。

從這個角度看康托爾對角論證法，其實更加類似於「取所有的自然數構成一個集合，這些自然數從小到大排列，最大的記為 $N$ ，那麼至少有一個自然數不在這個集合內，例如 $N+1$ 」。這個謬誤在於：自然數是無窮的，找不到一個最大的數，正如小數點後的數位是無窮多是一個道理。因此在我看來這仍然屬於可數而無法窮舉的問題。

最後，關於實數不可數的證明，回到開頭第一句話，即證明不存在相鄰的兩個實數：

用反證法的證明應當是：假設實數可數 $Rightarrow$ 實數可以按大小依次排列 $Rightarrow$ 對其中一對大小相鄰的數，找出一個數介於兩者之間 $Rightarrow$ 歸謬，即證明

$forall x_1,x_2in R ,x_1<x_2;exists xin R,xin left( x_1,x_2 ight)$

PS：本人非民科，期望大家指出疑點！

我是從科學哲學的角度來考慮的，作為一個思想實驗，對角線論證方法從邏輯上（而不是基於現實條件）就是無法結束的，因而也是無效的。本質上，人類永遠只有關於有限領域的經驗，而不可能具有關於無限領域的經驗。所以康托爾體系只是一個把基於有限領域的經驗外推到無限領域（比如把「所有元素一一對應則兩集合相等」默認為對無窮集合也有效）建立起來的假設。如果把「從集合A中取出所有集合B的元素後還有多餘，則A&>B」默認為對無窮集合也有效，大概也能建立一套自洽的集合論體系吧。這就跟歐幾里德幾何和非歐幾何的共存一樣，關鍵在於，對於無限（大的集合、或長的線），我們不可能有經驗，永遠只能假定。

可能我需要補充說明一下，在這裡，「我認為康托爾的論證無效」與「我認為康托爾的結論不對」是兩碼事。我真正的觀點是無窮集合等勢的問題，就好像平行線在無窮遠處有沒有相交的問題一樣，不是單單在數學範圍內來解決的。數學當然可以定義並研究沒有經驗的對象，但這跟數學能不能解決這個具體問題還是兩碼事。-2016.12.29