自然數集合的冪集

讓我們把所有自然數,從 $0$ 開始,收集起來,放在一個菜籃裡,用大括號表示菜籃的範圍,於是,我們把這個擺放了所有自然數的菜籃寫成:

$$\{0,1,2,3,4,5,6,7,8,9,…\}$$
假設你是一個零售商,專門賣裝自然數的菜籃。你知道並非每個人都嚥得下所有自然數,為迎合大眾的口味,你打算先準備好各式各樣自然數組合的菜籃,幫它們加上編號,方便客人訂購。反正你手頭上就有一堆自然數,你決定用自然數幫這些組合加上編號。例如,用 $0$ 代表 $\{1,3\}$ 這個菜籃,用 $1$ 代表另一個菜籃 $\{0,2\}$ ,如此類推。剛開始著手為各種自然數菜籃配對編號,你得到一個列表最前頭的部分:

編號菜籃
{$0$,$1$,$2$,$3$,$4$,$5$,$6$,$7$,$8$,$9$,...}
$0$oyoyoooooo...
$1$yoyooooooo...
$2$yyooyyoooo...
$3$yoyyyooooo...
$4$ooyyoyoooo...
$5$yyyoyyoooo...

這個列表有個簡單的規律,由 $0$ 作為第一行, $1$ 作第二行,每往下一行,編號遞增一。每個編號右方序列的 $y$ 和 $o$ 表示菜籃裡「有」還是「沒有」該位置最上方的自然數,例如第一行右方序列的第一個位置是 $o$ ,表示 $0$ 所配對的菜籃裡沒有 $0$ ;第二個位置是 $y$ ,表示菜籃裡有 $1$ 。於是,跟 $0$ 號相配的菜籃是 $\{1,3\}$ ,跟 $3$ 配的是 $\{0,2,3,4\}$ 。

你一直埋頭幫各個菜籃加編號,直到有一日,不禁問自己:「我甚麼時候才會整理好這個列表?」很可惜,答案是:就算有無限長的生命,無限多的墨水,無限好的精力,你都絕對不可能把這個表列完,因為總有一個菜籃是你未為它配上編號的。

關於這個答案,我們可以用歸謬法做個簡單的證明。首先假定你完成整個列表;即是,假定你將每個自然數組合的菜籃都配上一個自然數作為編號。有個方法可以從這個假定推導矛盾:證明有一個未配上編號的菜籃。找出這個菜籃的程序十分簡單。第一步,把對角線上的 $y$ 和 $o$ 排列收集起來,即是,把(所有 n 的)第 n 行的第 n 個位置上的 $y$ 和 $o$ 收集起來,如第 1 行(即編號 $0$ 右方的序列)的第 1 個位置是 $o$ ,第 2 行(即 $1$ 右方的序列)的第 2 個位置是 $o$,如此類推。用粗體標示,會浮現一條對角線:

編號菜籃
{$0$,$1$,$2$,$3$,$4$,$5$,$6$,$7$,$8$,$9$,...}
$0$oyoyoooooo...
$1$yoyooooooo...
$2$yyooyyoooo...
$3$yoyyyooooo...
$4$ooyyoyoooo...
$5$yyyoyyoooo...

將對角線上的 $y$ 和 $o$ 收集起來,依序排好,會是:

編號菜籃
{$0$,$1$,$2$,$3$,$4$,$5$,...}
$?$oooyoy...

第二步,將 $y$ 和 $o$ 互換,就會是一個全新的菜籃 $\{0,1,2,4,…\}$:
編號菜籃
{$0$,$1$,$2$,$3$,$4$,$5$,...}
$?$yyyoyo...

這個菜籃很明顯不在(假定已完成的)列表裡,因為它第 n 個位置上的 $y$ 或 $o$ 都與列表上第 n 行的第 n 個位置相反,例如,它的第 1 個位置是 $y$ ,而列表裡第 1 行(編號 $0$ 右方的序列)的第 1 個位置卻是 $o$ ,表示這個新菜籃裡有 $0$ ,列表第 1 行的菜籃沒有 $0$ ,所以新菜籃不會等於列表第 1 行的菜籃。同樣地,新菜籃有 $1$ ,與列表第 2 行的菜籃不同;新菜籃有 $2$ ,與第 3 行的菜籃不同;新菜籃沒有 $3$ ,與第 4 行的菜籃不同,如此類推。總有一些自然數是舊菜籃有而新菜籃無,或舊菜籃無而新菜籃有。由此可知,這個新菜籃不在列表裡,你未為它配上任何編號。列表未完成,與最初的假定相矛盾。

你可能會想到,反正自然數有無限多個,只要把剛才的新菜籃加到列表裡,再隨便找一個未用過的自然數編號與之相配,不也可以嗎?正是「不可以」。因為剛才的方法不只證明你那個聲稱完整的列表有所遺漏,而是所有聲稱完整的列表都會有所遺漏。所以,無論你的列表如何配對自然數和自然數菜籃──無論你加多少個自然數來配新菜籃──都必定有尚未配對的菜籃。

為了令這篇亂七八糟的文章看起來更加厲害,把「菜籃」改成「集合」。自然數組合的菜籃即是自然數組合的集合。這堆組合裡面,最「龐大」的正是由所有自然數組成的集合,即是最先出場的 $\{0,1,2,3,4,5,6,7,8,9,…\}$ ,這個「所有自然數的集合」有個很特別的名稱,叫做 $\mathbb{N}$ 。每一個自然數的組合,無論它裡面有多少個自然數,都是 $\mathbb{N}$ 的子集,因此都在 $\mathbb{N}$ 的冪集裡。根據這個證明,縱使自然數本身已有無限多,自然數組合的數目都比自然數的數目還要多。換個更厲害的講法: $\mathbb{N}$ 的冪集的基數(cardinality)比 $\mathbb{N}$ 的基數還要大。

2 則留言:

  1. “把所有自然數,從 0 開始,收集起來,放在一個菜籃裡,用大括號表示菜籃的範圍”
    從一開始就是鬼扯,無窮集合根本是亂扯。
    連No0 的 oyoyooooo... 菜籃根本就沒有從來成功被建構過
    證明當然是鬼扯,不過相信Cantor那套鬼扯就相信吧,數學已經離經叛道了...

    回覆刪除
    回覆
    1. 你的"經"以及"道"所謂何者?
      數學本就是存於純粹理性中的東西
      你可以不接受、不理解
      但別把自己不接受的東西說成鬼扯
      那只顯得自己更無知

      刪除

技術提供:Blogger.