第2章　無(wú)理數(shù)和超越數(shù)

從1，2，3,…開(kāi)始數(shù)起，只要我們?cè)敢饩涂梢砸恢睌?shù)下去。這些數(shù)就是我們熟知的基數(shù)、整數(shù)，或者說(shuō)自然數(shù)。它們看起來(lái)確實(shí)相當(dāng)自然，因?yàn)橛钪嬷杏泻芏辔覀兛梢杂?jì)數(shù)的物體。自然數(shù)也許是早期人類想象出的第一個(gè)數(shù)學(xué)對(duì)象。一些動(dòng)物似乎也有數(shù)的概念，只要這些數(shù)不是太大。

幾百年來(lái)，零一直不算作自然數(shù)，甚至至今也沒(méi)有共識(shí)。（在教科書的數(shù)論部分，作者通常會(huì)在第一頁(yè)標(biāo)明是否將零歸入自然數(shù)。）負(fù)整數(shù)位于零的另一側(cè)，正整數(shù)、負(fù)整數(shù)及零共同構(gòu)成了整數(shù)集合。整數(shù)在正負(fù)兩個(gè)方向趨向無(wú)窮大：

...　-3　-2　-1　0　1　2　3　...

我們將從1開(kāi)始的所有正的整數(shù)稱為正整數(shù)。對(duì)于那些從零開(kāi)始的正整數(shù)集合（即0，1，2，3，…），可以稱為非負(fù)整數(shù)，既明確，也不會(huì)太冗長(zhǎng)。

有理數(shù)是可以表示為兩個(gè)整數(shù)之比的數(shù)，但是分母不能為零。例如，

是一個(gè)有理數(shù)，它也可以寫成小數(shù)形式：

0.6

有理數(shù)包含所有整數(shù)，因?yàn)槿魏握麛?shù)（例如47）都可以寫成分母為1的分?jǐn)?shù)形式：

任何有限小數(shù)也是有理數(shù)。例如，

-23.45678

可以寫成比的形式：

有些有理數(shù)，例如：

的小數(shù)形式會(huì)寫成無(wú)限循環(huán)小數(shù)：

0.3333333333...

因?yàn)樗軐懗杀鹊男问?，所以仍然是個(gè)有理數(shù)。實(shí)際上，任何無(wú)限循環(huán)小數(shù)都是有理數(shù)，下面這個(gè)數(shù)，

0.234562345623456...

如果23456會(huì)重復(fù)出現(xiàn)，那么它就是個(gè)有理數(shù)。為了證明這個(gè)數(shù)是有理數(shù)，我們用x表示這個(gè)數(shù)

x = 0.234562345623456...

然后等式兩邊同時(shí)乘以100000：

100000x = 23456.23456234562346...

我們知道，等式兩邊同時(shí)減去相同數(shù)值，等式仍然成立。也就是說(shuō)，在第二個(gè)等式中，可以讓等式兩邊的數(shù)同時(shí)減去第一個(gè)等式的數(shù)：令10000_x_和23456.23456...分別減去x和0.23456...，這樣分?jǐn)?shù)部分就消失了：

99999x = 23456

所以：

這是一個(gè)整數(shù)比，所以它是有理數(shù)。

大致看來(lái)，有理數(shù)集似乎是完備的。如果把兩個(gè)有理數(shù)相加，結(jié)果還是有理數(shù)；同樣，將有理數(shù)相減、相乘或相除，結(jié)果仍然是有理數(shù)。

也許有人會(huì)想（就像以前人們那樣），所有的數(shù)都是有理數(shù)，但是如果考慮這個(gè)直角三角形的斜邊：

根據(jù)勾股定理，

x² = 1² + 1²

即：

x² = 2

也即：

是否存在某個(gè)整數(shù)與整數(shù)的比值，當(dāng)它乘以自身時(shí)等于2？當(dāng)然，人們可以找到許多非常接近的有理數(shù)。下面就是個(gè)例子：

這個(gè)有理數(shù)很接近，只差一點(diǎn)點(diǎn)了。當(dāng)它乘以自身時(shí)得到1.999 95。如果我們繼續(xù)尋找，也許可以找到一個(gè)完美的答案。

但也許我們這樣做只是在浪費(fèi)時(shí)間？

證明一些東西不存在是很困難的，但是數(shù)學(xué)家們發(fā)明了一種在類似情況下巧妙解決問(wèn)題的證明方法。這個(gè)方法叫做間接證法，又稱歸謬法、背理法。先提出一個(gè)假設(shè)，然后根據(jù)這個(gè)假設(shè)進(jìn)行符合邏輯的推理，直到推出一個(gè)矛盾的結(jié)論。這個(gè)矛盾的結(jié)論說(shuō)明我們最初的假設(shè)是錯(cuò)誤的。

歸謬法看起來(lái)拐彎抹角，但是它在現(xiàn)實(shí)生活中的應(yīng)用也許比我們想象的更普遍，“不在場(chǎng)證明”就是一種歸謬法。如果被告人被懷疑在犯罪現(xiàn)場(chǎng)，而案件發(fā)生時(shí)他在自己母親的家里，那么就意味著他在同一時(shí)間出現(xiàn)在了兩個(gè)地方，這是荒謬的。

我們假設(shè)2的平方根是有理數(shù)。因?yàn)樗怯欣頂?shù)，所以存在整數(shù)a和b，使得：

a和b是否都是偶數(shù)？如果是，同時(shí)除以2并且用得到的數(shù)來(lái)代替a和b。如果得到的數(shù)仍然是偶數(shù)，再除以2，一直持續(xù)做，直到a和b至少有一個(gè)是奇數(shù)。

等式兩邊同時(shí)平方：

即：

a² = 2b²

注意，a的平方是b的平方的2倍，這就說(shuō)明a的平方是個(gè)偶數(shù)，而要想a的平方為偶數(shù)，a必須為偶數(shù)。先前我們推導(dǎo)出a和b不可能都是偶數(shù)，所以我們知道b是奇數(shù)。

如果a是偶數(shù)，它應(yīng)該等于某個(gè)數(shù)的2倍，我們稱這個(gè)數(shù)為c：

(2c)² = 2b²

即：

4c² = 2b²

也即：

2c² = b²

這說(shuō)明b的平方是偶數(shù)，也就是說(shuō)b是偶數(shù)，這與我們先前的假設(shè)“a和b不能都為偶數(shù)”相悖。

因此，原來(lái)的假設(shè)“2的平方根是有理數(shù)”是錯(cuò)誤的。毫無(wú)疑義，2的平方根是無(wú)理數(shù)。當(dāng)它以小數(shù)形式呈現(xiàn)時(shí)，這些數(shù)字將無(wú)序地排列下去

1.4142135623730950488016887242097...

這個(gè)數(shù)只能在有無(wú)限的紙張、無(wú)數(shù)的筆和無(wú)限的時(shí)間下才能準(zhǔn)確地表達(dá)。我們只可能把它寫成近似值，并用一個(gè)省略號(hào)來(lái)承認(rèn)我們的失敗。要想用有限的方式表達(dá)這個(gè)數(shù)，最貼切的方法是提供計(jì)算這個(gè)數(shù)的算法。（這正是我要在第6章詳細(xì)闡述的。）

我們用“有理”和“無(wú)理”來(lái)形容一個(gè)數(shù)，仿佛數(shù)字真的會(huì)瘋掉一樣。其實(shí)，這是有歷史原因的。有時(shí)無(wú)理數(shù)也稱為“不盡根”（surds），這個(gè)詞和“荒謬”（absurd）有關(guān)。古希臘人對(duì)無(wú)理數(shù)并不陌生，但不怎么喜歡它們。據(jù)說(shuō)（無(wú)可靠歷史依據(jù)），畢達(dá)哥拉斯的學(xué)生希帕索斯在公元前6世紀(jì)發(fā)現(xiàn)2的平方根是無(wú)理數(shù)。故事里還說(shuō)，此發(fā)現(xiàn)引起了軒然大波，畢達(dá)哥拉斯及其追隨者試圖掩蓋這一發(fā)現(xiàn)，甚至把希帕索斯扔進(jìn)了地中海。他們相當(dāng)肯定，無(wú)理數(shù)不存在。丟番圖拒絕承認(rèn)無(wú)理數(shù)是其問(wèn)題的解，延續(xù)了無(wú)理數(shù)不合他口味的這一傳統(tǒng)。

在有了小數(shù)點(diǎn)（古希臘人沒(méi)有）后，我們就能輕易創(chuàng)造一個(gè)數(shù)，它顯然是一個(gè)無(wú)理數(shù)，只要寫下一些無(wú)重復(fù)片段的無(wú)序數(shù)字就行了。這樣一個(gè)小數(shù)，它的小數(shù)部分出奇地怪異，但顯然不會(huì)重復(fù)：

.0010110111011110111110111111...

在小數(shù)點(diǎn)之后，有兩個(gè)0和一個(gè)1，然后一個(gè)0和兩個(gè)1，再后一個(gè)0和三個(gè)1，等等。這不是一個(gè)有理數(shù)！它不能表示成兩個(gè)整數(shù)的比，因此它是無(wú)理數(shù)。

2的平方根是方程：

x² - 2 = 0

的解。這個(gè)等式和先前展示的一樣，只是我們將2移到了等號(hào)的另一邊。17的立方根（同樣也是個(gè)無(wú)理數(shù)）是方程：

x³ - 17 = 0

的解。上面兩個(gè)方程都叫做代數(shù)方程。下面是另一個(gè)代數(shù)方程：

-12x⁵ + 27x⁴ - 2x² + 8x - 4 = 0

代數(shù)方程有一個(gè)變?cè)?，通常表示?em >x。（代數(shù)方程和丟番圖方程不同，丟番圖方程可以有多個(gè)變?cè)＃┐鷶?shù)方程有相加為零的多個(gè)項(xiàng)，上述最后一個(gè)例子里有五項(xiàng)。每一項(xiàng)包含一個(gè)變?cè)膬?，冪為整?shù)或零。（因?yàn)槿魏螖?shù)的零次方都是1，第五項(xiàng)可以表示為-4乘以x的零次方。）任何帶冪的變?cè)汲艘砸粋€(gè)整數(shù)系數(shù)，在這個(gè)例子中，系數(shù)依次是-12、27、-2、8和-4。這些系數(shù)可以是零，就像這個(gè)例子里“丟失”的x的立方項(xiàng)。

代數(shù)方程在現(xiàn)實(shí)問(wèn)題中頻繁出現(xiàn)，所以它們很受重視。代數(shù)方程的一般形式是：

a_Nx^N + a_N-1x^N-1 + ... a₂x² + a₁x + a₀ = 0

其中，N是正整數(shù)，a_i是整數(shù)。它可以更簡(jiǎn)明地寫成：

在我們先前的例子：

-12x⁵ + 27x⁴ - 2x² + 8x - 4 = 0

中，N（最高的指數(shù)，也叫多項(xiàng)式的次數(shù)）是5，a₅是-12，a₄是27，a₃是0，等等。

代數(shù)方程的解（也叫方程的根）稱為代數(shù)數(shù)。一個(gè)N次多項(xiàng)式最多可以有N個(gè)不同的解。在第1章，代數(shù)方程

x² -10x + 21 = 0

有3和7兩個(gè)解。

2的平方根是代數(shù)方程：

x² - 2 = 0

的一個(gè)解，2的負(fù)平方根是另一個(gè)解。

代數(shù)數(shù)的范疇還包括所有整數(shù)和所有有理數(shù)。例如，整數(shù)5是代數(shù)方程：

x - 5 = 0

的解，而3/7是代數(shù)方程：

7x - 3 = 0

的解。有些代數(shù)方程的解只有負(fù)數(shù)的平方根：

x² + 5 = 0

這個(gè)方程看起來(lái)是無(wú)解的，因?yàn)槿魏螖?shù)乘以它本身都是正的量，加上5不可能得0。負(fù)數(shù)的平方根稱作虛數(shù)。（為了方便，-1的平方根記作字母i。）盡管名字如此，但虛數(shù)是一類非常有用的數(shù)，它在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。不過(guò)，圖靈論文和本書并不涉及虛數(shù)。

在18世紀(jì)的某個(gè)時(shí)間，數(shù)學(xué)家們開(kāi)始使用實(shí)數(shù)這一名稱，以便同虛數(shù)區(qū)分開(kāi)。根據(jù)定義，實(shí)數(shù)包括了除負(fù)數(shù)平方根以外的一切數(shù)。

實(shí)數(shù)也稱為連續(xù)統(tǒng)，因?yàn)閷?shí)數(shù)可以看成一條連續(xù)直線上全體點(diǎn)的集合：

這條線上標(biāo)記了一些整數(shù)，但是單靠這些整數(shù)點(diǎn)顯然無(wú)法形成一條連續(xù)的線。

同樣，有理數(shù)全體也不是連續(xù)的。顯然，有理數(shù)在實(shí)數(shù)軸上看上去是非常稠密的。對(duì)于任意兩個(gè)有理數(shù)，例如a和b，你都可以在它們之間插入另一個(gè)有理數(shù)，如a和b的平均數(shù)：

但是，在有理數(shù)之間仍存在無(wú)理數(shù)占據(jù)的間隙。例如，其中的一個(gè)間隙對(duì)應(yīng)了2的平方根。

現(xiàn)在，我們從兩個(gè)角度對(duì)數(shù)進(jìn)行分類。我們已經(jīng)將代數(shù)方程的解定義為了一類，稱作代數(shù)數(shù)，這一類包括整數(shù)、有理數(shù)和許多如平方根和立方根的無(wú)理數(shù)。我們還定義了一類數(shù)，稱作實(shí)數(shù)，它是除負(fù)數(shù)平方根外的其他數(shù)。現(xiàn)在的問(wèn)題是：

所有的實(shí)數(shù)都是代數(shù)數(shù)嗎？是否有些實(shí)數(shù)不是代數(shù)方程的解？

1740年，萊昂哈德·歐拉（1707—1783，一位瑞士出生的孜孜不倦的數(shù)學(xué)家，其名字的諧音是“油壺”¹）猜想，非代數(shù)數(shù)確實(shí)存在，他稱它們?yōu)槌綌?shù)，因?yàn)樗鼈兂搅舜鷶?shù)。證明超越數(shù)存在是艱難的，你如何證明一個(gè)特定的數(shù)不是一些極其冗長(zhǎng)并且無(wú)比繁雜的代數(shù)方程的解？

¹ “油壺”的英文是“oiler”，與歐拉名字“Euler”發(fā)音相似。——編者注

超越數(shù)的存在一直是一個(gè)未解決的問(wèn)題，直到1844年，法國(guó)數(shù)學(xué)家約瑟夫·劉維爾（1809—1882）想出了一個(gè)容易研究的數(shù)，并且成功證明了它不是代數(shù)數(shù)。劉維爾所選數(shù)的小數(shù)點(diǎn)后30位是：

.110001000000000000000001000000...

但是這個(gè)片段并不能完全揭示它的完整形式，劉維爾利用階乘構(gòu)造了這個(gè)奇特的數(shù)。一個(gè)數(shù)的階乘是小于等于這個(gè)數(shù)的所有正整數(shù)的乘積，用感嘆符號(hào)來(lái)表示：

1! = 1　　　　　　　　　　　　　

2! = 1 × 2 = 2　　　　　　　 　

3! = 1 × 2 × 3 = 6　　　　　　

4! = 1 × 2 × 3 × 4 = 24　　　

5! = 1 × 2 × 3 × 4 × 5 = 120

等等。劉維爾數(shù)（通常這樣稱呼它）在小數(shù)點(diǎn)后第1，2，6，24，120，...位為1，其余位置為0。劉維爾設(shè)計(jì)了這樣一個(gè)數(shù)，來(lái)證明它不是任何代數(shù)方程的解。越來(lái)越稀疏的非零數(shù)字是這個(gè)證明²的關(guān)鍵。

² 這個(gè)證明在Edward B. Burger和Robert Tubbs的著作Making Transcendence Transparent: An Intuitive Approach to Classical Transcendental Number Theory（Springer，2004），9-26中涉及。

1882年，德國(guó)數(shù)學(xué)家費(fèi)迪南德·林德曼（1852—1939）證明了長(zhǎng)久以來(lái)最著名的一個(gè)無(wú)理數(shù)也是超越數(shù)，這個(gè)數(shù)就是π，即圓的周長(zhǎng)與直徑的比：

π=3.1415926535897932384626433832795...

林德曼證明了π不是代數(shù)方程的解，這個(gè)事實(shí)為一個(gè)古老的難題提供了新的視角：在過(guò)去的兩千多年來(lái)，數(shù)學(xué)家和非數(shù)學(xué)家都在嘗試解決的“化圓為方”問(wèn)題。這個(gè)問(wèn)題可以簡(jiǎn)單敘述為：給出一個(gè)圓，用直尺和圓規(guī)構(gòu)建一個(gè)與圓面積相等的正方形。（一個(gè)類似的難題稱為“圓的矯正”，它需要構(gòu)建一條與圓的周長(zhǎng)相等的直線。）人們是如此瘋狂地嘗試解決這個(gè)問(wèn)題，以至于古希臘語(yǔ)中都有了專門表示這一活動(dòng)的詞，從字面上看，它的意思是“四角化”。³

³ 出自E.W. Hobson的Squaring the Circle: A History of the Problem（Cambridge University Press，1913），3。

用直尺和圓規(guī)構(gòu)建一個(gè)幾何圖形與求解某些特定形式的代數(shù)方程是等價(jià)的。因?yàn)棣胁皇侨魏我粋€(gè)代數(shù)方程的解，所以你不能在一個(gè)幾何構(gòu)造中表示這個(gè)數(shù)。這就意味著，用直尺和圓規(guī)構(gòu)建一個(gè)與圓面積相等的正方形是不可實(shí)現(xiàn)的。

另一個(gè)著名的超越數(shù)用符號(hào)e表示（代表歐拉）。如果計(jì)算

那么在N趨于無(wú)窮大的情況下，結(jié)果會(huì)趨近e：

e = 2.7182818284590452353602874713527...

你也可以用下面這個(gè)包含階乘的無(wú)限數(shù)列計(jì)算e：

你可以計(jì)算它，但它不是任何一個(gè)代數(shù)方程的解。

在過(guò)去的這個(gè)世紀(jì)中，許多數(shù)已經(jīng)被證明是超越數(shù)了，但是仍然沒(méi)有一種通用方法來(lái)證明一個(gè)數(shù)是不是超越數(shù)。例如，對(duì)于下面這個(gè)數(shù)仍然沒(méi)有結(jié)論：

π^π

圖靈論文（以及本書）將數(shù)限定在了實(shí)數(shù)（非虛數(shù)）。下面的圖匯總了實(shí)數(shù)領(lǐng)域內(nèi)幾個(gè)最重要的類別。

這個(gè)圖沒(méi)有按比例來(lái)畫。

等等，這么說(shuō)是什么意思？

這些類別中的數(shù)都有無(wú)窮多個(gè)，不是嗎？無(wú)窮多個(gè)整數(shù)，無(wú)窮多個(gè)有理數(shù)，無(wú)窮個(gè)無(wú)理數(shù)，不是嗎？無(wú)窮是無(wú)窮的，不是嗎？沒(méi)有不同大小的無(wú)窮，不是嗎？不存在一個(gè)無(wú)窮大于另一個(gè)無(wú)窮，不是嗎？

對(duì)嗎？

不論我們是從哲學(xué)、神學(xué)還是數(shù)學(xué)哪個(gè)方面談及無(wú)窮，它永遠(yuǎn)都不是一個(gè)簡(jiǎn)單的話題。然而在數(shù)學(xué)中，無(wú)窮幾乎不可回避，我們不得不鼓起所有勇氣去研究無(wú)窮這個(gè)概念。

自然數(shù)的無(wú)限增大似乎是無(wú)窮大這個(gè)概念的根源。無(wú)論我們數(shù)到哪個(gè)數(shù)，總能再多數(shù)一個(gè)。實(shí)數(shù)當(dāng)然也是可以無(wú)限增大的，但那只是因?yàn)樗鼈儠?huì)跟著自然數(shù)一起增加。當(dāng)我們一次又一次地細(xì)分連續(xù)統(tǒng)時(shí)，我們便開(kāi)始思考實(shí)數(shù)的無(wú)窮小了。

這兩個(gè)無(wú)窮——無(wú)窮無(wú)盡的自然數(shù)和無(wú)窮稠密的連續(xù)統(tǒng)——在某些方面有相似之處嗎？或者說(shuō)它們完全不同？

如果我們掌握了集合論的一些基本知識(shí)，接下來(lái)的討論就會(huì)簡(jiǎn)單些了。集合是由一些稱作集合元素的對(duì)象組成的。集合通常用大括號(hào)表示，例如，

{1,2,3,4}

是前四個(gè)自然數(shù)的集合。集合里的元素是唯一的，比如不允許出現(xiàn)兩個(gè)4。集合里元素的排列順序無(wú)關(guān)緊要，集合

{4,1,3,2}

與前一個(gè)集合是一樣的。集合中元素的個(gè)數(shù)稱作基數(shù)，也叫勢(shì)。上面的有限集合的基數(shù)是4。具有相同基數(shù)的集合稱作等勢(shì)的集合。

有些集合的勢(shì)是有限的，有些集合的勢(shì)是無(wú)限的。正整數(shù)集合：

{1,2,3,...}

的勢(shì)顯然是無(wú)限的。正偶數(shù)集合的勢(shì)也是無(wú)限的：

{2,4,6,...}

這兩個(gè)集合的勢(shì)之間有什么關(guān)系呢？

我們也許會(huì)脫口而出，第一個(gè)集合的元素個(gè)數(shù)是第二個(gè)集合的元素個(gè)數(shù)的兩倍，因?yàn)榈诙€(gè)集合少了所有的奇數(shù)。這當(dāng)然只是片面的看法。如果這兩個(gè)集合都是有限的，那么這種看法確實(shí)是對(duì)的。但是，這兩個(gè)集合都是無(wú)限的，我們?cè)趺茨苷f(shuō)一個(gè)集合是另一個(gè)集合的兩倍呢？

我們來(lái)數(shù)一下第二個(gè)集合的元素。什么叫做“數(shù)”？它的意思是將這些元素與我們數(shù)數(shù)時(shí)心中默念的自然數(shù)“1，2，3，...”一一對(duì)應(yīng)起來(lái)。

我們可以通過(guò)與自然數(shù)做一一對(duì)應(yīng)，來(lái)數(shù)無(wú)限集合里的正偶數(shù)：

對(duì)于每一個(gè)正整數(shù)，都有一個(gè)偶數(shù)與之對(duì)應(yīng)。對(duì)于任何一個(gè)偶數(shù)，都有一個(gè)正整數(shù)與之對(duì)應(yīng)。這么一看，這兩個(gè)集合現(xiàn)在似乎變得一樣大了，也就是說(shuō)它們是等勢(shì)的。這是怎么回事？（事實(shí)上，無(wú)限集合的這種獨(dú)有特征是伽利略在1683年⁴提出的，因此有時(shí)也稱作伽利略悖論。）

⁴ 伽利略·伽利萊，Two New Sciences （《兩種新科學(xué)》），2E，Stillman Drake譯（Wall & Emerson，2000），40-41。翻譯基于 Opere di Galileo Galilei（Florence，1898），VIII，78-79。顯然，伽利略不是第一個(gè)發(fā)現(xiàn)這個(gè)悖論的人。至于其他人，見(jiàn)斯蒂芬·科爾·克萊尼的《數(shù)學(xué)的邏輯》（Mathematical Logic，Wiley，1967，Dover，2002），pg.176，腳注121。

似乎沒(méi)有人過(guò)多關(guān)注過(guò)這個(gè)悖論，直到格奧爾格·康托爾（1845—1918）跟它較起勁來(lái)?？低袪?，偉大的數(shù)學(xué)家，出生于圣彼得堡，以建立集合論而聞名。他的父親是一名商人，在各方面引導(dǎo)兒子出類拔萃，他的母親出身于博姆音樂(lè)世家?？低袪枍渎读俗约涸谒囆g(shù)和音樂(lè)上的天賦，但是他在17歲時(shí)決定“獻(xiàn)身于數(shù)學(xué)”。⁵他去了蘇黎世理工學(xué)院和柏林大學(xué)。1869年，康托爾在哈雷大學(xué)獲得了一份教學(xué)工作，并在那里度過(guò)了余生。

⁵ 約瑟夫·沃倫·道本，Georg Cantor：His Mathematics and Philosophy of the Infinite（Harvard University press，1979，Princeton University Press，1990），277。

在1873年寄給數(shù)學(xué)家理查德·戴德金（1831—1916）的一封信中，康托爾探索了類似自然數(shù)與偶數(shù)之間的對(duì)應(yīng)，并且考慮是否可以在自然數(shù)和實(shí)數(shù)之間建立類似的對(duì)應(yīng)。他懷疑這不可能，但是無(wú)法解釋這是為什么。“我找不到我要尋找的答案，也許它很簡(jiǎn)單?！笨低袪枌懙?，⁶這是他著名的一句。

⁶ 格奧爾格·康托爾寫于1873年11月29日的書信，來(lái)自From Kant to Hilbert:A Source Book in the Foundations of Mathematics（Oxford University Press，1996），Vol. II，844。

如果集合中的元素能與自然數(shù)一一對(duì)應(yīng)，那么我們稱這個(gè)集合為可數(shù)的。如果我們能將集合中的元素按照某種方式排序或列舉出來(lái)，那么這個(gè)集合就是可數(shù)的，因?yàn)槿魏我粋€(gè)列表都是可以標(biāo)號(hào)的，也就是將各項(xiàng)與自然數(shù)1，2，3，...一一配對(duì)。所有有限集合當(dāng)然都是可數(shù)的。真正的難題來(lái)自于無(wú)限集合。

例如考慮由全體整數(shù)構(gòu)成的集合，其中包含正整數(shù)、負(fù)整數(shù)和零。這個(gè)集合是可數(shù)的嗎？是的。因?yàn)槲覀兛梢詮牧汩_(kāi)始列舉所有這些整數(shù)：

　 　 0

　 　 1

　 　-1

　 　 2

　 　-2

　 　 3

　 　-3

　 　...

這不是列舉整數(shù)的通常方法，但是它向我們展示了，單個(gè)列表能包含所有的整數(shù)。

有趣的是，有理數(shù)也是可數(shù)的。我們從正有理數(shù)開(kāi)始，而且不要擔(dān)心數(shù)列里有一些重復(fù)的數(shù)：

1/1

1/2

2/1

1/3

2/2

3/1

1/4

2/3

3/2

4/1

...

看出規(guī)律了嗎？數(shù)列中第一項(xiàng)的分子分母之和是2，接下來(lái)兩項(xiàng)的分子分母之和是3，之后三項(xiàng)的分子分母之和是4，以此類推。這個(gè)列表就包含了所有的正有理數(shù)。只需一正一負(fù)地交替列舉，我們便能把負(fù)有理數(shù)也加進(jìn)來(lái)。因此，有理數(shù)是可數(shù)的。

在1874年發(fā)表的一篇論文“關(guān)于實(shí)代數(shù)數(shù)集合的性質(zhì)”⁷中，康托爾指出甚至代數(shù)數(shù)都是可數(shù)的。正如我們知道的，代數(shù)數(shù)是代數(shù)方程的解，代數(shù)方程的一般式是

a_Nx^N + a_N-1x^N-1 + ... a₂x² + a₁x + a₀ = 0

⁷ 可從From Kant to Hilbert，Vol. Ⅱ，839-843查到。

其中N是正整數(shù)，a_i是整數(shù)。對(duì)于任何一個(gè)代數(shù)方程，將所有的系數(shù)（a_i的絕對(duì)值 ）和N相加，我們稱所得的值為方程的高。對(duì)于某個(gè)特定的高（例如5），存在有限個(gè)數(shù)的方程，每個(gè)方程至多有N個(gè)解。所以，所有的代數(shù)數(shù)都可以根據(jù)它的高和解來(lái)排列。因此，代數(shù)數(shù)是可數(shù)的。

那么超越數(shù)呢？超越數(shù)是否可以按照某種方式列成一張表？這看上去極不可能！我們甚至沒(méi)有檢測(cè)一個(gè)特定的數(shù)是否是超越數(shù)的一般步驟！

那么包含了代數(shù)數(shù)和超越數(shù)的實(shí)數(shù)呢？實(shí)數(shù)可數(shù)嗎？

在1874年康托爾證明代數(shù)數(shù)可數(shù)的同一篇論文中，他也證明了實(shí)數(shù)是不可數(shù)的。

康托爾首先假設(shè)實(shí)數(shù)是可數(shù)的。他假設(shè)存在一種枚舉實(shí)數(shù)的方法，并且這些實(shí)數(shù)已經(jīng)按照這種方式排列好了，我們用帶下標(biāo)的希臘字母ω來(lái)標(biāo)記：

ω₁　ω₂　ω₃　ω₄　ω₅　ω₆　...

康托爾打算證明這個(gè)列表是不完整的——無(wú)論怎樣構(gòu)造這個(gè)列表，它都不可能包含所有的實(shí)數(shù)。

隨便選擇一個(gè)數(shù)α和一個(gè)稍大的數(shù)β。你可以像這樣在數(shù)軸上表示這兩個(gè)數(shù)：

現(xiàn)在，從左至右依次查看那個(gè)列表里的數(shù)，找出兩個(gè)大小在α和β之間的實(shí)數(shù)，這兩個(gè)數(shù)均大于α并且小于β。我們稱這兩個(gè)數(shù)中小的那個(gè)為α'，大一些的為β'：

從剛才停下來(lái)的地方開(kāi)始，繼續(xù)往下搜索列表，直到碰上兩個(gè)新的大小介于α'和β'之間的數(shù)，稱這兩個(gè)數(shù)為α"和β"

繼續(xù)：

這個(gè)過(guò)程顯然可以無(wú)限進(jìn)行下去。你總能在剛才的兩個(gè)數(shù)之間再找到兩個(gè)新的數(shù)。

你怎么知道的？很簡(jiǎn)單。假設(shè)你被卡在了這一步

上標(biāo)(v)表明有v個(gè)小撇，也許是一億億億個(gè)，但仍是個(gè)有限的數(shù)?，F(xiàn)在，無(wú)論如何繼續(xù)在枚舉好的實(shí)數(shù)列表中搜索，都不能在α^(v)和β^(v)之間找到另一組數(shù)。很顯然，你的實(shí)數(shù)列表是不全的。這個(gè)列表缺少了α^(v)和β^(v)之間的每一個(gè)數(shù)。例如，夾在α^(v)和β^(v)正中間的數(shù)是這兩個(gè)數(shù)的平均數(shù)，也即：

這還只是個(gè)開(kāi)始。你的數(shù)列漏掉了許多數(shù)。

這就是你知道這個(gè)過(guò)程必定會(huì)無(wú)限進(jìn)行下去的原因。所有的α會(huì)持續(xù)增大，而β會(huì)持續(xù)減小，但是最大的α不能大于最小的β。（當(dāng)你在最后一組α和β之間找到兩個(gè)新數(shù)的時(shí)候，那個(gè)小的數(shù)總是α，大的數(shù)總是β。）α和β都有一個(gè)界線（極限），康托爾用無(wú)窮符號(hào)作為上標(biāo)來(lái)標(biāo)記：α^∞和β^∞。

α^∞是否可能小于β^∞？我們來(lái)看一下：

不，這不可能。如果α永遠(yuǎn)不會(huì)大于α^∞并且β永遠(yuǎn)不會(huì)小于β^∞，那么這個(gè)實(shí)數(shù)數(shù)列就會(huì)丟失每一個(gè)在α^∞和β^∞之間的數(shù)，第一個(gè)能想到的就是：

α^∞一定等于β^∞?？低袪柗Q這個(gè)極限為η（希臘字母eta）：

因?yàn)檫@是一個(gè)永遠(yuǎn)持續(xù)的過(guò)程（我們已經(jīng)說(shuō)明了它不可能在某一點(diǎn)停下來(lái)），α永遠(yuǎn)無(wú)法達(dá)到η，β也如此?，F(xiàn)在，你知道這是什么意思了，對(duì)嗎？這意味著，η不在最初的那個(gè)實(shí)數(shù)列表里！

如果η真的在這個(gè)實(shí)數(shù)數(shù)列里，那么它本該在某一次搜索下一個(gè)α和β的時(shí)候出現(xiàn)，但考慮數(shù)列中搜索到η之前的那一對(duì)α和β：

現(xiàn)在這個(gè)實(shí)數(shù)列表里漏掉了在α^(v)與β^(v)之間除了η以外的每一個(gè)數(shù)。

我們考慮完了所有情形。沒(méi)有一個(gè)成立，沒(méi)有一個(gè)符合邏輯，這都怪我們最原始假設(shè)是錯(cuò)的——我們假設(shè)了實(shí)數(shù)是可枚舉的，這一切一定都是因?yàn)槲覀兏咀霾坏竭@一點(diǎn)。

整數(shù)是可數(shù)的，有理數(shù)是可數(shù)的，甚至代數(shù)數(shù)是可數(shù)的。然而，實(shí)數(shù)都是不可數(shù)的。

康托爾考慮將實(shí)數(shù)不可數(shù)的性質(zhì)作為超越數(shù)存在的新證據(jù)。（如果超越數(shù)不存在，那么實(shí)數(shù)就等同于代數(shù)數(shù)，從而可數(shù)。）康托爾最終意識(shí)到至少有兩種無(wú)窮：可數(shù)的無(wú)窮和不可數(shù)的無(wú)窮，即自然數(shù)的無(wú)窮和連續(xù)統(tǒng)的無(wú)窮。自然數(shù)、有理數(shù)，甚至代數(shù)數(shù)的無(wú)限集合都是可數(shù)的。當(dāng)我們將超越數(shù)放進(jìn)來(lái)的時(shí)候，我們突然間就置身在一個(gè)完全不同的世界中了。我們眼前有兩種不同的無(wú)窮的勢(shì)：一種勢(shì)適用于自然數(shù)、有理數(shù)與代數(shù)數(shù)；另一種勢(shì)適用于實(shí)數(shù)和連續(xù)統(tǒng)。

康托爾的成果在當(dāng)時(shí)飽受爭(zhēng)議，他自己也一直沒(méi)能擺脫這種爭(zhēng)議。自康托爾后，沒(méi)有哪個(gè)數(shù)學(xué)家再像他那樣思考無(wú)窮了?？蓴?shù)的無(wú)窮和不可數(shù)的無(wú)窮之間的區(qū)別已被證明是極其有用的，即使想象一種簡(jiǎn)單的無(wú)窮就足以震撼人心。

有一種流行的說(shuō)法是，對(duì)無(wú)窮的冥思苦想讓康托爾本人最后瘋掉了。康托爾確實(shí)在他生命的最后20年中經(jīng)常出入精神病院，但這也許是一種跟職業(yè)無(wú)關(guān)的躁郁癥。⁸然而，最糟糕的是，疲勞和壓力經(jīng)常使他的精神疾病發(fā)作，而且這種壓力與其非傳統(tǒng)的數(shù)學(xué)理論是否被接受息息相關(guān)。在休養(yǎng)期間，他的興趣已不在數(shù)學(xué)上了。他研究過(guò)哲學(xué)、神學(xué)、形而上學(xué)，以及“培根是莎士比亞戲劇的真正作者”這一假說(shuō)。

⁸ 道本，Georg Cantor，285。

有限集合與無(wú)限集合有很多不同，其中一個(gè)很大的不同就是真子集，也就是那些與集合自身不相同的子集。有限集合的真子集總是有較小的基數(shù)，這一點(diǎn)顯而易見(jiàn)。無(wú)限集合的真子集也可以有較小的基數(shù)。（例如，自然數(shù)集就是實(shí)數(shù)集的真子集，它們的基數(shù)是不同的。）然而在有些情況下，有些集合的真子集有著與集合本身一樣的基數(shù)。這只對(duì)無(wú)限集合成立。自然數(shù)集是整數(shù)集的真子集，整數(shù)集是有理數(shù)集的真子集，有理數(shù)集又是代數(shù)數(shù)集的真子集。所有這些無(wú)限集合都有相同的基數(shù)，它們是等勢(shì)的。

實(shí)數(shù)的各種真子集也有可能是相互等勢(shì)的。想想1與0之間的實(shí)數(shù)。這些數(shù)可以與大于1的實(shí)數(shù)一一對(duì)應(yīng)，只要把每個(gè)數(shù)都用1除一下就好了。例如，0.5對(duì)應(yīng)2，0.25對(duì)應(yīng)4，0.1對(duì)應(yīng)10，0.0001對(duì)應(yīng)10000。這一事實(shí)非常有用，意味著我們可以考察0和1之間的實(shí)數(shù)的某些性質(zhì)，其結(jié)論將適用于所有的實(shí)數(shù)。（圖靈在他的論文中運(yùn)用到了這一概念，康托爾也用到了它。）

康托爾在探索無(wú)限集合時(shí)還有其他驚人發(fā)現(xiàn)。他發(fā)現(xiàn)我們可以在連續(xù)統(tǒng)（直線上的實(shí)數(shù)）和平面上的點(diǎn)，乃至N維空間中的點(diǎn)之間建立一一對(duì)應(yīng)關(guān)系。

下面我們只看x和y坐標(biāo)都在0和1之間的那部分平面區(qū)域。平面上的任何一點(diǎn)都可以表示為數(shù)字對(duì)(x， y)，并且這兩個(gè)數(shù)中的任何一個(gè)數(shù)小數(shù)點(diǎn)后都有無(wú)窮位。在下面的表示中，x的小數(shù)點(diǎn)后每一位都用帶有下標(biāo)的a來(lái)表示：

x = .a₁a₂a₃a₄...

y同樣如此：

y = .b₁b₂b₃b₄...

現(xiàn)在，把這些數(shù)插在一起，形成一個(gè)新的數(shù)：

.a₁b₁a₂b₂a₃b₃a₄b₄...

這是由兩個(gè)實(shí)數(shù)壓在一起形成的一個(gè)實(shí)數(shù)。每一個(gè)二維的點(diǎn)都對(duì)應(yīng)著連續(xù)統(tǒng)上的一個(gè)實(shí)數(shù)。因此，平面上的所有點(diǎn)和直線上的實(shí)數(shù)有著一樣的基數(shù)?？低袪柋贿@個(gè)發(fā)現(xiàn)震撼得說(shuō)不出話來(lái)。他在給戴德金的信⁹中寫道：“Je le vois, mais je ne le crois pas.”（我了解它，但我不相信它。）

⁹ 1877年6月29日的信，From Kant to Hilbert，Vol. Ⅱ，860。

1891年，康托爾發(fā)表了另一個(gè)實(shí)數(shù)不可數(shù)的證明，¹⁰從那以后，這個(gè)證明至今令人拍案叫絕。康托爾的證明涉及了集合而非數(shù)字，并且比我即將展示的例子更具一般性，二者思路是一樣的。這種思路被稱作對(duì)角線證明法（diagonal proof）、對(duì)角線過(guò)程（diagonal process）、對(duì)角線論證（diagonal argument）或者對(duì)角化（diagonalization），原因大家馬上就知道了。無(wú)論怎么稱呼它，總少不了對(duì)角線一詞。

¹⁰ 格奧爾格·康托爾，“關(guān)于流形理論的一個(gè)基本問(wèn)題”，From Kant to Hilbert，Vol. Ⅱ，920-922。

來(lái)看0和1之間的實(shí)數(shù)。假設(shè)我們?cè)O(shè)計(jì)了一種列出所有實(shí)數(shù)的方法。（正如你所料，這是另一個(gè)反證法。）假設(shè)這個(gè)排列像下面這樣：

.1234567890...

.2500000000...

.3333333333...

.3141592653...

.0101101110...

.4857290283...

.0000000000...

.9999999999...

.7788778812...

.2718281828...

...　　　　 　

我們似乎有了一個(gè)良好的開(kāi)端。這個(gè)數(shù)列包括0、1/4、1/3、π/10、e/10，還有之前那個(gè)連續(xù)數(shù)字“1”越來(lái)越多的無(wú)理數(shù)，以及一些不大能辨認(rèn)出來(lái)的數(shù)。每個(gè)數(shù)都有無(wú)限的十進(jìn)制小數(shù)位（即使它們都是0），并且這個(gè)列表有無(wú)限多個(gè)數(shù)。

即便這個(gè)列表是無(wú)限的，我們?nèi)匀豢梢哉f(shuō)服自己這里面漏掉了一些東西。我們從左上角到右下角看這個(gè)列表中的數(shù)字，這些數(shù)字用粗體顯示：

.1234567890...

.2500000000...

.3333333333...

.3141592653...

.0101101110...

.4857290283...

.0000000000...

.9999999999...

.7788778812...

.2718281828...

...　　　　　　 　

現(xiàn)在用這些粗體數(shù)字構(gòu)建一個(gè)數(shù)：

.1531190918...

因?yàn)閷?shí)數(shù)列表是無(wú)限的，每個(gè)數(shù)的位數(shù)也是無(wú)限的，所以上面這個(gè)數(shù)有無(wú)限位。現(xiàn)在將這個(gè)數(shù)的每一位都增加1。如果這一位是9，就把它變成0：

.2642201029...

這個(gè)新數(shù)是否在原來(lái)的列表里？讓我們一步一步來(lái)看：這個(gè)新數(shù)是否是列表中的第一個(gè)數(shù)？不是，因?yàn)榱斜砝锏谝粋€(gè)數(shù)的第一個(gè)位是1，而這個(gè)新數(shù)的第一位是2。

這個(gè)數(shù)是列表中的第二個(gè)數(shù)嗎？也不是，因?yàn)閿?shù)列中第二個(gè)數(shù)的第二位是5，而新數(shù)的第二位是6。

這個(gè)數(shù)是數(shù)列中的第三個(gè)數(shù)嗎？不是，因?yàn)閿?shù)列中第三個(gè)數(shù)的第三位是3，而新數(shù)的第三位是4。

等等等等。這個(gè)新數(shù)不是列表里的第N個(gè)數(shù)，因?yàn)榈?em >N個(gè)數(shù)的第N位與這個(gè)新數(shù)的第N位不相等。

因此，這個(gè)列表是不全的，我們先前的假設(shè)有問(wèn)題。枚舉0和1之間的所有實(shí)數(shù)是不可能的，我們?cè)俅慰吹綄?shí)數(shù)是不可數(shù)的。

當(dāng)我們對(duì)代數(shù)數(shù)進(jìn)行同樣的操作會(huì)發(fā)生什么？我們已經(jīng)知道如何枚舉代數(shù)數(shù)，這不是問(wèn)題。當(dāng)構(gòu)建一條對(duì)角線并且改變所有位上的數(shù)字時(shí)，所生成的數(shù)并不在這個(gè)列表中。這就意味著生成的數(shù)不是代數(shù)數(shù)，而是超越數(shù)。

你可以將代數(shù)數(shù)按照多種不同的方式排列，你可以制定不同的規(guī)則讓對(duì)角線和原數(shù)列中的每一個(gè)數(shù)都不同。每次這么做，你都將得到一個(gè)新的超越數(shù)。

1895年，康托爾選擇用希伯來(lái)文字母表中的第一個(gè)字母加上下標(biāo)0（，讀作“阿列夫零”）來(lái)表示可數(shù)的自然數(shù)集合（因此也是任何可數(shù)的無(wú)限集合）的基數(shù)?？低袪柗Q這是第一超限數(shù)。他將它與其他超限數(shù)（、、等）結(jié)合起來(lái)建立了超限數(shù)的整個(gè)數(shù)學(xué)體系。

如果可數(shù)集合的基數(shù)是，那么實(shí)數(shù)的不可數(shù)集合的基數(shù)是什么？我們能否表示這個(gè)基數(shù)？

也許吧。我們先來(lái)看一個(gè)有限的集合，它僅有3個(gè)元素：

{a, b, c}

這個(gè)集合有很多子集，你能構(gòu)造出多少個(gè)來(lái)？（一個(gè)集合的所有子集的集合叫做冪集。）你可以動(dòng)手嘗試一下，但是不要忘了空集和包含所有3個(gè)元素的集合：

{ }　　　 {a, b} 　

{a}　　　{a, c} 　

{b}　　　{b, c} 　

{c}　　　{a, b, c}

含3個(gè)元素的集合共有8個(gè)子集，而且這并非巧合：

2³ = 8

其中指數(shù)是原集合元素的個(gè)數(shù)，結(jié)果是子集的個(gè)數(shù)。一個(gè)含4個(gè)元素的集合有16（2的4次方）個(gè)子集，含5個(gè)元素的集合有32個(gè)子集。

為了更好地揭示這種聯(lián)系，我們還有一個(gè)更具條理的方法來(lái)枚舉這些子集。畫一個(gè)表格，原集合中的每個(gè)元素各占一列，用0和1來(lái)表示這些元素是否在各個(gè)子集中：

a　　　b　　　c　　　子集　 　

0　　　0　　　0　　　{ }　　　

0　　　0　　　1　　　{c}　　　

0　　　1　　　0　　　{b}　　　

0　　　1　　　1　　　{b, c} 　

1　　　0　　　0　　　{a}　　　

1　　　0　　　1　　　{a, c} 　

1　　　1　　　0　　　{a, b} 　

1　　　1　　　1　　　{a, b, c}

這些三位的0和1組合依次與二進(jìn)制數(shù)的0到7相對(duì)應(yīng)。3位得到8個(gè)二進(jìn)制數(shù)。一般的規(guī)則是：

冪集的勢(shì) = 2^{原集合的勢(shì)}

一個(gè)含10個(gè)元素的集合，其冪集含有1024個(gè)元素，一個(gè)含100個(gè)元素的集合，其冪集含有1267650600228229401496703205376個(gè)元素。

再來(lái)關(guān)注自然數(shù)（因?yàn)樾枰?也算進(jìn)來(lái)了）：

{0, 1, 2, 3, 4, 5, ...}

這個(gè)集合的基數(shù)是。它有多少個(gè)子集呢？或者說(shuō)，它的冪集的基數(shù)是多少？它的基數(shù)是：

我們有必要進(jìn)行進(jìn)一步的確認(rèn)。我們來(lái)構(gòu)建一個(gè)與有限集合類似的表格（顯然沒(méi)法畫全）。各列的第一行依次是自然數(shù)集合里的所有元素。每一列的0和1表示該元素在哪些子集中，所得的子集寫在每行最右邊：

0　　　1　　　2　　　3　　　4　　　5　 　 ...　　　子集

0　　　0　　　 0　　　0　　　0　　　0 　 　 ...　　　{ }

1　　　0　　　 0　　　0　　　0　　　0　　　...　　　{0}

0　　　1　　　 0　　　0　　　0　　　0　　　...　　　{1}