可数的含义
一个集合若是有限的，或能与自然数 ℕ 建立[[bijection|双射]]，则称为[[countable-set|可数]]。具体地说，可数意味着可列：你能把元素排成一个序列 a₀, a₁, a₂, …，使每个元素都出现在某个有限的位置上。自然数、整数、乃至有理数都是可数的——它们有相同的[[cardinality|基数]]，记作 ℵ₀，尽管有理数是[[density-of-the-rationals|稠密]]的而整数是分散的。
Why the rationals Q are countable: a snake through a grid.
List positive rationals p/q in a table, row p, column q:
q=1 q=2 q=3 q=4 ...
p=1 1/1 1/2 1/3 1/4
p=2 2/1 2/2 2/3 2/4
p=3 3/1 3/2 3/3 ...
p=4 4/1 ...
Traverse it along finite diagonals (p+q = 2, then 3, then 4, ...):
1/1 , 1/2 , 2/1 , 1/3 , 2/2 , 3/1 , 1/4 , ...
Skip any fraction not in lowest terms (2/2 already seen as 1/1).
Every positive rational sits on exactly one diagonal, so it
appears at some finite step. Interleave with 0 and negatives:
0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, ...
That is an explicit listing of ALL of Q. Hence Q is countable.康托对角线论证
现在转折来了。实数是[[uncountable-set|不可数]]的：不存在一张能把它们全部捕获的列表。证明是[[cantor-diagonal-argument|康托对角线论证]]，它用反证法。为导出矛盾，假设 [0, 1) 中每个实数都能列成 x₀, x₁, x₂, …。我们将制造一个可证明不在你列表中的实数，从而与「列表完整」的假设矛盾。
Cantor's diagonal argument (proof by contradiction).
Assume ALL reals in [0,1) are listed by their decimal digits:
x0 = 0 . d00 d01 d02 d03 ...
x1 = 0 . d10 d11 d12 d13 ...
x2 = 0 . d20 d21 d22 d23 ...
x3 = 0 . d30 d31 d32 d33 ...
^
the diagonal digits are d00, d11, d22, d33, ...
Build a new number y = 0 . e0 e1 e2 e3 ... by the rule
e_k = 5 if d_kk is not 5
e_k = 4 if d_kk is 5
(any rule avoiding 0 and 9 dodges the 0.4999...=0.5000... issue).
Then y differs from x_k in its k-th digit, for EVERY k:
e_k != d_kk by construction.
So y is not x0, not x1, not x2, ... -- y is on NO row.
But y is a real in [0,1), so the list was not complete.
Contradiction. Therefore [0,1), and hence R, is uncountable.停下来欣赏其优雅。对角线数 y 被精心设计成在第 k 位与第 k 行不同，因此它不可能是任何一行。结论是永久的：ℝ——[[the-continuum|连续统]]——的基数严格大于 ℕ。实数确实比有理数多，尽管二者都是无穷。这一刻，无穷不再是单一的概念，而成为一个层级。