大家知道，如果一個集的元素可以和正整數集 N 的元素一一對應的話，那麼這個集稱為可數的（countable）。例如：整數集 Z 是可數的，因為它可以和 N 作一一對應：
1←→0、2←→1、3←→ -1、4←→2、5←→ -2、6←→3、7←→ -3、……
換句話說，如果一個集的所有元素可以「順序列出來」，則它是可數的：
0、1、-1、2、-2、3、-3、……
以下是兩個「證明」，大家看看有甚麼問題：
(1) 0 和 1 之間的所有實數（不包括 0 和 1）是可數的
證明：我們只需把 0 和 1 之間的所有實數「順序列出來」即可：
0.1, 0.2, 0.3, ..., 0.9, 0.01, 0.02, ..., 0.99, 0.001, 0.002, ..., 0.999, 0.0001, ...
(2) 所有以整數為系數的多項式是不可數的
證明：假設所有以整數為系數的多項式是可數的，則存在一一對應
1 ←→ a10 + a11x + a12x2 + a13x3 + ...
2 ←→ a20 + a21x + a22x2 + a23x3 + ...
3 ←→ a30 + a31x + a32x2 + a33x3 + ...
4 ←→ a40 + a41x + a42x2 + a43x3 + ...
......
考慮 f(x) = (a10+1) + (a21+1)x + (a32+1)x2 + (a43+1)x3 + ...，則顯然 f(x) 不等於以上任何一個多項式，這跟一一對應的意義矛盾，因此所有以整數為系數的多項式是不可數的。
2 則留言:
說起關於可數性的「証明」，以下這個fake的，我也想了一回才想到是甚麼一回事：
Prove that the power set of N is countable.
Reason:
For each subset of N, the sum of the elements is an integer k. For any k, the number of subsets that sum to k is finite (simple combinatorial argument). Let the collection of the subsets that sum to k be called P_k. Then the power set of N is just union of P_k for k from 1 to infinity, which is a countable union of finite sets, so is countable.
haha... I like this "proof"... it took me more time to figure out what's wrong than in my two "proofs", although the trick is essentially the same.
張貼留言