可數與不可數集合（countable versus uncountable sets）

並非所有無限都一樣大——這就是這個想法核心處那個令人震驚的真相。一個集合是可數的，若你能把它的成員排進一條編號 1, 2, 3, … 的隊伍裡，使每樣東西終究輪得到，即使隊伍永不結束。整數是可數的，而令人意外的是，分數也是。一個集合是不可數的，若沒有任何這樣的隊伍能觸及一切：無論你怎麼試著列出它的成員，總有東西被漏掉。

精確的工具是雙射，一種完美的一一配對。一個集合可數，當它與自然數 1, 2, 3, …（的某個子集）之間存在雙射；直覺上，你能把它枚舉出來。有限字母表上所有有限字串的集合是可數的：按長度列出，每個長度之內按字典序，每個字串都會出現在某個有限的位置上。所有電腦程式的集合也是可數的，因為每個程式不過是一個有限的符號字串。基數是這個意義下「集合多大」的名稱，而可數無限是最小的無限大小。

下面是通往不可判定性那扇門的關鍵句。所有程式（或機器）的集合是可數的，但即使在只有一個符號的字母表上，所有語言的集合也是不可數的——它是一個可數無限集合的冪集，而 Cantor 的對角線論證顯示這嚴格更大。一個可數的程式集合，不可能與一個不可數的語言集合一一配對。因此必定存在沒有任何程式能辨識的語言——在我們動手建構任何一個之前，就已證明它們存在。這是「某些問題超出一切機器之外」的第一縷誠實氣息。